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]
- des fonctions récursives sur les listes.
- 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]
- des fonctions récursives sur les listes.
- représentation des listes circulaires (le successeur du dernier élément est le premier élément).
Partiel 2010 [pdf]
- des fonctions récursives sur les listes
- 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]
- des fonctions récursives sur les listes et les arbres binaires.
- retournement d'une liste par une fonction récursive efficace.
- représentation des expressions arithmétiques par des arbres binaires.
- Codage d'un dictionnaire par des arbres ternaires.
Partiel 2011 [pdf]
- des fonctions récursives sur les listes
- 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]
- des fonctions récursives sur les listes et les arbres binaires.
- une fonction mystère à comprendre.
- listes à trous, où l'on marque les éléments supprimés sans les retirer de la chaîne.