Jeu 10/09 8h: Introduction à l'algorithmique et aux notions
de complexité: calcul de x^n et algorithme de Strassen. Todo- Finir de compter les additions et les multiplications
nécessaires dans un produit de polynômes.
Mer 16/09 10h15: On pousuit diviser-pour-régner avec le
"master theorem" et l'inversion de matrices.
Introduction à la programmation dynamique (pièces de monnaies). Todo- Lire la section 2.4 "Résolution des
récurrences" - En bonus quelques lectures de programmation dynamique:
la pièce de 18 centimes, et un autre
papier sur les pièces de monnaies.
Mer 23/09 10h15: Programmation dynamique: le sac à
dos, les chaînes de matrices, plus longue sous-suite
commune. Démarche générale du programmeur dynamique.
Introduction à la démarche du programmeur glouton. Todo- Lire la section 3.3.3 "Location de skis" (et chercher la
solution avant de lire la réponse ;-) )
Mer 30/09 10h15: Algorithmes gloutons: le gymnase et le
sac-à-dos, et les coloriages de graphes. Démarche du programmeur
glouton: recherche de contre-exemples et preuves d'optimalité. Todo- Chercher un contre-exemple pour l'algorithme de
Brelaz. DM-Devoir
Maison (à rendre le 28 octobre). Attention: corrections par
rapport à la version initiale:
Exo1 Question 7 (gamma > beta);
Exo3 Question 1 (On notera Popt(n) la somme minimum des gains
avec 2n jetons. (et pas n jetons));
Exo3 Question 5 (2i-1 et 2i à la place de 2n-1 et 2n);
Exo4 Question 4c (Vérifier que g(t) est une solution de
f(t) = 1 + t(f(t))^2, et non pas l'équation d'avant qui était juste mais
n'aidait pas à trouver la suite). Lecture- Un peu de lecture pour les curieux: approfondir
les graphes d'intervalles.
Mer 07/10 10h15: Encore des gloutons au programme: contre-exemple
pour Brelaz (et optimalité sur graphes bipartis), théorie des
matroides, et application sur un exemple d'ordonnancement simple. Todo- Jouer sur un problème d'ordonnancement où les tâches ont
des durées différentes, et pour les curieux, l'article qui a introduit
les matroïdes.
Mer 14/10 10h15: Introduction à la NP-complétude: polynomes, taille des
données, certificats, classes P et NP, exemples divers et variés,
et principe de réduction. Todo- Lire la feuille distribuée en cours (extrait
du livre de Wilf, "Algorithmes et Complexité"), tout du moins le
principe des machines de Turing.
Mer 21/10 10h15: La première réduction: 3-SAT est au moins aussi
difficile que SAT. On poursuit avec la NP-complétude de SAT
(théorème de Cook). Todo- Oui oui, on n'a pas prouvé tout à fait entièrement le
théorème de Cook, mais vous pouvez cogiter sur le livre de Wilf pour
bien comprendre toutes les contraintes exprimées...
Mer 28/10 10h15: Réductions sur des problèmes de graphes: clique,
vertex-cover et
cycle hamiltonien. Introduction à l'approximation sur le problème
de vertex-cover: algorithme glouton et programmation linéaire pour
la version pondérée (les deux méthodes fournissent une
2-approximation). Todo- Lire (et bien comprendre) la NP-complétude des problèmes
de coloriage de graphes. Et réviser pour le partiel :-).