Algoritmer och programmering

{{ 'ml-heading-theory' | message }}

Datorer idag är väldigt kraftfulla och har en enorm bredd av användningsområden, men för att kunna utnyttja den här kraften måste datorn först förstå vad den ska göra. Det går inte att bara säga åt den att lösa ett problem, utan man måste ge tydliga instruktioner som förklarar hur den ska göra. Att formulera sådana instruktioner är att programmera.

Intro algoritmer 1 p.svg
Innan man börjar skriva program är det dock viktigt att komma in i rätt sätt att tänka. Datorer är ganska petiga när det gäller instruktioner, och små fel eller otydligheter kan få programmet att göra helt fel eller kanske inget alls. På den här sidan kommer du därför att få träna på att skriva algoritmer, alltså instruktioner för att lösa ett problem eller utföra en uppgift.
Begrepp

Algoritm

Inom matematik och programmering är en algoritm en serie instruktioner för att uppnå något. I skolan får man t.ex. lära sig en algoritm för addition genom uppställning, och senare pqpq-formeln som är en algoritm för att lösa andragradsekvationer. Algoritmer kan liknas vid recept, där tydliga steg måste utföras i en viss ordning för att det ska bli rätt. Ta t.ex. ett recept på havregrynsgröt.

Blanda 1 dl havregryn med 2 dl vatten och 1 krm salt i en kastrull.
Koka upp blandningen och låt sjuda tills gröten är tillräckligt tjock.

Recept behöver inte vara mer detaljerade än så, men en algoritm är ofta väldigt specifik. Receptet skulle kunna göras mer som en algoritm genom att dela upp stegen så här.

Ställ fram en kastrull.
Häll 2 dl vatten i kastrullen.
Häll 1 dl havregryn i kastrullen.
Häll 1 krm salt i kastrullen.
Blanda innehållet i kastrullen.
Ställ kastrullen på en spis.
Sätt spisens temperatur på medelhög värme.
Vänta tills blandningen kokar.
Sänk temperaturen till låg värme.
Rör om tills gröten når önskad konsistens.
Man kan förfina algoritmen ytterligare genom att dela upp instruktionerna igen. I det här fallet kan det kännas lite onödigt men inom matematik och programmering är det viktigt att alla instruktioner är detaljerade och entydiga.
Uppgift

Skriv en algoritm som beskriver hur man beräknar arean av en kvadrat om man känner till dess omkrets.

Visa lösning Visa lösning
Begrepp

Verktyg för algoritmer

När man skriver algoritmer måste man ibland ta en mer komplicerad väg genom instruktionerna än att bara gå igenom dem steg för steg. Det kan t.ex. vara så att vissa instruktioner bara ska göras ibland eller att vissa ska upprepas.

Begrepp

Upprepning

Om en algoritm innehåller något som ska göras flera gånger kan man markera upprepningen i instruktionerna istället för att skriva samma sak gång på gång. Ibland kanske man inte ens vet hur många gånger stegen ska upprepas när algoritmen skrivs. Om man t.ex. ska skriva en algoritm för att skala morötter kan man använda något i stil med följande.

Ta fram morötter.
Upprepa för varje morot:
	Skölj av moroten.
	Skär av blasten.
	Skala moroten.

Här ska de indragna instruktionerna, dvs. de som står längre in på raderna, göras för varje morot. Har man t.ex. 1010 morötter kommer alltså rad 33 till 55 upprepas 1010 gånger.

Begrepp

Villkor

Om en algoritm innehåller steg som bara ska göras under vissa omständigheter kan man införa ett villkor. Om man ska ut och cykla behöver man förmodligen inte pumpa däcken varje gång, så en algoritm för förberedelserna skulle kunna se ut på följande sätt.

Ta fram cykeln.
Om det är dåligt med luft i däcken:
	Pumpa däcken.
Sätt dig på cykeln och åk.
Här gör man ett val i rad 22 baserat på hur mycket luft det finns i däcken. Är det för lite luft går man till rad 33 och pumpar dem, annars går man direkt till rad 4.4.
Uppgift

Följande algoritm tar ett tal och gör en beräkning baserat på det.

Multiplicera talet med 3.
Subtrahera 12 från resultatet.
Om resultatet är jämnt: Dividera resultatet med 2.
Upphöj resultatet till 2.

Vad får man om man använder algoritmen på talet 7?7?

Visa lösning Visa lösning

Uppgifter

Nivå 1
1.1
{{ 'ml-btn-focusmode-tooltip' | message }} settings_overscan

Använd följande algoritm på talet 6.6.

Addera 2 till talet.
Upprepa följande instruktioner 5 gånger:
	Subtrahera 1 från resultatet.
	Dubblera resultatet.
Subtrahera 2 från resultatet.

Vad blir resultatet?

1.2
{{ 'ml-btn-focusmode-tooltip' | message }} settings_overscan

Vilmer anser att hans tandborstning har blivit lite ostrukturerad så han bestämmer sig för att skriva en algoritm som förtydligar hur man gör. Hjälp honom skriva en algoritm som beskriver hur man borstar tänderna.

1.3
{{ 'ml-btn-focusmode-tooltip' | message }} settings_overscan

Skriv en algoritm som beräknar variationsbredden av en datamängd.

1.4
{{ 'ml-btn-focusmode-tooltip' | message }} settings_overscan

En algoritm för att "översätta" ett ord till rövarspråket ser ut så här. Anta att det nya ordet skrivs under ordet som översätts.

Upprepa för varje bokstav i ordet:
	Om bokstaven är en vokal:
		Lägg till bokstaven i det nya ordet.
	Om bokstaven är en konsonant:
		Skriv bokstaven två gånger, med en lucka mellan dem.
		Skriv bokstaven "O" i luckan mellan dubbletterna.

Använd algoritmen för att översätta ordet PRIMTAL \text{PRIMTAL} till rövarspråket.

1.5
{{ 'ml-btn-focusmode-tooltip' | message }} settings_overscan

Skriv en algoritm i minst tre steg för att beräkna lutningen av en linje.

1.6
{{ 'ml-btn-focusmode-tooltip' | message }} settings_overscan

Skriv en algoritm för att lösa uppgifter av typen "Beräkna absolutbeloppet x|x|", där xx kan vara vilket reellt tal som helst.

Nivå 2
2.1
{{ 'ml-btn-focusmode-tooltip' | message }} settings_overscan

Ragnar är stolt eftersom han har skrivit sin första algoritm. Tanken är att den först ska addera 33 till ett tal, sedan dubblera resultatet fem gånger och till sist subtrahera 6.6. När Ragnar låter några vänner testa den blir han dock nedstämd eftersom de får fel resultat. Hjälp Ragnar att hitta felet i algoritmen och att skriva om den så att den fungerar.

Addera 3 till talet.
Upprepa 5 gånger:
	Multiplicera resultatet med 2.
	Subtrahera 6 från resultatet.
2.2
{{ 'ml-btn-focusmode-tooltip' | message }} settings_overscan

Skriv en algoritm med minst tre steg för att addera två bråk.

2.3
{{ 'ml-btn-focusmode-tooltip' | message }} settings_overscan

Eratosthenes såll är en tvåtusenårig algoritm för att hitta primtal. Den börjar med en lista av heltal från 22 upp till en gräns man själv väljer. Sedan följer man den här processen för att stryka allt som inte är primtal.

Upprepa tills alla tal är antingen inringade eller överstrukna:
	Ringa in första talet som inte är överstruket eller redan inringat.
	Kalla talet n.
	Stryk var n:te efterföljande tal i listan.

När man är klar är de inringade talen alla primtal i listan. Använd Eratosthenes såll för att hitta alla primtal upp till 50.50.

2.4
{{ 'ml-btn-focusmode-tooltip' | message }} settings_overscan

Den här algoritmen tar ett positivt heltal xx och svarar antingen "Ja" eller "Nej".

Gör en lista med alla heltal från 2 t.o.m. x-1.
Upprepa för varje tal i listan:
	Dividera x med talet.
	Om resultatet är ett heltal:
		Svara "Nej".
Om inget annat svar har givits:
	Svara "Ja".

Vilken fråga svarar algoritmen på?

2.5
{{ 'ml-btn-focusmode-tooltip' | message }} settings_overscan

En tidig metod för att kryptera meddelanden var att använda ett Caesarchiffer. Det är ett så kallat substitutionschiffer, där varje tecken i det kodade meddelandet har bytts ut baserat på en algoritm. För att avkoda meddelandet behöver man den nyckel som användes för att göra kodningen. En algoritm för att göra en sådan avkodning kan se ut på följande sätt.

Upprepa för varje tecken i det kodade meddelandet:
	Bestäm tecknets plats i alfabetet.
	Subtrahera nyckeln från platsnumret.
	Om resultatet är mindre än 1:
		Addera 29 till resultatet.
	Bestäm det tecken i alfabetet som motsvarar resultatet.
	Lägg till tecknet i det avkodade meddelandet.

Caesarchiffret är uppkallat efter den romerska kejsaren Julius Caesar, som använde det för att skicka hemliga meddelanden. Han använde nyckeln 33 eftersom C är den tredje bokstaven i alfabetet. Antag att följande meddelande skickades av Caesar och använd algoritmen för att avkoda det.

2.6
{{ 'ml-btn-focusmode-tooltip' | message }} settings_overscan

Beskriv med en algoritm hur man löser en ekvation av typen abx+c=d, ab^x + c = d, där ada-d är heltal större än 11 och d>c.d>c.

2.7
{{ 'ml-btn-focusmode-tooltip' | message }} settings_overscan

Skriv en algoritm som beskriver hur man deriverar ett polynom.

Nivå 3
3.1
{{ 'ml-btn-focusmode-tooltip' | message }} settings_overscan

Algoritmen "Beräknare" använder tre andra algoritmer, "Jämnhetskollare", "Förminskare" och "Förstorare", för att göra beräkningar på tal. Vad får man om använder "Beräknare" på talet 1?

Beräknare

Addera 2 till talet.
Upprepa 3 gånger:
	Använd Jämnhetskollare på resultatet.
Subtrahera 2 från resultatet.

Jämnhetskollare

Om talet är jämnt:
	Använd Förminskare på talet.
Annars:
	Använd Förstorare på talet.

Förminskare

Dela med 2.
Addera 1.

Förstorare

Multiplicera med 3.
Subtrahera 1.
3.2
{{ 'ml-btn-focusmode-tooltip' | message }} settings_overscan

I det gamla romarriket använde man följande siffror. I=1V=5  C=100X=10D=500L=50M=1000\begin{aligned} \text{I} & = 1 \\ \text{V} & = 5 \quad \quad\ \ \, \text{C} = 100\\ \text{X} & = 10 \quad \quad \, \text{D} = 500\\ \text{L} & = 50 \quad \quad \text{M} = 1000\\ \end{aligned} Anta att algoritmen nedan beskriver hur tal, t.ex. XII, tolkas i deras talsystem.

Upprepa för varje tecken:
	Översätt tecknet till motsvarande tal.
Lägg ihop talen.

Talet XII blir alltså 10+1+1=12.10 + 1 + 1 = 12. Säg nu att matematikern Matte Maticus kommer till kejsaren och föreslår att talsystemet byts ut till att följa den här algoritmen istället.

Upprepa för varje tecken:
	Skriv ner motsvarande tal.
Upprepa för varje tal:
	Om talet är mindre än det efterföljande:
		Sätt ett minustecken framför talet.
Lägg ihop talen.


a

Ge ett exempel på ett romerskt tal som algoritmerna tolkar olika.

b

Vilka fördelar har Maticus talsystem jämfört med det gamla?

Test
{{ 'mldesktop-selftest-notests' | message }} {{ article.displayTitle }}!
{{ tests.error }}

{{ 'ml-heading-exercise' | message }} {{ focusmode.exercise.exerciseName }}

keyboard_backspace
{{ section.title }} keyboard_backspace {{ 'ml-btn-previous' | message }} {{ 'ml-btn-previous-exercise' | message }} {{ 'ml-btn-next-exercise' | message }} keyboard_backspace {{ 'ml-btn-next-exercise' | message }}