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

  • Hely: déli tömb 0-805 Fejér Lipót terem
  • Idő: kedd 10:15-11:45,
  • Előadó: Grolmusz Vince
  • Első alkalom: 2024. szeptember10 .

……………………

A vizsgáról:

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

Érdeklődőknek (nem tananyag a tartalma) BitCoin: Egy jó cikk az EMS Magazinból

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. Minden véges nyelv rekurzív. Majdnem minden nyelv nemrekurzí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.

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

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

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.
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 független és a lefogó halmazok viszonya gráfban. A KLIKK nyelv NP-teljes. A G-LEFOG nyelv NP-teljes.

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. A minimális méretű csúcslefogó halmaz mérete  2-es faktoron belül közelíthető.

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.

Egy alkalmazás: A BitCoin (nem kell vizsgán)

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.

Véletlent használó protokoll az ID függvény kiszámítására.

A halmazdiszjunktsági függvény kommunikációs bonyolultsága általánosan és speciális esetekben: részfa-metszet protokoll, teljes és üres részgráf csúcsmetszete.