Tematika (címszavakban)

2024 tavasz

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 )