Véletlenített algoritmusok

Előadás: heti 3 óra március 20-április 20-ig nincsennek órák, Teljesítés módja: Kollokvium. A félév során a házifeladatok megoldásával, és az egyes előadások feldolgozásával, összefoglalók készítésével lehet a vizsgára plusszpontokat szerezni. A kollokvium során egy az megadott kérdéssorból összeállított vizsgát kell megoldani. A vizsgán 100 pont érhető el, a bizonyításokat nem tartalmazó kérdések legalább 40 pont értékűek lesznek. Osztályozás: 50-60 (2), 61-70 (3), 71-85(4), 86-100(5).

A kurzus felvételének előfeltételei: Algoritmusok és adatszerkezetek I., Valószínűségszámítás vagy sztochasztika, matematikai érdeklődés.

Tematika:

A kurzus során bemutatjuk az alapvető technikákat, amit a véletlenített algoritmusok tervezése és elemzése során használnak. A technikákat különböző területeken kifejlesztett algoritmusok és elemzéseik bemutatásával ismertetjük. A fő részek:

1. Alapvető fogalmak, véletlenített bonyolultsági osztályok.

2. Játékelméleti módszerek

3. Valószínűségszámítási módszer (Lovász Lokális Lemma).

4. Algebrai technikák, ujjlenyomat módszer, interaktív bizonyítási rendszerek

5. Alkalmazások főként gráf algoritmusok, geometriai algoritmusok, közelítő algoritmusok, párhuzamosított algoritmusok, online algoritmusok területén.

Ajánlott irodalom:

A kurzushoz irodalom csak angol nyelven van, ezért angol nyelvtudás javasolt. A kurzus anyaga elsősorban az [1] könyv témáján alapul.

[1] R. Motvani, P. Raghavan, Randomized Algorithms, Cambridge University Press, 1998

Fontos tudnivalók, linkek

• Első előadás: alapfogalmak, véletlen felosztó elemmel gyorsrendezés, minimális vágás feladata, bonyolultsági osztályok, játékfa kiértékelése összefoglaló , a házifeladatok már meg vannak oldva.
• Második előadás: mátrixjátékok, minimax elv, Yao elv, alkalmazás a játékfa kiértékelésre, halasztott döntés elve, ujjlenyomat technika: matrixszorzas, polinomazonossag Schwartz Zippel tétel, párosítás, összefoglaló a házifeladatok megoldva
• Harmadik előadás: ujjlenyomat: sztringek összehasonlítása, mintaillesztés, interaktív bizonyítási rendszerek (IP osztály) gráf nem izomorfizmus, 3SAT számlálási változata, visszafele elemzés módszere, konvex burok, összefoglaló a házifeladatok megoldva
• Negyedik előadás: elfoglalási probléma, kupongyűjtő probléma, stabil házassági feladat, Chernoff korlát (példák), forgalomirányítási probléma összefoglaló
• Ötödik előadás: Valószínűségszámítási módszer, MAX-SAT feladat aproximációs algoritmus, Lovász Lokális Lemma, alkalmazás a K-SAT problémára, összefoglaló
• Hatodik előadás: Online algoritmusok, lapozási feladat, determinisztikus és véletlenített alsó korlátok, determinisztikus véletlenített bélyegző algoritmus, reciprok algoritmus a súlyozott lapozási feladatra összefoglaló
• Hetedik előadás: Online algoritmusok: véletlenített alsó korlát a k-szerver algoritmusra. Markov láncok: alapfogalmak, főtétel, 2-SAT algoritmus, korlát a lefedési időre összefoglaló
• Nyolcadik előadás: Párhuzamosított és elosztott algoritmusok: alapfogalmak, maximális független halmaz, választás egyeztetési probléma, Byzantine megegyezés összefoglaló