UQAM Département d'informatique

INF3105 - Structures de données et algorithmes
Automne 2018

Professeur

Éric Beaudry
beaudry.eric@uqam.ca

Horaire et Locaux

Voir l'horaire et les locaux du cours.

Calendrier

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

# Dates Cours magistraux Laboratoires Lectures
1 mardi
4 septembre
(groupe 20)

jeudi
6 septembre
(groupe 40)
Début du cours.
[Beaudry] Section 1.
Langage C++. [Beaudry] Section 2.
[Goodrich] Chapitre 1.
[Gabrini] Chapitre 1.

Références techniques en ligne: Tutoriels en ligne:
jeudi/vendredi
6/7 septembre
Lab1 : Introduction à C++.
  • Compilation avec Gnu GCC (g++).
  • Makefile.
  • Programme C++ simple.
Solution du lab1 : lab1-final.zip.
[Beaudry] Sections 2.1 à 2.5.

Guide sur Makefile en ligne:
2 mardi
11 septembre
(groupe 20)

jeudi
13 septembre
(groupe 40)
Langage C++.
jeudi/vendredi
13/14 septembre
Lab2 : Intro à C++ sur les pointeurs, références, classes, constructeurs et destructeurs.
Solution du Lab2.
3 mardi
18 septembre
(groupe 20)

jeudi
20 septembre
(groupe 40)
Complexité algorithmique.
  • Analyse empirique.
  • Analyse asymptotique.
  • Études de cas : algorithmes de tri.
Exercices :
[Beaudry] Section 3.
[Goodrich] Section 4.
[Gabrini] Chapitre 3.

Référence et démo en ligne :
 http://www.sorting-algorithms.com/.
Tableaux génériques à taille automatique. [Beaudry] Section 4.
[Goodrich] Sections 3.1 11.1-.2.
[Gabrini] Section 2, 6.1-6.6.
TP1 - Résolution d'un problème simple.
jeudi/vendredi
20/21 septembre
Lab3 : Tableaux dynamiques génériques

4 mardi
25 septembre
(groupe 20)

jeudi
27 septembre
(groupe 40)
Quiz 1

Rappels : Piles et Files.

Listes et itérateurs de listes.
[Beaudry] Sections 5-7.
[Goodrich] Chapitres 5-7.
[Gabrini] Chapitres 6, 8 (8.4) et 9 (9.2).
jeudi/vendredi
27/28 septembre
Lab4 : Piles et Files.
Annexe: Rappels, trace tâche 2 et solution tâche 4.
5 mardi
2 octobre
(groupe 20)

jeudi
4 octobre
(groupe 40)
Listes et itérateurs de listes.

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

Arbres binaires de recherche.
  • Représentation.
  • Recherche.
  • Insertion.
  • Enlèvement.
[Beaudry] Sections 8.1 - 8.8.
[Goodrich] Sections 10.1-10.2.
[Gabrini] Sections 8.3 et 9.3.
jeudi/vendredi
4/5 octobre
Lab5 : Listes.
Solution: lab5.cpp.
6 mardi
9 octobre
(groupe 20)

jeudi
11 octobre
(groupe 40)
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] Section 8.9.
[Goodrich] Sections 10.1-10.2.
[Gabrini] Sections 8.3 et 9.3.

Démos d'arbres AVL en ligne :
jeudi/vendredi
11/12 octobre
Lab6 : Arbres AVL.
7 mardi
16 octobre
(groupe 20)

jeudi
18 octobre
(groupe 40)
Arbres binaires de recherche équilibrés (suite).
  • Enlèvement dans AVL.
  • Itérateurs d'arbres binaires de recherche.
  • Construction d'un itérateur suite à d'une recherche.
  • Recherche par bornes inférieurs et supérieures.
  • Copie (operator = et constructeur par copie).
  • Test d'équivalence (operator ==).
Exercice complexité algo.: progB.cpp.
[Beaudry] Section 8.12.
[Goodrich] Section 10.4.
[Gabrini] Section 9.4.

Dictionnaires / Arbres associatifs (Map).

Exercice: Examen 2013H / Q6.

TP2 - Résolution de problème faisant appel à des structures avancées

[Beaudry] Section 8.11.
[Goodrich] Section 9.1.
jeudi/vendredi
18/19 octobre
Lab7 : Arbres AVL (suite).
8 mardi
23 octobre
(groupe 20)

jeudi
25 octobre
(groupe 40)
Arbres rouge-noirs (Red-Black Trees). [Beaudry] Section 8.12
[Goodrich] Section 10.5.
[Gabrini] Section 9.4.

Démo en ligne:
Retour sur le TP1.

Exercices avec exemans antérieurs:
jeudi/vendredi
25/26 octobre
Lab8 : Dictionnaires (ArbreMap).
9 dimanche
28 octobre
09h30 - 12h30
Examen de mi-session
mardi
30 octobre
(groupe 20)

jeudi
1 novembre
(groupe 40)
Pas de cours de prévu. Toutefois, en cas de retard sur la matière, il pourrait y avoir un cours.
jeudi/vendredi
1/2 novembre
Lab9 : séance de consultation avec les démonstrateurs.
10 mardi
6 novembre
(groupe 20)

jeudi
8 novembre
(groupe 40)
Retour sur l'examen de mi-session:
Arbre B (B-Tree). [Beaudry] Section 8.13
[Goodrich] Section 14.3.

Démo en ligne:
Arbres spécialisés.

  • Arbre d'intervalles (non sujet à l'examen final).
[Cormen] Chapitre 14 (Augmenting Data Structures) / Section 14.3 (Interval Trees).
jeudi/vendredi
8/9 novembre
Bibliothèques normalisées.
  • Standard Template Library (STL) en C++ : stack, deque, slist, list, set, multiset, map et unordered_map.
  • Aperçu de Java Collection.
Lab10 : STL et exercices sur l'héritage avec structures de données.
Solution tâche 2
[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.
11 mardi
13 novembre
(groupe 20)

jeudi
15 novembre
(groupe 40)
Monceaux (heap).
  • Représentation.
  • Opérations.
  • Lien avec le tri de monceau (heap sort) (non présenté explicitement).
  • Files prioritaires.
[Beaudry] Section 9.
[Goodrich] Section 8.
[Gabrini] Sections 3.4 et 4.8.
Graphes.
  • Définitions.
  • Représentations.
  • Algorithmes de base :
    • Parcours recherche en profondeur et recherche en largeur.
    • Détection de cycles.
    • Extraction de composantes connexes.
    • Extraction de composantes fortement connexes (sujet du lab 12).
[Beaudry] Section 12.
[Goodrich] Section 13.1 - 13.3.
[Gabrini] Sections 10.1-10.3.
jeudi/vendredi
15/16 novembre
Lab11 : Graphes.
12 mardi
20 novembre
(groupe 20)

jeudi
22 novembre
(groupe 40)
Graphes (suite).
  • Algorithmes de base (suite) :
    • Détection de cycles. Exercice.
    • Extraction de composantes connexes.
    • Extraction de composantes fortement connexes (sujet du lab 12).
  • Algorithmes de recherche de chemin :
[Beaudry] Section 13.
[Goodrich] Section 13.4 - 13.6.
[Gabrini] Sections 10.4-10.6.
TP3 : Graphes.

Exemple Quiz2: Questionnaire | Annexe | Corrigé | Explications .
jeudi/vendredi
22/23 novembre
Lab12 : Graphes (suite).
13 mardi
27 novembre
(groupe 20)

jeudi
29 novembre
(groupe 40)
Quiz 2
Résultats TP2 : Sommaire | Détails
Graphes (suite).
jeudi/vendredi
29/30 novembre
Lab13: consultations TP2 et TP3.
14 mardi
4 décembre
(groupe 20)

jeudi
6 décembre
(groupe 40)
Tables 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.
jeudi/vendredi
6/7 décembre
Lab14 : Tables de hachage.
15 mardi
11 décembre
(groupe 20)

jeudi
13 décembre
(groupe 40)
Révision. Préparez vos questions.
jeudi/vendredi
13/14 décembre
Lab15 : assistance TP3.
16 dimanche
16 décembre

Examen final de 9h30 à 12h30

Bibliographie

Obligatoire

Recommandées

Complémentaires

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.