Recherche avancée
Libres Savoirs >> Informatique >> Informatique
Responsable :

Frédéric MAGNIEZ
  


Centre de Recherche

Niveau : Graduate

Langue du cours : Français

Période : Automne

Nombre d'heures : 36

Crédits ECTS : 4
INF554 Utilisation de l'aléatoire en algorithmique
Ressources Pédagogiques :
IIl y a plusieurs manière d'utiliser l'aléatoire en informatique. On peut étudier le comportement d'un processus informatique (programme, protocole, automate, …) face à un modèle aléatoire, ou encore construire des générateurs d'instances aléatoires (séquences, arbres, graphes, …) à des fins applicatives. Une autre approche, celle de ce cours, considère l'aléatoire comme une nouvelle ressource permettant de résoudre plus efficacement certains problèmes. Par exemple, on ne sait pas générer un nombre premier sans tirer au sort, ou encore la congestion dans les réseaux ne peut pas être évitée sans un protocole de routage en partie aléatoire.

De manière contre-intuitive, prendre des décisions au hasard permet de concevoir des algorithmes plus simples et souvent plus efficaces que leurs analogues déterministes. Les domaines et les applications sont vastes. Ce cours fournit une présentation accessible à la plupart de ces derniers et de leurs idées centrales. Chacune de ces idées sera présentée à travers des exemples simples et motivés.

Nous commencerons par acquérir un certain nombre de méthodes et outils à travers des problèmes fondamentaux de l'informatique, incluant le test de primalité, la résolution de problèmes SAT, l'algorithmique de graphe ou encore certains problèmes algébriques.
Puis nous étudierons les algorithmes de streaming, où l'utilisation de l'aléatoire est cruciale afin de réduire l'espace mémoire de ces algorithmes qui manipulent des données de taille gigantesque. L'étude en complexité de ces algorithmes est liée au modèle de la complexité de la communication. Ce modèle a de multiples applications, comme dans l'optimisation des circuits imprimés.
L'utilisation de l'aléatoire permet aussi de revisiter et d'enchérir la notion de preuve, comme nous le verrons lors de l'étude des preuves interactives probabilistes.
Enfin, l'étape ultime consiste à remplacer l'utilisation de phénomènes probabilistes par l'utilisation de phénomènes quantiques. Sans connaissance a priori de la physique quantique, il est possible d'aborder cette dernière sous le regard neuf de l'informatique. Cette interprétation des paradoxes quantiques a donné lieu à des protocoles cryptographiques et à des algorithmes, n'ayant aucun analogue probabiliste.

Les domaines abordés seront :
- Classes de complexité probabilistes
- Techniques d'amplification d'erreur
- Principe de hâchage
- Marches aléatoires en algorithmique
- Méthodes de dérandomisation
- Algorithmes de streaming
- Complexité de la communication
- Preuves interactives
- Ouverture sur l'informatique quantique

Niveau requis : Ce cours ne nécessite aucun prérequis particulier. En revanche, un minimum de connaissances algorithmiques (principalement) et de probabilités discrètes (secondairement) peuvent aider. Tous les outils probabilistes ainsi que les notions (élémentaires) de physique quantique nécessaires seront introduits durant le cours. Ce cours est complémentaire des cours Conception et analyse des algorithmes et Randomization in Computer Science: Games, Networks, Epidemic and Evolutionary Algorithms, mais peut être suivi indépendamment.

Modalités d'évaluation : L'évaluation consistera en un travail personnel (rédaction de notes de cours, DM ou projet), ainsi qu'un examen écrit. Elle sera précisément déterminée lors du premier cours.

Dernière mise à jour : dimanche 2 mars 2014

© Ecole Polytechnique 2014 - Réalisé par Winch Communication