Tematika (címszavakban)

2024 tavasz

Jelmagyarázat
CLRS -- Cormen, Leiserson, Rivest, Stein: Új algortimusok (eredeti: Introduction to Algorithms), A fejezet- és oldalszámok a 4. kiadásra vonatkoznak. Itt egy link a magyar változatra.
  1. febr.13.
    -- legnagyobb elem keresés, optimalitás
    -- legkiseb és legnagyobb elem keresés, optimalitás
    -- legkisebb és 2. legkisebb elem keresése
    .. k. elem keresés ötlet
    (Irodalom: CLRS 9.1, 9.2 )
    febr. 15.
    -- k. elem keresés randomizált és determinisztikus lineáris időben
    -- bináris keresőfában k rangú elem keresése
    -- bináris keresőfában elem rangja
    (Irodalom: CLRS 9.2, 9.3, 14.1 )
  2. febr.20.
    -- fában legkisebb közös ős lineáris előkészítés után konstans időben
    -- résztömb legkisebb eleme O(n log n)-es előkészítés után konstans időben
    -- résztömb legkisebb eleme O(n-es előkészítés után konstans időben ha a tömb mindig csak 1-gyel változik
    (Irodalom: Király Z.: Adatstruktúrák   9. fejezet (LCA és RMQ) )
  3. febr.27.
    -- összefoglaló a múltkoriakról
    -- kupac-tulajdonság
    -- a kEpac (treap) adatszerkezet egyszerű tulajdonságai: létezik és egyértelmű, KERES, BESZÚR (TÖRÖL) műveletek
    -- az általános résztömbök minimuma feladat visszavezetése legkisebb közös ősre
    -- az itt előforduló speciális kepac felépítése lineáris időben
    -- Síkgeometriai algoritmusok: keresztszorzat és merre fordul a vektor
    (Irodalom: kepac. ld wikipedia "treap"; résztömbök minimuma a Király-féle jegyeztben; Geometria: CLRS 33.1-ben )

    OLVASNI a következő órára: konvex burok keresés: CLRS 33.3.

    febr. 29.
    -- 1. kis zh !!
    -- síkban legközelebbi pontpár keresése O(n log n) időben
    -- szakaszok metszésének eldöntése osztás nélkül
    (Irodalom: CLRS 33.2, 33.4 )
  4. márc. 5.
    -- vödrös hash átlagos és legrosszabb eset
    -- univerzális hash-függvény család (fogalom, példák, várható lépésszám)
    -- növelhető hash
    (Irodalom: CLRS 11.2, 11.3.3, növelhető_hash.pdf )
  5. márc. 12.
    -- Mintaillesztés - naív algoritmus és gyorskeresés
    -- Mintaillesztés véges automatával
    -- Lineáris idejű algoritmus (Knuth-Morris-Pratt)
    (Irodalom: Naív és gyorskeresés , CLRS 32.3, Rónyai, Ivanyos, Szabó: Algoritmusok 9.5.3 vagy CLRS 32.4 )

    márc.14.
    -- Dinamikus programozás: max összegű résztömb, növő részsorozat
    -- Floyd-algoritmus legrövidebb utakra
    -- (Globális) Illesztés
    (Irodalom: Algel előadás anyag , Rónyai, Ivanyos, Szabó: Algoritmusok 6.3.1, illesztés )
  6. márc. 19.
    -- szemi-globális és lokális illesztés
    -- DP feladatmegoldás
    (Irodalom: 1. , 2. , 3. ), feladatsor
  7. márc. 26.
    -- DP feladatmegbeszélés
    -- Amortizációs elemzés bevezető: összesítéses és könyveléses módszer a bináris számláló elemzésén bemutatva
    (Irodalom: CLRS 17.1, 17.2)
  8. ápr. 9.
    -- amortizációs elemzés: potenciál módszer
    -- Pl.: bináris számláló
    -- dinamikus tábla (még csak a beszúrásos változat elemzése)
    (Irodalom: CLRS 17.3, 17.4.1)

  9. OLVASNI: a könyvbeli vermes példa amortizációs elemzése a 3 módszerrel: CLRS 17.1-3

    ápr. 16.
    -- dinamikus tábla befejezés
    -- Move-to-front heurisztika elemzése poetnciálfüggvénnyel
    (Irodalom: CLRS 17.4.2, move-to-front)
    ápr. 18.
    -- 2. kis zh !! (anyaga: mitaillesztés és variánsai, dinamikus programozás, amortizációs elemzés)
    -- hálózati folyam ismétlés
    -- Ford-Fulkerson-algoritmus lehet lassú
    -- egész kapacitások esetén megáll
    -- irracionális kapacitásos példa, amikor nem áll meg (és nem is a max. folyamhoz konvergál)
    -- Mohó javítás: amikor mindig a legtöbbet javító utat választjuk (Edmonds-Karp)
    (Irodalom: CLRS 26.1, 26.2. eleje, példa, mohó)
  10. ápr.23.
    -- A mohó elemzésének vége
    -- Edmonds-Karp-algoritmus, amikor a legrövidebb úttal javítunk
    (Irodalom: CLRS 26.2. vége)
  11. ápr.30.
    -- Edmonds-Karp elemzése
    -- Az előfolyam módszer
    (Irodalom: CLRS 26.2. vége, 26.4. eleje)
    május 2.
    -- Előfolyam módszer: helyesség, lépésszám
    -- Előreemelő algoritmus (vázlatosan)
    (Irodalom: CLRS 26.4., 26.5.)
  12. máj.7.
    -- Minimális feszítőfa keresés
    -- a piros-kék algoritmus
    -- alkalmazásai: Prim, Boruvka, Kruskal
    -- Prim lépésszáma
    -- UNIÓ-HOLVAN adatszerkezet definiciója
    (Irodalom: Rónyai, Ivanyos, Szabó: Algoritmusok 6.6, 6.6.1 - ebből a kupacos-éllistás és Johnson nem volt az órán, 6.6.2 )
  13. máj.13.
    -- UNIÓ-HOLVAN adatszerkezet megvalósítása tömbbel, lépésszámok
    -- UNIÓ-HOLVAN adatszerkezet megvalósítása fákkal, rang szerinti UNIÓval, lépésszámok
    -- útösszenyomással, amortizált O(m log*n)-os elemzés
    (Irodalom: Rónyai, Ivanyos, Szabó: Algoritmusok 6.6.3 és Király Z.: Adatstruktúrák   4.1, 4.2 )
  14. máj. 15.
    -- 3. kis zh !! (anyaga: folyamok, minimális feszítőfák, UNIÓ-HOLVAN tömbbel)
    -- további javítási lehetőségek, az Ackermann-függvény (bizonyítás nélkül)
    -- Strassen-féle gyors mátrixszorzás
    (Irodalom: CLRS 21.4 eleje, Lovász L. : Algoritmusok bonyolultsága   9.2.2 )
  15. máj. 22.
    -- nagy számok szorzása: Karacuba módszere
    (Irodalom: Lovász L. : Algoritmusok bonyolultsága   9.2.1 )

Következő alkalommal várható: