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.
- Notes 01 sur la récursion:
>
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
- 2. 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.
- 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
- 3. Analyse d'algorithmes
(2.5 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
- 4. Récursion et arbres
(3 heures)
-
- 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
- 5. Appartenance-union
(2.5 heures)
-
- TA appartenance-union (union-find)
- logarithme itéré, fonction d'Ackermann
-
- Notes 06 sur appartenance-union:
>
PDF.
Sedgewick, section 1.3.
Wikipedia:
union-find FR EN
| logarithme itéré EN
| fonction d'Ackermann FR EN
- 6. 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.
Sedgewick, sections 9.1-9.5.
Wikipedia:
file de priorité EN
| tas FR EN
Devoirs
- Devoir 1
à remettre le 25 janvier
- Énoncé
>
PDF.
- Devoir 2
à remettre le 8 février
- Énoncé
>
PDF.
- Devoir 3
(à venir)
- Devoir 4
(à venir)
Archives