Matériel
Notes de cours
- 1. Introduction
-
- Notes de cours 00 sur le plan de cours:
>
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
- Notes de cours 02 sur les tableaux:
>
PDF
Sedgewick, chapitres 3 et 4.
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.
- Notes de cours 03A sur les fondations mathématiques:
>
PDF.
- Notes de cours 04 sur l'analyse d'algorithmes:
>
PDF.
Sedgewick, chapitre 2.
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.
- Notes de cours 06 sur les arbres:
>
PDF.
Sedgewick, chapitre 5, sauf 5.8.
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.
- Notes de cours 08 sur le tri par tas:
>
PDF.
Sedgewick, sections 9.1-9.5.
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.
Sedgewick, sections 6.1-6.4, 6.6, 3.4, 6.9
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.
- 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.
- Notes de cours 12 sur le tri rapide:
>
PDF.
Sedgewick, chapitres 7-8, section 10.2
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.
- Notes de cours 14 sur splaying:
>
PDF.
- Notes de cours 15 sur les arbres rouge et noir:
>
PDF.
- Notes de cours 16 sur les arbres 2-3-4:
>
PDF.
Sedgewick, chapitre 12, sections 13.1-13.4
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.
- Notes de cours 18 sur hachage coucou :
>
PDF.
Sedgewick, chapitre 14
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.
Devoirs et examens
- Devoir 1 à remettre le 31 janvier.
- Énoncé >
PDF.
- Devoir 2 à remettre le 8 février.
- Énoncé >
PDF.
- Devoir 3 à remettre le 14 mars.
- Énoncé >
PDF.
- Devoir 4 à remettre le 21 mars.
- Énoncé >
PDF.
- Devoir 5 à remettre le 29 mars.
- Énoncé >
PDF.
- Devoir 6 à remettre le 14 avril.
- Énoncé >
PDF.
Examens finaux des années passées
- Hiver 2006: >
PDF.
- Hiver 2007: >
PDF.
- Hiver 2009: >
PDF.
- Hiver 2010: >
PDF.
- Automne 2010: >
PDF.