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

  • Hely: északi tömb 0-79-es terem
  • Idő: hétfő  10:15-11:45,
  • Előadó: Grolmusz Vince,
  • Első alkalom: 2018. február 12.

Az előadás látogatása nem kötelező, azonban a vizsga anyaga minden, ami az előadáson elhangzik. Kötelező azonban ezt az honlapot rendszeresen figyelemmel kísérni, itt jelennek meg majd a vizsgaidőpontok, elmaradó órák, egyéb hirdetmények.


Ajánlott irodalom:

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


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.

Vizsgaidőpontok a Neptunban találhatóak. Halasztáshoz nem kell bejönni a vizsgára, elég a Neptunban törölni a jelentkezést.
Nem szükséges ünneplőbe öltözni a vizsgára, és valamilyen személyazonosító iratra is szükség van.

A kérdések kiosztása után a felkészülési idő 30 perc. A  tételek kiosztása után, a vizsga befejezéséig a vizsgahelyiséget nem lehet elhagyni; akinek ez problémát jelent, szóljon előre, és elsőnek vagy az elsők között fog vizsgázni.

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).
Minden vizsga a Déli tömb 3-614-es szoba környékén lesz,  a Neptunban olvasható a  vizsga helye. A vizsgák 9:30-kor kezdődnek.



Volt:

 

32 bites szám kitalálása barkochbával (Illusztráció: játék a géppel)

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. (Illusztráció: egy remek Java applet) .

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

Church tézis.

Lesz:

 

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.

A megállási probléma.

 Algoritmikusan eldönthetetlen, hogy egy leírásával adott Turing-gép az üres inputon leáll-e. A Dominó-probléma. L_NEMRAK rekurzive felsorolható, L_KIRAK nem rekurzíve felsorolható.

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

Példák Polinomiális idejű algoritmusokra.

Egyszerű relációk a tárigény és az időigény között.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 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, gráf háromszínezhetõsége NP-teljesek.

Az INDEPENDENT nyelv  NP-teljessége. Az INDEPENDENT_k nyelv P-ben van, minden k-ra. A SAT3, a LEFOG, a LEFED, K-PART, PART NP-teljes.

 A SUBSET SUM és a KNAPSACK 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.

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. Titkos kulcs-csere protokoll.

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

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

A BitCoin, block-chain, a működés leírása: nincs központ, tulajdonos-nyilvántartás, kétszeres elköltés kezelése

(Háttér információk (nem kell vizsgán): Egy diplomamunka a BITCOIN-ról, Satoshi Nakamoto’s original BITCOIN paper;  Satoshi Nakamoto, the creator of BITCOIN, Transactions and block chains, A BITCOIN forum).

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.