game maker
Gebruikersnaam:
Wachtwoord:
Home Info Forums Help
Welkom, Gast. Alsjeblieft inloggen of registreren.
De activerings e-mail gemist?
+  Forums
|-+  Werken met Game Maker
| |-+  Tutorials en Uitbreidingen (Moderator: Maarten Baert)
| | |-+  [Tut] Combinatoriek en Kansrekening
Pagina's: [1]
« vorige volgende »
Print
Advertenties

Martin Beentjes
Gebruiker


Offline Offline

Berichten: 2332

Gelieve quotes gebruiken bij PB's.


« Gepost op: 17 Mei 2012, 19:27:13 »

Combinatoriek en kansberekening

GM Versie   N.v.t
Registratie   N.v.t
Moeilijkheidsgraad   Gemiddeld

Introductie
In deze tutorial ga ik jullie de beginselen proberen uit te leggen van combinatoriek en kansrekening. Je zult nu wel denken: "Waarom zou ik dit willen weten?". Nou dat is eigenlijk om een goede reden. De twee onderwerpen zal je bij het programmeren tegen kunnen komen. Wanneer een AI voor drie deuren staat, kan hij kiezen tussen drie deuren. Daar zit combinatoriek in, de kans dat hij deur 2 opent is weer kansrekening. Het zijn dus twee verschillende onderwerpen.

Ik heb ervoor gekozen deze tutorial te schrijven omdat ik vond dat ChrisCompany in zijn topic ([Scr] Faculteit, permutaties en combinaties) de begrippen Combinatoriek en Kansrekening als hetzelfde beschreef. In mijn opzicht zit er een verschil tussen.

De functies zijn niet beschikbaar in GM, maar ik raad je daarom aan de scripts in het topic van ChrisCompany te gebruiken. Knipoog

Inhoudsopgave
1 - Combinatoriek
1.1 - Tellen met en zonder herhaling
1.2 - Permutaties
1.3 - Faculteit
1.4 - Combinaties
2 - Kansrekening
2.1 - De kansdefinitie van Laplace
2.2 - Kansexperimenten en samengestelde kansexperimenten
2.3 - Vaasmodel
2.4 - Somregel
2.5 - Complementregel


De functies
Let even op, de functies die voorbij komen (permutaties, faculteit en combinaties) zitten niet in GameMaker verwerkt, aan het einde zal je het kopje De functiescripts in GM tegenkomen, daar staat de downloadlink bij naar het GML bestand die je kunt importeren in je GMK.

1 - Combinatoriek
In het eerste hoofdstuk ga ik je de beginselen van Combinatoriek uitleggen. Hieronder valleen bijvoorbeeld permutaties, faculteit en combinaties. Maar ik begin met het tellen met en zonder herhaling.

1.1 Tellen met en zonder herhaling
Als je een aantal mogelijkheden om van punt A naar D te gaan wilt weten, moet je dit toch gaan berkenen. Van punt A naar B zijn er 3 mogelijkheden. Van punt B naar C zijn twee mogelijkheden en van C naar D zijn er vier mogelijkheden.


Ik kan zo een paar mogelijkheden van verplaatsen van A naar D geven. Bijvoorbeeld:
Boven - onder - middenboven
Midden - onder - onder
Onder - boven - middenonder

En zo kan ik nog wel doorgaan totdat ik 24 mogelijkheden heb. Hoe kom ik nou aan die 24? Ik maak gebruik van de vermenigvuldigingsregel. Een gecombineerde handeling die bestaat uit handeling I die op p manieren kan worden uigevoerd én handeling II die op q manieren kan worden uitgevoerd én handeling III die op r manieren kan worden uitgevoerd kan op p * q * r manieren worden uitgevoerd.

In het plaatje heb ik inderdaad drie handelingen, van A naar B, van B naar C en van C naar D. We kunnen nu dus het maximaal aantal mogelijkheden berekenen.
N(maximaal aantal manieren) = 3 * 2 * 4 = 6 * 4 = 24



Maar als we nu een andere route introduceren als een punt E die alleen is verbonden met A én D dan kunnen we niet werken met enkel vermenigvuldigen. We moeten ook gaan optellen. Waarom? Omdat je of via E gaat of via de oude route (via B naar C en dan naar D). Wanneer het woordje 'of' in je omschrijving van routes voorkomt, dan gaan we optellen. En dan wordt het alsvolgt:

N(totaal aantal manieren) = (3 * 2 * 4) + (1 * 1) = 24 + 1 = 25
Omdat ik maar op één manier via E naar D kan, tel je er 1 bij de 24 manieren op. Maar als je al snel meerdere andere punten hebt, nemen de manieren snel toe.

Vuistregel: Is een vraagstelling te formuleren met en, dan moet je vermenigvuldigen.
Is een opgave te formuleren met of, dan moet je optellen.




Als je dat begrijpt, kunnen we beginnen met het tellen met en zonder herhalingen. Om dit uit te kunnen leggen geef ik een praktisch voorbeeld.

Zonder herhalingen
Een bestuur van acht personen kiest uit hun midden eerst de voorzitter, dan de secretaris en ten slotte de penningmeester. Iedereen kan maar één functie krijgen.

Oké, we hebben dus acht mensen en na elke keuze vermindert het aantal mogelijke personen. Hier zien we een telling zonder herhaling.

N(v s p) = 8 * 7 * 6 = 56 * 6 = 112 * 3  = 336

Met herhalingen
Een spelontwikkelingbedrijf ontwikkelt seriecodes door gebruik te maken van een code in de vorm van: AAA 99. Eerst drie letters en dan twee cijfers. Er kan gekozen worden uit de letters A, B, C, D en E. Het aantal mogelijke codes is:

N(l l l c c) = 5 * 5 * 5 * 10 * 10 = 25 * 5 * 100 = 125 * 100 = 12.500



1.2 - Permutaties
Nu je snapt hoe het zit met het tellen met en zonder herhaling, gaan we verder met de term permutaties. Een ander woord voor permutatie is rangschikking. In het voorbeeld van tellen zonder herhaling spreken we ook van een rangschikking. Het berekenen kunnen we dus ook op een andere manier doen.

N(v s p) = 8 nPr 3 = 336

Hé, dat is nog eens kort! Ja, inderdaad. Het is erg handig dat we zo kunnen rekenen, als je Wiskunde D zou hebben dan zal je vast wel eens permutaties tegen komen waar je hele grote getallen hebt. Dan is dit erg handig.

1.3 - Faculteit
Wanneer ik nou uit een groep van vier personen een bestuur moet vormen waarbij iedereen functie krijgt toegewezen, zou ik dus 4 nPr 4 kunnen doen. Dan zal het volgende berekend worden:

N(v s p n) = 4 * 3 * 2 * 1 = 12 * 2 = 24

Hier is het nog wel te doen, maar wat met 10 nPr 10? Dan zou ik dus uiteindelijk 3628800 mogelijke rangschikkingen kunnen krijgen! Dat is wel erg veel en niet meer uit je hoofd te berekenen. Daarom is in de Combinatoriek ook de faculteit geïntroduceerd. Om 10 faculteit uit te rekenen doen we dit:"

N(10 volgordes uit 10 mensen) = 10!

Ja, dat is een uitroepteken. Maar hier hebben we het over faculteit. Wat dit dus doet is berekenen van 10 nPr 10.

1.4 - Combinaties
We gaan een groepje van drie personen vormen. Aad, Piet, Jan en Lisa doen mee. Ik verzin zes mogelijke groepen:
Aad, Piet, Lisa.
Aad, Lisa, Piet.
Piet, Lisa, Aad.
Piet, Add, Lisa.
Lisa, Aad, Piet.
Lisa, Piet, Aad.


Maar nu heb ik maar één mogelijk groepje. Er is iets aan de hand. In deze situatie, rekenen we niet op een rangschikking en is het dus géén permutaties. Het aantal mogelijke groepjes is nu lastiger te berekenen en we doen het alsvolgt:

N(max aantal groepjes) = (4 nPr 3)/(4!)

Hier zien we een berekening waar we gebruik maken van permutaties en faculteit. We kunnen het gelukkig makkelijker noteren en dat doen we dan ook alsvolgt:

N(max aantal groepjes) = 4 nCr 3 = 4

Dit noemen we in de combinatoriek combinaties. We maken groepjes van drie personen, we kunnen kiezen uit vier personen. Omdat volgorde hier niet uitmaakt, spreken we van combinaties.
Aad, Piet, Lisa.
Aad, Piet, Jan.
Aad, Lisa, Jan.
Lisa, Piet, Jan.




2 - Kansrekening
Nu we combinatoriek gehad hebben, kunnen we verder met kansrekening. Wil je dit onderdeel begrijpen, moet je combinatoriek begrijpen. Begrijp je dat niet, dan zal je hier straks ook in de moeilijkheden komen.

2.1 - Kansdefinitie van Laplace
Pierre Simon de Laplace (1749-1827) studeerde theologie. In zijn studie raakte hij geïnteresseerd in de wiskunde. Vanaf 1789 was hij veel bezig met mechanica en waarschijnlijkheidsrekening. In 1812 verscheen zijn meesterwerk Théorie analytique des probabilités. Dit was het begin van de waarschijnlijkheidstheorie. In dit werk zei dat voor het toepassen van zijn kansdefinitie P = N(gunstig) / N(totaal) uitgegaan moet worden van even waarschijnlijke uitkomsten, zoals bij een dobbelsteen. Je hebt altijd een totaal aantal mogelijkheden van zes.

We gebruiken deze kansdefintie nog steeds. Ik geef even een voorbeeld om het te laten zien in de praktijk.

Piet gooit met een dobbelsteen van zes ogen. Wat is de kans dat hij een drie gooit?
Er zijn zes mogelijkheden, 1 tot en met 6. Er is één gunstige mogelijkheid, er komt natuurlijk maar één zijde naar boven gericht. Dus:
P(drie) = 1 / 6

2.2 - Kansexperimenten en samengestelde kansexperimenten
Het gooien van een dobbelsteen is een voorbeeld van een kansexperiment. Een kenmerk van een kansexperiment is dat de uitkomst van te voren niet vastligt. Een voorbeeld van een samengesteld kansexperiment is het gooien met twee dobbelstenen.

2.3 - Het vaasmodel
Veel vraagstukken bestaan eigenlijk uit dezelfde kern, maar omdat er een ander verhaal omheen is geschreven lijken ze allemaal anders. Wanneer je dit verhaalt weghaalt, kun je gaan bedenken hoe je een kansvraag oplost. Een van deze methodes is het vaasmodel. Om dit uit te leggen maak ik gebruik van een vraagstuk:
Citaat van: Vraagstuk
Pieter heeft bak met 30 lootjes. Op deze lootjes staan de letters A of B. A is een prijs, B is geen prijs. Er zitten 8 lootjes met A in de bak, voor de rest alleen maar lootjes met een B.

Wat is de kans nadat Pieter twee lootjes heeft gepakt, er twee lootjes met de letter A zijn gepakt?
Om hier de kans te berekenen gebruiken we het vaasmodel. We zien dit model als een vaas met een hoop gekleurde knikkers erin. We gaan het vraagstuk vertalen naar het Vaasmodel:
- 30 knikkers
- 8 rode knikkers
- 22 witte knikkers
- P(2 rode knikkers)

Dit berekenen we alsvolgt:


Wat gebeurt er bij de deling? Ik bereken eerst de gunstige mogelijkheden via combinaties (8nCr1 en 22nCr1) en deel dit door het totaal aantal mogelijkheden (30nCr). Hier komt een kans van 0,405 uit.

De kans dat Pieter twee keer een lootje met A pakt is dus 0,405.

Zo werk je veel vraagstukken door met het vaasmodel. Als je dit beheerst, is het een kwestie van het vraagstuk herkennen en dit toepassen.

2.5 - Somregel
Bij het gooien van twee dobbelstenen is P(som is 2 of som is 4) = P(som is 2) + P(som is 4). Dit is een voorbeeld van de somregel. Je mag de somregel alleen toepassen omdat de gebeurtenissen 'som is 2' en 'som is 4' geen gemeenschappelijke uitkomsten hebben. Dat betekent dat de gebeurtenissen elkaar uitsluiten.
Hebben twee gebeurtenissen wel gemeenschappelijke uitkomsten? Dan mag je de somregel niet gebruiken.

Vuistregel: Voor elkaar uitsluitende gebeurtenissen G1 en G2 geldt de somregel:
P(G1 of G2) = P(G1) + P(G2)


2.6 - Complementregel
Als ik uit een vaas 8 knikkers pak en ik wil de kans berekenen dat ik minder dan 8 witte knikkers pak, dan moet ik 8 kansen (P(0 wit) + P(1 wit) + P(2 wit).... + P(7 wit)) gaan bereken. Je ziet het al, dat is heel veel werk.

Omdat wiskundigen eigenlijk hele saaie mensen zijn, is daar wat op gevonden: de complementregel.

In plaats van P(0 wit) + P(1 wit) + P(2 wit).... + P(7 wit) te gaan berekenen bereken ik de kans als ik 8 knikkers pak en haal dat van 1 af:

P(minder dan acht) = 1 - P(acht wit)

Op deze manier bereken ik veel sneller de kans. Veel minder kans op fouten dus!


Nawoord
Ik heb veel plezier deze tutorial geschreven. Dit heeft mij ook geholpen het eerste gedeelte van Wiskunde D goed af te sluiten.

Naar boven Gelogd

The RuneSnake
Gebruiker


Offline Offline

Berichten: 4217


« Antwoord #1 Gepost op: 17 Mei 2012, 21:49:27 »

Het is een mooie en duidelijke tutorial  , bij sommige mensen kan dit wel eens van pas komen.
Ga zo door.

TR

Naar boven Gelogd

lucb1e
Gebruiker


Offline Offline

Berichten: 4554


WWW
« Antwoord #2 Gepost op: 18 Mei 2012, 01:49:28 »

+1 dit. Ongeveer de kwaliteit die je in boeken zou verwachten, de opbouw is erg methodisch (positief bedoeld dus) Gemoedelijk


Naar boven Gelogd

Ferry H.
Gebruiker


Offline Offline

Berichten: 1046

:)


WWW
« Antwoord #3 Gepost op: 18 Mei 2012, 09:24:22 »

Wow, mooie grote en Handige tut. Ook nog eens oVerziCHtelijk



Al je bestanden veilig op een online opslagplaats bij Dropbox. Een 2GB account is gratis! http://db.tt/zL3Nxa3G
Als je registreerd krijg jij en ik extra opslagplaats!

Naar boven Gelogd

Martin Beentjes
Gebruiker


Offline Offline

Berichten: 2332

Gelieve quotes gebruiken bij PB's.


« Antwoord #4 Gepost op: 18 Mei 2012, 15:49:37 »

Bedankt voor de reacties, dat doet mij goed. Gemoedelijk

Ik heb de volgorde aangehouden zoals wij het op school hebben gehad.  Die manier leek het mij het beste om te gebruiken in deze tutorial

« Laatste verandering: 18 Mei 2012, 18:03:17 door mbeentjes »
Naar boven Gelogd

thijsmie
Gebruiker


Offline Offline

Berichten: 307

Niets te melden....


« Antwoord #5 Gepost op: 18 Mei 2012, 18:06:34 »

Mooie tut, alles goed en begrijpelijk opgeschreven. Begrijpelijker dan Wiskunde Overal, Wiskunde D deel 1 4VWO in ieder geval. Ik had het hier nog in de kast staan van vorig jaar en ik heb het even erbij gepakt en weer doorgelezen, en ik denk dat ik de wiskundeleraar beter kan aanraden aan de leerlingen om deze tut te lezen....

mvg.

Thijs


Naar boven Gelogd

Martin Beentjes
Gebruiker


Offline Offline

Berichten: 2332

Gelieve quotes gebruiken bij PB's.


« Antwoord #6 Gepost op: 18 Mei 2012, 18:15:21 »

Bedankt! Dat is wel een eer als je dat vindt. Of de methode is gewoon slecht. Tong

Naar boven Gelogd

thoot-je
Gebruiker


Offline Offline

Berichten: 3232

Je kan me wakker maken voor een kop tomatensoep :D


WWW
« Antwoord #7 Gepost op: 20 Mei 2012, 19:53:34 »

Erg duidelijk Gemoedelijk
Ik ga volgend jaar naar 4havo dus ik denk dat ik het mss wel eens nodig krijg volgend jaar. Dan weet ik dat al vast Gemoedelijk


Mijn website: thomasbaake.nl

De 2 belangrijkste dingen in het leven: Productief zijn en extreem veel genieten
Naar boven Gelogd

Advertenties
« vorige volgende »
Pagina's: [1]
Print


Topic Informatie
0 geregistreerde leden en 1 gast bekijken dit topic.

Ga naar:  

Powered by SMF 1.1.21 | SMF © 2006-2007, Simple Machines
www.game-maker.nl © 2003-2019 Nederlandse Game Maker Community