INFORMAČNÝ LIST PREDMETU

Kód:

A716

Skratka:

AVZ

Názov: Algoritmy a výpočtová zložitosť

Študijný odbor: Aplikovaná matematika

Ekonomická

Garantuje: doc. Ing. Karol Matiaško, PhD.

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