Neprihlásený používateľ
Cesta: Menu > Štúdium > Zoznam predmetov
1-INF-167 Výpočtová zložitosť a vypočítateľnosť
Odporúčaný ročník: 3.
Semester: zimný
Rozsah: P3,C1
Hodnotenie: 30/70
Počet kreditov: 6
Vyučujúci:prednáša doc. RNDr. Dana Pardubská CSc.
www stránka: http://www.dcs.fmph.uniba.sk/zlozitost/

Cieľ:

Získať prehľad o základných pojmoch a výsledkoch vo výpočtovej zložitosti a teórii vypočítateľnosti.

Sylabus:

RAM a jeho varianty, registrové a Turingove stroje, rekurzívne funkcie, výpočty a ekvivalencia vypočítateľnosti na jednotlivých modeloch. Churchova téza, existencia nerozhodnuteľných problémov. Základné zložitostné triedy a vzťahy medzi nimi, existencia ťažkých problémov. NP-úplnosť, Cookova veta a niektoré ďalšie (aj pre prax dôležité) NP-úplné problémy, vzťah rozhodovacích a optimalizačných problémov. Dôležité polynomiálne riešiteľné problémy. Vzťah P a NP, rôzne prístupy k vymedzeniu efektívnej riešiteľnosti(aproximačné a pravdepodobnostné algoritmy). PSPACE-úplné problémy.

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.
Korec: Úvod do teórie algoritmov, skriptá MFF UK, Bratislava, 1981.
Ch.H.Papadimitriou: Computational Complexity, Addison-Wesley Publishing Company, 1994.


Informačný list predmetu z AISu

Kontakt Hlavná stránka © 2012