INFORMAČNÝ LIST PREDMETU |
|||||
Kód: A716 |
Skratka: AVZ |
Názov: Algoritmy a výpočtová zložitosť | |||
Študijný odbor: Aplikovaná matematika Ekonomická |
|||||
Garantuje: Zabezpečuje: RNDr. Peter Varša |
|||||
Semester: zimný Odporučený: 7 |
Rozsah výučby: prednášky – cvičenia –
laboratórne cvičenia Týždenný: 2-0-0 Za semester: 24-0-0 |
ECTS kredity: 3 |
|||
Podmieňujúce predmety: | |||||
Ukončenie predmetu a spôsob hodnotenia: priebežne – 15% skúška (písomná a ústna) – 85% |
|||||
Cieľ predmetu: Teória a prax návrhu a analýzy algoritmov. Časová a pamäťová zložitosť algoritmov. |
|||||
Stručný sylabus: Kombinatorické problémy a ich klasifikácia. Časová a pamäťová zložitosť algoritmov. Polynomiálne a exponenciálne algoritmy. Polynomiálne algoritmy riešenia vybraných problémov a analýza ich výpočtovej zložitosti – algoritmy vyhľadávania a triedenia. Vybrané grafové algoritmy. rekurzívne funkcie a ich zložitosť. Triedy problémov – P, NP, NPC, coNP. NP-úplné problémy. Metódy dôkazu NP-úplnosti algoritmov. Pamäťová náročnosť a triedy pamäťovej zložitosti – PSPACE, NPSPACE. Pravdepodobnostné algoritmy a ich zložitosť. Heuristiky. |
|||||
Literatúra: Kučera, L.: Kombinatorické algoritmy, SNTL Praha, 1989 |
|||||
Dátum poslednej úpravy osnovy: 18.12.2002 |