Gráfok és Algoritmusok Elmélete
Előadás másodéves matematikai elemző hallgatóknak
2008 ősz
Kedd 14:15-15:45, Északi tömb, 7.14
Csak a hallgatóimnak / Only for my students
Hirdetmények
- A definíciók és tételek
1.05.
verziója.
- Az algoritmusok jegyzet
2.05 verziója.
- A vizsga beugró (írásbeli) része:
mintafeladatsor.
- Vizsgázni természetesen az előadáson és a gyakorlaton
elhangzott anyagból kell.
- A vizsgán írásbeli beugró lesz a definíciókból, tételekből és
algoritmusokból. Aki eléri az elégséges jegyet, az választhat, hogy
elfogadja, vagy pedig jön szóbelire javítani.
- 2009 tavaszán nem tudunk keresztfélévet indítani ebből a
tárgyból.
Ajánlott irodalom
- [RISz] Rónyai-Ivanyos-Szabó: Algoritmusok, Typotex, 1998
- [CLR] Cormen, Leiserson, Rivest: Algoritmusok, Mûszaki
Kiadó, 1997, illetve
- [CLRS] Cormen, Leiserson, Rivest, Stein: Új Algoritmusok, Scolar
Kiadó, 2003
- [KRS] Katona-Recski-Szabó: A számítástudomány alapjai, Typotex, 2002
- [GL] Gács-Lovász: Algoritmusok, Tankönyvkiadó, 1989
- [AHU] Aho-Hopcroft-Ullman:
Számítógépalgoritmusok tervezése és
analízise, Mûszaki
Kiadó, 1982
- [K] Knuth: A számítógépprogramozás
mûvészete,Mûszaki
Kiadó, 1987
- Adatstruktúrák
jegyzet.
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.