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