Matériel
Notes de cours
- 1. Introduction
10 heures
- Sujets
- Plan et contenu du cours
- Appartenance-union
- Notions mathématiques: notation asymptotique, techniques de preuve
- Références
- Notes de cours sur le plan:
>PDF.
- Notes de cours sur appartenance-union (Union-find):
>PDF.
- Notes de cours sur la notation asymptotique:
>PDF.
- Notes de cours sur l'analyse d'algorithmes:
>PDF.
- Sedgewick, chapitres 1 et 2.
- 2. Listes
2 heures
- Sujets
- Listes chaînées
- Sentinelles, listes doublement chaînées, listes circulaires
- Traitement de listes: parcours, insertion, délétion
- Notion d'un type abstrait
- Piles et files
- Références
- Notes de cours sur les listes:
>PDF
- Notes de cours sur les tableaux:
>PDF [version corrigée par rapport à celle distribuée au cours].
- Sedgewick, chapitres 3 et 4.
- 3. Arbres
2 heures
- Sujets
- Arbres: arbres ordonnés, représentation d'arbres
- Parcours d'un arbre.
- Arbre syntaxique. Expressions arithmétiques.
- Algorithmes récursifs sur les arbres.
- Références
- Notes de cours sur les arbres:
>PDF.
- Notes de cours sur le parcours:
>PDF.
- Sedgewick, chapitre 5, sauf 5.8.
- 4. Méthodes élémentaires de tri
1 heure
- Sujets
- Tri par séléction
- Tri par insertion
- Tri de liste chaînée
- Références
- Notes de cours sur les tris:
>PDF.
- Sedgewick, sections 6.1-6.4, 6.6, 3.4, 6.9
- 5. Tri par fusion
2 heures
- Sujets
- Fusion de listes
- Tri par fusion
- Références
- Notes de cours sur le tri par fusion:
>PDF.
- Sedgewick, sections 8.1-8.4, 8.7
- 6. Tri rapide
2 heures
- Sujets
- Références
- Notes de cours sur le tri rapide:
>PDF.
- Sedgewick, chapitre 7
- 7. Files à priorités
2 heures
- Sujets
- TAD file à priorités
- Tas binaire et tas d-aire
- Tri par tas
- Références
- Notes de cours sur le tas binaire:
>PDF.
- Notes de cours sur le tri par tas:
>PDF.
- Sedgewick, sections 9.1, 9.2, 9.3, 9.4, 9.5.
- 8. Arbres binaires de recherche
- Sujets
- Type abstrait de la table de symboles
- Arbre binaire de recherche
- Arbre splay
- Arbre rouge et noir
- Arbre 2-3-4
- Références
- Notes de cours sur les arbres binaires de recherche:
>PDF.
- Notes de cours sur splaying:
>PDF.
- Notes de cours sur les ABRs équilibrés (AVL, rouge-et-noir):
>PDF.
- Notes de cours sur les arbres 2-3-4:
>PDF
- Sedgewick, chapitre 12, sections 13.1-13.4
- 9. Hachage
- Sujets
- Fonctions de hachage: méthode de la division, de la multiplication, hachage universel
- Chaînage séparé
- Adressage ouvert : sondage linéaire, double hachage
- Références
- Notes de cours:
>PDF
- Sedgewick, chapitre 14
Devoirs et examens
- Devoir 1 à remettre le 3 février.
- Énoncé >PDF.
- Devoir 2 à remettre le 17 février.
- Énoncé >PDF.
- Examen intra le 15 février.
- Énoncé: >PDF.
- Devoir 3 à remettre le 31 mars.
- Énoncé >PDF.
- Devoir 4 à remettre le 16 avril.
- Énoncé >PDF.
Examens finaux des années passées
- Hiver 2006: >PDF.
- Hiver 2007: >PDF.
- Hiver 2009: >PDF.