1. zlozitost:
- casove odhady algoritmov
- zoradenie funkcii
- definicie asymptotickej zlozitosti (theta, omega, omikron...)
- vypocet zlozitosti (napr. master theorem)
- je mozne aby sucasne platilo f(n) = o(g(n)) aj g(n) = o(f(n)) ? Zdovodnite.
- aky je vztah medzi triedami o(g(n)), O(g(n)) a OMEGA(g(n)) ?
- kdyz f(n) = O(g(n)), plati f(n)² = O(g(n)²) ?
- pokud plati f(n) nalezi theta g(n), plati pak 2^f(n) nalezi theta 2^g(n) ? Zduvodnete
- f(n) = suma od 1 do n z k²; g(n) = n² log n; dokazte zda f(n) nalezi theta g(n) nebo velke O g(n)
- f(n) = 6 ln(n), g(n) = 5* suma od 1 po n z 1/(2k). Plati g(n) = O(f(n)) alebo opacne? Zdovodnite.
- f(n) = ln(n^(ln n)) , g(n) = suma od 1 po n z 1/k. Z definic rozhodnite ci plati: f(n) = O(g(n)), g(n) = O(f(n)), f(n) = THETA(g(n))
- najdite najjednoduchsiu funkciu g(n) co najvacsieho asymptotickeho rastu, taku ze f(n) patri OMEGA(g(n)), kde f(n) = 2n^(log n) + (log n)^n + 5n + 10
- Je dána fce f(n) = lg(n!) + (lg n)^4 + n^2 ...., najdi nejjednodušší g(n) tak, aby platilo f(n) = Omega(g(n))
- Je dána fce f(n) = n log^3 n + n^2 + ...., najdi nejjednodušší g(n) tak, aby platilo f(n) = theta(g(n))
- f(n)= 5*log(n!) + 4*(log n)^4 + 5*n^2, určete co nejhezčí Ω(g(n)) a podrobně zdůvodněte
- Mame f(n) = 2n^(log n) + (log n)^n + 10n + 5, najdete nejmensi, nejjednodussi a nejkrasnejsi g(n) takove, ze f(n) = Omikron(g(n))
- Nejjednodušší fce g(n) taková, že f(n) € Omega(g(n)), kdy f(n) = 2n^2 . log n + Suma pres k pro k=0 do n.
2. turingov stroj
- definicia TM, z akych casti sa sklada a aky maju vyznam
- vysvetlit jeden krok TM
- co znamena ze TM realizuje funkciu
- kedy TM jazyk prijima a kedy akceptuje
- rozdiel medzi deterministickym a nedeterministickym TM
- priklad na TM: myslienka, navrh, popis behu vypoctu TM pre zadane vstupne slovo
3. teoria zlozitosti:
- triedy, ich vztahy a porovnania
- co ak by jazyk lezal tam a tam
- co je rekurzivne spocetne a nie je rekurzivne
- nejake priklady roznych jazykov (aj rekurzivnych)
- NP ulohy
- prevody (dobre sa naucit nejaky jeden)
- vztah medzi triedami jazykov rozpoznavanymi deterministickym a nedeterministickym TM
- definovat pamatovu a casovu zlozitost TM
- definovat P, NP, NPC, PSPACE, NPSPACE, R, RE, ZPP, RP, CO-NP... vsetky pouzite pojmy riadne vysvetlit.
- rozdiel medzi rekurzivnymi a rek. spocetnymi jazykmi
- priklad jazyka ktory patri do NPSPACE, RP. Zdovodnit.
- priklad rozhodovacieho problemu kt. nepatri do NP
- aky je vztah medzi triedami P, NP, PSPACE, NPSPACE (uviest vzdy najsilnejsie vztahy)
- vztah medzi triedou rekurzivnych jazykov a NPSPACE + zdovodnit
- vztah co-NP a ZPP.
- vztahy medzi NP a triedami rekurzivnych a rek. spocetnych jazykov. ak niektore triedy nie su rovnake, uvedte priklad jazyka, kt. lezi v jednej a nelezi v druhej.
- viete ze rozhodovacia uloha U sa polyn. redukuje na rozhod. ulohu V, ktora je NP uplna. Co plati pre rozhod. ulohu U?
- jaky je rozdil mezi tridou jazyku tvorenou jazyky prijimanymi DTM a NTM? (zadny, obe jsou R)
- vztah mezi jazyky ROZHODOVANÝMI deterministickým TM a jazyky rozhodovanými nedeterministikým TM.
- Třída co-RE je doplněk jazyka RE. Co platí pro třídy R, RE, co-RE a třídu úplně všech jazyků VS. Napiš všechny inkluze, které platí.
Pokud jsou některé tyto inkluze ostré, uveď příklad jazyka patřícího do jedné třídy a nepatřícího do druhé.
- Třída EXP je třída všech jazyků přijímaných TS v exponenciálním čase (nebo něco v tom smyslu), určit vztah mezi EXP, NPSPACE, NP, co-NP
- 2 priklady NPC uloh a priklad rozhodnutelnej ulohy ktora nelezi v NP (ak take ulohy existuju)
- 2 priklady NP uplnych a 2 priklady NP uloh (ak take ulohy existuju)
- su dane jazyky L1 - postov koresp. problem, L3 - doplnok diagonalneho jazyka. Co plati o jazyku L2, ak viete: L1 <| L2 <| L3 ? Zdovodnite.
- je dany jazyk L, kt. sa sklada z vsetkych grafov majucich barevnost (chrom. cislo) aspon 3. do kt. vsetkych tried jazyk patri? Zdovodnite.
- je dany jazyk L, kt. sa sklada zo vsetkych grafov, v kt. su presne 2 ham. kruznice. Zdovodnite ci patri do NP alebo NPSPACE.
- popiste postup ako ukazete ze rozhodovacia uloha je NP uplna. (vysvetlite co je polyn. redukcia, a co bude vhodna polyn. redukcia robit) - teoreticky alebo na konkretnom priklade
- je uloha najdenia najdlhsich ciest z daneho vrcholu v vseobec. orient. ohodnotenom grafe NP uplna? Ak hej, preco? Ak nie, uvedte polynom. alg. kt. ju riesi.
- je dany TM kt. rpijima jazyk s pamatovou zlozitostou f(n). Je pravda ze L je rekurzivny jazyk? Zdovodnit.
- ako zistime, ci dana uloha lezi v NPC? (pouzit redukciu z NPC ulohy, napr. SAT. popisat tranzitivitu, blabloly o instancich U a V, definovat U patri V pri popisu redukcie...)
- Zadány úlohy U, V, W. Platí U <| V <| W (<| je polynomiální redukce). U je 2-barevnost, W je existence hamiltonovské kružnice, V se neví.
Napište nejsilnější tvrzení, které platí pro úlohu V a zdůvodněte.
- redukcia ham. kruznice, 3-barevnosti...
MS4gemxveml0b3N0OgogICAtIGNhc292ZSBvZGhhZHkgYWxnb3JpdG1vdgogICAtIHpvcmFkZW5pZSBmdW5rY2lpCiAgIC0gZGVmaW5pY2llIGFzeW1wdG90aWNrZWogemxveml0b3N0aSAodGhldGEsIG9tZWdhLCBvbWlrcm9uLi4uKQogICAtIHZ5cG9jZXQgemxveml0b3N0aSAobmFwci4gbWFzdGVyIHRoZW9yZW0pCiAgIAogICAtIGplIG1vem5lIGFieSBzdWNhc25lIHBsYXRpbG8gZihuKSA9IG8oZyhuKSkgYWogZyhuKSA9IG8oZihuKSkgPyBaZG92b2RuaXRlLgogICAtIGFreSBqZSB2enRhaCBtZWR6aSB0cmllZGFtaSBvKGcobikpLCBPKGcobikpIGEgT01FR0EoZyhuKSkgPwoKICAgLSBrZHl6IGYobikgPSBPKGcobikpLCBwbGF0aSBmKG4pwrIgPSBPKGcobinCsikgPwogICAtIHBva3VkIHBsYXRpIGYobikgbmFsZXppIHRoZXRhIGcobiksIHBsYXRpIHBhayAyXmYobikgbmFsZXppIHRoZXRhIDJeZyhuKSA/IFpkdXZvZG5ldGUKICAgCiAgIC0gZihuKSA9IHN1bWEgb2QgMSBkbyBuIHoga8KyOyBnKG4pID0gbsKyIGxvZyBuOyBkb2thenRlIHpkYSBmKG4pIG5hbGV6aSB0aGV0YSBnKG4pIG5lYm8gdmVsa2UgTyBnKG4pCiAgIC0gZihuKSA9IDYgbG4obiksIGcobikgPSA1KiBzdW1hIG9kIDEgcG8gbiB6IDEvKDJrKS4gUGxhdGkgZyhuKSA9IE8oZihuKSkgYWxlYm8gb3BhY25lPyBaZG92b2RuaXRlLgogICAtIGYobikgPSBsbihuXihsbiBuKSkgLCBnKG4pID0gc3VtYSBvZCAxIHBvIG4geiAxL2suIFogZGVmaW5pYyByb3pob2RuaXRlIGNpIHBsYXRpOiBmKG4pID0gTyhnKG4pKSwgZyhuKSA9IE8oZihuKSksIGYobikgPSBUSEVUQShnKG4pKQoKICAgLSBuYWpkaXRlIG5hamplZG5vZHVjaHNpdSBmdW5rY2l1IGcobikgY28gbmFqdmFjc2llaG8gYXN5bXB0b3RpY2tlaG8gcmFzdHUsIHRha3UgemUgZihuKSBwYXRyaSBPTUVHQShnKG4pKSwga2RlIGYobikgPSAybl4obG9nIG4pICsgKGxvZyBuKV5uICsgNW4gKyAxMAogICAtIEplIGTDoW5hIGZjZSBmKG4pID0gbGcobiEpICsgKGxnIG4pXjQgKyBuXjIgLi4uLiwgbmFqZGkgbmVqamVkbm9kdcWhxaHDrSBnKG4pIHRhaywgYWJ5IHBsYXRpbG8gZihuKSA9IE9tZWdhKGcobikpCiAgIC0gSmUgZMOhbmEgZmNlIGYobikgPSBuIGxvZ14zIG4gKyBuXjIgKyAuLi4uLCBuYWpkaSBuZWpqZWRub2R1xaHFocOtIGcobikgdGFrLCBhYnkgcGxhdGlsbyBmKG4pID0gdGhldGEoZyhuKSkKICAgLSBmKG4pPSA1KmxvZyhuISkgKyA0Kihsb2cgbileNCArIDUqbl4yLCB1csSNZXRlIGNvIG5lamhlesSNw60gzqkoZyhuKSkgYSBwb2Ryb2JuxJsgemTFr3ZvZG7Em3RlCiAgIC0gTWFtZSBmKG4pID0gMm5eKGxvZyBuKSArIChsb2cgbilebiArIDEwbiArIDUsIG5hamRldGUgbmVqbWVuc2ksIG5lamplZG5vZHVzc2kgYSBuZWprcmFzbmVqc2kgZyhuKSB0YWtvdmUsIHplIGYobikgPSBPbWlrcm9uKGcobikpCiAgIC0gTmVqamVkbm9kdcWhxaHDrSBmY2UgZyhuKSB0YWtvdsOhLCDFvmUgZihuKSDigqwgT21lZ2EoZyhuKSksIGtkeSBmKG4pID0gMm5eMiAuIGxvZyBuICsgU3VtYSBwcmVzIGsgcHJvIGs9MCBkbyBuLiAgICAgCgoKMi4gdHVyaW5nb3Ygc3Ryb2oKICAgICAtIGRlZmluaWNpYSBUTSwgeiBha3ljaCBjYXN0aSBzYSBza2xhZGEgYSBha3kgbWFqdSB2eXpuYW0KICAgICAtIHZ5c3ZldGxpdCBqZWRlbiBrcm9rIFRNCiAgICAgLSBjbyB6bmFtZW5hIHplIFRNIHJlYWxpenVqZSBmdW5rY2l1CiAgICAgLSBrZWR5IFRNIGphenlrIHByaWppbWEgYSBrZWR5IGFrY2VwdHVqZQogICAgIC0gcm96ZGllbCBtZWR6aSBkZXRlcm1pbmlzdGlja3ltIGEgbmVkZXRlcm1pbmlzdGlja3ltIFRNCiAgICAgLSBwcmlrbGFkIG5hIFRNOiBteXNsaWVua2EsIG5hdnJoLCBwb3BpcyBiZWh1IHZ5cG9jdHUgVE0gcHJlIHphZGFuZSB2c3R1cG5lIHNsb3ZvCgozLiB0ZW9yaWEgemxveml0b3N0aToKICAgICAtIHRyaWVkeSwgaWNoIHZ6dGFoeSBhIHBvcm92bmFuaWEKICAgICAtIGNvIGFrIGJ5IGphenlrIGxlemFsIHRhbSBhIHRhbQogICAgIC0gY28gamUgcmVrdXJ6aXZuZSBzcG9jZXRuZSBhIG5pZSBqZSByZWt1cnppdm5lCiAgICAgLSBuZWpha2UgcHJpa2xhZHkgcm96bnljaCBqYXp5a292IChhaiByZWt1cnppdm55Y2gpCiAgICAgLSBOUCB1bG9oeQogICAgIC0gcHJldm9keSAoZG9icmUgc2EgbmF1Y2l0IG5lamFreSBqZWRlbikKICAgICAtIHZ6dGFoIG1lZHppIHRyaWVkYW1pIGphenlrb3Ygcm96cG96bmF2YW55bWkgZGV0ZXJtaW5pc3RpY2t5bSBhIG5lZGV0ZXJtaW5pc3RpY2t5bSBUTQoKICAgICAtIGRlZmlub3ZhdCBwYW1hdG92dSBhIGNhc292dSB6bG96aXRvc3QgVE0KICAgICAtIGRlZmlub3ZhdCBQLCBOUCwgTlBDLCBQU1BBQ0UsIE5QU1BBQ0UsIFIsIFJFLCBaUFAsIFJQLCBDTy1OUC4uLiB2c2V0a3kgcG91eml0ZSBwb2pteSByaWFkbmUgdnlzdmV0bGl0LgogICAgIC0gcm96ZGllbCBtZWR6aSByZWt1cnppdm55bWkgYSByZWsuIHNwb2NldG55bWkgamF6eWttaQogICAgIC0gcHJpa2xhZCBqYXp5a2Ega3RvcnkgcGF0cmkgZG8gTlBTUEFDRSwgUlAuIFpkb3ZvZG5pdC4KICAgICAtIHByaWtsYWQgcm96aG9kb3ZhY2llaG8gcHJvYmxlbXUga3QuIG5lcGF0cmkgZG8gTlAKICAgICAtIGFreSBqZSB2enRhaCBtZWR6aSB0cmllZGFtaSBQLCBOUCwgUFNQQUNFLCBOUFNQQUNFICh1dmllc3QgdnpkeSBuYWpzaWxuZWpzaWUgdnp0YWh5KQogICAgIC0gdnp0YWggbWVkemkgdHJpZWRvdSByZWt1cnppdm55Y2ggamF6eWtvdiBhIE5QU1BBQ0UgKyB6ZG92b2RuaXQKICAgICAtIHZ6dGFoIGNvLU5QIGEgWlBQLgogICAgIC0gdnp0YWh5IG1lZHppIE5QIGEgdHJpZWRhbWkgcmVrdXJ6aXZueWNoIGEgcmVrLiBzcG9jZXRueWNoIGphenlrb3YuIGFrIG5pZWt0b3JlIHRyaWVkeSBuaWUgc3Ugcm92bmFrZSwgdXZlZHRlIHByaWtsYWQgamF6eWthLCBrdC4gbGV6aSB2IGplZG5laiBhIG5lbGV6aSB2IGRydWhlai4KICAgICAtIHZpZXRlIHplIHJvemhvZG92YWNpYSB1bG9oYSBVIHNhIHBvbHluLiByZWR1a3VqZSBuYSByb3pob2QuIHVsb2h1IFYsIGt0b3JhIGplIE5QIHVwbG5hLiBDbyBwbGF0aSBwcmUgcm96aG9kLiB1bG9odSBVPwogICAgIC0gamFreSBqZSByb3pkaWwgbWV6aSB0cmlkb3UgamF6eWt1IHR2b3Jlbm91IGphenlreSBwcmlqaW1hbnltaSBEVE0gYSBOVE0/ICh6YWRueSwgb2JlIGpzb3UgUikKICAgICAtIHZ6dGFoIG1lemkgamF6eWt5IFJPWkhPRE9WQU7DnU1JIGRldGVybWluaXN0aWNrw71tIFRNIGEgamF6eWt5IHJvemhvZG92YW7DvW1pIG5lZGV0ZXJtaW5pc3Rpa8O9bSBUTS4KICAgICAtIFTFmcOtZGEgY28tUkUgamUgZG9wbG7Em2sgamF6eWthIFJFLiBDbyBwbGF0w60gcHJvIHTFmcOtZHkgUiwgUkUsIGNvLVJFIGEgdMWZw61kdSDDunBsbsSbIHbFoWVjaCBqYXp5a8WvIFZTLiBOYXBpxaEgdsWhZWNobnkgaW5rbHV6ZSwga3RlcsOpIHBsYXTDrS4KICAgICAgIFBva3VkIGpzb3UgbsSba3RlcsOpIHR5dG8gaW5rbHV6ZSBvc3Ryw6ksIHV2ZcSPIHDFmcOta2xhZCBqYXp5a2EgcGF0xZnDrWPDrWhvIGRvIGplZG7DqSB0xZnDrWR5IGEgbmVwYXTFmcOtY8OtaG8gZG8gZHJ1aMOpLgogICAgIC0gVMWZw61kYSBFWFAgamUgdMWZw61kYSB2xaFlY2ggamF6eWvFryBwxZlpasOtbWFuw71jaCBUUyB2IGV4cG9uZW5jacOhbG7DrW0gxI1hc2UgKG5lYm8gbsSbY28gdiB0b20gc215c2x1KSwgdXLEjWl0IHZ6dGFoIG1lemkgRVhQLCBOUFNQQUNFLCBOUCwgY28tTlAKICAgICAKICAgICAtIDIgcHJpa2xhZHkgTlBDIHVsb2ggYSBwcmlrbGFkIHJvemhvZG51dGVsbmVqIHVsb2h5IGt0b3JhIG5lbGV6aSB2IE5QIChhayB0YWtlIHVsb2h5IGV4aXN0dWp1KQogICAgIC0gMiBwcmlrbGFkeSBOUCB1cGxueWNoIGEgMiBwcmlrbGFkeSBOUCB1bG9oIChhayB0YWtlIHVsb2h5IGV4aXN0dWp1KQoKICAgICAtIHN1IGRhbmUgamF6eWt5IEwxIC0gcG9zdG92IGtvcmVzcC4gcHJvYmxlbSwgTDMgLSBkb3Bsbm9rIGRpYWdvbmFsbmVobyBqYXp5a2EuIENvIHBsYXRpIG8gamF6eWt1IEwyLCBhayB2aWV0ZTogTDEgPHwgTDIgPHwgTDMgPyBaZG92b2RuaXRlLiAgICAgCiAgICAgLSBqZSBkYW55IGphenlrIEwsIGt0LiBzYSBza2xhZGEgeiB2c2V0a3ljaCBncmFmb3YgbWFqdWNpY2ggYmFyZXZub3N0IChjaHJvbS4gY2lzbG8pIGFzcG9uIDMuIGRvIGt0LiB2c2V0a3ljaCB0cmllZCBqYXp5ayBwYXRyaT8gWmRvdm9kbml0ZS4KICAgICAtIGplIGRhbnkgamF6eWsgTCwga3QuIHNhIHNrbGFkYSB6byB2c2V0a3ljaCBncmFmb3YsIHYga3QuIHN1IHByZXNuZSAyIGhhbS4ga3J1em5pY2UuIFpkb3ZvZG5pdGUgY2kgcGF0cmkgZG8gTlAgYWxlYm8gTlBTUEFDRS4KICAgICAtIHBvcGlzdGUgcG9zdHVwIGFrbyB1a2F6ZXRlIHplIHJvemhvZG92YWNpYSB1bG9oYSBqZSBOUCB1cGxuYS4gKHZ5c3ZldGxpdGUgY28gamUgcG9seW4uIHJlZHVrY2lhLCBhIGNvIGJ1ZGUgdmhvZG5hIHBvbHluLiByZWR1a2NpYSByb2JpdCkgLSB0ZW9yZXRpY2t5IGFsZWJvIG5hIGtvbmtyZXRub20gcHJpa2xhZGUKICAgICAtIGplIHVsb2hhIG5hamRlbmlhIG5hamRsaHNpY2ggY2llc3QgeiBkYW5laG8gdnJjaG9sdSB2IHZzZW9iZWMuIG9yaWVudC4gb2hvZG5vdGVub20gZ3JhZmUgTlAgdXBsbmE/IEFrIGhlaiwgcHJlY28/IEFrIG5pZSwgdXZlZHRlIHBvbHlub20uIGFsZy4ga3QuIGp1IHJpZXNpLgogICAgIC0gamUgZGFueSBUTSBrdC4gcnBpamltYSBqYXp5ayBzIHBhbWF0b3ZvdSB6bG96aXRvc3RvdSBmKG4pLiBKZSBwcmF2ZGEgemUgTCBqZSByZWt1cnppdm55IGphenlrPyBaZG92b2RuaXQuCiAgICAgLSBha28gemlzdGltZSwgY2kgZGFuYSB1bG9oYSBsZXppIHYgTlBDPyAocG91eml0IHJlZHVrY2l1IHogTlBDIHVsb2h5LCBuYXByLiBTQVQuIHBvcGlzYXQgdHJhbnppdGl2aXR1LCBibGFibG9seSBvIGluc3RhbmNpY2ggVSBhIFYsIGRlZmlub3ZhdCBVIHBhdHJpIFYgcHJpIHBvcGlzdSByZWR1a2NpZS4uLikKICAgICAtIFphZMOhbnkgw7psb2h5IFUsIFYsIFcuIFBsYXTDrSAgVSA8fCBWIDx8IFcgKDx8IGplIHBvbHlub21pw6FsbsOtIHJlZHVrY2UpLiBVIGplIDItYmFyZXZub3N0LCBXIGplIGV4aXN0ZW5jZSBoYW1pbHRvbm92c2vDqSBrcnXFvm5pY2UsIFYgc2UgbmV2w60uCiAgICAgICBOYXBpxaF0ZSBuZWpzaWxuxJtqxaHDrSB0dnJ6ZW7DrSwga3RlcsOpIHBsYXTDrSBwcm8gw7psb2h1IFYgYSB6ZMWvdm9kbsSbdGUuCiAgICAgICAKCiAgICAgLSByZWR1a2NpYSBoYW0uIGtydXpuaWNlLCAzLWJhcmV2bm9zdGkuLi4KICAgICA=