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

További értesítésig az előadások elmaradnak, az óra olvasókurzus lett.

Évközi konzultácíókat tartunk az alábbi időpontokban:

November 12, csütörtök, 10:00 óra,  D 3-614-es szoba;

November 26, csütörtök,10:00 óra,  D 3-614-es szoba;


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.


 Az ajánlott irodalomban minden elhangzott tétel megtalálható, sokszor azonban más, hosszabb, bonyolultabb bizonyítással, mint ahogyan azt az előadäson elmondtuk. Vizsgán természetesen akármilyen helyes bizonyítást elfogadunk.

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ó: Algoritmusok bonyolultsága, jegyzet: angolul: gzipped postscript , vagy PDF. Magyarul: PDF, illetve PS.
  • 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 kavicsos 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.  (Netscape-pel nem megy, IE ajánlott))

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