Leçon #1234
Actif : false
Numero : 915
Titre : Classes de complexité. Exemples.2021
Créé le : 23/07/2026 12:42
Mis à jour : 23/07/2026 12:42
Rapport du jury 2015
Le jury attend que le candidat aborde à la fois la complexité en temps et en espace. Il faut naturellement exhiber des exemples de problèmes appartenant aux classes de complexité introduites, et montrer les relations d'inclusion existantes entre ces classes.Le jury s'attend à ce que le caractère strict ou non de ces inclusions soit abordé, en particulier le candidat doit être capable de montrer la non-appartenance de certains problèmes à certaines classes.Parler de décidabilité dans cette leçon serait hors sujet.
Le jury attend que le candidat aborde à la fois la complexité en temps et en espace. Il faut naturellement exhiber des exemples de problèmes appartenant aux classes de complexité introduites, et montrer les relations d'inclusion existantes entre ces classes.Le jury s'attend à ce que le caractère strict ou non de ces inclusions soit abordé, en particulier le candidat doit être capable de montrer la non-appartenance de certains problèmes à certaines classes.Parler de décidabilité dans cette leçon serait hors sujet.
Rapport du jury 2017
Le jury attend que le candidat aborde à la fois la complexité en temps et en espace. Il faut naturellement exhiber des exemples de problèmes appartenant aux classes de complexité introduites, et montrer les relations d’inclusion existantes entre ces classes, en abordant le caractère strict ou non de ces inclusions. Le jury s’attend à ce que les notions de réduction polynomiale, de problème complet pour une classe, de robustesse d’une classe vis à vis des modèles de calcul soient abordées. Parler de décidabilité dans cette leçon serait hors sujet.
Le jury attend que le candidat aborde à la fois la complexité en temps et en espace. Il faut naturellement exhiber des exemples de problèmes appartenant aux classes de complexité introduites, et montrer les relations d’inclusion existantes entre ces classes, en abordant le caractère strict ou non de ces inclusions. Le jury s’attend à ce que les notions de réduction polynomiale, de problème complet pour une classe, de robustesse d’une classe vis à vis des modèles de calcul soient abordées. Parler de décidabilité dans cette leçon serait hors sujet.
Rapport du jury 2019
Le jury attend que le candidat aborde à la fois la complexité en temps et en espace. Il faut naturellement exhiber des exemples de problèmes appartenant aux classes de complexité introduites, et montrer les relations d’inclusion existantes entre ces classes, en abordant le caractère strict ou non de ces inclusions. Le jury s’attend à ce que les notions de réduction polynomiale, de problème complet pour une classe, de robustesse d’une classe vis à vis des modèles de calcul soient abordées. $\\$ Se focaliser sur la décidabilité dans cette leçon serait hors sujet.
Le jury attend que le candidat aborde à la fois la complexité en temps et en espace. Il faut naturellement exhiber des exemples de problèmes appartenant aux classes de complexité introduites, et montrer les relations d’inclusion existantes entre ces classes, en abordant le caractère strict ou non de ces inclusions. Le jury s’attend à ce que les notions de réduction polynomiale, de problème complet pour une classe, de robustesse d’une classe vis à vis des modèles de calcul soient abordées. $\\$ Se focaliser sur la décidabilité dans cette leçon serait hors sujet.