Algorithmique I
Cours - Anne Benoit
TD - Victor Poupet et Damien Regnault
Page web des TDs
Cours
Version en cours de déboggage du poly: chapitres 1 à 5 + NP-complétude, cours uniquement [pdf].
Toutes remarques et corrections sont les bienvenues.
- 14/09/06: Calcul de x^n, Strassen, produit de
polynômes (à terminer chez soi)
- 22/09/06: Master Theorem, Programmation dynamique (pièces de
monnaie, sac à dos et chaînes de matrice).
A lire: résolution des récurrences dans le poly, la pièce de 18 centimes, et en
facultatif un
autre papier sur les pièces de
monnaies.
- 29/09/06: Prog dyn: la plus longue sous-suite. Exemple de la
location de ski à lire.
Algorithmes gloutons: le
gymnase et le sac à dos revu en rationnel.
- 06/10/06: Glouton: coloriage de graphes. Théorie des
matroïdes.
Trouver un contre-exemple pour montrer que
Brelaz n'est pas optimal, et finir de lire les
matroïdes dans le poly.
- 13/10/06: Glouton: matroïdes et ordonnancement. Tri fusion et tri par tas.
- 20/10/06: Pas cours. Attention, TD4 pour le groupe du vendredi.
- 27/10/06: PARTIEL.
- 03/11/06: Vacances.
- 10/11/06: Tri rapide, complexité du tri, tri petit nombres.
- 15/11/06: Attention, exceptionnellement, cours le mercredi à 13h30 et non le vendredi.
Introduction à la NP-complétude.
- 24/11/06: NP-complétude: Théorème de Cook, 3-SAT, Clique, Vertex-Cover, Cycle Hamiltonien, TSP.
- 01/12/06: Approximation: introduction, Vertex-Cover, TSP, Bin-Packing.
Si vous recherchez un algorithme d'approximation pour un problème donné, consultez le NP-Compendium qui liste les résultats d'approximation pour les problèmes NP. Notamment, les références pour l'algo du Vertex-Cover...
- 08/12/06: Approximation (suite de Bin-Packing) et NP-complétude (coloriage de graphes).
- 15/12/06: Pas cours le vendredi (visite de l'INRIA Sophia-Antipolis). Attention, exceptionnellement, cours le mercredi 13 à 13h30.
Approximation: 2-Partition, NP-Complétude au sens fort, PTAS et FPTAS.
- 22/12/06: Branch and Bound et Backtracking.
- 05/01/07: Analyse amortie.
- 12/01/07: Analyse amortie.
- Vendredi 19 Janvier, 9h-12h: EXAMEN
TDs: voir la page web
- TD1: Mardi 26/09 et Vendredi 29
- TD2: Mar 03/10 et Ven 06
- TD3: Mar 10 et Ven 13
- TD4: Mar 17 et Ven 20 à 10h15
- TD5: Ven 20 et Mar 24
- TD6: Ven 27 et Mar 07/11
- TD7: Ven 10 et Mar 14
- TD8: Ven 17 et Mar 21
- TD9: Ven 24 et Mar 28
- TD10: Ven 01/12 et Mar 5
- TD11: Ven 8 et Mar 12
- TD12: Mar 19 et Ven 22
- TD13: Mar 10/01 et Ven 12
Lien vers la page du cours à l'ENS
Anne Benoit (mail to Anne.Benoit at ens-lyon.fr)
Dernières modifications: 9 Janvier 2007