Existem aplicações de técnicas em análise real para a ciência da computação teórica?

Eu procurei em todo o lado essas aplicações e, na maioria das vezes, acabei ficando curto. Posso encontrar muitas aplicações de topologia e estruturas semelhantes em conjuntos contáveis ​​(ou incontáveis), mas raramente encontro conjuntos incontáveis ​​como objeto de estudo por cientistas da computação e, portanto, levando à necessidade de técnicas de análise.

Aqui estão dois cursos relacionados:

• Métodos analíticos em combinatória e CS por Ehud Friedgut na Universidade de Toronto (2009),
• Métodos Analíticos em Combinatória e Ciência da Computação por Irit Dinur e Ehud Friedgut na Universidade Hebraica (2006).

Verifique também as notas de Ryan O'Donnell para o seu livro:

• Análise de funções booleanas por Ryan O'Donnell.

e os links no canto superior direito.

Veja o livro Concrete Mathematics - A Foundation for Computer Science de Graham, Knuth e Patashnik. No capítulo 9, eles explicam a fórmula da soma de Euler-Maclaurin . Essa é uma técnica que permite aproximar uma soma finita usando integrais. No mesmo capítulo, página 466, eles usam essa técnica para aproximar o número harmônico (que aparece muito em várias áreas do TCS). Aconteceu-me uma vez que eu tive que usá-lo e acabei resolvendo uma integral usando técnicas de aproximação assintótica para equações diferenciais!

Existe a teoria dos limites das seqüências densas de grafos, desenvolvida no trabalho de Lovasz e B. Szegedy. Isso tem implicações para certos problemas de teste de propriedade em gráficos. Veja http://www.cs.elte.hu/~lovasz/hom-stoc.pdf . Basicamente, a idéia é que eles definam uma métrica adequada nos gráficos e uma noção de limites de seqüências gráficas e depois mostrem que uma propriedade do gráfico é testável se a função que mapeia um gráfico para a distância de edição da propriedade é contínua na espaço métrico nos gráficos que foram definidos.

E, claro, existe a magnum opus de Flajolet e Sedgewick dedicada inteiramente ao uso de métodos analíticos para análise assintótica de estruturas combinatórias, incluindo análise de algoritmos. Isso está gerando principalmente truques de funções que dependem de análises complexas

Como Shir mencionou, a desigualdade de Jensen aparece o tempo todo. Especialmente em provar limites em problemas combinatórios. Por exemplo, considere o seguinte problema:

Dada uma família de dos subconjuntos de V = { 1 , … , n } , seu gráfico de interseção G = ( V , E ) é definido por { i , j } ∈ E se e somente se S i ∩ S j ≠ ∅ . Suponhamos que o tamanho médio do conjunto seja r e que o tamanho médio das interseções aos pares seja no máximo k. Mostre que$S_1, \ldots, S_n$$V = \{1, \ldots, n\}$$G = (V, E)$$\{i, j\} \in E$$S_i \cap S_j \neq \emptyset$$r$$|E| \geq \frac{n}{k} \cdot \binom{r}{2}$ .

Prova:

Vamos contar os pares modo que e . Vamos primeiro corrigir , vemos que existem no máximo tais opções. Tomando todos os valores de também, temos um limite superior de. Agora corrigimos x. É fácil ver que cada tem maneiras de escolher . Pela desigualdade de Jensen, temos:x ∈ V x ∈ S i ∩ S j ( S i , S j ) k ( S i , S j ) k ⋅ ($(x, (S_i, S_j))$$x \in V$$x \in S_i \cap S_j$$(S_i, S_j)$$k$$(S_i, S_j)$x ( d(x$k \cdot \binom{n}{2} = k \cdot |E|$$x$ (Si,Sj$\binom{d(x)}{2}$$(S_i, S_j)$

$n \cdot \binom{r}{2} = n \cdot \binom{\frac{1}{n}\sum_x d(x)}{2} \leq \sum_x \binom{d(x)}{2} \leq k \cdot |E|$.

Finalmente combinamos termos para ter.$\frac{n}{k} \cdot \binom{r}{2} \leq |E|$

Embora isso seja um pouco mais "matemático" que o CS, ele serve para mostrar como uma ferramenta para funções convexas pode ser usada - especialmente na otimização combinatória.

que tal computação eficiente com Dedekind Reals, de Andrej Bauer e Paul Taylor.

Uma técnica muito comum e muitas vezes útil ao abordar um problema em matemática discreta é incorporá-lo em um domínio contínuo, pois isso permite que uma escolha mais rica de ferramentas matemáticas seja empregada. Portanto, corrigindo minha resposta: além dos campos em que a análise real aparecerá naturalmente (gráficos, processamento de sinais e outros campos que imitam ou interagem com o mundo físico), ela aparece basicamente em todos os lugares e em lugares que não - o meu acho que será no futuro.

Alguns exemplos rápidos:

1. Erro ao corrigir códigos: os códigos Reed salomão usam polinômios. Alguns limites nos códigos envolvem a visualização da função indicadora do código como uma função do cubo discreto aos reais, aplicando a transformação de Fourier e outras técnicas.
2. O método probabilístico - teoremas de concentração de medida (uma ferramenta analítica) são usados ​​para mostrar várias propriedades de gráficos aleatórios (por exemplo, número cromático). Veja o livro de Alon e Spencer.

3. O teorema de intersecção (isto é mais relacionada com Combinatória, mas de qualquer forma) - um gráfico com vértices e bordas tem pelo menos intersecções. A prova envolve pegar um gráfico aleatório e otimizar os parâmetros via derivação.e $v$$e$$\frac {1}{61} \cdot \frac {e^3} {v^2}$

4. O compartilhamento secreto de Shamir usa o fato de que um polinômio grau diferente de zero é definido exclusivamente por pontos (ele se baseia no fato de que pontos fornecem informações praticamente nulas).k k - $k-1$$k$$k-1$

Se eu me lembro corretamente, o teorema de Noga Alon sobre a divisão de colares usa a versão contínua do problema.

Veja: http://www.cs.tau.ac.il/~nogaa/PDFS/nocon.pdf

Também há uma menção a isso na página wiki aqui: http://en.wikipedia.org/wiki/Hobby%E2%80%93Rice_theorem

O campo da medida limitada a recursos aplica a medida de Lebesgue às classes de complexidade. A idéia é obter separações entre classes de complexidade, falando sobre os "tamanhos" relativos desses conjuntos.

Existe um belo artigo: a comunicação quântica unidirecional é exponencialmente mais forte que a comunicação clássica de Boaz Klartag & Oded Regev, que usa um número bastante grande de técnicas de análise real que são incomuns no TCS, incluindo a transformação Radon, harmônicas esféricas e hipercontrativas desigualdades na esfera unitária (não discreta)

Um limite inferior exponencial para o tamanho de circuitos reais monótonos (1997) por Haken, Cook

Eu sempre achei as conexões entre linguagens regulares / livres de contexto e séries de poder (formais) de teoria da função bastante empolgantes: é por isso que os franceses chamam essas classes de linguagem de "racionais" e "algébricas". Isso também indica conexões com a geometria fractal. De maneira semelhante, por exemplo, autômatos finitos podem definir idiomas em palavras infinitas que possuem boas propriedades topológicas quando equipadas com a topologia métrica padrão.

Outra conexão pode ser a teoria recentemente desenvolvida de "convoluções de conjuntos" que permite acelerar vários algoritmos semelhantes ao que é conhecido nas transformadas de Fourier. Suponho que essas sejam pelo menos "semelhanças inspiradoras".