Kombinatorikus Algoritmusok

IV. Matematikus számítástudomány sáv

Ajánlott könyvek:

Cormen-Leiserson-Rivest: Algoritmusok.

Randomizált algoritmusok: Motwani, R. and P. Raghavan, Randomized Algorithms, Cambridge University Press (1995).
Párhuzamos algoritmusok: Leighton, F.T., Introduction to Parallel Algorithms and Architectures. Arrays, Trees, Hypercubes.
Folyamok: Ahuja-Magnanti-Orlin, Network Flows

Régi Első és második feladatsorok

Az 1997-es anyag az Algoritmusok-könyv fejezeteivel

Tematika:

Szeptember 16:

Rendezések; Oszd meg és uralkodj; Rendező hálózatok:

  • Insertion sort (beszúró rendezés)
  • Mergesort (összefésülő rendezés)
  • Batcher rendezés; a 0-1 elv
  • Leszámláló és radix rendezés

    Szeptember 23:

    Rendezések

  • Rendező algoritmusok a 2D rácson: ,,piszkos'' sorok felezése, oszd meg és uralkodj (két algoritmus)
  • Gyorsrendezés (quicksort)

    Legrövidebb utak, dinamikus programozás

  • Szélességi keresés (BFS), FIFO-k
  • Legrövidebb út 0-1 élhosszakkal, editálási távolság

    Szeptember 30:

    Legrövidebb utak

  • Dijkstra algoritmus
  • Bellman-Ford algoritmus

    Október 7:

    Minimum feszítőfa algoritmusok:

  • Prim (minimum feszítőfa); lemma: vágás legkönnyebb éle hozzáadható
  • Kruskal (az igazi mohó algoritmus)

    Boruvka Minimum feszítőfa algoritmusa

  • pointer ugrás
  • log n menet potenciálokkal.

    Október 14:

    Legrövidebb utak

  • Mátrixszorzás és Gauss-elimináció típusú algoritmusok
  • Potenciálok, átidőzítés, Johnson algoritmus

    Október 21:

    Folyamok

  • Ford-Fulkerson algoritmus (javító utak);
  • A maxfolyam-minvágás tétel

    Távolságcímkéző algoritmus.

  • Távolságcímkék definíciója; átcímkézés.
  • Mélységi keresés és módosítása.

    Október 28:

    Távolságcímkéző algoritmus vizsgálata:

  • Telítő és nem telítő pumpa; címke-tulajdonságot megőrzi (Lemma 2);
  • Egymás utáni telítő pumpa közben átcímkézés (Lemma 4); O (nm) javító út;
  • Nem pumpálható él átcímkézésig az is marad (Lemma 3); O (n^2 m) lépésszám.

    Előfolyam algoritmus.

  • Távolságcímkék < 2n;
  • Ha minden többlet nulla, nincs javító út;
  • Nem telítő pumpák számára becslés potenciálokkal.

    A FIFO Előfolyam algoritmus.

    November 4-11:

    A minimum vágás probléma. A Nagamochi-Ibaraki algoritmus.

  • A k-adik erdő definíciója;
  • Az erdő-komponensek folytatólagosak;
  • A v _ n --> v _ {n - 1} min. vágás >= d (v _ n);
  • ritka élösszefüggőségi tanuk.

    November 18:

    Minimum vágások véletlen összehúzással

  • Karger algoritmusa
  • A Karger-Stein rekurzív algoritmus
  • Becslés a konstansszor minimum vágások számára.

    November 25:

    A Chernoff korlát.
    Véletlen mintavételezés megőrzi a vágásokat.

    Közelítő algoritmusok primál-duál módszerrel:

  • Páros gráf párosítás és fedő pontrendszer;
  • Halmazfedés.

    December 3: (terv)

    Raghavan-Thompson véletlen kerekítés.

    Szemidefinit közelítés maximum vágásra.
    Erről és a Primál-duál hálózattervezési közelítésekről a Goemans-Williamson szerzőpáros cikkeit érdemes elolvasni, különösen ezt a survey-t.

    vissza a nyitólapra

    vissza a nyitólapra

    Régebben ez is volt még:

    on-line algoritmusok:

  • A FIFO és az LRU algoritmusok k-kompetitívak;
  • A randomizált FWF (MARKING) algoritmus log k-kompetitív.

    Zárt félgyűrűk: a Gauss-elimináció típusú algoritmusok algebrai struktúrája (közkívántara)

    Dinamikus programozás:

  • leghosszabb monoton részsorozat; mese: beszúrás/törlés tömbbe/listába
  • hátizsákpakolás
  • háromszögelés
  • konvex részhalmaz
  • Mátrixlánc-szorzás

    Akit érdekel, a Cormen-Leiserson-Rivestben megtalálja a Strassen mátrixszorzó algoritmusát és a gyors Fourier transzformációt (ez utóbbit is a butterfly hálózaton lehet számolni!). Ezek szerepeltek a hálózat/www specin.