|
2014-15 Archives |
2014Objectifs du coursIl 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. 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. Contenu du coursLes domaines abordés seront :
EnseignantDéroulement du coursLe cours se déroulera les lundis de 13h30 à 17h15, à partir du lundi 23 septembre. Structure du coursLe cours sera proche de celui donné en 2012-13.
Elèves du cours
EvaluationL'évaluation portera sur un travail personnel et un examen écrit le lundi 9 décembre. Notes de coursLes notes de cours seront rédigées en LaTeX avec le package scribe.sty (adapté du script de Jeff Erickson). Répartition :
|