Dernière mise à jour: 27 novembre 2008.
IFT2015: Structures de données
Automne 2008
Nouvelles de novembre:
- 21 novembre 2008: Vous pouvez maintenant aller regarder les finaux des années
passées, dans la section Examens .
- 21 novembre 2008: Les notes de cours du lundi 1 décembre et mardi 2 décembre sont
maintenant disponibles sous l'onglet Notes de cours .
- 27 novembre 2008: Les exercices pour les travaux pratiques du vendredi 28 novembre sont
maintenant disponibles sous l'onglet Travaux Pratiques .
- 21 novembre 2008: Les notes de cours du lundi 24 novembre et mardi 25 novembre sont
maintenant disponibles sous l'onglet Notes de cours .
- 3 novembre 2008: L'énoncé du devoir 4 est maintenant disponible dans la
section Devoirs . Vous devez remettre le devoir le mardi 9 décembre 2008 , avant 16h00.
- 18 novembre 2008: Les exercices pour les travaux pratiques du vendredi 21 novembre sont
maintenant disponibles sous l'onglet Travaux Pratiques .
- 12 novembre 2008: Les notes de cours du lundi 17 novembre et mardi 18 novembre sont
maintenant disponibles sous l'onglet Notes de cours .
- 10 novembre 2008: Les exercices pour les travaux pratiques du vendredi 13 novembre sont
maintenant disponibles sous l'onglet Travaux Pratiques .
- 7 novembre 2008: Les notes de cours du lundi 10 novembre et mardi 11 novembre sont
maintenant disponibles sous l'onglet Notes de cours .
- 4 novembre 2008: Les exercices pour les travaux pratiques du vendredi 7 novembre sont
maintenant disponibles sous l'onglet Travaux Pratiques .
- 3 novembre 2008: L'énoncé du devoir 3 est maintenant disponible dans la
section Devoirs . Vous devez remettre le devoir le lundi 17 novembre 2008 , avant 16h00.
Professeur et démonstrateurs:
Horaire et locaux:
Cours théorique:
LUNDI 10h30-12h30 A.A. 1175
MARDI 11h30-12h30 A.A. 1175
Travaux pratiques:
VENDREDI 11h30-13h30 X-117
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 3,4 et 5,
environ 6 heures)
Listes avec priorité. (Chapitre 8, environ 3 heures)
Arbres: Rappels sur les arbres binaires de recherche, arbres AVL,
arbres de recherche généralisés, arbres (2,4), arbres rouges-noirs.
(Chapitres 7 et 10, environ 12 heures)
Dictionnaires: Tables et fonctions de hachage, méthode de
recherche avec mémoire externe. (Chapitres 9, environ 6 heures)
Graphes: graphes orientés, graphes avec poids, parcours de
graphes, arbre minimal couvrant un graphe, récupération de mémoire.
(Chapitre 13, environ 12 heures)
Description du cours
( Annuaire)
Manuel obligatoire:
Michael T. Goodrich et Roberto Tamassia, Data Structures and Algorithms in JAVA (4th edition),
John Wiley & Sons, Inc., 2006.
Autres références:
- M.A. Weiss, Data Structures and Algorithms Analysis in JAVA (Second edition), Addison Wesley, 2006.
- A. Drozdek, Data Structures and Algorithms in JAVA (Second edition), Thomson, Course Technology, 2005.
- R. Sedgewick, Algorithms in Java Parts 1-4 (Third edition), Addison Wesley, 2003.
- 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: 25%
FINAL: 35%
DEVOIRS: 40% (4 devoirs de 10%)
Pour réussir le cours, un étudiant doit obtenir une
note d'au moins 30/60, sur le cumulatif des 2 examens, et une note de 60% au total.
Devoirs:
Énoncé Devoir1.pdf
Énoncé Devoir2.pdf
Énoncé Devoir3.pdf
Énoncé Devoir4.pdf
Les parties théoriques et pratiques des devoirs
sont à remettre à la date indiquer sur l'énoncé.
Chaque étudiant doit remettre sa copie des devoirs 1 et 3.
Les devoirs 2 et 4 peuvent être fait en équipe de deux.
Une seule copie est alors remise pour l'équipe.
Examens des années passées:
Final Hiver 2004 Ici
Final Hiver 2005 Ici
Notes de cours:
- lundi 8 septembre 2008: (2 heures)
- mardi 9 septembre 2008: (1 heure)
Révision mathématiques
- Sommations
- Méthodes de preuve
- Logarithmes et exposants
- lundi 15 septembre 2008: (2 heures)
- mardi 16 septembre 2008: (1 heure)
- lundi 22 septembre 2008: (2 heures)
- mardi 23 septembre 2008: (1 heure)
Application des arbres binaires
- Arbres de codage de Huffman
- lundi 29 septembre 2008: (2 heures)
- mardi 30 septembre 2008: (1 heure)
- lundi 6 octobre 2008: (2 heures)
- mardi 7 octobre 2008: (1 heure)
Tables et fonctions de hachage
- lundi 13 octobre 2008: Congé férié
- mardi 14 octobre 2008: Congé, en conférence
Révision disponible ici
- lundi 20 octobre et mardi 21 octobre 2008: Semaine de relâche
- lundi 27 octobre 2008: (2 heures)
Discussion intra
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
- mardi 28 octobre 2008: (1 heure)
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
- lundi 3 novembre et mardi 4 novembre 2008: (3 heures)
- lundi 10 novembre et mardi 11 novembre 2008: (3 heures)
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é
- lundi 17 novembre 2008 (2 heures)
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
- mardi 18 novembre 2008 (1 heure)
- lundi 24 novembre 2008: (2 heures)
Parcours de graphes( 1 transparent
par page ou 4 transparents par page )
- Parcours en profondeur
~ Définition
~ Algorithme
~ Complexité
~ Spécialisation
- Parcours en largeur
~ Définition
~ Algorithme
~ Complexité
~ Spécialisation
- mardi 25 novembre 2008: (1 heure)
- lundi 1 décembre 2008: (2 heures)
- mardi 2 décembre 2008:
Travaux Pratiques:
- Séance 1, vendredi 12 septembre 2008: (2 heures)
Exercices dans Goodrich et Tamassia:
- Chapitre 4, p.181: R-4.6, R-4.7, R-4.12 à R-4.19, R-4.23, R-4.28, C-4.5 et C-4.9
- Séance 2, vendredi 19 septembre 2008: (2 heures)
Exercices dans Goodrich et Tamassia:
- Chapitre 3, p. 149: R-3.6, R-3.7, R-3.9, R-3.10, R-3.11, C-3.2 et C-3.6
- Chapitre 5, p.217: R-5.1, R-5.3, R-5.4, R-5.6, R-5.7, C-5.1, C-5.4 et, si le temps le permet P-5.1
Aide Devoir 1
- Séance 3 vendredi 26 septembre 2008: (2 heures)
Exercices dans Goodrich et Tamassia:
- Arbres et arbres binaires: Chapitre 7: R-7.1, R-7.2, R-7.11, R-7.12, R-7.14, R-7.21, R-7.25, R-7.26, C-7.10
- Code de Huffman: Chapitre 12: R-12.12
- Partie implémentation: P-7.1 et P-7.3
Aide devoir 1
- Séance 4 vendredi 3 octobre 2008: (2 heures)
Exercices dans Goodrich et Tamassia:
- Files avec priorités et monceaux: Chapitre 8: R-8.1, R-8.2, R-8.8, R-8.11, R-8.13, R-8.14
Correction devoir 1 (si aucun retard)
- Séance 5 vendredi 10 octobre 2008: (2 heures)
Exercices dans Goodrich et Tamassia:
- Dictionnaires: Chapitre 9: R-9.1, R-9.4, R-9.5, R-9.6, R-9.7, R-9.8, R-9.9, R-9.12, R-9.14
- Séance 6 vendredi 31 octobre 2008: (2 heures)
Exercices dans Goodrich et Tamassia:
- Skip List: Chapitre 9: R-9.15, R-9.16, C-9.11, C-9.12
Correction devoir 2
- Séance 7 vendredi 7 novembre 2008: (2 heures)
Arbres de recherche binaires et arbres AVL
- Séance 8 vendredi 13 novembre 2008: (2 heures)
Arbres (2,4), Arbres (a,b) et B-arbres
- Chapitre 10: R 10.12, R 10.13, R 10.14, R 10.16, R 10.17 a)
- Séance 9 vendredi 21 novembre 2008: (2 heures)
Arbres rouge-noir + Intro Graphes
- Chapitre 10: R 10.15, R 10.17 b), R 10.18, R 10.19
- Chapitre 13: R 13.3, R 13.9
- Séance 10 vendredi 28 novembre 2008: (2 heures)
Parcours de graphes, graphes orientés, fermeture transitive
Exercices dans Goodrich et Tamassia:
- R 13.6, R 13.8, R 13.10, R 13.11, R 13.22, R 13.23, R 13.25
- Séance 11 vendredi 5 décembre 2008: (2 heures)
Ordre topologique, algorithme de Dijkstra, algorithme de Kruskal
Exercices dans Goodrich et Tamassia:
- R 13.12, R 13.14, R 13.19, R 13.26, R 13.27, R 13.28