Tematika (címszavakban)

2025 tavasz

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.
    -- 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 Johnson nem volt az órán, 6.6.2 )


13. máj.12.
    -- 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 )
    >
    máj. 15.
    3. kis zh !! (anyaga: folyam, előfolyam, minimális feszítőfa, piros-kék algoritmus és alkalmazásai(UNIÓ-HOLVAN megvalósítások már nincsenek benne)
    -- 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 )
    
14. máj. 19.
    -- nagy számok szorzása: Karacuba módszere
    -- Schönhage-Strassen-módszer ötlete -- polinomok szorzása és a Fourier-transzformálás -- kis mese a gyors Fourier-transzformáltról. (Irodalom: Lovász L. : Algoritmusok bonyolultsága   9.2.1 )