Thèmes d'exposés
1. L’origine de la complexité algorithmique et son importance
o Introduction historique
o Différence entre P, NP et NP-complet
o Applications concrètes
2. Les classes de complexité : P, NP, NP-complet et NP-difficile
o Définitions et exemples concrets
o Relations entre ces classes
o Impact en cryptographie et en optimisation
3. Le théorème de Cook-Levin : démonstration et implications
o Preuve intuitive de la NP-complétude
o Importance du problème SAT
o Applications dans d’autres problems
4. Le problème du voyageur de commerce (TSP) et ses approximations
o Définition et complexité
o Algorithmes gloutons et heuristiques (Branch and Bound, algorithme
génétique, etc.)
o Applications industrielles
5. La machine de Turing et ses variantes
o Définition formelle
o Exemple d’une machine de Turing pour des opérations simples
o Machine de Turing universelle et concept d’indécidabilité
6. Le problème du sac à dos : algorithmes exacts et approchés
o Formulation mathématique
o Programmation dynamique vs approche gloutonne
o Applications dans l’optimisation
7. L’indécidabilité en informatique : le problème de l’arrêt
o Explication intuitive du problème de l’arrêt
o Conséquences théoriques et pratiques
o Exemples de problèmes indécidables
8. Les algorithmes probabilistes et leur impact sur la complexité
o Classes BPP, RP, ZPP
o Exemples d’algorithmes probabilistes
o Utilisation en cryptographie
9. Les algorithmes quantiques et la classe de complexité BQP
o Différence entre calcul classique et quantique
o Algorithme de Shor et implications pour la cryptographie
o Défis et limites actuels
10. La réduction polynomiale et son rôle en théorie de la complexité
• Définition et exemples concrets
• Application pour prouver la NP-complétude
• Études de cas sur des problèmes réduits entre eux
