MAT1030 – Diskret matematikk Forelesning 1: Algoritmer, pseudokoder og kontrollstrukturer Dag Normann

(1)

MAT1030 – Diskret matematikk

Forelesning 1: Algoritmer, pseudokoder og kontrollstrukturer

Dag Normann

Matematisk Institutt, Universitetet i Oslo

14. januar 2008

(2)

Vi som skal undervise

Dag Normann Roger Antonsen Christian Schaal

Robin Bjørnetun Jacobsen

http://www.uio.no/studier/emner/matnat/math/MAT1030/v08/

MAT1030 – Diskret matematikk 14. januar 2008 2

(3)

Vi som skal undervise

Dag Normann

Roger Antonsen Christian Schaal

(4)

Vi som skal undervise

Dag Normann Roger Antonsen

Christian Schaal

(5)

Vi som skal undervise

(6)

Vi som skal undervise

(7)

Hva er diskret matematikk?

Diskret matematikk er et samlebegrep for matematikk hvor kontinuitet, geometri eller algebra ikke spiller noen stor rolle.

Diskret matematikk er matematikken tilpasset en digital verden, mens mye annen matematikk er tilpasset en analog verden.

I MAT1030 skal vi ta for oss temaer som er relevante for en

grunnleggende forst˚aelse av bruk av, og virkem˚ate til, datamaskiner.

(8)

Hva er diskret matematikk?

(9)

Hva er diskret matematikk?

(10)

Hva er diskret matematikk?

(11)

Hva er innholdet i MAT1030?

Algoritmer: Hva og hvordan. Representasjon av tall.

Hvordan representeres tall og i en datamaskin. Logikk:

Relevans for informatikk.

Innføring i utsagnslogikk (Boolesk logikk). Litt om bevisteknikker.

(12)

Hva er innholdet i MAT1030?

Algoritmer: Hva og hvordan.

Representasjon av tall.

(13)

Hva er innholdet i MAT1030?

(14)

Hva er innholdet i MAT1030?

Hvordan representeres tall og i en datamaskin.

Logikk:

(15)

Hva er innholdet i MAT1030?

Logikk:

(16)

Hva er innholdet i MAT1030?

Logikk:

(17)

Hva er innholdet i MAT1030?

Logikk:

Innføring i utsagnslogikk (Boolesk logikk).

Litt om bevisteknikker.

(18)

Hva er innholdet i MAT1030?

Logikk:

Innføring i utsagnslogikk (Boolesk logikk).

Litt om bevisteknikker.

(19)

Mengdelære:

Grunnleggende begreper Relasjoner.

Funksjoner.

Induksjon og rekursjon. Kombinatorikk.

Grafteori med anvendelser. Litt om trær.

Kompleksitet av algoritmer.

(20)

Mengdelære:

Grunnleggende begreper

Relasjoner. Funksjoner.

(21)

Mengdelære:

Funksjoner.

(22)

Mengdelære:

Funksjoner.

(23)

Mengdelære:

Funksjoner.

Induksjon og rekursjon.

Kombinatorikk.

(24)

Mengdelære:

Funksjoner.

Kombinatorikk.

(25)

Mengdelære:

Funksjoner.

Kombinatorikk.

Grafteori med anvendelser.

Litt om trær.

(26)

Mengdelære:

Funksjoner.

Kombinatorikk.

Litt om trær.

(27)

Mengdelære:

Funksjoner.

Kombinatorikk.

Litt om trær.

(28)

Hva legger vi vekt p˚ a?

Hvilken relevans har dette stoffet for studier i informatikk? Hvordan kan vi finne algoritmer for ˚a løse de problemene som presenterer seg?

Vi kommer til ˚a arbeide med algoritmer i tilknytning til logikk i større grad enn det boka gjør, og vi vil utvikle en del ekstra undervisningsmateriale underveis.

(29)

Hva legger vi vekt p˚ a?

Hvilken relevans har dette stoffet for studier i informatikk?

Hvordan kan vi finne algoritmer for ˚a løse de problemene som presenterer seg?

(30)

Hva legger vi vekt p˚ a?

(31)

Hva legger vi vekt p˚ a?

(32)

Før vi begynner

MAT1030 er under omlegging, og vi trenger en kontinuerlig tlbakemelding p˚a ˚arets opplegg.

Vi trenger to eller flere kontaktpersoner vi kan ha møter med gjennom semesteret.

Vi skal gjennomføre en emneevaluering i samarbeid med kontaktpersonene.

Valg av kontaktpersoner finner sted neste onsdag.

(33)

Før vi begynner

(34)

Før vi begynner

(35)

Før vi begynner

(36)

Før vi begynner

(37)

Noen viktige datoer

29.02.2008: Innlevering av Oblig 1. 25.04.2008: Innlevering av Oblig 2. 10.06.2008, 09.00 - 12.00: Eksamen.

(38)

Noen viktige datoer

29.02.2008: Innlevering av Oblig 1.

25.04.2008: Innlevering av Oblig 2. 10.06.2008, 09.00 - 12.00: Eksamen.

(39)

Noen viktige datoer

10.06.2008, 09.00 - 12.00: Eksamen.

(40)

Noen viktige datoer

10.06.2008, 09.00 - 12.00: Eksamen.

(41)

Viktig informasjon til alle studenter

Husk:

1. februar er siste frist for:

• betaling av semesteravgift

• semesterregistrering

• melding til eksamen

• å søke om tilrettelegging ved eksamen

Dersom du har gjort alt riktig skal det se slik ut i studentweb:

Dersom det ikke står ”Vår 2008” under henholdsvis ”Betalt semesteravgift” og ”Semesterregistrert” risikerer du å ikke få ta eksamen og å miste din studierett.

Har du problemer, ta kontakt med MN studieinfosenter i Vilhelm Bjerknes’ hus FØR 1. februar.

Telefon: 22 85 63 44 e-post: [email protected]

(42)

ALGORITMER

En algoritme er en oppskrift som forteller oss hvordan vi skritt for skritt skal kunne oppn˚a et resultat eller løse et problem.

Eksempler p˚a algoritmer kan være:

Kakeoppskrifter.

Automatisk innsjekking p˚a fly.

Beskrivelsen av hvordan man utfører divisjon mellom flersifrede tall. Oppskrift p˚a hvordan man løser opp parenteser og trekker sammen flerleddede uttrykk i algebra.

(43)

ALGORITMER

Kakeoppskrifter.

(44)

ALGORITMER

Kakeoppskrifter.

(45)

ALGORITMER

Kakeoppskrifter.

(46)

ALGORITMER

Kakeoppskrifter.

(47)

ALGORITMER

Kakeoppskrifter.

Beskrivelsen av hvordan man utfører divisjon mellom flersifrede tall.

Oppskrift p˚a hvordan man løser opp parenteser og trekker sammen flerleddede uttrykk i algebra.

(48)

ALGORITMER

Kakeoppskrifter.

Beskrivelsen av hvordan man utfører divisjon mellom flersifrede tall.

Oppskrift p˚a hvordan man løser opp parenteser og trekker sammen flerleddede uttrykk i algebra.

(49)

Algoritmer

Hva er det som kjennetegner en algoritme?

Det skal ikke kreves intelligens eller forst˚aelse for ˚a følge den.

Du skal ikke kunne kjemi for ˚a bake en kake.

Du skal kunne sjekke inn p˚a fly selv om du har teknologifobi. Det er ikke nødvendig ˚a forst˚a hva man gjør n˚ar man utfører en divisjon, regnetrening er det som trengs.

Mange lærer seg hvordan de kan løse oppgaver i skolealgebra, uten ˚a ha peiling p˚a hva de egentlig driver med.

(50)

Algoritmer

(51)

Algoritmer

(52)

Algoritmer

Du skal kunne sjekke inn p˚a fly selv om du har teknologifobi.

Det er ikke nødvendig ˚a forst˚a hva man gjør n˚ar man utfører en divisjon, regnetrening er det som trengs.

(53)

Algoritmer

(54)

Algoritmer

(55)

Algoritmer

Vi skal fokusere p˚a algoritmer som

- beregner funksjoner

- avgjør om et objekt eller en datamengde har en gitt egenskap eller ikke

- organiserer gitte data p˚a en ønsket m˚ate (eksempelvis ordner dataene) - utfører andre oppgaver i tilknytning til matematikk eller informatikk

som vi ønsker ˚a kunne f˚a utført.

(56)

Algoritmer

Vi skal fokusere p˚a algoritmer som - beregner funksjoner

(57)

Algoritmer

(58)

Algoritmer

- organiserer gitte data p˚a en ønsket m˚ate (eksempelvis ordner dataene)

- utfører andre oppgaver i tilknytning til matematikk eller informatikk som vi ønsker ˚a kunne f˚a utført.

(59)

Algoritmer

(60)

Algoritmer

Hvem ønsker vi ˚a kommunisere algoritmen til, og hvordan skal det gjøres?

1. Kakebakere, flypassasjerer og liknende.

2. Skolebarn/ungdom og studenter som skal lære matematikk. 3. Teknisk kyndige medmennesker som skal “forst˚a” algoritmen. 4. Datamaskiner som skal utføre algoritmen for oss.

I MAT1030 er gruppe 3 den mest aktuelle.

(61)

Algoritmer

2. Skolebarn/ungdom og studenter som skal lære matematikk. 3. Teknisk kyndige medmennesker som skal “forst˚a” algoritmen. 4. Datamaskiner som skal utføre algoritmen for oss.

(62)

Algoritmer

2. Skolebarn/ungdom og studenter som skal lære matematikk.

3. Teknisk kyndige medmennesker som skal “forst˚a” algoritmen. 4. Datamaskiner som skal utføre algoritmen for oss.

(63)

Algoritmer

3. Teknisk kyndige medmennesker som skal “forst˚a” algoritmen.

4. Datamaskiner som skal utføre algoritmen for oss. I MAT1030 er gruppe 3 den mest aktuelle.

(64)

Algoritmer

4. Datamaskiner som skal utføre algoritmen for oss.

(65)

Algoritmer

4. Datamaskiner som skal utføre algoritmen for oss.

(66)

PSEUDOKODER

En pseudokode er en m˚ate ˚a beskrive en algoritme p ˚a.

Pseudokoden beskriver hvordan algoritmen kan følges trinn for trinn. En pseudokode formuleres i et spr˚ak som er mer teknisk enn naturlige spr˚ak og mindre teknisk enn programmeringsspr˚ak.

Vi skal bruke pseudokoder p˚a samme m˚ate som i læreboka.

Man m˚a se eksempler, og øve, for ˚a bli flink til ˚a skrive pseudokoder.

(67)

PSEUDOKODER

Pseudokoden beskriver hvordan algoritmen kan følges trinn for trinn. En pseudokode formuleres i et spr˚ak som er mer teknisk enn naturlige spr˚ak og mindre teknisk enn programmeringsspr˚ak.

(68)

PSEUDOKODER

Pseudokoden beskriver hvordan algoritmen kan følges trinn for trinn.

En pseudokode formuleres i et spr˚ak som er mer teknisk enn naturlige spr˚ak og mindre teknisk enn programmeringsspr˚ak.

(69)

PSEUDOKODER

(70)

PSEUDOKODER

(71)

PSEUDOKODER

(72)

Pseudokoder

Eksempel (Areal av trekant)

1. Inputh [h er høyden i trekanten.]

2. Inputg [g er lengden p˚a grunnlinjen i trekanten.] 3. areal ← ^h·g₂

4. Output areal

(73)

Pseudokoder

4. Output areal

(74)

Pseudokoder

4. Output areal

(75)

Pseudokoder

2. Inputg [g er lengden p˚a grunnlinjen i trekanten.]

3. areal ← ^h·g₂ 4. Output areal

(76)

Pseudokoder

3. areal ← ^h·g₂

4. Output areal

(77)

Pseudokoder

3. areal ← ^h·g₂ 4. Output areal

(78)

Pseudokoder

Vi kunne ha skrevet en annen pseudokode for ˚a beregne det samme: Eksempel

1. Inputh 2. Inputg 3. areal ←h·g 4. areal ← ^areal₂ 5. Output areal

(79)

Pseudokoder

Vi kunne ha skrevet en annen pseudokode for ˚a beregne det samme:

Eksempel

1. Inputh 2. Inputg 3. areal ←h·g 4. areal ← ^areal₂ 5. Output areal

(80)

Pseudokoder

Eksempel 1. Inputh

2. Inputg 3. areal ←h·g 4. areal ← ^areal₂ 5. Output areal

(81)

Pseudokoder

Eksempel 1. Inputh 2. Inputg

3. areal ←h·g 4. areal ← ^areal₂ 5. Output areal

(82)

Pseudokoder

Eksempel 1. Inputh 2. Inputg 3. areal ←h·g

4. areal ← ^areal₂ 5. Output areal

(83)

Pseudokoder

Eksempel 1. Inputh 2. Inputg 3. areal ←h·g 4. areal ← ^areal₂

5. Output areal

(84)

Pseudokoder

Eksempel 1. Inputh 2. Inputg 3. areal ←h·g 4. areal ← ^areal₂ 5. Output areal

(85)

Pseudokoder

S˚a langt best˚ar en pseudokode av en nummerert listeinstruksjonerhvor hver instruksjon har et av følgende tre formater:

Gi en input-verdi til en variabel.

Gi en variabel en ny verdi, som en funksjon av de eksisterende verdiene p˚a variablene.

Gi verdien til en av variablene som output, det vil si resultatet av algoritmen.

Vi kan bruke hva vi vil som variable, eksempelvis er h,g og areal variablene i pseudokodene vi har sett p˚a.

(86)

Pseudokoder

(87)

Pseudokoder

(88)

Pseudokoder

(89)

Pseudokoder

(90)

Pseudokoder

(91)

Pseudokoder

Hvis vi skal beregne verdien av en formel for areal, volum, hastighet etter en viss tids fritt fall og liknende, kan vi bruke pseudokoder slik vi har sett dem til n˚a.

Det finnes imidlertid algoritmer, og tilhørende kontrollstrukturer, for ˚a beregne

- |x|fra x - n! fra n

- Ledd nummer n i Fibonacci-følgen

1,1,2,3,5,8,13,21, . . . .

og for ˚a undersøke om

- Parentesene i et algebraisk uttrykk er satt p˚a lovlig m˚ate - Et naturlig tall er et primtall

(92)

Pseudokoder

- |x|fra x - n! fran

1,1,2,3,5,8,13,21, . . . . og for ˚a undersøke om

(93)

Pseudokoder

- |x|fra x

- n! fran

(94)

Pseudokoder

(95)

Pseudokoder

1,1,2,3,5,8,13,21, . . . .

og for ˚a undersøke om

(96)

Pseudokoder

(97)

Pseudokoder

- Parentesene i et algebraisk uttrykk er satt p˚a lovlig m˚ate

- Et naturlig tall er et primtall

(98)

Pseudokoder

(99)

KONTROLLSTRUKTURER

En kontrollstrukturbrukes for ˚a styre hvordan, og hvorvidt, de enkle instruksjonene i en pseudokode skal utføres.

Vi skal innføre de kontrollstrukturene det er aktuelt ˚a bruke i dette emnet via eksempler p˚a bruk. Disse eksemplene skal supplere eksemplene fra læreboka.

Vi skal benytte oss av de samme kontrollstrukturene som boka.

(100)

KONTROLLSTRUKTURER

(101)

KONTROLLSTRUKTURER

(102)

KONTROLLSTRUKTURER

(103)

Kontrollstrukturer

Eksempel (Absoluttverdi)

Vi skal gi en pseudokode for ˚a beregne absoluttverdien til et tallx:

1 Inputx 2 If x<0 then

2.1 x← −x

3 Output x

(104)

Kontrollstrukturer

1 Inputx 2 Ifx <0 then

2.1 x← −x

3 Output x

(105)

Kontrollstrukturer

1 Inputx

2 Ifx <0 then

2.1 x← −x

3 Output x

(106)

Kontrollstrukturer

2.1 x← −x 3 Output x

(107)

Kontrollstrukturer

2.1 x← −x

3 Output x

(108)

Kontrollstrukturer

2.1 x← −x 3 Output x

(109)

Kontrollstrukturer

Eksempel (Avstand)

Vi skal gi en pseudokode for ˚a beregne avstanden mellom to heltall.

1 Inputn [n et heltall] 2 Inputm [m et heltall] 3 If n<m then

3.1 x←m−n

else

3.2 x←n−m

4 Output x

(110)

Kontrollstrukturer

Eksempel (Avstand)

1 Inputn [n et heltall] 2 Inputm [m et heltall] 3 Ifn <m then

3.1 x←m−n

else

3.2 x←n−m

4 Output x

(111)

Kontrollstrukturer

Eksempel (Avstand)

1 Inputn [n et heltall]

2 Inputm [m et heltall] 3 Ifn <m then

3.1 x←m−n

else

3.2 x←n−m

4 Output x

(112)

Kontrollstrukturer

Eksempel (Avstand)

2 Inputm [m et heltall]

3 Ifn <m then

3.1 x←m−n

else

3.2 x←n−m

4 Output x

(113)

Kontrollstrukturer

Eksempel (Avstand)

3 Ifn <m then

3.1 x←m−n else

3.2 x←n−m

4 Output x

(114)

Kontrollstrukturer

Eksempel (Avstand)

3 Ifn <m then 3.1 x←m−n

else

3.2 x←n−m

4 Output x

(115)

Kontrollstrukturer

Eksempel (Avstand)

3 Ifn <m then 3.1 x←m−n else

3.2 x←n−m 4 Output x

(116)

Kontrollstrukturer

Eksempel (Avstand)

3.2 x←n−m

4 Output x

(117)

Kontrollstrukturer

Eksempel (Avstand)

3.2 x←n−m 4 Output x

(118)

Kontrollstrukturer

Vi skal se tre eksempler p˚a hvordan vi kan skrive pseudokoder for algoritmer som beregner

n! = 1·2·. . .·n.

I det ene eksemplet bruker vi en while-løkke, i det andre en repeat-until-løkke og i det siste en for-løkke.

(119)

Kontrollstrukturer

Vi skal se tre eksempler p˚a hvordan vi kan skrive pseudokoder for algoritmer som beregner

n! = 1·2·. . .·n.

I det ene eksemplet bruker vi en while-løkke, i det andre en repeat-until-løkke og i det siste en for-løkke.

(120)

Kontrollstrukturer

Eksempel (while-løkke)

1 Inputn [n ≥1,n heltall] 2 x ←1

3 i ←1

4 Whilei ≤n do

4.1 x←x·i 4.2 i←i+ 1

5 Output x

(121)

Kontrollstrukturer

Eksempel (while-løkke) 1 Inputn [n ≥1,n heltall]

2 x ←1 3 i ←1

4 Whilei ≤n do

4.1 x←x·i 4.2 i←i+ 1

5 Output x

(122)

Kontrollstrukturer

2 x ←1

3 i ←1

4 Whilei ≤n do

4.1 x←x·i 4.2 i←i+ 1

5 Output x

(123)

Kontrollstrukturer

2 x ←1 3 i ←1

4 Whilei ≤n do

4.1 x←x·i 4.2 i←i+ 1

5 Output x

(124)

Kontrollstrukturer

2 x ←1 3 i ←1

4 Whilei ≤n do

4.1 x←x·i 4.2 i←i+ 1 5 Output x

(125)

Kontrollstrukturer

2 x ←1 3 i ←1

4 Whilei ≤n do 4.1 x←x·i

4.2 i←i+ 1 5 Output x

(126)

Kontrollstrukturer

2 x ←1 3 i ←1

4 Whilei ≤n do 4.1 x←x·i 4.2 i←i+ 1

5 Output x

(127)

Kontrollstrukturer

2 x ←1 3 i ←1

4 Whilei ≤n do 4.1 x←x·i 4.2 i←i+ 1 5 Output x

(128)

Kontrollstrukturer

Eksempel (repeat-until-løkke)

3 i ←1 4 Repeat

4.1 x←x·i 4.2 i←i+ 1

until i =n+ 1 5 Output x

(129)

Kontrollstrukturer

Eksempel (repeat-until-løkke) 1 Inputn [n ≥1,n heltall]

2 x ←1 3 i ←1 4 Repeat

4.1 x←x·i 4.2 i←i+ 1

(130)

Kontrollstrukturer

2 x ←1

3 i ←1 4 Repeat

4.1 x←x·i 4.2 i←i+ 1

(131)

Kontrollstrukturer

2 x ←1 3 i ←1

4 Repeat

4.1 x←x·i 4.2 i←i+ 1

(132)

Kontrollstrukturer

2 x ←1 3 i ←1 4 Repeat

4.1 x←x·i 4.2 i←i+ 1 until i =n+ 1 5 Output x

(133)

Kontrollstrukturer

2 x ←1 3 i ←1 4 Repeat

4.1 x←x·i

4.2 i←i+ 1 until i =n+ 1 5 Output x

(134)

Kontrollstrukturer

2 x ←1 3 i ←1 4 Repeat

4.1 x←x·i 4.2 i←i+ 1

(135)

Kontrollstrukturer

2 x ←1 3 i ←1 4 Repeat

4.1 x←x·i 4.2 i←i+ 1 until i =n+ 1

5 Output x

(136)

Kontrollstrukturer

2 x ←1 3 i ←1 4 Repeat

4.1 x←x·i 4.2 i←i+ 1 until i =n+ 1 5 Output x

(137)

Kontrollstrukturer

Eksempel (for-løkke)

3 i ←1

4 For i = 1 ton do

4.1 x←x·i

5 Output x

(138)

Kontrollstrukturer

Eksempel (for-løkke)

1 Inputn [n ≥1,n heltall]

2 x ←1 3 i ←1

4 For i = 1 ton do

4.1 x←x·i

5 Output x