Département d'informatique et de recherche
opérationnelle
IFT2010 : Structures de données (Automne 2005)
| Démonstrateur |
Disponibilité |
| Jean-François
Bérubé |
Jeudi 15h00 - 16h00 au 3484 (dans le CRT) |
| François Duranleau |
Mardi 15h30 - 16h30 au 2388 |
Nous répondons aussi à vos questions par courriel:
dift2010@iro.umontreal.ca
Cours théorique :
LUNDI 10h30-12h30 A.A. 1355
MARDI 11h30-12h30 A.A. 1355
Travaux pratiques :
VENDREDI 11h30-13h30 A.A. 1177 et A.A. 1140. Début: le 16
septembre.
Cours magistral supplémentaire: VENDREDI le 9 septembre, 11h30-13h30
A.A. 1140
Barème (seuil à
45%):
| Examen intra | 30% |
| Examen final | 40% |
| TP (4) | 30% |
Devoirs :
- Devoir
1 (À remettre le vendredi 30 septembre avant 11h30)
PQueue.java,
TestPQ.java,
Elem.java
- Devoir
2 (À remettre le vendredi 14 octobre avant 11h30)
FileDescriptor.java,
FileDescriptorCatalog.java,
FileDescriptorIterator.java,
Random.java
La documentation: doc/
TestCatalog.java,
input1,
input2
NOUVEAU: Voici une solution possible pour ce devoir: FileDescriptorCatalogImpl.java
- Devoir
3 (À remettre le vendredi 11 novembre avant 11h30)
EchecBD.java,
Hash.java,
Equal.java,
Echiquier.java
La documentation: doc/
chess.pgn,
chess_subset.pgn,
TestEchecBD.java
NOUVEAU:
HashProfiler.java,
EqualProfiler.java,
Profiler.java
Pour un approfondissement sur les generics de Java, voici
un document intéressant: generics-tutorial.pdf
- Devoir 4
(À remettre le vendredi 2 décembre avant 11h30)
fichiers.tar.gz
Démonstrations :
16 septembre:
- Tri topologique
- Tableaux vs listes chaînées
23 septembre:
- Opérations sur un monceau
- Heapsort
- Preuve que i est une feuille ssi
2i > n - 2
- Freelist
- Conversion notation infixe -> postfixe
30 septembre:
- Solutions du devoir 1
- Démonstrations des complexités exactes des
opérations de recherches dans des arborescences binaires
balancées et dégénées
- Étude de cas: Drozdek sections 3.9 et 4.4 (+ exercice
5. p. 212)
7 octobre:
- Implantation d'une liste avec un arbre AVL
- Splaying/semisplaying + exemple d'application pour compter
la fréquence des mots dans un texte
- Liste orthogonale et matrice creuse
- Nombre de rotations pour la suppression dans un arbre AVL
14 octobre:
- Solutions du devoir 2
- Solutions de l'intra A03
- Insertion dans une arborescence cousue
21 octobre:
- Solutions de l'intra
- Codage de Huffman
- Recherche de mots dans un texte
- Brève introduction aux generics de Java
4 novembre:
- Retour sur les listes orthogonales
- Formation d'amas dans les tables de hachage à adressage ouvert
- Ensembles disjoints (code: DisjointSets.java,
Maze.java)
11 novembre:
- Solutions du devoir 3
- Plus courts chemins: algorithme de Dijkstra
18 novembre:
- Skip lists
- Affichage des plus courts chemins calculés par Dijkstra
- Exercice sur la gestion de mémoire
Manuel obligatoire :
A. Drozdek, Data Structures and Algorithms in Java (Second Edition), Thomson,
2005.
Guichet Étudiant:
Dernière m-à-j : 13 octobre 2005