Gráfok és algoritmusok elmélete (terv)

Matematika BSc, Elemző szakirány, 2016. ősz

Az előadások első része (1-7.)

1. Algoritmusokról (leírási mód, futási idők, az Ordó matematikája)

2. Alapvető adatszerkezetek I. (verem, sor, listák)

3. Alapvető adatszerkezetek II. (bináris fa, kupac (elsőbbségi sor))

4. Keresések és kiválasztások

5. Bináris keresőfa, AVL-fa

6. Összehasonlító rendezések

7. Hashelés, rendezés lineáris időben

Az előadások vázlatos tartalma (elsősorban a szereplő algoritmusok)

1. Algoritmusokról (leírási mód, futási idők, aszimptotika: az Ordó matematikája)

Verembe, Veremből műveletek (tömbös) – O(1)

Maximum kiválasztás – O(n)

Buborékrendezés – O(n²)

Bináris keresés – O(log n)

Hanoi tornyai – O(2ⁿ)

További nagyságrendekre majd jönnek algoritmusok, de ezek itt említésre kerülnek, pl. O(n log n)-es rendezések.

2. Alapvető adatszerkezetek I.

Verem

műveletei (tömbös ábrázolás): ÜresVerem, Üres?, Tele?, Verembe, Veremből, Felső

alkalmazása: helyes zárójelezés feldolgozása (összetartozó nyitó-csukó párok felismerése veremmel)

Sor

műveletei (tömbös ábrázolás): analóg a veremmel

alkalmazás: bináris fa szintfolytonos bejárása (lásd: 3. előadás))

Listák

lista, mint ábrázolási mód, pl. verem, sor pointeres megvalósítása, műveleteikkel együtt

alkalmazása: beillesztő rendezés fejelemes listára (lásd: 4. előadás)

lista, mint adattípus, fajtái: fejelem van/nincs, egyirányú/kétirányú, ciklikus/nem-ciklikus; egyiknek pl. a fejelemes egyszerű listának a teljes műveleti csomagja

3. Alapvető adatszerkezetek II.

Bináris fa

láncolt ábrázolás

tömbös ábrázolás (teljes, illetve majdnem teljes, balra rendezett bináris fa), szülő – gyerek csúcsok indexfüggvényei

három bejárás: preorder, inorder, posztorder

bináris fa szintfolytonos bejárása (sor adatszerkezet használatára példa)

rekurzív függvények bináris fákon, pl. levelek számának meghatározása

Kupac, elsőbbségi sor

a kupac, mint majdnem teljes balra tömörített bináris fa (ennek magassága), a szülő-gyerekei csúcsokban található értékek összefüggése

a kupac ábrázolása tömbben (emlékeztető: szülő-gyerek indexfüggvények)

kupac építése egy tömbben elhelyezett input értékekből

a kupac műveletei: maximum (vagy minimum) törlése, új kulcs beszúrása

az elsőbbségi sor (megvalósítható rendezetlen vagy rendezett tömbbel is, de általában a kupacot választjuk), műveletei: ÜresPrSor, Üres?, PrSorba, PrSorból, MaxPrior

4. Keresések és kiválasztások

Maximum kiválasztás (tömbös)

Bináris keresés

(két változat: <, =, > ágakkal, illetve ≤, > ágakkal (ez végigkeres és rákérdez); mindkettő esetén rekurzív és iteratív algoritmus)

Barkochba

Két legnagyobb elem kiválasztása

A k-adik elem kiválasztása véletlenített algoritmussal (várhatóan lineáris időben)

5. Bináris keresőfa, AVL-fa

A bináris keresőfa

fogalma, min. és max. magassága, átlagos magassága (≤ 1,39 log n, levezetés nélkül)

nevezetes tulajdonsága: inorder bejárással rendezett kulcssorozatot kapunk

műveletei: Keres, MinKulcs, Következő, Beszúr, Töröl (ennek pszeudokódja nem, csak végrehajtás adott ábrán)

Az AVL-fa

fogalma, magassága (≤ 1,44 log n, levezetéssel)

forgatások beszúrás esetén (pszeudokódjuk nem, csak végrehajtásuk adott ábrán)

a forgatások: helyesek; visszaáll a beszúrás előtti famagasság; elég egy is

az AVL-fa építésének műveletigénye (beszúrás, ellenőrzés, forgatás)

6. Összehasonlító rendezések (műveletigény mindegyiknél, levezetés nélkül)

Buborék rendezés, a javított változat is

Beillesztő rendezés (tömbre és láncolt listára is)

Összefésülő rendezés (az Összefésül eljárás is)

Gyorsrendezés (a Partícionál eljárás is)

Kupacrendezés

7. Hashelés, rendezés lineáris időben

Hashelés (csak áttekintés)

kulcsütközés feloldása láncolással, illetve nyílt címzéssel

hash-függvények

Rendezés lineáris időben

számjegypozíciós rendezés „előre”

számjegypozíciós rendezés „visszafelé”

kulcsmezők szerinti „visszafelé haladó” rendezés listákkal

leszámoló rendezés