http://www.lirmm.fr/~poupet/
e-mail: victor.poupet [at] lirmm.fr

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.

Floating Isle - -kol
image : Floating Isle - -kol

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)
L'article d'origine est disponible ici.

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.

Valid XHTML 1.0 Transitional Valid CSS! Valid Konami!