2012/13 ősz

Diszkrét matematika 3. - ELTE Matematika tanár, péntek, 10:00-11:30, Déli tömb 0-409

A bonyolultságelméleti részben (első hét előadás) a fejezetek, feladatok a Lovász-jegyzetre utalnak
Az extremális kombinatorikai témakörhöz jegyzet

Az első előadás anyaga: 8. oldal jelolesrol, nagysagrendrol, veges automatak: a teljes 1.1 fejezet
A második előadás anyaga: Turing-gép definíciója, pédák (1.2.1 feladat a,b,c, 1.2.2 feladat), univerzális T-gép (1.2.1 tétel, bizonyítás csak ötletszinten)
A harmadik előadás anyaga: 1.2.2 tétel (biz nélkül), 1.2.3 tétel, algoritmikus eldönthetőség, rekurzív és rek. felsorolható nyelvek definíciója, rek fels. nyelv ekvivalens def (2.1.1 lemma), rekurzív nyelv rek felsorolható (2.1.2 lemma), nyelv rekurzivitására szüks és elégs. feltétel (2.1.3 tétel), univ T-gép által felismert nyelv rek. fels, de nem rek. (2.1.4 tétel)
A negyedik előadás anyaga: 2.1.5 tétel, 2.1.6 és 2.1.7 következmények, a KIRAK és a NEMRAK nyelvek, 2.2.1 és 2.2.2 tétel
Az otodik eloadas anyaga: tar es ido, 3.1 fejezetbol a), b) reszek es c)-nel a determinans meretere vonatkozo becsles. Nemdeterminisztikus Turing-gepek definicioja. Nemdet. ido es tar. 4.1.1 tetel. 4.2.1 tetel (biz nelkul) es 4.2.2 kovetkezmeny. Peldak NP-beli nyelvekre.
A hatodik előadás anyaga: P és NP, coNP lehetséges viszonyai. polinomiális visszavezetés (Karp-redukció), NP-teljesség definíciója. lemmák a redukció tranzitivitásáról, illetve P-beli nyelvre való visszavezethetőségről. SAT, k-SAT, SAT-k nyelvek: Cook tétele (SAT NP-teljes, 4.4.4 tétel, bizonyítás nélkül). 3-SAT NP-teljes (4.4.5), 2-SAT P-beli (biz nélkül)
A hetedik előadás anyaga: NP-teljességi bizonyítások: SAT-3, LEFEDÉS, LEFOGÁS, PARTÍCIÓ, k-PARTÍCIÓ, DIOFANTOSZ (biz nélk.), 3-SZÍN (biz. nélk), FÜGGETLEN (biz nélk), RÉSZLETÖSSZEG (biz. nélk.), LÁDAPAKOLÁS (biz. nélk)
A nyolcadik előadás anyaga: Chvatal és Ore tétele, ex(n,F) definíciója, Turán tétele, Erdős-Stone tétel (csak kimondani), Erdős-Stone-Simonovits
A kilencedik előadás anyaga: Kővári - T. Sós - Turán, Erdős-Gallai (csak kimondva), Bondy-Simonovits (csak kimondva), Katona-Nemetz-Simonovits. epsilon-reguláris par fogalma, és következményei (túl kis, illetve túl nagy fokú pontok száma, háromszögek száma)
A tizedik előadás anyaga: epsilon-reguláris partíció fogalma, Szemerédi regularitási lemma (csak kimondani), G(n,p) és G(n,m,p) definíciója, élszámuk, fokszámsorozataik, G(n,n,p) majdnem mindig reguláris pár, G(n,p) fix k-pariticora majdnem mindig epsilon-reguláris tetszőleges epsilon esetén
A tizenegyedik előadás anyaga: lánc, maximális lánc, Sperner rendszer, k-Sperner rendszer definíciója. Sperner illetve Erdős tétele maximális Sperner / k-Sperner rendszer méretéről. lemma bireguláris páros gráfokról. LYM-egyenlőtlenség.
A tizenkettedik előadás anyaga: metsző halmazrendszer definíciója, lemma nem-uniform metsző rendszerekről. Erdős-Ko-Rado tétel. ciklikus permutációk, intevallumok, Katona-féle bizonyítás. Balratömörítés, tulajdonságai. Másik bizonyítás EKR-tételre.
A tizenharmadik eloadas anyaga: halmaz, halmazrendszer nyomanak fogalma, tr(F) definicioja. A Sauer-lemma indukcios illetve lefele tomoriteses bizonyitasa.