S5 : Algorithmie avancée

Programme

En trois/quatre parties.

TBD année prochaine faire préparer le cours avant et au tableau aller plus loin ?

Modèles de calculs et classes de problèmes "utiles"

1. Problèmes NP
   1. classes utiles
   2. réduction
   3. NPC
2. algorithmie et logique
   1. fonctions booléennes
   2. SAT, 3-SAT et 2-SAT
   3. Théorème de Levin-Cook
3. Modèle de calcul
   1. (pseudo-)assembleur
   2. architecture de Von Neumann
   3. Machine de Turing
4. problèmes NP complets du sac à dos :
   1. fractionnel
   2. énumération (juste donner le principe)
   3. programmation dynamique

Théorie des graphes

TBD

Peut-être

• Langage C
• Réseaux
• Cryptographie
• Graphes et réseaux (sociaux)

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

• deux dm de code
• une présentation d'une jolie démonstration du proof from the book.
• un ds de théorie des graphes/informatique théorique