Optimális adaptív keresés kis kapacitású, megbízhatatlan tesztekkel Fizika, Földtudományok és Matematika

35 OTDK, Fizika, Földtudományok és Matematika Szekció, Kombinatorika és gráfelmélet Tagozat.

Optimális adaptív keresés kis kapacitású, megbízhatatlan tesztekkel

Hallgatók: Márton Dávid
Szak: Matematikus, Képzés típusa: msc, Intézmény: Szegedi Tudományegyetem, Kar: Természettudományi és Informatikai Kar,
Fraknói Ádám
Szak: Matematika, Képzés típusa: bsc, Intézmény: Eötvös Loránd Tudományegyetem, Kar: Természettudományi Kar,
Simon Dániel Gábor
Szak: Matematika, Képzés típusa: bsc, Intézmény: Egyéb külföldi felsőoktatási intézmény, Kar: N

Témavazetők: Lenger Dániel Antal - doktorandusz, Eötvös Loránd Tudományegyetem Természettudományi Kar ,
Pálvölgyi Dömötör - egyetemi adjunktus, Eötvös Loránd Tudományegyetem Természettudományi Kar

Dolgozatunkban egy kombinatorikai keresési problémát vizsgálunk. Két játékos – a Kérdező és a Válaszoló – játszanak, a Válaszoló gondol egy számra az `{1,ldots,n}`  halmazból, a Kérdező ezt szeretné kitalálni. Ehhez minden körben megkérdezheti egy legfeljebb `k`  elemű részhalmazról, hogy tartalmazza-e a gondolt számot vagy sem. Erre a Válaszoló mindig azonnal válaszol úgy, hogy a játék során legfeljebb `l` -szer hazudhat. Ez a Rényi–Ulam-játék egy nehezített verziója. Vizsgálatunk tárgya, hogy benne a Kérdező egy optimális stratégiája hány kérdés után találja meg a gondolt számot a legrosszabb esetben.

Ezt az értéket jelöljük `RU_l^k(n)` -nel, mellyel kapcsolatban korábban csak az `l=1`  esetben születtek eredmények. Ezen eredményeket javítjuk, illetve általánosítjuk dolgozatunkban. Megadunk egy legfeljebb `(2l+1)` -es pontatlanságú alsó becslést tetszőleges `n,k`  értékek esetén, továbbá pontosan meghatározzuk `RU_l^k(n)` -et, amennyiben `n> > k` .

Ezen probléma vizsgálata hasznos lehet abból a szempontból is, hogy ha a halmazunk elemeit embereknek tekintjük, és köztük a Válaszoló által gondolt ember vírussal fertőzött, akkor a keresési feladatunk modellezi az úgynevezett pooling tesztelési stratégiát, hiszen kis kapacitású, megbízhatatlan tesztekkel, adaptív módon akarjuk megtalálni a vírusos személyt.