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

Enseignement : Algorithmique et structures de données (2009, 2010 et 2011)

Les séances de TP et TD sont encadrées par Martin Delacourt, Viet Phan Luong et moi-même.

Blue - mR-StIck
image : Blue - mR-StIck

Devoir à la maison

Sujet 2011 [pdf][py]

Implémentation d'ensembles à l'aide de skip-lists.

Sujet 2010 [pdf]

Implémentation des files de priorités à l'aide de listes et de tas.

Travaux dirigés

TD n° 1 [pdf]

Quelques algorithmes simples : évaluation d'une écriture binaire, décompte des lettres d'une chaîne, palindromes et tri rapide.

TD n° 2 [pdf]

Un peu de tri sur les tableaux d'entiers (tri bulle et quick sort).

TD n° 3 [pdf]

Quelques algorithmes récursifs : tri fusion et renversement d'une liste de manière efficace.

TD n° 4 [pdf]

Des fonctions récursives sur les listes.

TD n° 5 et 6 [pdf][corrigé]

Corrigé du partiel de l'année 2009. Des fonctions récursives, et des listes pointées (représentées par des listes chaînées, des piles et des tableaux).

TD n° 7 [pdf]

Complexité des tableaux dynamiques par analyse amortie.

TD n° 8 [pdf]

Tables de hachage, résolution des collisions par sondages linéaire, quadratique et par double hachage.

TD n° 9 [pdf]

Arbres binaires équilibrés et rotations.

Travaux pratiques

TP n° 1 [pdf][corrigé]

Manipulations de tableaux en Python : recherche de l'élément minimal et maximal, tri naïf par permutations et tri fusion. Mesure du nombre de comparaisons effectuées par chaque algorithme.

TP n° 2 [pdf]

Représentation des graphes par leur matrice d'adjacence ou liste d'adjacence. Fonctions simples les manipulant.

TP n° 3 [pdf]

Graphes pondérés. Fonctions simples et calcul du plus court chemin entre deux sommets en temps polynomial.

TP n° 4 et 5 [pdf][corrigé]

Plein de fonctions sur les listes chaînées.

TP n° 6 [pdf][test]

Les fonctions récursives du partiel 2010 et des manipulations de polynômes représentés par des listes.

TP n° 7 [pdf][py]

Substitution de Fibonacci et tours de Hanoï.

TP n° 8 [pdf][corrigé]

Fonctions élémentaires sur les arbres binaires.

TP n° 9 (corrigé) [pdf]

Les dictionnaires en Python (tables de hachage), un exemple de fonction de hachage mal choisie et le paradoxe des anniversaires.

Partiels et examens

Partiel 2009 [pdf]

Exercice 1 : des fonctions récursives sur les listes.
Exercice 2 : représentation des listes pointées (listes dans lesquels un curseur de lecture se déplace en avant ou en arrière) par différentes structures de données.

Examen 2009 (corrigé) [pdf]

Exercice 1 : des fonctions récursives sur les listes.
Exercice 2 : représentation des listes circulaires (le successeur du dernier élément est le premier élément).

Partiel 2010 [pdf]

Exercice 1 : des fonctions récursives sur les listes
Exercice 2 : différentes structures de données pour représenter des ensembles dans lesquels on peut efficacement insérer un nouvel élément et chercher si un élément est présent.

Examen 2010 (corrigé) [pdf]

Exercice 1 : des fonctions récursives sur les listes et les arbres binaires.
Exercice 2 : retournement d'une liste par une fonction récursive efficace.
Exercice 3 : représentation des expressions arithmétiques par des arbres binaires.
Exercice 4 : Codage d'un dictionnaire par des arbres ternaires.

Partiel 2011 [pdf]

Exercice 1 : des fonctions récursives sur les listes
Exercice 2 : différentes structures de données pour représenter des listes bilatères c'est-à-dire des listes pour lesquelles il est facile d'ajouter ou supprimer des éléments en tête et en queue.

Examen 2011, 2e session (corrigé) [pdf]

Exercice 1 : des fonctions récursives sur les listes et les arbres binaires.
Exercice 2 : une fonction mystère à comprendre.
Exercice 3 : listes à trous, où l'on marque les éléments supprimés sans les retirer de la chaîne.

Valid XHTML 1.0 Transitional Valid CSS! Valid Konami!