Nous faisons actuellement face à d'importantes perturbations en raison de problèmes liés à l'infrastructure de stockage de l'Université, dont nous sommes tributaires. Bien que les enregistrements soient effectués correctement, leur publication subit des retards, et la lecture peut être instable.
Pour suivre l'évolution de la situation et obtenir plus d'informations, nous vous invitons à consulter la page de statut de nos services e-learning. https://elearning.unige.ch/statut-elearning/
Nous mettons tout en œuvre pour rétablir rapidement un fonctionnement normal. Nous vous remercions de votre compréhension.
Vous avez été redirigé.e vers la plateforme de secours. Si vous rencontrez encore des problèmes (bug, etc.), nous vous serions reconnaissants de les signaler à l'adresse suivante : mediaserver@unige.ch
Merci également d'indiquer que vous vous trouvez actuellement sur la plateforme de secours.
Cours 9 : Classe NP
Collection
Complexité et calculabilité / cours
Cours 2 : Rappels de langages formels
Cours 3 : Décidable, reconnaissable, simulation
Cours 4 : Diagonalisation et indécidabilité
Cours 5 : Théorème de Rice (et degrés de Turing)
Cours 6 : Introduction à la complexité algorithmique
Complexité et calculabilité / exercices (révision)
Cours 7 - Classes de complexité basiques
Cours 8 : Relations connues; non-déterminisme; théorème de Savitch
Cours 9 : Classe NP
Cours 10 : NP-complétude
Cours 11 et 12 : Exemples de réductions (11) et Théorème de Cook-Levin (12)
Séance d'exercices (A. Berger)