Initiation à l'Algorithmique Avancée :
Calculabilité, Complexité, Décidabilité
Édouard BELAGA

Institut de Recherche en Mathématique Avancée
7, rue René Descartes, bureau 310

tél. : 03 90 42 02 35
belaga@math.u-strasbg.fr

Le cours aura lieu :
Salle C15
UFR de Mathématique et Informatique
de 13h30 à 15h30 heures, les Mardis :
13, 20, 27 mai et 3, 10, 17 juin


Résumé :

    Depuis l'invention d'ordinateur, la science (informatique théorique) et la culture technique (informatique tout court) d'automatisation et de perfection du calcul et du traitement des données symboliques ont vécu une vraie révolution, et tout spécialement, ont fait un progrès énorme pendant les trente dernières années.
    A la base de ce progrès est le modèle classique d'algorithme, déjà introduit par Euclide, il y a plus que 2000 ans, mais rigoureusement défini et perfectionné depuis les années trente du XXième siècle. Nous étudierons ce modèle, ses mérites et ses limites. Ensuite, nous étudierons un modèle de calcul radicalement nouveau, dit quantique, inventé il y a moins de trente ans. Il ne subsiste aucun doute que ce modèle, encore très mal compris et difficilement réalisable, sera à la base de tout progrès futur.
    La physique quantique et les sciences de l'information partagent un champ d'investigations scientifiques devenu foisonnant, celui de l'information quantique. Certains phénomènes mis en évidence par la physique à l'échelle quantique sont désormais considérés sous l'angle de leur exploitation pour représenter, traiter et communiquer l'information. Ces travaux ont d'abord donné lieu à quelques splendides résultats théoriques : téléportation quantique, factorisation polynomiale des entiers, accélération quadratique du parcours d'une base de données. 




L'empêtrement des protons
                                       
L'empêtrement des protons. 


    Les premiers signes de confirmation expérimentale ont suivi quelques années plus tard : téléportation de l'état d'un photon, exécution des algorithmes de Grover, puis de Shor, par une machine quantique. Le traitement quantique de l'information paraît ainsi offrir une puissance de calcul hors de portée du traitement classique. Ce champ scientifique, encore dans sa petite enfance, est riche de questions ouvertes : sur l'algorithmique quantique et la complexité, sur l'information quantique, sur la traduction physique et l'expérimentation des algorithmes quantiques.

Teleportation Experiment

L'expérimentation de téléportation.


    Finalement, nous étudierons les limites logiques de tout traitement algorithmique des problèmes mathématiquement formalisables.





Plan du cours :

Chapitre 1. Calculabilité : instruments et modèles de calcul.

• 1. Représentations d'information et algorithmes classiques.

— 1.1. Des alphabets finis et représentation des entiers.

— 1.2. Calcul et circuits Booléens.

— 1.3. Algorithmes et machines de Turing.

— 1.4. Fonctions récursives.

— 1.5. La thèse de Church.

• 2. Information et calcul quantiques.

— 2.1. Information quantique.

— 2.2. Qubits multiples.

— 2.3. Circuits quantiques.

— 2.4. Algorithmes quantiques.

— 2.5. Ordinateur quantique : une réalisation physique.

Chapitre 2. Complexité : problèmes, modèles et méthodes.

• 3. Complexité algébrique.

3.1. Multiplication des entiers.

3.2. Multiplication des matrices.

• 4. Complexité combinatoire.

4.1. Complexité des mots enchaînés.

4.2. Complexité de Kolmogorov.

• 5. Complexité logique.

5.1. La fonction d'Ackermann.

5.2. La séquence de Goodman.

Chapitre 3. Décidabilité : problèmes et modèles.

• 6. Le problème d'arrêt d'une machine de Turing.

• 7. Théorème de Goedel.

• 8. Le ver et le jeu de hydre.

Bibliographie :

Patrick Dehornoy [1993] : Complexité et Décidabilité. Springer, Berlin.

Michael A. Nielsen, Isaak L. Chuang [2000] : Quantum Computation and Quantum Information. Cambridge, University Press.

Jan van Leeuwen [1990] : Algorithms and Complexity. Elsevier, Amsterdam.