Számításelmélet elõadás IV. éves mat. tanároknak

Hirdetmények

A vizsga anyaga minden, ami az elõadáson elhangzik.
Az elõadás látogatása nem kötelezõ, azonban a vizsga anyaga minden, ami az elõadáson elhangzik.



 Ajánlott irodalom:




Volt:

Kommunikációs bonyolultság. A Mehlhorn-Schmidt tétel: a kommunikációs mátrix rangjának logaritmusa alsó becslés a kommunikációs bonyolultságra. Jön az E.T.: nem-determinisztikus kommunikációs bonyolultság.
 

A nem-determinisztikus kommunikációs bonyolultság jellemzése fedõ téglalapokkal. Következmény az ID problémára.

Véletlen kommunikációs protokoll az ID problémára: Rabin és Simon protokollja.
 

MAX, MIN, (MAX,MIN) megkeresése páronkénti összehasonlításokkal, ezek optimalitásának bizonyítása. 32 bites szám kitalálása barkochbával, ennek optimalitása, hazug barkochba.
 

 Középsõ elem megtalálása lineáris idõben. Vödör-rendezés O(n) lépésben. Nem ellentmondás a log n!-os alsó korláttal! Adatok tárolása: láncolt lista és tömb. Beszúrásos rendezés láncolt listán es tömbön. A kupac fogalma; DELETEMIN, MAKEHEAP. Williams és Floyd kupac-rendezése O(n log n) mûvelettel. n elem kupacba rakható O(n) összehasonlítással.

Karacuba algoritmusa két nagy szám szorzatára. Dinamikus programozás: maximális intervallum-összeg lineáris idõben, 0-1 mátrixban a legnagyobb egybefüggõ, négyzet alakú, csupa-1-es részmátrix megtalálása lineáris idõben. Mátrix-szorzás optimális zárójelezése.

A hátizsák-probléma, megoldása dinamikus programmal apró értékek esetén. Ibarra es Kim skálázási eljárása

A számítógépek egy absztrakt modellje: A Turing-gép. Példák, palindrómák.

Lesz: 

Az univerzális Turing gép. k szalagos Turing gép szimulálása 1 szalagossal.

Rekurziv és rekurzive felsorolható nyelvek. A megállási probléma.

Church tézis. Tár- és idõ-bonyolultsági osztályok. A P osztály. Nem-determinisztikus Turing-gépek. Az NP-osztály. co-NP. Példák NP-beli nyelvekre. Polinomiális redukció, NP-teljesség.
   

A SAT nyelv. Cook tétele: a SAT NP-teljes. Hipergráf-2 szinezhetõség NP-teljes.

3-szinezhetõ gráfok, a FÜGGETLEN nyelv.