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