Hamis érme keresés párok összehasonlításával
| Témavezető: | Pálvölgyi Dömötör |
| ELTE TTK, Számítógéptudományi Tanszék | |
| email: | domotor.palvolgyi@ttk.elte.hu |
Projekt leírás
Klasszikus kereséselmélet kérdés, hogy ha n pénzérme közül az egyik hamis, és a súlya kisebb, mint a többi érmének, akkor hány mérésre van szükségünk egy kétkarú mérlegen a legrosszabb esetben, hogy ezt az érmét biztosan megtaláljuk: a válasz log_3(n). Mi történik, ha van egy további megkötésünk, miszerint a mérleg mindkét serpenyőjébe legfeljebb egy érme kerülhet? Könnyen látható, hogy ebben az esetben a lépésszám már lineárisan fog nőni az érmék számával. Egy hamis érme esetén nem is különösebben nehéz meghatározni, hogy n/2 mérésre van szükségünk. Két hamis érme esetén is egy egyszerű gondolatmenet megmutatja, hogy nagyságrendileg 2n/3 a helyes válasz. Három hamis érme esetén azonban meglepő módon 7n/10 mérés is elég, ami kevesebb a természetesen adódó 3n/4-es felső korlátnál. Ez éles. Több hamis (konstans számú) érme esetén is van egy rekurzió, aminek a segítségével meg lehet határozni az aszimptotikát, azonban a rekurzió igen bonyolult. Az derült ki, hogy általában d hamis érme esetén a <d-dimenziós terek bizonyos feldarabolásaira kell rekurziót csinálnunk, amit kézzel már kis d értékek esetén is nagyon sok számolás elvégezni. A szükséges programozási feladatot elvégezni egyáltalán nem triviális, de megfelelő képzettség mellett igen érdekes eredményekhez vezethet.
Előfeltételek
Csak az jelentkezzen, aki képes egy d-dimenziós tér lineáris feldarabolásait leprogramozni, darabolások közös finomítását kiszámolni stb.