Notes de cours

1. É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
2. 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
3. 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
4. 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
5. 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
6. Files de priorité
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.
  • Sedgewick cover Sedgewick, sections 9.1-9.5.
  • Wikipedia logo Wikipedia: file de priorité EN | tas FR EN

Devoirs

Devoir 1 à remettre le 25 janvier
Énoncé >PDF icon PDF.
Devoir 2 à remettre le 8 février
Énoncé >PDF icon PDF.
Devoir 3 (à venir)
Devoir 4 (à venir)

Archives