Logo UQAM
Département d'informatique

INF3105 - Structures de données et algorithmes (Été 2016)

Professeur : Éric Beaudry (beaudry.eric@uqam.ca)
Auxiliaires d'enseignement : Mathieu Gravel (gravel.mathieu.3 @ courrier.uqam.ca), Jean Massardi (massardi.jean_julien_galileo@courrier.uqam.ca)

Calendrier

Ce calendrier est montré à titre indicatif et sera mis à jour tout le long de la session selon la progression du cours.

Sem.
#
Date Cours magistraux.
(les jeudis 13h30-17h00 au PK-R220)
Laboratoires et Travaux pratiques.
(les lundis 13h30-16h00 aux PK-S1560 et PK-S1570)
Lectures.
(obligatoires en gras)
1 lundi 2 mai

Exceptionnellement au PK-R250.

Avant de commencer :

Introduction.

Exceptionnellement, une séance de cours de 2.5h remplace le laboratoire.

[Beaudry] Sections 1 et 2.
[Goodrich] Chapitre 1.
[Gabrini] Chapitre 1.
[Laforest] Survol de C++.

Web :
 - http://cppreference.com/.
 - http://www.cplusplus.com/.
 - Tutoriel C++ du Site du Zéro.
 - Cours de C/C++ de Christian Casteyde.
 - Penser en C++ de Bruce Eckel.
 - Thinking in C++ de Bruce Eckel.
jeudi 5 mai

Introduction au langage C++ (suite à partir diapositive #25).

Exercice sur les pointeurs et références en C++ : ex1_pointeurs_refs.cpp.

Exercice sur C++ (classes, constructeurs, destructeurs, tableaux, etc.) : Exercice_C++_2014HEx1Q1.pdf.

   
2 lundi 9 mai  

Lab1 : Introduction à C++.

  • Compilation avec Gnu GCC (g++).
  • Makefile.
  • Programme C++ simple.

Solution du lab1 : lab1-final.zip.

[Beaudry] Sections 2.1 à 2.5.

Web :
 - A brief intro to Makefiles.
 - Introduction à Makefile.
jeudi 12 mai

Exercice sur C++ (classes, constructeurs, destructeurs, tableaux, etc.) : Exercice_C++_2013E_Ex1Q1.pdf. Solutions: Exercice_C++_2013E_Ex1Q1+.pdf

Complexité algorithmique.

  • Analyse empirique.
  • Analyse asymptotique.
  • Études de cas : algorithmes de tri.

Exercices :

[Beaudry] Section 3.
[Goodrich] Section 4.
[Gabrini] Chapitre 3.

Web :
 http://www.sorting-algorithms.com/.
3 lundi 16 mai  

Lab2 : Exercices sur les pointeurs, classes, constructeurs et destructeurs en C++.

Solution du Lab2.

 
jeudi 19 mai

Tableaux génériques à taille automatique.

  • Implémentation en C++.
  • Opérateurs [] (version const et version non const).
  • Introduction au mécanisme de template de C++.
  • Nécessité de l'opérateur = et du constructeur par copie.
  • Autres opérateurs.

Rappels : Piles et Files.

[Beaudry] Sections 3, 4.
[Goodrich] Sections 3.1 11.1-.2.
[Gabrini] Section 2, 6.1-6.6.
15h30:
Lab3 : Tableaux dynamiques génériques.
4 lundi 23 mai

Jour férié. Pas de laboratoire.

jeudi 26 mai

Quiz (5%).

Listes et itérateurs de listes.

Arbres.

  • Définitions.
  • Propriétés.
  • Représentation.
  • Parcours d'arbres.
  • Applications.

TP1 : Résolution d'un problème simple en C++.

Sommaire | Détails

[Beaudry] Sections 5 - 7.
[Goodrich] Chapitres 5 - 7.
[Gabrini] Chapitres 6, 8 et 9, sauf sections 8.4 et 9.2.
5 lundi 30 mai  

Lab4 : Piles et Files.

Lab5 : Listes (optionnel).

 
jeudi 2 juin

Arbres binaires de recherche.

  • Représentation.
  • Recherche.
  • Insertion.
  • Enlèvement.

Arbres binaires de recherche équilibrés (pas de diapos pour cette partie).

  • Arbre dégénéré (déséquilibré).
  • Notion d'arbre équilibré.
  • Arbres AVL.
    • Représentation, insertion, rotations et enlèvement.
    • Garantie log(n) pour opérations.

  [Beaudry] Sections 8.1 - 8.9.
[Goodrich] Sections 10.1-10.2.
[Gabrini] Sections 8.3 et 9.3.

Web :
 - Démos interactives arbres AVL : Applet Java | HTML + JS.
6 lundi 6 juin  

Lab6 : Arbres AVL.

 
jeudi 9 juin

Arbres binaires de recherche équilibrés (suite).

  • Itérateurs d'arbres binaires.
  • Construction d'un itérateur suite à une recherche.
  • Recherche par bornes inférieurs et supérieures.
  • Copie (operator = et constructeur par copie).
  • Test d'équivalence (operator ==).

Arbres rouge-noirs (Red-Black Trees).

[Beaudry] Section 8.12.
[Goodrich] Section 10.4.
[Gabrini] Section 9.4.

Web :
- Démo interactive arbres R-N.
7 lundi 13 juin   Lab6-7 : Arbres AVL (suite).  
jeudi 16 juin

Dictionnaires / Arbres associatifs (Map).

Arbres équilibrées (suite).

  • Arbre B (B-Tree).

Révision (si temps suffisant).

Examens de mi-session antérieurs.

TP2 - Arbres AVL + Résolution d'un problème.

Résultats: Sommaire | Détails

[Beaudry] Sections 8.11 et 8.13.
[Goodrich] Sections 10.4 - 10.5.
[Gabrini] Sections 9.4.

Web :
- Démo interactive avec plusieurs types d'arbre.
8 lundi 20 juin  

Lab8 : Révision.

 
jeudi 23 juin

Examen de mi-session

  
9 lundi 27 juin   Lab9 : Arbres Map.  
jeudi 30 juin

Retour sur l'examen de mi-session.

Arbres spécialisés.

  • Arbre d'intervalles (non sujet à l'examen final).

Bibliothèques normalisées.

  • Lib3105++.
  • Standard Template Library (STL) en C++ : stack, deque, slist, list, set, multiset, map et unordered_map.
  • Java Collection.

Héritage en C++ : quelques considérations lorqu'utilisé avec des conteneurs.

[Cormen] Chapitre 14 (Augmenting Data Structures) / Section 14.3 (Interval Trees).

[Beaudry] Section 11.

- Conteneurs dans la librairie standard C++
(standardisation de la STL dans C++ 03, 0x, 11).
- Implémentation STL de SGI.
- Article Wikipédia sur la STL.

10 lundi 4 juillet  

Lab10 : STL et exercices sur l'héritage combinée aux structures de données.

[Beaudry] Sections 11.

Web :
- Conteneurs dans la librairie standard C++
(standardisation de la STL dans C++ 03, 0x, 11).
- Implémentation STL de SGI.
- Article Wikipédia sur la STL.

jeudi 7 juillet

Monceaux (heap)

  • Représentation.
  • Opérations.
  • Lien avec le tri de monceau (heap sort).
  • Files prioritaires.

Graphes.

  • Définitions.
  • Représentations.
  • Algorithmes de base :
    • Parcours recherche en profondeur et recherche en largeur.
    • Extraction de composantes connexes.

[Beaudry] Section 9.
[Goodrich] Section 8.
[Gabrini] Sections 3.4 et 4.8.

[Beaudry] Section 12.
[Goodrich] Section 13.1 - 13.3.
[Gabrini] Sections 10.1-10.3.

11 lundi 11 juillet  

Lab11 : Graphes.

 
jeudi 14 juillet

Graphes (suite).

  • Algorithmes de base :
    • Parcours recherche en profondeur et recherche en largeur (bref retour).
    • Extraction de composantes connexes (bref retour).
    • Détection de cycles. Exercice Examen final 2012A / Question 4.
  • Algorithmes de recherche de chemin :

TP3 - Graphes + Conteneurs de la bibliothèque standard C++.

Détails | Nouveaux fichiers test

[Beaudry] Section 13.
[Goodrich] Section 13.4 - 13.6.
[Gabrini] Sections 10.4-10.6.

12 lundi 18 juillet  

Quiz 2 : Solutionnaire et explications

Lab12 : Graphes (suite).

 
jeudi 21 juillet

Graphes (suite).

Table de hachage (Hash Table).

  • Adressage dispersé.
  • Fonction de hachage
  • Gestion des collisions : ouverte | structure auxiliaire.
  • Dictionnaire.

[Beaudry] Sections 10.
[Goodrich] Sections 9.1-9.2.
[Gabrini] Chapitre 11.
Web :
- Démo table de hachage.

13 lundi 25 juillet

Lab13 : Préparation à l'examen final.

 
jeudi 28 juillet

Examen final de 13h30 à 16h30

Locaux selon la première lettre du nom de famille :

  • L-Z : PK-R220
  • A-K : PK-R250

Bibliographie

Errata

Les erreurs trouvées dans certaines références sont corrigées ou nuancées dans la page Errata du cours.

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.
© Éric Beaudry 2016.