Matériel

Notes de cours

1. Introduction
  • Notes de cours 00 sur le plan de cours: >PDF icon PDF.
2. Listes 4 heures
Sujets
  • Notions de type abstrait, implantation, client, interface
  • Listes chaînées
  • Sentinelles, listes doublement chaînées, listes circulaires
  • Traitement de listes: parcours, insertion, suppression
  • Piles et files
Références
  • Notes de cours 01 sur la liste chaînée: >PDF icon PDF
  • Notes de cours 02 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 6 heures
Sujets
  • Notation asymptotique
  • Techniques de preuve
  • Analyse d'algorithmes
Références
  • Notes de cours 03 sur la croissance de fonctions: >PDF icon PDF.
  • Notes de cours 03A sur les fondations mathématiques: >PDF icon PDF.
  • Notes de cours 04 sur l'analyse d'algorithmes: >PDF icon PDF.
  • Sedgewick cover Sedgewick, chapitre 2.
  • Wikipedia logo Wikipedia: assembleur FR EN | machine de Turing FR EN | machine RAM EN | formule de Stirling FR EN | nombre harmonique FR EN | notation grand-O FR EN
4. Récursion 4 heures
Sujets
  • Récursion, récursion terminale, diviser pour régner
  • Arbres: arbres ordonnés, arbres numérotés
  • Parcours d'arbres
Références
  • Notes de cours 05 sur les récurrences: >PDF icon PDF.
  • Notes de cours 06 sur les arbres: >PDF icon PDF.
  • Sedgewick cover Sedgewick, chapitre 5, sauf 5.8.
  • Wikipedia logo Wikipedia: nombres Fibonacci FR EN | récursion terminale FR EN | arbre binaire FR EN | notation polonaise FR EN | PostScript FR EN
5. Files de priorité 5 heures
Sujets
  • TAD file de priorité
  • Tas binaire et tas d-aire
  • Tri par tas
Références
  • Notes de cours 07 sur le tas binaire: >PDF icon PDF.
  • Notes de cours 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
6. Méthodes élémentaires de tri 1 heure
Sujets
  • Tri par séléction
  • Tri par insertion
  • Tri de liste chaînée
Références
  • Notes de cours 09 sur les tris: >PDF icon PDF.
  • Sedgewick cover Sedgewick, sections 6.1-6.4, 6.6, 3.4, 6.9
  • Wikipedia logo Wikipedia: tri par insertion FR EN | tri par sélection FR EN
Révision pour l'intra
  • Notes de cours 10 sur les sujets à l'intra: >PDF icon PDF.
7. Tri par fusion et tri rapide 5 heures
Sujets
  • Fusion de listes
  • Tri par fusion (ascendant et descendant)
  • Tri rapide
  • Sélection
Références
  • Notes de cours 11 sur le tri par fusion: >PDF icon PDF.
  • Notes de cours 12 sur le tri rapide: >PDF icon PDF.
  • Sedgewick cover Sedgewick, chapitres 7-8, section 10.2
  • Wikipedia logo Wikipedia: tri par fusion FR EN | tri rapide FR EN
8. 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 de cours 13 sur les arbres binaires de recherche: >PDF icon PDF.
  • Notes de cours 14 sur splaying: >PDF icon PDF.
  • Notes de cours 15 sur les arbres rouge et noir: >PDF icon PDF.
  • Notes de cours 16 sur les arbres 2-3-4: >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 AVL EN FR | arbre rouge et noir EN FR | arbre 2-3-4 EN
9. 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 de cours 17 sur les tables de hachage : >PDF icon PDF.
  • Notes de cours 18 sur hachage coucou : >PDF icon PDF.
  • Sedgewick cover Sedgewick, chapitre 14
  • Wikipedia logo Wikipedia: table de hachage FR EN | paradoxe des anniversaires FR EN | hachage coucou EN
Révision pour le final
  • Notes de cours 19 sur les sujets à au final: >PDF icon PDF.

Devoirs et examens

Devoir 1 à remettre le 31 janvier.
Énoncé >PDF icon PDF.
Devoir 2 à remettre le 8 février.
Énoncé >PDF icon PDF.
Devoir 3 à remettre le 14 mars.
Énoncé >PDF icon PDF.
Devoir 4 à remettre le 21 mars.
Énoncé >PDF icon PDF.
Devoir 5 à remettre le 29 mars.
Énoncé >PDF icon PDF.
Devoir 6 à remettre le 14 avril.
Énoncé >PDF icon PDF.

Examens finaux des années passées