ch 5 Flashcards
Definiera begreppet algoritm (algorithm)!
En ordnad mängd OTVETYDLIGA(tydliga) utförbara steg som definierar en avslutande process
Vad är rekursion?
En funktion som 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
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
Är det någon skillnad mellan iteration och rekursion när det gäller användningen av minne?
Varje rekursivt anrop i en rekursion kräver extra minne,
Iteration där varje varv inte kräver något extra minne
Vad är pseudo-kod (pseudo code)?
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!
Alla rektanglar och romber beskriver exekverbara steg,
Romber beskriver villkor
Pilar beskriver sekvenser och loopar
vilket är vad som behövs för att beskriva varje tänkbar algoritm
(romber = vilkor
pilar = sekvenser & loopar)
Är ett programmeringsspråk, t.ex. Python, lämpligt för att beskriva algoritmer? Motivera ditt svar!
Programmeringsspråk har väldefinierade primitiv och regler för hur primitiven kan kombineras.
Nackdel för att programmeringsspråk kräver att man specificerar många detaljer
(både ja & nej)
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
Vad är skillnaden mellan en algoritm och ett program?
Algoritmen inte är skriven i ett specifikt programspråk utan istället bara beskriver tillvägagångssättet.
Samma algoritm kan realiseras i olika programspråk och i olika program
Vilka två olika metoder används för att verifiera att ett program är korrekt (software verification)?
Statisk verifiering (static verification) /kodanalys (code analysis)
Testning (testing).
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. För varje repetition så undersök posten i mittenpositionen:
Om posten som eftersöks ordnas före posten i mittenpositionen så fortsätt sökningen i första halvan;
Om posten som eftersöks ordnas efter posten i mittenpositionen så fortsätt sökningen i andra halvan.
Fortsätt på liknande sätt och avsluta sökningen 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
Iteration
