3. Structuren in de taal
__________________________________________
In dit hoofdstuk behandelen we de belangrijkst econtrolestructuren die in de algoritmiek gebruikt worden. Dit zijn o.a. de opeenvolging, selectie en lussen (herhaling). Vóór we deze controle-structuren behandelen, vertellen we iets over variabelen. Ingewikkelder vormen van variabelen komen later in het hoofdstuk ter sprake in de vorm van de gegevenstructuren vector en matrix. Alle behandelde structuren zijn te gebruiken in de pseudotaal (zie ook het overzicht van de pseudotaal in hoofdstuk 11 van deze syllabus).
Zoals we in hoofdstuk 2 hebben uitgelegd moeten we, om algoritmen in de pseudotaal te kunnen beschrijven, afspraken maken over syntax en semantiek van die taal. De eerste stap die we zetten in die richting heeft betrekking op zg controle structuren. De eenvoudigste structuur in een taal is de opeenvolging. Al iets ingewikkelder worden de herhalingen en de uitzonderingen (selecties). Structuur in een algoritme is erg belangrijk, niet alleen om de computer ons te laten begrijpen, maar ook om zelf inzicht te krijgen in wat er eigenlijk gebeurt. Ook als je andere mensen je algoritme wilt geven, is een goede structuur noodzakelijk. Hierdoor begrijpen de mensen eerder wat je bedoelt en zullen ze meer vertrouwen in de resultaten van je algoritme hebben.
3.4 Lussen In deze paragraaf behandelen we de lus-structuren. De volgende contructies worden uitgelegd: Voor..Tot, Zolang...Doe, Herhaal...Totdat. Verder zullen we vertellen hoe je de ene constructie in de andere kunt omschrijven. Tot slot komen de geneste lussen ter sprake.
Bij de opeenvolging en de selectie worden opdrachten nooit meer dan één keer uitgevoerd (bij selectie soms zelfs nooit). Toch kan het heel vaak voorkomen dat een opdracht meerdere keren uitgevoerd moet worden. Om te voorkomen dat je dezelfde opdracht voor iedere keer dat hij uitgevoerd moet worden opnieuw moet intypen zijn lussen bedacht.
pagina 3.4 - 2
3.4.1
Voor..Tot Als we een opdracht meer dan eens willen uitvoeren kunnen we de Voor..Tot constructie gebruiken. Bijvoorbeeld: Voor A := 1 Tot 10 SCHRIJF 'A is met 1 verhoogd' SCHRIJF 'A is nu gelijk aan’,PLAK A Eindvoor
Bij deze constructie wordt A eerst gelijk aan 1, daarna wordt de schrijf-opdracht uitgevoerd. Nu gaat A met stapjes van 1 naar de waarde 10, en elke keer als A 1 verhoogd is wordt de schrijfopdracht uitgevoerd. Na uitvoering van het algoritme staat er dus 10 keer A is met 1 verhoogd A is nu gelijk aan … op het scherm. Bij de Voor-constructie wordt een variabele met stapgrootte 1 verhoogd van een bepaalde beginwaarde tot een bepaalde eindwaarde. De opdrachten die binnen de Voor en Eindvoor staan worden dan elke keer uitgevoerd. De Voor-constructie is dus: Voor variabele := beginwaarde Tot eindwaarde opdrachten Eindvoor
Het aantal keren dat de opdracht binnen de lus moet worden uitgevoerd staat dus van te voren vast! Het is niet aan een voorwaarde gebonden. Voorbeeld: Een voedsel-regulatie model Veel technologische feedbacksystemen worden gecontroleerd door een mechanisme dat een proces start of stopt. De thermostaat van een verwarming is hier een goed voorbeeld van. Wanneer het in een kamer te koud wordt dan zorgt de thermostaat ervoor dat de verwarming aanslaat. Wanneer het in een kamer te warm wordt dan zorgt de thermostaat dat de verwarming uit gaat. Een biologisch voorbeeld van een dergelijk controlesysteem is het voedingsgedrag van ratten. In een sterk vereenvoudigd model is in het voedsel systeem een regelmechanisme ingebouwd dat een 'switch' op aan zet als de rat gaat eten en de switch op uit zet als de rat niet eet. Van dit probleem is onderstaand diagram gemaakt. De darm dient in dit model als voedsel opslagplaats. Via de darmwand vindt energie toevoer naar het lichaam plaats. De snelheid van energie transport naar het lichaam is evenredig met het oppervlak van de darmwand. In dit model nemen we aan dat dit evenredig is met de wortel van de darm inhoud: M = km
÷D
pagina 3.4 - 3
Voedsel
Voedsel Opname
Energie
Darm
Regelmechanisme Hier is M de snelheid van energie overdracht van de darm naar het lichaam, km is de opnamecoëfficiënt en D is de hoeveelheid energie van het voedsel in de darmen. km kan gedurende een etmaal variëren. Omdat de rat een nachtdier is zal de coëfficiënt 's nachts hoger zijn dan overdag. Opname van voedsel vindt snel plaats, terwijl energieverbruik langzaam gaat. De snelheid van voedselopname, F, wordt berekend door: F = eI waarbij I de eetsnelheid is en e de feedback coëfficiënt (het regel mechanisme). Als de rat eet, is e gelijk aan 1. De darm stroomt dan met snelheid I vol. Als de rat niet eet is e gelijk aan 0. In ons model wordt het regelmechanisme aan- en uitgezet door de hoeveelheid energie M. Als M onder een bepaald niveau komt, M l, dan zal de rat gaan eten. Als M boven een maximum komt, M h, dan stopt de rat met eten en wordt e op 0 gezet. In dit model wordt aangenomen dat het gewicht van de rat constant blijft. De energie kan niet worden opgeslagen, alleen energie uit de darmen wordt gebruikt. Voedsel is ten alle tijden aanwezig. De uiteindelijke formule voor het systeem is: D(t) = D(t-1) + F - M We maken een algoritme waarin we 24 uur (1440 minuten) van de rat simuleren. We gebruiken tijdstapjes van 5 minuten. Gegeven zijn de volgende startwaarden: Om de 8 uur verandert de km van de rat (variërend van 1 naar 2 naar 3), afhankelijk van ochtend, dag, of nacht Variabelen en hun startwaarden: M l = 18 cal/min M h = 60 cal/min I = 500 cal/min D = 4000 cal Begintijd is 7 uur 's ochtends Dit levert ons het volgende algoritme: PROGRAM ‘VoedselRegulatie’ I := 500 Ml := 18 Mh := 60 D := 4000 km := 1 { km op 'ochtendstand' } e := 0 M := km MAAL WORTEL D Voor tijd:=1 Tot 288 { Doe 288 tijdstappen }
Als Dan
M KLEINER DAN Ml
Hoofdstuk 3.4
pagina 3.4 - 4 e := 1
Eindals Als Dan
M GROTER DAN Mh e:= 0
{ zet eetsysteem uit }
F := e MAAL I D := D PLUS F MIN M M := km MAAL WORTEL D SCHRIJF F, D, M
{ snelheid van darm-vullen } { bereken darminhoud } { energie overdracht }
tijd IS 96
{ om de 8 uur veranderd km }
km := 2
{ km op 'dagstand' }
Eindals
Als Dan
Eindals Als Dan
{ zet eetsysteem aan }
t IS 192 km := 3
Eindals Eindvoor
{ km op 'nachtstand' }
‘Prachtig hoor’, zul je zeggen, ‘maar hoe kom ik hier nu aan als ik het algoritme zelf moet schrijven ?. Geef eens wat richtlijnen ! ‘
Hoe bouwen we het algoritme op ? De beginregel is het eenvoudigst. Dat is de programma-definitie regel. Op die regel wordt de naam van het programma vastgelegd en, als daarom is gevraagd, ook de mogelijkheid om input (= parameters) mee te geven (zie Hoofdstuk 5) In dit geval wordt er niet gevraagd om parameters over te kunnen dragen. Dat betekent dat onze programma definitie regel er als volgt uit moet zien: PROGRAM 'programmanaam’ De volgende stap is de initialisatie-fase, en bestaat er uit dat we ons afvragen hoeveel variabelen er in het probleem dat we moeten oplossen een rol spelen, van welk type ('getal' of 'teken') ze zijn, als ze het type 'getal' hebben welke vorm (dimensie) ze moeten hebben (scalair, vector, of matrix: zie paragraaf 3.6 over gegevens-structuren), en welke startwaarde de variabelen bij het begin van het programma moeten krijgen. In dit geval wordt het aantal variabelen bepaald door de formule waarmee we de toestand van het metabolisme per tijdstap uitrekenen. In die formule spelen een zevental variabelen een rol. In de eerste plaats de eetsnelheid I, vervolgens de snelheid van energie overdracht M, het minimum- en maximum niveau, Ml en Mh, daarvan, de opname coëfficient km, de hoeveelheid energie D van het voedsel in de darm, en tot slot de feedback coëfficient e. Daarmee is het lijstje van variabelen kompleet. Alle zeven hebben ze aan het begin een startwaarde nodig; ze moeten worden geinitialiseerd anders kunnen we er verder op in het programma niet mee rekenen. Verder moeten we er rekening mee houden dat de waarde van de variabele M niet direct bekend is maar afhankelijk is van de waarde van km en D. M kan dus pas worden uitgerekend nadat km en D hun waarde hebben gekregen ! Het initialisatie blok komt er dan als volgt uit te zien: I := 500 {eetsnelheid} Ml := 18 {minimum energie overdracht} Mh := 60 {maximum energie overdracht} D := 4000 {energie in voedsel in darm} km := 1 {km op 'ochtendstand'} e := 0 {feedback}
pagina 3.4 - 5 M := km MAAL WORTEL D
{hoeveelheid energie overdracht}
OK, de voorbereidende stappen zijn achter de rug en we zijn nu aan het echte werk toe. Wat is het probleem ? We moeten voor een vaststaande periode (24 uur met 1440 minuten) in een bepaalde regelmaat (om de 5 minuten) volgens bepaalde formules de waarden van variabelen bepalen. De kern van het programma moet dus een lus bevatten, want we moeten om de 5 minuten steeds dezelfde formules toepassen. En aangezien we precies weten hoeveell blokjes van 5 minuten er in 24 uur gaan (288) ligt het soort lus ook vast, nl de voor-lus ! De structuur van een voorlus is als volgt: Voor tijdstip := 1 Tot totaalAantalTijdstippen Opdrachten Eindvoor We weten ook wat we in moeten vullen voor het blokje Opdrachten, namelijk de tot pseudotaal omgeschreven formules ! Dat ziet er als volgt uit: F := e MAAL I { snelheid van darm-vullen } D := D PLUS F MIN M { bereken darminhoud } M := km MAAL WORTEL D { energie overdracht } Eenmaal uitgerekend moet de gebruiker van het programma worden verteld wat nu de waarden van de verschillende variabelen is geworden. Dat kunnen we doen door die waarden naar het scherm te schrijven met een SCHRIJF opdracht: SCHRIJF F, D, M Daarmee is de kous nog niet af ! De waarde van een aantal van de variabelen is namelijk niet afhankelijk van de formule maar van het tijdstip van de dag (km) of van een bepaalde limiet overschrijding (e). Dat betekent dat we nog een aantal voorwaardelijke opdrachten moeten formuleren waarin die wisselende omstandigheden tot uitdrukking worden gebracht. De eerste serie voorwaarden betreffen de snelheid van energie overdracht. Zodra we voor de eerste keer M hebben uitgerekend (in het initialisatie blok) moeten we controleren of de minimum waarde Ml dan wel de maximum waarde Mh van M is overschreden. In die gevallen moeten we namelijk de waarde van de feedback coëfficient e wijzigen. Direct na het begin van de voorlus, maar nog voor het formule blok, komen deze voorwaarden te staan:
Als Dan
M KLEINER DAN Ml e := 1
Eindals Als Dan
{ zet eetsysteem aan }
M GROTER DAN Mh e:= 0
Eindals
{ zet eetsysteem uit }
De andere variabele die voorwaardelijk verandert is km, de opnamecoëfficient. Deze verandert afhankelijk van het tijdstip. We weten dat we de simulatie om 7 uur ‘s ochtends beginnen, en dus weten we de begin toestand van km, nl de ochtendstand. Maar km moet veranderen zodra we 8 uur verder zijn, en weer een keer na nog eens 8 uur. Die voorwaardelijke veranderingen in de waarde van km komen na het formule blok. (maakt dat wat uit, of we km voor of na het formule blok controleren ?):
Als Dan
tijd IS 96
{ om de 8 uur veranderd km }
km := 2
{ km op 'dagstand' }
Eindals Als Dan
t IS 192 km := 3
{ km op 'nachtstand' }
Hoofdstuk 3.4
pagina 3.4 - 6
Eindals Hiermee zijn de bouwstenen van het algoritme kompleet. Nu alles nog in de goede volgorde zetten.
3.4.2
Zolang...Doe Bij de Voor-constructie moet je altijd van te voren al weten hoe vaak de opdrachten binnen de lus uitgevoerd moeten worden. Het kan echter ook voorkomen dat je niet weet hoe vaak de opdrachten herhaald moeten worden, bijvoorbeeld als een bepaalde opdracht uitgevoerd moet worden zolang de temperatuur onder de 15o C is. Hiervoor kun je de Zolang constructie gebruiken. Bijvoorbeeld: Zolang temperatuur is kleiner dan 15 Doe verwarm de buis in de gasvlam.
In het algemeen: na de Zolang staat een conditie. Zolang deze conditie waar is worden de opdrachten na de D o e uitgevoerd. Ook dit statement moet afgesloten worden. We gebruiken hiervoor Eindzolang . Als de conditie niet (meer) waar is, gaat het algoritme verder met de opdrachten na de Eindzolang. Bekijk het volgende algoritme: PROGRAM ‘TestZolang’ A:=5 Zolang A>0 Doe A:=A-1 SCHRIJF 'A wordt met één verlaagd' SCHRIJF ‘De waarde van A is nu: ‘ PLAK A Eindzolang SCHRIJF 'A is nul'
In dit algoritme wordt A eerst 5. In de volgende regel wordt gecontroleerd of A groter dan 0 is, dit is het geval en dus worden de volgende twee regels uitgevoerd. Nu is A 4 geworden, dit is nog steeds groter dan 0 en de twee regels worden nogmaals uitgevoerd. Dit gaat zo door totdat A 0 is. Als het algoritme dan bij de conditie komt is deze niet waar: de laatste regel van het algoritme wordt nu uitgevoerd. Op het scherm staat nu dus 5 keer de tekst: 'A wordt met één verlaagd' en één keer 'A is nu nul'. De Zolang -constructie is: Zolang
pagina 3.4 - 7
Doe
conditie
opdrachten Eindzolang
Ook hier wordt de structuur aangegeven met inspringen. Voorbeeld: Speltheorie Bij ratten zijn er twee verschillende strategieën om aan voedsel te komen. Ten eerste zijn er de 'dominanten'. Deze vechten altijd totdat hun tegenstander verdreven of gewond is. Bij dit vechten lopen ze de kans gewond raken of dat ze zelf gedood worden. Ten tweede zijn er de 'recessieven'. Deze proberen de tegenstander wel te intimideren, maar gaan geen gevecht aan. Met deze ratten kan een evolutionair spel gespeeld worden waarbij fitness in punten weergegeven wordt. De punten verdelen we als volgt: De winnaar van een conflict krijgt 80 punten De verliezer van een conflict krijgt 50 punten Als je bij een gevecht gewond raakt krijg je 0 punten Intimideren kost 10 punten. We gaan er van uit dat het aantal nakomelingen van de ratten overeen komt met de behaalde fitness punten. Er zijn nu drie mogelijke situaties: 1) Als een dominant tegen een dominant vecht heeft elk van de dominanten een kans van 0.5 om te winnen en een kans van 0.5 om gewond te raken. Het gemiddeld behaalde aantal fitness punten bedraagt dan 0.5 x 80 + 0.5 x 0 = 40 . 2) Als een dominant een recessief tegenkomt dan wint de dominant altijd (de recessief vlucht namelijk zodra hij aangevallen wordt), en krijgt 80 punten. De recessief verliest en krijgt 50 punten. 3) Als een recessief een recessief ontmoet, dan intimideren de beesten elkaar totdat een van de twee beesten weggaat. Voor beide kost dit 10 punten en voor beide is er een kans van 0.5 op winnen en een kans van 0.5 op verliezen, gemiddeld levert dit: 0.5(80-10)+0.5 x (50-10) = 55 punten. In tabelvorm: Dominant
Recessief
Dominant
40
80
Recessief
50
55
Wanneer er nu een populatie is met alleen maar recessieven dan is de fitness voor iedereen 55. Als er in deze populatie een dominant komt, dan heeft deze een fitness van 80 en kan zich snel vermenigvuldigen. Wanneer een populatie uit alleen maar dominanten bestaat dan is de fitness voor iedereen 40. Een recessief zou in deze populatie een fitness van 50 hebben en heeft dan een hogere fitness dan de anderen. Hij kan zich dus snel vermenigvuldigen. De verwachting is dat zich na verloop van tijd een evenwicht in zal stellen tussen recessieven en dominanten (check: stopt het algoritme ?). Op basis van dit model kan een stelsel van vergelijkingen afgeleid worden:
➂
Eerst moet de fitness van de oude generatie berekend worden.
De fitness van een dominant is het aantal punten dat hij scoort wanneer hij een dominant individu tegen komt maal het aantal dominanten + het aantal punten dat hij scoort wanneer hij een recessief individu tegenkomt maal het aantal recesieven.
Hoofdstuk 3.4
pagina 3.4 - 8 FD(t) = (D(t-1)x 40) + R(t-1) x 80 Voor de recessieven geldt een soortgelijk verhaal. FR(t) = (D(t-1)x 50) + R(t-1) x 55
☞
Vervolgens kan dan de verhouding van de nieuwe generatie berekend worden.
Dit gebeurt door het aantal dominanten en recessieven met de relatieve fitness te vermenigvuldigen. VD = D(t-1) x FD/(FR+FD) VR = R(t-1) x FR/(FR+FD)
☞
Het enige wat nu nog gedaan moet worden is deze verhoudingsgetallen omzetten in ware aantallen. We nemen aan dat het aantal individuen in de populatie constant blijft en de waarde 'totaal' heeft. D(t) = totaal x VD/(VD+VR) R(t) = totaal x VR/(VD+VR)
FD is de gemiddelde fitness van de dominanten; FR is de gemiddelde fitness van de recessieven; D(t) is het aantal dominanten en R(t) is het aantal recessieven; VD is het verhoudingsgetal voor de nieuwe generatie dominanten; VR is het verhoudingsgetal voor de nieuwe recessieven. We kunnen nu een algoritme maken dat met het stelsel van vergelijkingen het evenwicht tussen de dominanten en recessieven berekent. We beginnen het algoritme met een generatie waarbij 50 recessieven aanwezig zijn en 50 dominanten en we laten de computer rekenen zolang het aantal recessieven nog veranderd. Om het evenwicht te bepalen onthouden we elke keer het oude aantal recessieven, en als de oude waarde min de nieuwe waarde 0 is stoppen we het algoritme. Dit geeft ons het volgende algoritme: PROGRAM ‘VoedselSpel’ {Simulatie van speltheoretisch model voor voedselacquisitie} D := 50 {aantal dominanten} R_oud := 0 R := 50 {aantal recessieven} Totaal := 100
Zolang Doe
NIET (R_oud MIN R) IS 0 R_oud := R { onthou deze R } FD := (D MAAL 40) P L U S { R b eM r eAkAeLn f8i t0n e s s dominanten } FR := (D MAAL 50) P L U S { R b eM r eAkAeLn f5i t5n e s s recessieven } VD := (D MAAL FD) GEDEELD DOOR FD PLUS FR {verh. domin. } VR := (R MAAL FR) GEDEELD DOOR FD PLUS FR {verh. recess.} D := Totaal MAAL VD GEDEELD DO {nieuw OR VR aantal PLUS domin. } R := Totaal MAAL VR GEDEELD DOOR VR PLUS VD {nieuw aantal R } SCHRIJF D,R
Eindzolang
Je ziet in dit algoritme dat we niet weten hoe vaak de opdrachten uitgevoerd gaan worden. Pas als R niet meer verandert stopt het algoritme. Bij de Voor-constructie moeten we wel altijd al aangeven hoe vaak de opdrachten gedaan moeten worden. Dit is het belangrijkste verschil tussen de
VD
pagina 3.4 - 9
Voor- en de Zolang-constructie. Als het aantal keer dat de opdrachten uitgevoerd moeten worden bekend is, kan een Zolang-lus altijd in een Voor-lus omgeschreven worden (en andersom).
3.4.3
Herhaal...Totdat Een derde lus-structuur is de Herhaal...Totdat constructie. Deze constructie lijkt erg op de Zolang-constructie. Ook hier weten we niet hoe vaak de opdrachten uitgevoerd worden. Het grote verschil tussen de Herhaal en de Zolang is de plaats van de conditie. We hebben gezien dat bij de Zolang-constructie de conditie vooraan staat (‘pre-tested loop’) , bij de Herhaal constructie staat de conditie juist achteraan (‘post-tested loop’). Een Herhaal lus bestaat uit een aantal opdrachten waarbij als laatste opdracht gekeken wordt of de opdrachten nogmaals uitgevoerd moeten worden. Het belangrijkste gevolg hiervan is dat de opdrachten in een Herhaal-lus altijd minstens één keer uitgevoerd worden. Bekijk bijvoorbeeld de volgende twee algoritmen: A:= 0 Zolang A GROTER DAN 0 Doe A:= A MIN 1 SCHRIJF A Eindzolang A:= 0 Herhaal A:=A MIN 1 SCHRIJF A Totdat A KLEINER DAN 0 Eindherhaal
Het eerste verschil dat opvalt is dat de conditie precies omgekeerd is; bij de Zolang wordt doorgegaan zolang A groter is dan nul, bij de Herhaal wordt doorgegaan totdat A kleiner is dan nul. Verder worden de opdrachten binnen de lus in het eerste algoritme niet uitgevoerd (want als de Zolang-lus begint is A gelijk aan nul en dus wordt de lus overgeslagen), terwijl in het tweede algoritme de opdrachten binnen de lus wél één keer uitgevoerd worden. Aan het eind van het eerste algoritme is A nog steeds nul, aan het eind van het tweede algoritme is A min 1 geworden. In het algemeen is de Herhaal-constructie: Hoofdstuk 3.4
pagina 3.4 - 10
Herhaal opdrachten Totdat conditie Eindherhaal
Een Zolang-lus is altijd om te schrijven in een Herhaal-lus en andersom. Je moet dan wel goed opletten dat je de conditie omdraait en dat de opdrachten niet opeens één keer te veel (of te weinig) uitgevoerd worden. Bijvoorbeeld in de volgende gedeeltes van een algoritme: (we gaan er vanuit dat A ≥ 0 en een geheel getal is) Zolang A IS_ONGELIJK 0 Doe A:=A MIN 1 Eindzolang Herhaal A:= A MIN 1 Totdat A IS 0 Eindherhaal
Dit gaat meestal goed, behalve als A nul is! In het eerste algoritme is er dan geen probleem, we slaan de lus gewoon over. In het tweede algoritme beginnen we echter wel aan de opdrachten in de lus en dus wordt er van A één afgetrokken. Als we dan bij de conditie komen is A gelijk aan -1 en dus beginnen we weer vooraan de lus. Het gevolg is dat A nooit meer 0 wordt en dat we dus altijd door gaan met van A één aftrekken! In dit geval zeggen we dat we in een oneindige lus zitten. Je moet dus altijd controleren of de eindconditie wel kan optreden ! Voorbeeld: Simulatie van mutaties Hoewel mutaties niet veel voorkomen zijn ze de bron van genetische variabiliteit in een populatie. Een puntmutatie is eigenlijk een chemisch proces waarbij een base in de DNA-code wordt vervangen door een andere base. Dit veroorzaakt een verandering in de genetische informatie op een bepaalde locus. Dit chemische proces is ook omkeerbaar. In dit voorbeeld zullen we mutaties bekijken waar, door een puntmutatie, een heel allel verandert. Veronderstel dat allel A met een bepaalde mutatiesnelheid in allel a muteert en vice versa. Schematisch weer gegeven door:
A
u ¤ v
a
pagina 3.4 - 11 Waarbij u de mutatiesnelheid van A naar a is en v de mutatiesnelheid van a naar A. Als het systeem zich in evenwicht bevindt dan wordt net zoveel van A naar a gemuteerd als er van a naar A gemuteerd wordt. Dit evenwicht kan worden beschreven door de volgende vergelijkingen: vq = up p = (1-q) Waarbij q de frequentie van allel a is en p de frequentie van allel A. Voor elke willekeurige generatie kan de verandering in frequentie van a worden gevonden door de formule:
Dq = -vq + up
= -vq + u(1-q) Als we aannemen dat er geen verschil in fitness is tussen A en a dan geldt voor elke generatie: q(t) = q(t-1) + q(t-1) We maken een algoritme dat de frequenties q en p in het evenwichtspunt berekent. Hierbij nemen we aan dat u=10-8 en v=10 -7 en dat het evenwicht gevonden is als q < 0.00001. Het algoritme voor simulatie van mutaties wordt: PROGRAM ‘SimulMutatie’ {Simuleer mutaties} q:=0.5 p:=0.5 u:=0.00000001 v:=0.0000001 e:=0.00001
Herhaal
dq := (-v MAAL q) PLUS u MAAL (1 MIN q) { bereken verandering in freq. } q := q PLUS dq { bereken nieuwe frequentie van allel}
Totdat
dq KLEINER DAN e
Eindherhaal
{ tot evenwicht gevonden }
p := 1 MIN q SCHRIJF p,q
3.4.4
Lussen in lussen Bij sommige problemen zijn meerdere lussen nodig. Een tweede lus kan ook binnen een andere lus zitten. We noemen dit geneste lussen (ook wel lussen in lussen). Een voorbeeld hiervan zien we in het volgende algoritme: PROGRAM ‘Klok’ {Boots een klok na} uren := 0 minuten := 0 Herhaal uren := uren PLUS 1 Herhaal SCHRIJF uren,minuten minuten := minuten PLUS 1 Totdat minuten IS 60 Eindherhaal minuten := 0
Hoofdstuk 3.4
pagina 3.4 - 12
Totdat uren IS 12 Eindherhaal
Dit algoritme simuleert een klok, eerst worden de uren en minuten op nul gezet, daarna gaan we de eerste Herhaal -lus in. Hierin wordt uren met 1 verhoogd, dan komen we in de tweede Herhaal-lus. De opdrachten van de tweede lus worden uitgevoerd totdat minuten 60 geworden is, dan gaan we uit de lus en wordt minuten weer gelijk aan nul. Omdat uren nu 1 is zijn we nog niet klaar met de eerste Herhaal-lus, we beginnen dus weer bovenaan en tellen 1 bij de uren op. Dan komen we wéér in de tweede Herhaal-lus, omdat minuten ondertussen weer op nul gezet is, worden de opdrachten binnen de tweede lus weer 60 keer uitgevoerd. Op het scherm zien we het volgende: 10 11 12 : 1 59 20 21 : : 12 0 12 1 : : 12 59
We kunnen de lussen zo diep nesten als we willen (d.w.z. we kunnen binnen de lus-in-de-lus ook weer een lus zetten en daarbinnen nog een, enz., enz.). We kunnen alle soorten lussen nesten, een lus binnen een andere lus hoeft niet van het zelfde soort te zijn als de 'omvattende' lus. Een uitgebreide versie van het 'klok'-programma kan bijvoorbeeld zijn: PROGRAM ‘KlokExt’ {Uitgebreide klok} uren := 0 minuten := 0 Herhaal Zolang minuten KLEINER DAN 60 Doe Voor seconden := 0 Tot 59 SCHRIJF uren,minuten,seconden Eindvoor minuten := minuten PLUS 1 Eindzolang minuten := 0 uren := uren PLUS 1 Totdat uren IS 12
pagina 3.4 - 13
Eindherhaal Voorbeeld: Epidemie Het verloop van een epidemie is sterk afhankelijk van een aantal factoren. In dit voorbeeld komen een aantal van deze factoren ter sprake en gaan we kijken hoe het verloop van een epidemie afhangt van de grootte van een populatie. In een populatie (mensen, zeehonden, varkens) kan een epidemie ontstaan door 1 besmettelijk individu in een populatie met allemaal vatbare individuen te plaatsen. Het verwachte aantal individuen dat het zieke individu tijdens zijn ziekte besmet noemen we R. Na verloop van tijd wordt de zieke weer beter en is immuun voor de ziekte geworden. Voor elk individu dat besmet wordt door het zieke individu geldt ook weer dat hij R andere individuen kan besmetten. Bij dit laatste gaan we ervan uit dat de vermindering van de vatbare populatie met R individuen niet noemenswaardig is. Hieruit volgt dat als: R>1 dan ontstaat er een epidemie. (elk individu besmet zelf meer dan 1 individu, het aantal zieken neemt dus toe) R<1 dan sterft de ziekte uit (elk individu besmet zelf minder dan 1 individu, het aantal zieken neemt dus af) De grootte van R is afhankelijk van 3 factoren: S: Het aantal vatbare individuen in de populatie Als we aannemen dat een ziek individu na verloop van tijd weer beter wordt en dan immuun is voor de ziekte, dan neemt het aantal vatbare individuen af door 'gewone' sterfte en besmetting door de ziekte. Het aantal vatbare individuen neemt toe door geboorte. b: De kans per dag dat een vatbaar individu besmet wordt. c: De kans per dag dat de een ziek individu geneest (het verwachte aantal dagen dat een individu ziek is, is dan 1/c, dus wanneer de kans op genezing 1/7 is dan is een individu gemiddeld 7 dagen ziek). Met deze drie factoren kunnen we R berekenen: R = b.S.(1/c) = (b.S)/c Stel: P: is Z: is g: is d: is
het totaal aantal individuen van de populatie (constant) het aantal zieken de fractie van de populatie die een kind krijgt de fractie van de populatie die sterft
dan kunnen we het volgend stelsel van vergelijkingen opstellen (tijdseenheid = 1 dag): S(t) = S(t-1) + ((P.g) - (S(t-1).d)) - Z(t-1).R(t).c Z(t) = Z(t-1) + Z(t-1).R(t).c - Z(t-1).c R(t) = b.S(t-1)/c We nemen aan dat b en c gedurende de hele epidemie constant blijven. Met dit stelsel van vergelijkingen kunnen we op elk tijdstip zien hoeveel individuen er ziek zijn en hoeveel er vatbaar zijn. Uit de hierboven gegeven vergelijkingen blijkt dat R afhankelijk is van het aantal vatbaren en dat het aantal vatbaren afhankelijk is van de populatiegrootte. Wat we nu willen weten is: hoe verandert het verloop van de epidemie met de populatiegrootte.
Hoofdstuk 3.4
pagina 3.4 - 14 We willen voor 20 populatiegrootten weten (van 2 miljoen tot 40 miljoen), na hoeveel dagen de epidemie is afgelopen (de epidemie hoeft niet te stoppen, de ziekte kan ook resident aanwezig blijven. R is dan ongeveer 1). Het volgende algoritme: - brengt bij elk van de 20 populatiegrootten 1 ziek individu in de populatie - simuleert de epidemie - stopt na 3 jaar, of stopt wanneer het aantal zieken (Z(t)) 0 is. Per populatiegrootte schrijven we op hoelang de epidemie heeft geduurd (als er na 3 jaar nog zieken waren, dan wordt het aantal zieken opgeschreven). We nemen aan dat: g = d = 0.001 c = 1/(8.5) b = 1/(2 x P) PROGRAM ‘Epidemie’ {Simuleer het verloop van een epidemie} g := 0.001 {fractie van de populatie wat kind krijgt} d := 0.001 {fractie van de populatie wat sterft} c := 1 GEDEELD DOOR 8.5 P := 0 Voor pop:=1 Tot 20 {doe voor 20 populatiegrootten } P := P PLUS 2000000 { nieuwe populatiegrootte } b := 1 GEDEELD DOOR (2 MAAL P) {besmettingskans} S := P {aantal vatbare individuene} Z := 1 {aantal zieken} t := 0 Herhaal { herhaal tot epidemie afgelopen of tijd om } R := (b MAAL {Sa)a n t a l G EbD e sEm E eL tDt e personen} S := S PLUS (P MAAL g) MIN (S MAAL d) PLUS Z MAAL R MAAL c Z := Z PLUS (Z MAAL R MAAL c) MIN Z MAAL c t := t PLUS 1 SCHRIJF t,R,S,Z
Totdat
(Z KLEINER DAN 0) OF (Z IS 0) OF ( t IS 1095)
Eindherhaal Als Dan
t IS 1095
SCHRIJF 'na 1095 dagen was het aantal zieken ' PLAK Z
Anders
SCHRIJF 'De epidemie is na ' PLAK t PLAK ' dagen afgelopen.'
Eindals Eindvoor
Een al heel oud algoritme is dat van Euclides voor het vinden van de grootste gemene deler van twee getallen. Het is een voorbeeld van een algoritme met een conditie in een lus. PROGRAM ‘GGD’ {Euclides’algoritme voor Grootste Gemene Deler} LEES ‘A’ LEES ‘B’ Zolang A IS_ONGELIJK B Doe Als A GROTER DAN B Dan
DOOR
pagina 3.4 - 15
A:=A MIN B Anders B:=B MIN A Eindals Eindzolang SCHRIJF ‘Grootste gemene deler is: ‘, PLAK A
Hoofdstuk 3.4
pagina 3.4 - 16
