S5 : Algorithmie 3 (avancée)
Programme
En trois parties.
EN chantier.
Théorie des graphes
Semaine 1 à ...
Un outil de modélisation puissant pour résoudre (joliment) nombre de problèmes informatique.
Cours 1
- Graphes bases :
- rappel des définitions
- quelques propriétés sur les degrés, les chemins et les cycles
- Rappel : encodage d'un graphe
- chemins cycles et connexité
- chemin
- composante connexe
Pour la semaine prochaines, 2 exposés tiré du proofs from the book.
Cours 2
Un exposé du proof from the book
- Cycles eulérien
- Une conséquence inattendue : Mots de Bruijn
Coder les parcours eulérien et les mots de Bruijn.
Cours 3 et cours 4
Cours 3
TBD : graphes eulériens et conséquences.
Annales
-->Modalités de contrôle
Note
La note de cette UE résulte de cette formule :
$$ \max (\frac{DM+ DS + ET}{3}, ET) $$
Avec :
- $DM$ devoir(s) maison ou exposé(s)
- $DS$ la note du devoir surveillé
- $ET$ est l'examen terminal
Rendus
- un dm
- une présentation d'une jolie démonstration du proof from the book.
- un ds de théorie des graphes