Det finns mycket terminologi och många förkortningar inom IT som även den ointresserade kan stöta på i vardagen. Digital teknik används ofta både i arbetsliv och på fritiden, det är därför oundvikligt att man stöter på IT-ord. Eftersom många av orden är relativt nya, är det också vanligt att engelska ord eller uttryck används och den språkligt intresserade kan undra vad det egentligen heter på korrekt svenska. Tänk exempelvis på hur vi använder orden: e-post, e-brev, email, mail, mejl; vilket ord är det som anses vara korrekt? Den svenska datatermgruppen ger rekommendationer om hur datatermer ska användas och på deras hemsida kan man exempelvis söka på ordet 'mail'. En annan välfungerande källa för den som undrar över terminologi är Computer Swedens IT-ord, Ord och uttryck i it-branschen.
I det här kapitlet kommer vi inledningsvis att, utan djupgående förklaringar, gå igenom viss terminologi som en genomsnittlig datoranvändare stöter på. För lärare kan det vara värt att tänka på att ord som operativsystem eller webbläsare är okända ord för en del elever, trots att de allra flesta elever använder något operativsystem och någon webbläsare dagligen.
Efter genomgången av ord som kan dyka upp då man använder en dator eller surfar på webben, går vi igenom teori som har direkt anknytning till programmering.
I de två sista delkapitlen nämner vi några begrepp som hör hemma i algoritmteori och diskret matematik.
Alla genomgångar är översiktliga och antalet definitioner som används i samband med olika begrepp hålls avsiktligt på en minimumnivå.
Delar av detta kapitel är enklare att förstå efter att du börjat programmera i något programmeringsspråk. Inom programmering, liksom inom de flesta ämnen, kommer förståelsen genom att man gör, inte genom att man läser om. Förslagsvis kan delkapitlen En dator, Internet och World Wide Web, Algoritmer, Binära tal och Logiska operatorer läsas utan några förkunskaper medan resterande delkapitel läses efter det att du börjat programmera.
Ordet dator kan användas på olika sätt i olika sammanhang. Om man med en dator menar någon sorts processor som kan köra ett program, så finns det exempelvis moderna köksapparater som innehåller en dator. Vi kommer att använda ordet dator för att beskriva en digital maskin med vilken man kan köra program och också installera program. På så vis inbegrips sedvanliga stationära eller bärbara datorer samt mobila enheter men inte köksapparater, robotgräsklippare eller dylikt. Med mobila enheter avses moderna mobiltelefoner samt surfplattor som exempelvis iPad.
En dator innehåller en processor som kan köra program. Ibland används den engelska förkortningen CPU vilket står för Central Processing Unit. När processorn ska köra ett program, hämtas programmets instruktioner och läggs i arbetsminnet, vilket också kan kallas för primärminnet. Om programmet hanterar någon sorts data läggs även denna data i arbetsminnet. En av enheterna i processorn kan utföra enkel aritmetik och logiska operationer. På låg nivå utförs sådana operationer med hjälp av elektroniska komponenter som behandlar signaler vilka antingen är på eller av, alternativt har hög spänning eller låg spänning, eller om man använder korta symboler: är 1 eller 0. Av den anledningen används binära tal internt av en dator.
Program och data ligger lagrade på något sekundärminne. Några vanliga sekundärminnen är en hårddisk, en diskett, eller ett usb-minne.
När man i vardagligt språk talar om en dators minne, menar man arbetsminnet. Ordet sekundärminne används sällan i vardagligt språk, däremot talas det ibland om en dators hårddisk, det vanligaste sekundärminnet.
För att kunna använda en dator krävs det någon sorts I/O-enheter. I/O är en förkortning av de engelska orden input och output, vilka på svenska kallas indata och utdata. Indatan är den data datorn tar emot av användaren. Utdata är den data användaren tar emot av datorn. Exempel på indataenheter är tangentbord, datormus och mikrofon. Exempel på utdataenheter är skärm och högtalare. Orden indata och utdata används också då man programmerar. Indata är då den data programmet tar emot och utdata den data som skapas av programmet.
När du sätter på en dator startar datorns operativsystem, vilket ibland förkortas till OS. Operativsystemet består av en samling program som ser till att datorn går att använda. Om du byter operativsystem på en dator kommer det som visas på skärmen att se annorlunda ut och datorn kommer att fungera lite annorlunda.
De vanligaste operativsystemen för datorer är Windows, Mac OS X och Linux. De vanligaste operativsystemen för mobila enheter är iOS (iPhone, iPad) och Android.
Internet är världens största datornätverk och är sprunget ur föregångaren ARPANET vilket utvecklades under 60-talet av det amerikanska försvaret. Världens första e-postmeddelande skickades 1971 via ARPANET av Ray Tomlinson. Tomlinson använde tecknet @ för att separera användarnamnet och datorns namn. Tomlinson räknas som e-postens upphovsman.
I slutet av 80-talet arbetade sir Tim Berners-Lee på den internationella forskningsanläggningen CERN i Schweiz. Till CERN kom det forskare från hela världen och de behövde kunna delge varandra information via datornätverk trots att de hade olika datorer. Berners-Lee uppfann 1989 World Wide Web (www eller w3) för att möjliggöra ett sådant informationsutbyte via internet. En av huvudidéerna med World Wide Web är att information ska kunna länka till annan information. Informationen skrivs därför som så kallad hypertext vilken innehåller länkar. Länkarna bildar ett nät som tillsammans utgör ett världsomspännande informationssystem.
I dag används sällan ordet hypertext eftersom texter med länkar på webben har blivit en så stor del av vår vardag. Ordet återfinns dock i vissa förkortningar exempelvis i förkortningen html (HyperText Markup Language) vilket betecknar den kod som används för att göra hemsidor. Ordet hypertext återfinns också i förkortningen http (HypertText Transfer Protocol) vilken en hemsidas adress vanligtvis inleds med. Ordet protokoll i förkortningen http är ett så kallat kommunikationsprotokoll, dvs en uppsättning regler som används för att datorer ska kunna kommunicera med varandra.
Vissa hemsideadresser inleds inte av http utan av förkortningen https vilket står för Hypertext Transfer Protocol Secure. För en hemsida vars adress inleds med https, skickas all information mellan server och klient som krypterad information. Hemsidor som kräver någon sorts inloggning, eller använder sig av formulär som användaren fyller i, bör använda sig av https. Om du skickar någon sorts data, genom att exempelvis fylla i ett formulär, är det viktigt att datan faktiskt hamnar på rätt ställe. Den server där hemsidan ligger kan identifiera sig med hjälp av ett så kallat SSL-certifikat, där SSL står för (Secure Sockets Layer). Om allting fungerar som det ska, märker du aldrig av att SSL-certifikatet används då din klient kommunicerar med servern. Det kan dock hända att en hemsidas ägare inte har uppdaterat sitt SSL-certifikat, eller att den hemsida du vill besöka är utsatt för någon sorts attack, då får du någon sorts felmeddelande.
Det vanligaste sättet att strukturera ett datornätverk är att använda den så kallade klient-server-modellen. Med klient-server-modellen tilldelas alla datorer i nätverket en roll som antingen är klient eller server. Klienter kan inte kommunicera direkt med varandra utan kommunicerar via en server.
World Wide Web är uppbyggd med klient-server-modellen. För att betrakta en hemsida på webben använder du ett program som kallas webbläsare, ibland används det engelska ordet browser istället för webbläsare. Webbläsaren skickar en förfrågan om exempelvis ett html-dokument till en webbserver som i sin tur skickar förfrågan till en annan server, osv, tills den server där html-dokumentet lagras har nåtts. Dokumentet skickas sedan tillbaka till webbläsaren som ser till att dokumentet visas på ett användarvänligt sätt för användaren. Om du vill se hur det ursprungliga dokumentet ser ut, kan du högerklicka på en hemsida och välja Visa källkod (eller liknande kommando).
De vanligaste webbläsarna är Edge (endast Windows), Safari (endast Mac), Chrome och Firefox.
När du söker efter information på webben använder du någon sorts sökmotor. Den vanligaste sökmotorn är Googles sökmotor. Denna är så vanlig att namnet ofta används som ett verb: att Googla. Det finns också andra sökmotorer exempelvis DuckDuckGo, Yahoo, Bing eller den kinesiska Baidu.
En algoritm är en beskrivning av hur man löser ett problem eller utför någon specifik uppgift. Algoritmer används ibland inom matematiken och ofta inom datavetenskap.
I skolans matematikundervisning används exempelvis algoritmer för hur man hanterar de fyra räknesätten då man räknar för hand. När eleverna får lära sig hur man använder en algoritm för något räknesätt, lär de sig i regel detta med hjälp av exempel: Så här dividerar man 1678 med 745.... Efter några sådana exempel lär sig eleven (förhoppningsvis) hur man gör i det allmänna fallet, dvs hur man dividerar vilka tal som helst. Det är enklare för en människa att lära sig dividera med hjälp av exempel, än att läsa och förstå en instruktion för hur man dividerar talet \(a\) med talet \(b\). Om man ska göra ett datorprogram som åskådliggör någon aritmetisk algoritm, behövs dock en skriven instruktion som hanterar det allmänna fallet. Nybörjare i programmering kan slås av att det är svårare att ge instruktioner till en dator än att berätta och förklare för en människa.
När man utvecklar en algoritm kan man börja med en grov beskrivning. Vi ger ett exempel som har färre instruktioner än additionsalgoritmen, en algoritm för hur man kokar en kopp te med en tepåse.
Gör en kopp te
Lägg en tepåse i en kopp
Koka vatten
Häll vattnet i koppen
Vänta en stund
Efter den grova beskrivningen kan man beskriva algoritmer för enstaka detaljer.
Koka vatten
Om det finns en vattenkokare:
Häll vatten i vattenkokaren
Sätt på vattenkokaren
Vänta tills vattenkokaren är klar
annars:
Häll vatten i en kastrull
Ställ kastrullen på spisen
Sätt på spisen
Vänta tills vattnet kokar
Stäng av spisen
Här har vi dragit in texten så att text som hör till vattenkokaren, respektive kastrullen, visuellt hänger ihop. Att dra in text på detta vis kallas för att indentera texten.
Ett annat vanligt sätt att beskriva en algoritm är att använda ett flödesschema.
Algoritmer inom datavetenskap beskriver hur någon uppgift kan utföras med hjälp av programmering. Ett program som utför den uppgift en algoritm beskriver sägs implementera algoritmen.
Innan vi går vidare med algoritmer i samband med programmering, går vi igenom två teoretiska moment som man bör känna till när man lär sig programmera, binära tal och logiska operatorer.
Med det decimala talsystemet skrivs varje tal som en sammansättning av siffrorna \(0, 1, 2, 3, 4, 5, 6, 7, 8 \) och \(9\). Talet tio används som bas och en siffras position avgör vilken tiopotens siffran ska multipliceras med, exempelvis är:
\[ 703,56 = 7\cdot 10^2+0\cdot 10^1 + 3\cdot 10^0+5\cdot 10^{-1}+6\cdot 10^{-2} \]Med det binära talsystemet skrivs varje tal som en sammansättning av siffrorna \(0\) och \(1\). Talet två används som bas och en siffras position avgör vilken tvåpotens siffran ska multipliceras med, exempelvis är:
\[ 1101,11 = 1\cdot 2^3+ 1\cdot 22 + 0 \cdot 2^1 + 1\cdot 2^0 + 1\cdot 2^{-1} + 1\cdot 2^{-2} \]I likheten ovan är vänsterledet ett binärt tal men högerledet är skrivet med decimala tal. För att tydliggöra vilken bas som används kan man använda ett nedsänkt index till höger om ett tal eller ett uttryck, ett index som betecknar basen. Likheten ovan skrivs då på följande vis:
\[ 1101,11_2 = (1\cdot 2^3+ 1\cdot 22 + 0 \cdot 2^1 + 1\cdot 2^0 + 1\cdot 2^{-1} + 1\cdot 2^{-2})_{10} \]Framöver kommer vi bara att använda heltal.
Att omvandla ett binärt tal till ett decimalt tal är relativt enkelt.
Skriv \(10110_2\) som ett decimalt tal.
Den första positionen till vänster om decimalkommat räknas som position \(0\). Siffran på denna position ska alltså multipliceras med \(2^0\). De andra positionerna räknas upp då man går åt vänster och för varje position ska siffran i talet multipliceras med två upphöjt till positionen.
| tal | \(1\) | \(0\) | \(1\) | \(1\) | \(0\) |
|---|---|---|---|---|---|
| position | \(4\) | \(3\) | \(2\) | \(1\) | \(0\) |
| tvåpotens | \(2^4\) | \(2^3\) | \(2^2\) | \(2^1\) | \(2^0\) |
| tvåpotens | \(16\) | \(8\) | \(4\) | \(2\) | \(1\) |
Vi får alltså att
\[ \begin{align*} 10110_2 & = (1\cdot 2^4 + 0 \cdot 2^3 + 1 \cdot 2^2 + 1 \cdot 21 + 0 \cdot 2^0)_{10} \\ &= (16+4+2)_{10} \\ &= 22_{10} \end{align*} \]\( 10110_2 = 22_{10}\)
Att omvandla från decimalt till binärt är något svårare.
Skriv \(210_{10}\) som ett binärt tal.
Vi ska skriva \(210_{10}\) som en summa av tvåpotenser där varje tvåpotens får vara med högst en gång. Vi börjar därför med att skriva upp de tvåpotenser som kan tänkas behövas.
| på potensform | \(2^8\) | \(2^7\) | \(2^6\) | \(2^5\) | \(2^4\) | \(2^3\) | \(2^2\) | \(2^1\) | \(2^0\) |
|---|---|---|---|---|---|---|---|---|---|
| uträknad | \(256\) | \(128\) | \(64\) | \(32\) | \(16\) | \(8\) | \(4\) | \(2\) | \(1\) |
Vi kommer inte behöva någon tvåpotens större än \(256\) eftersom \(256 > 210 \).
Sedan letar vi upp den största tvåpotens som är \( \le 210 \) och finner att det är \(128\). Vi utför subtraktionen
\[210-128 = 82.\]Sedan letar vi upp den största tvåpotens som är \( \le 82 \) och finner att det är \(64\). Vi utför subtraktionen
\[82-64 = 18.\]Sedan letar vi upp den största tvåpotens som är \( \le 18 \) och finner att det är \(16\). Vi utför subtraktionen
\[18-16 = 2.\]Sedan letar vi upp den största tvåpotens som är \( \le 2 \) och finner att det är \(2\). Vi utför subtraktionen
\[2-2 = 0.\]Nu vet vi att
\[ \begin{align*} 210 & = 128 + 82 \\ &= 128 + 64 + 18 \\ &= 128 + 64 + 16 + 2 \end{align*} \]vilket är en summa av tvåpotenser. Nu återstår det bara att ersätta varje tvåpotens som ingår med en etta på rätt position, och att placera en nolla på de positioner där tvåpotensen inte ingår.
\[ \begin{align*} 210 & = 2^7 + 2^6 + 2^4 + 2^1 \\ &= 2^7 + 2^6 + \color{red}{0 \cdot 2^5}+ 2^4 + \color{red}{0\cdot 2^3} + \color{red}{0\cdot 2^2}+ 2^1 +\color{red}{0 \cdot 2^0} \end{align*} \]\( 210_{10} = 11010010_2\)
Om man vill skriva ett program som omvandlar från decimalt till binärt, går det visserligen att använda metoden som visas i Exempel 2 men det finns en algoritm som är betydligt enklare att utföra, om än något svårare att förstå.
De flesta programmeringsspråk kan beräkna resten och kvoten då ett heltal divideras med ett annat heltal. Så kallad heltalsdivision är när man vid division delar upp resultatet i kvot och rest.
Om vi exempelvis dividerar \(20\) med \(6\) blir kvoten \(3\) och resten \(2\) vilket kan skrivas som
\[ \frac{20}{6} = 3 + \frac{2}{6} \]eller om man vill undvika bråktal som
\[ 20 = 6\cdot 3 +2. \]Genom att upprepade gånger heltalsdividera kan man ta reda på vilka siffror ett tal är sammansatt av. Vi ska börja med att visa hur det går till för ett decimalt tal och sedan använda samma metod för att omvandla från decimalt till binärt.
Ta reda på vilka siffror som ingår i talet \(2734\).
Om vi heltalsdividerar \(2734\) med \(10\) får vi kvoten \(273\) och resten \(4\), dvs
\[ 2734 = 10\cdot 273 + 4. \]Resten \(4\) är siffran längst till höger i talet \(2734\). För att få fram nästa siffra, från höger, heltalsdividerar vi kvoten \(273\). Vi kan upprepa heltalsdivision med tio tills kvoten blir noll.
\[ \begin{align*} 2734 &= 10\cdot 273 + 4 \\ 273 &= 10\cdot 27 + 3 \\ 27 &= 10\cdot 2 + 7 \\ 2 &= 10\cdot 0 + 2 \end{align*} \]I beräkningarna ovan är resterna vid heltalsdivision de siffror som ingår i \(2734\), i ordningen nerifrån och upp.
Om vi i Exempel 3 i varje steg hade dividerat med två istället för tio, hade vi i varje steg fått en rest som var antingen noll eller ett. Dessa rester hade varit siffrorna i det binära talet. Vi visar en sådan beräkning med samma tal som användes i Exempel 2.
Skriv \(210_{10}\) som ett binärt tal genom att använda upprepad heltalsdivision.
De binära siffrorna fås nu genom att skriva resterna nerifrån och upp.
\( 210_{10} = 11010010_2\)
Ett talsystem kan ha vilket heltal som helst som bas, bara talet är större än ett. Inom datavetenskap används ibland oktala tal (basen åtta) eller hexadecimala tal (basen sexton). Notera att både åtta och sexton är heltalspotenser av två. Vi kommer att särskilt nämna hexadecimala tal, dels för att tio siffror inte räcker till för att skriva ett hexadecimalt tal och dels för att hexadecimala tal ofta dyker upp när man håller på med program som hanterar färger.
Ett hexadecimalt tal sätts samman av sexton siffror. Eftersom det bara finns tio hindu-arabiska siffror övergår man till alfabetet när de hindu-arabiska siffrorna tagit slut.
| hexadecimal siffra | \(0\) | \(1\) | \(2\) | \(3\) | \(4\) | \(5\) | \(6\) | \(7\) | \(8\) | \(9\) | \(\text{a}\) | \(\text{b}\) | \(\text{c}\) | \(\text{d}\) | \(\text{e}\) | \(\text{f}\) |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| värde | \(0\) | \(1\) | \(2\) | \(3\) | \(4\) | \(5\) | \(6\) | \(7\) | \(8\) | \(9\) | \(10\) | \(11\) | \(12\) | \(13\) | \(14\) | \(15\) |
Med dessa siffror gäller det exempelvis att
\[ \begin{align*} \text{f}30\text{a}_{16} &= (15\cdot 16^3 +3\cdot 16^2 + 0\cdot 16^1 + 10\cdot 16^0)_{10} \\ &= (15\cdot 4\,096 + 3\cdot 256 + 10)_{10} \\ &= (62\,218)_{10} \end{align*} \]Ett av de vanligaste sätten att ange en färg när man använder datorprogram, är att ange en så kallad RGB-färg. Förkortningen RGB står för RedGreenBlue och en RGB-färg anges med hur mycket rött, grönt och blått färgen ska innehålla. Andelen rött, grönt och blått anges med tre tal som vardera är mellan \(0\) och \(255\).
En RGB-färg kan skrivas på hexadecimal form genom att man skriver varje tal (röd, grön, blå) som ett hexadecimalt tal och sätter samman de tre hexadecimal talen. På detta vis anges färger på webben, med ett #-tecken i början.
Om vi vill omvandla ett tal mellan \(0\) och \(255\) till ett hexadecimalt tal noterar vi först att \(16^2 = 256\). Talet kommer alltså att bestå av högst två hexadecimala siffror. Vi får den ena siffran genom att ta kvoten då talet divideras med sexton och det andra genom att ta resten.
För att exempelvis omvandla det decimala talet \(109\) till ett hexadecimalt tal, heltalsdividerar vi \(109\) med sexton. Eftersom \(109 = 16\cdot 6 + 13 \) får vi att \( 109_{10} = 6\text{d}_{16} \).
Binära tal, datalagring och färger, på YouTube.
En binär operator verkar på två operander. I operationen \(5-3\) verkar operatorn minus på två operander.
En unär operator verkar på en operand. I operationen \(-5\) verkar operatorn minus på en operand.
Aritmetiska operatorer verkar på tal och resultatet av en operation är ett tal. Alla programmeringsspråk kan hantera de fyra räknesätten och de flesta programmeringsspråk kan dessutom beräkna resten och kvoten vid heltaldivision. Alla dessa operationer är exempel på aritmetiska operationer.
En logisk operator verkar på ett logiskt värde och resultatet är ett logiskt värde. Det finns två logiska värden: sann och falsk.
Alla programmeringsspråk kan hantera tre logiska operatorer:och, eller samt inte. Inom logik och matematik brukar följande symboler användas:
| operator | och | eller | inte |
|---|---|---|---|
| symbol | \(\land\) | \(\lor\) | \(\lnot\) |
Operatorerna \(\land \) och \(\lor \) är binära operatorer. Operatorn \( \lnot \) är en unär operator.
De logiska operationer som utförs av de tre operatorerna kan beskrivas med sanningsvärdestabeller. Vi använder förkortningen s för sann och f för falsk. Vi låter \(p\) och \(q\) vara logiska påståenden eller uttryck. De tre sanningsvärdestabellerna ser ut så här:
| \(p\) | \(q\) | \( p \land q\) |
|---|---|---|
| s | s | s |
| s | f | f |
| f | s | f |
| f | f | f |
| \(p\) | \(q\) | \( p \lor q\) |
|---|---|---|
| s | s | s |
| s | f | s |
| f | s | s |
| f | f | f |
| \(p\) | \( \lnot p\) |
|---|---|
| s | f |
| f | s |
Sanningsvärdestabeller kan användas för att reda på vilka värden man får från sammansatta operationer. Vi visar ett exempel.
Visa med hjälp av sanningsvärdestabeller att sammansättningen
\[ \lnot(p\lor q) \]ger samma resultat som sammansättningen
\[ \lnot p\land \lnot q \]Vi börjar med att göra en sanningsvärdestabell för \( \lnot(p\lor q) \) och fyller i kolumnerna från vänster till höger. Den fjärde kolumnen får vi genom att negera värdena i den tredje kolumnen, vi använder alltså sanningsvärdestabellen för \( \lnot\) på värdena i kolumn tre.
| \(p\) | \(q\) | \( p \lor q\) | \( \lnot(p \lor q)\) |
|---|---|---|---|
| s | s | s | f |
| s | f | s | f |
| f | s | s | f |
| f | f | f | s |
Sedan gör vi en tabell för \( \lnot p\land \lnot q \). Vi börjar med att negera \(p\) och \(q\), därefter använder vi sanningsvärdestabellen för \(\land\) på de negerade värdena.
| \(p\) | \(q\) | \( \lnot p \) | \( \lnot q \) | \( \lnot p\land \lnot q \) |
|---|---|---|---|---|
| s | s | f | f | f |
| s | f | f | s | f |
| f | s | s | f | f |
| f | f | s | s | s |
Vi har nu visat att \( \lnot(p\lor q) \) och \( \lnot p\land \lnot q \) ger samma resultat för alla tänkbara värden på \(p\) och \(q\), därför är dessa två logiska sammansättningar ekvivalenta.
De logiska operatorerna skrivs på olika sätt i olika programmeringsspråk. Vi visar några exempel:
| logisk operator | \( \land \) | \( \lor \) | \( \lnot\) |
|---|---|---|---|
| Java, C, C++, Javascript | && |
|| |
! |
| Python | and |
or |
not |
| php | And |
Or |
Not |
När man programmerar används också ofta jämförelseoperatorer. En jämförelseoperator verkar på tal och resultatet är ett logiskt värde, dvs resultatet är antingen sant eller falskt. Inom matematiken används följande symboler för att jämföra två tal: \(= \), \(\neq\), \(>\), \(<\), \(\ge\), \(\le\). Dessa jämförelser skrivs på olika sätt i olika programmeringsspråk.
Logiska operatorer och sanningsvärdestabeller, på YouTube.
Det enda språk en dator kan förstå är så kallat maskinspråk eller maskinkod vilket enbart består av ettor och nollor. Eftersom koden enbart består av ettor och nollor kan den också kallas för binärkod. Det är synnerligen svårt för människor att hantera maskinkod så därför används något programmeringsspråk när man ska ge instruktioner till en dator. Det man skriver i något programmeringsspråk kallas för källkod. För att datorn ska kunna förstå källkoden måste den översättas till maskinkod.
När källkod ska översättas till maskinkod görs det antingen av en kompilator eller av en interpretator, beroende på vilket språk det handlar om. En kompilator tar den fil, eller de filer, programmet består av och skapar en ny exekverbar fil. Att köra ett datorprogram kallas för att exekvera programmet, en exekverbar fil kan alltså köras exempelvis genom att man dubbelklickar på filen. En interpretator skapar ingen exekverbar fil utan översätter källkoden till maskinkod och kör den direkt. De applikationer som du använder på din dator har i regel kompilerats till exekverbara filer som du använder. Program som exempelvis körs i webbläsaren interpreteras och körs direkt.
Det finns många olika listor (exempelvis TIOBE Index) på de mest använda och de mest populära programmeringsspråken i världen. Resultaten varierar beroende på hur listorna sammanställts men de flesta listor brukar ange programmeringsspråket Java på första plats. Några andra språk som är mycket vanliga är C, C++, Python, PHP och Javascript. Alla de nämnda språken kan användas oavsett vilket operativsystem du använder. Det finns också programmeringsspråk som är specifikt gjorda för Microsoft- eller Apple-miljöer.
Programmeringsspråket Javascript har en särställning eftersom det är det enda programmeringsspråk som alla vanliga webbläsare kan köra utan att man installerar en insticksmodul. Förr var det vanligt att Java användes även för program på webben. Då användes så kallade Java applets som kunde köras av webbläsare om man installerat en instickmodul för Java. Java applets ansågs med tiden utgöra en säkerhetsrisk och används numera sällan eller aldrig. Namnen Java och Javascript kan vara förvillande eftersom de antyder att det handlar om ungefär samma språk, vilket inte är fallet. Java och Javascript är två olika programmeringsspråk men vissa delar av syntaxen liknar varandra. Programmeringsspråken Java, Javascript, C och C++ har alla en syntax som till vissa delar liknar varandra.
Ett annat vanligt språk som används på webben är Flash. För att köra Flash krävs det att insticksmodulen Flash Player är installerat. Eftersom Flash Player inte används på en iPad, skapas det allt färre hemsidor som använder sig av Flash.
De symboler, de speciella ord och den struktur som ett programmeringsspråk använder sig av kallas för programmeringsspråkets syntax.
Några vanliga symboler som används av diverse programmeringsspråk är:
{ } [ ] ; , . ! $ " ' \ /
De speciella ord som används av ett programmeringsspråk kallas för reserverade ord. Några vanliga reserverade ord som används av diverse programmeringsspråk är :
for while if else repeat break end
All data och alla instruktioner som används vid programmering, måste internt representeras av ettor och nollor. Exakt hur den interna representationen ser ut, behöver man som programmerare inte känna till, däremot kan det vara bra att ha en hum om hur det fungerar. Datorns minne använder sig av ett eller flera register där data kan lagras och flyttas runt. Registret innehåller en mängd celler och varje cell har en adress. Data kan alltså flyttas från en cell med en viss adress till en annan cell med en annan adress. Vi visualiserar ett register med en tabell.
| adress | innehåll | |||
|---|---|---|---|---|
| \(573\) | 0 | 0 | 1 | 0 |
| \(574\) | 1 | 0 | 1 | 0 |
| \(575\) | 0 | 0 | 1 | 1 |
För vårt tänkta register består varje cell av fyra stycken ettor eller nollor. Om vi lagrar icke-negativa heltal i en sådan cell är det minsta talet \(0\) (0000) och det största talet \(15\) (1111). Vi kan alltså lagra \(16=2^4\) olika tal i ett register där varje cell består av fyra stycken ettor eller nollor.
En etta eller nolla kallas för en bit (BInary digiT). En byte betyder (vanligtvis) åtta stycken bitar. Med en byte kan \(256 = 2^8 \) olika sorters data lagras. En minnesadress består på moderna datorer (vanligtvis) av \(32\) bitar.
Nu kan vi notera att \(32/8 = 4\) alltså innehållet \(32\) bitar fyra bytes. För så kallade RGB-färger används tre bytes för andelen röd, grön och blå. Ofta används också en fjärde byte till att representera hur genomskinlig en färg är, detta värde brukar kallas för färgens alfavärde. Ett sådant färgsystem kallas för RGBA.
Om vårt tänkta register innehåller icke-negativa heltal i de tre celler som visas, så innehåller cell \(573\) talet \(2\), cell \(574\) talet \(10\) och cell \(575\) talet \(3\). Om cellerna istället innehåller bokstäver, numrerade i ordning, så innehåller cellerna bokstäverna 'b', 'j' och 'c'. Eftersom alla sorters data internt lagras på samma sätt måste ett datorprogram kunna skilja på olika sorters datatyper. Vad är det som ligger i cell \(573\), är det ett heltal, en bokstav, eller någonting annat?
En datatyp anger vilken sorts information ett antal bitar representerar. De mest grundläggande datatyperna är de som används för heltal, decimaltal och logiska värden. Exakt hur olika datatyper representeras binärt varierar. Vi nämner här översiktligt några principer för binär representation.
Det är lätt att förstå hur ett icke-negativt heltal kan lagras med hjälp av \(32\) stycken bitar. Om vi vill tillåta även negativa heltal måste någon bit användas till att ange om talet är positivt eller negativt.
För logiska värden behövs det bara två värden. Det går exempelvis att använda talet \(0\) för falsk och talet \(1\) för sann. Datatypen för logiska värden kallas boolesk efter Georg Boole som uppfann den så kallade booleska algebra. Inom boolesk logik används talet \(1\) för det logiska värdet sann och \(0\) för det logiska värdet falsk.
För att representera decimaltal skrivs talet om så att det delas upp på värdesiffror och en exponent i någon bas. Om basen tio används kan vi göra denna omskrivning av \(130,57\)
\[ 130,57 = 0,\underbrace{13057}_{\text{mantissa}}\cdot 10^\underbrace{3}_{\text{exponent}} \]Värdesiffrorna kallas för mantissa. Ett decimaltal representeras av sin mantissa och tillhörande exponent. Om vi tänker oss en registercell som för enkelhetens skull använder sig av basen tio och som inte hanterar negativa tal, måste vi lagra de två siffersammansättningarna \(13057\) och \(3\). Om vår tänkta minnescell använder tre positioner för mantissa och två för exponentet, skulle talet kunna lagras på följande sätt:
| adress | innehåll | ||||
|---|---|---|---|---|---|
| \(574\) | 1 | 3 | 1 | 0 | 3 |
I vår tänkta minnescell har talet avrundats för att få plats. I en riktig minnescell används binär lagring och både mantissan och exponenten kan vara negativa.
Eftersom decimalkommat alltid "flyter fram" när ett tal skrivs med mantissa och exponent, kallas decimaltal som representeras binärt för flyttal. Notera att mantissan representeras av ett ändligt antal bitar vilket innebär att ett flyttal, till skillnad från ett decimaltal, alltid har ett ändligt antal decimaler.
Förutom datatyper för tal och logik, behövs det datatyper för text. Ett tecken, som 'a', 'Å', '8', eller '€' kan symboliseras av ett heltal och på så vis lagras binärt i en dator. Det finns olika sätt att koda tecken till tal, några kända teckenkodningar är ISO, ASCII och UTF-8.
Text som "Hej!" kan lagras som fyra stycken tecken ('h', 'e', 'j' och '!'') som hänger ihop. Inom programmering kallas en sådan mängd tecken för en textsträng
Datatyper, på YouTube.
En variabel inom programmering har ett namn och ett värde. En variabels värde kan variera. En variabel måste alltid vara av någon datatyp, så att programmet vet hur det ska tolka den binära representationen av variabeln. I vissa programmeringsspråk (exempelvis Java) måste programmeraren ange vilken datatyp en variabel ska vara och vilka variabler som ska användas, detta kallas för att deklarera variabler. I andra programmeringsspråk (exempelvis Python) sköts all hantering av variablers datatyper automatiskt och variabler kan byta datatyp.
Ett datorprogram ger instruktioner till datorn som datorn ska utföra. Det finns tre grundläggande strukturer som kontrollerar vad det är som ska göras, dessa kallas för kontrollstrukturer. De tre grundläggande strukturerna är sekvens, selektion och upprepning.
En sekvens är en följd av kommandon som utförs i ordningen uppifrån ner.
En selektion innebär att olika saker ska utföras beroende på den situation som råder. En selektion kan också kallas för alternativ. För att avgöra vilken situation som råder används så kallade villkor. Ett villkor är antingen sant eller falskt. Den enklaste selektionen kan beskrivas som:
En selektion kan också innehålla en förgrening,
eller ett godtyckligt antal förgreningar.
En selektion kan också kallas för en villkorssats.
En iteration är en upprepning. Att upprepa någonting kallas inom programmering för att iterera.
Det finns olika strukturer för hur många gånger en uppgift ska upprepas. I vissa fall vet man från början hur många iterationer som ska genomföras, exempelvis tio gånger.
I andra fall vill man upprepa någonting minst en gång tills något villkor är uppfyllt.
I andra fall vill man bara iterera om något villkor är uppfyllt och fortsätta så länge villkoret är uppfyllt.
Det är vanligt att ordet loop används för en iteration. Om man repeterar beroende på något villkor, och om detta villkor aldrig förändras, får man en oändlig loop, dvs programmet slutar aldrig.
Med program som är händelsestyrda kan användaren bestämma vad som ska hända genom att klicka med datormusen, peka på en pekskärm eller genom att trycka ner någon tangent. När användaren gör något sådant, skapas en så kallad händelse (event på engelska) som innehåller information om händelsen, exempelvis vilken tangent som tryckts ner eller var på skärmen det klickats. Som programmerare kan man programmera kod som hanterar händelser.
Det finns andra händelser än musklickningar och tangenttryckningar. Inom webbprogrammering finns det exempelvis händelser för att användaren scrollar ner längs en hemsida eller ändrar storlek på fönstret, med mera.
En funktion inom programmering kan också kallas för en metod, en procedur eller en subrutin. Vilket, eller vilka, ord som används beror på programmeringsspråk.
Det finns två sorters funktioner: funktioner som bara utför ett stycke kod och funktioner som både utför ett stycke kod och returnerar ett värde. En funktion som returnerar ett värde påminner om funktioner inom matematiken.
När man programmerar en funktion definierar man någonstans vilken kod funktionen ska utföra. Att använda en funktion kallas för att anropa funktionen.
Funktioner används dels för att man ska slippa skriva exakt samma kod på flera ställen i programmet och dels för att koden blir enklare att förstå om man strukturerar upp den på så vis att detaljer beskrivs separat. I exemplet med att koka en kopp te, skulle man kunna beskriva "att koka vatten" som en funktion. I algoritmen Gör en kopp te anropas funktionen Koka vatten vilken definieras av algoritmen Koka vatten.
Inom matematiken kan man definiera en talföljd rekursivt. För en sådan talföljd definieras varje tal av ett eller flera föregående tal.
Talen i talföljden \( 4, 12, 36, 108, 324 \ldots \) kan definieras av en formel \(a_n = 4\cdot 3^n\) där \(n\) är ett heltal \(\ge 0\). Talföljden kan också definieras rekursivt på följande sätt:
\[ a_n = \begin{cases} 4 &\mbox{ om } n=0 \\ 3\cdot a_{n-1} &\mbox{ om } n > 0 \end{cases} \]För att beräkna \(a_2\) använder vi att \(a_2 = 3\cdot a_1\), vi måste först beräkna \(a_1\).
För att beräkna \(a_1\) använder vi att \(a_1 = 3\cdot a_0 = 3\cdot 4 = 12\).
När vi nu beräknat \(a_1\) kan vi beräkna \(a_2\) och får att \(a_2 = 3\cdot a_1 = 3\cdot 12 = 36\).
Rekursion är vanligt inom programmering och används oftast till andra saker än att beräkna talföljder. När man använder rekursion gör man en funktion som anropar sig själv.
Vi visar en algoritm för en tänkt funktion Talföljd. Funktionen använder sig av ett värde som är ett heltal, talet \(n\). Talet \(n\) är en så kallas parameter till funktionen. När man använder funktionen skickar man in vilket värde \(n\) ska ha. Det värde man skickar in till funktionen kallas för argument. Ofta gör man ingen skillnad på orden parameter och argument. Om du använder dig av antingen ordet argument eller ordet parameter, förstår alla som kan programmera vad det handlar om. Funktionen kan definieras så här:
Talföljd(n)
Om n = 0 :
returnera 4
annars:
returnera 3·Talföljd(n-1)
Om vi nu anropar Talföljd(2) kommer funktionen att anropa Talföljd(1) vilken i sin tur anropar Talföljd(0). Sedan returnerar Talföljd(0) värdet 4 till Talföljd(1) som returnerar 12 till Talföljd(2) som returnerar 36.
När man programmerar rekursion är det viktigt att rekursionen någon gång tar slut, annars fortsätter funktionen att anropa sig själv tills någon sorts felmeddelande genereras eller tills datorn hänger för att minnet har fyllts med rekursionsanrop.
Den lättroade kan roas av att Googla på ordet recursion.
En abstrakt datatyp definierar en mängd data och operationer som kan göras på datan. Operationerna beskrivs av algoritmer, därav ordet abstrakt. En abstrakt datatyp kan implementeras med något programmeringsspråk, dvs man kan skriva kod som hanterar datan och funktioner som utför de operationer som hör till den abstrakta datatypen.
Vi kommer att nämna två abstrakta datatyper, listor och grafer, utan att gå in på de operationer som hör till respektive datatyp.
En lista innehåller ett antal värden som man visuellt tänker sig längs en rad. Vi kallar de värden en lista innehåller för element. Ett listelement kan vara ett enkelt värde, exempelvis ett tal, eller en mängd värden, exempelvis namn, adress och personnummer.
Det finns olika sorters listor. Vi börjar med att beskriva en lista som vi inte kommer att använda senare i kursen, en så kallad länkad lista. Sedan beskriver vi en sorts lista som vi kommer att använda, en indexerad lista.
I en länkad lista innehåller varje element, utom det sista, en länk till nästa element. Det sista elementet länkar till "ingenting". Ingenting betecknas i många programmeringsspråk med ordet null. Vi kan beskriva en länk med en pil.
I en indexerad lista befinner sig varje element i listan på en position som har ett index. Det vanligaste är att den första positionen har index 0 och att man sedan räknar uppåt.
De flesta programmeringsspråk har en datatyp som implementerar en indexerad lista. En sådan datatyp kallas array på engelska. På svenska används ibland ordet lista men eftersom det finns olika sorters listor är en sådan benämning olämplig. Vi kommer att använda benämning indexerad lista eller det engelska ordet array.
Ett listelement kan i sin tur vara en lista. Man kan i regel nästla listor i listor ett godtyckligt antal gånger.
Listor, på YouTube.
Ordet graf kan betyda olika saker i matematiken. I skolan används ordet mestadels i samband med funktionslära, som grafen till en funktion. Inom grafteori består en graf av ett antal noder och ett antal bågar. Grafteori är en del av matematiken som först användes innan det fanns datorer. Inom datavetenskap används grafteori för att beskriva datastrukturer.
Mängden noder brukar betecknas \(V\), efter det engelska ordet vertex. Mängden bågar brukar betecknas \(E\) efter det engelska ordet edge. Att en graf \(G\) består av noder och bågar, brukar skrivas som att \(G = (V, E)\).
Bågarna i en graf kan ha så kallade vikter. Om en graf används för att representera en karta med städer, kan varje nod innehålla en stad och varje båge kan ha avståndet mellan två städer som vikt. Om en graf används för att representera ett tunnelbanenät, kan varje nod innehålla en station och varje båge kan ha restiden i minuter mellan två stationer. En graf vars bågar har vikter, kallas för en viktad graf.
I en sammanhängande graf finns det minst en väg, via bågar och noder, mellan alla noder i grafen. Grafen över städer i och utanför Skåne är inte sammanhängande eftersom det inte finns någon båge mellan någon stad i Skåne och någon stad på Bornholm.
Om en graf ska användas för att representera vägnätet i en stad som har enkelriktade gator, kan man använda en riktad graf. I en riktad graf går en båge bara i en riktning från en nod till en annan. Enkelriktade gator kan beskrivas av en båge som är riktad från en vägkorsning till en annan. Gator som inte är enkelriktade kan representeras av två bågar, en i varje riktning.
En graf sägs innehålla en cykel om man kan gå från en nod, längs bågar och andra noder, tillbaks till den nod man utgick ifrån, på ett sådant sätt att varje båge och varje nod längs vägen bara besöks en gång.
Man kan tala om cykler i både riktade och oriktade grafer. I en riktad graf måste vägen längs bågar följa bågarnas riktning. I grafen över några vägar i Lund finns det många cykler. Man kan lämna varje vägkorsning och via andra vägkorsningar komma tillbaka till startpunkten. I grafen över städer i och utanför Skåne, finns det en cykel med städerna Lund, Malmö och Landskrona som noder, det finns däremot ingen cykel på Bornholm. Om man går från Rønne till Nexø kan man inte komma tillbaka till Rønne igen eftersom bågen bara får användas en gång.
Härnäst ska vi ta upp en sorts grafer som inte innehåller cykler.
Grafer, på YouTube.
Inom grafteori är ett träd är en oriktad graf som är sammanhängande och inte innehåller någon cykel. Eftersom nodernas placering och bågarnas längder inte spelar någon roll när man ritar en graf, kan man rita ett träd på många olika sätt.
Ett träd som inte innehåller någon nod (och ingen båge) sägs vara ett tomt träd. Ett träd som inte är tomt kan alltid ritas upp så att en nod är överst i bilden och resten av noderna och bågarna förgrenar sig nedåt i bilden. Det går att välja vilken nod som helst som den översta noden.
Inom datavetenskap används ofta en datastruktur, som också kallas träd, där hierarkin med att noder kan vara placerade under eller över varandra fås genom att man använder riktade grafer. Den nod som ligger överst kallas rot (jo, träd inom datavetenskap ritas upp-och-ner). De noder som ligger närmast under en nod kallas för nodens barn.
Man kan definiera ett sådant träd rekursivt på följande vis: Ett träd är antingen tomt eller så innehåller det en nod som har barn vilka själva är träd.
En dators filsystem är strukturerat med trädstrukturer. En mapp kan innehålla andra mappar och filer. Varje mapp och fil kan vara en nod i ett träd. Mappar och filer som ligger inuti en mapp, placeras under denna i det uppritade trädet.
Det är inte bara företeelser inom datavetenskap som uppvisar trädstruktur. Man skulle exempelvis kunna beskriva en skola, som har tre stadier, vilka har tre årskurser, vilka har ett antal klasser, vilka har ett antal elever ‐ som ett träd.
Träd, på YouTube.
Träd används inte bara för att representera strukturer som har uppenbara trädliknande hierarkier, som ett filsystem. Träd kan också användas för att lagra data. Om mängden data inte är så stor, fungerar en lista bra men om mängden data är stor, kan det vara bättre att använda ett träd. Det finns också andra datastrukturer som används för att lagra stora mängder data men vi tar bara upp träd i denna kurs.
Ett träd där varje nod har högst två barn kallas för ett binärt träd. Om noderna innehåller data som kan ordnas efter jämförelserna: lika med, större än eller mindre än; kan trädet struktureras som ett binärt sökträd.
För ett binärt sökträd kallas en nods barnnoder för vänsterbarn och högerbarn. Alla noder som ligger i det vänstra underträdet under en nod, innehåller data som är mindre än nodens data. Alla noder som ligger i det högra underträdet under en nod, innehåller data som är större än nodens data. Detta gäller för alla noder i trädet. Om vi tillåter att det binära sökträdet innehåller samma data i flera noder, kan vi använda jämförelsen mindre än eller lika med för det vänstra underträdet.
Ett träds höjd är hur många bågar det är på en väg mellan roten och någon nod längst ner i trädet
Beroende på hur man sätter in data i ett binärt sökträd, kan man få träd som har olika höjd.
Ett träd som har minimal höjd sägs vara välbalanserat. Det finns kända algoritmer som ser till att ett träd hela tiden är välbalanserat.
Vad är det då som gör ett binärt sökträd bra för lagring av stora mängder data? Jo, det går snabbt att söka efter data i ett binärt sökträd. För att visa exempel på detta måste vi först förklara hur ordet snabbt ska tolkas
Träd, på YouTube.
När man mäter hur snabb en algoritm är kan man inte mäta hur lång tid det tar att köra ett program som implementerar algoritmen, datorer är olika snabba. Istället för att mäta tid, väljer man ut den operation som utförs flest gånger, den så kallade karakteristiska operationen, sedan räknar man hur många gånger denna utförs. Antalet gånger den karakteristiska operationen utförs är ett mått på hur snabb en algoritm är. Detta mått anger en algoritms tidskomplexitet.
För att åskådliggöra begreppet tidskomplexitet, jämför vi en sökning i en lista med en sökning i ett binärt sökträd. Vi antar att 15 tal är lagrade dels i en lista och dels i ett välbalanserat binärt sökträd och så vill vi ta reda om ett givet tal finns med i listan respektive trädet. En mer intressant situation hade varit att namn på personer var lagrade och att sökningen handlat om att leta upp någons telefonnummer. Principen är dock densamma oavsett vilken data det handlar om, tal, persondata eller annan data.
För att undvika ren tur, att det tal vi söker efter är först i listan eller överst i trädet, använder vi en värsta-falls-situation, vi väljer att söka efter ett tal som inte finns med i varken listan eller trädet.
Listan kan se ut så här:
Ett välbalanserat binärt sökträd kan se ut så här:
Nu vill vi söka efter talet \(25\).
Med listan jämför vi \(25\) med det första talet \(30\). Eftersom \(25 \ne 30 \) går vi vidare och jämför med det andra talet. Efter \(15\) jämförelser kan vi konstatera att \(25\) inte är med i listan.
Med det binära sökträdet jämför vi \(25\) med roten och konstaterar att \(25 \ne 53 \). Vi konstaterar också att \(25 < 53\) så vi fortsätter sökningen i det vänstra underträdet. Vi jämför \(25\) med \(22\) och eftersom \(25 > 22\) fortsätter vi neråt åt höger. Vi jämför \(25\) med \(30\) och eftersom \(25 < 30\) fortsätter vi neråt åt vänster. Vi jämför slutligen \(25\) med \(29\) och eftersom det inte går att fortsätta längre ner konstaterar vi att \(25\) inte är med i trädet. Det har tagit \(4\) jämförelser att konstatera detta.
Nu spelar det inte någon större roll om ett program måste utföra \(15\) eller \(4\) stycken jämförelser. Skillnaden i snabbhet blir dock stor för stora mängder data. Ett binärt sökträd med höjden \(3\) kan högst innehålla \(2^4-1 = 15\) noder och en sökning behöver högst \(4\) jämförelser. Ett binärt sökträd med höjden \(20\) kan innehålla högst \(2^{21} -1= 2\,097\,151\) noder och en sökning behöver högst \(20\) jämförelser. Om en lista används i detta fall krävs det \( 2\,097\,151\) jämförelser i värsta fall. När vi nu jämför \(20\) med \( 2\,097\,151\) ser vi att skillnaden i snabbhet är påtaglig.
Vi låter \(n\) beteckna hur många tal som är lagrade. Att göra en sökning på \(n\) stycken tal kräver i värsta fall \(n\) jämförelser om en lista används. För enkelhetens skull antar vi att \(n=2^k-1\) för något heltal \(k\). En sökning med ett binärt sökträd kräver då i värsta fall \(k-1\) jämförelser. När man mäter tidskomplexitet är man inte intresserad av exakta uttryck, istället försöker man beskriva ett ungefärligt uppförande. Vi kan därför säga att om indatan har storleken \(n\) så tar sökning med lista ungefär \(n\) tid och sökning med binärt sökträd ungefär \(\log_2n\) tid. (För en beskrivning av vad som här menas med ungefär, Googla på det svenska ordet ordo eller de engelska orden big O notation.)
Logaritmen av ett tal \(a\) i basen \(10\) är det tal \(10\) måste upphöjas till för att bli \(a\). Denna logaritm skrivs som \(\log_{10}a\). Exempelvis är
\[ \begin{align} \log_{10}1000 &= 3 \;\mbox{ eftersom } 10^3 = 1000 \\ \log_{10} 1 &= 0 \;\mbox{ eftersom } 10^{0} = 1 \\ \log_{10}0,1 &= -1 \;\mbox{ eftersom } 10^{-1} = 0,1 \end{align} \]Logaritmen av ett tal \(a\) i basen \(2\) är det tal \(2\) måste upphöjas till för att bli \(a\). Denna logaritm skrivs som \(\log_2 a\). Exempelvis är
\[ \begin{align} \log_2 16 &= 4 \;\mbox{ eftersom } 2^4 = 16 \\ \log_2 1 &= 0 \;\mbox{ eftersom } 2^{0} = 1 \\ \log_2 0,5 &= -1 \;\mbox{ eftersom } 2^{-1} = 0,5 \end{align} \]Inom datavetenskap används oftast basen \(2\).
Logaritmen i basen \(2\) av ett stort tal är ungefär hur många gånger du kan dela talet med två innan du kommer ner till ett.
Skillnaden mellan en linjär och en logaritmisk funktion kan åskådliggöras med grafer. En logaritmisk funktion växer extremt långsamt. En algoritm vars tidskomplexitet har ett logaritmiskt uppförande är en mycket snabb algoritm.
Kryptering brukar åskådliggöras med att Alice och Bob vill skicka meddelanden till varandra men någonstans på vägen finns det ett tjuvlyssnande öra som snappar upp de meddelanden som skickas. För att undvika att tjuvlyssnaren förstår kommunikationen, krypteras alla meddelanden.
Ett av de enklaste sätten att kryptera ett meddelande är att byta varje bokstav mot den bokstav som exempelvis är tre platser längre fram i alfabetet ‐ bokstaven A krypteras till D och bokstaven Ö krypteras till C, osv. Denna sorts kryptering kallas ibland för Ceasarkrypto eftersom Julius Ceasar lär ha använt den.
Vi kan göra det lite mer komplicerat genom att slumptalsgenerera vad varje bokstav ska bytas till.
Om Alice använder den slumpade tabellen för att kryptera ett meddelande måste Bob ha tillgång till samma tabell för att dekryptera meddelanden. Det tjuvlyssnande örat kan inte dekryptera meddelandet direkt men det är tämligen enkelt att lista ut hur tabellen ser. Om tjuvlyssnaren har tillgång till statistik kring det språk som används, och vet vilka bokstäver som är vanligast, är det en relativt enkel gissningslek att återskapa tabellen.
För att göra krypteringen mer komplicerad, skulle man kunna använda samma princip som de så kallade Enigma-maskinerna använde.
Enigma-maskiner användes under andra världskriget av tyskarna både till att kryptera och att dekryptera meddelanden. En Enigma-maskin innehöll bland annat ett tangentbord. Den som krypterade skrev ett meddelande på tangentbordet och för varje bokstav som trycktes ner på tangentbordet skrevs det ut en annan bokstav på ett till synes slumpmässigt sätt. Det som gjorde Enigma-maskinerna så intrikat svåra att knäcka var att om man tryckte ner bokstaven A två gånger, producerades två olika bokstäver. Det genererades alltså nya slumpmässiga bokstäver varje gång en tangent trycktes ner. Hur de slumpmässiga bokstäverna genererades berodde på vilken inställning maskinen hade. För att dekryptera ett meddelande kräves det en annan Enigma-maskin med exakt samma inställning. De inställningar som skulle användas av Enigma-maskinerna schemalades så att de som skulle dekryptera ett meddelande visste vilken inställning som skulle användas exempelvis den tredje juni.
Tack vare Enigma-maskinerna kunde de tyska ubåtarna få information om var det fanns fartyg, framför allt i den engelska kanalen, och på så vis kunde de blockera handel med Storbritannien. I Storbritannien inleddes ett projekt vid Bletchley Park för att knäcka tyskarnas Enigma-kryptering. Deltagarna i projektet vid Bletchley Park lyckades till slut knäcka koden, mestadels tack vare matematikern Alan Turing. Filmen The Imitation Game från 2014 handlar om Turings arbete vid Bletchley Park.
Om du vill se hur en Enigma-maskin fungerar kan du se Simon Singh demonstrera en i World Science Festival: The Enigma Machine Explained på YouTube
Nu tänker vi oss att Alice och Bob båda har tillgång till en Enigma-maskin, så att det avlyssnande örat inte kan gissa sig till hur bokstäverna krypterats. Sedan tänker vi oss att Alice och Bob bara kan kommunicera via datornätverk. När de ska komma överens om vilka inställningar deras maskiner ska använda, måste de kommunicera detta via datornätverk, och därmed får tjuvlyssnaren också reda på inställningarna. Nu behöver tjuvlyssnaren bara en egen Enigma-maskin för att kunna dekryptera alla meddelanden.
Svagheten i såväl en slumpad tabell, som i en Enigma-maskin, är att samma tabell, samma maskin, samma inställningar, används både vid kryptering och dekryptering. Det som används för att kryptera, eller att dekryptera, kallas för en krypteringsnyckel. Kryptering där samma nyckel används både vid kryptering och vid dekryptering kallas för symmetrisk kryptering. Symmetrisk kryptering är inte lämpat för kommunikation via datornätverk eftersom även nyckeln måste skickas via nätverket.
Vid asymmetrisk kryptering används två nycklar, en för att kryptera och en för att dekryptera.
Om Alice vill skicka meddelanden med hjälp av asymmetrisk kryptering skapar hon en privat nyckel som används till dekryptering och en publik nyckel som används för att kryptera. Sedan skickar hon den publika nyckeln till Bob.
Med hjälp av Alice publika nyckel kan Bob kryptera meddelanden som han skickar till Alice. Alice använder sin privata nyckel för att dekryptera de meddelanden hon får från Bob. Tjuvlyssnaren känner till den publika nyckeln men kan inte dekryptera Bobs meddelanden eftersom den privata nyckeln aldrig skickats.
Det finns olika metoder för att generera privata och publika nycklar. En av de mest kända metoderna är RSA-kryptering. Matematiken bakom RSA-kryptering är på för hög nivå för att vi ska gå igenom den här men metoden använder sig av kvot, rest och primtalsfaktorisering. Hela principen bakom RSA-kryptering bygger på att det är lätt för en dator att multiplicera men mycket svårt att faktorisera, om stora primtal används. Om \(p\) och \(q\) är två mycket stora primtal (fler än 100 siffror) är det lätt för en dator att multiplicera dem till produkten \(n = p\cdot q\). Talet \(n\) ingår i den publika nyckeln vid RSA-kryptering men de två primtalen \(p\) och \(q\) ingår i den privata nyckeln. Det finns inte någon känd metod för att faktorisera talet \(n\) inom rimlig tid. Tjuvlyssnaren kan snappa upp talet \(n\), vilken skickas, men kan inte ta reda på \(p\) och \(q\), vilka behövs för att dekryptera meddelanden.
