A tantárgy az alábbi témakörök ismeretére épít:
Algoritmuselmélet, sztochasztika
A tantárgy szerepe a képzés céljának megvalósításában:
TTK Matematika (BSc) képzés Adattudományi sávjának kötelezően választható tárgya.
A tantárgy részletes tematikája magyarul és angolul:
A tárgy célja, hogy a hallgatóink képesek legyenek randomizált algoritmusok tervezésére, és elemzésére. Alapelv: minden egyes témához sok konkrét alkalmazást mutatunk be, hangsúlyt helyezünk a szemléletre.
Tematika: Létezés és véletlen (4 óra). Véletlent használó egzisztanciabizonyítások (az ún. Erdős-módszer) nevezetes példákon keresztül (hipergráf
2-színezése, Ramsey-gráfok, stb.), ezek algoritmikus vonatkozásai. A Turán-tétel véletlent használó bizonyítása. Derandomizálás.
Néhány nevezetes randomizált algoritmus elemzése (8 óra). A gyorsrendezés várható lépésszáma . A Rabin—Miller-prímteszt elemzése. A Schwartz—Zippel-lemma és közvetlen alkalmazásai (Tutte-determináns, mátrixszorzás ellenőrzése). Randomizált mintaillesztés. Minimális feszítőfa számítása lineáris várható időben. Bolyongások és algoritmusok. Lovász lokális lemmája (2 óra). A módszer ismertetése, néhány egyszerű alkalmazása, a módszer algoritmikus változata. Véletlen és bonyolultsági osztályok (8 óra ea). Az RP és a Las Vegas nyelvosztályok,
példákkal. Az IP nyelvosztály: nem izomorrf gráfok, IP=PSPACE lényeges részének a bizonyítása. Nulla ismeretű bizonyítás fogalma, példák. A
BPP nyelvosztály, a BPP és a P viszonyával foglalkozó néhány eredmény vázlatos ismertetése. Az RL nyelvosztály. Véletlen grá fok (4 óra) Erdős- Rényi-gráfok, néhány gráftulajdonság (pl. összefüggőség) evolúciója. Barabási-Albert-gráfok, alkalmazásuk (számítógépes-, szociális-, biológiai-) hálózatok modellezésére.
Követelmények szorgalmi időszakban:
Követelmények vizsgaidőszakban:
Konzultációs lehetőségek:
Jegyzet, tankönyv, felhasználható irodalom:
Rónyai Lajos: Véletlen algoritmusok (online jegyzet)
Nyomtatóbarát változat
