S5 : Algorithmie avancée
Programme
En trois parties.
Modèles de calculs et classes de problèmes "utiles"
Semaine 1
- Rappels :
- écrire un algorithme avec un pseudo-code
- importance de la complexité polynomiale
- Réduction de problèmes
- Problèmes de NP
- Le problème SAT
Théorie des graphes
Semaine 2 à 5
Un outil de modélisation puissant pour résoudre (joliment) nombre de problèmes informatique.
Semaine 1
Cours 1
Semaine 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
- cliques et stables
Cours 2
- chemins cycles et connexité
- chemin
- composante connexe
- Parcours eulériens
- Parcours hamiltoniens
- applications :
- problème du postier chinois
- problème du digicode aussi appelé mots de Bruijin
Semaine 2
- version théorie des graphes des arbres
- Arbres couvrants
- Cayley et Prüfer
- Arbres planaires et chemins de Dyck
- Arbres de Catalan
- Arbres de Poyla et isomorphisme d'arbre
DM
L'ET de l'année dernière :
Semaine 3
TBD :
- Bi-parti
- coloriabilité
Semaine 4
TBD :
- couplage
- planarité
DS
TBD le faire.
Cryptographe
TBD en 2 semaines algo protocoles pgp et envois de message chiffrés
Bonus
TBD au choix :
- recherche universelle
- théorème de Cook-Levin
- graphes infinis
- méthode probabiliste ?
- ...
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