Számításelmélet előadás

Az előadás látogatása nem kötelező, de ennek a lapnak a rendszeres figyelése az. Az esetlegesen elmaradó előadásokról, időpontváltozásokról is itt kaphatnak tájékoztatást, emellett megjelenik itt az elhangzott előadások tematikája is.



A vizsgáról

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

Vizsgaidőpontok: Ld. az ETR-t.
 Minden vizsga a Déli tömb 3-614-es szoba környékén lesz, a szoba ajtaja melletti táblára lesz kirakva a vizsga reggelén a vizsga
helye. A vizsgára jelentkezni illetve törölni magad az ETR oldalakon lehet.
A vizsgák 9:30-kor kezdõdnek.




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.


Ajánlott irodalom:

A fő forrás:

  Cormen, Leiserson, Rivest: Algoritmusok, vagy az Új Algoritmusok c. könyve

  • Más kitünő művek magyarul:
  • Gács-Lovász: Algoritmusok
  • Katona-Recski-Szabó: A Számítástudomány alapjai
  • Lovász László: Bonyolultságelmélet, jegyzet (az 1992, vagy az utáni kiadások) - vagy ugyanez angolul, átdolgozva, ez a legfrissebb: gzipped postscript
  • Aho-Hopcroft-Ullman: Számítógépalgoritmusok tervezése és analízise
  • Knuth: A számítógépprogramozás művészete
  • Lawler: Kombinatorikus Optimalizálás: Hálózatok és matroidok
  • Rónyai, Ivanyos, Szabó: Algoritmusok jegyzet (BME jegyzete)


  • Vizsgatematika:

    32 bites szám kitalálása barkochbával, ennek optimalitása. n bites szám kitalálása barkochbával, ennek optimalitása.(Illusztráció: játék a géppel, Alexander Bogomolny). Hazug barkochba. MAX, MIN, (MAX,MIN) megkeresése páronkénti összehasonlításokkal. A legjobb és a legrosszabb játékos kitalálásának optimalitása: a kavizsos konstruklció.

    A legjobb és a második legjobb teniszjátékos kiválasztása.

    Rendezés kitalálása barkochbával.


    Ordó-jelölések.  Rendezéshez legrosszabb esetben log n! összehasonlítás kell. log n! becslései . Beszúrás, egy elem beszúrásához n elemű listába felsőegészrész(log (n+1)) összehasonlítás kell, ennyi azonban elég is.

    Rendezés beszúrásokkal O(n log n) összehasonlítással. Összefésüléses rendezés. Két n hosszú sorozat 2n-1 összehasonlítással összefésülhető, es ez optimális is. Rendezés összefésüléssel. (Illusztráció: applet a beszúrásos és az összefésüléses rendezésre; (Netscape-pel nem megy, IE ajánlott), illetve sok más rendezés applet)

    Középső elem megtalálása, a Floyd-Rivest algoritmus

    .Karacuba-Ofman algoritmus két nagy szám szorzatára. Strassen mátrix-szorzása. (illusztráció: Kirk Pruhs appletje a Karacuba-Ofman polinomszorzásra)

    Dinamikus programozás: maximális intervallum-összeg lineáris időben. Egy 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 naiv algoritmus és a dinamikus programmal elérhető lépésszám összehasonlítása.

    A hátizsák-probléma, megoldása dinamikus programmal. Apró értékek esetén az algoritmus polinomiális. Ibarra és Kim skalázási eljárása.

    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; DELETE_MIN, INSERT.

    Williams és Floyd kupac-rendezése O(n log n) mûvelettel. Gráfok ábrázolása. Gráfalgoritmusok: Szélességi gráf-bejárás, ezzel komponensek meghatározása, összefüggõség-vizsgálat, feszítö-erdö megadása.   

    Egy gráfnak exponenciálisan sok feszítöfája is lehet.  Minimális költségü feszítöfa keresése, Prim algoritmusa, kupac-implementáció.
    Dijkstra algoritmusa szemléletesen: golyók és fonalak. Dijkstra algoritmusa egy pontból kiinduló minimális költségü utak kiszámítására, kupac implementáció. 

    Páros gráfok. Egy gráf párosságának eldöntése. Párosításkeresés páros gráfban: alternáló utak. Lépésszám-becslés. Maximális méretû párosítás, teljes párosítás.

    Stabil házasságok problémája, ennek megoldása lineáris idõben.

    Maximális méretû független csúcsrendszer keresése gráfban. Kis javítás az exponenciális algoritmusban.

    Speciális eset intervallum-gráfokra: az intervallumpakolás. MIN-MAX-tétel, gyors algoritmus, lépésszámbecslés.  

    Véletlent használó algoritmusok. Polinomazonosság-ellenörzés, a Schwartz-lemma. Számelméleti algoritmusok: az euklideszi algoritmus, lépésszámbecsléssel. a mod m kiszámítása polinomiális idõben. Primtesztek: egy, amely pszeudoprímekre nem mûködik; egy másik, (Rabin-Miller) amely mindig mûködik.

    Kriptográfia: titkos kulcsú titkosírások, a one-time pad. Titkos kulcs-csere protokoll (Diffie & Hellman).  Nyilvános kulcsú titkosírások. A Rivest-Shamir-Adleman titkosírás. Digitális aláírás. Titokmegosztási eljárások: Shamir módszere és egy optiikai megoldás.

    Kommunikációs játékok. Protokoll x+y paritásának kiszámítására. Protokoll gráfban egy független halmazt és egy klikket feszítő csúcshalmaz diszjunktságának eldöntésére. Kommunikációs mátrix, kommunikációs bonyolultság. A Mehlhorn-Schmidt tétel. Alkalmazása az ID és a DISJ függvényekre. Rabin-Simon protokoll az ID függvény kiszámítására: amikor a véletlen bizonyítottan erősebb.