Véletlen struktúrák és alk. 2+0
Szimmetrikus kombinatorikai struktúrák 2+0
Válogatott fejezetek 2+0
A sáv elvégzéséhez 6 tanegységből kell jegyet szerezni,
de a két gyakorlatból jegy szerzése kötelező.
Kombinatorikus algoritmusok I. 2+0
Adatstruktúrák 2+0
Bonyolultságelmélet gyakorlat 0+2
Bonyolultságelmélet szeminárium 2+0
A sáv elvégzéséhez 6 tanegységből kell jegyet szerezni, de
Bonyolultságelmélet előadásból, gyakorlatból, Kombinatorikus algoritmusokból
és Adatstruktúrákból mindenképpen kell jegy.
Fejezetek a halmazelméletből I. 0+2
Fejezetek a halmazelméletből II. 2+0
Fejezetek a halmazelméletből III. 2+0
Fejezetek a halmazelméletből IV. 2+0
A sáv elvégzéséhez 3 tanegységből kell jegyet szerezni.
Tantervi egység leírás
|
Megnevezés |
Gráfelmélet (Diszkrét matematika sáv) |
|
Típus |
Tantárgy |
|
Altípus |
Alternatív |
|
Fajta |
Szakmai |
|
Felelős szervezeti egység |
Számítógéptudományi Tanszék |
|
Felelős oktató |
Király Zoltán |
A tantervi egység elvégzéséhez szükséges
|
1. |
tanórák száma |
2 |
|
1.a. |
ebből előadás |
2 |
|
1.b. |
gyakorlat |
|
|
1.c. |
terepgyakorlat |
|
|
2. |
egyéni hallgatói munkaóra száma |
|
|
3. |
Összesen (1+2) |
A tantervi egység teljesítésének számonkérése
X kollokvium
¨ többféléves kollokvium egy másik tantervi egység elvégzésekor
¨ többféléves kollokvium ennek a tantervi egység elvégzésekor
¨ szigorlat
¨ gyakorlati jegy
¨ beszámoló
A tantervi egység felvételéhez teljesítendő tantervi egységek:
|
1. |
Véges matematika 2 |
|
2. |
Algebra 2 |
A tantervi egységgel párhuzamosan (vagy korábban) teljesítendő tantervi egységek:
|
1. |
Tematika:
Gráfok összefüggősége. Erősen összefüggő gráfok, Lucchesi--Younger tétel. Diszjunkt fenyők (Edmonds), diszjunkt fák (Tutte és Nash-Williams). Struktúratételek: háromszorosan összefüggő gráfok, k-élösszefüggő gráfok és irányított gráfok.
Gráfok és hipergráfok színezései. Kromatikus index: Kőnig tétele a páros gráfok élszínezéseire, Vizing, Shannon tételei az általános esetre. Háromszöget nem tartalmazó nagy-kromatikus gráfok: a Kneser-gráf és Borsuk-gráf. Kritikus gráfok.
Ramsey-tétel, van der Waerden tétel, Hales-Jewett tétel és Shelah becslése a van der Waerden számra.
Párosítás-elmélet. Kőnig, Tutte, Edmonds--Gallai tételei. A kínai postás probléma.
Perfekt gráfok. Merev körű gráfok, összehasonlítási gráfok és jellemzéseik. Perfekt gráf tétel, erős perfekt gráf sejtés. Meyniel tétele.
Gráfrekonstrukció.
Beágyazások és minorok. Síkba, (felületbe) rajzolás, Robertson--Seymour tétel.
Tantervi egység leírás
|
Megnevezés |
Gráfelmélet gyakorlat (Diszkrét matematika sáv) |
|
Típus |
Tantárgy |
|
Altípus |
Alternatív |
|
Fajta |
Szakmai |
|
Felelős szervezeti egység |
Számítógéptudományi Tanszék |
|
Felelős oktató |
Király Zoltán |
A tantervi egység elvégzéséhez szükséges
|
1. |
tanórák száma |
2 |
|
1.a. |
ebből előadás |
|
|
1.b. |
gyakorlat |
2 |
|
1.c. |
terepgyakorlat |
|
|
2. |
egyéni hallgatói munkaóra száma |
|
|
3. |
Összesen (1+2) |
A tantervi egység teljesítésének számonkérése
¨ kollokvium
¨ többféléves kollokvium egy másik tantervi egység elvégzésekor
¨ többféléves kollokvium ennek a tantervi egység elvégzésekor
¨ szigorlat
X gyakorlati jegy
¨ beszámoló
A tantervi egység felvételéhez teljesítendő tantervi egységek:
|
1. |
Véges matematika 2 |
|
2. |
Algebra 2 |
A tantervi egységgel párhuzamosan (vagy korábban) teljesítendő tantervi egységek:
|
1. |
Gráfelmélet (Diszkrét matematika sáv) |
Tematika:
Gráfok összefüggősége. Erősen összefüggő gráfok, Lucchesi--Younger tétel. Diszjunkt fenyők (Edmonds), diszjunkt fák (Tutte és Nash-Williams). Struktúratételek: háromszorosan összefüggő gráfok, k-élösszefüggő gráfok és irányított gráfok.
Gráfok és hipergráfok színezései. Kromatikus index: Kőnig tétele a páros gráfok élszínezéseire, Vizing, Shannon tételei az általános esetre. Háromszöget nem tartalmazó nagy-kromatikus gráfok: a Kneser-gráf és Borsuk-gráf. Kritikus gráfok.
Ramsey-tétel, van der Waerden tétel, Hales-Jewett tétel és Shelah becslése a van der Waerden számra.
Párosítás-elmélet. Kőnig, Tutte, Edmonds--Gallai tételei. A kínai postás probléma.
Perfekt gráfok. Merev körű gráfok, összehasonlítási gráfok és jellemzéseik. Perfekt gráf tétel, erős perfekt gráf sejtés. Meyniel tétele.
Gráfrekonstrukció.
Beágyazások és minorok. Síkba, (felületbe) rajzolás, Robertson--Seymour tétel.
Tantervi egység leírás
|
Megnevezés |
Szimmetrikus kombinatorikai struktúrák (Diszkrét matematika sáv) |
|
Típus |
Tantárgy |
|
Altípus |
Alternatív |
|
Fajta |
Szakmai |
|
Felelős szervezeti egység |
Számítógéptudományi Tanszék |
|
Felelős oktató |
Szőnyi Tamás |
A tantervi egység elvégzéséhez szükséges
|
1. |
tanórák száma |
2 |
|
1.a. |
ebből előadás |
2 |
|
1.b. |
gyakorlat |
|
|
1.c. |
terepgyakorlat |
|
|
2. |
egyéni hallgatói munkaóra száma |
|
|
3. |
Összesen (1+2) |
A tantervi egység teljesítésének számonkérése
X kollokvium
¨ többféléves kollokvium egy másik tantervi egység elvégzésekor
¨ többféléves kollokvium ennek a tantervi egység elvégzésekor
¨ szigorlat
¨ gyakorlati jegy
¨ beszámoló
A tantervi egység felvételéhez teljesítendő tantervi egységek:
|
1. |
Véges matematika 2 |
|
2. |
Algebra 3 |
A tantervi egységgel párhuzamosan (vagy korábban) teljesítendő tantervi egységek:
|
1. |
Tematika:
Projektív és affin síkok definíciója, tulajdonságai, kapcsolatuk ortogonális latin négyzetekkel. A páronként ortogonális latin négyzetek számára vonatkozó néhány eredmény (Erdős-Chowla--Straus).
Testre épített síkok és különböző reprezentációik. Projektív és affin terek. Kombinatorikus kérdések: lefogó ponthalmazok projektív síkokon és testre épített affin terekben. de Bruijn-Erdős tétel, Steiner--rendszerek.
t-(v,k,l) blokkrendszerek. Megszorítások a paraméterek között. Fisher-egyenlőtlenség (t=2-re). Ferdén metsző rendszerek, négyzetes blokkrendszerek. A Fisher-egyenlőtlenség kiterjesztése nagyobb t-re (Wilson és Petrenjuk). Lineáris algebrai módszerek, Oddtown-tétel, Hoffmann--Singleton tétel.
További nemlétezési tételek: a Bruck--Ryser--Chowla tétel és variánsai. Projektív síkok létezésével kapcsolatos kérdések.
A projektív terek hipersíkjai alkotta blokkrendszer karakterizálása (Dembowski-Wagner); a paraméterek nem definiálják a blokkrendszert egyértelműen (Kantor).
Biplane-ek (l=2), Hadamard-mátrixok és Hadamard-féle blokkrendszerek (t=2). Néhány példa, Paley-blokkrendszer, PGn-1(n,2).
Erősen reguláris gráfok: megszorítások a paramáterekre. Blokkrendszerek pont-gráfjai és erősen reguláris gráfok. Erősen reguláris gráfok módosítása: a ``switching" (Seidel). Példák: a létra-gráf, a trianguláris gráf, stb.
Blokkrendszerek rekurzív konstrukciói: pont-reziduális és blokk-reziduális rendszer, bővítés. Hadamard 3-blokkrendszerek, affin síkok bővítése (Mőbius-síkok). Projektív síkok bővítése, általában négyzetes blokkrendszerek bővítése (Cameron tétele). A Mathieu-csoportokhoz tartozó Witt-féle blokkrendszerek (vázlatos konstrukciója). Aszimptotikus eredmények blokkrendszerek létezéséről (Wilson tétele, Teirlinck tétele a t>5 blokkrendszerek létezéséről). (Ezek biz. nélkül). Differencia-halmazok és a Hall-féle multiplikátor-tétel.
|
Megnevezés |
Leszámláló kombinatorika (Diszkrét matematika sáv) |
|
Típus |
Tantárgy |
|
Altípus |
Alternatív |
|
Fajta |
Szakmai |
|
Felelős szervezeti egység |
Számítógéptudományi Tanszék |
|
Felelős oktató |
Szőnyi Tamás |
A tantervi egység elvégzéséhez szükséges
|
1. |
tanórák száma |
2 |
|
1.a. |
ebből előadás |
|
|
1.b. |
gyakorlat |
2 |
|
1.c. |
terepgyakorlat |
|
|
2. |
egyéni hallgatói munkaóra száma |
|
|
3. |
Összesen (1+2) |
A tantervi egység teljesítésének számonkérése
¨ kollokvium
¨ többféléves kollokvium egy másik tantervi egység elvégzésekor
¨ többféléves kollokvium ennek a tantervi egység elvégzésekor
¨ szigorlat
X gyakorlati jegy
¨ beszámoló
A tantervi egység felvételéhez teljesítendő tantervi egységek:
|
1. |
Véges matematika 2 |
|
2. |
Analízis 2 |
A tantervi egységgel párhuzamosan (vagy korábban) teljesítendő tantervi egységek:
|
1. |
Tematika:
Permutációk és permutációcsoportok. ,,Szimmetria erejéig különböző'' objektumok leszámlálása: Burnside-tétel, ciklus-index polinom, Pólya--Redfield--de Bruijn módszer.
Rekurziók és megoldásaik. Inverziós formulák, Lagrange-inverzió. Halmazok és számok partíciói, lineáris homogén diofantoszi egyenletek, generátorfüggvények, kombinatorikus azonosságok (binomiális együtthatók és hipergeometriai függvények, Catalan, Stirling, Bell és Fibonacci-számok), ,,Snake Oil'' módszer.
A szita-formula általánosításai: részben rendezett halmazok, hálók és Mőbius-függvényük. A Mőbius-inverziós formula, technikák a Mőbius-függvény kiszámítására.
Gráfelméleti alkalmazások (fák, feszítő fák, 1-faktorok száma).
Tantervi egység leírás
|
Megnevezés |
Extremális kombinatorika (Diszkrét matematika sáv) |
|
Típus |
Tantárgy |
|
Altípus |
Alternatív |
|
Fajta |
Szakmai |
|
Felelős szervezeti egység |
Számítógéptudományi Tanszék |
|
Felelős oktató |
Katona Gyula |
A tantervi egység elvégzéséhez szükséges
|
1. |
tanórák száma |
2 |
|
1.a. |
ebből előadás |
2 |
|
1.b. |
gyakorlat |
|
|
1.c. |
terepgyakorlat |
|
|
2. |
egyéni hallgatói munkaóra száma |
|
|
3. |
Összesen (1+2) |
A tantervi egység teljesítésének számonkérése
X kollokvium
¨ többféléves kollokvium egy másik tantervi egység elvégzésekor
¨ többféléves kollokvium ennek a tantervi egység elvégzésekor
¨ szigorlat
¨ gyakorlati jegy
¨ beszámoló
A tantervi egység felvételéhez teljesítendő tantervi egységek:
|
1. |
Véges matematika 2 |
|
2. |
Algebra 2 |
A tantervi egységgel párhuzamosan (vagy korábban) teljesítendő tantervi egységek:
|
1. |
Szimmetrikus kombinatorikus struktúrák |
Tematika:
Turán tétel és alkalmazásai. Nem-páros kizárt részgráfok: Erdős-Stone tétel, Erdős-Simonovits tétele az aszimptotikusan extrém gráfok szerkezetéről, túltelített gráfokban a) a kisebb részgráffal együtt egy nagyobb is megjelenik (Dirac tétele), b) a részgráf sok példányban jelenik meg.
Páros kizárt részgráfok: Erdős-Gallai tétele utak Turán-számáról, Kővári-T.Sós-Turán becslése a K(p,q)-et nem tartalmazó gráf maximális élszámára, Erdős-Rényi-T.Sós-Brown véges geometriai konstrukciója K(2,2) esetére, Füredi élesítése.
Szemerédi regularitási lemma és alkalmazása az Erdős-Stone tételre.
Kocka mint tiltott részgráf. Turán-Ramsey típusú tételek: maximális élszám keresése teljes k-as mentes gráfban, ha nincs nagy üres sem a gráfban (Erdős-T.Sós és Erdős-Hajnal-T.Sós-Szemerédi tétele).
Extremális hipergráf problémák: Turán sejtése, Bollobás és Szidorenko tételei olyan hipergráfokra, amelyekben nincs két (3, ill. 4)-él, melyek szimmetrikus differenciáját tartalmazza egy harmadik. Erdős tétele a tiltott K_r(t,... ,t) esetére.
Sperner tétele és alkalmazásai, YBLM egyenlőtlenség. Erdős-Ko-Rado tétele egy-metszésre. Permutációs módszer, balratolás módszere. Árnyék minimizálása. Árnyék minimizálása metsző halmazrendszerre. t-metsző rendszerek. Csillag módszer, Erdős-Ko-Rado t-metszőkre. Algebrai módszer extremális halmazrendszerekre. Kneser-gráfok kromatikus száma. Keresztben metsző halmazpár-rendszerek (Bollobás).
Extremális problémák más parciálisan rendezett halmazokra.
Tantervi egység leírás
|
Megnevezés |
Válogatott fejezetek (Diszkrét matematika sáv) |
|
Típus |
Tantárgy |
|
Altípus |
Alternatív |
|
Fajta |
Szakmai |
|
Felelős szervezeti egység |
Számítógéptudományi Tanszék |
|
Felelős oktató |
Király Zoltán |
A tantervi egység elvégzéséhez szükséges
|
1. |
tanórák száma |
2 |
|
1.a. |
ebből előadás |
2 |
|
1.b. |
gyakorlat |
|
|
1.c. |
terepgyakorlat |
|
|
2. |
egyéni hallgatói munkaóra száma |
|
|
3. |
Összesen (1+2) |
A tantervi egység teljesítésének számonkérése
X kollokvium (C)
¨ többféléves kollokvium egy másik tantervi egység elvégzésekor
¨ többféléves kollokvium ennek a tantervi egység elvégzésekor
¨ szigorlat
¨ gyakorlati jegy
¨ beszámoló
A tantervi egység felvételéhez teljesítendő tantervi egységek:
|
1. |
A tantervi egységgel párhuzamosan (vagy korábban) teljesítendő tantervi egységek:
|
1. |
Tematika:
Választható az aktuálisan meghírdetett előadások/szemináriumok közül.|
Megnevezés |
Véletlen struktúrák és alkalmazások (Diszkrét matematika sáv) |
|
Típus |
Tantárgy |
|
Altípus |
Alternatív |
|
Fajta |
Szakmai |
|
Felelős szervezeti egység |
Számítógéptudományi Tanszék |
|
Felelős oktató |
Elekes György |
A tantervi egység elvégzéséhez szükséges
|
1. |
tanórák száma |
2 |
|
1.a. |
ebből előadás |
2 |
|
1.b. |
gyakorlat |
|
|
1.c. |
terepgyakorlat |
|
|
2. |
egyéni hallgatói munkaóra száma |
|
|
3. |
Összesen (1+2) |
A tantervi egység teljesítésének számonkérése
X kollokvium (C)
¨ többféléves kollokvium egy másik tantervi egység elvégzésekor
¨ többféléves kollokvium ennek a tantervi egység elvégzésekor
¨ szigorlat
¨ gyakorlati jegy
¨ beszámoló
A tantervi egység felvételéhez teljesítendő tantervi egységek:
|
1. |
Véges matematika 2 |
|
2. |
Valószínűségszámítás |
A tantervi egységgel párhuzamosan (vagy korábban) teljesítendő tantervi egységek:
|
1. |
Gráfelmélet (Diszkrét matematika sáv) |
Tematika:
Várható érték és második momentum módszer. (R(k,k) alsó becslése, tranzitív részturnament, van der Waerden,...) Véletlen objektum algoritmikus javítása. Konstrukció nagy kromatikus számú, kis kört nem tartalmazó gráfra.
Véletlen gráfok: Küszöbfüggvény, evolúció p=1/n környékén. Klikkméret, kromatikus szám várható értéke.
Kvázivéletlen gráfok (Chung--Graham--Wilson) és spektrális jellemzésük.
Lokális lemma és alkalmazásai. van der Waerden számok, Ramsey számok alsó becslése, hipergráfok 2-színezései.
Diszkrepancia-elmélet. Beck--Fiala-tétel, Spencer ,,6-szoros szórás'' tétele.
Vapnik-Cservonenkisz dimenzió alaptétele.
Diszkrét matematika sáv elvégzésének követelményei:
|
Megnevezés |
Kombinatorikus algoritmusok I (Számítástudomány sáv) |
|
Típus |
Tantárgy |
|
Altípus |
Alternatív |
|
Fajta |
Szakmai |
|
Felelős szervezeti egység |
Operációkutatási Tanszék |
|
Felelős oktató |
Jordán Tibor |
A tantervi egység elvégzéséhez szükséges
|
1. |
tanórák száma |
2 |
|
1.a. |
ebből előadás |
2 |
|
1.b. |
gyakorlat |
|
|
1.c. |
terepgyakorlat |
|
|
2. |
egyéni hallgatói munkaóra száma |
|
|
3. |
Összesen (1+2) |
A tantervi egység teljesítésének számonkérése
X kollokvium
¨ többféléves kollokvium egy másik tantervi egység elvégzésekor
¨ többféléves kollokvium ennek a tantervi egység elvégzésekor
¨ szigorlat
¨ gyakorlati jegy
¨ beszámoló
A tantervi egység felvételéhez teljesítendő tantervi egységek:
|
1. |
Véges matematika 2 |
A tantervi egységgel párhuzamosan (vagy korábban) teljesítendő tantervi egységek:
|
1. |
Tematika:
Max-vissza sorrend és tulajdonságai, használata a Nagamochi-Ibaraki algoritmusban, maximális folyam kiszámolása a sorrend utolsó két pontja közt.Gráfok bejárásai (BFS, DFS, SFS) és ezek alkalmazásai (távolság, topologikus sorrend, erősen összefüggő irányítás, erősen összefüggő komponensek). Ritka tanúk. Merevkörű gráf szimpliciális sorrendje. Menger tétel kiterjesztése vegyes összefüggőségre, éldiszjunkt linkek. Karger algoritmusa.
Maximális súlyú stabil halmaz merevkörű gráfban. Minimális súlyú fenyő.
$k$-csoportosítás, folyam-ekvivalens fa, tranzitív lezárt, tranzitív redukció. A $2$-SAT feladat.
Legrövidebb utak, konzervatív súlyozások, potenciálok, minimális körátlag. Dijkstra algoritmus, aciklikus digráfok esete.
Dinamikus programozás: legrövidebb utak minden pontpárra, részösszeg feladat, hátizsák feladat, maximális súlyú diszjunkt intervallumrendszer, minimális háromszögelés, maximális konvex részhalmaz, RNS párosítás, közelítő szakaszok, sorozat összehasonlítás, maximális súlyú stabil halmaz fában.
Fa-felbontás, fa-vastagság, alaptulajdonságok. Maximális súlyú stabil halmaz korlátos fa-vastagságú gráfokban. Közelítő algoritmus a fa-vastagság kiszámolására.
Lokális keresés: maximális vágás, a képfelbontási feladat.
Gomory-Hu fák és alkalmazásaik. A Steiner fa feladat: NP-teljesség, a Dreyfus-Wagner algoritmus.
|
Megnevezés |
Bonyolultságelmélet (Számítástudomány sáv) |
|
Típus |
Tantárgy |
|
Altípus |
Alternatív |
|
Fajta |
Szakmai |
|
Felelős szervezeti egység |
Számítógéptudományi Tanszék |
|
Felelős oktató |
Grolmusz Vince |
A tantervi egység elvégzéséhez szükséges
|
1. |
tanórák száma |
2 |
|
1.a. |
ebből előadás |
2 |
|
1.b. |
gyakorlat |
|
|
1.c. |
terepgyakorlat |
|
|
2. |
egyéni hallgatói munkaóra száma |
|
|
3. |
Összesen (1+2) |
A tantervi egység teljesítésének számonkérése
X kollokvium
¨ többféléves kollokvium egy másik tantervi egység elvégzésekor
¨ többféléves kollokvium ennek a tantervi egység elvégzésekor
¨ szigorlat
¨ gyakorlati jegy
¨ beszámoló
A tantervi egység felvételéhez teljesítendő tantervi egységek:
|
1. |
Számítástudomány |
|
2. |
Valószínűségszámítás |
A tantervi egységgel párhuzamosan (vagy korábban) teljesítendő tantervi egységek:
|
1. |
Tematika:
Randomizált algoritmusok. Prímtesztelés. Univerzális bejáró sorozatok, térfogatszámítás. Döntési fák. Alsó becslések döntési fák mélységére. Nem-determinisztikus és randomizált döntési fák. Kommunikációs bonyolultság (determinisztikus és nemdeterminisztikus). Randomizált kommunikációs bonyolultság. Interaktív és zero--knowledge bizonyítások. Kriptográfia. RSA--kód. Információs bonyolultság. Kolmogorov--bonyolultság, entrópia, kódolás. álvéletlen bitek generálása és tesztelése. Párhuzamos algoritmusok, összeadás és szorzás. Brent tétele. Mátrixszorzás alkalmazásai. Determináns számítása. A párhuzamos számítások különböző modelljei. Rendezés. Randomizált párhuzamos algoritmusok. Alsó becslések Booole-hálózatokon.
Tantervi egység leírás
|
Megnevezés |
Nyelvek és automaták (Számítástudomány sáv) |
|
Típus |
Tantárgy |
|
Altípus |
Alternatív |
|
Fajta |
Szakmai |
|
Felelős szervezeti egység |
Számítógéptudományi Tanszék |
|
Felelős oktató |
Horváth Sándor |
A tantervi egység elvégzéséhez szükséges
|
1. |
tanórák száma |
2 |
|
1.a. |
ebből előadás |
2 |
|
1.b. |
gyakorlat |
|
|
1.c. |
terepgyakorlat |
|
|
2. |
egyéni hallgatói munkaóra száma |
|
|
3. |
Összesen (1+2) |
2 |
A tantervi egység teljesítésének számonkérése
X kollokvium
¨ többféléves kollokvium egy másik tantervi egység elvégzésekor
¨ többféléves kollokvium ennek a tantervi egység elvégzésekor
¨ szigorlat
¨ gyakorlati jegy
¨ beszámoló
A tantervi egység felvételéhez teljesítendő tantervi egységek:
|
1. |
Számítástudomány |
|
2. |
Matematikai logika |
A tantervi egységgel párhuzamosan (vagy korábban) teljesítendő tantervi egységek:
|
1. |
Tematika:
Betű, szó, nyelv; a Chomsky-féle nyelvtan-- és nyelvosztályok; az utóbbiak néhány, algebrai jellegu zártsági tulajdonsága. A Chomsky-féle nyelvhierarchia megfelelése az absztrakt automaták egy hierarchiájának. Kombinatorikai jellegű tulajdonságok. Néhány eldönthetőségi/eldönthetetlenségi eredmény. Programozási nyelvek nem-környezetfüggetlen volta. Környezetfüggetlen nyelvek szintaktikai elemzése.
Tantervi egység leírás
|
Megnevezés |
Adatstruktúrák (Számítástudomány sáv) |
|
Típus |
Tantárgy |
|
Altípus |
Alternatív |
|
Fajta |
Szakmai |
|
Felelős szervezeti egység |
Számítógéptudományi Tanszék |
|
Felelős oktató |
Király Zoltán |
A tantervi egység elvégzéséhez szükséges
|
1. |
tanórák száma |
2 |
|
1.a. |
ebből előadás |
2 |
|
1.b. |
gyakorlat |
|
|
1.c. |
terepgyakorlat |
|
|
2. |
egyéni hallgatói munkaóra száma |
|
|
3. |
Összesen (1+2) |
A tantervi egység teljesítésének számonkérése
X kollokvium
¨ többféléves kollokvium egy másik tantervi egység elvégzésekor
¨ többféléves kollokvium ennek a tantervi egység elvégzésekor
¨ szigorlat
¨ gyakorlati jegy
¨ beszámoló
A tantervi egység felvételéhez teljesítendő tantervi egységek:
|
1. |
Véges matematika 2 |
|
2. |
Számítástudomány |
A tantervi egységgel párhuzamosan (vagy korábban) teljesítendő tantervi egységek:
|
1. |
Tematika:
Gráfok megadási módjai, sor. Szélességi keresés és alkalmazásai. Rendezés kupacokkal, MIN-törlés, kulcs-csökkentés, beszúrás kupacba, kulcs-csökkentés, kupac reprezentációja, kupacépítés. Leszámláló rendezés, számjegyes rendezés.Kruskal algoritmusa, megvalósítás tömbbel; tömb + láncolt listával. Fastruktúra az Únió-Holvan feladatra, útrövidítés és útfelezés, lépésszám elemzése. Prim algoritmusa. Dijkstra algoritmusa, Dijkstra variánsai, PERT módszer. d-edfokú kupacok.
Konvex burok keresése. Potenciál és amortizációs idő. Fibonacci kupac, megvalósítás, elemzés, alkalmazása Dijkstra és Prim algoritmusra. Párosítós kupacok. Az eredeti és a lusta változat. Radix kupacok (r-kupacok).
Szótárak. Bináris keresőfák. Törlés bináris fában. Optimális statikus keresőfa konstruálása. 2-3 fák. B-fák. Piros-fekete fák. AVL fák. Sleator és Tarjan önkiegyensúlyozó fája (splay tree).
Hash-elés: jó hash függvény, születésnap paradoxon, ütközések. Vödrös hash-elés, elemzése. Szekvenciális keresés. Nyílt címzések: lineáris hash-elés. Törlés lineáris hash-eléskor. Álvéletlen és dupla hash-elés, Brent módszere. Univerzális hash-elés, az egyenletes hash-elés elemzése.
Dinamikus fák, alkalmazásuk a Dinitz-féle folyamalgoritmusban.
Kitekintés a geometriai adatstruktúrákra: egy intervallumba eső pontok lekérdezése, egy téglalapba eső pontok lekérdezése (range tree), egy pontot tartalmazzó intervallumok lekérdezése (intervallum-fák), egy irányba végtelen téglalapba eső pontok lekérdezése. Kupacos keresőfák, Egy függőleges szakaszt metsző vízszintes szakaszok lekérdezése. Szakasz-fák, egy téglalapot metsző ferde szakaszok lekérdezése.
Tantervi egység leírás
|
Megnevezés |
Bonyolultságelmélet gyakorlat (Számítástudomány sáv) |
|
Típus |
Tantárgy |
|
Altípus |
Alternatív |
|
Fajta |
Szakmai |
|
Felelős szervezeti egység |
Számítógéptudományi Tanszék |
|
Felelős oktató |
Király Zoltán, Grolmusz Vince |
A tantervi egység elvégzéséhez szükséges
|
1. |
tanórák száma |
2 |
|
1.a. |
ebből előadás |
|
|
1.b. |
gyakorlat |
2 |
|
1.c. |
terepgyakorlat |
|
|
2. |
egyéni hallgatói munkaóra száma |
|
|
3. |
Összesen (1+2) |
A tantervi egység teljesítésének számonkérése
¨ kollokvium
¨ többféléves kollokvium egy másik tantervi egység elvégzésekor
¨ többféléves kollokvium ennek a tantervi egység elvégzésekor
¨ szigorlat
X gyakorlati jegy
¨ beszámoló
A tantervi egység felvételéhez teljesítendő tantervi egységek:
|
1. |
Számítástudomány |
A tantervi egységgel párhuzamosan (vagy korábban) teljesítendő tantervi egységek:
|
1. |
Bonyolultságelmélet (Számítástudomány sáv) |
Tematika:
Diagonalizációs módszer alkalmazásai. Alternáló hierarchia. Alsó becslések Boole-hálózatokra. Orákulumos Turing-gépek. Polinomiális hierarchia. PSPACE-teljesség. IP=PSPACE, MIP=NEXP, alkalmazások: áttetsző bizonyítások, approximálhatatlanság.
Tantervi egység leírás
|
Megnevezés |
Bonyolultságelmélet szeminárium (Számítástudomány sáv) |
|
Típus |
Tantárgy |
|
Altípus |
Alternatív |
|
Fajta |
Szakmai |
|
Felelős szervezeti egység |
Számítógéptudományi Tanszék |
|
Felelős oktató |
Király Zoltán |
A tantervi egység elvégzéséhez szükséges
|
1. |
tanórák száma |
2 |
|
1.a. |
ebből előadás |
2 |
|
1.b. |
gyakorlat |
|
|
1.c. |
terepgyakorlat |
|
|
2. |
egyéni hallgatói munkaóra száma |
|
|
3. |
Összesen (1+2) |
A tantervi egység teljesítésének számonkérése
X kollokvium (C)
¨ többféléves kollokvium egy másik tantervi egység elvégzésekor
¨ többféléves kollokvium ennek a tantervi egység elvégzésekor
¨ szigorlat
¨ gyakorlati jegy
¨ beszámoló
A tantervi egység felvételéhez teljesítendő tantervi egységek:
|
1. |
Bonyolultságelmélet (Számítástudomány sáv) |
A tantervi egységgel párhuzamosan (vagy korábban) teljesítendő tantervi egységek:
|
1. |
Tematika:
Az aktuális eredmények követése, főleg a FOCS és STOC
konferenciák kötetei alapján, nagyrészt a hallgatók előadásában.
Tantervi egység leírás
|
Megnevezés |
Geometriai algoritmusok (Számítástudomány sáv) |
|
Típus |
Tantárgy |
|
Altípus |
Alternatív |
|
Fajta |
Szakmai |
|
Felelős szervezeti egység |
Számítógéptudományi Tanszék |
|
Felelős oktató |
Elekes György |
A tantervi egység elvégzéséhez szükséges
|
1. |
tanórák száma |
2 |
|
1.a. |
ebből előadás |
2 |
|
1.b. |
gyakorlat |
|
|
1.c. |
terepgyakorlat |
|
|
2. |
egyéni hallgatói munkaóra száma |
|
|
3. |
Összesen (1+2) |
A tantervi egység teljesítésének számonkérése
X kollokvium
¨ többféléves kollokvium egy másik tantervi egység elvégzésekor
¨ többféléves kollokvium ennek a tantervi egység elvégzésekor
¨ szigorlat
¨ gyakorlati jegy
¨ beszámoló
A tantervi egység felvételéhez teljesítendő tantervi egységek:
|
1. |
Véges matematika 2 |
|
2. |
Geometria |
|
3. |
Számítástudomány |
A tantervi egységgel párhuzamosan (vagy korábban) teljesítendő tantervi egységek:
|
1. |
Adatstruktúrák |
Tematika:
A Helly tételkör. Konvex burok keresése a síkban és a térben. Síkdarabolások kombinatorikus tulajdonságai. Pont helyének meghatározása síkbeli bináris kereséssel. Voronoi diagrammok és Delaunay háromszögelések.
Számítástudomány sáv elvégzésének követelményei
Tantervi egység leírás
|
Megnevezés |
Fejezetek a halmazelméletből I (Halmazelmélet félsáv) |
|
Típus |
Tantárgy |
|
Altípus |
Alternatív |
|
Fajta |
Szakmai |
|
Felelős szervezeti egység |
Számítógéptudományi Tanszék |
|
Felelős oktató |
Komjáth Péter |
A tantervi egység elvégzéséhez szükséges
|
1. |
tanórák száma |
2 |
|
1.a. |
ebből előadás |
|
|
1.b. |
gyakorlat |
2 |
|
1.c. |
terepgyakorlat |
|
|
2. |
egyéni hallgatói munkaóra száma |
|
|
3. |
Összesen (1+2) |
A tantervi egység teljesítésének számonkérése
¨ kollokvium
¨ többféléves kollokvium egy másik tantervi egység elvégzésekor
¨ többféléves kollokvium ennek a tantervi egység elvégzésekor
¨ szigorlat
X gyakorlati jegy
¨ beszámoló
A tantervi egység felvételéhez teljesítendő tantervi egységek:
|
1. |
Halmazelmélet |
|
2. |
Matematikai logika |
|
3. |
Véges Matematika 2 |
A tantervi egységgel párhuzamosan (vagy korábban) teljesítendő tantervi egységek:
|
1. |
Tematika:
Kiválasztási axioma, rendszámok aritmetikája, megszámlálható rendszámok, stacionárius halmazok, hatványfüggvény, játékok, rendezett halmazok, részben rendezett halmazok, partíciók.
Tantervi egység leírás
|
Megnevezés |
Fejezetek a halmazelméletből II (Halmazelmélet félsáv) |
|
Típus |
Tantárgy |
|
Altípus |
Alternatív |
|
Fajta |
Szakmai |
|
Felelős szervezeti egység |
Számítógéptudományi Tanszék |
|
Felelős oktató |
Komjáth Péter |
A tantervi egység elvégzéséhez szükséges
|
1. |
tanórák száma |
2 |
|
1.a. |
ebből előadás |
2 |
|
1.b. |
gyakorlat |
|
|
1.c. |
terepgyakorlat |
|
|
2. |
egyéni hallgatói munkaóra száma |
|
|
3. |
Összesen (1+2) |
A tantervi egység teljesítésének számonkérése
X kollokvium
¨ többféléves kollokvium egy másik tantervi egység elvégzésekor
¨ többféléves kollokvium ennek a tantervi egység elvégzésekor
¨ szigorlat
¨ gyakorlati jegy
¨ beszámoló
A tantervi egység felvételéhez teljesítendő
tantervi egységek:|
1. |
Halmazelmélet félsáv 1 |
A tantervi egységgel párhuzamosan (vagy korábban) teljesítendő tantervi egységek:
|
1. |
Tematika:
Kombinatorikus halmazelmélet. Végtelen gráfok. Stacionárius halmazok. Ramsey-tétel és partíció kalkulus. Elérhetetlen, Mahlo, gyengén kompakt, mérhető, szuperkompakt számosságok. A szinguláris számosság probléma.
Tantervi egység leírás
|
Megnevezés |
Fejezetek a halmazelméletből III (Halmazelmélet félsáv) |
|
Típus |
Tantárgy |
|
Altípus |
Alternatív |
|
Fajta |
Szakmai |
|
Felelős szervezeti egység |
Számítógéptudományi Tanszék |
|
Felelős oktató |
Komjáth Péter |
A tantervi egység elvégzéséhez szükséges
|
1. |
tanórák száma |
2 |
|
1.a. |
ebből előadás |
2 |
|
1.b. |
gyakorlat |
|
|
1.c. |
terepgyakorlat |
|
|
2. |
egyéni hallgatói munkaóra száma |
|
|
3. |
Összesen (1+2) |
A tantervi egység teljesítésének számonkérése
X kollokvium
¨ többféléves kollokvium egy másik tantervi egység elvégzésekor
¨ többféléves kollokvium ennek a tantervi egység elvégzésekor
¨ szigorlat
¨ gyakorlati jegy
¨ beszámoló
A tantervi egység felvételéhez teljesítendő tantervi egységek:
|
1. |
Halmazelmélet |
|
2. |
Matematikai logika |
A tantervi egységgel párhuzamosan (vagy korábban) teljesítendő tantervi egységek:
|
1. |
Tematika:
Axiomatikus halmazelmélet. Forszolás, Cohen valósok. \diamondsuit, Szuszlin-fa forszolása. Lévy omlasztás, Kurepa-fák.
Tantervi egység leírás
|
Megnevezés |
Fejezetek a halmazelméletből IV (Halmazelmélet félsáv) |
|
Típus |
Tantárgy |
|
Altípus |
Alternatív |
|
Fajta |
Szakmai |
|
Felelős szervezeti egység |
Számítógéptudományi Tanszék |
|
Felelős oktató |
Komjáth Péter |
A tantervi egység elvégzéséhez szükséges
|
1. |
tanórák száma |
2 |
|
1.a. |
ebből előadás |
2 |
|
1.b. |
gyakorlat |
|
|
1.c. |
terepgyakorlat |
|
|
2. |
egyéni hallgatói munkaóra száma |
|
|
3. |
Összesen (1+2) |
A tantervi egység teljesítésének számonkérése
X kollokvium
¨ többféléves kollokvium egy másik tantervi egység elvégzésekor
¨ többféléves kollokvium ennek a tantervi egység elvégzésekor
¨ szigorlat
¨ gyakorlati jegy
¨ beszámoló
A tantervi egység felvételéhez teljesítendő tantervi egységek:
|
1. |
Halmazelmélet félsáv 3 |
A tantervi egységgel párhuzamosan (vagy korábban) teljesítendő tantervi egységek:
|
1. |
Tematika:
Iterált forszolás. Martin axióma. Prikry forszolás. Konzisztens hogy k mérhető és 2k>k+. L, tulajdonságok. L \models áKH, \diamondsuit. O^\sharp, Kunen tétele, lefedési lemma. L[U], iterált ultrahatvány, K, L[F].
Halmazelmélet félsáv elvégzésének követelményei