Matek II. tétel Flashcards
Valószínűség fogalma és kiszámításának kombinatorikus módszerei (permutációk, variációk, kombinációk). Feltételes valószínűség, függetlenség, Bayes-formula. Algoritmusok lépésszáma, aszimptotikus jelölések. Beszúrásos rendezés, keresések lineáris és logaritmikus lépésszámmal. Táblázatok, hash függvények, hash táblák. Gráfok, szélességi és mélységi bejárás.
Valószínűség fogalma
A valószínűség matematikában és statisztikában is egy esemény bekövetkezését méri. 0 és 1 közötti értéket vehet fel.
Valószínűség kiszámolásának kombinatorikus módszerei (permutáció, variáció, kombináció).
Permutációk:
A permutáció egy olyan kombinatorikai módszer, amely azt mutatja meg, hányféle módon rendezhetők el különböző elemek. A n elemű halmaz permutációinak száma n!, azaz a faktoriális érték.
Példa: Ha van egy 3 elemű halmaz, például {A, B, C}, akkor a permutációk száma 3!=3⋅2⋅1=6, tehát 6 különböző sorrend lehetséges: ABC, ACB, BAC, BCA, CAB, CBA.
Variáció
Variációk:
A variáció egy olyan kombinatorikai módszer, amely azt mutatja meg, hányféle módon választhatók ki és rendezhetők el különböző elemek egy adott számú helyre. A k-elemű halmaz n-variációinak száma n ^ k
Példa: Ha van egy 3 elemű halmaz (A, B, C) és 2 hely, akkor a variációk száma
3 ^ 2=9: AA, AB, AC, BA, BB, BC, CA, CB, CC.
Kombináció
Kombinációk:
A kombináció egy olyan kombinatorikai módszer, amely azt mutatja meg, hányféle módon választhatók ki különböző elemek egy adott számú hely nélkül. A k-elemű halmaz n-kombinációinak száma a kombinációs szám, vagyis
C( n, k)=n! /( k!(n−k)!)
Példa: Ha van egy 3 elemű halmaz (A, B, C) és 2 elemet választunk ki belőle kombinációval, akkor a kombinációk száma
C(3,2)= 3! / 2!(3−2)!=3: AB, AC, BC.
Feltételes valószínűség
A feltételes valószínűség azt mutatja meg, hogy egy esemény bekövetkezése mennyire valószínű, figyelembe véve egy másik esemény bekövetkezését vagy nem bekövetkezését. A feltételes valószínűség jelölése P(A∣B), és azt fejezi ki, hogy milyen valószínű, hogy az A esemény bekövetkezik, ha már tudjuk, hogy a B esemény megtörtént.
P(A∣B)= P(A∩B)/P(B)
ahol: P(A∣B) a feltételes valószínűség, hogy A bekövetkezik B ismeretében,
P(A∩B) az A és B együtt bekövetkezésének valószínűsége,
P(B) a B esemény valószínűsége.
Függetlenség
Két esemény független, ha az egyik esemény bekövetkezése vagy nem bekövetkezése nem befolyásolja a másik esemény bekövetkezésének valószínűségét. Matematikailag kifejezve, ha
P(A∩B)=P(A)⋅P(B), akkor az A és B események függetlenek.
Bayes-formula
A Bayes-formula a feltételes valószínűség alkalmazásával kapcsolatos és segít az események valószínűségének frissítésében az információ bővülésekor. A Bayes-formula a következőképpen néz ki:
P(A∣B)= P(B∣A)⋅P(A) / P(B)
ahol:
P(A∣B) a feltételes valószínűség, hogy A bekövetkezik B ismeretében,
P(B∣A) a feltételes valószínűség, hogy B bekövetkezik A ismeretében,
P(A) és P(B) az A és B események valószínűségei.
A Bayes-formula például alkalmazható orvosi diagnosztikában vagy spam szűrésben, ahol az információ bővülésekor vagy újabb adatok alapján kell újraértékelni az események valószínűségét.
Algoritmusok lépésszáma
Az algoritmusok lépésszáma az az összeg, amely kifejezi, hogy hány lépés szükséges egy algoritmus végrehajtásához egy adott bemeneten. Az aszimptotikus jelölések (O-notáció, Ω-notáció, Θ-notáció) segítenek az algoritmusok hatékonyságának, futási időinek vagy tárigényeinek értékelésében az input méretének növekedésével.
O-notáció (Big O): Az algoritmus felső határa, vagyis az összegzett lépésszám legrosszabb esetben.
Ω-notáció (Big Omega): Az algoritmus alsó határa, vagyis az összegzett lépésszám legjobb esetben.
Θ-notáció (Theta): Az algoritmus pontosan középső határa, vagyis a felső és alsó határ közötti egyenlőség.
Beszúrásos rendezés
A beszúrásos rendezés egy egyszerű rendezési algoritmus, amely az elemeket egyesével veszi figyelembe, és beszúrja azokat az már rendezett részbe. A legrosszabb esetben
O(n^2) lépésszámú.
Keresések Lineáris és Logaritmikus Lépésszámmal
Lineáris keresés: Az algoritmus az elemeket sorban vizsgálja meg, amíg meg nem találja a keresett értéket vagy el nem éri a végét. Lépésszám: O(n).
Bináris keresés: A rendezett tömbön vagy listán a középső elemet hasonlítja össze a keresett értékkel, és ennek alapján eldönti, hogy a keresett elem a bal vagy jobb részben található. Lépésszám: O(logn).
Táblázatok, hash függvények, hash táblák
Táblázatok: Adatok tárolására szolgáló struktúrák. A táblázatok hatékony elérést tesznek lehetővé, de nem mindig skálázódnak jól nagy méretű adatok esetén.
Hash Függvények és Hash Táblák: A hash függvények egyedi kulcsokhoz rendelnek egy hash értéket, amely indexként szolgál a hash táblában. Hatékony keresési, beszúrási és törlési műveleteket tesznek lehetővé átlagos esetben (O(1)), de néhány kritikus esetben a hatékonyság csökkenhet (O(n)).
