Gráfelmélet és algoritmusok

Matematika tanári mesterszak blokkóra

Hely:  déli tömb, 0-412-es terem 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
  • 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)



  • Volt:

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

    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. 

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

    Lesz:




    Mélységi gráfbejárás, kétszeresen összefüggő komponensek meghatározása.


    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.  

    Folyamok, vágások. Vágások kapacitása és értéke. A MAX-FLOW-MIN-CUT tétel. Egész értékű folyamok tétele. A Menger tétel.


    A webkeresők működése. A PageRang. Véletlen séták reguláris gráfokon.