📈

Classes de Complexité

Chapitre 6 • Machines de Turing, Temps, Espace & Classes P/NP

Statut : En cours
Chapitre 6

Classes de Complexité

Complexité en temps et en espace, domination asymptotique, classes DTime/NTime, P, NP et thèse de l'invariance.

Quel est le titre exact du chapitre 6 ?

#1/30

Quels sont les deux types de problèmes identifiés dans les chapitres précédents ?

#2/30

Quel problème est cité comme exemple de problème n'ayant pas de solution algorithmique ?

#3/30

Grâce à quelle thèse détermine-t-on si un problème possède une machine de Turing pour le résoudre ?

#4/30

Quelle condition est imposée sur les fonctions f sur les entiers dans ce chapitre ?

#5/30

Quelles sont les deux fonctions de complexité associées à une machine de Turing ?

#6/30

Dans le cas d'une machine déterministe, que représente ct(w) ?

#7/30

Dans le cas d'une machine déterministe, que représente ce(w) ?

#8/30

Pour une machine non-déterministe, comment définit-on ct(w) ?

#9/30

Pour une machine non-déterministe, comment définit-on ce(w) ?

#10/30

Comment définit-on la taille d'une donnée w, notée |w| ?

#11/30

Comment est défini Ct(n) à partir de ct(w) ?

#12/30

Comment est défini Ce(n) à partir de ce(w) ?

#13/30

À quelles fonctions usuelles cherche-t-on à associer Ct(n) et Ce(n) grâce à la domination asymptotique ?

#14/30

Comment se définit mathématiquement la domination asymptotique f = O(g) ?

#15/30

Quel exemple de domination avec un polynôme est donné dans le cours ?

#16/30

Quel exemple de domination avec un logarithme est donné dans le cours ?

#17/30

Pourquoi s'intéresse-t-on uniquement aux grandes valeurs de n ?

#18/30

Qu'est-ce que la classe DTime(f) ?

#19/30

Qu'est-ce que la classe DSpace(f) ?

#20/30

Qu'est-ce que la classe NTime(f) ?

#21/30

Qu'est-ce que la classe NSpace(f) ?

#22/30

Quelle est la propriété liant DTime, NTime et DTime exponentiel dans le cours ?

#23/30

Comment est définie la classe P ?

#24/30

Comment est définie la classe NP ?

#25/30

Par convention, comment appelle-t-on les problèmes qui appartiennent à la classe P ?

#26/30

Comment qualifie-t-on les problèmes de la classe P du point de vue de leur applicabilité ?

#27/30

Quel est l'impact de la traduction d'un programme en une machine de Turing déterministe sur le temps ?

#28/30

Quel est l'impact de cette même traduction en termes d'espace selon la thèse de l'invariance ?

#29/30

Quelle est la conséquence majeure de la thèse de l'invariance sur la classe P ?

#30/30