Gráfelmélet és algoritmusok

Matematika tanári mesterszak blokkóra

  • Hely:  déli tömb, 5-501-es terem
  • Idő: csütörtök 10:00-11:30, szünet nélkül
  • Előadó: Grolmusz Vince, E-mail:

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. a Neptunt.
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 magát törölni a Neptunban lehet.

A vizsgák 9:30-kor kezdődnek, ez alól kivétel a június 10-i vizsga.



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)

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 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 ⌈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 és 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.

Mélységi gráfbejárás, kétszeresen összefüggő komponensek meghatározá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.

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 webkeresők működése. A PageRang. Véletlen séták reguláris gráfokon.