Notes de cours
- I. Échauffement
(2.5 heures)
-
- factorielle, nombres Fibonacci
- algorithme d'Euclide
- tours de Hanoï
- variables locales et la pile d'exécution
- Références
- Préalables en Java: SW section 1.1
>HTML
- Note № 1 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
(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
-
- Note № 2 sur la liste chaînée:
> PDF.
Exercices:
> PDF.
- Note № 3 sur les tableaux:
> PDF.
- 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
- SW sections 1.2–1.3
>HTML
- Sedgewick chapitres 3–4
- III. Analyse d'algorithmes
(4 heures)
-
- notation asymptotique
- techniques de preuve
- analyse d'algorithmes
- étude empirique du temps de calcul
-
- Note № 4 sur l'analyse d'algorithmes:
> PDF.
- Note № 5 sur les aspects pratiques de performance:
> PDF.
- SW section 1.4
>HTML
- Sedgewick, chapitre 2.
- Wikipedia:
machine de Turing FR EN
| machine RAM EN
| nombre harmonique FR EN
| notation grand-O FR EN
- IV. Arbres
(2.5 heures)
-
- arbres: arbres enracinés et ordonnés
- parcours d'arbres
- arbre de syntaxe; notation infixe, préfixe, postfixe
-
- Note № 6 sur les arbres :
> PDF.
- Sedgewick, sections 4.3, 5.4-5.7
- Wikipedia:
arbre binaire FR EN
| notation polonaise FR EN
| PostScript FR EN
| Lisp FR EN
- V. Appartenance-union
(2 heures)
-
- TA appartenance-union (union-find)
- union-by-rank, compression de chemin
- logarithme itéré, fonction d'Ackermann
-
- Note № 7 sur appartenance-union:
> PDF.
- SW section 1.5
>HTML
- Sedgewick, section 1.3.
- Wikipedia:
union-find FR EN
| logarithme itéré EN
| fonction d'Ackermann FR EN
- VI. Files de priorité
(2 heures)
-
- TAD file de priorité
- ordre de tas
- tas binaire
- tri par tas
- Références
- Note № 8 sur le tas binaire:
> PDF.
- Note № 8b sur le tri par tas:
> PDF.
- SW section 2.4
>HTML
-
Sedgewick, sections 9.1-9.6.
- Wikipedia:
file de priorité EN
| ordre de tas FR EN
| tas binaire FR EN
tri par tas FR EN
- VII. Algorithmes sur graphes
(4 heures)
-
- représentation de graphes, listes d'adjacence
- arbre couvrant minimal (Kruskal, Prim)
- le plus court chemin (Dijkstra)
- parcours en profondeur, parcours en largeur
- tri topologique
-
- Note № 9 sur l'arbre couvrant minimal et le plus court chemin:
> PDF.
- Note № 10 sur le parcours de graphes:
> PDF.
-
Sedgewick, sections 3.7, 5.8
- SW sections 4.1
>HTML;
4.3
>HTML
- Wikipedia:
liste d'adjacence EN
| arbre couvrant minimal FR EN
| algorithme de Kruskal FR EN
| algorithme de Prim/Jarník FR EN
| algorithme de Dijkstra FR EN
| parcours en profondeur FR EN
| graphe biparti FR EN
| graphe acyclique orienté FR EN
| tri topologique FR EN
- Examen intra
(2 heures)
- Note № 11 sur les sujets à l'intra:
> PDF.
- Énoncé :
> PDF.
- VII. Tris
(6 heures)
- Sujets
- Tri par sélection
- Tri par insertion
- Fusion
- Tri par fusion
- Tri rapide
- Références
- Note № 12 sur le tri par fusion et les tris élémentaires:
> PDF.
- Note № 13 sur le tri rapide:
> PDF.
- Note № 14 sur les variantes du tri rapide:
> PDF.
- Note № 14b sur les permutations:
>PDF.
-
Sedgewick, sections 6.1-6.4, 6.6, 6.9; chapitres 7-8
- SW sections
2.1 >HTML;
2.2 >HTML;
2.3 >HTML
- 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
5 heures
- Sujets
- Type abstrait de la table de symboles
- Arbre binaire de recherche
- Arbre rouge et noir
- Arbre 2-3-4
- Références
- Note № 15 sur les arbres binaires de recherche:
> PDF.
- Note № 16 sur l'arbre rouge-et-noir:
> PDF.
- Note № 17 sur l'arbre 2-3-4:
> PDF.
- Sedgewick, chapitre 12, sections 13.3, 13.4
- SW sections
3.1 >HTML;
3.2 >HTML
- Wikipedia:
arbre binaire de recherche FR EN
| arbre rouge et noir EN FR
| arbre 2-3-4 EN
- IX. Hachage
3.5 heures
- 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
- Note № 18 sur les tables de hachage :
> PDF.
- Sedgewick, chapitre 14
- SW sections
3.4 >HTML;
3.5 >HTML
- Wikipedia:
table de hachage FR EN
| paradoxe des anniversaires FR EN
- Examen final
- Note № 19 sur les sujets au final
> PDF.
- Énoncé
> PDF.
- X. Divertissement
- Note № 20 sur le déploiement et le compteur probabiliste
> PDF.
- Wikipedia:
arbre splay EN
| compteur approximatif EN
Choréographie algorithmique (vidéos sur YouTube)
- tri par insertion (danse roumaine)
- tri par sélection (danse tsigane)
- tri par fusion (danse saxonne)
- tri rapide (danse hongroise)
Devoirs
- Devoir № 1
à remettre le 12 septembre
- Énoncé
> PDF
- Devoir № 2
à remettre le 30 septembre
- Énoncé
> PDF
>
lindenmayer.eps
- Devoir № 3
à remettre le 15 octobre
- Énoncé
> PDF
- Devoir № 4
à remettre le 13 novembre
- Énoncé
> PDF
- Devoir № 5
à remettre le 29 novembre
- Énoncé
> PDF
- Devoir № 6
à remettre le 12 décmbre
- Énoncé
> PDF
Archives