Beräkningsteori kap 12 Flashcards
Vad skiljer en deterministisk algoritm från en icke-deterministisk?
En deterministisk algoritm utförs alltid på samma sätt och ger alltid samma svar givet samma indata. En
icke-deterministisk algoritm kan utföras på olika sätt, även med samma indata, och kan därför också ge
olika svar.
Vad är en Turing-maskin och vad är dess syfte?
En Turing-maskin är en matematisk modell av en dator, och syftet är att studera vilka problem som går
att lösa med en dator
Vad är stopp-problemet (the halting problem), och varför är det intressant ur ett beräkningsteoretiskt
perspektiv?
Stopp-problemet: Är det möjligt att inom ändlig tidsrymd med något program avgöra om ett godtyckligt
program kommer att avslutas för godtyckliga indata? Stopp-problemet är olösbart, vilket visar att det
finns problem som inte går att lösa med algoritmer.
Vad innebär det att ett problem är ett polynomiellt problem (polynomial problem) (tillhör klassen
polynomiella problem)?
Att det finns en algoritm för att lösa problemet inom komplexitetsklass O(nx
) för något x.
Är klassen av polynomiella problem P mindre eller lika med klassen av icke-deterministiskt
polynomiella problem NP? Motivera ditt svar!
Det är ett öppet problem. Ingen har lyckats visa vare sig att P är mindre än NP, eller att P är lika med NP
Vad är en Turing-maskin och vad är dess syfte?
En Turing-maskin är en matematisk modell av en dator, och syftet är att studera vilka problem som går
att lösa med en dator.
Ordna följande komplexitets-/effektivitetsklasser (complexity/efficiency classes) från den mest
effektiva till den minst effektiva: Θ(n4
), Θ(n), Θ(2n
), Θ(log n).
Θ(log n), Θ(n), Θ(n4
), Θ(2n
).
Vad är stopp-problemet (the halting problem), och varför är det intressant ur ett beräkningsteoretiskt
perspektiv?
Alternativ 1 (stopp-problemet): Är det möjligt att inom ändlig tidsrymd med något program avgöra om
ett godtyckligt program kommer att avslutas för godtyckliga indata?
Alternativ 2 (stopp-problemet): Given the encoded version of any program, return 1 if the program is
self-terminating, or 0 if it is not.
Stopp-problemet är olösbart, vilket visar att det finns problem som inte går att lösa med algoritmer.
Ordna följande komplexitets-/effektivitetsklasser (complexity/efficiency classes) från den mest
effektiva till den minst effektiva: Θ(n10), Θ(log n), Θ(n), Θ(2n
).
Θ(log n), Θ(n), Θ(n10), Θ(2n
)
Vad är stopp-problemet (the halting problem), och varför är det intressant ur ett beräkningsteoretiskt
perspektiv?
Stopp-problemet: Är det möjligt att inom ändlig tidsrymd med något program avgöra om ett godtyckligt
program kommer att avslutas för godtyckliga indata? Stopp-problemet är olösbart, vilket visar att det
finns problem som inte går att lösa (med algoritmer).
