Dernière mise à jour: 1 décembre 2009.
IFT2015: Structures de données
Automne 2009
Nouvelles de novembre:
- 24 novembre 2009: Les notes de cours pour le reste de la session sont
maintenant disponibles sous l'onglet Notes de cours .
- 24 novembre 2009: Les exercices pour les travaux pratiques du mercredi 25 novembre et mercredi 2 décembre sont
maintenant disponibles sous l'onglet Travaux Pratiques .
- 13 novembre 2009: Le solutionnaire des exercices pour les travaux pratiques du
mercredi 11 novembre sont maintenant disponibles sous l'onglet Travaux Pratiques .
- 10 novembre 2009: L'énoncé du devoir 2 est maintenant disponible
dans la section Devoirs . Vous devez remettre le devoir le mardi
24 novembre 2009 , avant 16h00.
- 10 novembre 2009: Les exercices pour les travaux pratiques du mercredi 18 novembre sont
maintenant disponibles sous l'onglet Travaux Pratiques .
- 9 novembre 2009: Le solutionnaire des exercices pour les travaux pratiques du
mercredi 4 novembre sont maintenant disponibles sous l'onglet Travaux Pratiques .
- 3 novembre 2009: Les exercices pour les travaux pratiques du mercredi 11 novembre sont
maintenant disponibles sous l'onglet Travaux Pratiques .
- 2 novembre 2009: Les examens finaux des années passées sont maintenant disponibles dans la section
Examens .
- 2 novembre 2009: Les notes de cours sur les arbres de recherche sont
maintenant disponibles sous l'onglet Notes de cours .
Professeur et démonstrateurs:
Horaire et locaux:
Cours théorique:
LUNDI 10h30-12h30 A.A. 1177
MARDI 11h30-12h30 A.A. 1140
Travaux pratiques:
MERCREDI 15h30-17h30 Z-255
Objectifs et contenu:
Objectifs:
Le cours IFT2015 vise à familiariser l'étudiant avec les techniques de base
pour l'organisation, la manipulation et la recherche de données. Le but du cours
est d'être capable de choisir les structures de données qui rendent un
programme le plus efficace possible, que ce soit en terme du temps d'exécution ou
de l'espace mémoire utilisé.
Contenu:
Introduction et rappels: Mesure de complexité, types abstraits
de données, listes chaînées, piles, files. (Chapitres 2,3 et 4,
environ 6 heures)
Arbres binaires, files avec priorité. (Chapitre 5,9, environ 6 heures)
Dictionnaires: Tables et fonctions de hachage, méthode de
recherche avec mémoire externe. (Chapitres 14, environ 6 heures)
Arbres: Rappels sur les arbres binaires de recherche, arbres AVL,
arbres de recherche généralisés, arbres (2,4), arbres rouges-noirs et B-arbres.
(Chapitres 5, 12, 13 et 16.3, environ 9 heures)
Graphes: graphes orientés, graphes avec poids, parcours de
graphes, arbre minimal couvrant un graphe, récupération de mémoire.
(Notes de cours et chapitre 5, environ 6 heures)
Description du cours
( Annuaire)
Manuel obligatoire:
Robert Sedgewick, Algorithms in Java Parts 1-4 (Third edition), Addison Wesley, 2003.
Autres références:
- M.A. Weiss, Data Structures and Algorithms Analysis in JAVA (Second edition), Addison Wesley, 2006.
- M. T. Goodrich et R. Tamassia, Data Structures and Algorithms in JAVA (4th edition),
John Wiley & Sons, Inc., 2006.
- A. Drozdek, Data Structures and Algorithms in JAVA (Second edition), Thomson, Course Technology, 2005.
- C.A. Shaffer, A Practical Introduction to Data Structures and Algorithm Analysis,
Prentice-Hall, 1998.
- T.A. Standish, Data Structures in JAVA, Addison Wesley, 1998.
- A. Aho, J.E. Hopcroft and J.D. Ullman, Data Structures and Algorithms, Addison Wesley,
1983.
Évaluation:
INTRA: 30%
FINAL: 40%
DEVOIRS: 30%
Pour réussir le cours, un étudiant doit obtenir une
note d'au moins 35/70, sur le cumulatif des 2 examens, et une note de 60% au total.
Devoirs:
Examens des années passées:
Notes de cours:
- mardi 1 septembre et mardi 8 septembre: (2 heures)
- lundi 14 septembre et mardi 15 septembre: (3 heures)
- lundi 21 septembre et mardi 22 septembre: (3 heures)
- lundi 28 septembre et mardi 29 septembre: (3 heures)
- lundi 5 octobre et mardi 6 octobre: (3 heures)
- mardi 13 octobre: (1 heure)
- du lundi 26 octobre au mardi 3 novembre: (environ 5 heures)
Dictionnaires ( 1 transparent par page
ou 4 transparents par page )
- Introduction
- Définition d'un dictionnaire particulier (maps)
- Testeur d'égalités
- Implémentation utilisant une liste doublement chaînée
- TAD Dictionnaire
- Tables et fonctions de hachage
- Résolution de collision par hachage ouvert ou fermé
- Hachage parfait
Dictionnaires ordonnés et "Skip List" ( 1 transparent par page
ou 4 transparents par page )
- TAD Dictionnaires Ordonnés
~ Définition et nouvelles opérations
~ "Look-up Tables"
~ Recherche binaire
~ Performances
- "Skip List"
~ Définition
~ Algorithmes randomisés
~ Exécution des opérations
* de recherche
* d'insertion
* de suppression
~ Implémentation
~ Complexité en espace
~ Complexité en temps
- du mardi 3 novembre au mardi 24 novembre: (environ 9 heures)
Introduction arbres de recherche et arbres binaires de recherche ( 1 transparent par
page ou 4 transparents par page )
- Introduction aux arbres de recherche
~ Rappels dictionnaires ordonnés et implémentations "skip list"
~ Brève description des arbres de recherche que nous verrons dans les prochaines semaines:
* arbres binaires de recherche
* arbres AVL
* "splay tree" ou arbres auto-balancé
* arbres de recherche généralisés
* arbres (2,4)
* B-arbres
* arbres rouges-noirs
- Arbres binaires de recherche
~ Définition
~ Insertion, recherche et supression
~ Complexité en espace
~ Complexité en temps
Arbres AVL ( 1 transparent par page ou 4 transparents par page )
- Définition
- Hauteur d'un arbre AVL
- Restructurations
~ version Goodrich et Tamassia
~ rotations simples
~ rotations doubles
~ lois associatives
- Opérations
~ de recherche
~ d'insertion
~ de suppression
- Complexité en espace
- Complexité en temps
Arbres auto-balancés
( 1 transparent
par page ou 4 transparents par page )
Arbres de recherche généralisés, arbres(2,4) et B-arbres
Recherche en mémoire externe, arbres (a,b) et B-arbres ( 1 transparent
par page ou 4 transparents par page )
- Arbres (a,b)
~ Définition
~ Paramètres pour recherche externe
- B-Arbres
~ Définition
~ Complexité
Arbres rouge-noir( 1 transparent
par page ou 4 transparents par page )
- Arbres rouge-noir
~ Définition
~ Arbres rouge-noir versus arbres (2,4)
~ Recherche
~ Insertion, recherche et supression
~ Restructurations et recolorations
~ Complexité en temps
- lundi 30 novembre: (2 heures)
- mardi 1er décembre: (1 heure)
- lundi 7 décembre: (2 heures)
Travaux Pratiques:
- Séance 1, mercredi 16 septembre 2009: (2 heures)
- Séance 2, mercredi 23 septembre 2009: (2 heures)
- Séance 3, mercredi 30 septembre 2009: (2 heures)
- Séance 4, mercredi 7 octobre 2009: (2 heures)
- Séance 5, mercredi 14 octobre 2009: (2 heures)
- Séance 6, mercredi 28 octobre 2009: (2 heures)
Solutionnaire examen
- Séance 7, mercredi 4 novembre 2009: (2 heures)
- Séance 8, mercredi 11 novembre 2009: (2 heures)
- Séance 9, mercredi 18 novembre 2009: (2 heures)
ANNULÉE
- Séance 10, mercredi 25 novembre 2009: (2 heures)
- Séance 11, mercredi 2 décembre 2009: (2 heures)
Examen des années passées (.pdf disponibles dans la section Examens ).