Complexité
Aix-Marseille Université, Master 1 Informatique 2019–2020, Luminy
- Responsable de l’unité d’enseignement : Giuseppe Di Molfetta
- Chargés de CM : Giuseppe Di Molfetta, Antonio E. Porreca
- Chargés de TD et TP : Giuseppe Di Molfetta (Groupe 1), Antonio E. Porreca (Groupe 2), Nathanaël Eon (Groupe 3)
News ⚠️
- 28 novembre 2019 : J’ai publié le sujet de l’examen de l’année 2018–2019
- 21 novembre 2019 : J’ai publié les feuilles du TD10 et du TP3
- 20 novembre 2019 : J’ai publié les diapositives du CM10
- 19 novembre 2019 : J’ai publié la feuille du TD9
- 14 novembre 2019 : La semaine prochaine (jeudi 21 novembre) il y aura la séance de TP noté
- 13 novembre 2019 : J’ai publié les diapositives du CM9
- 8 novembre 2019 : J’ai publié les diapositives du CM8, la feuille du TD8 et la feuille du TP2
- 23 octobre 2019 : J’ai publié les diapositives du CM7, qui contiennent aussi une correction-de-la-correction de l’exercice 2.3 du contrôle continu (désolé pour l’erreur ! 😞)
Cours magistraux
- CM6 (16 octobre 2019) : Divinations et vérifications, réductions, complétude [diapositives]
- CM7 (23 octobre 2019) : Existence de problèmes NP-complets, techniques pour démontrer la NP-complétude, quelques réductions [diapositives]
- CM8 (5 novembre 2019) : Le théorème de Cook-Levin [diapositives]
- CM9 (13 novembre 2019) : Super Plombiers Italiens est NP-difficile, Théorème de Ladner [diapositives]
- CM10 (20 novembre 2019) : Problèmes d’optimisation approximables et non approximables [diapositives]
Travaux dirigés
- TD1 : Ordre de grandeur, codage, langage et problème [feuille]
- TD2 : Machines de Turing [feuille]
- TD3 : Le temps de calcul est une fonction de la taille des entrées [feuille]
- TD4 : Classes P et EXP [feuille]
- TD5 : The complexity cake [feuille]
- TD6 : Classes de complexité et non déterminisme [feuille]
- TD7 : Deviner, charactérisation existentielle de NP et réductions [feuille]
- TD8 : Réductions, NP-difficulté, NP-complétude [feuille]
- TD9 : Révisions [feuille]
- TD10 : Révisions (2) [feuille]
Travaux pratiques
Examens
- Examen terminal 2018-2019 [feuille]
Matériel