IDSV - Chapter 5 - Algorithms

Question 1

Vad är en algoritm?

Answer 1

En algoritm är en uppsättning av steg som beskriver hur en uppgift ska göras

Question 2

Vilka fyra krav måste en algoritm uppfylla?

Answer 2

• Ordning
• Exekverbara steg
• Otvetydighet
• Terminering

Question 3

Vad innebär ‘Ordning’ i en algoritm?

Answer 3

Stegen ska ha en bestämd struktur och utföras i en specifik ordning

Question 4

Vad betyder ‘Exekverbara steg’?

Answer 4

Varje steg måste gå att utföra, exempelvis kan inte ett steg vara omöjligt

Question 5

Vad innebär ‘Otvetydighet’ i en algoritm?

Answer 5

Stegen ska vara tydliga och inte öppna för tolkning

Question 6

Vad är ‘terminering’ i samband med algoritmer?

Answer 6

Algoritmen måste leda till ett slutresultat

Question 7

Vad är skillnaden mellan algoritm, program och process?

Answer 7

• Algoritm = Idén
• Program = Algoritmen skriven i kod
• Process = När programmet körs

Question 8

Vad är ‘primitiver’ i datavetenskap?

Answer 8

De minsta byggstenarna för att beskriva algoritmer

Question 9

Vad är pseudokod?

Answer 9

En enkel och lättläst beskrivning av en algoritm som liknar riktig kod

Question 10

Ge ett exempel på en pseudokodstruktur

Answer 10

• Tilldelning
• Villkor (if/else)
• Loopar (while)
• Funktioner

Question 11

Vad är syftet med pseudokod?

Answer 11

Att förklara algoritmer utan att blanda in syntaxfel

Question 12

Vad är en flödesschema?

Answer 12

Ett diagram med symboler som visualiserar processen i en algoritm

Question 13

Vad är en rekursiv struktur?

Answer 13

En funktion som anropar sig själv för att lösa en del av problemet

Question 14

Vad är binär sökning?

Answer 14

En rekursiv metod för att söka i en sorterad lista genom att halvera listan

Question 15

Vad är viktigt att ha i åtanke vid rekursion?

Answer 15

Termineringsvillkor (base case) för att undvika oändlig rekursion

Question 16

Vad beskriver algoritmeffektivitet?

Answer 16

Hur snabbt en algoritm arbetar

Question 17

Vad är skillnaden mellan sekventiell och binär sökning?

Answer 17

Sekventiell sökning kontrollerar varje element; binär sökning halverar listan

Question 18

Vad är big-theta notation?

Answer 18

En notation som beskriver algoritmers växt

Question 19

Vad är preconditions i programverifiering?

Answer 19

Villkor som måste vara sanna innan programmet startar

Question 20

Vad betyder postconditions?

Answer 20

Villkor som ska vara sanna efter programmet körts

Question 21

Vad är en loop invariant?

Answer 21

Ett påstående som alltid är sant vid varje iteration av en loop

Question 22

Rekursion kan användas för att göra vad?

Answer 22

Att lösa problem genom att dela upp dem i mindre delar

Question 23

Vad är en vanlig strategi för problemlösning?

Answer 23

• Arbeta baklänges
• Dela upp problemet
• Hitta liknande problem

Question 24

Vad innebär ‘effektivitet’ i algoritmer?

Answer 24

Algoritmer kan vara snabba eller långsamma beroende på strategi

Question 25

Vad är viktigt för korrekthet i program?

Answer 25

Att bevisa att programmet alltid gör rätt, inte bara testa det