A tantervi egység elvégzéséhez szükséges

A tantervi egység teljesítésének számonkérése

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.

A tantervi egység elvégzéséhez szükséges

A tantervi egység teljesítésének számonkérése

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.

A tantervi egység elvégzéséhez szükséges

A tantervi egység teljesítésének számonkérése

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, PG_n-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.

A tantervi egység elvégzéséhez szükséges

A tantervi egység teljesítésének számonkérése

Tematika:

Nevezetes NP-teljes problémák a gráfelméletben (kromatikus szám 3 vagy sem [síkbarajzolható gráfokra megszorítva is], van-e adott számú független pont, van-e egészértékű megoldás 2-termékes folyamproblémára, van-e Hamilton kör a gráfban).

Közelítő algoritmusok osztályozása, példák különböző NP-nehéz feladatok esetén (élszínezés, síkbarajzolható gráf pontszínezése, $\tau$, maximális vágás, az utazó ügynök probléma a metrikus esetben), heurisztikák az utazó ügynök problémára az euklideszi esetben.

Matroidelméleti alapfogalmak (alaphalmaz, függetlenség, bázis, kör, rang), dualitás, minorok, direkt összeg, összeg.

Matroidelméleti algoritmusok (mohó algoritmus, matroid partíciós és metszet-algoritmusok, orákulumok). Matroid párosítási probléma.

Matroidok és gráfok kapcsolata, vektorreprezentáció, geometriai reprezentáció. Tutte tételei (biz. nélkül).

A lineáris programmozás alapfeladata, dualitás, egészértékű programmozással való kapcsolat. Párosítási algoritmusok páros gráfokra (König-Hall-Frobenius a súlyozatlan esetben [csak ismétlés], Egerváry a súlyozott esetben). Kapcsolat totálisan unimoduláris mátrixokkal.

Alkalmazások a villamos hálózatok klasszikus elméletében (hálózatok egyértelmű megoldhatósága, a szabadsági fokok száma, általánosítás többpólusú lineáris alkatrészeket is tartalmazó hálózatokra, dualitás).

Alkalmazasok a távközlési hálózatok tervezésében (gráfok összefüggőségenek kiszámitása, növelése, diszjunkt fák, többszörösen összefuggő irányitások).

Alkalmazások a VLSI hálózatok huzalozásában (Gallai tétele és az egyetlen pontsor huzalozhatósága a Manhattan-modellben, csatornahuzalozás 2 és több rétegen, "switchbox"-huzalozás több rétegen, Frank A. algoritmusa az éldiszjunkt huzalozásra és ennek következményei).

Alkalmazások a rúdszerkezetek merevségének vizsgálatában (a probléma kitűzése, átfogalmazása lineáris algebrai feltétellé, a merevség definíciója, generikus merevség, Laman tétele, Lovász és Yemini tétele, a 3-dimenziós analógia nehézségei, kapcsolat a poliéderek vetületből való rekonstrukciójával, minimális számú csuklóval való rögzítés, síkbeli négyzetrácsok és térbeli kockarácsok merevítése átlós rudakkal és kötelekkel).

A tantervi egység elvégzéséhez szükséges

A tantervi egység teljesítésének számonkérése

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).

A tantervi egység elvégzéséhez szükséges

A tantervi egység teljesítésének számonkérése

Tematika:

Asszociációs szabálykeresés: Asszociációs szabály. Szintenként haladó algoritmusok: APRIORI és gyorsításai. Kétfázisú szabálykinyerés, mintavételezés: partíciós és Toivonen algoritmus. Mintanövelo algoritmusok: FP-growth. Hierarchikus és többdimenziós asszociációs szabályok. Constraint mining. Epizódkutatás: Soros epizód, szekvenciális mintakinyerés. APRIORIALL.

Korrelációkeresés: Korrelációs szabály. Khi-négyzet próbán alapuló korrálációkeresés. Hasonlóságkeresés és funkcionális függoség: lenyomat alapú hasonlóságkeresés.

Klaszterezés: A k-közép és k-medoids algoritmusok. CURE, BIRCH. Hierarchikus algoritmusok. Suruségalapú klaszterezo algoritmusok: DBSCAN, OPTICS. Link alapú klaszterezés: ROCK alapjai. Spektrál módszerek, szinguláris felbontás. Közelítés kis rangú mátrixszal.

Példák alkalmazásokra és implementációkra: Adatbányászati rendszerarchitektúrák. Adatszerkezetek. IT és biológiai alkalmazások. Szövegbányászat.

A tantervi egység elvégzéséhez szükséges

A tantervi egység teljesítésének számonkérése

Tematika:

Perfekt kódok, Hamming kódok (bináris és nem-bináris), Dekódolásuk.

Korlátok és aszimptotikus változataik (Hamming, Gilbert-Varshamov, Singleton)

Súlypolinom, a MacWilliams azonosság a duális kód súlypolinomjára.

A Golay-kódok egyértelműsége, előállításai.

Ciklikus kódok, BCH kódok, BCH korlát, BCH kódok dekódolása (euklideszi algoritmussal). A Hamming-kódok előállítása BCH-kódként.

Reed-Muller kódok, MDS kodok, Reed-Solomon kódok, RS kódok dekodolasa. Goppa kódok, Justesen kódok.

Kódok gyakorlati alkalmazásai: számítógép-memóriák, hálózatok.

Kódolás a CD-n: A CIRC kódok, konkatenált kódok.

Távközlési alkalmazások: Mariner, Voyager által használt kódok, dekódolásuk. A Golay-kódok alkalmazásai.

A tantervi egység elvégzéséhez szükséges

A tantervi egység teljesítésének számonkérése

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.

A tantervi egység elvégzéséhez szükséges

A tantervi egység teljesítésének számonkérése

Tematika:

A tantervi egység elvégzéséhez szükséges

A tantervi egység teljesítésének számonkérése

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.

Alkalmazott diszkrét matematika sáv elvégzésének követelményei:

A sáv elvégzéséhez 8 tanegységből kell jegyet szerezni.

A tantervi egység elvégzéséhez szükséges

A tantervi egység teljesítésének számonkérése

Tematika:

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.

A tantervi egység elvégzéséhez szükséges

A tantervi egység teljesítésének számonkérése

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.

A tantervi egység elvégzéséhez szükséges

A tantervi egység teljesítésének számonkérése

Tematika:

Folyamok és áramok: Hoffman tétel, Ford és Fulkerson tétele és algoritmusa, folyamok - áramok: mindkét irányú visszavezetés, Edmonds és Karp algoritmusa, előfolyam algoritmus, skálázás, minimális költségű folyam , minimális költségű áram.

Párosítások: Kőnig tétele, Hall tétele, Egerváry tétele, magyar módszer , algoritmus maximális súlyú teljes párosításra páros gráfban, Kőnig élszínezési tétele, Tutte tétele, telített nem-párosítható gráfok, Berge-Tutte formula, Edmonds algoritmusa maximális méretű párosításra, Petersen tétele, Birkhoff és Neumann tétele, De Werra tétele, diszjunkt élfedések, Edmonds algoritmusa minimális költségű teljes párosításra, Gallai-Edmonds struktúratétel, faktor-kritikus gráfok, Gallai lemma, legrövidebb utak irányítatlan gráfban, Tutte mátrix.

A tantervi egység elvégzéséhez szükséges

A tantervi egység teljesítésének számonkérése

Tematika:

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.

A tantervi egység elvégzéséhez szükséges

A tantervi egység teljesítésének számonkérése

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.

A tantervi egység elvégzéséhez szükséges

A tantervi egység teljesítésének számonkérése

Tematika:

Markov láncok és bolyongás gráfokon.

A Page Rank és két alkalmazása: Jeh--Widom Scaling Personalized Web Search, és SimRank: A Measure of Structural-Context Similarity.

A Kleinberg és a HITS algoritmus.

A szinguláris felbontás, gráfklaszterezés és a Kleinberg algoritmus.

Gráfmodellek: Erdős-Rényi, preferált illesztés (Albert-Barabási) és másolásos (Kumar és társai).

Preferált illesztés modellben a fokszámeloszlás bizonyítása, Bollobás és társai.

Kis Világ modellek: Kleinberg: The Small World phenomenon: an algorithmic perspective.

Ad hoc mobil hálózatok: Karger és társai: A scalable location service for geographic Ad Hoc routing.

A WWW oldalainak cache-elése. Az adatbázis frissítés.

A tantervi egység elvégzéséhez szükséges

A tantervi egység teljesítésének számonkérése

Tematika:

A tantervi egység elvégzéséhez szükséges

A tantervi egység teljesítésének számonkérése

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.

A tantervi egység elvégzéséhez szükséges

A tantervi egység teljesítésének számonkérése

Tematika:

Megosztott algoritmusok

Rácsalgoritmusok

Transzparens bizonyítások és approximálhatatlanság

Kvantum-számítógépek

Számítástudomány sáv elvégzésének követelményei

A sáv elvégzéséhez 8 tanegységből kell jegyet szerezni, de Bonyolultságelmélet előadásból és gyakorlatból mindenképpen jegy kell.