Théories des calculs

Code APOGÉE : IFJCE410 | 6 ECTS | Enseignant : Olivier Bournez | Validation : examen
Horaires hebdomadaires : 2h CM | Mutualisé avec : M2 MPRI

Titre complet : Complexity over the Reals

Motivation et objectifs du cours

Ce cours traite de la théorie du calcul (calculabilité et complexité) pour les calculs sur les nombres réels.

Il s’agit d’un cours classique de complexité et calculabilité mais appliqué aux questions sur les nombres réels ou les fonctions sur les nombres. Il couvre également des modèles basés sur les circuits, ou des modèles algébriques.

Prérequis

Notions de base d’informatique théorique (machines de Turing, NP-complétude, P, NP, etc.)

Description du cours

Nous introduirons diverses façons de modéliser et d’étudier la complexité des algorithmes sur les nombres réels :

Analyse calculable

Un réel est vu comme une séquence de nombres rationnels convergents, et on considère les machines de Turing transformant les séquences rationnelles en séquences rationnelles.

Complexité des modèles d’apprentissage profond

Les modèles d’apprentissage profond (réseaux de neurones) sont des modèles particuliers de calcul traitant des nombres réels. Comment peut-on mesurer la complexité associée ?

Modèles de calcul en temps continu

Que peut-on calculer en utilisant l’électronique analogique, ou les circuits ?

Langue du cours

Anglais sur demande ⇒ ANGLAIS pour 2024.

Évaluation 2024

• Un devoir à la maison servant d’examen de mi-parcours
• Un examen écrit final le jeudi 28 novembre 2024 (matin, horaire habituel du cours) – tous documents autorisés

Programme détaillé (Édition 2024)

Cours 1 : Introduction, motivation, tentative de démonstration sur THAT. Analyse calculable : réels calculables, Machine de Turing de Type 2, notation, représentation, fonction calculable. Le calculable implique la continuité.

Cours 2 : Théorème des valeurs intermédiaires : diverses déclarations calculables/incalculables. Calculabilité vs Continuité.

Cours 3 : Calculabilité vs Continuité (suite). Caractérisations alternatives des fonctions calculables. Énoncé de quelques résultats sélectionnés de la calculabilité. Théorème de Myhill et sa preuve.

Cours 4 : Complexité en analyse calculable : l’approche du livre de Ker I Ko. Résultats sélectionnés.

Cours 5 : Complexité des opérateurs en analyse calculable : quelques problèmes de base. L’approche de Kawamura & Cook.

Cours 6 : Complexité des opérateurs en analyse calculable : quelques exemples d’applications. Calcul sur une structure arbitraire. Le modèle BSS.

Cours 7 : La classe de complexité ∃R (aussi connue sous le nom d’ETR). Exemple de problèmes ∃R-complets. Problèmes de recherche totale. TFNP, FNP, complétude. La classe PPAD. La complexité des problèmes de descente de gradient.

Cours 8 : La complexité des problèmes de descente de gradient (suite). Modèles de calcul en temps continu. Le GPAC.

Bibliographie

• Weihrauch, K. (2000). Computable Analysis: an introduction. Berlin : Springer.
• Brattka, V., Hertling, P., & Weihrauch, K. (2008). A tutorial on computable analysis. In S. Barry Cooper, B. Löwe, & A. Sorbi (Eds.), New Computational Paradigms: Changing Conceptions of What is Computable (pp. 425-491). New York : Springer.
• Blum, L., Cucker, F., Shub, M., & Smale, S. (1998). Complexity and real computation. New York : Springer Science & Business Media.
• Poizat, B. (1995). Les petits cailloux (Vol. 995). Lyon : Aléas.
• Koiran, P. (1994). Computing over the reals with addition and order. Theoretical Computer Science, 133(1), 35-47.
• Koiran, P. (1997). A weak version of the Blum, Shub, and Smale model. Journal of Computer and System Sciences, 54(1), 177-189.