Vy\u010d\u00edslitelnost a slo\u017eitost 1 (Vy\u010d\u00edslitelnost a slo\u017eitost) – VYSL1, XVYS1, 7VYS1<\/p>\n\n\n\n
Vy\u010d\u00edslitelnost a slo\u017eitost 2 (Vy\u010d\u00edslitelnost a slo\u017eitost 2) – VYSL2, XVYS2 <\/p>\n\n\n\n
Z\u00e1kladn\u00ed opora Vy\u010d\u00edslitelnost a slo\u017eitost<\/a> <\/p>\n\n\n\n <\/p>\n\n\n\n Bal\u00ed\u010dek dodatkov\u00fdch materi\u00e1l\u016f pro VYSL1<\/a> nebo http:\/\/web.osu.cz\/~Habiballa\/opory\/vysl1pack.zip<\/a> Z\u00e1znamy p\u0159edn\u00e1\u0161ek v syst\u00e9mu Mediasite<\/a><\/p>\n\n\n\n Dopl\u0148kov\u00e1 opora VYSL2<\/a><\/p>\n\n\n\n Bal\u00ed\u010dek dodatkov\u00fdch materi\u00e1l\u016f pro VYSL2<\/a> nebo http:\/\/web.osu.cz\/~Habiballa\/opory\/vysl2pack.zip<\/a> Vy\u010d\u00edslitelnost a slo\u017eitost 1 (Vy\u010d\u00edslitelnost a slo\u017eitost) – VYSL1, XVYS1, 7VYS1 Vy\u010d\u00edslitelnost a slo\u017eitost 2 (Vy\u010d\u00edslitelnost a slo\u017eitost 2) – VYSL2, XVYS2 Z\u00e1kladn\u00ed opora Vy\u010d\u00edslitelnost a slo\u017eitost Bal\u00ed\u010dek dodatkov\u00fdch materi\u00e1l\u016f pro VYSL1 nebo http:\/\/web.osu.cz\/~Habiballa\/opory\/vysl1pack.zip Z\u00e1znamy p\u0159edn\u00e1\u0161ek v syst\u00e9mu Mediasite Dopl\u0148kov\u00e1 opora VYSL2 Bal\u00ed\u010dek dodatkov\u00fdch materi\u00e1l\u016f pro VYSL2 nebo http:\/\/web.osu.cz\/~Habiballa\/opory\/vysl2pack.zip Po\u017eadavky na studenta V prezen\u010dn\u00edm studiu […]<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":102,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"ngg_post_thumbnail":0,"footnotes":""},"class_list":["post-134","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/web.osu.cz\/~Habiballa\/wp-json\/wp\/v2\/pages\/134","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/web.osu.cz\/~Habiballa\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/web.osu.cz\/~Habiballa\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/web.osu.cz\/~Habiballa\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/web.osu.cz\/~Habiballa\/wp-json\/wp\/v2\/comments?post=134"}],"version-history":[{"count":9,"href":"https:\/\/web.osu.cz\/~Habiballa\/wp-json\/wp\/v2\/pages\/134\/revisions"}],"predecessor-version":[{"id":340,"href":"https:\/\/web.osu.cz\/~Habiballa\/wp-json\/wp\/v2\/pages\/134\/revisions\/340"}],"up":[{"embeddable":true,"href":"https:\/\/web.osu.cz\/~Habiballa\/wp-json\/wp\/v2\/pages\/102"}],"wp:attachment":[{"href":"https:\/\/web.osu.cz\/~Habiballa\/wp-json\/wp\/v2\/media?parent=134"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
<\/p>\n\n\n\n
<\/p>\n\n\n\nPo\u017eadavky na studenta<\/strong><\/td><\/tr> V prezen\u010dn\u00edm studiu 2 testy za celkem 60 bod\u016f a aktivity na cvi\u010den\u00ed za 40 bod\u016f na konci semestru. V kombinovan\u00e9m a distan\u010dn\u00edm studiu 4 koresponden\u010dn\u00ed \u00fakoly za celkem 100 bod\u016f.<\/td><\/tr> P\u0159ehled prob\u00edran\u00e9 l\u00e1tky<\/strong><\/td><\/tr> 1. Opakov\u00e1n\u00ed intuitivn\u00edch pojm\u016f algoritmick\u00e9 vy\u010d\u00edslitelnosti, rozhodnutelnosti a \u010d\u00e1ste\u010dn\u00e9 rozhodnutelnosti. Exaktn\u00ed formalizace t\u011bchto pojm\u016f. Deterministick\u00e9 Turingovy stroje (DTM), p\u0159\u00edklady. Univerz\u00e1ln\u00ed Turing\u016fv stroj.
2. Probl\u00e9m zastaven\u00ed a jeho nerozhodnutelnost. Dal\u0161\u00ed nerozhodnuteln\u00e9 probl\u00e9my, p\u0159evoditelnost probl\u00e9m\u016f. Churchova teze. D\u016fkazy nerozhodnutelnosti. Enumerace Turingov\u00fdch stroj\u016f. Riceova v\u011bta.
3. Algoritmy a jejich slo\u017eitost. T\u0159\u00eddy \u010dasov\u00e9 a prostorov\u00e9 slo\u017eitosti. Probl\u00e9my a jejich slo\u017eitost. Slo\u017eitost algoritmu jako horn\u00ed odhad slo\u017eitosti probl\u00e9mu. T\u0159\u00eddy \u010dasov\u00e9 slo\u017eitosti. Struktur\u00e1ln\u00ed slo\u017eitost. P\u0159\u00edklady v\u00fdpo\u010dt\u016f slo\u017eitosti probl\u00e9m\u016f.
4. Nedeterministick\u00e9 Turingovy stroje (NDTM), p\u0159\u00edklady NDTM. Jazyk akceptovateln\u00fd NDTM. Zm\u011bna \u010dasov\u00e9 a prostorov\u00e9 slo\u017eitosti p\u0159\u00ed p\u0159echodu od NDTM k DTM. T\u0159\u00edda P (=PTIME) a t\u0159\u00edda NP (=NPTIME) a jejich robustnost v\u016f\u010di v\u00fdpo\u010detn\u00edm model\u016fm. P\u0159\u00edklady NP probl\u00e9m\u016f. Polynomi\u00e1ln\u00ed redukovatelnost probl\u00e9m\u016f (jazyk\u016f).
5. NP-\u00fapln\u00e9 probl\u00e9my. Otev\u0159en\u00e1 ot\u00e1zka, zda P=NP. Probl\u00e9m SAT a jeho n\u00e1le\u017een\u00ed k t\u0159\u00edd\u011b NP. Idea d\u016fkazu NP-\u00faplnosti probl\u00e9mu splnitelnosti booleovsk\u00fdch formul\u00ed (Cookova v\u011bta).
6. Vyu\u017eit\u00ed polynomi\u00e1ln\u00ed redukovatelnosti k d\u016fkazu NP-\u00faplnosti dal\u0161\u00edch probl\u00e9m\u016f: 3CNF, k-vrcholov\u00e9 pokryt\u00ed, H-batoh, Partition, SubsetSum.
7. Dal\u0161\u00ed t\u0159\u00eddy \u010dasov\u00e9 i prostorov\u00e9 slo\u017eitosti a jejich vz\u00e1jemn\u00e9 vztahy. T\u0159\u00eddy PSPACE, EXPTIME, EXPSPACE. Idea rovnosti PSPACE=NPSPACE (Savitchova v\u011bta). P\u0159\u00edklady PSPACE-\u00fapln\u00fdch probl\u00e9m\u016f.
8. Primitivn\u011b rekurzivn\u00ed funkce. \u010c\u00e1ste\u010dn\u00e9 rekurzivn\u00ed funkce. Konstrukce konkr\u00e9tn\u00edch funkc\u00ed.
9. PL-vy\u010d\u00edsliteln\u00e9 funkce. Model RAM. D\u016fkaz ekvivalence s Turingov\u00fdmi stroji. V\u011bta o rekurzi.\u2002\u2002\u2002\u2002\u2002 <\/td><\/tr>Literatura<\/strong><\/td><\/tr> Z\u00e1kladn\u00ed: Habiballa, H. Vy\u010d\u00edslitelnost a slo\u017eitost, OU Ostrava, 2013..
Z\u00e1kladn\u00ed: Habiballa, H. \u00davod do informatiky, OU Ostrava, 2013..
Roz\u0161i\u0159uj\u00edc\u00ed: U. Manber. Introduction to Algorithms, Addison-Wesley..
Roz\u0161i\u0159uj\u00edc\u00ed: Aho, A., Hopcroft, J., Ullman, J. The design and analysis of computer algorithms, Addison-Wesley, 1974..
Doporu\u010den\u00e1: Jan\u010dar P.
JAN\u010cAR, PETR Teoretick\u00e1 informatika<\/em>. V\u0160B TU Ostrava
http:\/\/www.cs.vsb.cz\/jancar\/TEORET-INF\/teoret-inf.htm<\/a>
Doporu\u010den\u00e1: \u010cern\u00e1, I. \u00davod do teorie slo\u017eitosti, FI MUNI, 1993. <\/td><\/tr><\/tbody><\/table><\/figure>\n","protected":false},"excerpt":{"rendered":"