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:
> FR.
- Notes 01 sur les récursions:
> FR
EN.
- 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:
> FR
- Notes 03 sur les tableaux:
> FR
- 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
-
- notation asymptotique
- techniques de preuve
- analyse d'algorithmes
-
- Notes 04 sur l'analyse d'algorithmes:
> FR.
- Sedgewick, chapitre 2.
- 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:
> FR.
- Notes 06 sur les arbres:
> FR.
- Sedgewick, chapitre 5, sauf 5.8.
- 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:
> FR.
- Notes 08 sur le tri par tas:
> FR
(mise à jour: erreur sur page 1 - initialisation de H[j])
-
Sedgewick, sections 9.1-9.5.
- 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:
> FR
(mise à jour: numérotation des sections)
- Notes 11 sur le tri rapide:
> FR .
-
Sedgewick, sections 6.1-6.4, 6.6, 3.4, 6.9, 10.2; chapitres 7-8
- 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
(mise à jour: erreur sur page 3 - Cas 1 de suppression)
- Notes 13 sur les arbres splay:
> PDF.
- Notes 14 sur les arbres équilibrés:
> PDF.
- Notes 15 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
- 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.
- Sedgewick, chapitre 14
- Wikipedia:
table de hachage FR EN
| paradoxe des anniversaires FR EN
- Révision pour le final
- Notes 17 sur les sujets au final:
> PDF.
Devoirs
- Devoir 1
à remettre le 16 septembre
- Énoncé
> PDF.
- Devoir 2
à remettre le 6 octobre
- Énoncé:
> PDF.
- Devoir 3
à remettre le 19 octobre
- Énoncé: > PDF.
- Devoir 4
à remettre le 10 novembre
- Énoncé: > PDF.
[énoncé de l'exercice 4.3 (10 points boni) est fixé le 21 novembre]
- Devoir 5
à remettre le 24 novembre
- Énoncé: > PDF.
- Devoir 6
à remettre le 5 décembre
- Énoncé: > PDF.
Archives