Algoritmusok tervezése és elemzése I.

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

2021 tavasz

Előadó: Király Zoltán

Kedd 14:15-15:45, TEAMS


Csak a hallgatóimnak / Only for my students


Hirdetmények

Az online vizsgázásról:


Ajánlott irodalom


Vizsgatematika

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

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.

Az előadás táblaképe.

Az előadás videófelvétele. Elérhető II. 15.-ig.


2. előadás (II. 16.)

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.
BESZÚRÁS algoritmusa (felbillegtetés), jósága. MINTÖRLÉS algoritmusa (lebillegtetés), jósága.

Az előadás táblaképe.

Az előadás videófelvétele. Elérhető II. 22.-ig.


3. előadás (II. 23.)


MINTÖRLÉS pontos megvalósítása. Kupacos rendezés, kupacépítés, k legkisebb elem kiválasztása.

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

Számolás nagy számokkal I: összeadás, kivonás. Szorzás, maradékos osztás, hatványozás. mod számolások célja, alapjai.

Az előadás táblaképe.

Az előadás videófelvétele. Elérhető III. 1.-ig.


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

Számolás nagy számokkal II: mod m számítások, Euklideszi algoritmus és alkalmazásai.
Algoritmusok sebessége I, P osztály. NP osztály és NP-nehézség.
Dinamikus programozás: bevezetés, megoldás a hátizsák feladatra. A többi példa a Gyakorlaton.


Az előadás táblaképe.

Az előadás videófelvétele. Elérhető III. 8.-ig.


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

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.
Szélességi keresés alkalmazásai: komponensek meghatározása, legrövidebb út, Gyakorlaton: Gráf kétszínezése vagy páratlan kör megtalálása.
Összefüggőség eldöntéséhez kell is kb. annyi lépés, mint szélességivel.

Az előadás táblaképe.

Az előadás videófelvétele. Elérhető III. 15.-ig.


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

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.

Az előadás táblaképe.

Az előadás videófelvétele. Elérhető III. 22.-ig.


7. előadás (III. 23.)

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.
Irányított gráfok konzervatív súlyozása.
Bellmann-Ford módszer 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.

Az előadás táblaképe.

Az előadás videófelvétele. Elérhető III. 29.-ig.


8. előadás (III. 30.)

Irányítatlan mélységi keresés, mélységi és befejezési számozás.
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: Gyakorlaton.

Bináris keresőfák II. 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 (és törlés) AVL-fában.

Az előadás táblaképe.

Az előadás videófelvétele. Elérhető IV. 12.-ig.


9. előadás (IV. 13.)

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.
Univerzális hash függvény család és kakukk hashelés.

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

Az előadás táblaképe.

Az előadás videófelvétele. Elérhető IV. 19.-ig.


10. előadás (IV. 20.)

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.

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

Az előadás táblaképe.

Az előadás videófelvétele. Elérhető IV. 26.-ig.


11. előadás (IV. 27.)

Hopcroft és Karp algoritmusa párosítás keresésére.

Kétirányú Dijkstra, A^* algoritmus.
Autópálya hierarchia.

Az órán említett doktori értekezés.

Az előadás táblaképe.

Az előadás videófelvétele. Elérhető V. 3.-ig.


12. előadás (V. 4.)

Mediáns keresése. Gyorsrendezés.
Legrövidebb útkeresés minden pontból minden pontba.

Az előadás táblaképe.

Az előadás videófelvétele. Elérhető V. 10.-ig.


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

ELMARAD!