Exercices corrigés — Décidabilité et classes de complexité (informatique (MP2I/MPI))
15 exercices avec corrigé rédigé, du plus simple au plus exigeant.
- Le test de primalité naïf est-il polynomial ? Exercice de TD
- Le certificat vide Exercice de TD
- Du seuil à l'optimum Exercice de TD
- Lire une réduction dans le bon sens Exercice de TD
- Deux problèmes, une réduction d'une ligne Exercice de TD
- L'arrêt sur l'entrée vide Exercice de TD
- Problème — Une réduction depuis SAT Exercice de TD
- Un certificat pour la réponse « non » ? Application directe du cours
- Le sac à dos, et le mot « pseudo » Application directe du cours
- Écrire un vérificateur Application directe du cours
- « Il suffit de l'exécuter » Application directe du cours
- Problème — SAT : vérifier est facile, chercher ne l'est pas Application directe du cours
- Problème — -SAT est linéaire Application directe du cours
- Problème — Le problème de l'arrêt : ce qu'il interdit vraiment Application directe du cours
- Problème — Du seuil à l'approximation garantie : la couverture par sommets Application directe du cours