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
  • Acétates gelés: pages 0-15 (10 jan), 16-18 (12 jan), 19-29 (17 jan), 30 (19 jan). 31-32 (24 jan).
  • Weiss, chapitres 1 et 2.
  • Jon Bentley. Algorithm design techniques. Communications of the ACM, 27:865-873 (1984). [quatre algorithmes pour le problème de subsequence sum] >HTML.
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
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
  • Acétates discutés : pages 0-8 (7 mars), 9-16 (9 et 16 mars).
  • Weiss, sections 6.1-6.5, 7.5
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
  • Acétates discutés : pages 0-12 (21 mars), 13-16 (23 et 28 mars).
  • Acétates de Sylvie Hamel : >HTML.
  • Weiss, chapitre 5.
  • Andrew Chi-Chih Yao. Should tables be sorted? Journal of the ACM, 28:615-628 (1981). [ensembles statiques - excursion par vélos] >HTML.
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
  • Acétates discutés : pages 0-10 (28 mars), 11-18 (29 et 30 mars), 19-30 (11 avril), 31-32 (13 avril).
  • Weiss, sections 9.1, 9.2., 9.3, 9.5.
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)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 et MyInteger, toutes les trois dans le package DataStructures. Au lieu de l'interface DataStructures.Comparable, utilisez l'interface java.lang.Comparable (et donc ne copiez pas le fichier Comparable.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 de WorstFitTest 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
    (Il suffit de mettre le résultat d'une seule expérience à chaque case au lieu d'une moyenne de quelque sort, mais utilisez la même liste dans une paire triée-non-triée.) Sommarisez votre expérience en français en quelques phrases et essayez d'expliquer la différence observée quand la liste est triée (ou s'il n'y a pas de différence, expliquez pourquoi...) Ne remettez pas les listes que vous avez utilisées dans les tests.
Devoir 4 à remettre le 13 mars.
Énoncé >PDF.