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
- 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
- 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
- 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.