TD n° 1 [ps][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 [ps][pdf]
Recherche des deux plus grands éléments dans un
tableau et matrices de Toeplitz.
TD n° 3 [ps][pdf]
Trois problèmes résolus par programmation
dynamique.
TD n° 4 [ps][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 [ps][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 [ps][pdf]
NP-complétude (des variantes de sat, subset-sum et sous-chaîne transitive).
TD n° 8 [ps][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)
L'article d'origine est disponible ici.
TD n° 9 [ps][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 [ps][pdf]
Retour sur les problèmes subset-sum et sac à dos. Preuves de NP-complétude et algorithmes d'approximation.
TD n° 11 [ps][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).
TD n° 12
A venir...
|