Notes de cours

I. Échauffement (3 heures)
  • factorielle, nombres Fibonacci
  • algorithme d'Euclide
  • tours de Hanoï
  • variables locales et la pile d'exécution
Références
  • Notes 00 sur le plan de cours: >PDF icon PDF.
  • Notes 01 sur la récursion: >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 (4 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
  • Notes 02 sur la liste chaînée: >PDF icon PDF.
  • Notes 03 sur les tableaux: >PDF icon PDF.
  • Sedgewick cover Sedgewick, chapitres 3 et 4.
  • 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
III. Analyse d'algorithmes (2.5 heures)
  • notation asymptotique
  • techniques de preuve
  • analyse d'algorithmes
  • Notes 04 sur l'analyse d'algorithmes: >PDF icon PDF.
  • 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. Récursion et arbres (3 heures)
  • diviser pour régner, récursion terminale
  • arbres: arbres ordonnés, arbres numérotés
  • parcours d'arbres
  • arbre de syntaxe
  • Notes 05 sur les arbres et les techniques de récursion: >PDF icon PDF.
  • Sedgewick cover Sedgewick, chapitre 5, sauf 5.8.
  • Wikipedia logo Wikipedia: récursion terminale FR EN | arbre binaire FR EN
V. Appartenance-union (2.5 heures)
  • TA appartenance-union (union-find)
  • logarithme itéré, fonction d'Ackermann
  • Notes 06 sur appartenance-union: >PDF icon PDF.
  • 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é (4 heures)
Sujets
  • TAD file de priorité
  • Tas binaire et tas d-aire
  • Tri par tas
Références
  • Notes 07 sur le tas binaire: >PDF icon PDF.
  • Notes 08 sur le tri par tas: >PDF icon PDF.
  • Sedgewick cover Sedgewick, sections 9.1-9.5.
  • Wikipedia logo Wikipedia: file de priorité EN | tas FR EN | tas d-aire EN | tri par tas FR EN
Examen intra (2 heures)
  • Notes 09 sur les sujets à l'intra: >PDF icon PDF.
  • Intra: >PDF icon PDF.
VII. Algorithmes sur graphes (2 heures)
Sujets
  • Représentation de graphes, listes d'adjacence
  • Arbre couvrant minimal (Kruskal, Prim)
  • Le plus court chemin (Dijkstra)
Références
  • Notes 10 sur l'arbre couvrant minimal et le plus court chemin: >PDF icon PDF.
  • Wikipedia logo Wikipedia: liste d'adjacence EN | arbre couvrant minimal FR EN | algorithme de Kruskal FR EN | algorithme de Prim/Jarnik FR EN | algorithme de Dijkstra FR EN
VIII. Tris
Sujets
  • Tri par sélection
  • Tri par insertion
  • Tri de liste chaînée
  • Fusion
  • Tri par fusion
  • Tri rapide
  • Sélection (de la médiane ou k-ème élément)
Références
  • Notes 11 sur le tri par fusion et les tris élémentaires: >PDF icon PDF.
  • Notes 12 sur le tri rapide: >PDF icon PDF.
  • Sedgewick cover Sedgewick, sections 6.1-6.4, 6.6, 3.4, 6.9, 10.2; chapitres 7-8
  • Wikipedia logo Wikipedia: tri par insertion FR EN | tri par sélection FR EN | tri par fusion FR EN | tri rapide FR EN
IX. Arbres binaires de recherche
Sujets
  • Type abstrait de la table de symboles
  • Arbre binaire de recherche
  • Arbre splay
  • Arbre rouge et noir
  • Arbre 2-3-4
Références
  • Notes 13 sur les arbres binaires de recherche: >PDF icon PDF
  • Notes 14 sur les arbres splay: >PDF icon PDF.
  • Notes 15 sur les arbres rouge et noir: >PDF icon PDF.
  • Sedgewick cover Sedgewick, chapitre 12, sections 13.1-13.4
  • Wikipedia logo Wikipedia: arbre binaire de recherche FR EN | rotations EN | arbre splay EN | arbre rouge et noir EN FR | arbre 2-3-4 EN
X. Hachage
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
  • Notes 16 sur les tables de hachage : >PDF icon PDF.
  • Sedgewick cover Sedgewick, chapitre 14
  • Wikipedia logo Wikipedia: table de hachage FR EN | paradoxe des anniversaires FR EN
Révision pour le final
  • Notes 17 sur les sujets au final: >PDF icon PDF.

Devoirs

Devoir 1 à remettre le 25 janvier
Énoncé >PDF icon PDF.
Devoir 2 à remettre le 8 février
Énoncé >PDF icon PDF.
Devoir 3 à remettre le 13 mars
Énoncé >PDF icon PDF.
Devoir 4 à remettre le 25 septembre
Énoncé >PDF icon PDF.

Archives