Un problème de décision, c'est un problème dont la réponse est "oui" ou "non". Une classe de problèmes de décision, c'est un regroupement de problèmes selon un critère particulier. Par exemple, il y a la classe des problèmes de décision dont la réponse est toujours "oui" (pas très intéressante comme classe).
Lorsque le critère qui nous intéresse est la complexité des problèmes, on parle tout naturellement de "classes de complexité". On trouvera dans une même classe tous les problèmes de complexité similaire (voir plus loin).
Qu'est ce une taille d'instance?
Un problème, c'est une question et des données. La question est toujours la même, ce sont les données qui changent. On appelle un jeu de données particulier une "instance". Ce jeu de données a une taille, que l'on compte par exemple en bits nécessaires pour la représenter.
Par exemple, le problème suivant
Problème: le résultat de l'addition de A et B est-il supérieur à C ?
Données: trois entiers A, B et C
une instance de ce problème peut être (3, 1, 2), et la taille de cette instance est 3 fois le nombre de bits utilisés pour représenter un entier.
Q'est un temps polynomial par rapport à une taille d'instance?
On compte le temps que met un algorithme à s'exécuter en comptant le nombre d'opérations unitaires effectuées (en général, dans le pire des cas).
- Si mon algorithme effectue exactement K opérations, quelle que soit la taille de mes données, il est en temps constant
- Si j'ai des données de taille N et que mon algorithme doit effectuer K fois N opérations, il est en temps linéaire (en fonction de la taille des données).
- Si mon algorithme doit effectuer K puissance N opérations, il est en temps exponentiel (en fonction de la taille des données).
- etc.
En règle générale, si le nombre d'opérations effectuées par l'algorithme est un polynome qui dépend de la taille des données (a*N^K + b*N^(K-1)... + c*N + d), on dit qu'il est en temps polynomial. "P" est la classe des problèmes s'effectuant en temps (et espace) polynomial en fonction de la taille des données, voila voila.
[^] # Re: Enfin bon
Posté par Yusei (Mastodon) . En réponse au journal Les informaticiens précoces. Évalué à 2.
Un problème de décision, c'est un problème dont la réponse est "oui" ou "non". Une classe de problèmes de décision, c'est un regroupement de problèmes selon un critère particulier. Par exemple, il y a la classe des problèmes de décision dont la réponse est toujours "oui" (pas très intéressante comme classe).
Lorsque le critère qui nous intéresse est la complexité des problèmes, on parle tout naturellement de "classes de complexité". On trouvera dans une même classe tous les problèmes de complexité similaire (voir plus loin).
Un problème, c'est une question et des données. La question est toujours la même, ce sont les données qui changent. On appelle un jeu de données particulier une "instance". Ce jeu de données a une taille, que l'on compte par exemple en bits nécessaires pour la représenter.
Par exemple, le problème suivant
Problème: le résultat de l'addition de A et B est-il supérieur à C ?
Données: trois entiers A, B et C
une instance de ce problème peut être (3, 1, 2), et la taille de cette instance est 3 fois le nombre de bits utilisés pour représenter un entier.
On compte le temps que met un algorithme à s'exécuter en comptant le nombre d'opérations unitaires effectuées (en général, dans le pire des cas).
- Si mon algorithme effectue exactement K opérations, quelle que soit la taille de mes données, il est en temps constant
- Si j'ai des données de taille N et que mon algorithme doit effectuer K fois N opérations, il est en temps linéaire (en fonction de la taille des données).
- Si mon algorithme doit effectuer K puissance N opérations, il est en temps exponentiel (en fonction de la taille des données).
- etc.
En règle générale, si le nombre d'opérations effectuées par l'algorithme est un polynome qui dépend de la taille des données (a*N^K + b*N^(K-1)... + c*N + d), on dit qu'il est en temps polynomial. "P" est la classe des problèmes s'effectuant en temps (et espace) polynomial en fonction de la taille des données, voila voila.