Complexité
Aix-Marseille Université, Master 1 Informatique 2022–2023, Luminy
- Responsables de l’unité d’enseignement : Philippe Jégou, Antonio E. Porreca
- Chargés de TD : Nathan Lhote, Kévin Perrot, Antonio E. Porreca
- Chargés de TP : Sami Cherif, Nathan Lhote, Kévin Perrot, Antonio E. Porreca
Page AMeTICE
Cours magistraux
- CM5 (deuxième partie, 5 octobre 2022) : Machines de Turing non déterministes, classe de complexité NP [diapositives]
- CM6 (12 octobre 2022) : Algorithmes nondéterministes, divinations et vérifications [diapositives]
- CM7 (19 octobre 2022) : Réductions, complétude, existence de problèmes NP-complets, techniques pour démontrer la NP-complétude [diapositives]
- CM8 (2 novembre 2022) : Quelques réductions [diapositives]
- CM9 (9 novembre 2022) : Théorème de Cook-Levin [diapositives]
Livre de complexité
Complexité algorithmique par Sylvain Perifel