fork download
copy 
  1. 1. zlozitost:
  2.    - casove odhady algoritmov
  3.    - zoradenie funkcii
  4.    - definicie asymptotickej zlozitosti (theta, omega, omikron...)
  5.    - vypocet zlozitosti (napr. master theorem)
  6.  
  7.    - je mozne aby sucasne platilo f(n) = o(g(n)) aj g(n) = o(f(n)) ? Zdovodnite.
  8.    - aky je vztah medzi triedami o(g(n)), O(g(n)) a OMEGA(g(n)) ?
  9.  
  10.    - kdyz f(n) = O(g(n)), plati f(n)² = O(g(n)²) ?
  11.    - pokud plati f(n) nalezi theta g(n), plati pak 2^f(n) nalezi theta 2^g(n) ? Zduvodnete
  12.  
  13.    - 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)
  14.    - 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.
  15.    - 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))
  16.  
  17.    - 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
  18.    - 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))
  19.    - Je dána fce f(n) = n log^3 n + n^2 + ...., najdi nejjednodušší g(n) tak, aby platilo f(n) = theta(g(n))
  20.    - f(n)= 5*log(n!) + 4*(log n)^4 + 5*n^2, určete co nejhezčí Ω(g(n)) a podrobně zdůvodněte
  21.    - 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))
  22.    - 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.     
  23.  
  24.  
  25. 2. turingov stroj
  26.      - definicia TM, z akych casti sa sklada a aky maju vyznam
  27.      - vysvetlit jeden krok TM
  28.      - co znamena ze TM realizuje funkciu
  29.      - kedy TM jazyk prijima a kedy akceptuje
  30.      - rozdiel medzi deterministickym a nedeterministickym TM
  31.      - priklad na TM: myslienka, navrh, popis behu vypoctu TM pre zadane vstupne slovo
  32.  
  33. 3. teoria zlozitosti:
  34.      - triedy, ich vztahy a porovnania
  35.      - co ak by jazyk lezal tam a tam
  36.      - co je rekurzivne spocetne a nie je rekurzivne
  37.      - nejake priklady roznych jazykov (aj rekurzivnych)
  38.      - NP ulohy
  39.      - prevody (dobre sa naucit nejaky jeden)
  40.      - vztah medzi triedami jazykov rozpoznavanymi deterministickym a nedeterministickym TM
  41.  
  42.      - definovat pamatovu a casovu zlozitost TM
  43.      - definovat P, NP, NPC, PSPACE, NPSPACE, R, RE, ZPP, RP, CO-NP... vsetky pouzite pojmy riadne vysvetlit.
  44.      - rozdiel medzi rekurzivnymi a rek. spocetnymi jazykmi
  45.      - priklad jazyka ktory patri do NPSPACE, RP. Zdovodnit.
  46.      - priklad rozhodovacieho problemu kt. nepatri do NP
  47.      - aky je vztah medzi triedami P, NP, PSPACE, NPSPACE (uviest vzdy najsilnejsie vztahy)
  48.      - vztah medzi triedou rekurzivnych jazykov a NPSPACE + zdovodnit
  49.      - vztah co-NP a ZPP.
  50.      - 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.
  51.      - viete ze rozhodovacia uloha U sa polyn. redukuje na rozhod. ulohu V, ktora je NP uplna. Co plati pre rozhod. ulohu U?
  52.      - jaky je rozdil mezi tridou jazyku tvorenou jazyky prijimanymi DTM a NTM? (zadny, obe jsou R)
  53.      - vztah mezi jazyky ROZHODOVANÝMI deterministickým TM a jazyky rozhodovanými nedeterministikým TM.
  54.      - 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í.
  55.        Pokud jsou některé tyto inkluze ostré, uveď příklad jazyka patřícího do jedné třídy a nepatřícího do druhé.
  56.      - 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
  57.  
  58.      - 2 priklady NPC uloh a priklad rozhodnutelnej ulohy ktora nelezi v NP (ak take ulohy existuju)
  59.      - 2 priklady NP uplnych a 2 priklady NP uloh (ak take ulohy existuju)
  60.  
  61.      - su dane jazyky L1 - postov koresp. problem, L3 - doplnok diagonalneho jazyka. Co plati o jazyku L2, ak viete: L1 <| L2 <| L3 ? Zdovodnite.     
  62.      - je dany jazyk L, kt. sa sklada z vsetkych grafov majucich barevnost (chrom. cislo) aspon 3. do kt. vsetkych tried jazyk patri? Zdovodnite.
  63.      - je dany jazyk L, kt. sa sklada zo vsetkych grafov, v kt. su presne 2 ham. kruznice. Zdovodnite ci patri do NP alebo NPSPACE.
  64.      - 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
  65.      - 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.
  66.      - je dany TM kt. rpijima jazyk s pamatovou zlozitostou f(n). Je pravda ze L je rekurzivny jazyk? Zdovodnit.
  67.      - 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...)
  68.      - 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í.
  69.        Napište nejsilnější tvrzení, které platí pro úlohu V a zdůvodněte.
  70.  
  71.  
  72.      - redukcia ham. kruznice, 3-barevnosti...
  73.  
Not running #stdin #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/DWUXfX
language:
Text (text 6.10)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!