http://perso.ens-lyon.fr/victor.poupet
e-mail: victor [point] poupet [at] ens-lyon [point] fr
home

ENSEIGNEMENT : Algorithmique (1er semestre 2006 - 2007)

Cours d'Anne Benoit en L3 à l'ENS Lyon.
Les TD ont été écrits avec Damien Regnault, également chargé de TD.

TRAVAUX DIRIGES


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...

PARTIEL

Partiel de l'année 2006 - 2007 [ps][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 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.

ice - frostfire101
image : Ice - frostfire101