Du 1er au 5 février 2010 — ENS Lyon
Intervenants :
Emploi du temps: (Salle Amphi B de l’ENS-Lyon)
- Première partie: Lun. 14:00-18:00, Mar. 14:00-18:00, Merc. 9:00-13:00.
- Deuxième partie: Merc. 14:00-17:00, Jeu. 9:00-12:00 & 14:00-17:00, Ven. 9:00-12:00.
Résumé du cours :
Notre compréhension de ce qu'est un ordinateur (modèles de calculs) et de la manière
dont il peut résoudre des problèmes mathématiques(algorithmique) est en évolution
constante. Au-delà de l'approche traditionnelle, essentiellement fondée sur des
systèmes déterministes et discrets (automates etc.) , une nouvelle vision émerge
et qui se saisit des phénomènes probabilistes (aléatoire, approximation) et même
des phénomènes quantiques (interférence, enchevêtrement) en les concevant non plus
comme des difficultés à surmonter, mais comme de nouveaux outils offrant des
perspectives remarquables. Quelles sont les limites de l'approche traditionnelle et
qui sont franchies grâce à ces nouveaux outils? Jusqu'où peut-on éspèrer aller grâce
à eux?
Partie 1 (P.Arrighi, J.Degorre): Information quantique, causalité et automates cellulaires
La physique quantique a précisément mis en évidence des phénomènes extrêmement
utiles pour représenter, traiter et communiquer l'information. Ceci a donné
lieu dans les 15 dernières années à de splendides résultats théoriques qui
montrent que des performances quantitatives et qualitatives hors de portée de
l'informatique classique deviennent alors possibles. Ainsi il est prouvé
qu'un ordinateur quantique pourrait factoriser des nombres entiers en temps
polynomial, ou bien rechercher un élément parmi une liste désordonnée de
taille n en temps racine carrée de n. Ces résultats menacent la
cryptographie moderne; mais ce que la physique quantique prend d'une main
elle le redonne de l'autre. Ainsi des systèmes de transmission quantiques,
déjà commercialisés, permettent d'obtenir une sécurité prouvée et
inconditionnelle des communications. Ce cours effectuera d'abord tous les
rappels nécessaires en algèbre linéaire. Les postulats de la mécanique
quantique seront introduits, puis les principaux concepts et résultats connus
et ayant trait à la nature particulière et non-locale de l'information
quantique.
Le cours sera alors axé vers la quête d'un modèle de calcul à la fois quantique et
distribué, prenant en compte plusieurs des symmétries fondamentales de la physique
(causalité, invariance par translation). C'est ce qui nous amènera à aborder des
thèmes comme la causalité en mécanique quantique, les automates cellulaires dans
un tel contexte, et la nature des relations entre physique et calcul.
Plan:
- Rappels d'algèbre linéaire
- Postulats de la théorie quantique
- Explorations sur la nature de l'information quantique (Algorithme de Deutsch,
Non-disctinction d'états non-orthogonaux, No-cloning, Codage Super-dense,
Téléportation)
- Matrices de densité, opérateurs quantiques
- Enchevêtrement quantique (classification, boîtes non-locales)
- Opérateurs causaux et leur structure
- Automates cellulaires : trois définitions et leur équivalence
- définition axiomatique des automates cellulaires quantiques
- théorèmes de structure
- automates cellulaires quantiques universels
Partie 2 (F. Magniez): Algorithmique efficace
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 d'approximation. Les contextes modélisent les contraintes
exercées sur la machine concernant ses ressources (temps, espace, aléa, requête,
communication) et l'accès aux données (non contraint (random access) ou
séquentiel (streaming)).
Les domaines abordées seront donc :
- Marches aléatoires : k-SAT, (s,t)-CONNECTIVITY dans RL
- Graphes d'expansion (expander) : derandomizaton, (s,t)-CONNECTIVITY dans L
- Algorithmes d'approximation (approximation du résultat)
- Property testing (approximation sur l'entrée)
- Théorème PCP (version light) : application à des preuves de non approximation
- Streaming algorithms
- One-way communication complexity : application a des preuves de non
existence de streaming algorithms
Correspondant local
Pablo Arrighi