Bonyolultságelmélet elõadás II.


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 kisérni, itt jelennek meg majd a vizsgaidõpontok, elmaradó órák, egyéb hirdetmények.

A matematikusoknak javasolt a Varga Dániel által vezetett gyakorlatot idén elvégezni (bár ez mint V. éves sáv-óra van kiirva).

Az ambiciózus diákoknak javasolt a Bonyolultságelméleti szeminárium látogatása, minden második héten 10:15-tõl a 3-614-es teremben. Ehhez praktikus felvetetni magad a bonyszem levelezési listára, amelyet egy Király Zoltánnak írt (kiraly@cs.elte.hu) levélben kérhetsz. 



A legfontosabb két könyv:

    Lovász László: Algoritmusok bonyolultsága, jegyzet (az 1992, vagy az utáni kiadások).
        Vagy ugyanez angolul, átdolgozva, ez  a legfrissebb: gzipped postscript .

Papadimitriou: Algoritmusok bonyolultsága, (egyetemi tankönyv)  Novadat, 1999.

Egyéb ajánlott könyvek:

    Gács-Lovász: Algoritmusok
    Knuth: A számítógépprogramozás mûvészete
     Rónyai, Ivanyos, Szabó:  Algoritmusok
 


Need some cash? Try this!



A vizsgáról
 



Vizsgatematika

 1. elõadás: Véletlen algoritmus teljes párosítás létezésének eldöntésére páros gráfban. Prímtesztek: gyenge próbálkozások, Fermat-teszt,  Miller-Rabin - teszt.

2. elõadás: Az Agrawal-Kayal-Saxena teszt:   a prímek P-ben vannak (csak mese). Titkosírások: titkos kulcsú tikosírások, kulcs-csere (Diffie, Hellman, Merkle); nyilvános kulcsú titkosírások: a legismertebb példa: az RSA (Rivest, Shamir, Adleman) titkosírás. Titokmegosztás (itt már vannak bizonyítások): egy optikai (Naor-Shamir, egy példa) és egy algebrai módszer polinom-interpolációval (Shamir).
 

3. elõadás: Véletlen komplexitásosztályok,