Algoritmusok tervezése és elemzése I.

Előadás matematika szakos BSc hallgatóknak

2024 tavasz

Előadó: Király Zoltán

Szerda 14:00-15:30, D.0.820. Hunfalvy János terem

Csak a hallgatóimnak / Only for my students

Hirdetmények

A jegyzet.
A vizsga elején, 10:15-től 10:35-ig mindenki beugrót ír. Utána a szóbeli részre csak az jöhet, aki mind a három kérdésre jó választ adott.
A beugró lehetséges kérdései (2023).
Vizsgázni az előadáson és a gyakorlaton elhangzott anyagból kell. Vizsgára csak az jöhet, akinek a Neptunban be van írva a gyakjegye.

Ajánlott irodalom

[RISz] Rónyai-Ivanyos-Szabó: Algoritmusok, Typotex, 1998
[CLRS] Cormen, Leiserson, Rivest, Stein: Új Algoritmusok, Scolar Kiadó, 2003
[AHU] Aho-Hopcroft-Ullman: Számítógépalgoritmusok tervezése és analízise, Mûszaki Kiadó, 1982
[KRS] Katona-Recski-Szabó: A számítástudomány alapjai, Typotex, 2002
[GL] Gács-Lovász: Algoritmusok, Tankönyvkiadó, 1989
[K] Knuth: A számítógépprogramozás mûvészete, Mûszaki Kiadó, 1987
Adatstruktúrák jegyzet.

VIZSGATEMATIKA

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

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.
Gyakorlaton: Két legnagyobb elem, illetve egyszerre legnagyobb és legkisebb elem megkeresése.

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

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. Bináris kupac definíciója.

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

Bináris kupac tárolása. 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. 6.)

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.

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

Dinamikus programozás: bevezetés, Fibonacci-számok.
Példák főleg a Gyakorlaton. 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 (III. 20.)

A szélességi keresés jósága, tulajdonságai. 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.

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

A d-edfokú kupac, Prim megvalósítása d-edfokú kupaccal.
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.

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

Aciklikus Dijkstra, tartalék idők kiszámítása.

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.

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

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. 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.

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

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

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

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

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.

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

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

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.