Dagens ord


Ansvar väger tyngre än frihet - Responsibility trumps liberty

8 dec. 2012

Programmeringens grunder

Att programmera är lätt. Om man vet exakt vad man vill att datorn ska göra.

Och för att klura ut det måste man beskriva för sig själv vad det är som ska göras. Det kan man göra på vanlig svenska. Men man måste vara noggrann, och inte ta något för givet. En sådan beskrivning kallas algoritm. En algoritm kan liknas vid ett recept i en kokbok: Någon som aldrig har bakat förut ska kunna baka en sockerkaka genom att följa receptet till punkt och pricka.

En annan människa, alltså... För att skriva en algoritm som en dator kan följa måste man ta hänsyn till vad en dator kan, och inte kan, göra. Och det betyder oftast att man måste omformulera sin algoritm så att den bara använder mycket enkla instruktioner. En sådan, datorvänlig, beskrivning kallas pseudo-kod.

För oss människor kanske pseudo-koden verkar onödigt krånglig, men vem som helst kan förstå den. Och den gör det också möjligt för oss att få datorn att förstå.

Sista steget, det lätta, är att översätta pseudo-koden till programkod eller källkod. Källkoden skrivs i ett programspråk. Programspråket kan ses som datorns eget språk*, precis som svenska är vårt språk. Olika datorer talar olika språk, t.ex. Pascal, C# eller Java. Dessa språk består av ett litet antal ord, och regler för hur dessa får användas. Så det gäller bara för oss att ta fram rätt ordbok!


Nu ska du få lära dig att programmera! Vi ska lösa en uppgift och sedan skriva en algoritm som beskriver exakt hur vi gjorde när vi löste uppgiften. Sedan ska vi skriva pseudo-kod genom att omformulera algoritmen till enkla och otvetydiga instruktioner. Slutligen ska vi översätta pseudo-koden till ett ett programspråk, och skriva in denna källkod i datorn. Eller, i det här fallet, räknaren.

Ja, den grafritande räknaren (TI-84) går att programmera. Den talar sitt eget språk (som inte har något namn), och ordboken för det språket hittar du här.


Men först, uppgiften! Vi ska lösa en andragradsekvation på formen:

x2 + px + q = 0

Och hur gör man nu det? Ja, i det här fallet har vi en färdig formel att tillgå, så problemet är nästan löst. Men låt oss ändå ta det steg för steg. Formeln ser ut så här:






Med hjälp av formeln kan vi formulera en** algoritm:

  1. Dela p med 2

  2. Kvadrera kvoten

  3. Subtrahera q

  4. Dra kvadratroten ur resultatet

  5. Multiplicera termen p/2 med -1

  6. Lägg till roten för att erhålla den första lösningen

  7. Dra bort roten för att erhålla den andra lösningen

Den här algoritmen är lite otydlig och utelämnar en del detaljer. Men någon som läser matematik på gymnasiet kan (förhoppningsvis) följa den.


När vi skriver pseudo-kod måste vi vara exakta och inte utelämna några detaljer. Det kan se ut så här:

  1. Ta reda på p

  2. Ta reda på q

  3. Multiplicera p med -1 och dela sedan produkten med 2; kalla kvoten a

  4. Kvadrera a; kalla resultatet för b

  5. Subtrahera q från b; kalla resultatet c

  6. Dra kvadratroten ur c; kalla resultatet d

  7. Addera d till a; kalla summan x

  8. Subtrahera d från a; kalla differensen y

  9. Rapportera x

  10. Rapportera y

I pseudo-koden råder det inget tvivel om vad som ska göras, eller om vilka värden som ska användas i de olika beräkningsstegen. De enda instruktioner (ord) som används är de vanliga aritmetiska operationerna, samt instruktioner för att ta reda på de värden som ska användas och för att rapportera resultaten av beräkningarna. Alla värden och delresultat ges också ett bestämt namn. Och alla instruktioner följer efter varandra i en bestämd ordning, eller sekvens.


Nu är vi redo att skriva vårt program, vår källkod. Vi ska alltså översätta pseudo-koden, ord för ord, till en källkod som räknaren kan förstå, med hjälp av ordboken:


Input ”P=”, P

Input ”Q=”, Q

–P/2 ➔ A

A2 ➔ B

B - Q ➔ C

√(C) ➔ D

A + D ➔ X

A - D ➔ Y

Disp ”X1=”, X

Disp ”X2=”, Y


Jämför programmet med pseudo-koden, rad för rad! Du som är van vid räknaren känner igen det mesta: de aritmetiska operationerna fungerar som vanligt. Det nya är dels pilarna (➔) som används för att ge olika värden ett namn (och att lagra dessa i räknarens minne), och orden Input och Disp som används för att ta reda på ingångsvärden respektive rapportera slutresultat. Här har vi alltså gjort en översättning genom att byta ut vissa ord i pseudo-koden mot andra ord från räknarens ordbok. Vi har också följt några regler för hur orden ska användas. Men visst är de båda versionerna ganska lika?


För att skriva in programmet i räknaren, och använda det, gör vi så här:

  • Börja med att trycka på knappen PRGM och välj NEW. Tryck sedan ENTER.

  • Fyll i ett lämpligt namn på programmet, t.ex. ANDRA, och tryck ENTER.

  • Tryck PRGM, välj I/0 och sedan 1:Input. Skriv ”P=”,P och tryck ENTER. (Du hittar tecknet = under 2ND TEST. För att skriva tecken och bokstäver trycker du först på ALPHA.)

  • Gör likadant på nästa rad men byt ut P mot Q. (När du kör programmet kommer räknaren att visa P= tills du skriver in ett tal och trycker på ENTER. Då lagras talet i variabeln P. Sedan sker samma sak med Q.)

  • Skriv nu in rad 3-8 av programmet ovan. Avsluta varje rad med ENTER. (Pilarna ges av knappen STO. När du sedan kör programmet kommer resultaten av dina beräkningarna att sparas i variablerna A, B, C, D, X och Y.)

  • Tryck därefter PRGM, välj I/0 och sedan 3:Disp. Skriv ”X1=”, X. Avsluta med ENTER.

  • Slutligen skriver du på samma sätt in ”X2=”,Y och avslutar med ENTER. (Programmet ska nu se ut som ovan. Kontrollera att det du ser i räknarens fönster stämmer överens med programkoden vi skrev tidigare!)

  • Tryck 2ND QUIT och provkör programmet genom att trycka PRGM och välja ANDRA.

Använd ditt program för att beräkna lösningarna till den här ekvationen:

x2 + 5x - 25 = 0

Nu har du alltså skrivit ett program som du hädanefter kan använda för att enkelt räkna ut lösningarna på en andragradsekvation, eller för att kontrollräkna de lösningar som du räknar ut för hand. Grattis!



Men vänta! Vi är inte färdiga ännu...

En mycket viktig del av programmering är att testköra och felsöka sina program. Att säkerställa att de verkligen fungerar i alla situationer. Eller att tydliggöra i vilka situationer de fungerar. Helst ska ett program vara utformat så att det aldrig kan gå fel. Om programmet inte fungerar i vissa situationer så ska dessa situationer inte kunna uppstå!***

Hur är det med vårt andragradsprogram? Fungerar det? I alla situationer? Hur är det med den här ekvationen****:

x2 + 5x + 25 = 0

Koefficienterna p och q i den här ekvationen ger ett negativt värde under rottecknet (den s.k. diskriminanten). Då finns ingen (reell) lösning till ekvationen. När programmet försöker dra roten ur ett negativt tal ger det ett felmeddelande, och programmet avslutas. Av felmeddelandet framgår bara att något har gått fel, men inte vad.

Du kan förbättra programmet genom att i sådana fall låta programmet skriva ut till exempel ”INGEN REELL ROT”.

Nu måste alltså programmet göra två olika saker, beroende på vilka koefficienter som matas in. Det löser vi genom genom att införa ett villkor. Så här:


Input ”P=”, P

Input ”Q=”, Q

–P/2 ➔ A

A2 ➔ B

B - Q ➔ C

If C < 0

Then


Disp "INGEN REELL ROT"


Else


√(C) ➔ D

A + D ➔ X

A - D ➔ Y

Disp ”X1=”, X

Disp ”X2=”, Y

End


Testkör programmet och kontrollera att det nu ger ett lämpligt meddelande om diskriminanten blir negativ!



Låt oss nu göra programmet ännu bättre! Det skulle vara bra om man slapp att starta om programmet varenda gång man vill lösa en andragradsekvation. I stället vore det bekvämt om man kunde starta programmet, lösa så många ekvationer man ville, och först därefter avsluta programmet.

Vi vill alltså att programmet ska upprepa instruktionerna. Och inte nog med det: Vi vill att instruktionerna ska upprepas tills ett villkor är uppfyllt. Upprepning, eller iteration som det också kallas, är en mycket vanlig beståndsdel av problemlösning och programmering. I vårt fall kan de se ut så här:



➔ S

Repeat S ≠ 0

Input ”P=”, P

Input ”Q=”, Q

–P/2 ➔ A

A2 ➔ B

B - Q ➔ C

If C < 0

Then


Disp "INGEN REELL ROT"


Else


√(C) ➔ D

A + D ➔ X

A - D ➔ Y

Disp ”X1=”, X

Disp ”X2=”, Y

End

Input "AVSLUTA?", S

End



Testkör programmet igen! När du får frågan "AVSLUTA?" trycker du 0 för att svara nej, och alltså fortsätta programmet och börja om från början. Om du trycker något annat än 0 så avslutas programmet.



Som en avslutande övning, utöka nu själv programmet så att det kan lösa andragradsekvationer på formen:

ax2 + bx + c = 0



---

(*) Detta är inte riktigt sant: Datorn utför inte instruktionerna direkt som de står skrivna i programmet. Först översätts programmet i flera steg, tills det består av en sekvens av ettor och nollor. Det första steget i denna översättning görs oftast av ett annat program, som kallas kompilator.

(**) Egentligen kan vi, utifrån formeln, formulera många olika algoritmer som alla beskriver en väg mot samma mål: att räkna ut lösningarna på ekvationen. Algoritmerna kan t.ex. skilja sig åt när det gäller i vilken ordning vi räknar ut olika termer i uttrycket. (Men självklart måste vi följa aritmetikens lagar.)

(***) Det har hänt att flygplan har kraschat för att programmen ombord inte har kunnat hantera en oförutsedd situation.

(****) Och vad händer om den som använder programmet skriver in en bokstav i stället för ett tal...?

(*****) I den här texten beskrivs något som brukar kallas imperativ programmering. Det finns andra sätt, men här används alltså i huvudsak tre byggstenar (sekvens, villkor och iteration) - även om en enda (sekvens) i princip hade räckt. (Det är ungefär så här en Turing-maskin fungerar, och med en sådan kan man faktiskt beräkna allt som över huvud taget är möjligt att beräkna.)


10 kommentarer:

  1. Kan man verkligen ange variabler med flera bokstäver i TI84? Hade helt klart för mig att det var single letter only. =P

    Men annars så borde det gå att följa detta; tror jag.

    SvaraRadera
    Svar
    1. Hmm, jag hade på känn att det nog var så. Men jag tog inte med mig räknaren hem från jobbet, så jag chansade så länge. Fixar detta. Tack! (Minskar läsbarheten något, men det kan ju inte hjälpas.)

      Radera
  2. "Olika datorer talar olika språk, t ex" -> "En dator kan tala ett eller flera olika språk, t ex"

    I algoritmen delar du upp punkt 1 och 5, medan du i pseuodo-koden har slått samman dessa i punkt 3, den direkta översättningen går lite förlorad.

    Man kan väl inte ha variabelnamn med flera tecken i räknaren?

    SvaraRadera
    Svar
    1. Jag funderade över punkt 1 och 2, men kom fram till att jag vill ha det så. Bl.a. för att demonstrera hur de två beskrivningsnivåerna skiljer sig åt - den första ligger nära den "vanliga" problemlösningen, och den andra ligger närmare datorn. Men också för att visa att detaljer mycket väl kan skilja sig åt mellan olika, likvärdiga, beskrivningar. Ska fundera lite till... Har du något konkret förslag på lämplig kompromiss? (Jag försöker ju undvika explicit variabelhantering så mycket som möjligt.)

      Variabelnamnen... Check! Fixar det. Synd, för det gör koden mer "främmande" för nybörjare, tror jag.

      Radera
    2. Jag tänkte att fotnoten skulle räcka för att hantera din punkt 1.

      Radera
    3. Så som du skrivit (över)tolkar jag det som att vissa datorer talar bara C# andra bara Pascal osv. Men "alla" datorer kan ju tala "alla" språk.
      Det kan ju räcka med att tala om att det finns flera olika språk.

      Radera
  3. Det är ungefär så här en Turing-maskin fungerar, och med en sådan kan man faktiskt beräkna allt som över huvud taget är möjligt att beräkna.

    Ett intressant påstående. Är din källa Dennett?

    SvaraRadera
    Svar
    1. Ok, då tolkar jag dig som att du har missförstått (vilket läsning av Dennett kan orsaka).

      Radera
    2. Nej. Jag är väl medveten om den diskussion du hänvisar till, Daniel. Men i den aktuella kontexten, och för textens primära målgrupp, gjorde jag en kalkylerad förenkling.

      Radera