plik


Dodatek A Wiadomości z kombinatoryki i elementarnego rachunku prawdopodobieństwa Zrozumienie podstaw matematycznych algorytmów genetycznych nie przedstawia trudności, ale wymaga gruntownej znajomości operacji na zbiorach skończonych, kombinatoryki i elementarnego rachunku prawdopodobieństwa. Dodatek ten ma służyć z jednej strony jako krótkie wprowadzenie dla nowicjuszy, a z drugiej - jako zwięzła powtórka dla osób, którym wiedza ta już nieco wywietrzała z głów. Materiał ten może być traktowany jako tymczasowa kładka ratunkowa, ale nie trwały most łączący ze stałym lądem. Ten ostatni można zbudować tylko uważnie studiując standardowe podręczniki (Feller, 1968; Hines i Montgomery, 1980; Papoulis, 1984; Ross, 1976). Nie bacząc nato, zajmiemy się dalej zliczaniem skończonego i zgłębianiem prawdopodobnego. Omówimy regułę iloczynu, permutacje i kombinacje. Wprowadzimy pojęcie przestrzeni zdarzeń elementarnych, sformułujemy trzy aksjomaty prawdopodobieństwa i przedstawimy niektóre wynikające z nich konsekwencje. Wspomnimy krótko o prawdopodobieństwie warunkowym, twierdzeniu Bayesa, niezależności zdarzeń oraz o najprostszych rozkładach prawdopodobieństwa. Na zakończenie omówimy pojęcie wartości oczekiwanej dyskretnej zmiennej losowej i sformułujemy ważne twierdzenie graniczne. A.1. Reguła iloczynu Większość z nas uznaje umiejętność liczenia za oczywistą, jednak sposoby dokładnego zliczania wzorców, kategorii lub podziałów na grupy stanowią rodzaj abstrakcyjnej sztuki noszącej miano kombinatoryki lub analizy kombinatorycznej. Większość wzorów ko-mbinatorycznych daje się wyprowadzić z prostej zasady, zwanej regulą iloczynu: «.:. Jeżeli doświadczenie M ma m możliwych wyników, a doświadczenie N - n możliwych wyników, to istnieje łącznie m-n wyników doświadczenia złożonego MN. 330 A. Wiadomości z kombinatoryki i elementarnego rachunku prawdopodobieństwa Prawdziwość tej zasady można wykazać, wypisując wszystkie możliwe wyniki w postaci macierzowej. Zamiast tego, zilustrujemy jej zastosowanie na kiłku prostych przykładach. Przykład 1 Student spodziewa się piątki lub czwórki ze Struktur Danych. Nie jest natomiast pewien, którą z ocen 5, 4, 3 lub 2 otrzyma z Algorytmów Genetycznych. Ile jest zestawów ocen z tych przedmiotów, które może on uzyskać? Odpowiedź: Istnieje m-n = 2'4 = 8 możliwości, a mianowicie: 5-5, 5-4, 5-3, 5-2, 4-5, 4-4, 4-3,4-2. Przykład 2 Ile sześciopozycyjnych numerów rejestracyjnych można utworzyć, jeżeli trzy pierwsze znaki mają być literami alfabetu łacińskiego, a trzy pozostałe cyframi? Odpowiedź: Można utworzyć 26 • 26 • 26 racyjnych. 10 • 10 • 10 = 17576000 numerów rejest- Przykład 3 Ile numerów rejestracyjnych można utworzyć przy założeniach jak wyżej, jeśli ponadto litery ani cyfry nie mogą się powtarzać? Odpowiedź: Pierwszą literę wybieramy spośród 26 możliwych. Drugą literę wybieramy spośród 25 możliwych itd. Ostatecznie otrzymujemy 26 • 25 • 24 • 10 • 9 • 8 = 11 232 000 różnych numerów rejestracyjnych bez powtarzających się znaków. Przykład 4 W komitecie Narodów Zjednoczonych zasiadają przedstawiciele trzech krajów członkowskich w następującym składzie: Japonia (7), Chiny (3), Stany Zjednoczone (6). Ile podkomitetów można utworzyć wybierając po jednym przedstawicielu każdego kraju? Odpowiedź: Można utworzyć 7 • 3 • 6 = 126 różnych podkomitetów. A.2. Permutacje Permutacja jest to uporządkowanie zbioru złożonego z różnych przedmiotów. Dla przykładu rozważmy sześć możliwych uporządkowań trzech liter A, B i C: ABC, ACB, BAC, BCA, CAB, CBA Ogólnie, w celu policzenia wszystkich permutacji n różnych przedmiotów, zauważmy, że pierwszy przedmiot możemy wybrać na n sposobów, a przy każdym następnym tracimy jeden stopień swobody. A zatem, zgodnie z regułą iloczynu, całkowita liczba permutacji n przedmiotów jest równa n(n - l)(n - 2)...3 • 2 • 1 = n\. Istnieje więc n\ (czytaj: n silnia) permutacji n przedmiotów. A.3. Kombinacje 331 Przykład 5 Na ile sposobów można ustawić zawodników w dziewięcioosobowym zespole baseballowym? Odpowiedź: 9! = 9 • 8 • ...3 • 2 • 1 = 362880 : ••„!-• '; ', ". "J'- >'^- •' '1' ,V 'i / ' ó ' !.' ' - • : ' . - ; ; . ' • • :' • ' - ' ' '• •• ' \j''' Przykład 6 Przypuśćmy, że na półce stoją cztery publikacje na temat algorytmów genetycznych (AG), sześć na temat systemów klasyfikujących (SK), jeden z dziedziny genetyki populacji (GEN) i siedem ze sztucznej inteligencji (SI). Na ile sposobów można je posegregować, zachowując podział tematyczny? Odpowiedź: Ustalmy pewien porządek tematów, powiedzmy AG, SK, GEN, SI. Mamy teraz 4! 6! 1! 7! = 87 091 200 uporządkowań prac w ramach wybranego porządku tematycznego. Ponieważ same tematy można uporządkować na 4! sposobów, otrzymujemy łącznie 4! • 87091 200 = 2090 188800 tematycznych uporządkowań 18 publikacji. Jest to oczywiście znacznie mniej niż 18! = 6,402 x 10'5 uporządkowań pozatematycznych. Niekiedy interesuje nas liczba wyborów uporządkowanych, których można dokonać w grupie n przedmiotów. Przypuśćmy, że chcemy policzyć wszystkie możliwe wybory uporządkowane r przedmiotów ze zbioru n przedmiotów. Podobnych obliczeń do-konaliśmyjuż wjednym z wcześniejszych przykładów. Uogólniając ten wynik, otrzymamy następujący wzór na liczbę P(n,r) permutacji r elementów wybranych ze zbioru n-elementowego: P(n, r) = n(n - \)(n - 2)...(n - r 4- 1), (r czynników) Wyrażając to za pomocą silni, uzyskamy bardziej zwartą postać wzoru: P(n, r) = n(n - \)(n - 2)...(n -r+ 1) = n\l(n - r)\ ' Ov'^> Przykład? Na ile sposobów można ustawić dziewięciu zawodników z 15-osobowej drużyny baseballowej, zakładając, że każdy zawodnik może zagrać na każdej pozycji? Odpowiedź: P(15,9) = 15!/(15 - 9)! = 1 816214400. A.3. Kombinacje W pewnych przypadkach interesuje nas liczba różnych wyborów nieuporządkowanych (komhinacji) przedmiotów z danego zbioru. Dla przykładu rozważmy wszystkie wybory uporządkowane dwóch liter z trzech: AB, AC, BA, BC, CA, CB 332 A. Wiadomości z kombinatoryki i elementarnego rachunku prawdopodobieństwa Istnieje oczywiście 3!/(3 - 2)! = 6 takich wyborów; jeśli jednak chcemy określić liczbę różnych par, pomijając ich porządek (utożsamiając np. AB i BA), to musimy podzielić liczbę wyborów uporządkowanych przez liczbę „duplikatów". Ponieważ liczba „duplikatów" jest równa liczbie uporządkowań r przedmiotów, zatem liczba kom- binacji r-wyrazowych ze zbioru w-elementowego (symbolicznie: C(n,r) lub ( ), co czy-tamy,,nnadr")jestrowna C(n,r) = n\ _ n(n- \)...(n-r+ 1) (n - r)!r! ~ ~r\ Bardziej intuicyjne uzasadnienie tego wyniku można podać w postaci następującej równości werbalnej: Liczba wyborów nieuporządkowanych r spośród n przedmiotów liczba uporządkowań r przedmiotów = liczba wyborów uporządkowanych r spośród n przedmiotów Przykład 8 Senat Stanów Zjednoczonych liczy 100 senatorów. Ile pięcioosobowych podkomitetów można utworzyć z członków tego szacownego ciała? Odpowiedź: Ponieważ kolejność wyboru w skład komitetu nie jest istotna (pomijając /100\ względy prestiżowe oraz starszeństwa), istnieje I = 75 287 520 takich podkomitetów. Przykład 9 W grze w pokera każdy gracz otrzymuje pięć zakrytych kart. Na ile sposobów można rozdać karty danemu graczowi? •<• - •' •',. r ' '.' -fi>:i~;..: - . • • • • - • • - • - (52\ Odpowiedź: Ponieważ porządek rozdawania nie jest istotny, istnieje różnych sposobów. A.4. Wzór dwumianowy Podamy tu wzór dwumianowy bez wyprowadzenia: . uV^' A.5. Zdarzenia 333 Ze względu na powyższy wynik, liczby \ = C(n, r) nazywają się współczynnikami dwumianowymi. Wzór ten jest przydatny w rozmaitych obliczeniach kombinatorycznych i probabilistycznych. Przykład 10 Pokazac,zeX" •' Odpowiedź: l"= = (1 + 1)" = 2". A.5. Zdarzenia Przypuśćmy, że dokonujemy eksperymentu, którego wynik zależy od przypadku. Zbiór S wszystkich możliwych wyników takiego doświadczenia będziemy nazywać przestrzenią zdarzeń elementarnych (lub przestrzenią prób). Oto kilka przykładów: j Rzutmoneta:5'={orzel,reszka} Rzut kostką do gry: 5 = {1, 2, 3, 4, 5, 6} Rzut dwiema monetami: 5={OO, OR, RO, RR} Zdarzeniem E nazywamy dowolny podzbiór możliwych wyników doświadczenia (zdarzeń elementarnych). Oto dwa przykłady: Co najmniej jeden orzeł w dwóch rzutach: E={OO, OR, RO} Więcej niż trójka przy rzucie kostką: L={4, 5, 6} Mając dwa zdarzenia E i F możemy utworzyć z nich nowe zdarzenia za pomocą operacji sumy i przecięcia (iloczynu) zbiorów. Suma zdarzeń E'\ F(symbolicznie: EuF) jest przedstawiona graficznie na diagramie Venna w postaci zakreskowanego obszaru (rys. A.1). Podobnie iloczyn zdarzeń E i F (symbolicznie: EF) jest zilustrowany na Rys. A.1. Diagram Venna dla sumy zdarzeń E \ F 334 A. Wiadomości z kombinatoryki i elementarnego rachunku prawdopodobieństwa Rys. A.2. Diagram Venna dla iloczynu zdarzeń E \ F Rys. A.3. Diagram Venna dla wykluczających się zdarzeń L i F rys. A.2. Jeżeli iloczyn dwóch zdarzeń jest zbiorem pustym (EF = 0) to mówimy, że zdarzenia te wzajemnie się wykluczają (rys. A.3). Na koniec zdefiniujemy zdarzenie Ec przeciwne do zdarzenia E, jako podzbiór tych wszystkich zdarzeń elementarnych, które nie należą do E. Na rysunku A.4 przedstawiono graficznie przestrzeń zdarzeń elementarnych S, zdarzenie E i zdarzenie przeciwne Ec. Rys. A.4. Diagram Venna dla zdarzenia E \ przeciwnego doń zdarzenia E° A.6. Aksjomaty prawdopodobieństwa W rachunku prawdopodobieństwa przyjmuje się trzy aksjomaty, z których można wyprowadzić wszystkie inne wyniki. Definiujemy wielkość P(E} zwaną prawdopodobieństwem zdarzenia E. Wielkość ta musi spełniać następujące aksjomaty: A.6. Aksjomaty prawdopodobieństwa 335 Aksjomat 1 0< P(E} < 1. Prawdopodobieństwo zdarzeniajest liczbą z przedziału [0,1]. Aksjomat 2 P(5)=1 * ; ' ' ; '' Prawdopodobieństwo całej przestrzeni S''jest równe 1. Aksjomat 3 Dla dowolnego ciągu parami wykluczających się zdarzeń Et, i= 1, 2,... 00 ~ ,) = X P(E,) Prawdopodobieństwo sumy zdarzeń wykluczających się parami jest równe sumie prawdopodobieństw tych zdarzeń. Z powyższych aksjomatów wynikają twierdzenia rachunku prawdopodobieństwa; dalej sformułujemy kilka ważniejszych wyników bez podawania dowodu. Prawdopodobieństwozdarzeniaprzeciwnego P(EC) = 1 - P(E) Prawdopodobieństwo zdarzenia przeciwnego jest równe jeden minus prawdopodobieństwo danego zdarzenia. Prawdopodobieństwosumydwóchzdarzeń P(E u F) = P(E} + P(F} - P(EF} Prawdopodobieństwo sumy dwóch zdarzeń jest równe sumie prawdopodobieństw tych zdarzeń pomniejszonej o prawdopodobieństwo ich iloczynu. Chociaż podajemy ten wzór bez dowodu, staje się on intuicyjnie oczywisty, jeśli odwołać się do diagramu Venna z rys. A.2. Ilustruje on wyraźnie fakt podwójnego liczenia zdarzeń elementarnych w przypadku sumowania zdarzeń nakładających się na siebie. Powyższy wzór uwzględnia po prostu poprawkę do tej sumy, polegającą na odjęciu prawdopodobieństwa części wspólnej. Zdarzenie S zazwyczaj nazywane jest zdarzeniem pewnym Qirzyp. tlum.). 336 A. Wiadomości z kombinatoryki i elementarnego rachunku prawdopodobieństwa A.7. Przypadek jednakowych szans W wielu sytuacjach zakłada się, że mamy do czynienia z jednakowo prawdopodobnymi wynikami doświadczenia losowego; dla przykładu wymieńmy tu: rzut uczciwą monetą, obrót koła ruletki, rzut wyważoną kostką, wybór karty z dobrze potasowanej talii. Jeśli ograniczymy się do modeli, w których wszystkie zdarzenia elementarne uważa się za równie prawdopodobne, to prawdopodobieństwo dowolnego zdarzenia E wyraża się w prosty sposób: liczba elementów E liczba elementów 5 Przykład 11 Jakie jest prawdopodobieństwo wyrzucenia 1 lub 2 oczek przy rzucie rzetelną kostką do gry? '•" • ^ - Odpowiedź: P(E} = 2/6 = 1/3. t , . Przykład 12 Jakie jest prawdopodobieństwo wyrzucenia w sumie 8 oczek przy rzucie dwiema kostkami? Odpowiedź: Sumę 8 oczek można otrzymać na pięć sposobów: (2, 6), (6, 2), (3, 5), (5, 3) oraz (4, 4). Zatem P(E} = 5/(6 • 6) = 5/36. Przykład 13 Jakie jest prawdopodobieństwo wypadnięcia co najmniej jednego orła w 10 rzutach uczciwą monetą? Odpowiedź: Rozważmy zdarzenie przeciwne. Istnieje oczywiście tylko jeden sposób (R, R, R, R, R, R, R, R, R, R), aby nie otrzymać ani jednego orła na 2'" możliwych 10--elementowych sekwencji. Zatem prawdopodobieństwo zdarzenia przeciwnego wynosi P(EC) = (l/2)10, skąd P(E) = 1 - (l/2)10 = 0,999. Przykład 14 Jakiejest prawdopodobieństwo otrzymania przy grze w pokera pokera cesarskiego z ręki? /52\ Odpowiedź: Są cztery pokery cesarskie ^eden w każdym kolorze) na możliwych /52\ rąk. Zatem P(L) = 4/ = 1,5 x 10^*. Przykład 15 Jakie jest prawdopodobieństwo otrzymania przy grze w pokera strita z ręki? A.8. Prawdopodobieństwo warunkowe 337 Odpowiedź: Strit składa się z pięciu następujących po sobie kart nie będących tego samego koloru (wówczas byłby to poker). Aby wyznaczyć liczbę stritów, rozważmy uporządkowaną sekwencję kart, w której jeden strit został ujęty w nawiasy kwadratowe ": [A2345]678910JQKA -l^-r:> ..*•'. Istnieje oczywiście 4 • 4 • 4 • 4 -4 = 45 różnych stritów typu A-2-3-4-5, ponieważ każdą z kart można wybrać z dowolnego z czterech kolorów; jednak dokładnie cztery z tych stritów są pokerami, tak więc mamy 45-4 zwyczajnych stritów typu A-5. To samo obliczenie pozostaje w mocy dla każdego z pozostałych typów stritów w talii, a przesuwając nawiasy wzdłuż wypisanej sekwencji stwierdzamy bez trudu, że jest 10 takich /52\ typów. W rezultacie istnieje 10(45-4) zwyczajnych stritów na rąk. A zatem W P(E} = 10200/2598960 = 0,00392. A.8. Prawdopodobieństwo warunkowe W wielu życiowych sytuacjach jedno zdarzenie zależy od drugiego i łatwiej jest mówić o prawdopodobieństwie zajścia pewnego zdarzenia lub obliczać je, wiedząc, że zaszło inne związane z nim zdarzenie. Takie prawdopodobieństwo nazywamy warunkowym; używamy przy tym oznaczenia P(E\F) - prawdopodobieństwo warunkowe zdarzenia E pod warunkiem, że zaszło zdarzenie F. Związek między prawdopodobieństwem warunkowym, prawdopodobieństwem iloczynu obu zdarzeń oraz prawdopodobieństwem zdarzenia warunkującego wyraża się wzorem: P(EF} = P(E\F}P(F} Oznacza to, że prawdopodobieństwo iloczynu dwóch zdarzeń jest równe iloczynowi prawdopodobieństwa warunkowego jednego z tych zdarzeń pod warunkiem zajścia zdarzenia warunkującego i prawdopodobieństwa zdarzenia warunkującego. v- l'KiXV^ Przykład 16 Kasia ma do wyboru dwa wykłady, jeden z algorytmów genetycznych i drugi z mechaniki płynów. Kasia ocenia szanse otrzymania piątki na egzaminie z algorytmów genetycznych na 50%, a na egzaminie z mechaniki płynów na 75%. Jakie są jej szanse, że zakończy semestr piątką z algorytmów genetycznych, jeżeli podejmie decyzję co do wykładu rzucając rzetelną monetą? Sekwencja uwzględnia tzw. strita amerykańskiego albo łatanego fj)rzyp. tlum.). 338 A. Wiadomości z kombinatoryki i elementarnego rachunku prawdopodobieństwa Odpowiedź: Niech A oznacza zdarzenie polegające na tym, że Kasia otrzyma piątkę z egzaminu, a B ~ zdarzenie polegające na tym, że wybierze ona wykład z algorytmów genetycznych. P(AB) = P(A \ B)P(E} = 0,5 • 0,5 = 0,25 Kasia ma jedną szansę na cztery, że zakończy semestr piątką z algorytmów genetycznych. A.9. Rozbicia zdarzeń W niektórych przypadkach łatwiej wyznaczyć prawdopodobieństwo danego zdarzenia, rozbijając je na dwa lub więcej wzajemnie wykluczających się zdarzeń (por. rys. A.5). Przypuśćmy, że interesuje nas prawdopodobieństwo zdarzenia E, ale umiemy więcej o nim powiedzieć w związku ze zdarzeniem F. Biorąc pod uwagę, że zdarzenia EF i EFC wykluczają się (patrz rys. A.5) oraz EF u EF* = E, mamy stąd P(E} = P(EF} + P(EFC). Korzystając z pojęcia prawdopodobieństwa warunkowego, wprowadzonego w poprzednim punkcie, możemy przepisać ostatnią równość w postaci: P(E) = P(EIF)P(F) + P(E\FC)P(FC) = P(E\F)P(F) + P(E\ F')[1 - P(F)] Rys. A.5. Diagram Venna ilustrujący rozbicie zdarzenia fFna zdarzenia EF'\ EF i '1,V T '". •: Przykład 17 Przypuśćmy, że w przykładzie 16 Kasia może wybrać wykład z mechaniki płynów (zdarzenie C) lub z algorytmów genetycznych (zdarzenie B), ale nie oba jednocześnie i załóżmy, jak poprzednio, że podejmuje ona decyzję na podstawie rzutu monetą. Obliczyć prawdopodobieństwo, że Kasia otrzyma piątkę na egzaminie (zdarzenie A). Odpowiedź: Rozbijmy zdarzenie A między dwa wykluczające się zdarzenia B i C° P(A) = P(A \B)P(B} + P(A \ QP(Q = 0,5 • 0,5 + 0,75 • 0,5 = 0,625 Korzystamy przy tym z faktu, że C = B' rzyp. ttum.). A.11. Zdarzenia niezależne 339 A.10. Reguła Bayesa Z zależności wyprowadzonej w poprzednim paragrafie można z kolei wyprowadzić inny przydatny związek, zauważając, że prawdopodobieństwo iloczynu dwóch zdarzeń można otrzymać wybierając dowolne z nich jako zdarzenie warunkujące: P(EF} = P(E \ F}P(E} = P(F I E}P(E} Spostrzeżenie to prowadzi do reguly Bayesa, z której można korzystać w celu wyznaczania prawdopodobieństw warunkowych w wielu ważnych przypadkach: P(E\F) = P(F\E}P(E) P(EF} _ P(F} ~ P(F\ E}P(E} + P(F\ EC)P(EC) A.11. Zdarzenia niezależne Mówimy, że zdarzenia E i E są niezależne, jeżeli zachodzi równość P(E\F} = P(E}. Zatem P(EF} = P(E}P(F} dla zdarzeń niezależnych °. Przykład 18 f Jakie jest prawdopodobieństwo wyrzucenia dwóch oczek przy rzucie dwiema kostkami? Odpowiedź: Wynik ten można uzyskać tylko w jeden sposób: na obu kostkach musi wypaść pojednym oczku (zdarzenie 1): P(\ + 1) = P(1)P(1) = (l/6)(l/6) = 1/36 Tę samą odpowiedź można otrzymać, zauważając, że dwa oczka odpowiadają dokładnie jednemu z 36 zdarzeń elementarnych. Przykład 19 Obliczyć prawdopodobieństwo wyrzucenia n orłów w n rzutach uczciwą monetą. Odpowiedź: Niech Hi będzie zdarzeniem polegającym na wyrzuceniu orła w /-tej próbie (i=l,2...n). P(ff, H2...Hn) = P(HJP(HJ...P(HJ = " W rachunku prawdopodobieństwa za definicję niezależności powszechnie przyjmuje się tę ostatnią równość. Jest ona ogólniejsza, gdyż obejmuje również zdarzenia o prawdopodobieństwie równym zeru, dla których prawdopodobieństwo warunkowe nie istnieje 00 Może nas także interesować rozkład sum częściowych. Centralne twierdzenie graniczne mówi, że w granicy jest to rozkład normalny (gaussowski), którego gęstość ma postać znanej krzywej w kształcie dzwonu. Z wyniku tego nie korzystaliśmy bezpośrednio w tej książce, po dokładne sformułowanie odsyłamy więc Czytelnika do standardowych źródeł. A.15. Podsumowanie W tym zwięzłym dodatku zebraliśmy kilka podstawowych wyników z zakresu kom-binatoryki i rachunku prawdopodobieństwa. Naszym zamiarem było przejrzenie podstaw w celu zrozumienia subtelności związanych z działaniem elementarnego algorytmu genetycznego. Z tą myślą omówiliśmy regułę iloczynu i elementarne prawa analizy kom-binatorycznej. Wprowadziliśmy pojęcia przestrzeni zdarzeń elementarnych i zdarzenia oraz. podaliśmy aksjomaty prawdopodobieństwa. Omówiliśmy kilka ważniejszych pojęć i twierdzeń rachunku prawdopodobieństwa, w tym prawdopodobieństwo warunkowe, twierdzenie Bayesa, wartość oczekiwaną zmiennej losowej oraz mocne prawo wielkich liczb. Z tą podbudową dyskusja i analiza własności algorytmów genetycznych powinny przebiegać bardziej gładko. A.16. Zadania A.1. Ośmioro dzieci bawi się w „komórki do wynajęcia" na sześciu krzesłach. Gdy muzyka ustaje, sześć osób siada, a dwie pozostają na stojąco. Na ile różnych sposobów można usadzić osiem osób na sześciu krzesłach? Jeśli zaniedbać kolejność siedzenia, ile można utworzyć kombinacji sześciu siedzących spośród ośmiu osób biorących udział w zabawie? 342 A. Wiadomości z kombinatoryki i elementarnego rachunku prawdopodobieństwa A.2. A.3. A.4. A.5. A.6. A.7. A.8. A.9. Ile różnych permutacji można utworzyć z liter następujących wyrazów: a) algorytm b) matematyka , .•., ,„,, Numer karty kredytowej składa się z 10 pozycji, każda z których zawiera literę (A-Z) lub cyfrę (0-9). Ile różnych numerów kart kredytowych można utworzyć w ten sposób? Programista chce zapamiętywać kody kart kredytowych w pamięci komputera binarnego w najbardziej oszczędny sposób. Oblicz minimalną liczbę bitów potrzebnych do reprezentacji numeru karty w pamięci komputera. Komitet składa się z 13 studentów I roku, 6 studentów II roku, 7 studentów III roku i 5 studentów IV roku. Zakładając, że przewodniczący komitetu zostaje wybrany losowo, oblicz prawdopodobieństwo, że przewodniczącym: a) będzie student IV roku; b) będzie student I roku; c) nie będzie student II roku; d) będzie student I lub III roku. Jakie jest prawdopodobieństwo otrzymania karety z ręki przy grze w pokera z peł- ną talią kart? W szufladzie znajduje się 20 białych i 10 czarnych skarpet. Jakiejest prawdopo- dobieństwo wyciągnięcia dokładnie dwóch czarnych skarpet przy losowym wybo- rze pięciu skarpet jednocześnie? Jak zmieni się odpowiedź, jeśli skarpety są wy- bierane pojedynczo i zwracane za każdym razem do szuflady? Na egzaminie testowym należy wybrać jedną z czterech odpowiedzi na każde z pięciu pytań. Jakie jest prawdopodobieństwo udzielenia co najmniej czterech poprawnych odpowiedzi metodą losowego zgadywania? Gracz trzyma w kieszeni dwie monety. Jedna z nich jest uczciwa, a druga ma po obu stronach orła. Gracz wyciąga z kieszeni losową monetę i wykonuje rzut. Oblicz prawdopodobieństwo, że moneta upadnie orłem do góry. Jeżeli wiadomo, że wypadł orzeł, to jakie jest prawdopodobieństwo, że wybrana moneta jest uczciwa? W ramach loterii wypuszczono milion losów, wśród których znajduje się 1 wygrana w wysokości $500000 10 wygranych w wysokości $50000 100 wygranych w wysokości $1000 lOOOwygranychwwysokości $100 10000 wygranych w wysokości $10 Jaka jest oczekiwana wysokość straty gracza biorącego udział w tej loterii, jeżeli cena losu wynosi $2,00? Jakie jest prawdopodobieństwo wygrania jakiejkolwiek nagrody? ' .., n, jest rze- A.10. Pokaż, że rozkład dwumianowy pO) = \P'(\ ~ \ji czywiście rozkładem prawdopodobieństwa.

Wyszukiwarka

Podobne podstrony:
Teoria1 Elementarny rachunek prawdopodobienstwa
Dyl D Elementy rachunku różniczkowego i całkowego w kinematyce

więcej podobnych podstron