Matériel
Notes de cours
- 1. Introduction >PDF [dernière modification: 24 janvier] 7 heures
- Sujets
- Plan de cours
- Contenu du cours
- Notions mathématiques: notation asymptotique, techniques de preuve
- Références
- 2. Types abstraits >PDF [dernière modification: 6 février] 6 heures
- Sujets
- Types abstraits
- Pile ADT
- Queue (file) ADT
- Liste ADT
- Références
- Acétates discutés : pages 0-6 (24 jan), 7-15 (26 jan), 16-35 (31 jan), 36 (2 fév), 37-42 (7 fév).
- Weiss, chapitre 3.
- Code source de Mark Weiss: implantation de la pile par un tableau, implantation de la la queue par un tableau.
- 3. Arbres >PDF [dernière modification: 7 mars] 7 heures
- Sujets
- Arborescences et arbres numerotés
- Arbres binaires de recherche
- Arbre AVL
- Arbre rouge et noir
- Arbre déployé (splay tree)
- B-arbres
- Références
- 4. Files de priorité >PDF [dernière modification: 16 mars] 3 heures
- Sujets
- TAD file de priorité
- Tas binaire
- Tas d-aire
- Applications: simulation d'événements discrets, bin packing, recherche A*
- Tri par tas (Heapsort)
- Références
- 5. Hachage >PDF [dernière modification: 21 mars] 4 heures
- Sujets
- TAD dictionnaire
- Fonctions de hachage: méthode de la division, de la multiplication, hachage universel
- Chaînage
- Adressage ouvert : sondage linéaire, sondage quadratique, double hachage
- Ensembles statiques
- Références
- 6. Graphes >PDF [dernière modification: 13 avril] 7 heures
- Sujets
- Notions de base: sommets, arcs, arêtes, adjacence, incidence, chemins, cycles
- Représentation de graphes en mémoire : matrice d'adjacence ou listes d'adjacence
- Parcours par largeur ou par profondeur
- Arbre couvrant minimal: algorithmes de Prim et de Kruskal
- Plus court chemin: algorithme de Dijkstra et de Bellman
- Références
- 7. Algorithmes de tri >PDF [dernière modification: 13 avril]
- Référence
- Weiss, sections 7.1, 7.2, 7.6.
Devoirs
La commande remise
ne fonctionne que sur la machine
remise.iro.umontreal.ca
.
À partir de frontal
(ou d'autres machines de DIRO),
les étudiant(e)s doivent donc taper :
ssh remise
pour effectuer une remise.
Sur la machine remise.iro.umontreal.ca
,
la commande remise ift2010 tp1 PSPile.java
est utilisé pour remettre PSPile.java
du devoir 1.
- Devoir 1 à remettre le 9 février.
- Énoncé >PDF (correction le 1 février).
- Solutions et commentaires (exercices 1-3)>PDF. (Solution à l'exercice 4 se trouve sur la page de démonstrations.)
- La classe
ListeChaine
: source Java et documentation. - J'ai reçu une question sur la notation nO(1). C'est l'ensemble de fonctions de la forme nh(n) où h(n)=O(1). Donc 3n2=nO(1) --- posez h(n)=2+lg 3/lg n=O(1).
- Devoir sans numéro à remettre le 15 février.
- Énoncé >PDF.
- Le devoir vaut 0 points : il est donc optionnel. Vous pouvez même choisir à garder votre anonymité en utilisant un pseudonym!
- Devoir 2 à remettre le 14 mars.
- Énoncé >PDF.
- Devoir 3 à remettre le 30 mars.
- Énoncé >PDF. (Exemple de sortie corrigée le 23 mars - il y a deux fichiers sur le premier disque au lieu de 4.)
- Notez que la classe
BinaryHeap
utilise d'autres classes:Overflow
etMyInteger
, toutes les trois dans le packageDataStructures
. Au lieu de l'interfaceDataStructures.Comparable
, utilisez l'interfacejava.lang.Comparable
(et donc ne copiez pas le fichierComparable.java
de Weiss). - Testez votre implantation sur des
listes avec 10, 100, 1000, 10000, 100000 et 1000000 fichiers
de tailles alétoires (a) 1-50000 et (b) 200000-700000.
Notez qu'il faudra utiliser le constructeur
BinaryHeap(capacity)
pour permettre plus que 100 disques. Pour générer les listes, utilisez la code de Guillaume Langelier:WorstFitTest
. Exemple: java WorstFitTest 10000 200000 700000 > liste-27-10k.txt. Les nombres entiers sur la liste d'entrée sont séparés par des espaces blanches (y inclut la nouvelle ligne'\n'
) : la sortie deWorstFitTest
utilise le séparateur espace' '
. - Évaluez la performance
de l'heuristique aprés avoir trié (dans l'ordre décroissant)
la liste à l'entrée.
Vous pouvez trier le fichier produit par
WorstFitTest
sous Unix par tr -s ' ' '\n' < liste-27-10k.txt | sort -nr | tr '\n' ' ' > liste-27-10k-trie.txt Remettez un rapport sur la performance de l'heuristique: dans un tableau, donnez le nombre de disques utilisés à chaque instance de test. Il faut donc remplir le tableau suivant:Nombre de fichiers 1-50k, non-trié 1-50k, trié 200-700k, non-trié 200-700k, trié 10 100 1000 10000 100000 1000000
- Notez que la classe
- Devoir 4 à remettre le 13 mars.
- Énoncé >PDF.