|
Année 2012 Archives Autres |
AccueilEnglish version - The course will be given in english if one student does not understand french. Objectifs du coursCe 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 coursLes domaines abordés seront :
|