INF3105 - Structures de données et algorithmes (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.

Le cours est en présentiel au PK-1705 (groupe 30).
Mattermost: canal public INF3105
Centre d'aide du département d'informatique

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: http://cppreference.com/. http://www.cplusplus.com/. Tutoriels en ligne: Cours de C/C++ de Christian Casteyde. Penser en C++ de Bruce Eckel. Thinking in C++ de Bruce Eckel.
	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: A brief intro to Makefiles. Introduction à Makefile.

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/.
2	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.
	DateSéance	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: 2019A: Programmes en annexe \| Questionnaire \| Solutionnaire . 2020A: Questionnaire Groupe 20 \| Explications des réponses .	[Beaudry] Section 5-7. [Goodrich] Sections 3.2-3.3, Chapitres 5-6.
4	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): `int ArbreBinRech<T>::nbCommun(const ArbreBinRech<T>& a)` `int ArbreBinRech<T>::nbDiff(const ArbreBinRech<T>& a)` 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 : AVLTree.
6	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.
	DateSéance	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: RedBlack.
		Arbres spécialisés : (total: 0h24m27s).	[Cormen] Chapitre 14 (Augmenting Data Structures) / Section 14.3 (Interval Trees).
		TP3 - Arbres AVL.
		Examens antérieurs: 2022E : Questionnaire\| Solutionnaire 2021E : Questionnaire en ligne. 2019A : Questionnaire: Partie A, Partie B avec annexes \| Solutionnaire: Partie A, Partie A avec explications, Partie B
	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
	DateSéance
	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: B-Tree
		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.
	DateSéance	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]
	DateSéance	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. Détails de la correction (LibreOffice Calc).
	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. - Applets Java avec animation : - Applet Java 1 - Applet Java 2 - Démo HTML: Ouvert \| Fermé.
	DateSéance	Examens finaux antérieurs: 2016E : Questionnaire \| Solutionnaire 2014E : Questionnaire \| Solutionnaire 2013A : Questionnaire \| Solutionnaire
	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). Solutionnaire de l'examen Notes de l'examen
	DateLab	Période d'aide pour TP5.


16		Fin

Bibliographie

Lecture obligatoire

[Beaudry] Éric Beaudry (Été 2024). Notes de cours INF3105 - Structures de données et algorithmes. PDF de 139 pages.

Livres recommandés

[Goodrich] Michael T. Goodrich, Roberto Tamassia et David Mount (2011). Data Structures & Algorithms in C++ (second edition). Wiley. [Coop UQAM] [Bibliothèque UQAM]
[StroustrupB] Bjarne Stroustrup. A Tour of C++ (2nd Edition). Addison-Wesley. [Coop UQAM]

Livres complémentaires

[Cormen] Cormen, Leiserson, Rivest et Stein. Introduction to Algorithms, Third Edition. [Bibliothèque UQAM]
[StroustrupA] Bjarne Stroustrup. The C++ Programming Language (4th edition). Addison-Wesley. [Bibliothèque UQAM]

Articles

[Geisberger] R. Geisberger, P. Sanders, D. Schultes, et C. Vetter. (2012) Exact Routing in Large Road Networks Using Contraction Hierarchies Transporation Science, vol. 46, no. 3, pp. 388–404.
[Hard] R. Peter E. Hart; Nils J. Nilsson; Bertram Raphael. (1968) A Formal Basis for the Heuristic Determination of Minimum Cost Paths IEEE Transactions on Systems Science and Cybernetics, vol. 4, no. 2, pp. 100–107.

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.

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