Az előadás táblaképe.
Az előadás videófelvétele. Elérhető II. 15.-ig.
Az előadás táblaképe.
Az előadás videófelvétele. Elérhető II. 22.-ig.
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.
Az előadás táblaképe.
Az előadás videófelvétele. Elérhető III. 8.-ig.
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.
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.
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.
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.
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.
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.
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.
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.
ELMARAD!