Budapesti Műszaki és Gazdaságtudományi Egyetem
Természettudományi Kar		 Tantárgy Adatlap
Tantárgy kód BMETE91AM50
Tantárgy azonosító adatok
1. A tárgy címe Véletlen algoritmusok
2. A tárgy angol címe Random Algorithms
3. Heti óraszámok (ea + gy + lab) és a félévvégi követelmény típusa 2 + 0 + 0 v Kredit 2
4. Ajánlott/kötelező előtanulmányi rend
vagy Tantárgy kód 1 Rövid cím 1 Tantárgy kód 2 Rövid cím 2 Tantárgy kód 3 Rövid cím 3
4.1 BMEVISZAB01 AlgoritmusElm
4.2
4.3
5. Kizáró tantárgyak
6. A tantárgy felelős tanszéke Algebra Tanszék
7. A tantárgy felelős oktatója Dr. Rónyai Lajos beosztása egyetemi tanár
Akkreditációs adatok
8. Akkreditációra benyújtás időpontja 2015.02.16. Akkreditációs bizottság döntési időpontja 2016.04.18.
Tematika
9. A tantárgy az alábbi témakörök ismeretére épít
Algoritmuselmélet, sztochasztika
10. A tantárgy szerepe a képzés céljának megvalósításában (szak, kötelező, kötelezően választható, szabadon választható)
TTK Matematika (BSc) képzés Adattudományi sávjának kötelezően választható tárgya.
11. A tárgy részletes tematikája
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.
12. Követelmények, az osztályzat (aláírás) kialakításának módja
szorgalmi
időszakban		 zárthelyi vizsga-
időszakban		 írásbeli vizsga
13. Pótlási lehetőségek
TVSZ szerint
14. Konzultációs lehetőségek
TVSZ szerint
15. Jegyzet, tankönyv, felhasználható irodalom
Rónyai Lajos: Véletlen algoritmusok (online jegyzet)
16. A tantárgy elvégzéséhez átlagosan szükséges tanulmányi munka mennyisége órákban (a teljes szemeszterre számítva)
16.1 Kontakt óra
28
16.2 Félévközi felkészülés órákra
14
16.3 Felkészülés zárthelyire
0
16.4 Zárthelyik megírása
8
16.5 Házi feladat elkészítése
0
16.6 Kijelölt írásos tananyag elsajátítása (beszámoló)
0
16.7 Egyéb elfoglaltság
0
16.8 Vizsgafelkészülés
10
16.9 Összesen
60
17. Ellenőrző adat Kredit * 30
60
A tárgy tematikáját kidolgozta
18. Név beosztás Munkahely (tanszék, kutatóintézet, stb.)
Dr. Rónyai Lajos
egyetemi tanár
Algebra Tanszék
A tanszékvezető
19. Neve aláírása
Dr. Nagy Attila