Complexité
Aix-Marseille Université, Master 1 Informatique 2020–2021, Luminy
- Responsables de l’unité d’enseignement : Philippe Jégou, Antonio E. Porreca
- Chargés de TD : Nicolas Prcovic, Antonio E. Porreca, Raphaël Sturgis
- Chargés de TP : Nicolas Prcovic, Antonio E. Porreca, Raphaël Sturgis, François Hamonic
Page AMeTICE
Cours magistraux
- CM6 (15 octobre 2020) : Machines de Turing non déterministes, classe de complexité NP [diapositives]
- CM7 (22 octobre 2020) : Divinations et vérifications, réductions, complétude [diapositives]
- CM8 (5 novembre 2020) : Existence de problèmes NP-complets, techniques pour démontrer la NP-complétude, quelques réductions [diapositives]
- CM9 (12 novembre 2020) : Theorème de Cook-Levin [diapositives]
- CM10 (19 novembre 2020) : Super Plombiers Italiens est NP-complet, problèmes d’optimisation approximables et non approximables [diapositives]