1. Datoranvändning, matematiska program Aarne Ranta Datorintroduktion 2009, D och DV, Chalmers & GU %!target:html %!postproc(html): #NEW %!postproc(html): #HR

#NEW ==Den här kursen== Introduktion till - datoranvändning - programmering - datavetenskap Utformad för dem som vet och skall veta allra mest om datorer och programmering - D-linjen på Chalmers - DV-linjen på Göteborgs Universitet #NEW ==Webbsidan== Hur hittar man den: från svårast till lättast 0. Navigera i Chalmers studieportal ``` http://www.student.chalmers.se/ ``` 1. Anteckna URL (Uniform Resource Locator) ``` http://www.cs.chalmers.se/~aarne/datorintro/ ``` 2. Googla med ``` datorintroduktion D-linjen Chalmers ``` 3. Googla med läraren ``` Aarne Ranta ``` tryck på "Datorintroduktion" #NEW ==Kursens uppbygnad== Vi går snabbt genom [kurswebbsidan ..], för att förklara - vad man ska lära sig under kursen - hur man ska göra för att klara kursen #NEW ==Datavetenskap== **Datavetenskap** (Computer Science) har sina rötter på två håll: - matematik - elektronik Datavetenskap kan därför se rätt så olika ut beroende på datavetare. #NEW ==Hårdvara och mjukvara== hårdvara = maskinvara, mjukvara = programvara ``` mjukvara användarprogram -- Firefox, emacs, GHC operativsystemet -- Windows, Unix, Symbian ------------------------------------------------------------- hårdvara datorn -- PC, Mac, iPhone, PSP ``` #NEW ==Operativsystemet Unix== Första versionen i 1970 Känns numera under namnen Linux, Mac OS X, SunOS, BSD... Fungerar på alla sorters maskiner Populärt bland professionella programmerare och datavetare - användaren kan lätt programmera systemet - relativt bra säkerhet - "känns rätt" p.g.a. enkelhet, tydlighet, modularitet, ortogonalitet, öppenhet #NEW ==Huvuddelarna i Unix== Kärnan (Eng. kernel): närmast hårdvaran Filsystemet: kataloger och filer Kommandotolken (Eng. shell): närmast användaren Därtill: - drivrutiner - fönstersystem - grafiska gränssnitt #NEW ==Shellkommandon== När man matat in användar-ID och lösenord, kommer man oftast in i ett fönstersystem. Man kan då öppna ett "shell", som kan heta "terminal", "konsole", "xterm", "cygwin", etc. I shellen kör vi följande kommandon (vart och ett efter prompten ``$``): ``` $ whoami -- visa mitt användarnamn $ pwd -- print working directory $ ls -- lista innehållet i biblioteket $ mkdir datorintro -- skapa bibliotek för kursen $ cd datorintro -- gå till det nya biblioteket ``` För mera information: see Unix-kompendiet (kommer snart) #NEW ==Emacs== En texteditor som är många programmerares favorit. Speciellt lämpligt för att skriva programkod i. Kan öppnas från shellet med kommandot ``emacs``, eller eventuellt från en meny i "applications" eller motsvarande. Från shellet: ``` $ emacs MyProgram.hs -- öppna filen MyProgram.hs i emacs-editorn ``` #NEW ==Programspråk i vår utbildningar== Vi lär ut Haskell först Senare lär vi Java, C, assembler Och ännu lägre: datorarkitektur, kretselektronik... Och ännu högre: matematiska modeller av beräkning Och bryggan mellan nivåer: **kompilatorer** #NEW ==Kompilatorn== Kompilatorn är ett program som automatiskt översätter högnivåspråk till maskinspråk. Det är därför programmerarna (oftast) kan hålla sig till högnivåspråk. Det är därför samma program kan köras på olika sorters datorer. #NEW ==GHC(i)== GHC = Glasgow Haskell Compiler GHCi = GHC Interactive Vi kommer att - skriva Haskell-program - kompilera dem med GHCi - köra dem på datorn GHC(i) finns för Linux, Mac, Windows... gratis från [``www.haskell.org/ghc`` www.haskell.org/ghc] #NEW ==Ett sätt att använda GHC(i)== Starta ett GHCi-shell i Unix-shellet och skriva program till prompten ``` $ ghci Prelude> 2+2 4 Prelude> sum [1 .. 100] 5050 ``` Snabbt och effektivt för mycket korta program. Även för att testa längre program. #NEW ==Ett annat sätt att använda GHC(i)== Skriv program i en fil, t.ex. ``MyProgram.hs``, läs in i GHCi, och kör i GHCi ``` Prelude> :l MyProgram.hs MyProgram> factorial 12 479001600 ``` Snabbt för program stora som små, men inte effektivast. Det vi mest använder resten av kursen. Filen ``MyProgram.hs`` kan se ut så här: ``` factorial n = product [1 .. n] ``` #NEW ==Funktionell programmering== Haskell är ett **funktionellt programspråk** Köra ett program = beräkna värdet av en funktion med givna argument Exempel från matematik: //f : R -> R// //f(x) = (x + 1)(x - 1)// //f(3.1) = 8.61// (Ungefär) samma exempel i Haskell: ``` f :: Float -> Float f x = (x + 1) * (x - 1) MyProgram> f 3.1 8.61 ``` #NEW ==Aritmetiska funktioner i Haskell== Heltal, flyttal: ``Int``, ``Float`` De fyra räknesätten: ``+ - * /`` Potensupphöjning: ``2.7 ^ 6`` Dessa kan kombineras i **uttryck**, där parenteser kan behövas: ``` Prelude> 2 + 3 * 4 14 Prelude> (2 + 3) * 4 20 ``` Nu ska vi sitta ner och göra några beräkningar. #NEW ==Prelude-modulen== GHCi-prompten visar den **modul** vars funktioner är tillgängliga. En modul, som heter ``Prelude`` är alltid tillgänglig. Även om man har laddat in ett annat program, är ``Prelude`` tillgänglig. ``Prelude`` innehåller de flesta funktioner vi behöver på denna kurs, t.ex. de viktigaste matematiska funktionerna. #NEW ==Listor== Hur definierar vi medelvärdet av en lista av tal? Just det: vi behöver en **lista** av tal. Listor kan skrivas på olika sätt: ``` [] [1,2,3} [1 .. 100] [2,4 .. 100] ``` Preludfunktionen ``sum`` tar en lista av tal och returnerar deras summa. Nu: ``` Prelude> sum [1,2,3] / 3 2.0 Prelude> sum [1 .. 100] / 100 50.5 ``` #NEW ==Oändliga listor== En lista kan vara oändlig. ``` Prelude> [1 ..] [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22, 23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41, 42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57Interrupted. ``` Tryck Control-C för att avbryta beräkningen! Kan vi beräkna summan av en oändlig lista? ``` Prelude> sum [1 ..] Prelude> sum [0,0 ..] ``` Dags att sitta ner och experimentera igen. #NEW ==Val från en lista== Hur skriver vi listan av jämna tal mellan 1 och 100? Antingen med med stegning: ``` [2,4 .. 100] ``` eller också med en **listkomprehension**: ``` [x | x <- [1 .. 100], even x] ``` Delarna i listkomprehensionen: - resulterande element: ``x`` - **generator**: ``x <- [1 .. 100]`` - **villkor**: ``even x`` Obs. ``even`` är en funktion som avgör om ett tal är jämnt. Den returnerar ``True`` eller ``False``. #NEW ==Mera val från en lista== Vi ska sitta ner och prova exempel: - listan av alla tal som är udda (``odd``) - listan av alla tal som är mindre än (``<``) 50 - listan av alla tal vars kvadrat är mindre än 200 - listan av alla tal som är lika med (``==``) sig själva #NEW =='Och' och 'eller'== Villkor kan kombineras med ``&&`` ("och") och ``||`` ("eller"). Listan av tal som är mindre än 10 eller större är 90: ``` [x | x <- [1 .. 100], x < 10 || x > 90] ``` #NEW ==Hur många?== Funktionen ``length`` anger en listas **längd** som heltal. ``` Prelude> length [] 0 Prelude> length [2,4 .. 100] 50 Prelude> length [1,1,1] 3 ``` Observera att ``length`` räknar varje etta separat i det tredje exemplet. Hur många tal uder 100 har kvadrat mindre än 500? ``` length [x | x <- [1 .. 100], x * x < 500] ``` #NEW ==Ändra resultatet i listkomprehension== Ta en lista av tal och addera 1 till varje tal; ``` [x + 1 | x <- [1 .. 100]] ``` Ta en lista av tal returnera talens kvadrater: ``` [x * x | x <- [1 .. 100]] ``` Ta en lista av tal och returnera talens fakulteter: ``` [product [1 .. x] | x <- [1 .. 20]] ``` Ta en lista av tal returnera kvadraterna av dem som är udda: ``` [x * x | x <- [1 .. 100], odd x] ``` Nu ska vi verkligen sitta ner och experimentera! #NEW ==Klipp av en lista== Man kan "klippa av" början av en lista, även oändlig, med ``take``: ``` take 5 [1 ..] == [1,2,3,4,5] take 5 [1,2,3] == [1,2,3] ``` Med detta kan man skapa **approximeringar** av en oändlig lista: ``` Prelude> take 10 [1/n | n <- [1 ..]] [1.0,0.5,0.3333333333333333,0.25,0.2,0.16666666666666666, 0.14285714285714285,0.125,0.1111111111111111,0.1] ``` #NEW ==Par och tabeller== Listor är en **datastruktur**: en komplex form av data (jämfört med tal, som är enkla). En annan datastruktur är **par** ``` (1,2) ``` En **tabell** är en lista av par. Här är en tabell av kvadrater: ``` [(x, x * x) | x <- [1 .. 100]] ``` Och, lite mer intressant: av kvadratrötter: ``` [(x, sqrt x) | x <- [1 .. 100]] ``` Låt oss köra några till exempel igen. #NEW ==Delbarhet och faktorering== När ett heltal delas med ett heltal, kan man få kvoten med funktionen ``div`` och resten med ``mod``: ``` Prelude> div 13 5 2 Prelude> mod 13 5 3 ``` Att ett tal //m// är **delbart** med //n// betyder att ``` mod m n == 0 ``` Ett tals **faktorer** är alla de tal som det är delbart med: ``` [n | n <- [1 .. m], mod m n == 0] Prelude> [n | n <- [1 .. 123], mod 123 n == 0] [1,3,41,123] ``` Ett **primtal** har inga andra faktorer än 1 och sig självt. Hur ska vi uttrycka detta i Haskell? Låt oss prova! #NEW ==Ett delbarhetsbibliotek== Beräkna alla primfaktorer av talet 45678. Det här blir risigt, även med listkomprehensioner. Nu är det dags att skriva ett litet **bibliotek**, en fil med användbara funktioner som har att göra med delbarhet: ``` module Prime where divisible m n = mod m n == 0 factors m = [n | n <- [1 .. m], divisible m n] prime m = m > 1 && factors m == [1,m] primeFactors m = [n | n <- factors m, prime n] ``` #NEW ==Primtest och faktortabellen== Vi laddar vårt bibliotek i GHCi: ``` Prelude> :l Prime.hs Prime> primeFactors 45678 [2,3,23,331] ``` Ny uppgift: skriv ut tabellen av alla tal från 1 till 1000 och deras primfaktorer. ``` Prime> [(x,primeFactors x) | x <- [1 .. 1000]] [(1,[]),(2,[2]),(3,[3]),(4,[2]),(5,[5]),(6,[2,3]),(7,[7]), (8,[2]),(9,[3]),(10,[2,5]),(11,[11]),(12,[2,3]),(13,[13]), (14,[2,7]),(15,[3,5]),(16,[2]) ... ``` Obs: vår algoritm för att räkna primfaktorer är långsam: senare kurser ska lära ut bättre algoritmer! #NEW ==Delbarhetsbiblioteket med typer== För att dokumentera vad funktionerna gör anger man med fördel **typsignaturer** till varje funktion: ``` module Prime where divisible :: Int -> Int -> Bool divisible m n = mod m n == 0 factors :: Int -> [Int] factors m = [n | n <- [1 .. m], divisible m n] prime :: Int -> Bool prime m = m > 1 && factors m == [1,m] primeFactors :: Int -> [Int] primeFactors m = [n | n <- factors m, prime n] ``` #NEW ==Tvillingprimtal== Konjektur: Det finns oändligt många //p// sådana att både //p// och //p+2// är primtal. T.ex. 3,5 ; 5,7 ; 11,13 ; 17,19 ; ... Detta har varken bevisats eller motbevisats. Uppgift: Skriv ett Haskell-program som genererar (den oändliga?) listan av alla tvillingprimtal. #NEW ==Uppgifter== ===Format=== Uppgifterna ska redovisas i en fil ``Ex1.hs``, som ser ut så här: ``` module Main where import Prime main = do print ex2 print ex3 print ex4 print ex5 -- definitionerna av ex2, ex3, 3x4, ex5, samt eventuella hjälpfunktioner ``` När man kör kommandot ``` runghc Ex1 ``` skrivs lösningarna på skärmen, rad för rad. Hur ``print`` och ``do`` exakt fungerar kommer att förklaras i Föreläsning 3. #NEW ===Uppgifterna=== 1. Skriv och beräkna ett Haskell-uttryck som anger antalet dagar sedan du föddes. 2. Definiera ett Haskell-uttryck ``ex2``, som genererar tabellen av konverteringar från Fahrenheit till Celsius för Fahrenheit-värdena 0,20,40,...,300 (20 graders stegning). Konversionsformeln är: C = 5(F-32)/9. T.ex. om F=86 är C=30. 3. Hur många primtal finns mellan 0 och 1000 respektive 7000 och 8000? Definiera ett uttryck ``ex3``, som returnerar dessa som ett par. Du får använda filen [``Prime.hs`` Prime.hs] som hjälp. 4. Definiera ett Haskell-uttryck ``twins``, som genererar (den oändliga?) tabellen av alla tvillingprimtal. Du får använda filen [``Prime.hs`` Prime.hs] som hjälp. Definiera sedan ett uttryck ``ex4``, som ger de tio första paren. 5. Skriv en funktion ``geom``, som approximerar den **geometriska serien** ``` 1 + 1/2 + 1/4 + 1/8 + ... + 1/(2^n) + ... ``` med ett heltal ``n`` som argument. Skriv sedan ett uttryck ``ex5``, som ger listan av approksimationerna med ``n = 1,...,10``. #NEW ==Sammanfattning och referens== ===GHCi = Glasgow Haskell Compiler interactive=== Starta GHCi med kommandot ``ghci`` Beräkna värdet av ett uttryck: skriv uttrycket i prompten Ladda en fil: ``:l FILE`` Help: ``:?`` Avbryta beräkning: Control-C Föregående kommando: pil-upp ===Haskell-filer=== **Module-header** följd av eventuella **modulimportdirektiv** följda av **funktionsdefinitioner** med eller utan **typsignaturer**: ``` module Prime where import List divisible :: Int -> Int -> Bool divisible m n = mod m n == 0 -- ingen typsignatur (detta är en kommentar) factors m = [n | n <- [1 .. m], divisible m n] ``` Modulen ``Prime`` ska finnas i filen ``Prime.hs``. Undantag: om modulen heter ``Main`` kan filen heta vad som helst. Varje definition ska börja från början av en rad. Inget annat får placeras i början av en rad (förutom kommentarer). Det finns måga sätt att skapa och modifiera en fil under Unix och andra operativsystem. De flesta dataloger använder **Emacs**. Den kan startas från Unix-shellen med kommandot ``emacs``. Då öppnas ett fönster med menyer för att skapa, öppna och spara filer, osv. ===Typer=== Numeriska typer: - heltal: ``Int``, med positiva och negativa heltal - flyttal ("reella tal"): ``Float`` Sanningsvärden: ``Bool``, med objekten ``True`` och ``False`` Datastrukturer: - listor: ``[a]`` där ``a`` är en typ - par: ``(a,b)``, där ``a`` och ``b`` är typer Funktioner: ``a -> b`` där ``a`` och ``b`` är typer - flerställiga funktioner skrivs som ``a -> b -> c`` ===Uttryck=== **Infixoperatorer**, med parenteser vid behov: ``(2 + 3) * 4 > 15`` **Funktionsapplikationer**: ``divisible 12 4`` Listor: - **listning**: ``[1,2,3]`` - **range**: ``[1 .. 100]``, ``[1 ..]``, ``[1,3 .. 100]`` - **listkomprehension**: ``[x * x | x <- [1 .. 100], even x]`` ===Preludfunktioner=== ``` -- defined for Numeric types (+) :: (Num a) => a -> a -> a (-) :: (Num a) => a -> a -> a (*) :: (Num a) => a -> a -> a (/) :: (Num a) => a -> a -> a (^) :: (Num a) => a -> Int -> a -- a^n är a upphöjt till potens n div :: Int -> Int -> Int mod :: Int -> Int -> Int sqrt :: Float -> Float -- defined for types with Equality (==) :: (Eq a) => a -> a -> Bool (/=) :: (Eq a) => a -> a -> Bool (<) :: (Eq a) => a -> a -> Bool (>) :: (Eq a) => a -> a -> Bool (&&) :: Bool -> Bool -> Bool (||) :: Bool -> Bool -> Bool even :: Int -> Bool odd :: Int -> Bool sum :: (Num a) => [a] -> a product :: (Num a) => [a] -> a length :: [a] -> Int take :: Int -> [a] -> [a] ```