Algoritmusok tervezése és elemzése I.

Előadás másodéves alkalmazott matematikus hallgatóknak

2023 tavasz

Előadó: Király Zoltán

Hétfő 12:15-13:45, D.3.218.


Csak a hallgatóimnak / Only for my students


Hirdetmények


Ajánlott irodalom


VIZSGATEMATIKA


1. előadás (II. 27.)

Algoritmus, input, output. Az algoritmusok lépésszáma, nagy ordó jelölés. Az algoritmusok tervezésének és elemzésének lépései nagy vonalakban, absztrakt adatstruktúrák.
A rendezési és a kiválasztási feladat.
4 algoritmus a legnagyobb elem kiválasztására. Kell is legalább n-1 összehasonlítás, alsó becslések, ellenség stratégia.
Két legnagyobb elem, illetve egyszerre legnagyobb és legkisebb elem megkeresése.


2. előadás (III. 6.)

A szótár feladat, felező (bináris) keresés rendezett tömbben.
Egyszerű rendezési algoritmusok.
Rendezéshez összehasonlításokkal kell n*log(n) lépés.
Összefésülő rendezés.
Adatstruktúrák, kupacok: bevezetés. Kupac definíciója, tárolása.


3. előadás (III. 13.)

BESZÚRÁS és felbillegtetés, BESZÚRÁS jósága. MINTÖRLÉS és lebillegtetés, MINTÖRLÉS jósága.

Kupacos rendezés, kupacépítés, k legkisebb elem kiválasztása.

Leszámláló rendezés. Számjegyes rendezés.


4. előadás (III. 20.)

Számolás nagy számokkal : összeadás, kivonás. Szorzás, maradékos osztás. Hatványozás, mod számolások célja, alapjai. mod m számítások, Euklideszi algoritmus és alkalmazásai.
Algoritmusok sebessége I, P osztály. NP osztály és NP-teljesség.
Dinamikus programozás: bevezetés, Fibonacci-számok.
Példák a Gyakorlaton.



5. előadás (III. 27.)

A hátizsák feladat és megoldása kis teherbírás esetén.

Láncolt listák, sorok, vermek.
Különböző gráfok tárolási módjai.
Összefüggőség eldöntése szélességi kereséssel, implementáció, lépésszám.


6. előadás (IV . 3.)

Szélességi keresés alkalmazásai: komponensek meghatározása.
Gyakorlaton: Gráf kétszínezése vagy páratlan kör megtalálása, legrövidebb út.

Összefüggőség eldöntéséhez kell is kb. annyi lépés, mint szélességivel.
Szélességi irányított gráfokon, gyenge és erős öf, eldöntésük.

Min költségű feszítőfa feladat, Prim algoritmusa. Prim algoritmus jósága, lépésszáma, megvalósítása bináris kupaccal, KULCS-CSÖKKENTÉS kupacokban.
A d-edfokú kupac, Prim megvalósítása d-edfokú kupaccal.


7. előadás (IV. 17.)

A legjobb d meghatározása.

Legrövidebb utak keresése, Dijkstra algoritmusa. Futási idő különböző implementációk esetén.
Dijkstra alkalmazások: legbiztonságosabb út, legszélesebb út.
Aciklikus gráfok, topologikus sorrend. PERT módszer. Tartalék idők kiszámítása.


8. előadás (IV. 24.)

Irányított gráfok konzervatív súlyozása.
Bellmann-Ford módszere legrövidebb utak keresésére konzervatív súlyozás esetén, jóság, futási idő.
Potenciál, negatív körök detektálása.

Legrövidebb útkeresés minden pontból minden pontba: Floyd-Warshall és Johnson.

Irányítatlan mélységi keresés (bejárás), mélységi és befejezési számozás.
Gyakorlaton: Az irányítatlan mélységi keresés alkalmazásai: erősen összefüggővé irányítás, 2-összefüggő blokkok keresése.

Bináris keresőfák definíciója.


9. előadás (V. 8.)

Bináris fák tárolása. Keresés, Beszúrás és Törlés bináris keresőfában.

AVL-fák: definíció, tétel a mélységről.
Belső művelet: a billentés. Beszúrás AVL-fába.

Párosítások, Stabil párosítás páros gráfban.


10. előadás (V. 15.)

Legnagyobb párosítás páros gráfban.
Hopcroft és Karp gyorsabb algoritmusa.
Párosítás nem páros gráfban (mese).

A hashelés alapjai: jó hash függvény, ütközések.
Vödrös hashelés.
Nyílt címzés, lineáris hashelés.
A lineáris hashelés várható lépésszámai.


11. előadás (V. 22.)

Univerzális hash függvény család és kakukk hashelés.

A bonyolultságelmélet alapjai, Turing-gép, eldönthetetlenség.

P és NP osztályok, NP-teljesség, Cook-tétel, példák NP-teljességre. A co-NP osztály, N\cap co-NP, a faktorizációs probléma.