Matériel

Vous trouvez ci-dessous le contenu détaillé du cours. L'examen intra (16 février) couvre sections 1-5.

Notes de cours

1. Introduction >PDF [dernière modification: 14 janvier] 6 heures
Sujets
  • Plan de cours
  • Contenu du cours
  • Notions mathématiques: notation asymptotique, techniques de preuve
Références
  • Acétates par rencontre : pages 0-16 (12 jan), 17-21 (14 jan), 22-31 (19 & 21 janvier).
  • Notes de cours sur la notation asymptotique: >PDF.
  • Sedgewick, chapitres 1 et 2.
2. Listes >PDF [dernière modification: 25 janvier] 3+1 heures
Sujets
  • Listes chaînées
  • Sentinelles, listes doublement chaînées, listes circulaires
  • Traitement de listes
Références
  • Sedgewick, chapitre 3.
3. Types abstraits >PDF [dernière modification: 4 février] 2 heures
Sujets
  • Notion d'un type abstrait
  • Piles et files
Références
  • Sedgewick, chapitre 4.
4. Récursion et arbres >PDF [dernière modification: 13 février] 2 heures
Sujets
  • Récursion et itération, récursion terminale
  • Arbres: arbres ordonnés, représentation d'arbres, algorithmes de base
Références
  • Sedgewick, chapitre 5, sauf 5.8.
5. Files à priorités >PDF [dernière modification: 13 février] 4 heures
Sujets
  • TAD file à priorités
  • Tas binaire et tas d-aire
Références
  • Sedgewick, sections 9.1, 9.2, 9.3, 9.5.
6. Méthodes de tri >PDF [dernière modification: 25 février] 4 heures
Sujets
  • Tri par séléction
  • Tri par insertion
  • Tri par tas
  • Tri par fusion
  • Tri rapide
Références
  • Sedgewick, sections 6.1-6.4, 6.6, 6.9, 7.1-7.5, 8.1-8.4, 9.4
7. Arbres binaires de recherche >PDF [dernière modification: 18 mars] 6.5 heures
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
  • Acétates par rencontre : pages 0-20 (9 mars), 21-24 (11 mars), 25-41 (16 mars), 42-50 (18 mars), 51-53 (23 mars).
  • Notes de cours sur les arbres rouges et noirs, et les arbres 2-3-4: >PDF.
  • Notes de cours sur splaying: >PDF.
  • Démo du 25 mars: >PDF.
  • Sedgewick, chapitre 12, sections 13.1-13.4
8. Recherche externe >PDF [dernière modification: 23 mars] 1.5 heures
Sujets
  • Accès séquentiel indexé
  • Arbres B
Référence
  • Sedgewick, sections 16.1-16.3
9. Tableaux de hachage >PDF [dernière modification: 1 avril]
Sujets
  • Fonctions de hachage: méthode de la division, de la multiplication, hachage universel
  • Chaînage
  • Adressage ouvert : sondage linéaire, double hachage
  • Ensembles statiques Compteur probabiliste
Références
  • Acétates par rencontre : pages 0-4 (25 mars), 5-11 (30 mars), 5-11 (1 avril).
  • Sedgewick, chapitre 14
10. Graphes >PDF [dernière modification: 6 avril]
Sujets
  • Graphes : rappel de notions de base
  • Représentation par matrice ou listes d'adjacence
  • Parcours par largeur et par profondeur
  • Arbre couvrant minimal : algorithmes de Kruskal et de Prim
Références
  • Sedgewick, sections 3.7 (représentation) et 5.8 (parcours)
  • Notes de cours sur les algorithmes de Kruskal et de Prim: >PDF.

Devoirs

Devoir 1 à remettre le 2 février.
Énoncé >PDF.
Devoir 2 à remettre le 11 février (pas de pénalité pour une soumission tardive avant minuit du 16 février).
Énoncé >PDF.
Examen intra le 16 février
Énoncé >PDF.
Devoir 3 à remettre le 30 mars.
Énoncé >PDF.
Devoir 4 à remettre le 13 avril (pas de pénalité pour une soumission tardive avant minuit du 15 avril).
Énoncé >PDF.