BMETE91AM50

Nyomtatóbarát változatNyomtatóbarát változat
Tantárgy azonosító adatok
A tárgy címe: 
Véletlen algoritmusok
A tárgy angol címe: 
Random Algorithms
A tárgy rövid címe: 
VéletlenAlgoritmusok
2
0
0
v
Kredit: 
2
Ajánlott/Kötelező előtanulmányi rend
1.Követelménytárgy kódja: 
BMEVISZAB01
1.Követelménytárgy (rövidített) címe: 
AlgoritmusElm
A tantárgy felelős tanszéke: 
Algebra Tanszék
A tantárgy felelős oktatója: 
Dr. Rónyai Lajos
A tantárgy felelős oktatójának beosztása: 
egyetemi tanár
Akkreditációs adatok
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
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: 
zárthelyi
Követelmények vizsgaidőszakban: 
írásbeli vizsga
Pótlási lehetőségek: 
TVSZ szerint
Konzultációs lehetőségek: 
TVSZ szerint
Jegyzet, tankönyv, felhasználható irodalom: 
Rónyai Lajos: Véletlen algoritmusok (online jegyzet)
A tárgy elvégzéséhez átlagosan szükséges tanulmányi munka mennyisége órákban (a teljes szemeszterre számítva)
Kontakt óra: 
28
Félévközi felkészülés órákra: 
14
Felkészülés zárthelyire: 
0
Zárthelyik megírása: 
8
Házi feladat elkészítése: 
0
Kijelölt írásos tananyag elsajátítása (beszámoló): 
0
Egyéb elfoglaltság: 
0
Vizsgafelkészülés: 
10
Összesen: 
60
Ellenőrző adat: 
60
A tárgy tematikáját kidolgozta
Név: 
Dr. Rónyai Lajos
Beosztás: 
egyetemi tanár
Munkahely (tanszék, kutatóintézet, stb.): 
Algebra Tanszék
A tanszékvezető neve: 
Dr. Nagy Attila
A tantárgy adatlapja PDF-ben: