Gráfok és Algoritmusok Elmélete

Előadás másodéves matematikai elemző hallgatóknak

2008 ősz

Előadó: Király Zoltán

Kedd 14:15-15:45, Északi tömb, 7.14


Csak a hallgatóimnak / Only for my students


Hirdetmények

A beadandó programozási feladat, értékelése és új feladatok.


Ajánlott irodalom


1. előadás (IX. 9.)

Algoritmus és lépésszám intuitív fogalma, nagy ordó jelölés. Szám kitalálása barkochbával, alsó becslés, barkochba előre leírt kérdésekkel. A szótár feladat, felező keresés rendezett vektorban. Legnagyobb elem, illetve egyszerre legnagyobb és legkisebb elem megkeresése. Alsó becslések, ellenség stratégia. A rendezési feladat.

2. előadás (IX. 16.)

ELMARADT.

3. előadás (IX. 23.)

Beszúró rendezés. (Gyakorlaton). Rendezéshez összehasonlításokkal kell n.log(n) lépés.
Kupac definíciója, tárolása. Beszúrás megvalósítása (felbillegtetés), jósága. MINTÖRLÉS megvalósítása (lebillegtetés), jósága.
Kupacépítés, kupacos rendezés.
Középső elem keresése. Gyorsrendezés vázlata.

4. előadás (IX. 30.)

Gyorsrendezés. Leszámláló rendezés. Számjegyes rendezés.
Számolás nagy számokkal, mod m számítások, Euklideszi alg., hatványozás.

5. előadás (X. 7.)

Algoritmusok sebessége II, P osztály.
Dinamikus programozás: Fibonacci számok. Legkisebb intervallum-összeg kiszámítása -- gyakorlaton.
Hátizsák feladat, megoldása ha a hátizsák teherbírása kicsi.
Mátrix-szorzás zárójelezése dinamikus programozással.
Láncolt listák.

6. előadás (X. 14.)

Különböző gráfok tárolási módjai.
Bináris keresőfák. Törlés bináris keresőfában, AVL fák.
Sor és verem megvalósítása.

7. előadás (X. 21.)

Szélességi keresés: összefüggőségi teszt, komponensek meghatározása. Szélességi keresés lépésszáma, alkalmazása különböző feladatok megoldására, jósága. Öf eldöntéséhez kell is kb. annyi lépés, mint szélességivel.
Szélességi irányított gráfokon, gyenge és erős öf, eldöntésük.
Min költségű feszítőfa feladat, Prim algoritmus vázlata.

8. előadás (XI. 4.)

Prim algoritmusa, jóság, lépésszám. Prim megvalósítás kupaccal. KULCS-CSÖK kupacban. d-edfokú kupac. Legrövidebb utak keresése, Dijkstra algoritmusa. Futási idő. Dijkstra jósága.

9. előadás (XI. 11.)

Dijkstra alkalmazások: legbiztonságosabb út, legszélesebb út.
A házépítési feladat, PERT módszer, leghosszabb út aciklikus gráfban, tartalék-idők.
Bellmann-Ford módszer 1. változat legrövidebb utak keresésére, jóság, futási idő.

10. előadás (XI. 18.)

Bellmann-Ford módszer 2. változat, negatív körök detektálása.
A hasítás alapjai.
Stabil házasítás.
Párosítás páros gráfokban, javító út, az algoritmus vázlata. Részletes algoritmus megbeszélése I.

11. előadás (XI. 25.)

Részletes alg. közepe, lépésszáma. Jóság, bizonyíték. Froebenius, Hall, Ore és Kőnig tételei.
Mese párosításról nem páros gráfban. Tutte tétele.
Hálózat, folyam, vágás, vágás kapacitása és folyamértéke. Maradék hálózat (segédgráf) készítése egy folyamhoz. Folyam-algoritmus (Ford-Fulkerson). Javítás a folyamon a megtalált javító-út segítségével. Minimális vágás megtalálása.

12. előadás (XII. 2.)

Ford-Fulkerson tétel. Edmonds-Karp tétel (biz. nélkül), algoritmusok futási ideje.
Folyam irányítatlan gráfokon, csúcskapacitások kezelése, több termelő/fogyasztó esete. Redukált folyam, felbontása utakra.
Menger tételei, gráfok többszörös összefüggősége.
Mélységi keresés, mélységi és befejezési számozás. Gráf erősen összefüggővé irányítása, elvágó csúcsok keresése (vázlatosan).


13. előadás (XII. 9.)

Abc, szó, nyelv. Huffman-kód. Lempel-Ziv-Welch tömörítési eljárása.
Turing-gépek, eldönthetőség, DTIME osztályok, P, NP és NP-teljesség. Néhány nevezetes NP-teljes feladat.