Existe-t-il des applications des techniques d'analyse réelle à l'informatique théorique?

J'ai cherché loin pour de telles applications et je me suis surtout retrouvé court. Je peux trouver de nombreuses applications de la topologie et des structures similaires sur des ensembles dénombrables (ou non dénombrables), mais je trouve rarement des ensembles indénombrables comme objet d'étude par des informaticiens, et donc conduisant à la nécessité de techniques d'analyse.

Voici deux cours connexes:

• Méthodes analytiques en combinatoire et CS par Ehud Friedgut à l'Université de Toronto (2009),
• Méthodes analytiques en combinatoire et informatique par Irit Dinur et Ehud Friedgut à l'Université hébraïque (2006).

Consultez également les notes de Ryan O'Donnell pour son livre:

• Analyse des fonctions booléennes par Ryan O'Donnell.

et les liens dans le coin supérieur droit.

Voir le livre Concrete Mathematics - A Foundation for Computer Science de Graham, Knuth et Patashnik. Au chapitre 9, ils expliquent la formule de sommation d'Euler-Maclaurin . Il s'agit d'une technique qui vous permet d'approximer une somme finie en utilisant des intégrales. Dans le même chapitre, page 466, ils utilisent cette technique pour approximer le nombre harmonique (qui apparaît beaucoup dans plusieurs domaines du TCS). Cela m'est arrivé une fois où je devais l'utiliser et j'ai fini par résoudre une intégrale en utilisant des techniques d'approximation asymptotique pour les équations différentielles!

Il y a la théorie des limites des séquences de graphes denses, développée dans les travaux de Lovasz et B. Szegedy. Cela a des implications pour certains problèmes de test de propriétés sur les graphiques. Voir http://www.cs.elte.hu/~lovasz/hom-stoc.pdf . Fondamentalement, l'idée est qu'ils définissent une métrique appropriée sur les graphiques et une notion de prise de limites des séquences de graphiques, puis ils montrent qu'une propriété de graphique est testable si la fonction qui mappe un graphique à la distance d'édition de la propriété est continue dans le espace métrique sur les graphiques qui a été défini.

Et puis il y a bien sûr Flajolet et Sedgewick magnum opus de entièrement dédié à l'utilisation de méthodes analytiques pour l'analyse asymptotique des structures combinatoires, y compris l'analyse des algorithmes. Cela génère principalement des astuces de fonction reposant sur une analyse complexe

Comme Shir l'a mentionné, l'inégalité de Jensen apparaît tout le temps. Surtout pour prouver les limites des problèmes combinatoires. Par exemple, considérez le problème suivant:

Étant donné une famille de de sous-ensembles de V = { 1 , … , n } , son graphe d' intersection G = ( V , E ) est défini par { i , j } ∈ E si et seulement si S i ∩ S j ≠ ∅ . Supposons que la taille moyenne définie est$S_1, \ldots, S_n$$V = \{1, \ldots, n\}$$G = (V, E)$$\{i, j\} \in E$$S_i \cap S_j \neq \emptyset$ et que la taille moyenne des intersections par paires soit au plus k. Montre CA$r$ .$|E| \geq \frac{n}{k} \cdot \binom{r}{2}$

Preuve:

Comptons les paires telles que x ∈ V et x ∈ S i ∩ S j . Fixons d'abord ( S i , S j ) , nous voyons qu'il y a au plus k tels choix. En prenant également toutes les valeurs de ( S i , S j ) , nous avons une borne supérieure de 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)$. Nous corrigeons maintenant x. Il est facile de voir que chaquexa ( d(x$k \cdot \binom{n}{2} = k \cdot |E|$$x$ façons de choisir(Si,Sj$\binom{d(x)}{2}$$(S_i, S_j)$ . Par l'inégalité de Jensen, nous avons:

$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|$.

Nous combinons enfin les termes pour avoir .$\frac{n}{k} \cdot \binom{r}{2} \leq |E|$

Bien que ce soit un peu plus "mathématique" que CS, cela sert à montrer comment un outil pour les fonctions convexes peut être utilisé - en optimisation combinatoire, en particulier.

que diriez-vous du calcul efficace avec Dedekind Reals par Andrej Bauer et Paul Taylor.

Une technique très courante et souvent utile pour aborder un problème en mathématiques discrètes consiste à l'intégrer dans un domaine continu, car cela permet d'utiliser un choix plus riche d'outils mathématiques. Donc, corrigeant ma réponse: à part les champs dans lesquels une véritable analyse apparaîtra naturellement (graphiques, traitement du signal et autres champs qui imitent ou interagissent avec le monde physique), elle apparaît essentiellement partout, et dans des endroits où elle n'avait pas - mon je suppose que ce sera le cas à l'avenir.

Quelques exemples rapides:

1. Codes d'erreur de correction: les codes Reed Solomon utilisent des polynômes. Certaines limites des codes impliquent de visualiser la fonction d'indicateur du code comme une fonction du cube discret aux réels, appliquant ainsi la transformée de Fourier et d'autres techniques.
2. La méthode probabiliste - mesurer les théorèmes de concentration (un outil analytique) est utilisée pour montrer diverses propriétés des graphiques aléatoires (par exemple le nombre chromatique). Voir le livre d'Alon et Spencer.

3. Le théorème d'intersection (c'est plus lié à la combinatoire, mais de toute façon) - un graphe avec sommets et arêtes e a au moins $v$$e$ intersections. La preuve consiste à prendre un graphe aléatoire et à optimiser les paramètres via la dérivation.$\frac {1}{61} \cdot \frac {e^3} {v^2}$

4. $k-1$$k$$k-1$

Si je me souviens bien, le théorème de Noga Alon sur la division des colliers utilise la version continue du problème.

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

Il y a aussi une mention de cela dans la page wiki ici: http://en.wikipedia.org/wiki/Hobby%E2%80%93Rice_theorem

Le domaine de la mesure liée aux ressources applique la mesure de Lebesgue aux classes de complexité. L'idée est d'obtenir des séparations entre les classes de complexité en parlant des «tailles» relatives de ces ensembles.

Il y a un beau papier, la communication unidirectionnelle quantique est exponentiellement plus forte que la communication classique par Boaz Klartag & Oded Regev, qui utilise un assez grand nombre de techniques d'analyse réelle qui sont rares dans TCS, y compris la transformation de Radon, les harmoniques sphériques et hypercontractif inégalités sur la sphère unitaire (non discrète)

Une limite inférieure exponentielle pour la taille des circuits réels monotones (1997) par Haken, Cook

J'ai toujours trouvé les connexions entre les langages réguliers / sans contexte et la théorie des fonctions (séries de pouvoirs (formelles)) assez excitantes: c'est pourquoi les Français appellent ces classes de langues "rationnelles" et "algébriques". Cela indique également des liens avec la géométrie fractale. Dans la même veine, par exemple, les automates finis peuvent définir des langues sur des mots infinis qui ont de belles propriétés topologiques lorsqu'ils sont équipés de la topologie métrique standard.

Une autre connexion pourrait être la théorie récemment développée des «convolutions d'ensemble» qui permet d'accélérer plusieurs algorithmes similaires à ce qui est connu des transformées de Fourier. Je suppose que ce sont au moins des "similitudes inspirantes".