Complexité
Aix-Marseille Université, Master 1 Informatique 2021–2022, Luminy
- Responsables de l’unité d’enseignement : Philippe Jégou, Antonio E. Porreca
- Chargés de TD : Kévin Perrot, Pacôme Perrotin, Antonio E. Porreca
- Chargés de TP : Kévin Perrot, Pacôme Perrotin, Antonio E. Porreca, Raphaël Sturgis
Page AMeTICE
Cours magistraux
- CM5 (deuxième partie, 6 octobre 2021) : Machines de Turing non déterministes, classe de complexité NP, problème P vs NP [diapositives]
- CM6 (13 octobre 2021) : Divinations et vérifications, réductions, complétude [diapositives]
- CM7 (20 octobre 2021) : Existence de problèmes NP-complets, techniques pour démontrer la NP-complétude, quelques réductions [diapositives]
- CM8 (3 novembre 2021) : Theorème de Cook-Levin [diapositives]
- CM9 (10 novembre 2021) : Problèmes d’optimisation approximables et non approximables [diapositives]
Livre de complexité
Complexité algorithmique par Sylvain Perifel