Fő tartalom
Számítástudomány
Tantárgy/kurzus: Számítástudomány > 2. témakör
7. lecke: Véletlen algoritmusok- Véletlen algoritmusok (bevezetés)
- Feltételes valószínűség vizuális magyarázata
- Találd ki, melyik érme volt!
- Véletlen prímteszt (bemelegítő)
- 9. szint: Próbálkozásos osztás és véletlen osztás összehasonlítása
- Kis Fermat-tétel
- Fermat-prímteszt
- 10. szint: Fermat-prímteszt
© 2023 Khan AcademyFelhasználási feltételekAdatkezelési tájékoztatóSüti figyelmeztetés
Feltételes valószínűség vizuális magyarázata
Szeretnél részt venni a beszélgetésben?
Még nincs hozzászólás.
Videóátirat
Tekintsük az alábbi példát. Bob bemegy egy szobába két érmével. Az egyik egy normális érme, a másiknak mindkét oldala fej (H). Véletlenszerűen kiválasztja az egyiket, feldobja, majd megmutatja az eredményt. - [Bob]: Fej! Mi a valószínűsége annak,
hogy a normális érmét választotta? A kérdés megválaszolásához lépésenként a
kezdetektől rajzoljuk meg a fát. Az eső esemény: kiválaszt egy érmét,
úgyhogy a fának két ágat növesztünk, a két azonos valószínűségű kimenethez,
a normális és a dupla oldalú érméhez. A következő esemény az
érme feldobása. Tovább rajzoljuk a fát, tudjuk, hogy a normális érme két, azonos
valószínűségű kimenetet eredményezhet, fejet, vagy írást. A duplaoldalú érmével is két kimenet
lehet, mind a kettő fej. Kész a fa,
látjuk, négy levele van, ami a négy lehetséges
azonos valószínűségű kimenetet mutatja. Végül megkapjuk a végső információt.
Bob közli: [Bob]: – Fej! Az új információ alapján
megnyírjuk a fát. Letöröljük az íráshoz vezető ágakat, mivel tudjuk, hogy nem írás jött ki. Elkészültünk. Annak a valószínűsége,
hogy a normális érmét választotta, az egy fej kimenet a normális ágon osztva
a három lehetséges fej kimenettel, azaz 1/3. Mi a helyzet akkor, ha újból feldobja,
és közli az eredményt? [Bob]: – Fej! Ne feledd, minden esemény után
megnő a fa. A normális érme két egyenlő
valószínűségű ágat növeszt, fejet és írást, a duplaoldalú érme
két egyenlő valószínűségű ágat növeszt, fejet, és fejet. Miután másodszor meghalljuk: [Bob]: – Fej! –, levágjuk az íráshoz vezető ágakat. Tehát annak a valószínűsége, hogy a normális érmét választotta
két egymást követő fej dobás esetén egy fej a normális érmével osztva az összes
lehetséges kimenettel, azaz 1/5. Látható, hogy a normális
érme valószínűsége az újabb fej dobásokkal egyre csökken, de soha nem éri el a nullát. Akárhányszor dobjuk fel az érmét, soha nem lehetünk 100%-osan biztosak,
hogy az érme duplaoldalú. Minden feltételes valószínűséggel
kapcsolatos kérdés megválaszolható fa rajzolásával. A biztonság kedvéért vegyünk
egy másik példát. Bobnak három érméje van,
két normális és egy cinkelt, ami miatt az esetek
kétharmadában fejre esik, egyharmadában írásra. Véletlenszerűen kiválaszt egy érmét,
és feldobja. [Bob]: – Fej! Mi annak a valószínűsége,
hogy a cinkelt érmét választotta? Lépésenként építsük fel a fát! Az első eseménynek,
az érme kiválasztásának három egyenlő valószínűségű
kimenete lehet, normális, normális, cinkelt. A következő esemény,
hogy az érmét feldobjuk. Mindkét normális érméhez két egyenlő
valószínűségű kimenet tartozik, fej és írás. A cinkelt érmének három
egyenlő valószínűségű kimenete van, két fej és egy írás. Az a trükk itt, hogy a fának
kiegyensúlyozottnak kell lennie, ami azt jelenti, hogy minden ághoz
azonos számú levélnek kell tartoznia. Ehhez azt kell tennünk, hogy megnöveljük
az ágak számát a legkisebb közös többszörösre. A 2 és 3 esetén ez 6 lesz. Végül megjelöljük a leveleket. A normális érméhez most hat egyenlő
valószínűségű levél tartozik, három fej és három írás. A cinkelt érméhez két írás
és négy fej. Megvagyunk. Bob közli az eredményt, [Bob]: – Fej! Az új információ alapján
levághatjuk az íráshoz vezető ágakat, mivel írás nem fordult elő. Így annak a valószínűsége, hogy a cinkelt
érmét választotta, ha fej jött ki: nos,
négy levél tartozik a cinkelt érméhez, osztva az összes levelek számával. 4/10, azaz 40%. Ha nem vagy biztos a dolgodban, a feltételes valószínűséges feladatok
mindig megoldhatók a Bayes-tétel alapján, ami megadja egy adott A esemény
valószínűségét, ha tudjuk, hogy B bekövetkezett. De ha elfelejtetted, akkor sincs baj. Csak azt kell tudnod, hogyan kell
történetet építened megnyírt fákkal.