Problema de decisió
En teoria de la computació, un problema és un conjunt de frases de llongitut finita que tenen associades frases resultants també de llongitut finita. Un problema de decisió és un problema en a on les respostes possibles són «sí» o «no».
Un problema de decisió també es pot formalisar com el problema de decidir si una certa frase pertany a un conjunt donat de frases, també cridat llenguage formal. El conjunt conté exactament les frases per a les quals la resposta a la pregunta és positiva.
Concepte intuïtiu
[editar | editar còdic]S'usa el terme «problema» per a designar a tota una classe de preguntes que tenen una estructura similar i la resposta de la qual depén de certs paràmetros d'entrada. Una instància és un cas particular que s'obté d'un problema en assignar valors concrets als paràmetros d'entrada. Per tant una instància té una resposta específica: «sí» o «no».
Un eixemple típic de problema de decisió és la pregunta: ¿És un número sancer donat primer? Una instància d'este problema seria: ¿És 17 cosí?
La pregunta anterior sobre els número primo es pot vore també com el llenguage de totes les frases en l'alfabet {0, 1,..., 9} tals que el sancer corresponent és primer.
Problema decidible
[editar | editar còdic]Si existix un algoritme que puga decidir per a cada possible frase d'entrada si eixa frase pertany al llenguage, llavors es diu que el problema és decidible, d'una atra forma es diu que és un problema indecidible. Quan existix un algoritme que pot respondre positivament quan la frase està en el llenguage, pero que corre indefinidament quan la frase no pertany al llenguage es diu que el problema és parcialment decidible. En teoria de la computabilidad, s'estudia qué llenguages són decidibles en diferents tipos de màquines. En teoria de la complexitat computacional s'estudia quànts recursos necessita un algoritme decidible per a eixecutar (recursos de temps, espai, número de processadors, tipo de màquina, etc.).
Vore també
[editar | editar còdic]Referències
[editar | editar còdic]- (DecisionProblem) Definició en MathWorld.
- Este artícul conté una traducció derivada de «Problema de decisión» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.