news rss feed
Prerekvizity
Od študenta, ktorý si zapíše tento predmet, budem očakávať približne nasledovné vedomosti:
- mať základy analýzy časovej zložitosti: vedieť správne použiť O, Thetu a Master theorem
- poznať a vedieť použiť klasické dátové štruktúry, ako napr. haldu a vyvažovaný binárny strom
- poznať základné diskrétne štruktúry (vektory, matice, grafy, stromy) a vedieť ich v programe vhodne reprezentovať
- ovládať základné techniky návrhu efektívnych algoritmov, vrátane dynamického programovania
- poznať aspoň jeden algoritmus na nájdenie najlacnejšej cesty a aspoň jeden na nájdenie najlacnejšej kostry v grafe
Ciele
Absolvent predmetu by mal stretnúť (a možno dokonca vedieť používať) nejaké pokročilejšie algoritmické techniky. Ešte nie na úrovni "cutting-edge research" ale lepšie a viac ako ľudia ktorí absolvovali len úvodné predmety z tohto smeru. Dôraz u tohto predmetu je pritom na exaktné a efektívne algoritmy, teda veci čo bežia v polynomiálnom čase a počítajú optimálne riešenia problémov.
Syllabus
TODO: Syllabus nie je úplný a ešte v ňom budú prebiehať zmeny.
- Najkratšie cesty v grafoch: teoretický a praktický pohľad.
- Matroidy a efektívne pažravé algoritmy.
- FFT, výpočet konvolúcií a jeho aplikácie.
- Algoritmy z teórie čísel.
- Kombinatorické algoritmy.
- Analýza netriviálnych algoritmov (e.g., súvis qsortu a náhodných BST).
- Techniky optimalizácie dynamického programovania.
- Efektívna implementácia algoritmov.