Sam en Vatting Wiskunde Voor Informatici 2 [PDF]

Zitiervorschau

Wiskunde voor informatici 2 Hoofdstuk 1 – Basisregels combinatieleer enkele gekende getalverzamelingen: • • •

•

ℕ = de verzameling van de natuurlijke getallen ℤ = de verzameling van de gehele getallen ℚ = de verzameling van de rationale getallen ℝ = de verzameling van de reële getallen

(algemene) somregel

#(𝐴 ∪ 𝐵) = #𝐴 + #𝐵 − #(𝐴 ∩ 𝐵)

speciale somregel

#(𝐴 ∪ 𝐵) = #𝐴 + #𝐵

Productregel

#(𝐴1 × 𝐴2 × … × 𝐴𝑛 ) = #𝐴1 ∙ #𝐴2 ∙ … ∙ #𝐴𝑛

Hoofdstuk 2 - Herhalingsvariaties en variaties Herhalingsvariatie van k elementen uit n elementen Op hoeveel manieren kan je 3 genummerde balletjes in 7 hokjes leggen?

𝑉�𝑛𝑘 = #�𝐴𝑘 � = #(𝐴 × 𝐴 × … × 𝐴) =) = #𝐴 ∙ #𝐴 ∙ … ∙ #𝐴 = (#𝐴)𝑘 = 𝑛𝑘

Variatie van k elementen uit n elementen

Op hoeveel manieren kan je 3 genummerde balletjes in 7 hokjes leggen, zonder dat in een hokje meerdere balletjes komen te liggen?

𝑉𝑛𝑘 = 𝑛 ∙ (𝑛 − 1) ∙ … ∙ (𝑛 − 𝑘 + 1) =

𝑛! (𝑛 − 𝑘)!

Hoofdstuk 3 - Permutaties en herhalingspermutaties Permutaties van n elementen Op hoeveel manieren kan je 7 genummerde balletjes rangschikken?

𝑷𝒏 = 𝒏!

Herhalingspermutaties van n elementen verdeeld in k klassen Op hoeveel manieren kan je onderstaande rij genummerde balletjes rangschikken? 𝒏 ,𝒏𝟐 ,…,𝒏𝒌

𝑷𝒏𝟏

𝒏 𝒏! =� �= 𝒏𝟏 , 𝒏𝟐 , … , 𝒏𝒌 𝒏𝟏 ! ∙ 𝒏𝟐 ! ∙ … ∙ 𝒏𝒌!

Hoofdstuk 4 – Combinaties en herhalingscombinaties Combinaties van k elementen uit een verzameling van n elementen Op hoeveel manieren kan je 3 ongenummerde balletjes in 7 hokjes leggen, zonder dat in een hokje meerdere balletjes komen te liggen?

𝒏! 𝒏 𝑪𝒌𝒏 = � � = (𝒏 − 𝒌)! ∙ 𝒌! 𝒌

Herhalingscombinaties van k elementen uit n elementen Op hoeveel manieren kan je 3 ongenummerde balletjes in 7 hokjes leggen?

� 𝒌𝒏 = � 𝑪

(𝒏 + 𝒌 − 𝟏)! 𝒏+𝒌−𝟏 �= (𝒏 − 𝟏)! ∙ 𝒌! 𝒌

Hoofdstuk 5 - Inleiding eindige kansrekening kansexperiment = experiment waarvan de uitkomst door toeval wordt bepaald. uitkomst = een elementaire (of atomaire) uitkomst van een kansexperiment

uitkomstenruimte (of –universum) Ω = verzameling van alle mogelijke uitkomsten Uniforme kansruimten

Voorwaardelijke kansen

Algemene productregel

Speciale productregel

P(A) =

P(A|B) =

#𝐴 #Ω

𝑃(𝐴 ∩ 𝐵) 𝑃(𝐵)

P(A ∩ B) = P(A|B) ∙ P(B) P(A ∩ B) = P(A) ∙ P(B)

Hoofdstuk 6 – Kansvariabelen Kansfunctie Bij een kansvariabele 𝑘 definiëren we de kansfunctie 𝑓 door 𝑓(𝑘) = 𝑃(𝑘 = 𝑘)

Verdelingsfunctie Bij een kansvariabele 𝑘 definiëren we de verdelingsfunctie of de cumulatieve kansfunctie 𝐹 door 𝐹(𝑘) = 𝑃(𝑘 ≤ 𝑘)

Verwachtingswaarde

Variantie

E�𝑘� = � 𝑘 ∙ 𝑃(𝑘 = 𝑘)

𝑉𝑎𝑟�𝑘� = 𝐸�𝑘2� − 𝐸(𝑘)2

Hoofdstuk 7 – Binomiaal verdelingen De binomiale verdeling … • •

is een veelvoorkomende kansverdeling is eigenlijk een familie van verdelingen. Elke binomiale verdeling wordt bepaald door (uitleg volgt): o n : aantal pogingen o π : succeskans

notatie: 𝑘~𝐵𝑖𝑛(𝑛, 𝜋) Kansfunctie

𝑛

𝑓(𝑘) = 𝑃�𝑘 = 𝑘� = � � 𝜋𝑘 (1 − 𝜋)𝑛−𝑘 𝑘

Verdelingsfunctie

𝐹(𝑘) = 𝑃�𝑘 ≤ 𝑘� = �

Verwachtingswaarde

𝑘

𝑖=0

𝑛

� � 𝜋𝑖 (1 − 𝜋)𝑛−𝑖 𝑖

E�𝑘� = 𝑛𝜋

Variantie

𝑉𝑎𝑟�𝑘� = 𝑛𝜋(1 − 𝜋)

Hoofdstuk 8 – Hypergeometrische verdelingen De hypergeometrische verdeling … • •

is een discrete kansverdeling is eigenlijk een familie van verdelingen. Elke hypergeometrische verdeling wordt bepaald door: o N : totaal aantal elementen van gans de populatie o M : aantal “succesvolle” elementen in gans de populatie o n : grootte steekproef = aantal getrokken elementen

notatie: 𝑘~𝐻𝑦𝑝𝑔𝑒𝑜(𝑁, 𝑀, 𝑛) Verwachtingswaarde

E�𝑘� = 𝑛 ∙

Variantie 𝑉𝑎𝑟�𝑘� = 𝑛 ∙

𝑀 = 𝑛𝜋 𝑁

𝑀 𝑁−𝑀 𝑁−𝑛 𝑁−𝑛 ∙ ∙ = 𝑛𝜋(1 − 𝜋) ∙ 𝑁 𝑁 𝑁−1 𝑁−1