Mer 12/09/07 10h15: Produit de polynômes, Master theorem, Programmation dynamique (pièces de monnaie, sac à dos et chaînes de matrice). A faire: terminer le calcul de A(n) pour le produit de polynômes, et écrire l'algo pour le calcul des chaînes de matrices en respectant bien les dépendances. 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.
Attention pas cours mercredi 19/09!
Mer 26/09/07 10h15: Programmation dynamique (plus longue sous-suite), algorithmes gloutons (le gymnase, la route à suivre, et quelques gloutons de coloriage de graphes). A lire: la location de skis dans le poly (prog dyn).
Mer 03/10/07 10h15: Gloutons: coloriage de graphes et théorie des matroïdes.
Mer 10/10/07 10h15: Ordonnancement et tri rapide.
Attention pas cours mercredi 17/10!
Mer 24/10/07 10h15: Partiel
Jeu 25/10/07 08h00: Tri fusion, tri par tas, complexité du tri et tri petits nombres.
Mer 31/10/07 10h15: Introduction à la NP-complétude.
Mer 07/11/07 10h15: Principe de réduction, théorème de Cook, NP-complétude de 3-SAT et CLIQUE.
Mer 14/11/07 10h15: Vertex-cover: NP-complétude et approximation; NP-complétude de CH.
Mer 21/11/07 10h15: TSP et Bin-Packing: NP-complétude et approximation. A lire: NP-complétude des problèmes de coloriage de graphes.
Mer 28/11/07 10h15: 2-Partition: Gloutons, PTAS et FPTAS
Mer 05/12/07 10h15: Analyse amortie (1)
Mer 19/12/07 10h15: Analyse amortie (2)
Mer 09/01/08 10h15: Branch and Bound et Backtracking