IDSV Kap 5 Algorithms

Ge den formella definitionen av en algoritm.

An algorithm is an ordered set of unambiguous, executable steps that defines a terminating process.

Vad innebär ordered i algoritmdefinitionen?

Stegen har en bestämd ordning.

Vad innebär unambiguous?

Stegen är otvetydiga.

Vad innebär executable?

Stegen kan utföras.

Vad innebär terminating process?

Processen måste avslutas.

Vad är primitives?

En väldefinierad mängd building blocks som algorithm representations kan konstrueras från.

Vad är ett programming language i algoritmrepresentation?

En collection of primitives plus regler för hur primitives får kombineras.

Vad är pseudocode?

Ett notationssystem där algorithms kan uttryckas, mindre formellt än riktig programming language code.

Hur skrivs variable assignment i kursens pseudocode?

variable_name = expression.

Vilken konstruktion används för conditional selection?

if/else.

Vilken konstruktion används för repeated execution?

while.

Vad innebär working the problem backwards?

Att försöka lösa problemet bakifrån.

Vad innebär bottom-up methodology?

Att lösa pieces of the problem först.

Vad innebär top-down methodology?

Att dela problemet i mindre sub-problems.

Vad är ett annat namn för top-down methodology?

Stepwise refinement.

Vilka tre delar ingår i loop control?

Initialize, Test och Modify.

Vad gör Initialize?

Etablerar ett initial state.

Vad gör Test?

Kontrollerar om current state uppfyller loop condition.

Vad gör Modify?

Ändrar state i riktning mot termination state.

Vad är en pre-test loop?

En loop där condition testas före body.

Vilket exempel på pre-test loop används?

while.

Hur många gånger kan en pre-test loop minst köra body?

0 gånger.

Vad är en post-test loop?

En loop där body körs innan condition testas.

Hur många gånger körs body minst i en post-test loop?

1 gång.

x=0; while x<3: x=x+1. Vad blir x?

3.

x=5; while x<3: x=x+1. Hur många gånger körs body?

0 gånger.

Vad gör sequential search?

Söker efter target value genom att undersöka list entries i ordning.

När returnerar sequential search success?

När aktuell entry är lika med target value.

När returnerar sequential search failure?

När listan tar slut utan att target hittas.

Sök efter 9 i [4,7,2,9,5] med sequential search. Hur många comparisons?

4.

Sök efter 3 i [4,7,2,9,5] med sequential search. Hur många entries måste kontrolleras?

5.

Vilket viktigt krav har binary search?

Listan måste vara ordered/sorted.

Vad undersöker binary search först?

Middle entry.

Vad gör binary search om middle entry är större än target?

Söker i delen av listan före middle entry.

Vad gör binary search om middle entry är mindre än target?

Söker i delen efter middle entry.

Sorterad lista [2,4,6,8,10,12,14], target 12. Första middle är 8. Vilken del söks därefter?

[10,12,14].

Varför är binary search effektivare än sequential search på stora sorterade listor?

Binary search eliminerar en stor del av den återstående listan vid varje steg.

Vad är recursion?

När exekveringen av en procedure leder till en ny exekvering av samma procedure.

Vad händer med procedure activations vid recursion?

Flera activations skapas och alla utom en kan vänta på andra activations.

Hur mäts algorithm efficiency enligt materialet?

Som antalet instructions executed.

Vilka notationer används för efficiency classes?

Big Theta, Θ, och Big O.

Vilken efficiency class anges för insertion sort?

Θ(n²).

Vilken efficiency class anges för sequential search?

Θ(n).

Vilken efficiency class anges för binary search?

Θ(log n).

Vilka tre typer av case analysis anges?

Best, worst och average case.

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

log n → n → n².

Om n dubbleras, ungefär hur förändras n²?

Det blir fyra gånger så stort.

Vad är log2(1024)?

10.

Vad är static verification?

Code analysis.

Vad är formal verification?

Proof of correctness.

Vilken annan software verification-metod anges?

Testing.