UQAM Département d'informatique

INF3105 - Structures de données et algorithmes
Été 2024

Équipe

Groupe 30 (mardis après-midi)

Chargé de cours : Jaël Champagne Gareau

📧 champagne_gareau.jael@uqam.ca

Démonstrateur et correcteur : Guillaume Gosset

📧 gosset.guillaume@uqam.ca

Horaire, Salle de cours et Aide

Voir l'horaire officiel et le local du cours.

Calendrier

Des capsules vidéos, enregistrées lorsque ce cours était offert en ligne, sont disponibles via les bouttons 🎞. Puisque le contenu peut légèrement varier d'une session à l'autre, la présence au cours demeure fortement recommandée.

# Date 📅 Contenu 🗎 🎞 📝 Lectures 📚
1 DateSéance Plan de cours officiel : HTML | PDF
Présentation du cours : (Total: 0h38m46s) .

Politiques et directives sur les environnements de développement, les outils et la remise des travaux.
[Beaudry] Section 1.
Introduction au langage C++: (Total: 3h34m33s) .

📝 Exercice : C++ : pointeurs, références, classes, constructeurs, destructeurs, tableaux, etc.
[Beaudry] Section 2.
[Goodrich] Chapitre 1.

Références techniques en ligne: Tutoriels en ligne:
DateLab Documentation pour accéder aux serveurs LabUnix

Lab1 : Introduction à C++.
  • Compilation avec Gnu GCC (g++).
  • Makefile.
  • Programme C++ simple.

« Solution » du lab1: lab1_solution.zip

[Beaudry] Sections 2.1 à 2.6.

Guides sur Makefile en ligne:
2 DateSéance Analyse et complexité algorithmique : (total: 1h58m25s) .

📝 Exercice : Analyse d'algorithmes : .
[Beaudry] Section 3.
[Goodrich] Section 4.

Référence et démo en ligne :
http://www.sorting-algorithms.com/.
DateLab Lab2 : Suite C++ sur les pointeurs, références, classes, constructeurs et destructeurs.
Solution
3 DateSéance Tableaux génériques à taille automatique : (total: 1h42m36s) .

📝 Exercice: Tableau<T> et C++ | Solution.
[Beaudry] Section 4.
[Goodrich] Chapitres 3.1.
TP1 - Tableaux dynamiques.
DateLab Lab3: classe générique Tableau.
(La solution ne sera pas fournie sur le site, car elle fait partie du TP1.)
4 DateSéance Piles : (total: 0h56m29s).
Files : .

Listes et itérateurs : (total: 0h53m59s).

Exercices de préparation pour Quiz 1:
  1. 2019A: Programmes en annexe | Questionnaire | Solutionnaire .
  2. 2020A: Questionnaire Groupe 20 | Explications des réponses .
[Beaudry] Section 5-7.
[Goodrich] Sections 3.2-3.3, Chapitres 5-6.
DateLab Lab4 - Analyse d'un bogue (C++ et Pile) + File :
Code source de la solution du lab4.
5 DateSéance Arbres : (total: 0h56m48s).
Arbres binaires de recherche : (total: 1h40m17s)

📝 Exercice: Arbres binaires de recherche en C++: Codez (sans itérateurs):
  1. int ArbreBinRech<T>::nbCommun(const ArbreBinRech<T>& a)
  2. int ArbreBinRech<T>::nbDiff(const ArbreBinRech<T>& a)
  3. constructeur ArbreBinRech<T>::ArbreBinRech(const Tableau<T>& t) en O(n) lorsque t serait déjà trié
[Beaudry] Sections 8.1 - 8.8.
[Goodrich] Sections 10.1-10.2.
Quiz 1
TP2 - Déplacements dans un univers virtuel
DateLab Lab5 - Implémentation et application des listes chaînées.
Solution du lab5
6 DateSéance Arbres AVL : (total: 1h26m29s).

Implémentation ArbreAVL : (total: 0h53m17s).
[Beaudry] Section 8.9.
[Goodrich] Sections 10.1-10.2.

Démo AVL :
DateLab Lab6 - Arbres AVL.
(La solution ne sera pas fournie sur le site, car elle fait partie du TP3.)
7 DateSéance

Itérateurs d'arbres binaires de recherche: (total: 1h25m57s).

[Beaudry] Section 8.10.
Dictionnaires / Arbres associatifs (Map) : (total: 1h54m01s). [Beaudry] Section 8.11.
[Goodrich] Section 9.1.
DateLab Lab7 - Arbres AVL, itérateurs et recherches par bornes.
(La solution ne sera pas fournie sur le site, car elle fait partie du TP3.)
8 DateSéance Arbres rouge-noirs (Red-Black Trees): (total: 1h37m43s).
* Erratum cas hauteur impaire dans la capsule Analyse.
[Beaudry] Section 8.12
[Goodrich] Section 10.5.

Démo Arbre RN:
Arbres spécialisés : (total: 0h24m27s). [Cormen] Chapitre 14 (Augmenting Data Structures) / Section 14.3 (Interval Trees).
TP3 - Arbres AVL.
Examens antérieurs:
DateLab Exercices de révision.
9 DateSéance Examen de mi-session.

Informations :

  • Aucune documentation permise à l'exception de ce petit aide-mémoire sur le langage C++ qui sera fourni dans l'examen.
  • L'examen porte sur l'ensemble de la matière vue avant l'examen (en classe, labs et notes de cours).
Solutionnaire de l'examen Notes de l'examen
DateLab Lab8 : Dictionnaire ArbreMap
(La solution ne sera pas fournie sur le site, car elle fait partie du TP4.)
10 DateSéance Arbres B (B-Tree): (total: 0h49m22s). [Beaudry] Section 8.13
[Goodrich] Section 14.3.

Démo Arbre B:
Monceaux (heap): (total: 0h53m00s). [Beaudry] Section 9.
[Goodrich] Section 8.
TP4.

Retour sur l'examen de mi-session.
DateLab Lab9 : Monceaux
11 DateSéance Graphes: (total: 1h59m54s). [Beaudry] Section 12.
[Goodrich] Section 13.1 - 13.3.
Graphes / Algorithme de Dijkstra: (total: 0h43m45s). [Beaudry] Section 13.
[Goodrich] Section 13.4 - 13.6.
DateLab Lab10 : Conteneurs de la bibliothèque standard C++ et héritage. [Beaudry] Section 11.

- Conteneurs dans la Bibliothèque standard de C++.
12 DateSéance (Non sujet à examen) Aperçu d'autres algorithmes: (total: 0h27m16s). [Geisberger]
[Hart]
Questionnaire Pratique Quiz 2
DateLab Lab11 - Graphes
13 DateSéance Graphes / Algorithme de Floyd-Warshall: (total: 0h33m14s).

Graphes / Arbres de recouvrement minimal (ARM): (total: 1h31m51s).
Quiz 2
TP5.
DateLab Lab12 - Graphes / Extraction d'une composante fortement connexe
14 DateSéance Tables de hachage (Hash Tables) : (total: 1h54m27s). [Beaudry] Sections 10.
[Goodrich] Sections 9.1-9.2.


Démos Web avec animation :
- Applet Java externe, Copie Applet Java.
- Démo HTML: Ouvert | Fermé.
Examens finaux antérieurs:
DateLab Lab13 - Tables de hachage
15 DateSéance Examen final.

Informations :

  • Aucune documentation permise à l'exception de ce petit aide-mémoire sur le langage C++ qui sera fourni dans l'examen.
  • L'examen porte sur l'ensemble de la matière vue avant l'examen (en classe, labs et notes de cours).
DateLab Période d'aide pour TP5.
16 Fin

Bibliographie

Lecture obligatoire

Livres recommandés

Livres complémentaires

Articles

Avis de changements

Les ajouts récents et les corrections récentes, portant sur les semaines antérieures, sont ou seront surlignés en vert.