Discrete Wiskunde. D. Bruin J.M. Jansen

Discrete Wiskunde

D. Bruin J.M. Jansen Opleiding Hogere Informatica Noordelijke Hogeschool Leeuwarden Nederlandse defensie academie, faculteit militaire wetenschappen Juni 1999 + oktober 2013

Discrete Wiskunde

2

1.

EXPRESSIES ...................................................................................................................................7

1.1 EXPRESSIES EN HERSCHRIJVINGEN .................................................................................................7 1.2 REGELS VOOR EXPRESSIES ..............................................................................................................8 1.2.1 Opgaven .................................................................................................................................9 1.3 BEREKENEN VAN EXPRESSIES .........................................................................................................9 1.3.1 Opgaven .................................................................................................................................9 1.4 EXPRESSIES IN AMANDA ..............................................................................................................10 1.5 WAARHEIDSWAARDEN (BOOLEANS).............................................................................................10 1.5.1 Opgaven ...............................................................................................................................12 1.6 HERSCHRIJFREGELS ......................................................................................................................13 1.6.1 Opgaven ...............................................................................................................................14 2.

INLEIDING FUNCTIONEEL PROGRAMMEREN ................................................................15

2.1 FUNCTIES ......................................................................................................................................15 2.1.1 De Amanda interpreter ........................................................................................................16 2.1.2 Functies met meer resultaten en where clauses...................................................................16 2.1.3 Functies in functies ..............................................................................................................17 2.2 FUNCTIES MET CONDITIES ............................................................................................................17 2.2.1 Opgaven ...............................................................................................................................18 2.3 ANDERS DAN GETALLEN ...............................................................................................................18 2.3.1 Waarheidswaarden (booleans) ............................................................................................18 2.3.2 Karakters .............................................................................................................................18 2.3.3 Opgaven ...............................................................................................................................19 2.4 LIJSTEN & TUPLES ........................................................................................................................19 2.4.1 Lijsten van karakters............................................................................................................22 2.4.2 Opgaven ...............................................................................................................................22 2.4.3 Tuples...................................................................................................................................22 2.5 LIJST-COMPREHENSIES .................................................................................................................22 2.5.1 Opgaven ...............................................................................................................................24 2.6 ZIP ................................................................................................................................................25 2.6.1 Opgaven ...............................................................................................................................25 2.7 TYPERING IN AMANDA .................................................................................................................26 2.7.1 Typering van expressies.......................................................................................................26 2.7.2 Typering van functies...........................................................................................................27 2.7.3 Typering van lijsten .............................................................................................................28 3.

TOEPASSINGEN VAN LIJSTCOMPREHENSIES .................................................................29

3.1.1 Opgaven ...............................................................................................................................29 3.2 VOORBEELD: CIJFER ADMINISTRATIE ...........................................................................................30 3.2.1 Opgaven ...............................................................................................................................30 3.3 VERWERKEN VOETBALUITSLAGEN ...............................................................................................31 3.4 DATABASES MBV. LIJSTCOMPREHENSIES ......................................................................................32 3.4.1 Queries over één tabel .........................................................................................................33 3.4.2 Opgaven ...............................................................................................................................33 3.4.3 Subqueries en hulpfuncties ..................................................................................................34 3.4.4 Opgaven ...............................................................................................................................34 3.4.5 Queries over twee tabellen ..................................................................................................34 3.4.6 Opgaven ...............................................................................................................................35 3.4.7 Complexe queries.................................................................................................................35 3.4.8 Opgaven ...............................................................................................................................35 3.5 ANALYSE VAN TEKSTEN ...............................................................................................................35 3.5.1 Opgaven ...............................................................................................................................36 3.5.2 Lay-out .................................................................................................................................37 3.6 FUNCTIES OP LIJSTEN ....................................................................................................................38 3.6.1 Patronen...............................................................................................................................38 3.6.2 Opgaven ...............................................................................................................................39 3.6.3 Ingewikkelder patronen .......................................................................................................39

Discrete Wiskunde

3

4.

RECURSIE EN INDUCTIE .........................................................................................................41

4.1 RECURSIE .....................................................................................................................................41 4.1.1 Opgaven ...............................................................................................................................42 4.2 INDUCTIE ......................................................................................................................................42 4.2.1 Opgaven ...............................................................................................................................43 4.3 TORENS VAN HANOI .....................................................................................................................44 4.3.1 Opgaven ...............................................................................................................................45 4.4 RECURSIEVE BOMEN .....................................................................................................................45 4.4.1 Opgaven ...............................................................................................................................45 4.4.2 Opgaven ...............................................................................................................................47 5.

RECURSIEVE DATASTRUCTUREN EN BOMEN.................................................................48

5.1 ZELF DATASTRUCTUREN MAKEN ..................................................................................................48 5.1.1 Opgaven ...............................................................................................................................49 5.2 BINAIRE BOMEN ...........................................................................................................................49 5.2.1 Functies op bomen ...............................................................................................................50 5.2.2 Afdrukken van een boom......................................................................................................50 5.2.3 Opgaven ...............................................................................................................................51 5.2.4 Binaire Zoekbomen ..............................................................................................................52 5.2.5 Opgaven ...............................................................................................................................54 6.

HUFFMAN CODERING ..............................................................................................................56

6.1 HUFFMAN BOMEN ........................................................................................................................56 6.1.1 Opgaven ...............................................................................................................................57 6.2 CODEER- EN DECODEER-ALGORITMEN VOOR HUFFMAN BOMEN ..................................................57 6.2.1 Codeer..................................................................................................................................57 6.2.2 Decoderen............................................................................................................................58 6.3 CONSTRUCTIE VAN DE HUFFMAN BOOM .......................................................................................58 7.

EINDIGE AUTOMATEN.............................................................................................................60

7.1 TALEN EN EINDIGE AUTOMATEN...................................................................................................60 7.1.1 Opgaven ...............................................................................................................................61 7.2 EEN EINDIGE AUTOMAAT BOUWEN ...............................................................................................62 7.2.1 Opgaven ...............................................................................................................................63 7.3 DETERMINISME .............................................................................................................................63 7.3.1 Opgaven ...............................................................................................................................65 7.4 DETERMINISTISCH MAKEN VAN EEN AUTOMAAT ..........................................................................65 7.4.1 Opgaven ...............................................................................................................................68 7.5 REGULIERE EXPRESSIES ................................................................................................................68 7.5.1 Opgaven ...............................................................................................................................71 8.

GRAMMATICA’S.........................................................................................................................72

8.1 REKENKUNDIGE EXPRESSIES ........................................................................................................72 8.1.1 Opgaven ...............................................................................................................................74 9.

BACKTRACKING........................................................................................................................77

9.1 INLEIDING .....................................................................................................................................77 9.2 KLEUREN VAN EEN LANDKAART ..................................................................................................77 9.3 HET ACHT KONINGINNEN PROBLEEM ............................................................................................78 9.3.1 Opgaven ...............................................................................................................................79 10.

GULZIGE ALGORITMEN .....................................................................................................81

10.1 GRAFEN ........................................................................................................................................81 10.1.1 Representaties......................................................................................................................81 10.2 MINIMALE OPSPANNENDE BOOM ..................................................................................................83 10.2.1 Het algoritme van Kruskal...................................................................................................83 10.2.2 Het algoritme van Prim .......................................................................................................83 10.2.3 Opgaven ...............................................................................................................................84 10.3 KORTSTE PAD ...............................................................................................................................84

Discrete Wiskunde

4

10.3.1 10.3.2 10.3.3 10.3.4

Het algoritme van Dijkstra ..................................................................................................85 Opgaven ...............................................................................................................................85 Het algoritme van Floyd ......................................................................................................86 Opgaven ...............................................................................................................................87

Discrete Wiskunde

5

Discrete Wiskunde

6

1. Expressies 1.1 Expressies en herschrijvingen Discrete wiskunde gaat over wiskundige structuren en technieken die van fundamenteel belang zijn voor de informatica. Zoals wiskundige beschrijvingen van de vorm, de syntax, van programmeertalen. Zoals wiskundige beschrijvingen van berekeningen. Zoals het wiskundig analyseren van complexe datastructuren en algoritmen. Een veel gebruikte techniek is om een object te beschrijven met een formule (meestal een expressie genaamd) en deze expressie stap voor stap te herschrijven volgens bepaalde rekenregels. In deze inleidende paragraaf bekijken we dat procede voor de ons bekende wiskunde. De basiselementen van “gewone” wiskunde zijn getallen, punten, lijnen, matrixen etc. De getallen kunnen we onderscheiden in natuurlijke getallen (0, 1, 2 ...), de gehele getallen (... -2, -1, 0, 1, 2 ...), de breuken (1/2 , 3/4 ..) en de reele getallen (π, √ 2 ...). Uit de basiselementen kunnen we expressies opbouwen m.b.v. functies zoals sin, cos, ln en operatoren zoals +, -, *, /. Voorbeelden: sin π * (ln 1 + 3) (8-2) * (8+2)

(= 0) (= 60)

Voor de operatoren gelden allerlei rekenregels zoals: (1) x+y=y+x (2) x*y=y*x (3) x * (y + z) = x * y + x * z (4) (x+y)2 = x2 + 2 * x * y + y2 (5) (x+y) * (x-y) = x2 - y2 Het nut van de rekenregels is dat we er expressies mee kunnen herschrijven tot een handiger vorm. Bijvoorbeeld: (8-2) * (8+2) = 82 - 22 = 64 - 4 = 60 (volgens (5)) (8-2) * (8+2) = 6 * 10 = 60 Via herschrijvingen kunnen we ook vergelijkingen oplossen: Voorbeeld: 2*x+4=0 2*x+4-4=0-4 (van gelijke dingen 4 aftrekken) 2 * x = -4 0.5 * 2 * x = 0.5 * -4 x = -2

Discrete Wiskunde

7

Voorbeeld: x2 + 4 * x - 12 = 0 x2 + 4 * x + 4 - 4 - 12 = 0 (x + 2)2 - 16 = 0 (x + 2)2 = 16 x + 2 = 4 \/ x + 2 = -4 x = 2 \/ x = -6 Voorbeeld: x+2*y=8 2*x-y=6 x=8-2*y 2 * (8 - 2 * y) - y = 6 16 - 5 * y = 6 -5 * y = -10 y=2

(stelsel van 2 vergelijkingen met 2 onbekenden)

(invullen in tweede vergelijking)

x=8-2*2=4 Met herschrijven moet je wel voorzichtig zijn want een verkeerde toepassing van regel (2) is: 1+2*2+1=2+1*1+2 (x = 1 + 2 en y = 2 + 1) Wel correct is: (1 + 2) * (2 + 1) = (2 + 1) * (1 + 2) (x = (1 + 2) en y = (2 + 1)) In het vak discrete wiskunde zullen we allerlei nieuwe waarden bestuderen zoals waarheidswaarden (True, False) en lijsten. We zullen de functionele programmeertaal Amanda bestuderen die herschrijven gebruikt om dingen uit te rekenen. We zullen formalismen bestuderen die de precieze vorm van expressies beschrijven. Waar het in de wiskunde vooral gaat om het bedenken van efficiente algoritmen voor het oplossen van numerieke of ruimtelijke problemen, gaat het in de informatica veel meer om de structuur: de vorm van expressies, de opbouw van programma’s.

1.2 Regels voor expressies Voor rekenkundige expressies gelden er allerlei regels: * heeft een hogere prioriteit dan +, a - b - c moet gelezen worden als: (a - b) - c. Indien we van de standaard regels willen afwijken dan gebruiken we haakjes: 3 * (4 + 5) 6 - (3 - 1) Bij a + b + c maakt het niet uit hoe we de haakjes plaatsen: a + (b + c) (a + b) + c

Discrete Wiskunde

8

hebben beide hetzelfde resultaat. Dit geldt ook voor de * operator. + en * heten daarom ook wel associatieve operaties. Dit geldt niet voor - en /. - en / heten links-associatieve operaties, omdat we in a - b - c de haakjes links moeten zetten: (a - b) - c. Er bestaan ook rechts-associatieve operaties. Machtsverheffing is hier een voorbeeld van. a ^ b ^ c moet gelezen worden als a ^ (b ^ c).

1.2.1 Opgaven Opgave 1.1

Zet in onderstaande expressies de haakjes op de juiste plaats: 3*2+1 4 + 5 + 6 -2 8^7*4-1 3 * (6 + 7 -3) 7^2-2^3 Verwijder in onderstaande expressies de overtollige haakjes: (3 * 2) + 5 2 + (3 + (6 * 2)) (2 ^ 3) ^ 4 7 - ((5 - 2) + 1)

1.3 Berekenen van expressies Je kunt het reultaat van een rekenkundige expressie vaak op meerdere manieren berekenen: (3 + 2) ^ 2 -> 5 ^ 2 -> 5 * 5 -> 25

of (3 + 2) ^ 2 -> (3 + 2) * (3 + 2) -> 5 * (3 + 2) -> 5 * 5 -> 25

of (3 + 2) ^ 2 -> (3 + 2) * (3 + 2) -> (3 + 2) * 5 -> 5 * 5 -> 25

Alle manieren van berekenen leiden tot hetzelfde resultaat, alleen de eerste manier gaat het snelste. Bij rekenkundige expressies is het altijd zo dat het resultaat onafhankelijk is van de manier van berekenen. We zullen later andere expressies zien waarbij het resultaat wel afhangt van de manier van berekenen.


Discrete Wiskunde

9

Op hoeveel manieren kan 1 + 2 + 3 berekend worden? Op hoeveel manieren kan 3 * 2 + 3 * 3 berekend worden? Op hoeveel manieren kan ((2 + 3) ^ 2) ^ 2 berekend worden?

1.4 Expressies in Amanda In de Amanda interpreter kunnen gewone rekenkundige expressies berekend worden. Amanda is in dit opzicht niet meer dan een uitgebreide rekenmachine. Amanda gebruikt de standaard regels voor prioriteiten en associatie. In Amanda kunnen expressies echter nog veel ingewikkelder zijn. Er kunnen bv. functieaanroepen en lijsten in voorkomen. Hieronder volgen een aantal voorbeelden met functieaanroepen: sqr 3 telop 2 3 sqr 3 + 1 sqr (3 + 1)

// sqr en telop zijn in een file gedefinieerde functies

Omdit goed te kunnen begrijpen moeten we in Amanda extra afspraken maken over proriteiteiten. sqr 3 + 1 moeten we lezen als (sqr 3) + 1. Het toepassen van een functie op een argument heeft de allerhoogste prioriteit. telop is een functie met twee argumenten. Ook voor functies met meerdere argumenten gebruiken we alleen haakjes als dit echt nodig is: telop 2 3 + 1 betekent telop (2+3) (4+5) ->

(telop 2 3) + 1 telop 5 9 ->

14

1.5 Waarheidswaarden (booleans) Tot dusver hebben we alleen expressies met getallen (en functies van getallen) bekeken. Amanda kent echter ook zgn. waarheidswaarden (booleans). Zoals getallen worden gebruikt om te tellen of afstanden te meten worden de waarheidswaarden True en False gebruikt om aan te geven of een uitspraak waar of onwaar is. Voorbeelden: “de aarde is rond” = True “alle zoogdieren kunnen vliegen” = False De waarheidswaarden of eigenlijk de uitspraken kunnen we combineren met de operatoren niet, en, of, als dan. Voorbeelden:

Discrete Wiskunde

10

niet “de aarde is rond” = False “de aarde is rond” en “alle zoogdieren kunnen vliegen” = False “de aarde is rond” of “alle zoogdieren kunnen vliegen” = True als “de aarde is rond” dan “alle zoogdieren kunnen vliegen” = False als “alle zoogdieren kunnen vliegen” dan “de aarde is rond” = True De uitkomsten van de operatoren hangen alleen af van de waarheidswaarden van hun operanden. Met zogenaamde waarheidstabellen kunnen we de werking van de operatoren precies vastleggen. p ~p -----------------------T F F T

(niet p)

Voor het gemak gebruiken we T als afkorting van True en F als afkorting van False. In het vak computerorganisatie wordt hetzelfde gedaan met bits die dan 0 en 1 heten. p q p /\ q (p en q) -------------------------------------T T T T F F F T F F F F p q p \/ q (p of q) -------------------------------------T T T T F T F T T F F F p q p -> q (als p dan q) -------------------------------------T T T T F F F T T F F T

(-> komt niet voor in Amanda)

De tabellen voor \/ en -> verschillen maar heel weinig. Het is niet zo moeilijk om te zien dat: p -> q = ~p \/ q We kunnen dit narekenen met een waarheidstabel voor ~p \/ q

Discrete Wiskunde

11

p q ~p ~p \/ q ------------------------------------------------T T F T T F F F F T T T F F T T Het aantal rijen van een waarheidstabel hangt af van het aantal variabelen dat erin voorkomt. Als er 1 variabele is dan zijn 2 rijen genoeg. Bij 2 variabelen zijn er 4 rijen. Bij 3 variabelen zijn er 8 rijen. Zoals het volgende voorbeeld laat zien: p q r p /\ q /\ r (p /\ q /\ r) -> p ----------------------------------------------------------------------------T T T T T T T F F T T F T F T T F F F T F T T F T F T F F T F F T F T F F F F T Hier is iets bijzonders aan de hand: de uitspraak is altijd waar ongeacht de waarheidswaarden van de variabelen. Zo’n uitspraak noemen we een tautologie. Om het aantal haakjes in expressies te beperken gebruiken we de conventie dat ~ het sterkst bindt, dan /\, dan \/ en als laatste -> De expressie: p \/ ~q /\ q -> ~p moeten we dus lezen als (p \/ ((~q) /\ q)) -> (~p) Waarheidswaarden spelen een belangrijke rol bij de werking van computersystemen. True en Faklse corresponderen hier met wel of geen spanning. In essentie zitten er in een microprocessor alleen maar schakkelingen die and en or uit kunnen rekenen. Alle andere operaties worden hier op teruggevoerd. In het vak Computer Organisatie komt dit uitgebreid aan de orde en zal er ook dieper worden ingegaan op booleaanse logica.


Bepaal aan de hand van een waarheidstabel of de volgende uitspraken tautologien zijn: a. p /\ ~p -> q b. q -> p \/ ~p c. p -> (q -> p) d. ~p -> p \/ q e. p -> (q -> (r -> ~q)) f. p /\ q -> p \/ q Opgave 1.4

Gegeven zijn de volgende uitspraken:

Discrete Wiskunde

12

p = “het regent” q = “de zon schijnt” Formuleer mbv p en q en de logische operatoren de volgende uitspraken: a. het regent niet, maar de zon schijnt wel b. als het regent dan schijnt de zon niet c. als de zon schijnt dan regent het niet d. de zon schijnt of het regent Opgave 1.5

Geef de ontkenning van de volgende uitspraken: a. 10 is groter dan 12 b. het regent en de zon schijnt c. ik heet Piet of jij heet Klaas d. als het regent dan schijnt de zon niet

1.6 Herschrijfregels Voor de logische operatoren gelden allerlei “bekende” regels: p /\ q = q /\ p p /\ (q /\ r) = (p /\ q) /\ r p \/ q = q \/ p p \/ (q \/ r) = (p \/ q) \/ r p /\ (q \/ r) = (p /\ q) \/ (p /\ r) Veel mensen onthouden deze regels door /\ te lezen als * en \/ als + Er zijn meer regels: T \/ p = T F \/ p = p T /\ p = p F /\ p = F ~p /\ p = F ~p \/ p = T p \/ (q /\ r) = (p \/ q) /\ (p \/ r) ~(~ p) = p p -> q = ~p \/ q

(als dan regel)

~(p /\ q) = ~p \/ ~q ~(p \/ q) = ~p /\ ~q

(regel van De Morgan) (regel van De Morgan)

Let er bij de regels van De Morgan op dat /\ verandert in \/ en andersom! We kunnen de regels gebruiken om expressies te vereenvoudigen.

Discrete Wiskunde

13

p /\ q -> p ~(p /\ q) \/ p (~p \/ ~q) \/ p ~p \/ ~q \/ p ~p \/ p \/ ~q T \/ ~q T

= = = = = =

(als dan regel) (De Morgan)

Dus p /\ q -> p is een tautologie. De volgorde waarin de regels werden toegepast is niet willekeurig. Vaak is het handig om alle -> weg te werken met de als dan regel en daarna ~ binnen haakjes te werken met De Morgan. Nog een voorbeeld: ~(p -> q) -> p ~(~(p -> q)) \/ p (p -> q) \/ p (~p \/ q) \/ p ~p \/ p \/ q T \/ q T

= = = = = =

(als dan regel) (als dan regel)

Alweer een tautologie.


Bepaal aan de hand van herschrijving of de volgende uitspraken tautologien zijn: a. p /\ ~p -> q b. q -> p \/ ~p c. p -> (q -> p) d. ~p -> p \/ q e. p -> (q -> (r -> ~q)) f. p /\ q -> p \/ q Opgave 1.5

Vereenvoudig de volgende uitspraken: a. (p \/ q) /\ ~p b. ~(p -> q) -> p c. (~p -> ~q) -> (q -> p) d. (p -> q) -> (~q -> ~p)

Discrete Wiskunde

14

2. Inleiding Functioneel Programmeren In dit hoofdstuk geven we een inleiding in Functioneel Programmeren. We gebruiken hiervoor de functionele programmeertaal Amanda. Functionele programmeertalen onderscheiden zich van de 'gewone' programmeertalen, zoals Pascal, C en C++, omdat ze het wiskundige functiebegrip als uitgangspunt gebruiken i.p.v. het model van de computer. De notatie van Functioneel Programmeren sluit daarom beter aan bij de wiskunde, hetgeen bij dit vak goed van pas komt.

2.1 Functies De functies zoals ze in functioneel programmeren gebruikt worden lijken veel op de functies zoals je die bij wiskunde hebt gehad: verhoog x = x + 1

De functie verhoog heeft een argument x en heeft als resultaat x + 1. Wat zijn de verschillen met de functies die je bij wiskunde gewend was. 1. We geven de functie een naam die de lading dekt i.p.v. f, g of h. De naam moet met een kleine letter beginnen. 2. Het argument van de functie staat niet tussen haakjes; dus geen verhoog(x)=x+1. De reden om het argument niet tussen haakjes te zetten is een praktische, je wilt gewoon zo weinig mogelijk typen! Haakjes worden alleen gebruikt als dit nodig is om de betekenis goed te begrijpen. Nu nog wat terminologie: 1. verhoog heet de naam van de functie 2. x heet de naam van het argument 3. x + 1 heet de definiërende expressie van de functie De definiërende expressie van een functie mag een willekeurige rekenkundige expressie zijn waarin de argumenten mogen voorkomen. Een functie mag ook meerdere argumenten hebben. gem x y = (x + y) // 2

gem berekent het gemiddelde van de getallen x en y. Ook als er meerdere argumenten zijn gebruiken we geen haakjes aan de linkerkant van de functiedefinitie. In de definiërende expressie van deze functie (x+y) // 2 hebben we wel haakjes nodig vanwege de hogere prioriteit van // boven +. In Amanda is // deling voor reële getallen. / is deling voor gehele getallen en wordt ook wel met div aangeduid.

Discrete Wiskunde

15

Dus: 10 // 3 = 3.33333 10 / 3 = 3 10 div 3 = 3

2.1.1 De Amanda interpreter Tijdens het werkplaats hebben we al kennisgemaakt met de Amanda interpreter. Van de Amanda interpreter bestaan verschillende versies. Als we in dit diktaat een voorbeeld willen geven van een expressie die geëvalueerd wordt dan doen we dit als volgt: > 3 * 6 + 5 23

Op de eerste regel voorafgegaan door een > staat de expressie die geëvalueerd moet worden, op de regel daarna het resultaat. Functie definities staan in een file. Deze kunnen in de Amanda omgeving geladen worden.

2.1.2 Functies met meer resultaten en where clauses. We gaan nu eens een wat meer ingewikkelde functie bekijken. Een functie die de nulpunten van een tweedegraads polynoom berekent. Dit gaat m.b.v. de abc-formule. In eerste instantie definiëren we twee functies, voor iedere wortel één. Als argumenten voor deze functie geven we de coefficiënten a, b en c. x1 a b c = (-b - sqrt (b^2 - 4 * a * c) // (2 * a) x2 a b c = (-b + sqrt (b^2 - 4 * a * c) // (2 * a)

Het zou fraaier zijn als we een functie hadden die beide resultaten in een keer oplevert. Dit kan m.b.v. zogenaamde tuples. Een tuple is een expressie bestaande uit meerdere expressies tussen haakjes en gescheiden met komma's. Voorbeelden: (1,2) is het tuple bestaande uit de getallen 1 en 2. (5,7,3,3*4) is het tuple bestaande uit de getallen 5, 7, 3 en de expressie 3 * 4. Typ in Amanda zelf ook een aantal tuples in en kijk wat er gebeurt als je ze evalueert. We definiëren nu een nieuwe functie die beide nulpunten van een tweedegraads polynoom berekent en het resultaat oplevert in een tuple: x12 a b c = ((-b - sqrt (b^2-4*a*c) // (2*a), (-b-sqrt (b^2-4*a*c) // (2*a))

Deze functiedefinitie heeft een nadeel: de expressie sqrt (b^2-4*a*c) moet twee keer worden uitgerekend. Dit kan voorkomen worden door een zgn. where clause te gebruiken. x12 a b c = ((-b - wd) // (2*a), (-b + wd) // (2*a)) where wd = sqrt (b^2 - 4 * a * c)

Discrete Wiskunde

16

Op deze manier wordt sqrt (b^2-4*a*c) maar één keer uitgerekend en is ook de definitie overzichtelijker geworden. Let op: In de definitie van x12 is er nog geen rekening mee gehouden dat de discriminant wel eens negatief kan zijn.

2.1.3 Functies in functies In de definitie van een functie mag ook gebruik gemaakt worden van andere functies: vbfunctie n = verhoog n * 2 > vbfunctie 4 10

verhoog n * 2 moet hier gelezen worden als (verhoog n) * 2. Toepassing van een functie op een argument gaat voor iedere andere opperatie. Wil je eerst vermenigvuldiging met 2 en daarna pas verhogen, dan moet je haakjes plaatsen: vbfunctie2 n = verhoog (n*2)

2.2 Functies met condities Vaak is het resultaat van een functie afhankelijk van een conditie. Neem bv. de functie die de absolute waarde van een getal berekent. Dit is het getal zelf als het getal positief is en - getal als het getal negatief is. In Amanda wordt dit nu: abs x = x, if x >= 0 = - x, if x < 0

In deze definitie moeten de = tekens precies onder elkaar staan. Een alternatieve definitie die hetzelfde resultaat oplevert: abs x = x, if x >= 0 = -x, otherwise

otherwise gebruik je als de conditie er niet toe doet. In het tweede geval is dit zo omdat een niet positief getal automatisch negatief is. Achter if staat een zgn. waarheidsexpressie die True of False oplevert. Deze mag ook ingewikkelder zijn. Een ander voorbeeld van een functie met condities: f n = 1, if x > 0 /\ x < 5 = 2, if x >= 5 /\ x < 10 = 3, otherwise

Een ander voorbeeld van een functie gebaseerd op een conditie (let op: max2 is al gedefinieerd in Amanda):

Discrete Wiskunde

17

max2 x y = x, if x >= y = y, otherwise


Definieer een functie max3 x y z, die het maximum van x, y en z oplevert.

Opgave 2.2

Definieer een functie grootsteVerschil x y z, die het maximum van de verschillen tussen x, y en z oplevert.

2.3 Anders dan getallen Tot dusver hebben we alleen functies bekeken die getallen als argument en resultaat hebben. Om echt interessante programma's te maken moeten we ook met andere zgn. data typen kunnen werken. Voorbeelden van deze datatypen zijn karakters (bv letters), waarheidswaarden (True en False), en strings (bv. namen).

2.3.1 Waarheidswaarden (booleans) Hiervan hebben we al voorbeelden gezien bij functies met condities. Een functie kan echter ook True of False opleveren (denk om de hoofdletters). kleinerDan3 x = x < 3 > kleinerDan3 5 False > kleinerDan3 2 True

2.3.2 Karakters Dit zijn 256 tekens waarmee onder andere teksten zijn opgebouwd. Er zijn zichtbare en onzichtbare karakters. Zichtbare karakers zijn (onder andere): !"£%^&*()_+-=[]{};:'@#~/?.>,<\123..0ab..zAB..Z Onzichtbare karakters zijn bv: spatie, regelovergang, tab, bel etc. Een karakter wordt in een functie genoteerd als zijn waarde tussen quotes: 'a', 'b', '1'. Dit wordt gedaan om een karakter te onderscheiden van een functie- of argument-naam! Voor onzichtbare karakters bestaan er veelal speciale notaties: '\n' voor een regelovergang, '\t' voor een tab, etc. Let op: Maak goed onderscheid tussen bv. 0 (het getal nul) en '0' het karakter nul. Getallen kun je optellen, karakters niet.

Discrete Wiskunde

18

Ieder karakter heeft een speciale waarde, zijn zgn. ascii code. Deze code is standaard (dus hetzelfde voor alle computer systemen). Amanda heeft een tweetal functies om met ascii codes te kunnen werken: code en decode. code levert voor een karakter zijn ascii code. decode geeft voor een code het bijbehorende karakter. > code 'a' 97 > decode 97 'a'

Dmv. deze codering is er ook een volgorde gedefinieerd op karakters: er geldt voor twee karakters x en y, x < y als code x < code y. Aangezien letters en cijfers in de 'goede' volgorde gecodeerd zijn levert dit geen conflikten op.


Definieer de functie isEven die een getal als argument heeft en True oplevert als het getal even is en False als het oneven is (denk aan mod (%)). Opgave 2.4

Vergelijk de ascii codes van 'a' en 'A', 'b' en 'B' etc. Bedenk nu een functie kLetter die van een hoofdletter een kleine letter maakt. Opgave 2.5

Definieer een functie isLetter die gegeven een karakter aangeeft of dit een letter is: a..z of A..Z. Doe hetzelfde voor cijfers.

2.4 Lijsten & Tuples Rijen van gelijksoortige dingen heten lijsten. Lijsten worden genoteerd tussen [ en ], waarbij de elementen gescheiden zijn door komma's. [1,2,3,6,3,9] [True,False,True] ['d','i','c','k'] []

(lege lijst)

Let erop dat er alleen gelijksoortige dingen in een lijst mogen. Dus: [1,True], ['b',3,4] zijn niet toegestaan. De elementen in een lijst zijn genummerd vanaf 0. Om het i-de element in een lijst te selecteren gebruiken we de ! operator: > [4,2,6] ! 0 4 > [4,2,6] ! 2

Discrete Wiskunde

19

6

De # operator geeft het aantal elementen van een lijst: > # [1,2,3] 3

Mbv. ++ kunnen twee lijsten aan elkaar geplakt worden: > [1,2] ++ [3,4] [1,2,3,4] > ['a','b'] ++ ['c','d'] ['a','b','c','d']

Let erop dat de lijsten van dezelfde soort zijn! Met -- berekenen we het verschil van twee lijsten. > [1,2,3,4,5,6] -- [4,2,3] [1,5,6]

Let goed op bij de volgende voorbeelden: > [1,1,2,2,3,3,3,3] -- [1,2,3] [1,2,3,3,3]

|| elk element uit de tweede lijst wordt maar een keer verwijderd.

> [1,2,3,4,5] -- [3,6] [1,2,4,5]

|| met 6 gebeurt niets

De : operator wordt gebruikt om een element aan het begin van een lijst te plakken. > 3 : [4,5] [3,4,5]

Natuurlijk hadden we dit ook met [3] ++ [4,5] kunnen bereiken. Het gebruik van : is echter efficiënter en verdient daarom de voorkeur. Er bestaan een aantal nuttige functies op lijsten. We geven hier alleen voorbeelden van het gebruik: > take 3 [5,6,7,8,9,1,2] [5,6,7] > drop 3 [5,6,7,8,9,1,2] [8,9,1,2] > hd [1,2,3] 1 > tl [1,2,3] [2,3]

Discrete Wiskunde

20

hd en tl (head en tail) zijn niet gedefinieerd voor lege lijsten. take en drop zijn complementair. Als xs een lijst is en n een getal, dan geldt er: take n xs ++ drop n xs = xs

Voor lijsten bestaan een aantal handige afkortingsnotaties: > [1..10] [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] > [2,4..10] [2, 4, 6, 8, 10] > [7,6..1] [7, 6, 5, 4, 3, 2, 1]

Let op: Lijsten kunnen ook oneindig zijn: > [1..] [1,2,3,4,5,6,7,8,9,.. etc

Oneindige lijsten kunnen handig zijn in expressies waarin maar een (eindig) deel van de lijst gebruikt wordt. > take 20 [1..] [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20]

Andere handige voorgedefinieerde functies op lijsten zijn: > sum [1,2,3,4] 10 > prod [1,2,3,4] 24 > min [4,1,2,6,7] 1 > max [4,5,7,3,1,2] 7 > and [1 < 2,4 < 9] True > or [8 < 2,4 < 9] True

De functie prod kunnen we gebruiken om n! (faculteit) te berekenen. n! is gedefinieerd als 1 * 2 * .. * n In Amanda wordt dit: fac n = prod [1..n]

Discrete Wiskunde

21

2.4.1 Lijsten van karakters Voor lijsten van karakters is er een bijzondere notatie: ['a','a','p'] mag ook worden geschreven als: "aap". Lijsten van karakters worden ook wel strings genoemd en deze spelen een belangrijke rol in veel computer programma's. Veel operaties en functies voor lijsten gelden ook voor strings!


Welke van de bovenstaande functies gelden niet voor strings?

2.4.3 Tuples Lijsten gebruiken we om elementen van dezelfde soort te groeperen. Willen we elementen van verschillende soort groeperen dan gebruiken we tuples. We zijn tuples al eerder tegengekomen: (1,True), ('a',1',False)

Tuples zijn minder flexibel in het gebruik dan lijsten. Je kunt geen tuples aan elkaar plakken. Ook bestaan er geen speciale functies om elementen uit een tuple te selecteren, behalve voor twee-tuples (fst en snd). > fst (3,4) 3 > snd (3,4) 4

Je kunt eenvoudig functies op tuples definiëren dmv. patronen: fst3 (x,y,z) = x snd3 (x,y,z) = y thd3 (x,y,z) = z

Op het gebruik van patronen in functie definities zullen we later nog terugkomen. Tuples hebben dus een veel minder krachtige functionaliteit dan lijsten en worden dan ook voornamelijk gebruikt om resultaten te groeperen, zoals in het voorbeeld van de nulpunten van een tweedegraads polynoom.

2.5 Lijst-comprehensies Lijsten zijn we al eerder tegengekomen. Amanda bevat krachtige operaties op lijsten, de zgn. lijst-comprehensies. We geven weer een aantal voorbeelden om dit begrip te introduceren:

Discrete Wiskunde

22

> [2*x| x <- [3,4,1,6]] [6, 8, 2, 12]

Lees dit als: de lijst van alle waarden 2 * x, waarbij x komt uit de lijst [3,4,1,6]. Andere voorbeelden: > [x+2| x <- [1..10]] [3, 4, 5, 6, 7, 8, 9, 10, 11, 12] > [3| x <- [1..10]] [3, 3, 3, 3, 3, 3, 3, 3, 3, 3]

Een iets ingewikkelder voorbeeld: > [x| x <- [1..10]; x mod 2 = 0] [2, 4, 6, 8, 10]

Lees dit als: de lijst van alle waarden x, waarbij x komt uit de lijst [1..10] en waarbij x voldoet aan x mod 2 = 0 (x is even). > [3*x| x <- [1..10]; x mod 2 = 0] [6, 12, 18, 24, 30]

Lees dit als: de lijst van alle waarden 3 * x, waarbij x komt uit de lijst [1..10] en waarbij x voldoet aan x mod 2 = 0 (x is even). Nu even wat terminologie: x <- [1..10] heet een generator. x mod 2 = 0 heet een conditie.

Aan de linkerkant van de pijl in een generator moet een variabele staan, aan de rechter kant een expressie die een lijst oplevert. In deze expressie mogen variabelen uit eerdere generatoren voorkomen. De conditie is een expressie die True of False oplevert en waarin variabelen uit eerder gedefinieerde generatoren kunnen optreden. Er mogen in een lijst-comprehensie best meerdere generatoren en condities voorkomen. > [x + y| x <- [1..3]; y <- [7..9]] [1+7,1+8,1+9, 2+7,2+8,2+9, 3+7,3+8,3+9]

(dit is een tussenstap)

[8,9,10,9,10,11,10,11,12]

We zien hier dat de tweede generator 3 keer herhaald wordt, voor iedere waarde uit de eerste generator een keer. De tweede generator loopt het hardst. Mbv. lijstcomprehensies kunnen velen programmeerproblemen opgelost worden. We zullen hiervan in dit vak nog veel voorbeelden tegenkomen. Het eerste voorbeeld dat we bekijken is het volgende:

Discrete Wiskunde

23

Geef alle drietallen (x,y,z) tussen de 1 en 32 zodat: x - y = 6, z + x = 17 en y * z = 18. Mbv. een lijstcomprehensie los je dit probleem in één regel op: [(x,y,z)| x <- [1..32]; y <- [1..32]; z <- [1..32]; x - y = 6; z + x = 17; y * z = 18]

Vraag

Hoeveel combinaties van (x,y,z) worden er in deze lijstcomprehensie uitgeprobeerd? Bovenstaande lijstcomprehensie geeft ons wel de juiste oplossing voor ons probleem, maar is niet erg efficiënt. Immers als voor x een waarde gekozen is, dan liggen y en z al vast omdat: x - y = 6 en z + x = 17. We passen onze lijstcomprehensie hiervoor aan: [(x,y,z)| x <- [1..32]; y <- [x - 6]; z <- [17 - x]; y * z = 18]

We zien hier twee generatoren met een lijst met slechts een element: y <- [x - 6] en z <- [17 - x]. Hiervoor bestaat in Amanda een speciale notatie: y := x - 6 en z := 17 - x. Onze lijstcomprehensie wordt nu: [(x,y,z)| x <- [1..32]; y := x - 6; z := 17 - x; y * z = 18]

Vraag

Hoeveel keer efficiënter is de tweede oplossing?


Wat is er fout in onderstaande oplossingen van bovengenoemde puzzel? [(x,y,z) | x <- [1..32]; x - y = 6; y <- [1..32]; z <- [1..32]; z + x = 17; y * z = 18] [(x,y,z) | x <- [1..32]; y <- x - 6; z <- [17 - x]; y * z = 18] [(x,y,z) | x <- [1..32]; y = x - 6; z <- [17 - x]; y * z = 18]

Vooral de laatste fout wordt veel gemaakt! Opgave 2.8

De standaard functie member test of een lijst een bepaald element bevat: > member [1,2,3] 3 True > member [1,2,3] 4 False

Definieer nu zelf mbv. een lijstcomprehensie de functie mem die hetzelfde doet als member. Definieer de functies and en or mbv. een lijstcomprehensie (tellen!). Opgave 2.9

Definieer mbv. een lijstcomprehensie een functie aantalDelers n, die voor gegeven n het aantal delers van n berekent (d is een deler van n, als n mod d = 0). Opgave 2.10

Discrete Wiskunde

24

Mbv. lijstcomprehensies kunnen we echte programma’s maken. Toepassing telefoonboek: De inhoud van een telefoonboek kunnen we opslaan in een lijst van tupels bestaande uit naam en telefoonnummer: telboek = [("jan",123),("piet",234),...]

Definieer nu mbv lijstcomprehensies de opzoekfuncties telnr en abb: telnr : geeft voor gegeven naam (een lijst van) telefoonnummer(s). abb: geeft bij telnr de bijbehorende (lijst van) na(a)m(en). Opgave 2.11

Toepassing gepast betalen: Definieer mbv. een lijstcomprehensie de functie inMunten b, die gegeven een bedrag b alle mogelijke 4 tuples (g,k,d,s) (guldens, kwartjes, dubbeltjes en stuivers) geeft die samen het bedrag b vormen.

2.6 Zip Een handige operatie op lijsten, die vaak in lijstcomprehensies gebruikt wordt, is zip (rits). Met zip kun je twee lijsten paarsgewijs koppelen. > zip ([1,2,3],["aap","noot","mies"]) [(1,"aap",(2,"noot"),(3,"mies")]

Het is hierbij niet noodzakelijk dat de lijsten even lang zijn, het resultaat is echter nooit langer dan de kortste lijst. Zip is vooral handig in combinatie met lijstcomprehensies. Bekijk de volgende definitie die het i-de element van een lijst oplevert: elem n xs = hd [x | (x,m) <- zip (xs,[0..]);

n = m]

Omdat zip zo vaak gebruikt wordt in lijstcomprehensies is er in Amanda een aparte afkortingsnotatie voor: elem n xs = hd [x | x,m <- xs,[0..]; n = m]

zip kan ook handig zijn wanneer je ieder element uit een lijst met zijn buurman moet vergelijken. Dit kun je bereiken door de lijst met zijn tail te 'zippen'. In het volgende voorbeeld wordt zo gecontroleerd of een lijst gesorteerd is: isSorted xs = and [x <= y| x,y <- xs,tl xs]

In de volgende paragraaf zullen we nog een aantal toepassingen van zip tegenkomen.


Discrete Wiskunde

25

Ga na wat het resultaat is van: zip ([1,2,3,4,5],[4..])

Opgave 2.13

Gebruik zip in een lijstcomprehensie om te tellen hoe vaak, in een lijst van getallen, een getal precies een groter is dan zijn voorganger. Opgave 2.14

In een lijstcomprehensie kun je ook een zip nemen van meer dan twee lijsten. Dit gaat op de volgende manier: [ ...| a,b,c <- as,bs,cs]

Gebruik dit om te testen hoe vaak de lettercombinatie "een" in een string voorkomt.

2.7 Typering in Amanda Amanda is een zgn. sterk getypeerde taal. Dit betekent dat iedere expressie en functie een type heeft. Door de sterke typering van Amanda kunnen veel programmeerfouten tijdig door de interpreter worden opgespoord.

2.7.1 Typering van expressies Het type van een expressie is het soort van de waarde van de expressie. Amanda kent drie basis types: num, bool en char. num is het type van getallen. Iedere rekenkundige expressie heeft dit type. bool is het type van de waarheidswaarden. Iedere booleaanse expressie heeft dit type. char is het type van de karakters zoals ‘a’, ‘b’ etc. Je kunt het type van een expressie is Amanda opvragen door achter de expressie :: te typen en daarna op enter te drukken. > 1 + 2 :: num > 1 = 3 :: bool > ‘a’ char

Omdat er in Amanda ook lijsten gemaakt kunnen worden bestaat er ook het type lijst van: > [1,2,3] :: [num]

Discrete Wiskunde

26

> [True,False] :: [bool] > [‘a’,’v’] :: [char] > “aap” [char]

Er bestaat ook een type voor tupels: > (1,True) :: (num,bool)

Amanda is in staat om fouten in het type van een expressie op te sporen: > 1 + True incorrect use of: + type1: (num -> bool -> *) type2: (num -> num -> num) ERROR: 1 type error

2.7.2 Typering van functies Iedere functie heeft ook een type. Het type van een functie is een combinatie van het type van de argumenten en het type van het resultaat: verhoog x = x + 1 > verhoog :: num -> num

Dit betekent dat het type van argument x van verhoog een getal (num) moet zijn en dat het resultaat van verhoog toegepast op een getal weer een getal is. Als je in Amanda een functie toepast op een element van een verkeerd type, wordt er een foutmelding gegeven. > inc True incorrect use of: inc type1: (bool -> *) type2: (num -> num) ERROR: 1 type error

Nu een voorbeeld van een functie met twee argumenten: telop x y = x + y > telop:: num -> num -> num

Dit is enigszins merkwaardig. Je zou bv. num, num -> num verwachten. Amanda ziet een functie van twee argumenten als een functie die toegepast op het eerste element een nieuwe functie oplevert die daarna op het tweede argument kan worden toegepast! num -> num -> num moet je dus lezen als num -> (num -> num), -> associeerd naar rechts.

Discrete Wiskunde

27

Het toepassen van een functie op maar een deel van de argumenten heet currying (naar H.B. Curry). Currying is vaak erg handig. > map (telop 3) [1..10] [4, 5, 6, 7, 8, 9, 10, 11, 12, 13]

Het eerste argument van map (telop 3) is een gecurryde functie.

2.7.3 Typering van lijsten > [1..10]:: [num] > “hallo” [char]

Voor veel functies op lijsten geldt dat het type van de elementen van de lijst er niet toe doet. Dit wordt in Amanda met een * aangegeven. > take :: num -> [*] -> [*]

Voor * kan nu een willekeurig type worden ingevuld. Merk wel op dat voor take de argument lijst en de resultaat lijst hetzelfde type hebben.

Discrete Wiskunde

28

3. Toepassingen van lijstcomprehensies Veel wiskundige problemen zijn van de soort: Ga na of alle elementen in een verzameling voldoen aan ...., of is er een element in deze verzameling dat voldoet aan ..., hoeveel elementen in deze verzameling voldoen aan ... Lijstcomprehensies bieden een mogelijkheid dit soort problemen te verwoorden, waarbij we lijsten als stand-in voor verzamelingen gebruiken: Zijn alle elementen in de verzameling vs even (een getal g is even als g mod 2 = 0)? and [ v mod 2 = 0| v <- vs]

Geldt voor alle elementen in de verzameling vs dat ze groter zijn dan 3 en kleiner dan 20? and [ v > 3 /\ v < 20| v <- vs]

Is er een element in vs dat even is? or [ v % 2 = 0| v <- vs]

Nu een wat ingewikkelder voorbeeld: Is er voor ieder element v in vs een ander element w in vs zodat: of v = 3 * w of w = 3 * v. In feite lopen hier twee beweringen door elkaar heen, alle elementen uit vs moeten aan iets voldoen, dus: and[ ???| v <- vs]

Hierbij is ??? de voorwaarde (tweede bewering), waaraan v moet voldoen. Dus is er een element w in vs zo dat: v = 3*w of w = 3 * v: or [v = 3 * w \/ w = 3 * v| w <- vs]

Deze laatse bewering moeten we dus op de plaats van ??? invullen. Totaal krijgen we: and [or [v = 3 * w \/ w = 3 * v| w <- vs]| v <- vs]


Schrijf lijstcomprehensies voor de volgende beweringen: Geldt voor alle element in vs dat ze een drievoud zijn. Is er een element in vs dat groter is dan 25 en deelbaar door 18. Voor ieder element v in vs is er een ander element w in vs, dat gelijk is aan v. Maw. ieder element komt minimaal 2 keer voor.

Discrete Wiskunde

29

3.2 Voorbeeld: Cijfer administratie Nu een wat groter voorbeeld. Gegeven een lijst van cijfers voor het vak discrete wiskunde cfs. We willen hier graag wat statistiek op plegen: Wat is het gemiddelde cijfer? Hoeveel (on)voldoendes zijn er? Hoe vaak werd er tussen de 7 en 8 gescoord? Komen er cijfers dubbel (of meer) voor? gem cfs = sum [c| c <- cfs] // # cfs onvoldoendes cfs = # [c| c <- cfs; c < 5.5] tussen7en8 cfs = # [c| c <- cfs; c >= 7 /\ c <= 8] dubbel cfs = or [# [k| k <- cfs; k = c] > 1| c <- cfs]

De eerste 3 uitwerking spreken voor zich, de laatste heeft misschien wat toelichting nodig: Gevraagd wordt of er een cijfer is dat dubbel voorkomt. Dit betekent dat het een probleem is van het type: or [??? | c <- cfs]

Hierbij moet ??? een test zijn die aangeeft of c meer dan een keer voorkomt. Alle voorkomens van c in cfs wordt gegeven door: [k| k <- cfs; k = c]

Nu nog testen of c vaker dan een keer voorkomt: # [k| k <- cfs; k = c] > 1

Het laatste ingevuld op de plaats van ??? geeft nu het gevraagde.


Geef verder lijstcomprehensies voor: Hoe vaak kwam het cijfer 8 voor. Hoe vaak werd het hoogste cijfer behaald.

Discrete Wiskunde

30

3.3 Verwerken voetbaluitslagen Gegeven zijn een lijst van uitslagen van voetbalwedstrijden (bv alle wedstrijden tot nu toe gespeeld) en een lijst van deelnemende teams, in de volgende vorm: uitslagen = [("ajax","psv",2,0),

|| (thuisclub, uitclub, doelp voor, doelp tegen)

("go ahead", "fc utrecht",0,3), ..... ] clubs = ["ajax","feyenoord","psv",...]

Bereken nu : Lijst van wedstrijdpunten (3 voor gewonnen, 1 voor gelijk, 0 voor verloren). Het totaal aantal punten per ploeg. Welke ploegen hebben thuis nooit verloren? Om de wedstrijdpunten te kunnen berekenen gebruiken we een functie die een uitslag omzet in punten voor beide teams: punten (c1,c2,p1,p2) = [(c1,3),(c2,0)], if p1 > p2 = [(c1,1),(c2,1)], if p1 = p2 = [(c1,0),(c2,3)], if p1 < p2

We kunnen nu eenvoudig een lijst van alle wedstrijdpunten maken: wedstrijdpunten uitslagen = [(c,p)| u <- uitslagen; (c,p) <- punten u]

We kunnen de wedstrijdpunten ook zonder hulpfunctie in een keer mbv. een lijstcomprehensie uitrekenen: wedstrijdpunten uitslagen = [(c1,0)| (c1,c2,p1,p2) <- uitslagen; p1 < p2] ++ [(c1,1)| (c1,c2,p1,p2) <- uitslagen; p1 = p2] ++ [(c1,3)| (c1,c2,p1,p2) <- uitslagen; p1 > p2] ++ [(c2,0)| (c1,c2,p1,p2) <- uitslagen; p1 > p2] ++ [(c2,1)| (c1,c2,p1,p2) <- uitslagen; p1 = p2] ++ [(c3,3)| (c1,c2,p1,p2) <- uitslagen; p1 < p2]

Het is een kwestie van smaak welke oplossing je prefereert. De eerste oplossing is wel korter, maar heeft een hulpfunctie nodig. Nu we de wedstrijdpunten hebben, is het eenvoudig het totaal aantal punten per club te berekenen: We moeten informatie per club hebben. Dit betekent een lijstcomprehensie van de vorm: [???| c <- clubs]

Hierbij is ??? een expressie die ons de punten van club c levert. De lijst van punten voor een club c wordt gegeven door.

Discrete Wiskunde

31

[p| (c1,p) <- wedstrijdpunten uitslagen; c1 = c]

Om het totaal aantal punten voor een club te krijgen, moeten we hiervan de som nemen: sum [p| (c1,p) <- wedstrijdpunten uitslagen; c1 = c]

Het laatste vullen we in op de plaats van ???: totalen uitslagen = [(c, sum [p| (c1,p) <- wedstrijdpunten uitslagen; c1 = c]) | c <- clubs]

3.4 Databases mbv. lijstcomprehensies Een tabel uit een database kan in Amanda worden voorgesteld als een lijst van tuples. Queries op een tabel kunnen vaak geformuleerd worden mbv. een lijstcomprehensie. Net als in SQL worden de queries pas echt interessant als er gegevens van meerdere tabellen gecombineerd moeten worden. We beginnen ons voorbeeld met een tabel van persoongegegevens. Om de leesbaarheid te vergroten voeren we eerst een aantal nieuwe typen in. Dit kan op de volgende manier: nieuwe naam == bestaand type

Voor onze eerste tabel definiëren we de volgende nieuwe typen: naam == [char] adres == [char] woonplaats == [char] leeftijd == num persoon

== (naam,adres,woonplaats,leeftijd)

personen :: [persoon] personen = [("Piet Augustein","de Kwakel 23","Leeuwarden",18), ("Freek de Boer","Beasterdyk 23","Sneek",23), ("Jacobien Bosch","Hegedyk 53","Bolsward",21), ("Richard Bouma","Tjerkepaad 12","St. Annaparochie",20), ("Cornelis vd Heide","Buorren 3","Ferwerd",19), ("Piet de Jong","Tongerwei 4","Birdaard",21), ("Sytze Lemstra","Oude dyk 78","Leeuwarden",19) ]

De tweede tabel is de resultaten tabel: vak == [char] cijfer == num stp == num resultaat

== (naam,vak,cijfer)

resultaten :: [resultaat] resultaten = [("Piet Augustein","Discrete Wiskunde",6),

Discrete Wiskunde

32

("Piet Augustein","Computer Organisatie",7), ("Piet Augustein","Programmeren 1",5), ("Piet Augustein","Database systemen 1",6), ("Piet Augustein","Project 1",8), ("Freek de Boer","Discrete Wiskunde",7), ("Freek de Boer","Computer Organisatie",9), ("Freek de Boer","Programmeren 1",6), ("Freek de Boer","Computer Organisatie",8), ("Freek de Boer","Telematica I",7), || etc. ]

Als laatste tabel hebben we de vakgegevens: vakgegeven == (vak,stp) vakken :: [vakgegeven] vakken = [("Discrete Wiskunde",3), ("Computer Organisatie",3), ("Programmeren 1",4), ("Database systemen 1",4), ("Project 1",7), ("Telematica I",3), ("Informatie Analyse",3)]

3.4.1 Queries over één tabel We gaan nu queries formuleren. We beginnen met eenvoudige queries over één tabel. Lijst van resultaten (Naam en Cijfer) voor het vak Discrete Wiskunde resdiwi = [(naam,cijfer)| (naam,vak,cijfer) <- resultaten; vak = "Discrete Wiskunde" ]

Namen van studenten uit Leeuwarden: naamLeeuw = [naam| (naam,adres,woonplaats,leeftijd) <- personen; woonplaats = "Leeuwarden" ]

Voor de leesbaarheid is het beter om de tuple velden waarin we niet zijn geïnteresseerd te vervangen door een streepje: naamLeeuw = [naam| (naam,_,woonplaats,_) <- personen; woonplaats = "Leeuwarden" ]


Formuleer queries voor:

Discrete Wiskunde

33

Hoogste cijfer voor Informatie Analyse.

3.4.3 Subqueries en hulpfuncties Net als in SQL is het soms noodzakelijk om een query binnen een query te gebruiken. Voorbeeld: Wat is het vak met de meeste studiepunten? maxstp = [(vak,stp)| (vak,stp) <- vakken; stp = maxstp ] where maxstp = max [stp| (_,stp) <- vakken]

Een alternatief zonder where clause is: maxstp = [(vak,stp)| (vak,stp) <- vakken; stp = max [stp| (_,stp) <- vakken] ]

Het nadeel van de laatste functie is dat max [stp| (_,stp) <- vakken] steeds weer opniew wordt uitgerekend. De eerste formulering verdient daarom de voorkeur (ook vanwege de leesbaarheid). We zien dus dat we hier de subquery als een hulpfunctie realiseren. Bij complexere queries is het vaak verstandig het resultaat op te bouwen mbv. een aantal hulpfuncties.


Welke student heeft het hoogste cijfer?

3.4.5 Queries over twee tabellen Bij queries over twee tabellen moet er vaak een join gemaakt worden. Binnen een lijstcomprehensie ziet dit er in de regel als volgt uit: [result_expr| t1 <- table1; t2 <- table2; join_conditie; overige condities ]

Als eerste voorbeeld: de resultaten van de studenten uit Leeuwarden [(naam,vak,cijfer)| (naam,_,woonplaats,_) <- personen; (naam2, vak, cijfer) <- resultaten; naam = naam2; woonplaats = “Leeuwarden” ]

Discrete Wiskunde

34


Studiepunten voor de vakken behaald door Cornelis vd Heide.

3.4.7 Complexe queries Bij complexe is het meestal handig eerst een aantal hulptabellen(functies) te definiëren voor deelresultaten. Voorbeeld: Het vak met de meeste onvoldoendes. Maak hiertoe eerst een hulptabel: vakOnvoldoendes met als type: [(vak,num)], waarin het tweede veld het aantal onvoldoendes voor het vak uit het eerste veld geeft. vakOnvoldoende

= [(vak,count) | (vak,_) <- vakken; count := # [cijfer| (_,vak2,cijfer) <- resultaten; vak = vak2; cijfer < 5.5 ] ]

meesteOnvoldoendes = [vak| (vak,o) <- vakOnvoldoende; o = meesteon] where meesteon = max [o| (vak,o) <- vakOnvoldoende]


Welke student heeft de meeste studiepunten behaald.

3.5 Analyse van teksten Gegeven is een tekst in de vorm van een string (lijst van karakters). We willen graag een statistische analyse op de tekst plegen. Eerst een aantal eenvoudige zaken: Maak een histogram van de verschillende letters. Het resultaat moet zijn een lijst van tuples van letter en het aantal keer dat de letter voorkomt. bv: het aantal keren dat 'a' in een tekst voorkomt: # [c| c <- tekst; c = 'a']

Voor alle letters wordt dit nu: histogram tekst = [(c,# [k| k <- tekst; k = c])| c <- "abcdefghijklmnopqrstuvwxyz"]

Nu een wat lastiger probleem: Hoe vaak komt de combinatie "de" voor?

Discrete Wiskunde

35

Hiervoor bestaan verschillende oplossingen. Eerst een aantal 'dure' oplossingen: # [i| i <- [0..#tekst-2]; tekst ! i = 'd' /\ tekst ! (i+1) = 'e'] # [i| i <- [0..#tekst-2]; take 2 (drop i) tekst = "de"]

En dan nu de efficiente (en fraaiere) oplossing mbv. zip. We zippen hiertoe tekst met tl tekst, waardoor we een lijst van paren van een karakter en zijn opvolger in de tekst krijgen: # [(c1,c2)| c1,c2 <- tekst, tl tekst; c1 = 'd' /\ c2 = 'e']

Nog wat lastiger: Hoeveel woorden bevat de tekst. Om dit probleem op te kunnen lossen, moeten we ons eerst realiseren wat een woord is. Woorden worden gescheiden door interpunctie tekens. Dit zijn: spatie, punt, komma en puntkomma. Het is echter niet voldoende het aantal interpunctie tekens in een tekst te tellen, omdat er best meerdere spaties achter elkaar kunnen staan. Dit kunnen we ondervangen door niet het aantal interpunctie tekens te tellen, maar combinaties van een interpunctie teken gevolgd door een niet interpunctie teken. Dus bv: (' ', 'd') of ('.','e'). Hiertoe zippen we de tekst weer met zijn tl. # [(c1,c2)| c1, c2 <- tekst,tl tekst; interpunctie c1 /\ ~ (interpunctie c2)]

De functie interpunctie kunnen we als volgt definiëren: interpunctie c = member " ;,." c

~ betekent niet. Op deze manier vergeten we echter het eerste woord, tenminste, als er een eerste woord is. Dit komt omdat er aan het eerste woord geen interpunctieteken vooraf gaat. Dit kunnen we ondervangen door aan het begin van de tekst een 'kunstmatig' interpunctieteken te zetten: # [(c1,c2)| c1, c2 <- '.' : tekst, tekst; interpunctie c1 /\ ~ (interpunctie c2)]

Let op: tl in het tweede argument van de zip komt nu te vervallen!


Schrijf een lijstcomprehensie voor: welke letter komt het meeste voor. Hierboven hebben we het aantal keren dat "de" in een tekst voorkwam geteld. Tel nu eens het aantal keren dat het woord "de" voorkomt in de tekst. Lastig: Wat is de lengte van het langste woord. Tip maak eerst functies voor het begin en eind van ieder woord.

Discrete Wiskunde

36

3.5.2 Lay-out Als we een lijst van getallen netjes naast elkaar op het scherm willen laten zien, dan moeten we de getallen eerst naar strings converteren. Hiervoor bestaat in Amanda een speciale functie itoa. Verder heb je, om een lijst van strings aan elkaar te plakken, de functie concat, die een lijst van lijsten aaneenrijgt tot een lange lijst: > concat [itoa n ++ " "| n <- [1..10]] 1 2 3 4 5 6 7 8 9 10

Vraag

Waarom kan dit niet met: [n ++ " " | n <- [1..10]]? Opgave 3.7

Definieer de functie histogram xs die voor een lijstje van getallen een histogram uitprint. > histogram [3,1,5,8,2,3] **** ** ****** ******** *** ****

Het zou nog mooier zijn als we aan ieder rijtje sterren het bijbehorende getal vooraf laten. Een problem hierbij echter is, dat als het getal uit meerdere cijfers bestaat, de layout van het histogram niet meer klopt: 8: ******** 10: **********

Gelukkig valt hier wat aan te doen. Amanda heeft een drietal uitlijningsfuncties: ljustify, cjustify en rjustify. ljustify n xs, vult de string xs aan de rechterkant aan met spaties tot een lengte n. Ga zelf na wat cjustify en rjustify doen. Pas nu histogram aan volgens het volgende voorbeeld: > histogram [3,1,5,8,14,2,3] 3

: ****

1

: **

5

: ******

8

: *********

14 : *************** 2

: ***

3

: ****

Definieer, gewapend met de kennis uit de vorige opgave, de functie tafel n, die voor gegeven n de tafel van vermenigvuldiging voor n print: > tafel 4 1

* 4 =

2

* 4 =

4 8

3

* 4 =

12

4

* 4 =

16

5

* 4 =

20

Discrete Wiskunde

37

6

* 4 =

24

7

* 4 =

28

8

* 4 =

32

9

* 4 =

36

10 * 4 =

40

3.6 Functies op lijsten We hebben al een aantal voorgedefinieerde functies op lijsten bekeken zoals: max, min, sum, prod etc. Verder hebben we gezien dat sommige functies mbv. een lijstcomprehensie gedefinieerd kunnen worden. Maar dit geldt niet voor alle functies op lijsten. Probeer maar eens bv. de functie sum mbv. een lijstcomprehensie te definiëren. Als we zelf zo'n functie moeten definiëren, dan gaat dit altijd mbv. een zgn. recursieve definitie. Een functie heet recursief als hij zichzelf aanroept. Laten we eens beginnen met de functie die het aantal elementen van een lijst uitrekent: aantalEl xs = 0, if xs = [] = 1 + aantalEl (tl xs), otherwise

In woorden: Het aantal elementen van een lege lijst is 0; het aantal elementen van een niet lege lijst is 1 plus het aantal elementen van de staart (tl) van de lijst. Vraag

Schrijf mbv. deze definitie eens aantalEl [1,2,3] uit.

3.6.1 Patronen Ipv. met if en otherwise kunnen we in Amanda functies vaak ook op een elegantere manier definiëren. Dit geldt met name voor recursieve functies. aantalEl [] = 0 aantalEl (x:xs) = 1 + aantalEl xs

Dit heet een definitie mbv. patronen. Hier zijn [] en (x:xs) de patronen. Bij een aanroep van de functie wordt van boven naar beneden het argument van de functie met de patronen vergeleken. Als het argument een lege lijst is ‘matched’ het eerste patroon en wordt de eerste definitie uitgevoerd. Voor een niet lege lijst ‘matched’ het tweede patroon. Dit patroon is hier (x:xs). We hebben eerder gezien dat : de operator is om een element voor aan een lijst toe te voegen. Als we lijst met het patroon (x:xs) ‘matchen’ dan wordt het eerste element van de lijst (hd) gebonden aan x en de rest van de lijst (tl) aan xs. Dit kan natuurlijk alleen voor een niet lege lijst, maar dit is altijd het geval omdat een lege lijst 'matched' met het bovenste patroon. Nu een wat moeilijker voorbeeld. We willen graag een definitie geven voor de ! operator. Als we ! als functie schrijven, dan zou een aanroep er als volgt uit zien: elem 3 [1,2,3,4,5,6,7] elem 0 (x:xs) = x elem n (x:xs) = elem (n-1) xs

Discrete Wiskunde

38

De recursie loopt hier over n, maar we gebruiken toch patronen voor de lijst.


Definieer nu zelf de functie sum, die de som van alle elementen van een lijst berekent. Definieer mbv. patronen de functies hd en tl. Denk eraan, hd en tl zijn niet gedefinieerd voor lege lijsten! Ga na wat er gebeurt als je elem aanroept voor een lege lijst. Probeer nu zelf op recursieve wijze de functies member, drop, take, min en max te definiëren. Lastig: min en max kunnen wel mbv. een lijstcomprehensie gedefinieerd worden, probeer deze definitie te geven. Tip: bedenk eerst wat het betekent als een element het maximum van een lijst is.

3.6.3 Ingewikkelder patronen Patronen in lijsten kunnen best ingewikkelder zijn dan in het bovenstaande voorbeeld. De volgende functie controleert of een lijst is gesorteerd van klein naar groot: isSorted []

= True

isSorted [x] = True isSorted (x:y:xs) = x <= y /\ isSorted (y:xs)

Het idee hierbij is: • de lege lijst is gesorteerd • een lijst bestaande uit een element is gesorteerd • een lijst bestaande uit minimaal twee elementen is gesorteerd als het eerste element kleiner of gelijk is als het tweede element en vanaf het tweede element de lijst gesorteerd is. We zien hier een tweetal nieuwe patronen: [x] 'matched' met een lijst van lengte precies een, het ene element wordt gebonden aan x. (x:y:xs) 'matched' met een lijst van lengte tenminste 2. Het eerste element wordt gebonden aan x, het tweede aan y en de rest aan xs. Opmerking In de tweede regel: isSorted [x] = True, komt in het patroon de variabele x voor die aan de rechter kant niet wordt gebruikt. In dit soort gevallen mag de variabele door _ vervangen worden. De tweede regel wordt dan: isSorted [_] = True

In lijstcomprehensies mogen variabelen aan de linkerkant van generatoren, die verder niet gebruikt worden, ook worden vervangen door _. herhaal n s = [s| _ <- [1..n]]

Discrete Wiskunde

39

Het gebruiken van _ ipv. een variabele naam voorkomt niet alleen het bedenken van namen, maar zorgt ook voor een betere leesbaarheid van programma's.

Discrete Wiskunde

40

4. Recursie en inductie 4.1 Recursie Een recursieve functie is een functie die gedefinieerd is m.b.v. zichzelf. We hebben daar al diverse voorbeelden van gezien: fac 0 = 1 fac n = n * fac (n-1) aantalEl []

= 0

aantalEl (x:xs) = 1 + aantalEl xs isSorted []

= True

isSorted [x]

= True

isSorted (x:y:xs) = x <= y /\ isSorted (y:xs)

Deze definities hebben een vast patroon: voor een aantal basisgevallen worden directe definities gegeven en voor de andere gevallen wordt de functie zelf weer aangeroepen maar met parameters die ‘dichter’ bij de basisgevallen zijn. Zulke definities leiden altijd tot een eindige berekening zoals uit de volgende voorbeelden blijkt: fac 4 = 4 * fac 3 = 4 * 3 * fac 2 = 4 * 3 * 2 * fac 1 = 4 * 3 * 2 * 1 * fac 0 = 4 * 3 * 2 * 1 * 1 = 24 aantalEl [1, 2, 3] = 1 + aantalEl [2, 3] = 1 + 1 + aantalEl [3] = 1 + 1 + 1 + aantalEl [] = 3 isSorted [1, 3, 2, 4, 5] = 1 <= 3 /\ isSorted [3, 2, 4, 5] = isSorted [3, 2, 4, 5] = 3 <= 2 /\ isSorted [2, 4, 5] = False

Er zijn ook wel recursieve definities denkbaar die niet tot een eindige berekening leiden zoals de volgende definitie van de faculteitsfunctie: fac n = fac (n+1) / (n+1)

Het eigenaardige is dat deze definitie in wiskundige zin correct is, maar voor berekeningen tot niets leidt. Nog krasser is de volgende definitie:

Discrete Wiskunde

41

fac n = fac n

Ook dat is in wiskundige zin een ware bewering, maar voor berekeningen heb je er niets aan.


Beredeneer dat de volgende sorteerfuncties correct zijn en altijd tot een eindige berekening leiden (welke is de snelste ?) a.

minsort [] = [] minsort xs = minxs : minsort (xs -- [minxs]) where minxs = min xs

b.

quicksort []

= []

quicksort (x:xs) = quicksort [y | y <- xs; y <= x] ++ [x] ++ quicksort [y | y <- xs; y > x]

Opgave 4.2

De fibonacci-reeks is [1, 1, 2, 3, 5, 8, 13, 21 ...] Geef een recursieve definitie van de functie fib n, die het n-de element van deze reeks oplevert. (voor alle duidelijkheid: fib 0 = 1, fib 1 = 1, fib 2 = 2, fib 3 = 3, fib 4 = 5 enz.) Opgave 4.3

De functie sum die de som van de elementen van een lijst berekent kunnen we als volgt definieren met een hulpfunctie, die een zogenoemde opsparende parameter gebruikt om tussenresultaten in te bewaren: mysum xs = add 0 xs add s []

= s

add s (x:xs) = add (s+x) xs

Definieer op net zo’n manier de functie reverse die een lijst omdraait. myreverse xs = rev [] xs rev s []

= s

rev s (x:xs) = ....

4.2 Inductie Inductie is een wiskundige bewijstechniek gebaseerd op het idee dat de verzameling van natuurlijke getallen (in Amanda notatie: [0..]) recursief gedefinieerd kan worden:

Discrete Wiskunde

42

natuurlijkeGetallen = from 0 from n = n : from (n+1)

Hieruit volgt het inductieprincipe: een bewering p is waar voor alle natuurlijke getallen als • p is waar voor 0 en • als p waar is voor n, dan is p waar voor n+1 Een andere formulering is: een bewering p is waar voor alle natuurlijke getallen als • p is waar voor 0 en • als p waar is voor alle natuurlijke getallen kleiner dan n, dan is p waar voor n Hiermee kunnen we wiskundig bewijzen dat de oorspronkelijke definitie van de faculteitsfunctie voor alle natuurlijke getallen tot een eindige berekening leidt. De bewering is dan: p n = “fac n leidt tot een eindige berekening” Omdat fac 0 = 1 is de berekening van fac 0 eindig dus p is waar voor 0. Als p n waar is dan leidt fac n tot een eindige berekening. Dan is fac (n+1) te berekenen volgens fac (n+1) = (n+1) * fac n. De berekening voor fac (n+1) is daarmee ook eindig. M.a.w. p geldt voor n+1. Volgens het inductieprincipe geldt p nu voor alle natuurlijke getallen. Ofwel voor alle natuurlijke getallen leidt de faculteitsfunctie tot een eindige berekening. Net zo kunnen we bewijzen dat de functie aantalEl voor alle eindige lijsten leidt tot een eindige berekening. We nemen dan als bewering: p n = “de functie aantalEl leidt tot een eindige berekening voor alle lijsten met lengte n” Wiskundigen gebruiken inductie om te controleren of bepaalde formules kloppen. Bijvoorbeeld: voor alle natuurlijke getallen n geldt: sum [1..n] = n * (n+1) / 2 De bewering p n is nu sum [1..n] = n * (n+1) / 2 Voor 0 is de bewering waar, want sum [1..0] = 0 en 0 * (0+1) / 2 = 0 Als de bewering waar is voor n, dan geldt sum [1..n] = n * (n+1) / 2. We gaan nu kijken of de bewering ook waar is voor n+1: sum[1..n+1] = sum[1..n] + (n+1) = n*(n+1)/2 + (n+1) = (n+2) * (n+1) / 2 = (n+1) * ((n+1)+1)/2

Inderdaad klopt de bewering ook voor n+1.


Bewijs dat de functie quicksort voor alle eindige lijsten leidt tot een eindige berekening.

Discrete Wiskunde

43

Opgave 4.5

De functie altsum is (informeel) gedefinieerd als: altsum n = 1 - 2 + 3 - 4 .. (+/-) n

Bewijs dat voor alle natuurlijke getallen n geldt: altsum n = -n / 2

,if n mod 2 = 0

= (n+1) / 2 ,otherwise

4.3 Torens van Hanoi In het verre verleden stonden er in Hanoi 3 palen met op paal 0 een stapel van 64 schijven allemaal van verschillende diameter en nooit een grotere bovenop een kleinere schijf. Een monnik was bezig de schijven naar paal 2 te verplaatsen. Hij kon maar een schijf per keer verplaatsen en er mocht nooit een grotere bovenop een kleinere komen te liggen. Verder moesten de schijven altijd om een van de palen worden gelegd. De vraag was nu: als de monnik er 1 minuut over deed om een schijf te verplaatsen, hoe lang zou het duren voor de hele toren verplaatst was ? Om de gedachten te bepalen zullen we eerst een wat kleiner voorbeeld uitwerken: 1 2 3 4 paal 0 paal 1 paal 2

2 3 4 1 paal 0 paal 1 paal 2







Werk het nu zelf helemaal uit. We zien er misschien een patroon in:

Discrete Wiskunde

44

• in een oneven zet wordt de kleinste schijf verplaatst (en wel 1 paal circulair verder) • in een even zet wordt een andere schijf verplaatst (hiervoor is maar 1 mogelijkheid) Na wat experimenteren met torens van verschillende groottes kunnen we inzien dat bij een toren van n schijven in een oneven zet telkens de kleinste schijf (1 + n mod 2) palen verder verplaatst wordt en in een even zet telkens een andere schijf verplaatst wordt. Bovendien hebben we misschien gezien dat er (2^n - 1) verplaatsingen nodig zijn. Hoe kunnen we dat wiskundig hard maken ? Er is een recursief algoritme: Om een toren van 0 schijven van paal 0 naar paal 2 te verplaatsen, hoeven we niets te doen. Om een toren van n schijven van paal 0 naar paal 2 te verplaatsen, verplaatsen we eerst een toren van (n-1) schijven van paal 0 naar paal 1, dan verplaatsen we de grootste schijf van paal 0 naar paal 2 en dan verplaatsen we een toren van (n-1) schijven van paal 1 naar paal 2. In Amanda zouden we een functie hanoi kunnen definieren die een lijst van verplaatsingen oplevert: hanoi 0 van via naar = [] hanoi n van via naar = hanoi (n-1) van naar via ++ [(van, naar)] ++ hanoi (n-1) via van naar


Bewijs met inductie dat geldt #(hanoi n van via naar) = 2^n - 1

4.4 Recursieve bomen (extra) In Amanda kun je de functie graphicsout gebruiken om te tekenen. Het tekenen gebeurt in een vierkant met coordinaten van (-1, -1) tot (1, 1).


De volgende opgave moet met de grafische versie van Amanda gemaakt worden. Probeer het volgende uit in Amanda: graphicsout[GraphPolyLine 2 [(0, 0), (0.5, 0), (0.5, 1), (0, 0)], GraphDisc 5 (-0.5, -0.5) (0, 0)] We willen nu een recursieve boom tekenen die er als volgt uitziet:

Discrete Wiskunde

45

Informeel kunnen we deze boom beschrijven als stam + linker tak + rechter tak, waarbij de linker en de rechter tak er weer net zo uitzien als de hele boom alleen een stukje verplaatst en over een hoek gedraaid. Een boom kunnen we beschouwen als een lijst van lijnstukken, die we met een functie tekenBoom tekenen: tekenBoom boom = graphicsout[GraphPolyLine 0 lijnstuk | lijnstuk <- boom]

Een boom van hoogte n kunnen we nu definieren als: boom 0 = [] boom n = [[(0, 0), (0, 0.3)]] ++ /* de stam */ links (boom (n-1)) ++ rechts (boom (n-1))

Hierbij zijn links en rechts functies die een boom op de goede manier verdraaien, verschuiven en verkleinen. Daarom definieren we eerst een aantal meetkundige functies:

Discrete Wiskunde

46

vergroot factor (x, y) = (factor*x, factor*y) draai hoek (x, y) = (c*x+s*y, -s*x+c*y) where c = cos hoek s = sin hoek verschuif (dx, dy) (x, y) = (x+dx, y+dy)

De functies links en rechts worden dan: links boom = [[f p1, f p2] | [p1, p2] <- boom] where f = verschuif (0, 0.3) . draai (-0.7) . vergroot 0.7 rechts boom = [[f p1, f p2] | [p1, p2] <- boom] where f = verschuif (0, 0.3) . draai (0.7) . vergroot 0.7

Met al dit voorwerk kunnen we een boom laten tekenen via > tekenBoom (boom 7)


Experimenteer in Amanda met bovenstaande definities. Uit hoeveel lijnstukken bestaat boom n ? Opgave 4.9

Het berekenen van de lijnstukken gaat nog niet erg vlug, omdat de linker en rechter boom telkens helemaal opnieuw berekend worden. Een veel sneller resultaat krijgen we als volgt: recboom = boom where boom = [[(0, 0), (0, 0.3)]] ++ [lijnstuk | [p1, p2] <- boom; lijnstuk <- [[fl p1, fl p2], [fr p1, fr p2]]] where fl = verschuif (0, 0.3) . draai (-0.7) . vergroot 0.7 fr = verschuif (0, 0.3) . draai (0.7) . vergroot 0.7

Je kunt dit laten tekenen via (nb: het is een oneindige definitie) > tekenBoom recboom

Experimenteer met deze definitie. Probeer te begrijpen hoe deze ingenieuze constructie werkt.

Discrete Wiskunde

47

5. Recursieve datastructuren en Bomen We hebben al gezien dat recursie een uiterst krachtig middel is om functies mee te definieren. We zullen nu zien dat we recursie ook kunnen gebruiken om krachtige datastructuren te maken.

5.1 Zelf datastructuren maken Amanda bevat een aantal voorgedefinieerde types zoals: num, char, bool en lijsten hiervan. Soms hebben we behoefte aan andere datatypen. We kunnen deze in Amanda op eenvoudige wijze maken. Voorbeeld In een applicatie spelen de maanden van het jaar en hun lengte een rol. We kunnen deze maanden natuurlijk als een string definieren, maar dit geeft soms aanleiding tot vervelende fouten: maanden = [(“Januari”,31),(”Februari”,28),....]

We kunnen de functie lengte nu als volgt definieren: lengte m = hd [l | (n,l) <- maanden; n = m]

Maar als je deze functie nu per ongeluk als volgt aanroept: lengte “januari”

// let op januari met kleine letter!!

Dan leidt dit tot de run-time foutmelding: hd of empty list. We hadden liever gezien dat er bij het interpreteren al een foutmelding wordt gegeven. Dit kan bereikt worden door het volgende nieuwe type te definieren: maand ::=

Januari | Februari | Maart | April | Mei | Juni | Juli | Augustus | September | Oktober | November | December

Let hierbij op ontbreken van aanhalings tekens en het gebruik van |. De hoofdletters zijn verplicht! We hebben nu een nieuw type maand gedefiniëerd en hierbij aangegeven welke waarden dit type kan aannemen. We definiëren nu maandlengtes en lengte als volgt: maandlengtes = [(Januari,31),(Februari,28),(Maart,31),...] lengte m = hd [l | (n,l) <- maandlengtes; n = m]

Een foutieve aanroep zoals: lengte Janauri

wordt nu al bij het vertalen van het programma opgemerkt.

Discrete Wiskunde

48

Zelfgedefinieerde types kunnen ook ingewikkelder zijn. Beschouw hiertoe het volgende type temperatuur: temperatuur ::= Celcius num | Fahrenheit num

Een temperatuur kan in Celcius of in Fahrenheit worden gegeven. Elementen van dit type zijn: Celcius 23, Fahrenheit 43. Een lijst met elementen van het type temperatuur zou er nu als volgt uit kunnen zien: [Celsius 23, Fahrenheit 40,Celsius 88]

We kunnen nu functies definieren door gebruik te maken van patroonherkenning. koud (Celcius t)

= t < 0

koud (Fahrenheit t)

= t < 32


Maak een functie convert die een temperatuur in Celsius in een temperatuur in Fahrenheit converteert. De formule die je hier bij moet gebruiken is: F = 1.8 * C + 32.

5.2 Binaire Bomen Een belangrijke datastructuur is de binaire boom. Er bestaan verschillende versies van binaire bomen. Hier bekijken we de binaire boom van getallen: binboom ::= Leeg | Knoop num binboom binboom

Deze definitie heeft een recursief karakter, immers binboom komt ook aan de rechterkant van de definitie voor. Een boom is dus of leeg of bestaat uit een knoop met daarin een getal (label) en daaronder een linker en rechter subboom. Dit lijkt op de definitie van een lijst, die ook of leeg is of bestaat uit een element head en een andere lijst tail. Het verschil is hier dat we nu een dubbele vertakking hebben ipv. één. Voorbeelden van binaire bomen: Leeg

|| een lege boom

Knoop 1 Leeg Leeg

|| een boom met één label

Knoop 1 (Knoop 2 (Knoop 3 Leeg Leeg) Leeg) (Knoop 4 Leeg Leeg))

Bomen kunnen overzichtelijker in een plaatje weergeven worden. De laatste boom ziet er dan als volgt uit:

Discrete Wiskunde

49

1 / \ ------

------

2

4

/ -3

Terminologie • De wortel van een boom is de bovenste knoop. • Een knoop heet een uiteinde of blad als de twee subbomen in deze knoop beide leeg zijn. • Een pad is een rij van labels van de wortel tot en met een blad. • De diepte van een boom is de lengte van het langste pad. • Een boom heet volledig als alle paden even lang zijn. • Een boom heet evenwichtig als in iedere knoop de dieptes van de twee subbomen ten hoogste één verschillen.

5.2.1 Functies op bomen Functies op bomen worden altijd recursief gedefinieerd. De recursieve structuur van de boom zelf laat ons geen andere mogelijkheid. Laten we eerst een functie definieren die het aantal getallen in een boom telt: aantalGet Leeg = 0 aantalGet (Knoop g links rechts) = 1 + aantalGet links + aantalGet rechts

Een lege boom bevat 0 getallen, een boom bestaande uit een knoop en twee subbomen bevat 1 plus het aantal elementen van de linker subboom plus het aantal elementen van de rechter subboom.

5.2.2 Afdrukken van een boom Je kunt een boom op verschillende manieven afdrukken. De belangrijkste zijn, pre-order, inorder en post-order. In-order: druk voor iedere knoop eerst de elementen van de linker subboom af, dan je eigen label en dan de elementen van de rechter subboom. Pre-order: druk voor iedere knoop eerst je eigen label af, dan de elementen van de linker subboom af en dan de elementen van de rechter subboom. Post-order: druk voor iedere knoop eerst de elementen van de linker subboom af, dan de elementen van de rechter subboom en dan je eigen label Voorbeeld Knoop 1 (Knoop 2 (Knoop 3 Leeg Leeg)

(Knoop 4

(Knoop 5 (Knoop 6 Leeg Leeg)

Discrete Wiskunde

Leeg Leeg) )

(Knoop 7

Leeg Leeg) )

50

1 / \ ------

------

2

5

/ \

/ \

--

--

3

-4

6

-7

in-order:

[3,2,4,1,6,5,7]

pre-order:

[1,2,3,4,5,6,7]

post-order:

[3,4,2,6,7,5,1]


Definieer een functie diepte. Opgave 5.3

Definieer een functie sumtree die de som van alle labels in een boom berekent. Opgave 5.4

Definieer een functie sumleaf die de som van alle bladeren berekent. Opgave 5.5

Definieer een functie komtvoor die gegeven een boom t en een getal n nagaat of het getal in de boom voorkomt. Opgave 5.6

Definieer een functie maaltien die alle labels met 10 vermenigvuldigt. Opgave 5.7

Definieer een functie maptree die een functie f :: num -> num op alle labels van een boom toepast. Opgave 5.8

Definieer een functie spiegelBoom die een boom spiegelt in een verticale as door het midden. Opgave 5.9

Definieer functies, in_order, pre_order en post_order voor het afdrukken van een boom. Opgave 5.10

Definieer een functie paden die alle paden van een boom geeft (het resultaat is dus een lijst van lijsten van getallen).

Discrete Wiskunde

51

Opgave 5.11

Definieer een functie isVolledig die na gaat of een boom volledig is. Opgave 5.12

Definieer een functie isEvenwichtig die na gaat of een boom evenwichtig is. Opgave 5.13

Definieer een functie maakBoom die een lijst van getallen omzet in een evenwichtige boom. Hint: doe dit door de lijst steeds te halveren.

5.2.4 Binaire Zoekbomen Een belangrijke categorie van bomen zijn de binaire zoekbomen. Deze hebben dezelfde definitie als de voorgaande bomen en moeten voldoen aan de volgende extra voorwaarden: In iedere knoop geldt:

de labels in de linker subboom hebben een waarde kleiner dan de knoop de labels in de rechter subboom hebben een waarde groter dan de knoop

Er mogen dus ook geen dubbele waarden voorkomen. Voorbeeld 5 / \ ------

------

2

11

/ \ --

/ \ --

1

-4

--

8

/

13

/ \

3

7

9

/

\

6

10

Binaire zoekbomen worden gebruikt voor de opslag van informatie. Om ze goed te kunnen gebruiken hebben we de volgende functies nodig: • • •

insertboom: om een getal toe te voegen aan een bestaande boom. printboom: on de inhoud van een binaire zoekboom af te drukken. remboom: om een label uit een binaire zoekboom te verwijderen.

De definitie van de functie insertboom is recht toe recht aan. insertboom n Leeg = Knoop n Leeg Leeg insertboom n (Knoop m l r) = Knoop m (insertboom n l) r, if n < m = Knoop m l (insertboom n r), if n > m = Knoop m l r, otherwise

Discrete Wiskunde

52

maakboom zet een lijst van getallen om in een binaire zoekboom door ze één voor één aan een boom toe te voegen. maakboom [] = Leeg maakboom (x:xs) = insertboom x (maakboom xs)

Oefening Wat is het resultaat van maakboom [7,3,5,2,1,6]. printboom drukt de boom in-order volgorde af. Het resultaat is dus een gesorteerde lijst van getallen: printboom Leeg = [] printboom (Knoop n l r) = printboom l ++ [n] ++ printboom r

De moeilijkste functie is remboom. Om een knoop te kunnen verwijderen uit de boom moeten we, als het element dat we verwijderen niet een blad is, het opengevallen gat weer opvullen. Als een van beide subbomen leeg is, is dit geen probleem. We vervangen dan de knoop zelf door de niet lege subboom. Als beide subbomen niet leeg zijn, dan vervangen we het label van de knoop door de kleinste waarde uit de rechter subboom, waarna we deze kleinste waarde (recursief) uit de rechter subboom verwijderen. Om dit te kunnen doen hebben we een hulpfunctie minboom nodig die de kleinste waarde uit een boom oplevert. Voorbeeld Als we 10 willen verwijderen uit de volgende boom, geeft dat geen probleem, omdat 10 een blad is. 5 / \ ------

------

2

11

/ \

--

/ \

--

1

-4

--

8

/

13

/ \

3

7

9

/

\

6

10

We kunnen gewoon de knoop die 10 bevat vervangen door de lege knoop. 5 / \ ------

------

2

11

/ \

--

/ \

--

1

-4

--

8

/

13

/ \

3

7

9

/ 6

Discrete Wiskunde

53

In het volgende voorbeeld verwijderen we een knoop (met label 4) met één subboom. We hoeven nu alleen de knoop te vervangen door de niet lege subboom. 5 / \ ------

------

2

11

/ \

--

/ \

--

1

-3

--

8

13

/ \ 7

9

/

\

6

10

In het laatste voorbeeld willen een knoop (met label 8) verwijderen met twee niet lege subbomen. Hiertoe moeten we 8 vervangen door het minimum van de rechter subboom (9), waarna we 9 weer verwijderen uit deze subboom. 5 / \ ------

------

2

11

/ \ --

/ \ --

1

-4

--

9

/

13

/ \

3

7

10

/ 6

minboom (Knoop n Leeg r) = n minboom (Knoop n l r)

= minboom l

remboom n Leeg = Leeg remboom n (Knoop m Leeg Leeg) = Leeg, if n=m = Knoop m Leeg Leeg,otherwise remboom n (Knoop m Leeg r)

= r, if n = m = Knoop m Leeg (remboom n r), if n > m = Knoop m Leeg r, otherwise

remboom n (Knoop m l Leeg)

= l, if n = m = Knoop m (remboom n l) Leeg, if n < m = Knoop m l Leeg, otherwise

remboom n (Knoop m l r)

= Knoop minr l (remboom minr r), if m = n = Knoop m (remboom n l) r, if n < m = Knoop m l (remboom n r), otherwise

where minr = minboom r


Discrete Wiskunde

54

Geef een efficiente versie van de functie bevat die controleert of een zoekboom een gegeven element bevat. Opgave 5.15

Definiëer een functie sorteer die een lijst van getallen sorteert door deze eerst om te zetten in binaire zoekboom en deze zoekboom daarna in pre-order volgorde af te drukken.

Discrete Wiskunde

55

6. Huffman codering 6.1 Huffman Bomen We zullen nu een toepassing van binaire bomen bekijken. Het betreft hier het coderen van teksten op een dusdanige manier dat ze zo weinig mogelijk ruimte in beslag nemen. Normaal gesproken neemt in een tekst ieder karakter precies 1 byte (8 bits in beslag). Een tekst van 1024 karakters neemt dus 1 kbyte in beslag. Door slimme codering kan dit veel efficiënter. Een van deze coderingstechnieken is Huffman codering. Dit is een zgn. variabele lengte codering. Dit betekent dat niet ieder karakter evenveel ruimte in beslag neemt. Deze techniek is op het volgende idee gebaseerd: •

Karakters die vaak voorkomen in een tekst hebben een kortere codering dan karakters die minder vaak voorkomen

•

De ruimte die een karakter in beslag neemt is minimaal 1 bit. Er is theoretisch een maximum dat net zo lang is als het aantal verschillende karakters dat kan voorkomen. In de praktijk wordt dit maximum vrijwel nooit bereikt.

•

We moeten voorkomen dat een korte code het beginstuk is van een langere code. Bv. als ‘e’ coderen als 1, ‘t’ als 10 en ‘h’ als 11, dan kan 1110 zowel voor “eet” als “ht” staan.

Door gebruik te maken van binaire bomen kan dit laatste probleem eenvoudig voorkomen worden. Bekijk hiertoe de volgende binaire boom: / \ -----/ \ -n

-----e

-t

We zien hier dat alleen de bladeren (uiteinden) labels hebben. De interne knopen hebben geen label. De datastructuur die bij dit soort bomen hoort is als volgt: huffboom ::= Blad char | Knoop huffboom huffboom

De boom geeft aan hoe we de karakters ‘n’, ‘t’ en ‘e’ moeten coderen. Om de code te vinden voor een karakter volgen we de weg vanaf de top van de boom tot het karakter. Iedere keer als we linksaf gaan noteren we een 0, als we rechtaf gaan noteren we een 1. Dus voor ‘n’ wordt de code 00, voor t 01 en voor e 1. Merk op dat we nu niet het probleem hebben dat een korte code (die van ‘e’) het begin is van een andere code (‘n’ of ‘t’). Hiervoor is automatisch gezorgd door de codering mbv. een boom. Als we nu het woord “teen” willen coderen krijgen we de code 011100.

Discrete Wiskunde

56

Oefening Geef zelf de codering van het woord “eten”. Mbv. van bovenstaande boom kunnen we natuurlijk alleen maar woorden met ‘e’, ‘t’ en ‘n’ coderen. Verder gaan we ervan uit dat de ‘e’ het meest voorkomt. Decoderen gaat op analoge wijze. Als we de code 001101 willen decoderen, beginnen we boven in de boom en volgen een pad naar beneden mbv. de code: Eerst gaan we twee keer linksaf (00) en komen bij ‘n’. Dan beginnen we weer boven en gaan we rechtsaf (1) en komen bij ‘e’. Daarna nog een keer een ‘e’. En tot slot een ‘t’. 001101 staat dus voor “neet”.


Beschouw de volgende huffman-code-boom. / \ --------------

--------------

/ \ ------

/ \ ------

‘ ‘

-----e

------

/ \ --

/ \ --

h

--

/ \ l

--

/ \ o

/ \ / \

/ \ t

a

m r , g

‘ ‘ staat hier voor spatie. Codeer nu de volgende woorden: “moer”, “geel”, “tol” en de zin “hallo, hoe gaat het” (denk om de spaties). Decodeer de volgende codes mbv. bovenstaande boom: 1100110110111000 110111111111111001 110011011101000100011110001110101101

6.2 Codeer- en decodeer-algoritmen voor Huffman bomen We zullen nu codeer en decodeer algoritmen in Amanda maken.

6.2.1 Codeer De datastructuur voor de Huffman-boom was: huffboom ::= Blad char | Knoop huffboom huffboom

Discrete Wiskunde

57

Om te kunnen coderen moeten we eerst uit de Huffman boom de codes voor alle karakters (bladeren) daarin afleiden. Dit gaat mbv. de functie boomToTabel: boomToTabel (Blad c)

= [(c,[])]

boomToTabel (Knoop l r)

=

[(c,'0':code)| (c,code) <- boomToTabel l] ++ [(c,'1':code)| (c,code) <- boomToTabel r]

boomToTabel werkt van de bladeren af naar boven. Controleer zelf de werking van boomToTabel aan de hand van een eenvoudige boom. Voor de boom uit de vorige opgave geeft boomToTabel de onderstaande tabel: [('t', "000"), ('a', "001"), ('e', "01"), ('h', "100"), ('l', "1010"), ('o', "1011"), ('m', "11000"), ('r', "11001"), (',', "11010"), ('g', "11011"), (' ', "111")]

Het is nu eenvoudig een tekst te coderen mbv. deze tabel. Dit gaat met de functies codeer en vindCode. vindCode zoekt de code van een karakter op in de tabel. codeer zoekt voor alle karakters in de tekst de code op en plakt deze codes aan elkaar. codeer codetabel txt = concat [vindCode c codetabel | c <- txt] vindCode c codetabel = hd [code| (l,code) <- codetabel; l = c]

6.2.2 Decoderen Decoderen is een kwestie van mbv. de code de boom af lopen tot je bij een blad komt. Begin daarna weer boven in de boom: decodeer hufboom cs = dc hufboom cs where dc (Blad c)

= [c]

|| laatste bit bereikt

dc (Blad c) cs

[]

= c : dc hufboom cs

|| karakter herkend

dc (Knoop l r) ('0':cs)

= dc l cs

|| linksaf bij 0

dc (Knoop l r) ('1':cs)

= dc r cs

|| rechtsaf bij 1

6.3 Constructie van de Huffman boom Opmerking: Het onderstaande is geen tentamenstof! Om een Huffman boom te kunnen construeren moeten we eerst een frequentie analyse van de te coderen tekst doen. De functie freqtabel telt voor ieder karakter hoe vaak het in een tekst voorkomt: freqtabel xs = sort [(ax,x)| x <"abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ ,."; ax := # [y| y <- xs; y = x]; ax>0]

freqtabel losgelaten op de tekst “hallo, hoe gaat het er mee” levert ons: [(1, ','), (1, 'g'), (1, 'm'), (1, 'r'), (2, 'l'), (2, 'o'), (2, 't'), (3, 'a'), (3, 'h'), (4, ' '), (5, 'e')]

Discrete Wiskunde

58

Omdat we willen sorteren op frequentie staat de frequentie voorop. Voor het bouwen van de boom is het nodig dat we de definitie van huffboom iets aanpassen. In ieder blad houden we bij hoe vaak het karakter voorkomt. In iedere knoop houden we bij wat de som van de frequenties van alle karakters in de bladeren van beide subbomen zijn. huffboom ::= Blad num char | Knoop num huffboom huffboom

Het bouwen van de boom gaat nu in een aantal stappen: Eerst maken we een lijst van bomen bestaande uit alleen maar bladeren. Dit gebeurt in de uitdrukking: [Blad f c| (f,c) <- freqlist]

Deze lijst van bomen gaan we net zolang combineren totdat we nog maar één boom overhouden. Deze boom is nu het eindresultaat. We combineren steeds de eerste twee bomen uit de lijst. Het combineren van twee bomen l en r bestaat uit het samenvoegen tot een knoop Knoop waarde l r, met als waarde de som van de waarden van de twee subbomen. De zo geconstrueerde boom wordt weer ingevoegd in de lijst van bomen waarbij er voor wordt gezorgd dat deze gesorteerd op freqentie blijft. Uiteindelijk houden we een lijst met één boom over. Dit is nu de gezochte boom. maakBoom freqlist = mb [Blad f c| (f,c) <- freqlist] mb [t]

= t

mb (t1 : t2 : ts) = mb (insert (Knoop (waarde t1 + waarde t2) t1 t2) ts) insert t [] = [t] insert t (t1:ts) = t : t1 : ts, if waarde t <= waarde t1 = t1 : insert t ts, otherwise waarde (Knoop n _ _) = n waarde (Blad n _)

Discrete Wiskunde

= n

59

7. Eindige automaten 7.1 Talen en eindige automaten Talen en zeker programmeertalen hebben een duidelijke structuur. Eindige automaten en grammatica’s zijn manieren om die structuur te beschrijven. Definities: een taal is een verzameling strings een string is een rij letters een alfabet is een verzameling letters Voorbeelden: { a, b } is een alfabet aa is een string aaaaab is een string ε is een string (een speciaal geval: de string van nul letters) { b, ab, aab, aaab, .... } is een taal De bovenstaande taal heeft een nogal simpele structuur: enkele a’s gevolgd door een b. Zulke vrij eenvoudige talen kunnen met een eindige automaat gegenereerd worden. Voor de voorbeeldtaal voldoet de volgende eindige automaat: a 1

b

2

Deze automaat bestaat uit toestanden (aangegeven met een cirkel) en overgangen (aangegeven met een pijl). De toestanden hebben als labels 1 en 2. Er zijn overgangen van 1 naar 1 met als label a en van 1 naar 2 met als label b. Het symbool => geeft aan dat toestand 1 de begintoestand is. De dubbele rand om toestand 2 geeft aan dat dit een eindtoestand is. Elke automaat heeft altijd 1 begintoestand, maar kan meerdere eindtoestanden hebben. Een automaat werkt als volgt: hij begint in de begintoestand hij maakt telkens een overgang hij stopt in een eindtoestand Belangrijk hierbij is dat de automaat mag stoppen in een eindtoestand, maar ook door kan gaan. De labels van de gemaakte overgangen vormen achter elkaar een string. Alle strings die de automaat zo kan maken vormen tezamen de taal van de automaat.

Discrete Wiskunde

60

Voorbeeld: a

1

2

a

De taal van deze automaat is de verzameling van alle strings die bestaan uit een oneven aantal a’s. Voorbeeld: a

a a

1 b

2

a

3 b

De taal van deze automaat is de verzameling van alle strings bestaande uit a’s en b’s, waarin aa voorkomt als deelstring. Met deze automaat is iets bijzonders aan de hand, want hij kan de string aaa op 2 manieren maken: 1 --> 1 --> 2 --> 3 1 --> 2 --> 3 --> 3 Dit is op zich een ongewenst gedrag, want de automaat moet als het ware kiezen en als hij aaa zou proberen te maken door te beginnen met 1 --> 1 --> 1 dan lukt het niet meer om aaa te maken. Definitie: een eindige automaat is deterministisch als hij elke string op hoogstens 1 manier kan maken. Een eindige automaat die een bepaalde string op meer dan 1 manier kan maken, noemen we non-deterministisch. Zo’n automaat is te herkennen aan het feit dat hij een toestand bevat van waaruit je met een bepaalde letter naar meer dan 1 toestand kan gaan. In het voorbeeld gebeurt dit bij toestand 1 want met de letter a kun je zowel naar toestand 1 als naar toestand 2 gaan.


Maak een eindige automaat voor de volgende talen van strings bestaande uit a’s en b’s: a. alle strings waarin precies 2 a’s voorkomen b. alle strings waarin na een a altijd een of meer b’s komen c. alle strings die bestaan uit een even aantal a’s gevolgd door een even aantal b’s d. alle strings waarin ab niet voorkomt e. alle strings waarin aaa precies 2 keer voorkomt (in aaaa is dit ook het geval) f. alle strings waarin een even aantal a’s of een even aantal b’s voorkomt

Discrete Wiskunde

61

Opgave 7.2

Gegeven is de volgende eindige automaat: a

a b

1

a

2 b

b

a. b.

3 b

Is de automaat deterministisch ? Beschrijf de taal van de automaat

7.2 Een eindige automaat bouwen Een aardige manier om een deterministische eindige automaat te construeren voor een bepaalde taal is om elke toestand iets te laten onthouden van de tot nog toe gegenereerde letters. Voorbeeld: maak een automaat voor de taal van alle strings bestaande uit a’s en b’s waarin aa voorkomt. Van belang om te weten is nu P: we hebben aa al gehad Q: de laatste letter was een a Voor de automaat zijn de volgende toestanden van belang: 1: ~P /\ ~Q 2: ~P /\ Q 3: P We zouden toestand 3 ook weer op kunnen splitsen in P /\ ~Q en P /\ Q maar dit hoeft niet omdat we als we aa al gehad hebben er willekeurig wat achter kunnen zetten. Het verschil tussen wel of niet als laatse een a speelt geen enkele rol meer. De automaat wordt: a a

1 b

b

2

a

3 b

In het begin hebben we het lege woord. Dus we hebben aa nog niet gehad en de laatste letter was geen a. De begintoestand is dus 1. Als er in toestand 1 een a komt, dan hebben we nog steeds aa niet gehad maar de laatste letter is wel een a, daarom wordt de toestand 2. Als er in toestand 1 een b komt, dan is de laatste letter geen a en blijven we dus in toestand 1. Zo kun je ook de andere overgangen beredeneren. Dat toestand 3 eindtoestand is, is omdat we dan aa gehad hebben.

Discrete Wiskunde

62

Voorbeeld: maak een automaat voor de taal van alle strings bestaande uit a’s en b’s die precies 2 a’s en minstens 2 b’s bevatten. We moeten nu weten of we 0, 1 of 2 a’s gehad hebben en of we 0, 1 of meer dan 1 b gehad hebben. De automaat wordt: a

0, 0 b

b

a

1, 1

a b

2, 1 b

b

0, >1

2, 0 b

b a

0, 1

a

1, 0

a 1, >1 b

2, >1 b

De labels van de toestanden hebben de volgende betekenis: het eerste cijfer geeft het aantal a’s aan en het tweede cijfer geeft het aantal b’s dat we al gehad hebben. Vanuit de toestand 2, 0 is er geen overgang met de letter a, omdat we geen strings mogen genereren met meer dan 2 a’s.


Maak een eindige automaat voor de volgende talen van strings bestaande uit a’s en b’s door de betekenis van de toestanden goed te definieren: a. alle strings waarin precies 3 b’s voorkomen b. alle strings waarin na een a altijd precies twee b’s komen c. alle strings waarin een even aantal a’s en een even aantal b’s voorkomt

7.3 Determinisme Een deterministische eindige automaat kunnen we gebruiken om te testen of een string tot zijn taal behoort, want bij elke string hoort er dan hoogstens 1 pad en dus hoogstens 1 toestand waar we met deze string uitkomen. Als die resulterende toestand een eindtoestand is dan hoort de string tot de taal en anders niet. Voorbeeld:

Discrete Wiskunde

63

a a

1

a

2

b

b

3 b

De string aaab heeft als pad: 1 --> 2 --> 3 --> 3 --> 3. Omdat we in 3 uitkomen en 3 eindtoestand is kan de automaat de string maken. De string bba heeft als pad: 1 --> 1 --> 1 --> 2. Nu komen we in 2 uit en 2 is geen eindtoestand; daarom kan de automaat deze string niet maken. Dit procede kunnen we in Amanda als volgt programmeren: test string = stap 1 string where stap 1 (‘a’:cs) = stap 2 cs stap 1 (‘b’:cs) = stap 1 cs stap 2 (‘a’:cs) = stap 3 cs stap 2 (‘b’:cs) = stap 1 cs stap 3 (‘a’:cs) = stap 3 cs stap 3 (‘b’:cs) = stap 3 cs stap 3 “” = True stap _ _ = False

De lokale functie stap heeft de volgende betekenis: stap toestand string = True

,if “de automaat kan vanuit de gegeven toestand de gegeven string maken”

= False ,otherwise

Zo’n vertaling van een automaat in Amanda code werkt alleen goed voor een deterministische automaat, omdat Amanda ook deterministisch werkt. Voorbeeld: maak een Amanda functie om te testen of een string bestaat uit een even aantal a’s en een willekeurig aantal b’s. De bijbehorende automaat heeft 2 toestanden: 1: we hebben een even aantal a’s 2: we hebben een oneven aantal a’s a

1 b

a

2 b

De Amanda functie wordt:

Discrete Wiskunde

64

test string = stap 1 string where stap 1 (‘a’:cs) = stap 2 cs stap 1 (‘b’:cs) = stap 1 cs stap 2 (‘a’:cs) = stap 1 cs stap 2 (‘b’:cs) = stap 2 cs stap 1 “” = True stap _ _ = False


Maak voor elk van de volgende talen een Amanda functie die test of een string tot die taal hoort: a. alle strings waarin minstens 3 b’s voorkomen b. alle strings waarin na een a altijd precies een b komt c. alle strings waarin een even aantal a’s en een even aantal b’s voorkomt Probeer de functies ook direct in Amanda te programmeren mbv lijstcomprehensies.

7.4 Deterministisch maken van een automaat Om strings te herkennen is een deterministische eindige automaat handig, maar vaak is het eenvoudiger om een non-deterministische automaat ervoor te construeren. Stel we willen een eindige automaat maken voor alle strings bestaande uit a’s en b’s waarin de string aab voorkomt. Een non-deterministische automaat hiervoor is: a

a a

1 b

2

a

3

b

4 b

Een deterministische automaat hiervoor maken is lastiger. Maar het blijkt dat er een algoritme is om van een non-deterministische automaat een deterministische automaat te maken, die precies dezelfde taal genereert. De deterministische automaat bootst de non-deterministische automaat na. De string aaa heeft de volgende paden in de non-deterministische automaat: 1 --> 1 --> 1 --> 1 1 --> 1 --> 1 --> 2 1 --> 1 --> 2 --> 3 Dus vanuit 1 kom je met aaa in 1, 2 of 3.

Discrete Wiskunde

65

De deterministische automaat heeft hoogstens 1 pad voor aaa. De toestand die uiteindelijk bereikt wordt zullen we 1, 2, 3 noemen, omdat hij overeenkomt met paden in de oorspronkelijke automaat die in 1, 2 of 3 uitkomen. Kijken we nu naar de string aaab, dan kan die in de oorspronkelijke automaat uitkomen in 1 of 4. Hiervoor hoeven we alleen te kijken hoe je de paden van aaa kunt verlengen met een overgang met een b. We hoeven dus alleen te kijken naar de eindtoestanden van aaa en hoe je van daaruit verder kan met een b. In een schema: 1 - b -> 1 2 - b -> 3 - b -> 4 ----------------1,2,3 - b -> 1,4 In de nieuw te maken deterministische automaat komt dus de overgang van 1,2,3 naar 1,4 voor met de letter b. Omdat er maar 1 begintoestand is, begint de nieuwe automaat op dezelfde manier als de oorspronkelijke:

1

Beginnend vanuit de unieke begintoestand krijgen we: 1 - a -> 1 1 - a -> 2 --------------1 - a -> 1,2

1 - b -> 1 Dit levert de eerste stap: a

1

1,2

b

Vanuit 1,2 heb je overgangen:

Discrete Wiskunde

66

1 - a -> 1 1 - a -> 2 2 - a -> 3 ------------1,2 - a -> 1,2,3 1 - b -> 1 2 - b -> -----------1,2 - b -> 1

a

1 b

1,2

a

1,2,3

b

Nu gaan we kijken wat we vanuit 1,2,3 kunnen doen: 1 - a -> 1 1 - a -> 2 2 - a -> 3 3 - a -> ------------1,2,3 - a -> 1,2,3 1 - b -> 1 2 - b -> 3 - b -> 4 --------------1,2,3 - b -> 1,4 Nu is 4 een eindtoestand in de oorspronkelijke automaat, dus 1,4 is ook een eindtoestand in de nieuwe automaat. Het resulteert in: a

1 b

b

1,2

a

b

1,2,3

1,4

a

We kunnen dit procede stug doorzetten en de totale deterministische automaat wordt dan:

Discrete Wiskunde

67

a

1 b

a

1,2

b

1,2,3 a

b

b

1,4 a

b

1,2,3,4

a

b

1,2,4

a


Maak equivalente deterministische eindige automaten voor de volgende automaten: a. a

a b

1

a

2

3

b

b

b

b. a

a

b

1

a a

2 b

b

3 b

Opgave 7.6

a. Maak een nondeterministische eindige automaat voor de taal van alle strings bestaande uit a’s en b’s waarin aabaab voorkomt b. Maak voor de automaat uit onderdeel a. een equivalente deterministische automaat

7.5 Reguliere expressies De taal van een eindige automaat heeft doorgaans een eenvoudige herhalende structuur zoals de volgende voorbeelden laten zien:

a 1

b

2

Taal: b, ab, aab, aaab ... Patroon: a*b

Discrete Wiskunde

68

a

1

2

b

Taal: a, aba, ababa, abababa ... Patroon: (ab)*a a a

1

2

b 3 b

Taal: ε, a, aa, aaa ..., b, bb, bbb ... Patroon: a* | b* Bij de automaten hebben we het patroon waaraan hun strings voldoen vermeld. Zo’n patroon heet ook wel een reguliere expressie. Hij kan bestaan uit letters, keuze en herhaling. De keuze tussen x en y geven we aan als x | y. Een herhaling van 0 of meer keer x geven we aan als x*. De conventie is dat herhaling (*) sterker bindt dan keuze (|). Dus a* | b* betekent (a*) | (b*) en is iets heel anders dan (a | b)*. Het is meestal niet zo moeilijk om bij een reguliere expressie een equivalente automaat te construeren. Voorbeeld: maak een automaat met als taal (a | b)*a(a | b)*b a

a a

1 b

b

2

3

b

Andersom dus van een automaat een reguliere expressie geven is doorgaans ook niet al te ingewikkeld. Waar het op neer komt is dat je toestanden als het ware wegwerkt. Voorbeeld: bepaal een reguliere expressie voor de taal van de automaat

Discrete Wiskunde

69

a a

1

b

2

a

3

b

Dit lijkt een onhandelbaar ding met al die pijlen heen en weer terug. Toch is de situatie in de buurt van toestand 3 vrij eenvoudig. We kunnen toestand 3 wegwerken als we een reguliere expressie langs een pijl zetten:

ba*b a

1

2

a

Na deze manipulatie is ook de situatie rond toestand 2 eenvoudig geworden. We werken dus nu toestand 2 weg.

a(ba*b)*a 1

Dus de reguliere expressie is: (a(ba*b)*a)* Nog een voorbeeld: b 1

a

2

a

b

3

b

Nu kunnen we toestand 2 wegwerken door elke overgang naar 2 met 1 stap te verlengen: b ab 1 aa

ba

3 bb

Alle overgangen naar toestand 1 kunnen we op dezelfde manier behandelen, waardoor we toestand 1 gedeeltelijk wegwerken.

Discrete Wiskunde

70

(b|ba)(aa)*ab ab

3

1 aa

bb

De af te lezen reguliere expressie is dan: (aa)* ab ( bb | (b|ba)(aa)*ab )*.


Bepaal reguliere expressies voor de talen van de volgende automaten: a. a

a b

1

a

2

3

b

b

b

b. a

a b

1

a a

2

3

b

b

b

c. a

a b

1 a

a

2 b

3 b

Opgave 7.8

Bepaal eindige automaten bij de volgende reguliere expressies: a. (a | b)* ab(aa)* b. (a | b)* (aa)* c. (a (aab)*)* | (bb)*

Discrete Wiskunde

71

8. Grammatica’s 8.1 Rekenkundige expressies De taal van de rekenkundige expressies bestaat uit strings zoals: 182 13 * 17 - 5 + 18 (1 + 8) * (7 - 14) Als we even afzien van de haakjes en tussenliggende spaties, dan beschrijft de volgende reguliere expressie hun structuur: (0 | (1|2..|9) (0|1|2..|9)*) ( (+|-|*|/) (0 | (1|2..|9) (0|1|2..|9)*) )* Een onleesbare onderdelen: cijfer begincijfer getal operator sectie expressie

formule, die wat helderder gemaakt kan worden door hem op te breken in = 0 | 1 | 2 .. | 9 = 1 | 2 .. | 9 = 0 | begincijfer cijfer* =+|-|*|/ = operator getal = getal sectie*

De expressie 13 * 17 - 5 + 18 bestaat uit het getal 13 gevolgd door de secties * 17 en - 5 en + 18. De sectie * 17 op zijn beurt bestaat uit de operator * en het getal 17. Het zo benoemen van alle onderdelen heet ontleden. Nu de haakjes nog. Dat is niet zo eenvoudig als het misschien lijkt, want haakjes moeten netjes in paren voorkomen. Dus we moeten op een of andere manier haakjes tellen en dat is iets wat met een eindige automaat niet kan. Immers een eindige automaat kan nooit verder tellen dan het aantal toestanden waar hij uit bestaat. Het aardige is dat we wel haakjes kunnen tellen als we onze definities recursief maken, wat zoveel wil zeggen dat de definities willekeurig naar elkaar mogen verwijzen zoals in een where-clause van Amanda. De volgende verzameling definities is voldoende: cijfer = 0 | 1 | 2 .. | 9 begincijfer = 1 | 2 .. | 9 getal = 0 | begincijfer cijfer* | ( expressie ) operator = + | - | * | / sectie = operator getal expressie = getal sectie* Het enige dat veranderd is, is de definitie van een getal. Definitie: een verzameling (recursieve) reguliere expressies noemen we een grammatica.

Discrete Wiskunde

72

(1 + 8) * (7 - 14) kunnen we volgens de gegeven grammatica als volgt ontleden: (1 + 8) is een getal, want 1 + 8 is een expressie * (7 - 14) is een sectie, want (7 - 14) is een getal, want 7 - 14 is een expressie Een ontleedboom geeft de structuur visueel weer: (

1

+

8

beginc

getal

)

*

(

beginc

op

-

1

beginc

getal

getal

sectie

4

beginc

op

)

cijfer

getal

sectie

expressie

getal

7

expressie

op

getal

sectie

expressie De grammatica voor rekenkundige expressies is nogal rijk. Daarom zullen we ons in het vervolg van dit hoofdstuk beperken tot de volgende deelgrammatica van rekenkundige expressies bestaande uit cijfers, optellen en aftrekken, en natuurlijk haakjes. cijfer getal sectie expressie

= 0 | 1 | 2 .. | 9 = cijfer cijfer* | ( expressie ) = + getal | - getal = getal sectie*

Voor deze grammatica zullen we stap voor stap in Amanda een ontleder (Engels: parser) maken. Dit is een stukje programma dat controleert of een string voldoet aan de grammatica en dat eventueel de bijbehorende waarde van de string bepaalt. Om te laten zien hoe de grammatica in staat is de waarde van een rekenkundige expressie te bepalen gaan we de string 13 + 8 - 7 ontleden. In de ontleedboom geven we ook de waarde van onderdelen aan.

Discrete Wiskunde

73

1

cijfer(1)

3

+

cijfer(3)

getal(1*10+3 = 13)

8

-

7

cijfer(8)

cijfer(7)

getal(8)

getal(7)

sectie(8)

sectie(-7)

expressie(13+8+(-7) = 14)


Gegeven is de volgende grammatica: X = ab | a X b Geef ontleedbomen voor de volgende strings: a. aabb b. aaabbb c. aaaaaaabbbbbbb d. beredeneer dat de taal van X = { an bn | n >= 1 } waarbij an betekent n a’s achter elkaar Opgave 8.2

Gegeven is de volgende grammatica: S=X|cS X = ab | a X b Geef ontleedbomen voor de volgende strings: a. caabb b. ccaaabbb c. cccccccab d. wat is de taal van X ? Opgave 8.3

Gegeven is de volgende grammatica: S=dX|cS X=aX|Y Y=bY|ε Geef ontleedbomen voor de volgende strings: a. cdaa b. ccdaaabbb c. cccccccdab

Discrete Wiskunde

74

Geef een reguliere expressie en een eindige automaat voor de taal S Opgave 8.4

Stel voor de volgende talen grammatica’s op (an betekent n a’s achter elkaar): a. { an bn | n >= 0 } b. { an bm | n >= 0 /\ m >= 0 /\ m <= n } c. { (an bn)* c* | n >= 0 } Opgave 8.5

De volgende grammatica kan ook alle rekenkundige expressies aan: cijfer = 0 | 1 | 2 .. | 9 getal = cijfer | cijfer getal operator = + | - | * | / expressie = getal | ( expressie ) | expressie operator expressie Geef zoveel mogelijk ontleedbomen voor de volgende rekenkundige expressies en vermeld ook telkens de waarde van de onderdelen: a. 89 + 007 * 3 b. (8 - 90) / 7 * 8 c. (78 + 9 + 78) - (6) Wat zou het nadeel zijn van deze grammatica ? Opgave 8.6

Maak de volgende (deel)grammatica voor Pascal statements af: statement = assignment | ifstatement | whilestatement | forstatement | repeatstatement | group | ε group = “begin” statements “end” statements = ε | statement | statement (“;” statement)* assignment = variable “:=“ expression ifstatement = “if” condition “then” statement | ... whilestatement = ... forstatement = ... repeatstatement = ... Hierbij hoeven variable, expression en condition niet verder uitgewerkt te worden. Deze grammatica werkt niet op letters zoals we gewend zijn, maar op strings zoals “if” en “while” en “repeat”.

8.2 Vereenvoudigde schrijfwijze Hierboven werden grammatica’s beschreven als recursieve regulier expressies. We zullen nu laten zien dat we grammatica’s nog eenvoudiger kunnen beschrijven. In grammatica’s zijn nml de herhaling (*), de optie ([iets]) en de keuze (|) niet nodig. Deze constructie kunnen met recursie beschreven worden.

Discrete Wiskunde

75

Voorbeelden: S -> a* wordt: S -> eps S -> aS S -> [a] wordt: S -> eps S -> a S -> a | b wordt: S -> a S -> b Wel worden hierbij voor non-terminals vaak meerdere regels geïntroduceerd. Dit is bij implementatie vaak lastig omdat het kan gebeuren dat je bij het toepassen van een regel er soms pas na een tijdje achterkomt dat deze regel niet van toepassing is en je een andere regel had moeten gebruiken (backtracking). Dit maakt parsers traag. We streven er daarom naar grammatica’s zo in elkaar te steken dat op ieder moment dat een nieuwe regel moet worden toegepast het eerst volgende symbool uniek bepaalt welke versie van de regel er van toepassing is. We noemen een grammatica dan LL1. Voor praktisch gebruik is iedere grammatica als een LL1 grammatica te realiseren. De realisatie van een parser voor een LL1 grammatica m.bv. recursieve functie noemen we een recursive descent parser. Er zijn ook andere manieren om parsers te maken (genereren) m.b.v tabellen. De grammatica hoeft dan niet noodzakelijk LL1 te zijn. Deze parsers zijn i.h.a efficiënter dan LL1 parsers.

Discrete Wiskunde

76

9. Backtracking 9.1 Inleiding Een belangrijke, veelgebruikte, programmeertechniek is backtracking. Backtracking wordt gebruikt voor zgn. zoekproblemen. Dit zijn problemen waarbij er één (alle) mogelijke oplossing(en) gezocht moet(en) worden. Voorbeelden: Vind een (alle) inkleuring(en) voor een landkaart zodat twee ieder tweetal aan elkaar grenzende landen verschillende kleuren hebben. Vind een route lang verschillende steden zodat de totale afstand minimaal is. Vind een plaatsing op een schaakbord van acht dames, zodat ze elkaar niet kunnen slaan. Vind een korrekte oplossing voor de volgende puzzel ......

9.2 Kleuren van een landkaart Uit de wiskunde is bekend dat het mogelijk is een landkaart zo in te kleuren dat twee aan elkaar grenzende landen verschillende kleuren hebben, met slechts vier verschillende kleuren. Het bewijs van deze stelling is buitengewoon ingewikkeld. Het was het eerste wiskundige bewijs waarbij uitgebreid gebruik werd gemaakt van computers om een groot aantal bijzondere gevallen door te rekenen. Een landkaart daadwerkelijk met vier kleuren inkleuren gaat gelukkig een stuk makkelijker, al kan ook hierbij de computer de taak een stuk eenvoudiger maken: Gegeven zijn een lijst van 4 kleuren, een lijst van landen en een lijst die per land aangeeft aan welke andere landen dit land grenst. landen = ["Ned","Lux","Bel","Fra","Dui"] kleuren = ["Rood","Blauw","Geel","Groen"] grenzen = [("Ned",["Bel","Dui"]), ("Bel",["Ned","Fra","Dui","Lux"]), ("Dui",["Fra","Ned","Bel","Lux"]), ("Lux",["Fra","Dui","Bel"]), ("Fra",["Bel","Lux","Dui"])]

De functie kleuringen moet alle mogelijke lijsten van (land,kleur) opleveren die aan de vraag voldoen. De oplossing is dus een lijst van lijsten! We gaan het probleem recursief oplossen. De recursie loopt over de landen die we moeten kleuren. Stel we hebben een aantal landen korrekt gekleurd en we willen het volgende land kleuren. We kunnen dan kiezen uit alle kleuren, waarbij we er op moeten letten of de kleur

Discrete Wiskunde

77

die we aan het laatste land hebben gegeven niet conflicteert met de kleuren van de landen die al gekleurd zijn. De controle gebeurt in de functie save. Safe m k ks controleert of kleur k voor land m niet in strijd is met de lijst van paren (land,kleur) in ks. Hoe gieten we dit in een recursieve functie? Een recursieve functie bestaat altijd uit (minimaal) twee gevallen. Eén daarvan is de stop case. Hier is dat het geval dat we een lege lijst van landen moeten kleuren. Als we nul landen moeten kleuren levert ons dat één oplossing: de lege lijst. Daar we een lijst van alle mogelijke kleuringen moeten opleveren, wordt het resultaat nu [[]]. Een niet lege lijst van landen bestaat uit een kop m en een staart ms. We willen het probleem recursief oplossen, dus we gaan eerst de landen uit de staart kleuren met een recursieve aanroep van kleuringen. Dit levert ons een lijst van alle mogelijke kleuringen van ms op. Voor ieder van deze kleuringen ks, gaan we nu proberen de kop m een kleur k (gekozen uit kleuren) te geven die niet in strijd is met de kleuren uit ks. Deze check kan gedaan worden met een aanroep van safe. Samen geeft ons dit: kleuringen [] = [[]] kleuringen (m:ms) =

[(m,k) : ks| ks <- kleuringen ms; || alle kleuringen van de

overige landen k <- kleuren;

|| voor m een kleur kiezen uit

safe m k ks

|| test of deze kleur is

kleuren toegestaan ] where safe m k ks = [land| (land,kleur) <- ks; kleur = k;

|| ieder land met dezelfde

kleur als m (l2,buren) <- grenzen; l2 = land; member buren m]

|| mag m niet als buur hebben

= []

Het schema dat we nu bedacht hebben is heel algemeen. In de meeste backtrack-problemen gaat het erom om een voorwerpen te koppelen aan iets anders op een dusdanige manier dat de koppelingen niet in strijd met elkaar zijn.

9.3 Het acht koninginnen probleem Geef alle mogelijke manieren om 8 koninginnen op een schaakbord te plaatsen zonder dat ze elkaar kunnen slaan. Bij dit probleem is het zaak eerst een goede representatie te vinden. We willen het probleem graag weer reduceren tot een koppelingsprobleem. Maar wat moeten we aan wat koppelen? Op het eerste gezicht zou men zeggen koninginnen aan bordposities. Maar wat is een koningin? Als we even nadenken komen we er achter dat alle koninginnen in verschillenden rijen moeten staan en dat er in iedere rij precies één koningin komt te staan. Het is daarom natuurlijker om rijposities aan kolomposities te koppelen.

Discrete Wiskunde

78

We noteren een positie op het schaakbord als (r,k) waarbij r de rij is en k de kolom. r en k variëren beide van 1 tot 8. We kunnen nu voor twee koninginnen de functie slaat definiëren die aangeeft of de eerste koningin de tweede slaat (en vice versa): slaat (i,j) (m,n) = i = m \/ j = n \/ abs(i-m) = abs(j-n)

Een koningin slaat een andere koningin als ze, of in dezelde rij staan, of in dezelfde kolom, of in dezelfde diagonaal. Queens wordt nu aangeroepen met als parameter de lijst van rijen waarvoor een bijbehorende kolom postitie moet worden gevonden. Voor het achtkoninginnenprobleem wordt dit dus: queens [1..8] queens [] = [[]] queens (r:rs) = [(r,k) : qs|

qs <- queens rs;

|| oplossingen voor overige rijen

k <- [1..8];

|| koppel rij aan kolom

and [~(slaat (i,j) (r,k))| (i,j) <- qs] ]

Het patroon is weer hetzelfde als bij de oplossingen van het vorige problemeen. De recursieve aanroep lost het probleem op voor de overige rijen. We proberen hieraan een koningin toe te voegen op rij r. We controleren hierbij of de nieuwe koningin niet geslagen wordt door een reeds geplaatste koningin.


Vind het (unieke) getal n bestaande uit 9 cijfers met de volgende eigenschappen: - de cijfers 1 t/m 9 komen precies één keer voor - de eerste k cijfers van n zijn deelbaar door k voor k 1 t/m 9 Opgave 9.2

Vind alle deellijsten van een lijst van getallen waarvan de som precies gelijk is aan de helft van de som van alle getallen in de lijst. Opgave 9.3

Gegeven een lijst van winkels met afname hoeveelheid en een lijst van distributiecentra met capaciteit. Geef alle toekenningen van winkels aan distributiecentra zodat de totale capaciteit van een distributiecentrum niet wordt overschreden. Er mogen meerdere winkels aan 1 distributiecentrum gekoppeld worden. winkels = [("ah1",15),("ah2",18),("ah3",17),("ah4",25)] distr = [("d1",40),("d2",19),("d3",20)]

Tip: definiëer eerst een functie update d h ds, die in een lijst van distributiecentra ds de capaciteit van distributiecentrum d verlaagt met hoeveelheid h.

Discrete Wiskunde

79

Discrete Wiskunde

80

10. Gulzige algoritmen 10.1 Grafen Een graaf is een netwerk bestaande uit een verzameling knopen en een verzameling verbindingen tussen de knopen. De verbindingen kunnen voorzien zijn van een label (bijvoorbeeld een lengte of kosten). De verbindingen kunnen een richting hebben. Voorbeelden: Een eindige automaat is een gerichte graaf waarvan de labels letters zijn.

a

1 b

2

a

b

Een wegenkaart is een ongerichte graaf waarvan de labels afstanden voorstellen. Leeuwarden

Groningen

60 30

25

40 20

Drachten

Heerenveen

Een pad in een graaf is een reeks op elkaar aansluitende verbindingen. Bijvoorbeeld: Leeuwarden -> Drachten -> Groningen In de informatica kom je grafen tegen in de vorm van datacommunicatienetwerken. De knopen zijn dan computers (internetservers, repeaters, routers, bridges, gateways e.d.). De verbindingen zijn dan de datacommunicatielinks. Ook het world wide web kun je opvatten als een graaf met als knopen de webpagina’s en als verbindingen de hyperlinks.

10.1.1 Representaties In Amanda kunnen we een graaf op verschillende manieren representeren.

Discrete Wiskunde

81

Voorbeeld: 5

b

a

3 3

c

d 2

Voor de hand ligt een representatie bestaande uit een lijst van knopen en een lijst van verbindingen. knopen = [“a”, “b”, “c”, “d”] verbindingen = [(“a”, “b”, 5), (“a”, “c”, 3), (“b”, “c”, 3), (“c”, “d”, 2)]

Eigenlijk zouden we ook de omgekeerde verbindingen zoals (“b”, “a”, 5) moeten opslaan, maar in een ongerichte graaf kunnen we deze natuurlijk altijd berekenen. (deze representatie is gebruikt in de opgave over de voetbalcompetitie in hoofdstuk 2) Een andere veelgebruikte representatie is een lijst van knopen met per knoop een lijst van verbindingen. Voor het voorbeeld: graaf = [(“a”, [(“b”, 5), (“c”, 3)]), (“b”, [(“a”, 5), (“c”, 3)]), (“c”, [(“a”, 3), (“b”, 3), (“d”, 2)]), (“d”, [(“c”, 2)])]

Hierbij is het verstandig om wel alle verbindingen op te slaan, omdat het berekenen van de omgekeerde verbindingen lastig is. In Pascal kunnen we een matrix gebruiken om de labels van de verbindingen in op te slaan. Als de labels bijvoorbeeld afstanden tussen knopen voorstellen, kunnen we een speciale grote waarde gebruiken om aan te geven dat er geen verbinding is. CONST aantalKnopen = 4; inf = 10000; (* infinite *) TYPE Matrix = array[1..aantalKnopen, 1..aantalKnopen] of integer; CONST afstand: Matrix = ((

0,

5,

3,inf),

(

5,

0,

3,inf),

(

3,

3,

0,

2),

(inf,inf,

2,

0,));

Discrete Wiskunde

82

10.2 Minimale opspannende boom We gaan nu uit van een samenhangende ongerichte graaf, waarvan de labels positieve getallen zijn. Dit kan bijvoorbeeld een datacommunicatienetwerk zijn met de kosten van aanleg van de verschillende verbindingen. Gevraagd wordt een deelnetwerk te bepalen met minimale kosten, waarbij nog wel elke knoop vanuit elke andere knoop te bereiken valt. Voorbeeld: 2 2

b

d

4

2 a

3 3

1

c

f 3

e 2

Het gevraagde minimale deelnetwerk bevat alle knopen maar niet alle verbindingen. In het bijzonder bevat het geen lussen. Want als we van een lus een verbinding weglaten, dan hebben we een goedkoper netwerk dat nog steeds alle knopen met elkaar verbindt.

10.2.1 Het algoritme van Kruskal Een voor de hand liggend algoritme is nu: sorteer de verbindingen in volgorde van kosten en laat hieruit een voor een de verbindingen weg die voor een lus zorgen. In het voorbeeld: d-1-e a-2-b b-2-d b-2-e c-2-e a-3-c b-3-c e-3-f d-4-f

2 2

b

d

weglaten a

weglaten weglaten

1 c

e

f 3

2

weglaten

10.2.2 Het algoritme van Prim Een andere aanpak is om in een willekeurige knoop te beginnen en van daaruit telkens uit te breiden met de goedkoopste verbinding vanuit de al gekozen punten naar een ander punt. Op die manier krijgen we nooit lussen en vinden we een minimaal netwerk. In het voorbeeld:

Discrete Wiskunde

83

begin bij knoop a de verbinding a - b is de goedkoopste vanuit a de verbinding b - d is de goedkoopste vanuit a en b de verbinding d - e is de goedkoopste vanuit a, b, en d de verbinding e - c is de goedkoopste vanuit a, b, d en c de verbinding e - f is de goedkoopste vanuit a, b, d, c en e Min of meer toevallig krijgen we dezelfde oplossing.


Pas beide algoritmen toe op de volgende graaf: 2 4

b

d

4

3 a

1 3

5

c

e

f 3

2

Opgave 10.2

Welke representatie van een graaf is het meest geschikt voor het algoritme van Kruskal en welke voor het algoritme van Prim ?

10.3 Kortste pad We gaan nu uit van een samenhangende graaf waarvan de labels positieve getallen zijn die de lengte van een verbinding voorstellen. Gevraagd wordt om het kortste pad tussen twee gegeven knopen te bepalen.

Discrete Wiskunde

84

Voorbeeld: 2 2

b

d

4

2 a

3 3

1

c

e

f 3

2

Gevraagd: het kortste pad tussen a en f.

10.3.1 Het algoritme van Dijkstra We kunnen op dezelfde manier te werk gaan als bij het algoritme van Prim. D.w.z. we beginnen bij a en breiden de verzameling knopen steeds uit met de dichtsbijzijnde andere knoop. Van deze verzameling knopen weten we precies de kortste afstand tot a. Zodra we f aan de verzameling hebben toegevoegd weten we de kortste afstand van a tot f. We beginnen bij a, de minimale afstand van a naar a is duidelijk 0. Omdat b het dichtste bij a ligt, is de minimale afstand van a naar b ook bekend en wel 2. We bekijken nu alle directe verbindingen vanuit a, b. Dit zijn a-c, b-c, b-e en b-d. Voor c levert dit een pad naar a met lengte 3 of met lengte 5 op. Voor e levert dit een pad van lengte 4 op. Voor d levert dit een pad van lengte 4 op. Voor c vinden we de kleinste waarde (3) dit moet dus wel het kortste pad van a naar c zijn, want elk ander pad loopt via de andere en is dus langer. Vanuit a, b, c zijn er directe verbindingen naar d en e. Voor d vinden we een pad met lengte 4. Voor e vinden we een pad met lengte 4 en een pad met lengte 5. Het minimum is 4 en we voegen d en e toe. Tenslotte vinden we paden naar f van lengte 7 en 8. Omdat 7 de kleinste waarde is moet dit dus wel de lengte van het kortste pad van a naar f zijn. We weten nu wel voor elke knoop wat zijn minimale afstand tot a is, maar hoe vinden we nu het kortste pad? Door terug te rekenen: f ligt 7 van a af en is verbonden met d en e. Via d levert op 4 + 4, via e levert op 4 + 3. Dus het kortste pad van a naar f gaat via e. Vanuit e kunnen we hetzelfde doen. Enzovoorts.


Discrete Wiskunde

85

Pas Dijkstra’s algoritme toe op de volgende graaf om het kortste pad van a naar f te vinden. 2 4

b

d

4

3 a

1 3

5

c

e

f 3

2

Opgave 10.4

We hebben Dijkstra’s algoritme toegepast op een ongerichte graaf. Werkt het algoritme ook correct op een gerichte graaf, waarbij de verbindingen een richting hebben en de afstand van x naar y ongelijk kan zijn aan de afstand terug van y naar x ? Opgave 10.5

In veel puzzels kun je een graaf herkennen. Het oplossen van de puzzel komt dan eigenlijk neer op het vinden van het kortste pad tussen de beginstand en een gevraagde eindstand. Teken de (gerichte) graaf behorend bij het volgende waterkannenprobleem en geef aan hoe Dijkstra’s algoritme een oplossing kan vinden. Waterkannenprobleem: Gegeven zijn een waterkan met een capaciteit van 3 liter en een waterkan met een capaciteit van 4 liter. Op de kannen staan geen maatstrepen. Verder is er kraan waaruit de kannen onbeperkt kunnen worden gevuld en er is een put waarin de kannen kunnen worden geleegd. In het begin zijn de kannen leeg. Door bijvullen, leeggieten en overgieten moet er uiteindelijk 2 liter water in de 3 liter kan overblijven.

10.3.3 Het algoritme van Floyd Dikwijls wordt gevraagd naar de kortste afstanden tussen alle knopen. Dit kan natuurlijk met Dijkstra’s algoritme gedaan worden, maar er zijn meer eenvoudige methoden. We zullen dit illustreren in Pascal, waarbij we als representatie van de graaf een afstandenmatrix gebruiken. Voor de kortste afstanden gebruiken we ook zo’n matrix (KA genaamd). KA initialiseren we met de afstandsmatrix. Als de afstand van knoop i naar knoop j via knoop k kleiner is dan de tot nu bekende afstand van knoop i naar knoop j, dan kunnen we die afstand verbeteren. In Pascal: if KA[i,k] + KA[k,j] < KA[i,j] then KA[i,j] := KA[i,k] + KA[k,j];

Dit wordt herhaald tot de kortste afstanden niet meer veranderen.

Discrete Wiskunde

86

procedure KortsteAfstand(afstand: Matrix; VAR KA: Matrix); var i, j, k: integer; veranderd: boolean; begin KA := afstand; repeat veranderd := false; for i:=1 to aantalKnopen do for j:=1 to aantalKnopen do for k:=1 to aantalKnopen do if KA[i,k] + KA[k,j] < KA[i,j] then begin KA[i,j] := KA[i,k] + KA[k,j]; veranderd := true; end; until not veranderd; end;

Dit werkt al behoorlijk snel want het aantal keren dat de repeat-lus wordt uitgevoerd is ongeveer gelijk aan de 2-log van het aantal knopen. Want in het begin is KA[i,j] de lengte van een pad van i naar j bestaande uit hoogstens 1 verbinding. Na de eerste slag van de repeat-lus is KA[i,j] de kleinste lengte van een pad van i naar j bestaande uit hoogstens 2 verbindingen. Na de tweede slag is KA[i,j] de kleinste lengte van een pad van i naar j bestaande uit hoogstens 4 verbindingen. Na de derde slag gaat het om paden bestaande uit 8 verbindingen. Met dit verdubbelen komen we al snel aan de maximale lengte, die hoogstens gelijk is aan aantalKnopen-1. Maar het kan nog sneller door de volgorde van de for-lussen te veranderen, we krijgen dan het algoritme van Floyd: procedure KortsteAfstand(afstand: Matrix; VAR KA: Matrix); var i, j, k: integer; begin KA := afstand; for k:=1 to aantalKnopen do for i:=1 to aantalKnopen do for j:=1 to aantalKnopen do if KA[i,k] + KA[k,j] < KA[i,j] then KA[i,j] := KA[i,k] + KA[k,j]; end;

Waarom is dit correct ? KA[i,j] bevat de kleinste lengte van een pad van i naar j lopend via de knopen 1, 2 t/m k-1. De binnenste twee for-lussen passen KA zo aan, dat ook gekeken wordt naar paden die via knoop k lopen.


Discrete Wiskunde

87

In een provincie moet een ziekenhuis gebouwd worden. Het ziekenhuis moet in een van de steden komen, zodanig dat er zo weinig mogelijk met de ambulance gereden hoeft te worden. Het aantal ernstige ziektegevallen is procentueel in alle steden gelijk. Welke stad heeft de voorkeur uitgaande van de volgende gegevens: stad

aantal inwoners

---------------------------a

10.000

b

15.000

c

20.000

d

17.000

e

13.000

f

14.000

stad

stad

afstand

---------------------------a

b

10

a

c

15

a

d

20

b

c

5

b

d

5

b

e

10

c

e

12

c

f

12

d

f

5

Hint: maak hier een (Amanda) programma voor. Opgave 10.7

Gegeven is de volgende niet-samenhangende graaf. Geef aan hoe we het algoritme van Floyd kunnen gebruiken om te bepalen welke knopen vanuit welke andere knopen bereikbaar zijn.

b

d

g i

a

f c

e

h

Bedenk ook zelf een algoritme om te bepalen of knoop i vanuit knoop a bereikbaar is.

Discrete Wiskunde

88

Discrete Wiskunde. D. Bruin J.M. Jansen

Recommend Documents