Dernière mise à jour: 24 novembre 2009.
IFT2810: Structures de données
Automne 2009
Nouvelles pour novembre:
- 24 novembre 2009: La révision finale est maintenant disponible sous l'onglet Notes de cours .
- 24 novembre 2009: Pendant la démo du 1er décembre, vous parlerez de l'examen final
que j'ai donné dans ce cours en 2007. Le .pdf de l'examen est disponible sous l'onglet
Travaux Pratiques .
- 24 novembre 2009: Les exercices pour les travaux pratiques de ce soir
(désolé pour le retard) sont maintenant disponibles sous l'onglet Travaux Pratiques .
- 13 novembre 2009: L'énoncé du devoir 2 est maintenant disponible
dans la section Devoirs . Vous devez remettre le devoir le mardi
24 novembre 2009 .
- 3 novembre 2009: Les exercices pour les travaux pratiques du 10 novembre sont
maintenant disponibles sous l'onglet Travaux Pratiques .
Professeur et démonstrateurs:
Horaire et locaux:
Cours théorique:
MARDI 18h30-20h30, A.A. 1355
Travaux pratiques:
MARDI 20h30-21h30, A.A. 1355
Objectifs et contenu:
Objectifs:
Le cours IFT2810 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:
Mesure de complexité, types abstraits
de données, listes chaînées, récursivité. (Chapitres 2, 3 et 4)
Piles et Files (Chapitre 4)
Arbres binaires et files avec priorité. (Chapitre 5 et 9)
Arbres (Chapitres 12 et 13)
Dictionnaires (Chapitre 14)
Graphes (Chapitre 5 + notes de cours)
Description du cours
( Annuaire)
Manuel obligatoire:
Robert Sedgewick, Algorithmes en Java (3ieme édition), Pearson Education, 2004.
Autres références:
- M.T. Goodrich and R. Tamassia, Data Structures and Algorithms in JAVA (4th
edition), John Wiley et Sons, Inc., 2006.
- Weiss, M.A., Data Structures and Algorithm Analysis in Java, 2nd Edition, Pearson Education, 2007.
- 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:
Notes de cours:
- mardi 1 septembre 2009 et mardi 8 septembre: (4 heures)
- mardi 15 septembre 2009 et mardi 22 septembre: (4 heures)
- mardi 29 septembre 2009 à mardi 13 octobre 2009: (5-6 heures)
- mardi 3 novembre et mardi 10 novembre 2009: (environ 3 heures)
Dictionnaires ( 1 transparent par page
ou 4 transparents par page )
- Introduction
- Testeur d'égalités
- Implémentation utilisant une liste doublement chaînée
Tables et fonctions de hachage
- TAD Dictionnaires
- Fonctions de hachage
~ Codes de hachage
~ Fonctions de compression
- Tables de hachage
- Résolution de collisions
~ Par chaînage:
~ Par hachage fermé:
* Sondage linéaire
* Sondage quadratique
* Hachage aléatoire
- Performance du hachage
- mardi 10 novembre au mardi 1 décembre 2009: (environ 6 heures)
Introduction arbres de recherche et arbres binaires de recherche ( 1 transparent par
page )
- Dictionnaires ordonnés
- Brève description des arbres de recherche:
~ 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 de recherche généralisés et arbres(2,4) ( 1 transparent
par page ou 4 transparents par page )
- Introduction aux arbres de recherche généralisés
~ Définition
~ Implémentation
~ Généralisation du parcours symétrique
~ Recherche
- Arbres(2,4) (si le temps le permet)
~ Définition
~ Hauteur
~ Insertion, recherche et supression
~ Complexité en espace
~ Complexité en temps
- mardi 1 décembre 2009: (2 heure)
Travaux Pratiques:
- Séance 1, mardi 8 septembre 2009: (1 heure)
Exercices sur les opérations élémentaires:
- Séance 2, mardi 15 septembre 2009: (1 heure)
Retour sur les exercices d'opérations élémentaires
Exercices sur la notation asymptotique:
Si le temps le permet, exercices sur les techniques de preuve:
Exercices 3 (les numéros 1 à 3 méthode de preuves, seulement)
- Séance 3, mardi 22 septembre 2009: (1 heure)
Exercices sur les techniques de preuves et les fonction récursives:
- Séance 4, mardi 29 septembre 2009: (1 heure)
Exercices sur les piles, les files et les listes chaînées
- Séance 5, mardi 6 octobre 2009: (1 heure)
Exercices sur arbres et l'algorithme de Huffman
- Séance 6, mardi 10 novembre 2009: (1 heure)
- Séance 7, mardi 17 novembre 2009: (1 heure)
- Séance 8, mardi 24 novembre 2009: (1 heure)
- Séance 9, mardi 1 décembre 2009: (1 heure)