Chapter 12 - Beräkningsteori Flashcards
Ordna följande komplexitets-/effektivitetsklasser (complexity/efficiency classes) från denvmest effektiva till den minst effektiva:
Θ(n10), Θ(log n), Θ(n), Θ(2n).
Θ(log n), Θ(n), Θ(n10), Θ(2n)
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 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.
Ge exempel på tre komplexitetsklasser i O-notation och ordna dessa från mest effektiv till
minst effektiv!
Exempelvis: O(n), O(n2), O(2n).
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 innebär det att en funktion är beräkningsbar?
Att funktionen kan beräknas av någon algoritm.
