Devoir à la maison
Sujet [pdf]
Implémentation d'ensembles à l'aide de skip-lists.
Fichier annexe contenant des fonctions Python à utiliser [py]
Remarques :- Le devoir est à rendre par courrier électronique (à l'adresse qui est indiquée en haut de cette page) sous la forme d'un fichier texte contenant les fonctions Python demandées ainsi que les réponses aux questions qui demandent une réponse en langage courant (par exemples les questions de complexité ou les explications), ou deux fichiers séparés (un fichier .py et un contenant le texte des réponses aux autres questions).
- Vous pouvez travailler à plusieurs (c'est assez difficile à interdire de toute façon pour un devoir à la maison) mais chacun doit envoyer sa propre solution (les fonctions en Python peuvent être écrites à plusieurs mais les réponses aux autres questions ne doivent pas être identiques d'une copie à l'autre...
- Les skip-lists sont des objets assez connus en algorithmique et relativement bien documentés. Vous pouvez éventuellement chercher quelques informations sur Internet ou à la bibliothèque si vous voulez en savoir plus (il y a une page wikipédia...).
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]
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]
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]
Les dictionnaires en Python (tables de hachage), un exemple de fonction de hachage mal choisie et le paradoxe des anniversaires.
TP n° 9 [pdf]
Fonctions élémentaires sur les arbres binaires.
Partiels et examens
Partiel de l'année 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 de l'année 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 de l'année 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 de l'année 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.
