1-INF-310 Tvorba efektívnych algoritmov
Odporúčaný ročník: | 3. |
Semester: | zimný |
Rozsah: | P3,C1 |
Hodnotenie: | 30/70 |
Počet kreditov: | 6 |
Vyučujúci: | |
www stránka: |
Cieľ:
Naučiť študentov základné metódy tvorby efektívnych algoritmov a oboznámiť s principiálnymi algoritmami.
Sylabus:
- Problém slovníka (2-3 stromy).
- Union/Find-Set problém.
- Algoritmy pre hľadanie najkratších ciest a najlacnejšej kostry grafu.
- Princípy tvorby efektívnych algoritmov (vrátane konkrétnych aplikácií).
- Rozdeľuj a panuj.
- Dynamické programovanie.
- "Greedy" algoritmy, vyváženosť a voľba vhodnej dátovej štruktúry.
- Triedy P a NP, polynomiálna redukovateľnosť, [Cookova veta] a NP-úplné problémy, string matching, pravdepodobnostné algoritmy, výpočtová geometria.
Literatúra:
Cormen T.H., Leiserson C.E., Rivest R.L.: Introduction to Algorithms, MIT Press, 1990
Aho A.V., Hopcroft J.E., Ullman J.D.: The Design and Analysis of Computer Algorithms, Addison-Wesley, 1976
Brassard G., Bratley P.: Fundamentals of Algorithmics, Prentice-Hall, 1996
R. Sedgewick: Algorithms in C++, Addison-Wesley, 1992