Kapitel 12 - instuderingsfrågor 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).
Θ(log n) < Θ(n) < Θ(n^10) < Θ(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: Θ(n^4), Θ(n), Θ(2^n), Θ(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²) och algoritm D är O(n log n²), lista algoritmerna i ordning från den mest effektiva till den minst effektiva!
B, A, D, C.
log n < n < n log n² < n²
Ge exempel på tre komplexitetsklasser i O-notation och ordna dessa från mest effektiv till minst effektiv!
Exempelvis: O(n), O(n2), 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). Inte möjligt teoretiskt till skillnad från traveling salesman-problemet (som är motsatsen, möjligt teoretiskt men inte praktiskt).
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.
