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
  • Tri rapide
  • Sélection
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