Notes de cours
- I. É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.
- Notes 01 sur la récursion:
> PDF.
Exercices:
> PDF.
- 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
- II. 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.
Exercices:
> PDF.
- Notes 03 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
- III. Analyse d'algorithmes
(3 heures)
-
- notation asymptotique
- techniques de preuve
- analyse d'algorithmes
-
- Notes 04 sur l'analyse d'algorithmes:
> PDF.
- Sedgewick, chapitre 2.
- Wikipedia:
machine de Turing FR EN
| machine RAM EN
| nombre harmonique FR EN
| notation grand-O FR EN
- IV. Récursion et arbres
-
- 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.
- Sedgewick, chapitre 5, sauf 5.8.
- Wikipedia:
récursion terminale FR EN
| arbre binaire FR EN
- V. Files de priorité
- Sujets
- TAD file de priorité
- Tas binaire et tas d-aire
- Tri par tas
- Références
- Notes 06 sur le tas binaire:
> PDF.
-
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
- Notes 07 sur les sujets à l'intra:
> PDF.
- VI. Algorithmes sur graphes
-
- TA appartenance-union (union-find)
- logarithme itéré, fonction d'Ackermann
- Représentation de graphes, listes d'adjacence
- Arbre couvrant minimal (Kruskal, Prim)
- Le plus court chemin (Dijkstra)
-
- Notes 08 sur appartenance-union:
> PDF.
- Sedgewick, section 1.3.
- Notes 09 sur l'arbre couvrant minimal et le plus court chemin:
> PDF.
- Wikipedia:
union-find FR EN
| logarithme itéré EN
| fonction d'Ackermann FR EN
| liste d'adjacence EN
| arbre couvrant minimal FR EN
| algorithme de Kruskal FR EN
| algorithme de Prim/Jarnik FR EN
| algorithme de Dijkstra FR EN
- VII. Tris
- Sujets
- Tri par sélection
- Tri par insertion
- Tri de liste chaînée
- Fusion
- Tri par fusion
- Tri rapide
- Sélection (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.
- Notes 11 sur le tri rapide:
> PDF.
-
Sedgewick, sections 6.1-6.4, 6.6, 3.4, 6.9, 10.2; chapitres 7 et 8
- Wikipedia:
tri par insertion FR EN
| tri par sélection FR EN
| tri par fusion FR EN
| tri rapide FR EN
- VIII. 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.
- Notes 13 sur les arbres rouge et noir:
> PDF.
- Sedgewick, chapitre 12, sections 13.1, 13.3, 13.4
- Wikipedia:
arbre binaire de recherche FR EN
| arbre rouge et noir EN FR
| arbre 2-3-4 EN
- IX. 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 14 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 15 sur les sujets au final:
> PDF.
Devoirs
- Devoir 1
à remettre le 1er novembre
- Énoncé
> PDF
[exemple en 1.3d corrigé le 24 octobre].
- Devoir 2
à remettre le 3 décembre
- Énoncé
> PDF
- Devoir 3
à remettre le 14 décembre
- Énoncé
> PDF
- Devoir 4
à remettre le 21 décembre
- Énoncé
> PDF
Archives