Budapesti Műszaki és Gazdaságtudományi Egyetem
Természettudományi Kar		 Tantárgy Adatlap
Tantárgy kód BMETEAGBsMVALG-00
Tantárgy azonosító adatok
1. A tárgy címe Véletlen algoritmusok
2. A tárgy angol címe Randomized Algorithms
3. Heti óraszámok (ea + gy + lab) és a félévvégi követelmény típusa 2 + 0 + 0 f Kredit 3
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 BMEVISZAA08 Algoritmuselmélet
4.2
4.3
5. Kizáró tantárgyak
6. A tantárgy felelős tanszéke Algebra és Geometria Tanszék
7. A tantárgy felelős oktatója Dr. Kiss Sándor beosztása egyetemi docens
Akkreditációs adatok
8. Akkreditációra benyújtás időpontja 2026.05.14. Akkreditációs bizottság döntési időpontja 2026.05.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 kötelezően választható tantá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.

The objective of the  course is to enable students to design and analyse randomised algorithm, and have a first understanding of randomness in the context of computation.
Major topics: Existence and randomness. Existence proofs using probailistic arguments (the Erdős method) through notable examples (2-coloring of hypergraphs, diagonal Ramsey numbers, good assignments for a 2-CNF, etc. ), with algorithmic aspects. Probabilistic proof for Turán's theorem. Derandomization. – Analysis of some important randomized algorithms: the expected running time of quicksort, Rabin-Miller primality test, the Schwartz-Zippel lemma and some applications (Tutte determinant, equality testing). Randomized pattern matching. Minimum weight spanning tree in expected linear time. Random walks and algorithms. Lovász local lemma, applications and algorithmic aspects. – Randomness and complexity classes. RP and Las Vegas classes with examples. The IP language class: non isomorphic graphs, interactive proof for #3-SAT. The BPP and RL complexity classes. –  Random graph models. Erdős–Rényi graphs, threshold functions. Watts-Strogatz and Albert-Barabási graph models. Kleinberg's algorithmic small world.
12. Követelmények, az osztályzat (aláírás) kialakításának módja
szorgalmi
időszakban		 Egy félévközi zárthelyi dolgozat. vizsga-
időszakban
13. Pótlási lehetőségek
A zárthelyi egy alkalommal pótolható.
14. Konzultációs lehetőségek
Az oktatóval egyeztetve
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
30
16.3 Felkészülés zárthelyire
30
16.4 Zárthelyik megírása
2
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
0
16.9 Összesen
90
17. Ellenőrző adat Kredit * 30
90
A tárgy tematikáját kidolgozta
18. Név beosztás Munkahely (tanszék, kutatóintézet, stb.)
Dr. Kiss Sándor
egyetemi docens
BME TTK Algebra és Geometria Tanszék
A tanszékvezető
19. Neve aláírása
Dr. Hegedüs Pál