Chapter 5 - Algoritmer Flashcards
Definiera begreppet algoritm (algorithm)!
En ordnad mängd otvetydiga(tydliga) utförbara steg som definierar en avslutande process.
Vad är rekursion?
En funktionsom anropar sig själv, vilket innebär repetition.
Varför är binär sökning bättre än sekvensiell sökning på sorterad data?
Därför att med binärsökning så växer antalet steg i sökprocessen logaritmiskt med antalet poster, medan med sekvensiell sökning så växer antalet steg linjärt med antalet poster, vilket innebär att binärsökning är betydligt effektivare.
Vad är det minsta antalet gånger som satserna i en loop-kropp (loop body) utförs i en iteration med post-test- villkor? Ange svaret som ett heltal.
1
Vad är det minsta antalet gånger som satserna i en loop-kropp (loop body) utförs i en iteration med pre-test-villkor?
0
Är det någon skillnad mellan iteration och rekursion när det gäller användningen av minne?
Ja, varje rekursivt anrop i en rekursion kräver extra minne, till skillnad från en iteration där varje varv inte kräver något extra minne.
Vad är pseudo-kod (pseudo code)?
Ett beskrivningssystem för algoritmer, och som är mindre formellt än riktiga programmeringsspråk
Kan alla algoritmer beskrivas som ett flödes-schema (flow chart)? Motivera ditt svar!
Ja, rektanglar och romber beskriver exekverbara steg, varav romber beskriver villkor, och pilar beskriver sekvenser och loopar, vilket är vad som behövs för att beskriva varje tänkbar algoritm.
Är ett programmeringsspråk, t.ex. Python, lämpligt för att beskriva algoritmer? Motivera ditt svar!
Ja, för att programmeringsspråk har väldefinierade primitiv och regler för hur primitiven kan kombineras. (Nej, för att programmeringsspråk kräver att man specificerar många detaljer.)
Vad är ett program i förhållande till en algoritm?
Ett program är en algoritm kodad i ett programmeringsspråk, d.v.s. på ett sådant sätt att en dator kan exekvera den.
Beskriv hur binärsökning går till! Vilka krav finns på den data som man söker i?
Binärsökning kräver att den data man söker i är sorterad. Vid varje repetition i sökningen halveras antalet poster. Sökningen avslutas när posten antingen hittats eller den kvarvarande halvan är tom.
Vilka metoder kan användas för att verifiera ett programs korrekthet?
Statisk verifiering (static verification) eller kodanalys (code analysis), och testning (testing)
På vilka två grundläggande olika sätt kan man åstadkomma repetition i en algoritm?
Rekursion och iteration
När är sekventiell sökning att föredra framför binärsökning?
Sekventiell sökning är att föredra för mkt korta listor och när data inte är sorterat eftersom binärsökning kräver sorterad data.
Vad är en förutsättning för att binärsökning (binary search) ska fungera? Motivera ditt svar.
Sorterad data. Sorted/ordered data.
