Számítástudomány előadás III. éves matematika, alkalmazott matematika BSc-seknek

  • Hely: on-line, YouTube-on
  • Idő: hétfő  14:00-15:30,
  • Előadó: Grolmusz Vince,
  • Első alkalom: 2021. február 8.

………………

A távolléti oktatás előadásai az üzenetben kapott jelszóval megtekinthetőek itt. Az előadások két hétig elérhetőek, és az előadás napján kerültek fel az oldalra.

 

Vizsga:

Reguláris vizsgaidőpontok: május 21., 28., június 4., 11., 9:30-kor, on-line (ha az ELTE másképpen nem rendelkezik), a tárgy Teams csatornáján. Az ELTE TTK on-line vizsgázásra vonatkozó szabályait követjük.

Pót- és javítóvizsga időpontok: a fentieken kívül: június 18. és 25. és július 2. 9:30; első vizsgát ekkor nem lehet tenni.

Jelentkezni a Neptunban lehet.

A vizsga anyaga minden, ami az előadáson elhangzik. Az ajánlott irodalomban minden elhangzott tétel megtalálható,
sokszor azonban más, hosszabb, bonyolultabb bizonyítással. Vizsgán természetesen akármilyen helyes bizonyítást  elfogadok.

Az ezen oldalon levő tematikából kap mindenki két tételt, távolabb levő helyekről.

A sikeres vizsga feltételei:

A két kiadott tétel alapos ismerete, különösen:

A definíciók és a tételek pontos ismerete.   A tétel bizonyításában

  • lényeges eredmény elérése a kettes,
  • a bizonyítás lényegében történő befejezése nagyobb hiánnyal  a hármas,
  • apró hiánnyal a négyes,
  • hiánytalanul az ötös szinthez.

Hiányosság a definíciókban illetve a tételek kimondásában nem megengedett (azaz rögtön elégtelen a hibás definíció illetve állítás kimondása).


Ajánlott irodalom:

Lovász László: Algoritmusok bonyolultsága, jegyzet:   (PDF),
Rónyai, Ivanyos, Szabó:  Algoritmusok
Papadimitriou: Algoritmusok bonyolultsága


Vizsgatematika:

32 bites szám kitalálása barkochbával

A számítógépek egy absztrakt modellje: A Turing-gép.  Nyelvek, abc. Példák Turing-gépekre. A palindrómák felismerése egy- és kétszalagos Turing-géppel.

Az univerzális Turing-gép definíciója és létezése.

Church tézis.

A k-szalagos Turing gép szimulálható 1 szalagossal O(N2) időben.

A RAM-gép.
 
A RAM-gép és a Turing-gép ekvivalenciája: a Turing-gép szimulálása RAM-gépen. A RAM-gép szimulálása Turing gépen.
 

Rekurzív és rekurzíve felsorolható nyelvek, ezek alapvető tulajdonságai. Majdnem minden nyelv nemrekurzív, Minden véges nyelv rekurzív.

Majdnem minden nyelv nem rekurzíve felsorolható.

A megállási probléma.

A Dominó-probléma. L_NEMRAK rekurzíve felsorolható,

Algoritmikusan eldönthetetlen, hogy egy leírásával adott Turing-gép az üres inputon leáll-e.

L_KIRAK nem rekurzíve felsorolható.

Idő-és tárkorlátos nyelvosztályok. DSPACE(f(n)), DTIME(f(n)), P, PSPACE.

Egyszerű relációk a tárigény és az időigény között.

Példák polinomiális idejű algoritmusokra: euklideszi algoritmus; a^b mod m.

Lineáris gyorsítási tétel.

Minden rekurzív f függvényhez létezik olyan rekurzív nyelv, amely nincs benne DTIME(f(n))-ben (azaz tetszőlegesen nehéz rekurzív  nyelv van).

A nem-determinisztikus Turing-gép. Nem-determinisztikus nyelvosztályok. NP,

co-NP definíciói.

Tanú fogalma. Példák polinomiális tanúra. Az NP nyelvosztály jellemzése tanúkkal.
 
Pratt tétele. Számok faktorizációja, A FACTOR nyelv.

Nyelvek polinomiális visszavezetése, tulajdonságai. NP-teljesség definíciója.

Boole függvények, Boole polinomok, CNF formulák, kielégíthetőség. A SAT nyelv.
 
Cook tétele: A SAT NP-teljes.
 
Halmazrendszer kétszínezhetősége NP-teljes.A gráfok háromszínezhetõsége NP-teljes. Minden háromnál nagyobb k-ra a gráfok k-színezhetősége NP-teljes.

Az INDEPENDENT nyelv  NP-teljessége.

Az INDEPENDENT_k nyelv P-ben van, minden k-ra.

A SAT3, a LEFOG, a LEFED NP-teljes.

A K-PART, PART NP-teljes.
 A SUBSET_SUM és a HÁTIZSÁK feladat NP-teljessége.
 
Egy algoritmus a hátizsák feladat megoldására. Az algoritmus lépésszámbecslése.

Ibarra és Kim skálázási eljárása   közelítő optimum keresésére.

Gráf kromatikus számának közelítése.

Véletlen algoritmusok, polinomazonosság ellenőrzése, Schwartz lemma.

Alkalmazás páros gráfban teljes párosítás létének eldöntésére.
 

Prímtesztelő eljárások: egy egyszerű módszer, amely nem mindig működik, és a Rabin-Miller teszt.

Kriptográfia: titkos- és nyilvános kulcs. OTP : One Time Pad.

Titkos kulcs-csere protokoll.

Az RSA titkosírás, digitális aláírás.

Titokmegosztás: egy optikai és egy algebrai megoldás.

Kommunikációs játékok. A Mehlhorn-Schmidt tétel.

A nem-determinisztikus kommunikációs komplexitás jellemzése fedő téglalapokkal.

A Simon-Rabin protokoll az ID függvény gyors, randomizált kiszámítására.

Példák nemtriviális protokollokra: részfa-metszet, teljes-üres részgráf metszet. Az Aho-Ullman-Yannakakis tétel; a P, NP, co-NP analógiái kommunikációs bonyolultságra, ezek viszonya.