Speciális algoritmusok vizsgatematika 2013. december

1. Példák véletlenített algoritmusokra (munkatárs felvétel és elemzése rekurzióval és indikátor változókkal, rendezőfa építés és elemzése rekurzióval és indikátor változókkal, adatbázisok egyenlőségének vizsgálata és a ráerősítés, prímek generálása)

2. A véletlenített algoritmusok néhány jellemzője (hiba valószínűség, a futási idő és egyéb erőforrások legrosszabb, legjobb, illetve várható értéke). A véletlenített algoritmusok osztályozása a hiba valószínűsége alapján: Las Vegas, Monte Carlo, kétoldali Monte Carlo, egyoldali Monte Carlo (+, - oldali , illetve igaz, hamis oldali), példák.

3. A Las Vegas és a passzos Las Vegas. Egyenértékűségük. Példa arra, hogy Las Vegasból készülhet értelmesen passzos változat is.

4. Az egyoldali Monte Carlo algoritmusok. Példa. A klasszikus (a hiba valószínűsége nem nagyobb ½) és gyengített változat egyenértékűsége. A hiba valószínűségének csökkentése ismétléssel (ráerősítés).

5. Kétoldali Monte Carlo algoritmus, példa, korlátlan és korlátozott változat. A hiba valószínűségének csökkentése ismétléssel (ráerősítés).

6. Véletlenített algoritmusok maximum, illetve minimum feladatokban, a +, illetve - oldali Monte Carlo. A hiba valószínűségének csökkentése ismétléssel (ráerősítés). A minimális vágás feladat véletlenített megoldása

7. A minimális vágás feladat, a megoldás tisztán véletlen és vegyes változata, a ráerősítés alkalmazása.

8. A véletlenített algoritmusok tervezésénél használt paradigmák (az ellenség elbuktatása, ujjlenyomat módszer, tanú módszer, véletlen mintavétel, ráerősítés, véletlen kerekítés. Mindegyikre egy-egy példa (vázlatosan, elemzések nélkül).

9. Védekezés az ellenséges inputok ellen 1. (az ellenség elbuktatása, foiling the adversary), a módszer bemutatása a Quick-sort rendezésen és a k. elem kiválasztásának algoritmusán keresztül.

10. Védekezés az ellenséges inputok ellen 2. A szótár adattípus, legfontosabb műveletei, implementálása hasításos technikával, véletlen inputok esete és az ellenséges inputok esete. Az univerzális hasítás.

11. Az ujjlenyomat módszer (finger printing), sémája, alkalmazásai (adatbázis egyenlőség, résszó probléma, metszet probléma, mintaillesztés, Rabin-Carp féle véletlenített mintaillesztési eljárás)

12. A tanúk bősége (abundance of witnesses). Az elnevezés magyarázata, a megoldandó feladat absztrakt sémája, speciális esetei (univerzális igaz tanú, igaz tanúk határozott többsége, az igaz válaszban sohasem tévedő tanúk, a hamis válaszban sohasem tévedő tanúk, CO NP, NP). Véletlenítés a tanúk halmazából való véletlen választással. Freivalds algoritmusa

13. Véletlen kerekítés (random rounding). Sémája: visszavezetése egész értékű, illetve {0,1} értékű lineáris programozásra, áttranszformálás lineáris programozási feladatra és annak megoldása, majd véletlen kerekítés egészekre. A minimális fedés és a MaxEkSat megoldása véletlen kerekítéssel.