Notes de cours

I. Échauffement (2.5 heures)
  • factorielle, nombres Fibonacci
  • algorithme d'Euclide
  • tours de Hanoï
  • variables locales et la pile d'exécution
Références
  • Préalables en Java: SW cover SW section 1.1 >HTML
  • Note № 1 sur la récursion: >PDF icon PDF. Exercices: >PDF icon PDF.
  • Wikipedia logo Wikipedia: factorielle FR EN | formule de Stirling FR EN | pile d'exécution FR EN | nombres Fibonacci FR EN | algorithme d'Euclide FR EN | tours de Hanoï FR EN
II. Listes (5 heures)
  • notions de type abstrait, implantation, client, interface
  • manipulation de tableaux
  • listes chaînées
  • sentinelles, listes doublement chaînées, listes circulaires
  • traitement de listes: parcours, insertion, suppression
  • piles et files
  • Note № 2 sur la liste chaînée: >PDF icon PDF. Exercices: >PDF icon PDF.
  • Note № 3 sur les tableaux: >PDF icon PDF.
  • Wikipedia logo Wikipedia: liste chaînée FR EN | recherche séquentielle EN | sentinelle EN | tableau FR EN | pile FR EN | file FR EN | analyse amorti (crédit-débit) EN | dèque EN
  • Sedgewick cover SW sections 1.2–1.3 >HTML
  • Sedgewick cover Sedgewick chapitres 3–4
III. Analyse d'algorithmes (4 heures)
  • notation asymptotique
  • techniques de preuve
  • analyse d'algorithmes
  • étude empirique du temps de calcul
  • Note № 4 sur l'analyse d'algorithmes: >PDF icon PDF.
  • Note № 5 sur les aspects pratiques de performance: >PDF icon PDF.
  • Sedgewick cover SW section 1.4 >HTML
  • Sedgewick cover Sedgewick, chapitre 2.
  • Wikipedia logo Wikipedia: machine de Turing FR EN | machine RAM EN | nombre harmonique FR EN | notation grand-O FR EN
IV. Arbres (2.5 heures)
  • arbres: arbres enracinés et ordonnés
  • parcours d'arbres
  • arbre de syntaxe; notation infixe, préfixe, postfixe
  • Note № 6 sur les arbres : >PDF icon PDF.
  • Sedgewick cover Sedgewick, sections 4.3, 5.4-5.7
  • Wikipedia logo Wikipedia: arbre binaire FR EN | notation polonaise FR EN | PostScript FR EN | Lisp FR EN
V. Appartenance-union (2 heures)
  • TA appartenance-union (union-find)
  • union-by-rank, compression de chemin
  • logarithme itéré, fonction d'Ackermann
  • Note № 7 sur appartenance-union: >PDF icon PDF.
  • Sedgewick cover SW section 1.5 >HTML
  • Sedgewick cover Sedgewick, section 1.3.
  • Wikipedia logo Wikipedia: union-find FR EN | logarithme itéré EN | fonction d'Ackermann FR EN
VI. Files de priorité (2 heures)
  • TAD file de priorité
  • ordre de tas
  • tas binaire
  • tri par tas
Références
  • Note № 8 sur le tas binaire: >PDF icon PDF.
  • Note № 8b sur le tri par tas: >PDF icon PDF.
  • Sedgewick cover SW section 2.4 >HTML
  • Sedgewick cover Sedgewick, sections 9.1-9.6.
  • Wikipedia logo Wikipedia: file de priorité EN | ordre de tas FR EN | tas binaire FR EN tri par tas FR EN
VII. Algorithmes sur graphes (4 heures)
  • représentation de graphes, listes d'adjacence
  • arbre couvrant minimal (Kruskal, Prim)
  • le plus court chemin (Dijkstra)
  • parcours en profondeur, parcours en largeur
  • tri topologique
  • Note № 9 sur l'arbre couvrant minimal et le plus court chemin: >PDF icon PDF.
  • Note № 10 sur le parcours de graphes: >PDF icon PDF.
  • Sedgewick cover Sedgewick, sections 3.7, 5.8
  • Sedgewick cover SW sections 4.1 >HTML; 4.3 >HTML
  • Wikipedia logo Wikipedia: liste d'adjacence EN | arbre couvrant minimal FR EN | algorithme de Kruskal FR EN | algorithme de Prim/Jarník FR EN | algorithme de Dijkstra FR EN | parcours en profondeur FR EN | graphe biparti FR EN | graphe acyclique orienté FR EN | tri topologique FR EN
Examen intra (2 heures)
  • Note № 11 sur les sujets à l'intra: >PDF icon PDF.
  • Énoncé : >PDF icon PDF.
VII. Tris (6 heures)
Sujets
  • Tri par sélection
  • Tri par insertion
  • Fusion
  • Tri par fusion
  • Tri rapide
Références
  • Note № 12 sur le tri par fusion et les tris élémentaires: >PDF icon PDF.
  • Note № 13 sur le tri rapide: >PDF icon PDF.
  • Note № 14 sur les variantes du tri rapide: >PDF icon PDF.
  • Note № 14b sur les permutations: >PDF iconPDF.
  • Sedgewick cover Sedgewick, sections 6.1-6.4, 6.6, 6.9; chapitres 7-8
  • Sedgewick cover SW sections 2.1 >HTML; 2.2 >HTML; 2.3 >HTML
  • Wikipedia logo Wikipedia: tri par insertion FR EN | tri par sélection FR EN | tri par fusion FR EN | tri rapide FR EN
VIII. Arbres binaires de recherche 5 heures
Sujets
  • Type abstrait de la table de symboles
  • Arbre binaire de recherche
  • Arbre rouge et noir
  • Arbre 2-3-4
Références
  • Note № 15 sur les arbres binaires de recherche: >PDF icon PDF.
  • Note № 16 sur l'arbre rouge-et-noir: >PDF icon PDF.
  • Note № 17 sur l'arbre 2-3-4: >PDF icon PDF.
  • Sedgewick cover Sedgewick, chapitre 12, sections 13.3, 13.4
  • Sedgewick cover SW sections 3.1 >HTML; 3.2 >HTML
  • Wikipedia logo Wikipedia: arbre binaire de recherche FR EN | arbre rouge et noir EN FR | arbre 2-3-4 EN
IX. Hachage 3.5 heures
Sujets
  • Fonctions de hachage: méthode de la division, de la multiplication, hachage universel
  • Chaînage séparé
  • Adressage ouvert : sondage linéaire, double hachage
Références
  • Note № 18 sur les tables de hachage : >PDF icon PDF.
  • Sedgewick cover Sedgewick, chapitre 14
  • Sedgewick cover SW sections 3.4 >HTML; 3.5 >HTML
  • Wikipedia logo Wikipedia: table de hachage FR EN | paradoxe des anniversaires FR EN
Examen final
  • Note № 19 sur les sujets au final >PDF icon PDF.
  • Énoncé > PDF icon PDF.
X. Divertissement
  • Note № 20 sur le déploiement et le compteur probabiliste >PDF icon PDF.
  • Wikipedia logo Wikipedia: arbre splay EN | compteur approximatif EN
Choréographie algorithmique (vidéos sur YouTube)
  • tri par insertion (danse roumaine) Youtube icon
  • tri par sélection (danse tsigane) Youtube icon
  • tri par fusion (danse saxonne) Youtube icon
  • tri rapide (danse hongroise) Youtube icon

Devoirs

Devoir № 1 à remettre le 12 septembre
Énoncé >PDF icon PDF
Devoir № 2 à remettre le 30 septembre
Énoncé >PDF icon PDF >lindenmayer.eps
Devoir № 3 à remettre le 15 octobre
Énoncé >PDF icon PDF
Devoir № 4 à remettre le 13 novembre
Énoncé >PDF icon PDF
Devoir № 5 à remettre le 29 novembre
Énoncé >PDF icon PDF
Devoir № 6 à remettre le 12 décmbre
Énoncé >PDF icon PDF

Archives