Kapitel 5 - instuderingsfrågor Flashcards
Definiera begreppet algoritm (algorithm)!
En algoritm är en ordnad mängd av otvetydiga, exekverbara steg som beskriver en avslutande process.
Vad är rekursion?
Rekursion är en repetition vars funktion kan anropa sig själv.
Varför är binär sökning bättre än sekvensiell sökning på sorterat data?
Därför att med binärsökning så växer antalet steg i sökprocessen logaritmiskt med antalet poster, medan med sekventiell 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?
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)?
Pseudo-kod är kod som inte skrivits enligt reglerna för ett specifikt programmeringsspråk utan för en annan människa. 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, alla programmeringsspråk är grundade på algoritmer. De är uppbyggda på primitives och regler. Men kräver att man specificerar många detaljer.
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?
Ett program är en algoritm kodad på ett sådant sätt att en dator kan exekvera den.
Vilka två olika metoder används för att verifiera att ett program är korrekt (software verification)?
Statisk verifiering eller kodanalys och testing.
Beskriv hur binärsökning går till! Vilka krav finns på den data som man söker i?
En förutsättning som ska finnas för att binärsökning ska fungera är att listan ska vara sorterad. Utan en sorterad lista kan binär sökningen inte tillämpas på korrekt vis.
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.
På vilka två grundläggande olika sätt kan man åstadkomma repetition i en algoritm?
Iteration och rekursion
När är sekventiell sökning att föredra framför binärsökning?
När det är korta listar, eller datan inte är sorterad (eftersom binärsökning kräver en sorterad lista)
Är binärsökning ett bra val för att söka i osorterad data? Motivera ditt svar.
Nej, det fungerar inte.
