Aszimptotikusan biztos esemény

Aszimptotikusan bizonyos eseménynek nevezzük azt az eseményt , amelynek valószínűsége valamely paramétertől függ, és a végtelenségig tart , vagyis ennek az eseménynek a valószínűsége tetszőlegesen magasra tehető . Egy ilyen eseményről azt mondják, hogy „ nagy valószínűséggel ” ( az angol nagy valószínűséggel , általában whp-re rövidítve ) vagy „ aszimptotikusan majdnem biztosan ” ( aszimptotikusan majdnem biztosan ) következik be. Minden majdnem biztos esemény (ami valószínűséggel történik ) aszimptotikusan biztos, fordítva nem igaz. $n$ $egy$ $n$ $n$ $egy$

A számítástechnikában a valószínűségi algoritmusok aszimptotikus elemzésében használják . Például, ha valamelyik algoritmus csúcsokkal rendelkező gráfokon dolgozik, és annak a valószínűsége, hogy az algoritmus a helyes eredményt adja , akkor kellően sok csúcs esetén a gráfban annak a valószínűsége, hogy az algoritmus a helyes választ adja, közel lesz , vagyis azt mondhatjuk, hogy "az algoritmus nagy valószínűséggel helyes. $n$ $1-1/n$ $egy$

Néhány az aszimptotikus bizonyosság fogalmát használó algoritmus:

Miller-Rabin teszt : valószínűségi algoritmus annak ellenőrzésére, hogy egy szám prím vagy összetett, ha összetett, akkor az algoritmus ezt nagy valószínűséggel határozza meg; $n$ $n$
Freivalds-algoritmus : véletlenszerű algoritmus a mátrixszorzat ellenőrzésére, gyorsabb, mint az ismert determinisztikus algoritmusok nagy valószínűséggel;
derékszögű fa : véletlenszerű bináris keresőfa, amelynek magassága nagy valószínűséggel logaritmikus.

A gépi tanulásban egy valószínűleg megközelítőleg helyes tanulási sémát használnak , amelyben a szerkesztett függvényben nagy valószínűséggel alacsony az általánosítási hiba.

Külön kiemeljük a BQP komplexitási osztályt , amely olyan problémákból áll, amelyekhez polinomiális kvantum algoritmusok vannak , amelyek nagy valószínűséggel helyesek.

Linkek

Metivier, Y.; Robson, JM; Saheb-Djahromi, N.; Zemmari, A. Egy optimális bitkomplexitású randomizált elosztott MIS algoritmus // Distributed Computing : Journal. - 2010. - 20. évf. 23 , sz. 5-6 . — 331. o . - doi : 10.1007/s00446-010-0121-5 .
Az elosztott számítástechnika alapelvei (7. előadás) (hivatkozás nem elérhető) . ETH Zürich. Letöltve: 2015. február 21. Az eredetiből archiválva : 2015. február 21.. (határozatlan)