UQAM Département d'informatique

INF3105 - Structures de données et algorithmes
Automne 2017

Enseignants et auxiliaires d'enseignement

Groupe 20 (mardis après-midi)

Professeur:

Éric Beaudry
beaudry.eric@uqam.ca

Démonstrateurs:

Mathieu Gravel
gravel.Mathieu.3@courrier.uqam.ca
Eric Lavallée
lavallee.eric.2@courrier.uqam.ca

Groupe 40 (jeudis soir)

Chargée de cours:

Aléna Tsikhanovich
tsikhanovich.alena@uqam.ca

Démonstrateurs:

Jean Massardi
massardi.jean_julien_galileo@courrier.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
5 septembre
(groupe 20)

jeudi
7 septembre
(groupe 40)
Début du cours.
  • Présentation du cours.
  • Plan de cours officiel : HTML | PDF
  • Politiques et directives sur les environnements de développement, les outils et la remise des travaux.
  • Dates importantes :

    TP1 TP2 TP3 Quiz 1 et 2 Exam1 Exam2
    Pondération 15% 20% 15% 5% 20% 25%
    Énoncé 19/21 septembre 17 octobre 21/23 novembre 26/28 septembre 28/30 novembre 29 octobre 17 décembre
    Échéance 15 octobre 12 19 novembre 20 décembre 26/28 septembre 28/30 novembre 29 octobre 17 décembre
    Les dates pour les TPs peuvent varier selon la progression du cours. Référez-vous toujours aux énoncés de TP pour les dates de remise exactes.
  • Types abstraits de données (voir intro).
[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
7/8 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
12 septembre
(groupe 20)

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

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

Correction: Sommaire | Détails |Nouveaux tests (contreexemple-{bixi,req0}.txt

jeudi/vendredi
21/22 septembre
Lab3 : Tableaux dynamiques génériques

4 mardi
26 septembre
(groupe 20)

jeudi
28 septembre
(groupe 40)
Quiz 1 : annexes pour le groupe 20.

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
28/29 septembre
Lab4 : Piles et Files.
Annexe: Rappels, trace tâche 2 et solution tâche 4.
5 mardi
3 octobre
(groupe 20)

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

En début de cours: promotion du Programming Challenge associé à la conférence CAN-CWiC.

[Beaudry] Sections 8.1 - 8.8.
[Goodrich] Sections 10.1-10.2.
[Gabrini] Sections 8.3 et 9.3.
jeudi/vendredi
5/6 octobre
Lab5 : Listes.
Solution: lab5.cpp.
6 mardi
10 octobre
(groupe 20)

jeudi
12 octobre
(groupe 40)
Arbres binaires de recherche (suite à partir de diapo #22).
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.
Exercice: Examen 2015E / Q4 (b) et (c).
[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
12/13 octobre
Lab6 : Arbres AVL.
7 mardi
17 octobre
(groupe 20)

jeudi
19 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 - Liste d'épicerie

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

jeudi
26 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: Les solutionnaires seront débloqués à 16h25.
jeudi/vendredi
26/27 octobre
Lab8 : Dictionnaires (ArbreMap).
9 dimanche
29 octobre
09h30 - 12h30
Examen de mi-session
mardi
31 octobre
(groupe 20)

jeudi
2 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
2/3 novembre
Lab9 : séance de consultation avec les démonstrateurs.
10 mardi
7 novembre
(groupe 20)

jeudi
9 novembre
(groupe 40)
Retour sur l'examen de mi-session:
TP2 : Report de la date de remise d'une semaine ?
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
9/10 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
14 novembre
(groupe 20)

jeudi
16 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
16/17 novembre
Lab11 : Graphes.
12 mardi
21 novembre
(groupe 20)

jeudi
23 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
23/24 novembre
Lab12 : Graphes (suite).
13 mardi
28 novembre
(groupe 20)

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

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

jeudi
14 décembre
(groupe 40)
Révision. Préparez vos questions.

Examens finaux antérieurs.

jeudi/vendredi
14/15 décembre
Lab15 : assistance TP3.
16 dimanche
17 décembre

Examen final de 9h30 à 12h30

mercredi
20 décembre

Heure limite pour remettre le TP3: 24h00 (23h59 + 1 minute).

Résultats du TP3: Résultats de l'examen final:

Bibliographie

Obligatoire

Recommandées

Complémentaires

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.