1. Datoranvändning, matematiska program

Aarne Ranta
Datorintroduktion 2009, D och DV, Chalmers & GU

Den här kursen

Introduktion till

Utformad för dem som vet och skall veta allra mest om datorer och programmering

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"

Kursens uppbygnad

Vi går snabbt genom kurswebbsidan, för att förklara

Datavetenskap

Datavetenskap (Computer Science) har sina rötter på två håll:

Datavetenskap kan därför se rätt så olika ut beroende på datavetare.

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

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

Huvuddelarna i Unix

Kärnan (Eng. kernel): närmast hårdvaran

Filsystemet: kataloger och filer

Kommandotolken (Eng. shell): närmast användaren

Därtill:

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)

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

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

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.

GHC(i)

GHC = Glasgow Haskell Compiler

GHCi = GHC Interactive

Vi kommer att

GHC(i) finns för Linux, Mac, Windows... gratis från

www.haskell.org/ghc

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.

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]

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

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.

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.

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

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.

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:

Obs. even är en funktion som avgör om ett tal är jämnt. Den returnerar True eller False.

Mera val från en lista

Vi ska sitta ner och prova exempel:

'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]

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]

Ä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!

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]

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.

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!

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]

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!

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]

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.

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.

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

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:

Sanningsvärden: Bool, med objekten True och False

Datastrukturer:

Funktioner: a -> b där a och b är typer

Uttryck

Infixoperatorer, med parenteser vid behov: (2 + 3) * 4 > 15

Funktionsapplikationer: divisible 12 4

Listor:

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]