intervenants: Christoph Dürr, Nguyễn Kim Thắng
[cote de la bibliothèque]
Ce plan peut être sujet à des ajustements. Toutes les séances sont de 8h30 à 10h00 pour le cours, puis de 10h15 à 11h45 pour les TDs.
Les deux séances sont dans l’amphi F3.05
Introduction.
Diviser pour régner: Compter le nombre d’inversions en O(n log n).
Glouton: Ordonnancement d’intervalles. Ordonnancer sur une machine pour minimiser le temps d’attente pondéré.
Plus long/court chemin dans un graphe orienté acyclique. Plus longue sous séquence commune. Multiplication d’une séquence de matrices. Voyageur de commerce.
Les deux séances sont dans les salles F209 et F210.
exercices : Exercice des cartes bancaires. Placement d’antennes. Problème de cache.
exercices : Arbre binaire de recherche optimal. Distance d’édition de Levenshtein. Corriger un mot bien parenthésé. Parenthéser une expression booléenne. Partage équitable. Rendu de monnaie.
Cours en F2.09, et TDs en F2.09 et F2.10.
Plus longue sous séquence croissante. Plus grand rectangle sous un histogramme.
exercices : Plus grand carré dans une grille. Plus long chemin dans un arbre. Jeux avec des pièces alignées. Pavage par des dominos.
Cours en F3.05, et TDs en F2.09 et F2.10.
Compter le nombre d'intersections pour un ensemble de segments données dans le plan.
exercices: finir ceux des feuilles précédentes.
Cours en F2.09, et TDs en F2.09 et F2.10.
Théorème max-flot min-coupe. Algorithme de Ford Fulkerson. Amélioration de Edmonds-Karp.
exercices : Problèmes réduisant au problème du flot maximum. corrigé
Annonce devoir maison.
Cours en F3.05, et TDs en F2.09 et F2.10.
exercices : Algorithme de Dinic ou de Goldberg et Tarjan. Couverture par sommets dans les graphes bipartis (Bipartite Vertex Cover). corrigé
Problèmes réduisant au problème du couplage.
Cours en sc.046 Bouygues, et TDs en F2.09 et F2.10.
Les classes P, NP. Preuves de NP-complétude. Réductions. Exemples: partition, Vertex Cover, etc.
Cours en F3.05, et TDs en F2.09 et F2.10.
Équilibrage de Charge. Algorithme de Christofides pour le problème de voyageur de commerce. Problème de sac à dos.
mes sources: [note de cours de Jelani Nelson, Page wikipedia, chapitre 9.2 de Algorithms par Dasgupta, Papadimiriou, Vazinari]
exercices. Couverture par sommets (Vertex Cover). Couverture des ensembles (Set Cover).
Cours en sc.046 Bouygues, et TDs en F2.09 et F2.10.
Tri rapide randomisé. Coupe minimale dans un graphe par Karger.
mes sources: chapitre 1 du livre de chapitre de Motwani et Raghavan. chapitre 13 du livre de Jeff Erickson.
exercices. Max 3-SAT, Médian, Collecteur de coupon. corrigé.
Examen en F2.09 et F2.10.
Toutes les notes sont autorisées. Mais pas de livres. Ni de calculatrices.