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.
- 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)
- 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) )
- 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.
- 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)
- 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 )
- 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
- 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)
- 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
-
á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ó)
- á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)
- ápr.28.
-- Előfolyam módszer: helyesség, lépésszám
-- Előreemelő algoritmus (vázlatosan)
(Irodalom: CLRS 26.4., 26.5.)
- 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