2011

Objectifs du cours

Notre compréhension de ce qu'est un ordinateur et de la manière dont il peut résoudre des problèmes est en évolution constante. Au-delà de l'approche traditionnelle, essentiellement fondée sur des systèmes déterministes, une nouvelle vision émerge, qui se saisit des phénomènes probabilistes, et même des phénomènes quantiques, en les concevant non plus comme des difficultés à surmonter, mais comme de nouveaux outils offrant des perspectives remarquables.

Le but du cours est d'aborder les techniques permettant d'élaborer des algorithmes efficaces dans plusieurs contextes. Les techniques reposent sur des outils probabilistes et quantiques. Les contextes modélisent les contraintes exercées sur les ressources disponibles (temps, espace, aléa, requête, communication) et sur l'accès aux données (non contraint ou séquentiel).

Ce cours est à destiné aux élèves du programme d'approfondissement d'Informatique, ayant de préférence suivi les cours Conception et analyse des algorithmes et Théorie de l'information. Il est aussi conseillé de suivre en parallèle le cours Algorithmes et complexité.

Contenu du cours

Les domaines abordés seront :

• Information et cryptographie quantique
• Complexité de la communication : déterministe, probabiliste et quantique
• Algorithmes probabilistes : marches aléatoires, algorithmes sous-linéaires, algorithmes de streaming
• Algorithmes quantiques : marches quantiques, factorisation

Enseignants

• Frédéric Magniez
• David Xiao

Déroulement du cours

Le cours est donné au tableau. Les notes de cours sont rédigées par les élèves et font partie de l'évaluation du cours.

Structure du cours

Lundi, 13h30 - 17h15, PC 17

1. 03/01 (FM) : Echauffement avec des exemples d'algorithmes probabilistes - Définition du modèle
2. 17/01 (FM) : Algorithmes probabilistes pour SAT
3. 24/01 (FM) : Marches aléatoires
4. 31/01 (DX) : Preuves interactives : introduction, exemples, propriétés
5. 07/02 (DX) : Preuves à divulgation nulle (zero-knowledge proofs)
6. 14/02 (FM) : Introduction à l'information quantique, distribution quantique de clés
7. 28/02 (FM) : Paradoxe EPR et applications~: superdense coding, téléportation quantique
   Notes en 2010 : parties 3.2.1, 3.2.3 et 3.2.4 du cours 3-2
8. 07/03 (FM) : Algorithmes quantiques évolués : premiers exemples, factorisation
   Notes en 2010 : cours 6-1 (preuve de la partie 6.2 sans matrices densités) et cours 7 (rapidement pour la partie 7.2.3)
9. 14/03 (FM) : Algorithmes quantiques : suite et fin du cours précédent

Elèves du cours

Signaler erreurs et omissions à un des enseignants

1. DO Quoc Khanh
2. FAURE Julien
3. LORENZI Pierre
4. MALAGA SABOGAL Alba Marina
5. PREVOST Romain
6. ROUGE Jean

Evaluation

L'évaluation portera sur un travail personnel et un examen écrit le 21/03 de 13h30 à 16h30.
Le travail personnel consistera à rédiger des notes de cours de manière seule ou partagée. Au début de chaque cours, un élève ou binôme sera désigné pour la rédaction des notes de ce cours. La participation est obligatoire.

Notes de cours

Les notes de cours seront rédigées en LaTeX avec le package scribe.sty (adapté du script de Jeff Erickson).
Consulter le modèle exemple.tex, exemple.pdf.

Répartition :

• Cours 1 (FM) : FAURE Julien
• Cours 2 (FM) : DO Quoc Khanh
• Cours 3 (FM) : ROUGE Jean
• Cours 4 (DX) : PREVOST Romain
• Cours 5 (DX) : MALAGA SABOGAL Alba Marina
• Cours 6 (FM) : LORENZI Pierre
• Cours 7 (FM)
• Cours 8 (FM)
• Cours 9 (FM)