Algoritmer och Programmering: Vad är en Algoritm i Mattematiken

Ragnar är stolt eftersom han har skrivit sin första algoritm. Tanken är att den först ska addera $3$ till ett tal, sedan dubblera resultatet fem gånger och till sist subtrahera $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.

För att se vad som går fel i Ragnars algoritm kan vi testa den. Vi kan t.ex. börja med talet 5 och se vad som händer. Först ska vi addera 3, vilket ger 5 + 3 = 8. Sedan ska vi upprepa rad 3 och 4 fem gånger, alltså först dubblera, 8 * 2 = 16, och sedan subtrahera 6 från resultatet, 16 - 6 = 10. Men här har det blivit fel! Det var ju först på slutet som vi skulle subtrahera 6. "Tanken är att den först ska addera $3$ till ett tal, sedan dubblera resultatet fem gånger och till sist subtrahera $6.$" Eftersom rad 4 är indragen ingår den i upprepningen. Det betyder att man kommer att subtrahera 6 fem gånger: en gång efter varje dubblering. För att få algoritmen att göra det vi vill måste vi alltså ta bort indraget på sista raden så att den instruktionen inte ingår i upprepningen.

Addera 3 till talet. Upprepa 5 gånger: Multiplicera resultatet med 2. Subtrahera 6 från resultatet.

Nu gör algoritmen det Ragnar vill att den ska göra.

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

För att addera två bråk lägger man ihop deras täljare, men det kräver att bråken står på samma nämnare. Därför borde första steget i algoritmen vara att undersöka nämnarna.

Undersök om nämnarna är lika.

Om nämnarna skulle vara olika, som t.ex. för 13 och 14, måste man förlänga bråken till en gemensam nämnare.

Undersök om nämnarna är lika. Om nämnarna är olika: Förläng första bråket med det andra bråkets nämnare. Förläng andra bråket med det första bråkets nämnare.

Nu kommer bråken ha samma nämnare, oavsett hur de såg ut från början. Då kan de läggas ihop, och den färdiga algoritmen ser ut så här.

Undersök om nämnarna är lika. Om nämnarna är olika: Förläng första bråket med det andra bråkets nämnare. Förläng andra bråket med det första bråkets nämnare. Gör ett nytt bråkstreck. Låt täljaren i det nya bråket vara summan av de andra täljarna. Låt nämnaren i det nya bråket vara samma som i de andra bråken.

Det är värt att notera att den här proceduren inte alltid ger ett bråk på sin enklaste form. Testa t.ex. algoritmen på bråken 12 och 14. Kan du ändra i algoritmen så att den alltid ger ett bråk på enklaste form?

Eratosthenes såll är en tvåtusenårig algoritm för att hitta primtal. Den börjar med en lista av heltal från $2$ 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 .

Hur många är de?

Algoritmen behöver en lista av tal från 2 upp till någon övre gräns. Vi vill hitta alla primtal upp till 50, och då är 50 den övre gränsen.

Nu kan vi använda algoritmen. Steg ett är att ringa in det första talet, dvs. 2. Steg två säger då att n=2, och steg tre att vi ska "stryka var n:te tal". När n=2 betyder det vartannat tal.

Efter strykningarna gjorts är det dags för nästa varv i algoritmen. Nu är det talet 3 som ringas in, och sedan stryks var 3:e tal. Vissa tal som t.ex. 6 ska då strykas igen enligt algoritmen, inte hoppas över. Processen fortsätter tills listan innehåller endast inringade och överstrukna tal. Tryck Starta nedan för att se hela processen.

Den här algoritmen tar ett positivt heltal $x$ 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å?

Vi börjar med att testa algoritmen på ett tal för att se vad som händer. Vi väljer x = 5 och börjar på första steget, vilket är att göra en lista med alla tal från 2 till och med x - 1, alltså 5 - 1 = 4. Listan innehåller då talen 2, 3 och 4. För varje tal i listan ska vi sedan dividera x=5 med talet och om resultatet är ett heltal svarar vi "Nej". Vi gör uträkningarna och ser att vi inte får några heltal som resultat. 5/2 = 2,5 5/3 = 1,666... 5/4 = 1,25 Vi svarar alltså inte "Nej" utan går vidare från upprepningen. Inget annat svar har givits, så vi svarar "Ja". För x = 5 får man alltså resultatet "Ja". Vi gör samma sak för x = 6, där listan med tal blir 2, 3, 4 och 5. När vi går igenom dem märker vi direkt på första talet att divisionen 62 = 3 ger ett heltal som resultat. Då ska vi svara "Nej". Fortsätter vi igenom talen ser vi att även 63 = 2 är ett heltal. När vi kommer ut ur upprepningen har vi alltså redan gett svaret "Nej" så vi hoppar över den sista instruktionen. Använder man algoritmen för talen från x = 3 till x = 10 får man följande resultat. &3: Ja 4: Nej 5: Ja 6: Nej &7: Ja 8: Nej 9: Nej 10: Nej Algoritmen verkar avgöra vilka tal som är primtal och vilka som inte är det. Genom att titta på instruktionerna i algoritmen kan vi bekräfta detta. Ett primtal är jämnt delbart endast med 1 och sig självt, och det är ju det vi kontrollerar när vi försöker dividera x med olika tal. Algoritmen svarar alltså på frågan: "Är $x$ ett primtal?"

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 $3$ 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.

När vi går igenom algoritmen måste vi ganska ofta avgöra vilket platsnummer en viss bokstav har i alfabetet. Då kan det vara bekvämt att ha alfabetet och de motsvarande numren utskrivna så att man lätt kan göra en avläsning istället för att räkna igenom alfabetet varje gång.

Algoritmen säger att vi ska göra samma sak för alla tecken i det kodade meddelandet, så vi börjar med det första tecknet. Det är ett W och för att avgöra vilket platsnummer det har i alfabetet tittar vi i vår tabell.

Nästa steg är att vi ska subtrahera nyckeln, som är 3, från platsvärdet, vilket ger 23 - 3 = 20. Detta är inte under 1 så vi kan hoppa över rad 5 och gå direkt till rad 6. På den ska vi avgöra vilken bokstav 20 motsvarar, vilket vi kan göra genom att göra en till avläsning i tabellen.

Bokstaven W blir alltså ett T efter att man har avkodat den.

Vi gör sedan samma sak för nästa tecken i det kodade meddelandet. Det är ett B, som har platsnummer 2 i alfabetet. Drar vi bort nyckeln från detta får vi 2 - 3 = -1. Det är mindre än 1, så vi måste göra steg 5 i algoritmen: addera 29 till resultatet. Då får vi -1 + 29 = 28, vilket motsvarar bokstaven Ä i alfabetet.

Nästa tecken är ett U, som har platsnummer 21. Det ger det nya platsnumret 18 efter att man har dragit bort nyckeln. Det är inte under 1 så vi kan direkt läsa av att det avkodade tecknet är R.

Fortsätter vi på samma sätt får vi till slut hela det avkodade meddelandet.

Beskriv med en algoritm hur man löser en ekvation av typen

a b^{x} + c = d,

där

a - d

är heltal större än

1

och

d > c .

För att förstå problemet lite bättre väljer vi några värden på koefficienterna. Vi måste tänka på att de ska vara större än 1 och att värdet på d måste vara högre än c, t.ex. såhär: 2* 3^x +4 = 5. Genom att lösa ekvationen på vanligt sätt kan vi se vilka steg som behövs i algoritmen.

Nu har vi räknat med specifika tal, men en algoritm ska vara generell. Den ska alltså använda bokstäverna a,b,c,d istället för tal. Utöver det behöver vi faktiskt bara beskriva beräkningsstegen ovan i ord, så är algoritmen klar.

Subtrahera c från båda led. Dividera båda led med a. Logaritmera båda led. Använd logaritmlagen lg(b^x)=x*lg(b). Dela båda led med lg(b).

Vad hade hänt utan kravet på att d > c? Då hade det blivit 0 eller negativt i högerledet efter första steget. Då hade logaritmen i tredje steget inte gått att räkna ut, och ekvationen skulle sakna lösning.

Skriv en algoritm som beskriver hur man deriverar ett polynom.

När man deriverar polynom gör man det term för term, och beroende på hur termen ser ut gör man på olika sätt. Om termen innehåller en variabel med en exponent gäller följande regel. D(a x^n) = a * n x^(n-1) Om variabeln har exponenten 1, alltså när det bara står x, tar man helt enkelt bort variabeln när man deriverar. D(ax) = a Sista fallet är när det inte finns någon variabel alls utan bara en konstant. Då försvinner denna konstant när man deriverar. D(a) = 0 De sista två fallen är egentligen specialfall av det första, men det är enklare att se dem som tre olika situationer. Nu när vi har tänkt igenom de olika situationerna kan vi börja skriva vår algoritm. Först anger vi att man ska göra samma sak för alla termer i polynomet.

Upprepa för varje term i polynomet:

Sedan måste vi avgöra vilket av de tre fallen som gäller för varje term. Vi börjar med att undersöka om det finns någon variabel i termen.

Upprepa för varje term i polynomet: Om det finns en variabel i termen:

Om det finns en variabel måste det vara fall 1 eller 2 det är frågan om. Vilket av dessa fall det är kan vi avgöra genom att titta på variabelns exponent. Om den är 1 har vi det andra fallet och då räcker det med att ta bort variabeln.

Upprepa för varje term i polynomet: Om det finns en variabel i termen: Om exponenten på variabeln är 1: Ta bort variabeln.

Om exponenten på variabeln inte är 1 måste det vara frågan om det första fallet. Då ska vi multiplicera termen med det värde som står i exponenten och sedan subtrahera 1 från exponenten.

Upprepa för varje term i polynomet: Om det finns en variabel i termen: Om exponenten på variabeln är 1: Ta bort variabeln. Annars: Multiplicera termen med exponenten. Subtrahera 1 från exponenten.

Till sist måste vi skriva in i algoritmen vad man ska göra om det inte finns någon variabel alls i termen, alltså när den är en konstant. Då ska vi bara ta bort termen.

Nu har vi en färdig algoritm som kan användas för att derivera ett polynom.

Algoritmer och programmering

Förkunskaper

Algoritm

Skriv algoritmen

Svar

Ledtråd

Lösning

Verktyg för algoritmer

Upprepning

Villkor

Använd algoritmen

Ledtråd

Lösning

Algoritmer och programmering

Rekommenderade uppgifter

	6 sidor teori
	15 Uppgifter - Nivå 1 - 3
	Varje lektion är menad motsvara 1-2 lektioner i klassrummet.