ch 12 Flashcards
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)
Ordna följande komplexitets-/effektivitetsklasser (complexity/efficiency classes) från den
mest effektiva till den minst effektiva: Θ(n^10), Θ(log n), Θ(n), Θ(2^n)
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), Θ(n^4), Θ(2^n)
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 skiljer en deterministisk algoritm från en icke-deterministisk?
En deterministisk algoritm ger alltid samma svar givet ett visst indata. En icke-deterministisk algoritm kan ge olika svar för samma indata
Givet att komplexiteten för algoritm A är O(n), algoritm B är O(log n), algoritm C är O(n^2) och algoritm D är O(n log n^2), lista algoritmerna i ordning från den mest effektiva till den minst effektiva!
B, A, D, C
Ge exempel på tre komplexitetsklasser i O-notation och ordna dessa från mest effektiv till minst effektiv!
Exempelvis: O(n), O(n^2), O(2^n)
Varför är stopp-problemet (the halting problem) intressant ur ett beräkningsteoretiskt perspektiv?
Stopproblemet är olösbart, vilket visar att det finns problem som inte går att lösa med algoritmer/program
Ge ett exempel på en icke-beräkningsbar funktion?
Stopp-problemet
Vad kännetecknar stopp-problemet (inom beräkningsteori)
Att det inte är beräkningsbart (algoritmiskt lösbart)
Vad är syftet med Turing-maskiner?
Det är ett verktyg för att studera datorers beräkningsförmåga (algoritmisk bearbetning)
Vad kallas den maskin som utgör den enklast tänkbara modellen av en dator?
Turing-maskin
Vad innebär det att en funktion är beräkningsbar?
Att funktionen kan beräknas av någon algoritm
