2013

Objectifs du cours

Ce cours fournit une présentation accessible des idées centrales de l'informatique moderne, et plus précisément concernant l'utilisation de l'aléatoire en algorithmique au sens large afin d'optimiser les ressources disponibles (temps, espace, communication, ...). Le cours se terminera par une ouverture à la théorie de l'information quantique, et des algorithmes quantiques.

Faire des choix aléatoires permet de concevoir des algorithmes plus rapides que leurs analogues déterministes pour de nombreux problèmes importants, tels que le test de primalité, la résolution de SAT, l'algorithmique de graphe ou encore certains problèmes algébriques. Une autre application cruciale des techniques probabilistes est la réduction de l'espace mémoire nécessaire pour résoudre un problème donné, comme cela est utilisé aujourd'hui dans les algorithmes de streaming. Dans ce dernier contexte, l'étude de la complexité repose sur la complexité de communication, une notion ayant aussi des applications dans l'optimisation des circuits imprimés.

L'étape ultime consiste à remplacer l'aléatoire par l'utilisation des phénomènes quantiques en informatique. Sans connaissance a priori de la mécanique quantique, il est possible d'aborder ces notions sous l'oeil neuf de l'informatique. Cette interprétation de paradoxes quantiques a donné lieu à des protocoles cryptographiques et à des algorithmes, n'ayant aucun analogue probabiliste.

Ce cours est avant tout destiné aux élèves du programme du département Informatique, ayant de préférence suivi le cours Conception et analyse des algorithmes.

Contenu du cours

Les domaines abordés seront :

• Algorithmes et techniques probabilistes
• Complexité en espace
• Algorithmes de streaming
• Complexité de la communication
• Preuves interactifs
• Ouverture sur l'informatique quantique

Enseignants

• Frédéric Magniez
• David Xiao pour les séances des 23 et 30 janvier

Déroulement du cours

Le cours se déroulera en PC 7 de 13h30 à 17h15.
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.

Les séances des 6 février et 13 mars sont annulées et remplacées par des séances supplémentaires, qui auront lieux trois fois afin de prendre en compte les disponibilités de chacun :

• Le 6 février est remplacé par une séance à choisir parmi
  • lundi 4 février matin (8h30-12h15) en PC 7
  • lundi 4 février après-midi (13h30-17h15) en PC 7
  • vendredi 8 février après-midi (13h30-17h15) en PC 6
• Le 13 mars est remplacé par une séance à choisir parmi
  • vendredi 22 février après-midi (13h30-17h15) en PC 7
  • lundi 25 février matin (8h30-12h15) en PC 7
  • lundi 25 février après-midi (13h30-17h15) en PC 7

Structure du cours

Le cours sera proche de celui donné en 2012.
Les archives de 2012 sont consultables.

1. 09/01 Echauffement avec des exemples d'algorithmes probabilistes - Définition du modèle
2. 16/01 Marches aléatoires : Connectivité et 2-SAT
3. 23/01 Graphes d'expansion : définition, propriétés et premières applications (cours donné par David Xiao)
4. 30/01 Graphes d'expansion : construction et application pour la réduction d'erreur (cours donné par David Xiao)
5. 04/02 ou 06/02 Algorithme de Shöning pour 3SAT - Algorithmes de streaming (séance en remplacement du 06/02)
6. 13/02 Algorithmes de streaming (suite)
7. 20/02 Complexité de la communication : notes de 2012
8. 22/02 ou 25/02 Introduction à l'information quantique, distribution quantique de clés, téléportation et superdense coding (séance en remplacement du 13/03) : notes de 2012
9. 27/02 Algorithmes quantiques : premiers exemples et principes de la factorisation : notes de 2012
   Transparents des deux dernières séances

Elèves du cours

Merci de signaler toute omission.

1. Aufrant Lauriane (abandon)
2. Covanov Svyatoslav
3. Deo Thierry
4. Fu Menglong
5. Gonzalez Suitt
6. Grosshans Nathan
7. Li Jia
8. Uribe Gavilano
9. Van Merriënboer Bart
10. Vegreville Matthieu
11. Wang Yan
12. Wenzek Guillaume

Evaluation

L'évaluation portera sur un travail personnel et un examen écrit le 20 mars 2012.
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 :

1. Aufrant Lauriane et Vegreville Matthieu
2. Van Merriënboer Bart et Wang Yan
3. Fu Menglong et Grosshans Nathan
4. Deo Thierry et Wenzek Guillaume
5. Covanov Svyatoslav
6. Gonzalez Suitt
7. Uribe Gavilano