Cours 11 et 12 : Exemples de réductions (11) et Théorème de Cook-Levin (12)
mardi 14 mai 2024 / 16:15 - 18:00 @ Battelle - D185
- Centre universitaire d'informatique CUI - Directement rattaché au CUI
-
Ce fichier sera en ligne jusqu'au jeudi 20 février 2025
Complexité et calculabilité / cours
1Cours 2 : Rappels de langages formels
2Cours 3 : Décidable, reconnaissable, simulation
3Cours 4 : Diagonalisation et indécidabilité
4Cours 5 : Théorème de Rice (et degrés de Turing)
5Cours 6 : Introduction à la complexité algorithmique
6Complexité et calculabilité / exercices (révision)
7Cours 7 - Classes de complexité basiques
8Cours 8 : Relations connues; non-déterminisme; théorème de Savitch
9Cours 9 : Classe NP
10Cours 10 : NP-complétude
11Cours 11 et 12 : Exemples de réductions (11) et Théorème de Cook-Levin (12) 
12Séance d'exercices (A. Berger)
13Séance d'exercices (A. Berger)
1Cours 2 : Rappels de langages formels01:44:59
2Cours 3 : Décidable, reconnaissable, simulation01:44:59
3Cours 4 : Diagonalisation et indécidabilité01:44:59
4Cours 5 : Théorème de Rice (et degrés de Turing)01:44:59
5Cours 6 : Introduction à la complexité algorithmique01:44:59
6Complexité et calculabilité / exercices (révision)01:44:59
7Cours 7 - Classes de complexité basiques01:44:59
8Cours 8 : Relations connues; non-déterminisme; théorème de Savitch01:44:59
9Cours 9 : Classe NP01:44:59
10Cours 10 : NP-complétude01:44:59
11Cours 11 et 12 : Exemples de réductions (11) et Théorème de Cook-Levin (12) 01:44:59
12Séance d'exercices (A. Berger)01:44:59
13Séance d'exercices (A. Berger)01:44:59