2012

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

Enseignant

• Frédéric Magniez

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

1. 04/01 Echauffement avec des exemples d'algorithmes probabilistes - Définition du modèle
2. 11/01 Autres algorithmes via des techniques de hachage - Algorithme probabiliste pour 2-SAT
3. 18/01 Marches aléatoires : 3-SAT et Connectivité
4. 25/01 PAS COURS -> DM à rendre par email au plus tard le 27/01 à 12h
5. 01/02 Algorithmes de streaming
6. 08/02 Complexité de la communication
7. 15/02 Preuves interactives : introduction, exemples, propriétés
8. 29/02 Introduction à l'information quantique, distribution quantique de clés, téléportation et superdense coding
9. 07/03 Algorithmes quantiques : premiers exemples et principes de la factorisation

Elèves du cours

Signaler erreurs et omissions à un des enseignants

1. Biswas Arindam
2. Bost Raphaël
3. Boutara Danai
4. Kumar Amrit
5. Lambert Aurélien
6. Maillasson Frédéric
7. Rerra Anna-Isavella

Evaluation

L'évaluation portera sur un travail personnel et un examen écrit.
Le travail personnel consistera à rendre un devoir maison et à 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. Biswas Arindam
2. Kumar Amrit
3. Maillasson Frédéric
4. PAS COURS
5. Lambert Aurélien
6. Bost Raphaël
7. Boutara Danai and Rerra Anna-Isavella