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 FR.
  • Notes 01 sur les récursions: >PDF icon FR PDF icon EN.
  • 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 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
  • Notes 02 sur la liste chaînée: >PDF icon FR
  • Notes 03 sur les tableaux: >PDF icon FR
  • 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
  • notation asymptotique
  • techniques de preuve
  • analyse d'algorithmes
  • Notes 04 sur l'analyse d'algorithmes: >PDF icon FR.
  • 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
  • programmation dynamique, récursion terminale, diviser pour régner
  • arbres: arbres ordonnés, arbres numérotés
  • parcours d'arbres
  • arbre de syntaxe
  • Notes 05 sur les techniques de récursion: >PDF icon FR.
  • Notes 06 sur les arbres: >PDF icon FR.
  • Sedgewick cover Sedgewick, chapitre 5, sauf 5.8.
  • Wikipedia logo Wikipedia: récursion terminale FR EN | arbre binaire FR EN | sous-somme maximale EN | programmation dynamique EN | notation polonaise FR EN | PostScript FR EN
5. 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 FR.
  • Notes 08 sur le tri par tas: >PDF icon FR (mise à jour: erreur sur page 1 - initialisation de H[j])
  • 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
6. Tris
Sujets
  • Tri par sélection
  • Tri par insertion
  • Tri de liste chaînée
  • Fusion
  • Tri par fusion
  • Tri rapide
  • Séléction (de la médiane ou k-ème élément)
Références
  • Notes 10 sur le tri par fusion et les tris élémentaires: >PDF icon FR (mise à jour: numérotation des sections)
  • Notes 11 sur le tri rapide: >PDF icon FR .
  • 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
7. 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 12 sur les arbres binaires de recherche: >PDF icon PDF (mise à jour: erreur sur page 3 - Cas 1 de suppression)
  • Notes 13 sur les arbres splay: >PDF icon PDF.
  • Notes 14 sur les arbres équilibrés: >PDF icon PDF.
  • Notes 15 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
8. 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 16 septembre
Énoncé >PDF icon PDF.
Devoir 2 à remettre le 6 octobre
Énoncé: >PDF icon PDF.
Devoir 3 à remettre le 19 octobre
Énoncé: >PDF icon PDF.
Devoir 4 à remettre le 10 novembre
Énoncé: >PDF icon PDF. [énoncé de l'exercice 4.3 (10 points boni) est fixé le 21 novembre]
Devoir 5 à remettre le 24 novembre
Énoncé: >PDF icon PDF.
Devoir 6 à remettre le 5 décembre
Énoncé: >PDF icon PDF.

Archives