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
DM
L'ET de l'année dernière :
À rendre sur papier pour le 10 octobre 2025.
Semaine 3
Semaine 4
- rappel sur les flots
- couplage :
- problème et chemins augmentant
- graphes bi-parti et idée de la généralisation aux graphes quelconques.
- couplage max dans les graphes bi-partis (si on a le temps)
- colorabilité des sommets d'un graphe
- graphes planaires
DS
Cryptographie
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 ?
- ...
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