Kombinatorikus Optimalizálás

IV. Prog Mat diszkrét és opkut sávok

Vizsgatematika

Előadás: Csutörtök 9:30 - 10:00, 2-712
Gyakorlat: első feladatsor - második feladatsor - harmadik feladatsor

A félév legnagyobb részében használható könyv:

Cormen-Leiserson-Rivest-Stein: Algoritmusok.

Vizsgaidőpontok

  • Junius 3, pentek
  • Junius 10, pentek
  • Junius 24, pentek
  • Julius 8, pentek Kezdés 10:00-kor, déli tömb 3-607.

    Tematika *: nincs a Cormen-Leiserson-Rivestben

    Február 16.

    Legrövidebb utak
  • Szélességi keresés, FIFO
  • 0-1 élhosszak, módosított FIFO-LIFO
  • Editálási távolság, diff *

    Február 23.

  • Dijkstra, helyesség bizonyítással
  • Bellman-Ford, helyesség bizonyítással

    Március 2.

    Legrövidebb utak

  • Mátrixszorzás-típusú algoritmus
  • Floyd-Warshall legrövidebb út algoritmus

    Dinamikus programozás

  • Mátrixlánc szorzás
  • Konvex sokszög háromszögelése
  • Maximális konvex rész

    Március 16.

    Minimum feszítőfák
  • Prim algoritmus, kék szabály, Dijkstrával hasonlóság
  • Kruskal algoritmus

    Március 23.

    Matroidok:
  • a mohó algoritmus helyessége és a matroid-tulajdonságok ekvivalensek.
  • Bázis, független, kör, vágás, rang. *
  • Síkgráf duálisa. *
  • Matroid dualitás és az óvatos algoritmus. *
    A piros szabály

    Március 30.

    Johnson legrövidebb ut algoritmusa, átidőzítés.

    Bináris számláló növelése, potenciálfüggvények.

    Páros gráf párosítása, Konig és Hall tételek

    Április 6.

    A Ford-Fulkerson folyamalgoritmus és a max folyam - min vágás tétel
    Páros gráf párosítása mint a folyam speciális esete

    Április 20.

    A távolságcímkéző folyamalgoritmus, pszeudokód és mélységi keresés*
    Távolságcímkéző folyamalgoritmus *
  • távolságcímke tulajdonság megőrződik *
  • éllistát átcímkézésenként elég egyszer végignézni *
  • két átcímkézésenként max egy telítés *

    Április 27.

    Az előfolyam algoritmus.
  • Pozitív többletből vezet s-be r > 0 él
  • d (v) < 2n
  • Ha nincs többlet, nincs javító út
    Az előfolyam algoritmus analízise: potenciál a nem telítő pumpák számának becslésére

    Május 4.

    Közelítő algoritmusok
  • Mohó közelítés az éllefogás (= csúcsfedés = vertex cover) problémára. 35.1. fejezet
  • A párosítás/éllefogás (vertex cover) IP megfogalmazása, relaxált, duális
  • Közelítő éllefogás LP kerekítéssel. 35.4. fejezet

    Május 11.

    Közelítő algoritmusok és lineáris programozás II.
    A mohó algoritmus vizsgálata primál/duál módszerrel* A halmazfedés (set cover) probléma (35.3. fejezet) a könyvhöz képest kicsit módosított, LP dualitásos bizonyítása:
  • bevezethetünk w_S költséget a halmazokon, ez kerül c_x definíciójában a számlálóba
  • a (35.9) egyenlőtlenség valójában egyenlőség
  • a (35.10) egyenlőtlenség kicsit egyszerűbben bizonyítható, ha az S pontjait rendezzük fedésük sorrendjében és az i-edik x pontra bizonyítjuk, hogy c_x <= w_S / (|S| - i - 1)

    Páros gráf párosítás LP mindig van egész optimum megoldása (totális unimodularitás)

    Vissza a nyitólapra