IDSV Kap 12 Theory of Computation

Vad är en function?

Varje possible input value maps to a single output value.

Vad är en computable function?

En function som kan computed by some algorithm.

Vad är en non-computable function?

En function som inte kan computed by any algorithm.

Vad används en Turing machine till?

Att studera the power of computing, alltså algorithmic processing.

Vilka centrala components har en Turing machine?

Control unit, infinite tape och read/write head.

Vad innehåller control unit?

State och actions.

Hur lång är en Turing machine tape i den teoretiska modellen?

Infinite.

Vilka två inputs avgör en Turing machine operation?

Current state och value at current tape position.

Vilka tre actions kan en Turing machine utföra?

Write a value, move read/write head left or right och change state.

Hur långt flyttas read/write head i en action enligt materialet?

Ett steg left eller right.

Kan Turing machine ändra till samma state som den redan är i?

Ja.

En Turing machine-regel säger "write 1, move right, change to state B". Vilka tre typer av actions sker?

Write, move och change state.

Vad säger Church-Turing thesis enligt materialet?

Turing-computable functions är equivalent to computable functions.

Vad betyder self-terminating i kursens halting-problem-framställning?

Program execution terminates när programmet startas med sig självt som input.

Vad är halting problem enligt kursens formulering?

Givet encoded version av ett program, returnera 1 om programmet är self-terminating och 0 annars.

Är halting problem generellt lösbart?

Nej.

Vad visar halting problem om computation?

Att det finns problem/funktioner som inte kan lösas/beräknas av någon generell algorithm.

Vad är ett polynomial problem?

Ett problem där det finns en algorithmic solution inom complexity class O(n^x) för något x.

Vad är ett non-polynomial problem enligt materialet?

Ett problem där det inte finns någon algorithmic solution inom O(n^x) för något x.

Är O(n) polynomial?

Ja.

Är O(n²) polynomial?

Ja.

Är O(n^10) polynomial?

Ja.

Är O(2^n) polynomial?

Nej.

Hur beskriver materialet polynomial problems praktiskt?

Practically solvable och theoretically solvable.

Hur beskriver materialet non-polynomial problems praktiskt?

Practically unsolvable men theoretically solvable.

Vilken växer snabbare asymptotiskt, n^10 eller 2^n?

2^n.

Ordna log n, n, n² och 2^n från långsammast till snabbast tillväxt.

log n → n → n² → 2^n.

Vad är en non-deterministic algorithm enligt materialet?

En "algorithm" vars steps inte behöver vara uniquely and completely determined by process state.

Vad är ett non-deterministic polynomial problem?

Ett problem med en non-deterministic algorithmic solution inom O(n^x) för något x.

Vilket exempel på non-deterministic polynomial problem anges?

Traveling salesman problem.

Vad är Traveling Salesman Problem enligt materialets korta beskrivning?

Find the best way to visit a number of cities.

Vad står P för i materialets problem classification?

Class of polynomial problems.

Vad står NP för enligt materialets framställning?

Class of non-deterministic polynomial problems.

Vet man enligt materialet om NP är större än P?

Nej, det är currently not known.

Vilken complexity anges för insertion sort?

Θ(n²).

Vilken complexity anges för sequential search?

Θ(n).

Vilken complexity anges för binary search?

Θ(log n).

Vilken är asymptotiskt effektivare, Θ(log n) eller Θ(n)?

Θ(log n).

Vilken är asymptotiskt effektivare, Θ(n) eller Θ(n²)?

Θ(n).