Tematika (címszavakban)

2025 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.10.
    -- 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 véletlent használva

    febr. 13.
    -- középső elemmel k. elem
    -- közel középső elemmel k. elem
    -- k. elem keresés determinisztikus lineáris időben
    -- bináris keresőfában k. elem elem keresése
    (Irodalom: CLRS 9.2, 9.3, 14.1)

  2. febr.17.
    -- bináris keresőfában elem rangja
    -- fában legkisebb közös ős és átfogalmazása résztömbök minimumaira
    -- résztömb legkisebb eleme O(n log n)-es előkészítés után konstans időben
    -- javítás: algoritmus csoportokra bontással
    (Irodalom: Király Z.: Adatstruktúrák   9. fejezet (LCA és RMQ) )

  3. febr.24.
    -- 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
    -- fában legkisebb közös ős lineáris előkészítés után konstans időben
    -- a kEpac (treap) adatszerkezet
    -- 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: legközelebbi pontpár. Kvadratikus algoritmus és az O(n log n)-es algoritmus ötlete
    (Irodalom: Király Z.: Adatstruktúrák   9. fejezet (LCA és RMQ)
    kepac. ld wikipedia "treap")


    febr. 27.
    -- legközelebbi pontpár keresése
    -- konvex burokra Graham algoritmusa
    -- Graham optimalitása
    -- Jarvis algoritmusa
    -- vázlat (mese) Chan algoritmusáról
    (Irodalom: CLRS 33.3, 33.4 )

    OLVASNI a következő órára: -- szakaszok metszése, szög merre fordul - osztás nélkül. Metsző szakaszpár
    : CLRS 33.2.

  4. márc. 3.
    -- 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)
    (Irodalom: CLRS 11.2, 11.3.3)

  5. márc. 10.
    -- 1. kis zh !!
    -- növelhető hash
    -- Bloom-filter
    (Irodalom: , növelhető_hash.pdf , Bloom-filter )
    márc.13.
    -- Mintaillesztés - naív algoritmus és gyorskeresés
    -- Mintaillesztés véges automatával
    (Irodalom: Naív és gyorskeresés , CLRS 32.3 )

  6. márc. 17.
    -- Lineáris idejű algoritmus (Knuth-Morris-Pratt)
    -- Dinamikus programozás: max összegű résztömb, növő részszó és részsorozat
    (Irodalom: Rónyai, Ivanyos, Szabó: Algoritmusok 9.5.3 vagy CLRS 32.4, Algel előadás anyag

  7. márc. 24.
    -- Floyd-algoritmus legrövidebb utakra
    -- Szerkesztési távolság (globális illesztés)
    -- Közelítő mintaillesztés ( szemi-globális illesztés)
    -- Lokális illesztés
    (Irodalom: illesztés 1. , 2. , 3. )

    márc.27
    -- Lokális illesztés
    -- Példa az illesztésekhez
    -- Amortizációs elemzés 3 módszere
    -- Szemléltetés a bináris számlálóval
    (Irodalom: CLRS 17.1-3)

  8. márc. 31.
    -- Dinamikus tábla amortizált elemzése
    -- Move-to-front heurisztika és a potenciál függvénye
    (Irodalom: CLRS 17.4)

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

  9. ápr. 7.
    -- Move-to-Front heurisztika elemzése poetnciálfüggvénnyel
    -- Hálózati folyamok ismétlés, jelőlések
    -- Egész kapacitásoknál elég max folyamnyi javítás.
    (Irodalom: move-to-front)

    ápr.10.
    -- lépésszámbecslés egész és racionális kapacitásokra
    -- példa, amikor végtelen hosszú javítólépés-sorozat is van
    -- Mohó Edmonds-Karp: amikor mindig a legtöbbet javító utat választjuk (Edmonds-Karp)
    (Irodalom: CLRS 26.1, 26.2. eleje, egy példa, mohó)

  10. ápr.14.
    -- 2. kis zh !! (anyaga: mintaillesztés és variánsai, dinamikus programozás, amortizációs elemzés)
    -- Edmonds-Karp-algoritmus, amikor a legrövidebb úttal javítunk
    -- Az előfolyam módszer
    (Irodalom: CLRS 26.2. vége, 26.4. eleje)

  11. ápr.28.
    -- Előfolyam módszer: helyesség, lépésszám
    -- Előreemelő algoritmus (vázlatosan)
    (Irodalom: CLRS 26.4., 26.5.)

  12. máj.5.

Következő alkalommal várható:
-- Minimális feszítőfa keresésre piros-kék algoritmus
-- alkalmazásai: Prim, Boruvka, Kruskal
-- UNIÓ-HOLVAN adatszerkezet