Toppfrågor
Tidslinje
Chatt
Perspektiv
Beslutsproblem
Från Wikipedia, den fria encyklopedin
Remove ads
Inom datavetenskapen, och särskilt komplexitetsteori är ett beslutsproblem ett beräkningsproblem som ska besvaras med ja eller nej.
 |
Den här artikeln behöver källhänvisningar för att kunna verifieras. (2019-10) Åtgärda genom att lägga till pålitliga källor (gärna som fotnoter). Uppgifter utan källhänvisning kan ifrågasättas och tas bort utan att det behöver diskuteras på diskussionssidan. |
Ett exempel på ett beslutsproblem är: kan man rita den här figuren utan att lyfta pennan? Detta problem kallas i matematiken för att hitta en Eulerstig. Märk att själva lösningen i ett beslutsproblem, i exemplet hur man ritar figuren, inte är intressant. Avsikten är att förenkla och formalisera beräkningsproblem så att man kan resonera om dem på ett matematiskt sätt. Har man väl en algoritm som löser ett beslutsproblem brukar det inte vara svårt att anpassa den till att plocka fram lösningen.
Remove ads
Se även
Wikiwand - on
Seamless Wikipedia browsing. On steroids.
Remove ads