Algoritmer kap 5 Flashcards
a) Definiera begreppet algoritm (algorithm)!
En algoritm är en ordnad mängd otvetydiga och exekverbara steg som definierar en process som
avslutas
b) 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 mycket korta listor och när data inte är sorterat eftersom
binärsökning kräver sorterad data.
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).
Ett program kan ge upphov till tre olika typer av fel: syntaktiska fel (syntactic errors), exekveringsfel
(runtime errors) och logiska fel (logic errors). Vilken typ av fel är mest allvarliga och varför?
Logiska fel, eftersom de inte ger upphov till något felmeddelande.
c) Vilket typ av fel är minst allvarliga och varför?
Syntaktiska fel, eftersom de upptäcks redan av kompilatorn.
Antag att vi har två algoritmer Algoritm1 och Algoritm2 för att utföra en beräkning, och vi har
följande exekveringstider (i någon tidsenhet) för dessa algoritmer för olika stora datamängder:
Data mängd: 8, 16, 32, 64
Algoritm1: 64, 256, 1024, 4096
Algoritm2: 8000, 16000, 32000, 64000
Vilken av dess algoritmer är effektivast att använda för större datamängder (> 10000)? Motivera ditt
svar!
Algoritm2, eftersom tiden för Algoritm1 växer kvadratiskt O(n2
) medan tiden för Algoritm2 växer linjärt
Definiera begreppet algoritm (algorithm)!
En algoritm är en ordnad mängd av otvetydiga, exekverbara steg som beskriver en avslutande process
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.
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.
c) Vilka två olika metoder används för att verifiera att ett program är korrekt (software verification)?
Statisk verifiering (static verification) eller kodanalys (code analysis), och testning (testing).
b) Ä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 det minsta antalet gånger som satserna i en loop-kropp (loop body) utförs i en iteration med
pre-test-villkor?
0 (noll).
Vad är pseudo-kod (pseudo code)?
Ett beskrivningssystem för algoritmer, och som är mindre formellt än riktiga programmeringsspråk (a
notational system in which algorithms can be expressed, and which is less formal than real programming
language code)
