| Vendredi
18 janvier 2013 16h15-18h15 |
Analyse
en moyenne et séries génératrices I) Motivation : nombre d'affectations dans la recherche dans un tableau 1) Algorithme
II) Séries génératrices2) Définition de la complexité en moyenne 3) Relation de récurrence 1) Un anneau
III) Un peu de dénombrements2) Dérivées et intégrations 1) Sans répétition
IV) Résoudre des relations de récurrence2) Avec répétition 3) Un exemple fruité V) Complexité en moyenne et NP-complétude Discussions autour
d'articles de recherche...
|
| Jeudi 24 janvier 2013 14h-16h |
TD |
| Jeudi 31 janvier 2013 14h-16h |
Analyse
amortie I) Motivation a) Problème avec
l'analyse dans le pire des cas / moyenne
II) Deux points de vue (raconté avec l'exemple du tableau dynamique)
ex : Image du bureau désorganisé b) Définition = moyenne sur une séquence du pire des cas a) Méthode comptable
III) Union-find (avec le point du vue du banquier)
IV) Tas de Fibonacci (avec le point du vue du physicien)
~ Discussion avec un banquier b) Méthode du potentiel ~ Discussion avec un physicien |
| Jeudi 7 février 2013 14h-16h |
TD |
| Jeudi 14 février 2013 14h-16h |
Algorithmes
d'approximation I) Introduction : quoi faire face à NP a) Réduire
l'ensemble des entrées possibles
II) Algorithme approximant à un facteur constantb) Être moins exigeant 1) Vertex cover
III) Borne en log(n)a) Algorithme naïf
2) Weighted vertex cover - relaxation linéaireb) Algorithme via maximal matching 3) Voyage de commerce avec inégalités triangulaires a) Algorithme
2-approximant
b) Algorithme de Christofides 1) Set cover
IV) Aussi approximant qu'on le souhaite1) Principe général
2) Sac à dos via programmation dynamique |
| Jeudi 21 février 2013 14h-16h |
TD |
| Jeudi 7 mars 2013 14h-16h |
V) Inapproximabilité Inapproxabilité du
voyage de commerce si P != NP
Algorithme probabiliste : Las Vegas et Monte Carlo I) Rappels de probabilités II) Contrer les attaques : tri rapide, Las Vegas III) Monte Carlo : coupe minimale IV) Classes de complexité |
| Jeudi 14 mars 2013 14h-16h |
TD |
| Jeudi 21 mars 2013 14h-16h |
La
méthode probabiliste I) Introduction avec MAX-CUT 1) Montrer l'existence de coupe assez grande II) Nombres de Ramsey2) Dérandomisation 3) Etat de l'art sur MAX-CUT III) Lemme local de Lovász 1) Enoncé
1) Un exemple stupide : coloriage d'un cycle 2) Satisfiabilité d'une k-CNF avec contraintes sur les variables |
| Jeudi 28 mars 2013 14h-16h |
TD |
| Jeudi 4 avril 2013 14h-16h |
Algorithme
quantique Magnets chats I) Comparaison modèle classique/quantique II) Etat d'un système
1) Etats physiques
III) Mesures2) Superposition 3) Produits tensoriels 1) Mesure d'un état entier
IV) Circuits d'une machine quantique2) Mesure partielle V) Algorithme de Deutsch-Jozsa VI) Algorithme de Grover Animation de l'algorithme de Grover (avec des chats) |
| Jeudi 11 avril 2013 10h15-12h15 et 14h-16h |
Soutenance des projets |