Mer 10/09/08 10h15: Introduction à l'algorithmique et aux notions
de complexité: calcul de x^n et algorithme de Strassen. Todo- réfléchir à la preuve du Th.2 (lim opt(n)/log(n)=1) avec
une méthode en base m (et comparer avec la solution du poly).
Jeu 11/09/09 10h15: On pousuit diviser-pour-régner avec le
"master theorem", l'inversion de matrices et le produit de
polynômes. Introduction à la programmation dynamique (pièces de monnaies). Todo- Lire la section 2.4 "Résolution des
récurrences" - Compter les additions et
multiplications dans un produit de polynôme et résoudre les
récurrences obtenues - Exercice 1.7.1 "Le grand saut" - En bonus quelques lectures de programmation dynamique:
la pièce de 18 centimes, et un autre
papier sur les pièces de monnaies.
Attention pas cours mercredi 17/09!
Mer 24/09/08 10h15: Suite de la programmation dynamique: le sac à
dos, les chaînes de matrices, plus longue sous-suite
commune. Démarche générale du programmeur dynamique. Todo- Lire la section 3.3.3 "Location de skis" (et chercher la
solution avant de lire la réponse ;-) )
Mer 01/10/08 10h15: Les algorithmes gloutons: l'exemple du
gymnase et coloriages de graphe. Démarche de
l'algorithmicien glouton. Todo- Finir de trouver des contre-exemples pour les divers
gloutons inventés en cours. Et bosser sur le DM :-).
Mer 08/10/08 10h15: Fin du chapitre glouton: graphes d'intervalles, théorie des matroïdes
et ordonnancement. Todo- Un peu de lecture pour les curieux: approfondir
les graphes d'intervalles et découvrir
l'article qui a introduit les matroïdes.
Mer 15/10/08 10h15: Le tri: médiane en temps linéaire, et
complexité du tri (au pire, en moyenne).
Mer 22/10/08 10h15: Peut-on atteindre la borne du tri dans le
pire cas? et introduction à la NP-complétude. Todo- Réviser pour le partiel ;-) et s'initier aux machines de
Turing grâce à la feuille que je vous ai distribuée (c'est un extrait
du livre de Wilf, "Algorithmes et Complexité").
Mer 29/10/08 10h15: Partiel
Mer 05/11/08 10h15: Les problèmes NP-complets et les réductions:
Théorème de Cook et 3-SAT. Todo- Lire et comprendre en détail le théorème de Cook (feuille
distribuée en cours, toujours extrait du livre de Wilf).
Attention pas cours mercredi 12/11!
Mer 19/11/08 10h15: NP-complétude de clique et vertex-cover,
2-approximation de vertex-cover (classique et pondéré),
NP-complétude de cycle-hamiltonien. Todo- Lire la NP-complétude des problèmes de coloriage de graphes.