Travaux dirigés
TD n°1 [pdf]
Recherche simultanée du maximum et du minimum des éléments dans un tableau. Preuve d'optimalité dans le pire des cas par la méthode de l'adversaire.
TD n°2 [pdf]
Recherche des deux plus grands éléments dans un tableau et matrices de Toeplitz.
TD n°3 [pdf]
Trois problèmes résolus par programmation dynamique.
TD n°4 [pdf]
Un algorithme glouton pour déterminer le codage de Huffmann correspondant à un texte donné.
Le TD n°5 n'a jamais existé... (il a été remplaçé par le partiel)
TD n°6 [pdf]
Recherche d'un élément majoritaire dans un tableau par une technique de "diviser pour régner" d'abord puis selon un algorithme spécifique au problème. Preuve d'optimalité.
TD n°7 [pdf]
NP-complétude (des variantes de sat, subset-sum et sous-chaîne transitive).
TD n°8 [pdf]
NP-complétude de cubic, un jeu à un joueur où l'on pousse des blocs de couleur soumis à la gravité qui disparaissent quand ils entrent en contact avec d'autres blocs de la même couleur. On effectue une réduction à partir de SAT en construisant les gadgets permettant de représenter un circuit booléen (les deux dernières pages sont à distribuer à la fin du TD).
Le sujet est basé sur un article d'Erich Friedman.
TD n°9 [pdf]
Preuve de NP-complétude puis calcul d'une 2-approximation des problèmes du k-centre et du sac à dos.
TD n°10 [pdf]
Retour sur les problèmes subset-sum et sac à dos. Preuves de NP-complétude et algorithmes d'approximation.
TD n°11 [pdf]
Algorithmes de parcours en profondeur d'un graphe orienté et de construction des composantes fortement connexes. Application : 2-SAT est soluble en O(n+m) (n variables et m clauses).
Partiel
Partiel de l'année 2006 - 2007 [pdf]
Trois exercices indépendants : un algorithme glouton pour ranger des fichiers dans une mémoire trop petite, de la programmation dynamique pour paver un carré à l'aide de rectangles en minimisant le périmètre et l'analyse de la complexité d'un algorithme de tri très peu efficace.
Devoir à la maison
Devoir à la maison [pdf]
Le devoir est composé de 3 exercices indépendants sur un même thème : les systèmes de vote. Le premier exercice concerne les ordres vus comme des graphes orientés sans cycles. Le second exercice est consacré à la preuve du théorème d'Arrow. Enfin le dernier exercice concerne la gerrymanderisation, procédé visant à grouper les résultats d'un vote de manière à favoriser un candidat.