LISP och Diskret matematik

Innehållet på den här sidan bygger på kurslitteratur från kursen Datorvetenskapens grunder, 5p (Foundations of Computer Science). Kursen gavs vid Örebro universitet ht 2005 och lärare var Lars Karlsson (http://aass.oru.se/~lkn). Kurslitteraturen var: Eriksson, Kimmo & Gavel, Hillevi (2002). Diskret matematik och diskreta modeller. Studentlitteratur, ISBN/ISSN: 91-44-02465-7 samt artikelmaterial.

LISP (http://www.lisp.org)
Lisp är ett av de första programmeringsspråken och står för List Processing. På kursen används den variant som går under namnet Common-Lisp (CL). Lisp är ett tolkande (interpreterande) språk och fördelen med det är att vi kan exekvera kod utan att första behöva köra koden genom en kompilator eller länkare. Nackdelen (inte bara med Lisp utan även andra tolkande språk) är att det går mycket långsammare än maskinkod. I mjukvaran Allegro Common Lisp som används på kursen finns dock en inbyggd kompilator för den som behöver det.

I Lisp är såväl programkod som data i formen av listor. I Lisp använder vi paranteser för att skriva listor, vilket gör att det lätt blir väldigt många paranteser. Ett öknamn på Lisp som driver med det faktum att det är många paranteser är ”Lots of Irritating Stupid Parantheses”. Utöver det så har Lisp en flexibel men enkel syntax. En annan fördel är att tack vare att programkod och data har samma format kan man göra saker som nära på omöjliga (eller iaf väldigt krångliga) med andra programmeringsspråk. Fler fördelar är att i Lisp kan vi skriva Lisp-program som själva sätter ihop kod, kod som därefter kan exekveras genom ett anrop till Lisp-evaluatorn.

Variabler
Variabler används för att hålla reda på data som kan ändras över tid. En variabel har ett namn (som är en symbol) och ett värde (som kan vara av vilken typ som helst). Variabler deklareras såhär: (defvar var) eller (defvar var x). Ett annat exempel är när vi skriver (defvar width-of-box 45) och får variablens värde genom att skriva variablens namn som ett anrop såhär: width-of-box vilket returnerar 45.

Datatyper (mer ingående nedan)
Symboler i Lisp är teckenföljder som inte kan innehålla mellanslag eller paranteser. T.ex. b, billy-gates, c45. Symboler kan fungera som namn på funktioner eller variabler, men de kan även användas direkt som data. Listor i Lisp består av en sekvens dataelement som skrivs inom en parantes och som separeras med mellanslag. T.ex. (soc gnu), (6 7 8 9), (). Två paranteser utan innehåll kallas för ”tomma listan”. Det går även bra med listor inuti listor; ( (1 2 3 ( 4 5 ) ) ). Tal kan vara heltal såsom 2, -7 eller 78000, decimaltal som 1,61803, bråktal som 40/6 eller 12/3, tal med exponent som 10E+5 (10*105). Strängar, omges av citattecken och kan innehålla nästa vad som helst. T.ex. ”Hello World”, ”5+5 (10)” eller ”Björn Sennbrink”. Andra datatyper är tecken och matriser.

Tal
Det finns många numeriska funktioner i CL:

(numberp x) – testar om x är ett tal. (integer x), (rational x) och (floatp x) – testar om x är ett heltal, bråktal eller decimaltal.

De fyra räknesätten skrivs: addition (+ x y), subtraktion (- x y), multiplikation (* x y) och division (/ x y).

Jämförelser av tal skrivs: ”lika med” (= x y), ”mindre än” (< x y), "större än" (> x y), ”mindre än eller lika med” (<= x y), "större än eller lika med" (>= x y), ”ej lika” (/= x y).

För att addera eller subtrahera 1 används: (1+ x) eller 1- x). För att utröna om ett tal är 0, positivt, negativt, udda eller jämnt används: (zerop x), (plusp x), (minusp x), (oddp x) eller (evenp x). För att returnera det större eller mindre av två eller flera tal används: (max x y) eller (min x y). (abs x) ger absolutvärdet av ett tal. (sqrt x), (expt x y), (log x y) – står för roten av talet, talet x upphöjt i talet y, och y-logaritmen av x. (round x) avrunda bort decimalerna för talet x. T.ex. (round 0.3) => 0 medan (round 0.7) => 1. (tructate x) avrundar alltid nedåt, i riktning mot noll t.ex. ger (tructate 0.8) => 0 och (tructate 1.3) => 1. (mod x y) gör en heltalsdivision av x med y och (rem x y) ger resten av en heltalsdivision av x med y. Pi är en konstant och en konstant är en symbol som har ett värde men till skillnad mot en variabel kan konstantens värde inte ändras.

Strängar & Tecken

Strängar är teckensekvenser som skrivs inom citattecken t.ex. ”hello”. Tecken ser ut som vanliga tecken när de förekommer i strängar, men behöver man skriva ut ett enskilt tecken skriver man #A, #B, #1, #2 osv. För att behandla strängar och tecken i CL används bl.a. de här funktionerna:

(stringp x) – testar om x är en sträng. (string= s1 s2) – testar om två strängar är identiska (lika). (string-equal s1 s2) – testar om två strängar är identiska men gör ingen skillnad på små och stora bokstäver t.ex. ”Hello” och ”hello” anses vara identiska med den senare funktionen. (string< s1 s2), (string> s1 s2), (string>= s1 s2), (string =/ s1 s2) – jämför två strängar baserat på lexikalisk ordning. T.ex. (string< "alfa" "beta") returnerar T. (make-string size) - skapar en ny sträng av en viss storlek (size). (length s) ger längden på en sträng. (concatenate 'string s1 s2) slår ihop två strängar, med s1 första och s2 därefter. T.ex. ger (concatenate 'string "hello" "world"); helloworld. (characterp c) testar om c är ett tecken (jfr. (numberp x) eller (stringp x) som testar om x är ett tal eller en sträng).För att jämföra två tecken används (char= c1 c2), (charc< c1 c2), (charc> c1 c2), (charc<= c1 c2), (charc>= c1 c2) och (charc/= c1 c2).

Matriser
Matriser (eng. arrays) kan användas för att representera t.ex. ett schackbräde. I CL går det att använda matriser av alla storlekar och de är inte begränsade till att innehålla siffor. En sak som behandlats tidigare är strängar som även kan ses som endimensionella matriser. När det kommer till matriser så bör det vara lättare att förstå hur Lisp hänger ihop med matematikens formler. En matris enligt matematisk notation kan se ut såhär:

image003

Men när vi skriver samma matris i Lisp (direkt i Debuggern) ser det ut såhär:

(make-array dimensioner :initial-contents lista-med-innehåll)

(make-array dimensioner :initial-contents lista-med-innehåll)

vilket i det här exemplet blir:

(setq v (make-array ‘(3) :initial-contents ‘(1 2 3)))

Det går även att skriva (setq v (make-array ‘(3) :initial-contents ‘(1 2 3))) som vanligt, spara filen, ladda den och sen anropa den från debuggern. För att få ut innehållet ur en matris används t.ex. anropet (aref v1) vilket returnerar 2. Argumentet :initial-contents i make-array är inget egentligt argument utan ett ncykelord för ett valfritt argument vars värde kommer efter i anropet. Det går däremot inte att strunta i argumentet:

Skriv det här och det blir error:

(setq v (make-array ‘(3) ‘(1 2 3)))

Funktionsanrop
För att något ska hända när vi programmerar i Lisp måste vi använda oss av funktionsanrop. Funktionsanrop i första stycket (+, equal, symbol p) behöver ingen kod för att kunna köras. Vi skriver anropet direkt i debuggern. Själv funktionsnamnet är en symbol som kommer först i funktionsanropet. Vi skriver t.ex. (+ 5 5) och inte (5 + 5). Sifforna i paranteserna kallas för funktionens argument och de är indata till funktionen. Funktionen + returnerar ett tal och andra funktioner returnerar andra saker. Det som returneras kallas för värde. Det finns funktioner som kallas för predikat och dessa returnerar T eller NIL (sant eller falskt). Exempel på predikat är equal och symbol p. T.ex så returnerar (equal x y) T om x och y är samma. Observera att det kan vara förvillande att kalla x och y för värden här eftersom värden är något som en funktion returnerar. Komihåg termen argument. Om (equal x y) och x och y är olika returneras NIL. Samma sak med argument som består av strängar: (equal ”hello” ”world”) ger NIL. För predikatet symbolp returneras T om x är en symbol i följande funktion; (symbolp x).

LISP-evaluatorn

Lisp-evaluatorn är en funktion som tar ett Lisp-uttryck och evaluerar det samt returnerar ett resultat. Evaluatorn arbetar enligt tre principer:

1) Symboler tolkas som variabler. Om x har variabelvärdet 5 så returneras 5.

2) Listor tolkas som kod. T.ex. (+ 5 5) returnerar 10 (5 + 5 = 10). För en vanlig funktion evalueras alla argumenten i ordningsföljd innan funktionsanropet sker. Listan (+ 5 5) tolkas som ett anrop till funktionen + med argumenten 5 och 5. Funktionsanropet returnerar därpå ett värde t.ex. 10. Om listan är ett macro eller en specialform (t.ex. villkorssatsen if och iterationssatser såsom loop) så evalueras parametrarna på ett anpassat vis. T.ex. för specialformen setq så evalueras inte det första argumentet (variabelnamnet), men däremot det andra argumentet (det nya värdet).

3) Allt annat tolkas som sig självt, 5 ger 5 osv.

Användningen av specialformen quote stoppar evalueringen. Detta för att kunna använda symboler och listor som data och undvika att de tolkas som variabler och funktionsanrop. Exempel: {quote b} returnerar symbolen b och {quote 1 2 3} returnerar listan (1 2 3).

Trace

För att följa alla steg när en funktion anropas kan vi använda trace. I Allegro Common-Lisp markerar vi den del av en funktion som vi vill köra trace på. I bildexempel X har vi definierat följande funktion: (defun foo (x) (+ x x)). Om vi skriver (foo 2) i debugfönstret får vi 4 eftersom vi med anropet anger att (x) ska vara 2: (+ 2 2) = 4 = (2 + 2). För att köra trace markerar vi + och trycker därefter på F8. Vi går vidare ner till debuggern och skriver (foo 2) som vanligt. Som du ser i bildexempel X så ges vi nu information om alla steg i funktionsanropet.

In- och utmatning

Det finns en uppsjö av funktioner för in- och utmatning till filer t.ex. (princ data) som skriver ut data på skärmen. Skriv (princ ”hello”) i debuggern och ”hello” returneras. (terpri) ger en radbrytning.

Listor

Styrsatser i LISP

progn, if, case, dotimes mm.

Definiera egna funktioner i LISP

LISP-länkar

Mängdlära

* En mängd bestäms enbart av vilka element som är med. Ordningen spelar ingen roll, inte heller om t.ex. elementet c förekommer flera gånger, det räknas iallafall bara som ett element. Exempel: A = { b, a, c, c } innehåller elementen a, b och c.

* Mängder kan innehålla andra mängder. Exempel: { a } tillhör { {a} {b} }. Däremot så tillhör inte ”a” exempelmängden ovan.

* Viktiga begrepp och symboler är; tomma mängden, universum, A delmängd till B, snittet, differensen, komplementet (alla element i universum som inte tillhör ex. mängd A), kardinalitet.

* Räkneregler, återkommande i logik och boolesk algebra.

* Mängders storlek: |A| + |B| = |AUB| + |A∩B|

* Delmängder: Om A är en delmängd till B och B är en delmängd till C så är A en delmängd till C, vilket är en transitiv relation.

* Potensmängder är alla delmängder till ex. mängd A.

* Par: A x B, ta ett element från A och ett element från B osv. och bilda par.

* Om två mängder är lika stora. Bijektioner – parar ihop tal. Undersök skillnad mot parbildningen.

* Standardmängder. Symbolerna för positiva heltal Z+, naturliga tal N, heltal (positiva och negativa) Z, bråktal Q, reella tal R.

Artimetik

* Heltalsdivision med kvot (p) och rest (q). Delar man 17 med 6 får man kvoten 2 och resten 5. Detta eftersom en heltalsdivision inte tillåter decimaltal (17/6 är annars = 2.83333…).

* Talbaser

– När man skriver ett tal som 34567 är det underförstått att talet är givet i talbasen 10. 34567 kan utläsas som 3*10000+4*1000+5*100+6*10+7*1, alternativt som; 3*104+4*103+5*102+6*101+7*100. Talbasen 10 är standard i västvärlden idag men det inget som säger att 10 är särskilt bättre än andra talsystem. Detta talsystem kallas för det decimala.

– Det binära talsystemet, används i datorer och använder 1 och 0 samt talbasen 2. Det är här konverteringen från ett talsystem till ett annat kommer in.

Anta att vi har ett binärt tal t.ex. 1001101 och vill ta reda på vad sifferkombinationen är i decimal form. Börja med att komma ihåg att det binära talsystemet har talbas 2. Fortsätt med steg två, som är att tilldela exponenter till varje del av 1001101, vilket ger oss ett utgångsläge (se bild nedan):

Omvandling av värden från t.ex. decimal form till binär eller från binär till hexadecimal

Det decimala talet 2005 till binär form med hjälp av divisions-algoritmen:

2005 = 2 * 1002 + 1

1002 = 2 * 501 + 0

501 = 2 * 250 + 1

250 = 2 * 125 + 0

125 = 2 * 62 + 1

62 = 2 * 31 + 0

31 = 2 * 15 + 1

15 = 2 * 7 + 1

7 = 2 * 3 + 1

3 = 2 * 1 + 1

1 = 2 * 0 + 1 och när vi läser ut det, nerifrån och upp, får vi: 11111010101

Det binära talet 101010 till decimal form:

1*2^5 + 0*2^4 + 1*2^3 + 0*2^2 + 1*2^1 + 0*2^0

32 + 0 + 8 + 0 + 2 = 42

Det decimala talet 2005 till oktal form:

2005 = 8 * 250 + 5

250 = 8 * 31 + 2

31 = 8 * 3 + 7

3 = 8 * 0 + 3 vilket ger 3725

Det hexadecimala talet 1977 till decimal form 6519

1*16^3 + 9*16^2 + 7*16^1 + 7*16^0

4096 + 2304 + 112 + 7 = 6519

Det oktala talet 105 till decimal form

1*8^2 + 0*8^5 + 5*8^0 =

64 + 0 + 5

Det hexadecimala talet 5BE till decimal form =

5BE16 = 5*16^2 + 11*16^1 + 14*16^0 = 5*256 + 11*16 + 14 * 0 = 20656

Mer i boken.

Se även separat sida om talbaser (länk).

* Delare d|m och får q = 0.

* Primtal (används vid kryptering). Delbara med 1 eller -1 eller sig själva. Exempelvis är 2 ett primtal för att du kan bara dela det med 2 (eller -2) eller 1 och få en heltalskvot. 4 är inte ett primtal för det kan delas med 2 vilket iofs ger en heltalskvot, men som ändå är fel i sammanhanget.

* Primfaktorisera – Delargraf – Det finns 1 unikt sätt att primfaktorisera.

* Det finns ett oändligt antal primtal. Se lista (Länk till 10000 minsta primtal).

* Moduloaritmetik. 6 + 6 = 0 (modulo 12). Mer i boken.

Rekursion & Induktion

* Rekursiva definitioner

* Reguljärt uttryck (r. u.):

– Mer i anteckningarna -EJ KLAR

* Induktionsbevis – Rörigt- Mer i anteckningarna – Ej Klar.

Sannolikheter

* Likformig fördelning av utfall – Alla utfall har samma sannolikhet

* Händelse = Mängd av utfall

* Komplementhändelse

* Sannolikheten (P) för Ac = 1 – P(A).

* Addistionsprincipen, för disjunkta utfall (Två utfall kan inte inträffa samtidigt) (undantag om man t.ex. kastar 2 tärningar, se nedan).

* Multiplikationsprincipen, för oberoende utfall eller händelser. Ex. kast med två tärningar.

Kombinatorik

Additionsprincipen

Multiplikationsprincipen

Permutationer

Ordnat urval

Oordnat urval

Relationer & Funktioner

Relationer

Egenskaper: Reflexiv (på samma plats), Symmetriskt (bredvid), Anti-Symmetriskt (under), Transitivt (under).

Ekvivalensrelation: R + S + T

Partialordning: R + A-S + T

Funktioner

Mer i anteckningar

Grafer

* Noder ihopsatta med bågar

– Definitioner att kunna? Väg, stig, vandring, cykel, krets.

* Enkla eller multigrafer

* Riktade och oriktade grafer

* Hamiltonstig/cykel – Stig/cykel när vi besöker varje nod exakt en gång.

* Eulerväg/krets – …bseöker varje båge exakt en gång.

* Eulerkrets finns om grafen är sammanhängande och varje nod måste ha en jämn grad (båge?).

* Träd: Graf utan cykler.