Teorie algoritmů

Cvičení

Semestrální testy

V semestru se píší dva testy za 15 a za 20 bodů.

Test 1

20.3.2019 - 1. Test

  1. V prvním příkladu se po nás chtělo napsat definici f(n) je o(g(n)) a velke omega. A potom napsat nejsilnejsi vztah mezi o a velke omega a zduvodnit jej (2 body).
  2. Ve druhem prikladu bylo receno ze: f(n) je o(h(n)) a g(n) je velke omega (h(n)) a ukolem bylo dokazat nebo vyvratit f(n) + g(n) je o(h(n)) (za 6 bodu).
  3. Ve tretim prikladu byla zadana funkce f(n) = 3lg(n!) + 2(lg(n))^5 + 4n a meli jsme nalezt nejjednodussi a asymptoticky nejrychleji rostouci g(n) tak aby f(n) byla velke omega (g(n)) (3 body).
  4. Posledni priklad byl master teorem za 4 body.

20.3.2019 - 2. Test (Stejné bodové hodnocení jako v 1. testu)

  1. Stejný jako v 1. testu
  2. Stejný jako v 1. testu
  3. Ukázat na dvou konkrétních fcí f(n) a g(n), jestli $$ f(n) \in \omega(g(n))$$, nebo $$ g(n) \in \omega(f(n))$$ nebo oboje.
  4. Také příklad na Master Theorem.

29.5.2020 - 1. test

test1-20.pdf

Test 2

15. dubna 2020

test2-20.pdf

Zkouška

Zkouška probíhá následující den už od dopoledne. Jakmile odevzdáte písemku, je možné se na papíře zapsat na konkrétní hodinu. Na 30 minut jsou bráni 4 studenti.

- ústní naprosto v poho, dávala to i lidem kteří měli >45 bodů. Když vidí, že tomu rozumíte, není 20 bodů limitujícím faktorem, klidně se dá polepšit i o trošku víc, ale to už musíte fakt něco předvést. Naopak, kdo má málo bodů z testu, už si většinou o moc nepomohl. Na začátku ústní projde s vámi písemku a řekne, co si o tom myslí, případně přidá body :). Když chcete lepší známku, dá vám nějaký příklad navíc. Někdo si mohl dokonce říct, co umí nejvíc.

potvrzuji, prisel jsem tam s ohodnoceni 60+b a odesel s A, stezoval jsem na to, ze se dalo snadno opisovat a na to jak je ta pisemka lehoucka, tak to proste nic nevypovida o skutecne znalosti…, na druhou stranu by byla asi sebevrazda, kdybych to skutecne neumel. Plusem taky bylo, ze pisemka byla hodne zdlouhava, a kdo si to pise poctive z hlavy, tak proste nestiha

Ustni 2014: Scholtzova uplne v pohode. Davali to i lidi, co meli z testu 33/70 (min. 35), ale ty dva body tam je treba najit behem diskuze o testu, treba tak, ze reknete, ze tohle jste mysleli tak a tohle zase onak. Lidi s 35+ to vetsinou dali. Osobne jsem mel 50 a jako otazku k ustni jsem mel posledni priklad z testu (pokud ho sem nekdo da, tak se podivejte, cele zadani nevim, slo o Lu, Ld, Le, Lne jazyky, RE, R tridy a vztahy mezi nimi) s tim, ze me postouchla a ja uz pak vetsinu napsal a rekl sam a co bylo nejasne nebo chybelo, tak doplnila za me. Odesel jsem s C (lip by to ani neslo). Ostatni na ustni dostavali napr. ukazte nejakou redukci NPC (konkretni priklad jste si mohli vybrat).

Ustni 2019: Pokud je nejaka definice, nebo dukaz v prednaskach, zapamatujte si ho doslova. U ustni jsem rekl ekvivalentni ale mirne zmenenou definici diagonalniho jazyka a pani Demlova mi malem ukousla hlavu. To same s dukazy, pokud je v prednasce neco dokazano sporem na ne-rekursivne-spocetny Ld, dokazat to pomoci Halting problemu, nebo tvrzeni ohledne nerekursivniho doplnku znamena ztratu bodu.

řešení testů z minulých let

Přednášky - vše v jednom

Přednášky - vše v jednom včetně doplňků a prolinkování dle výkladu

Zkouška 7. 6. 2010

Zkouška 14. 6. 2010

Zkouška 24. 6. 2010

Zkouška 30. 6. 2010

Zkouška 26. 5. 2011

Zkouška 16. 6. 2011

Zkouška 23. 6. 2011

Zkouška 21. 5. 2012

Zkouška 5. 6. 2012

Zkouška 19. 6. 2012

Zkouška 25. 6. 2012

Zkouška 24. 8. 2012

Zkouška 13. 6. 2013

Zkouška 21. 5. 2014

Zkouška 5. 6. 2014

Zkouška 12. 6. 2014

Zkouška 4. 6. 2015

Zkouška 8. 6. 2015

Zkouška 16. 6. 2016

Zkouška 30. 6. 2016

Zkouška 7. 9. 2016

sourhn otazek ze zkousek 2010-2012

Materiály

Přednášky a konzultace ze semestru 2019/2020 ve formě videí + domácí úkoly s řešením.

Kvalitny strucny prehlad toho co sa vzdy opakuje na skuskach, a co je dolezite: p0_prehladtal.pdf

Příklady na master theorem se všemožnými zradami : master_theorem.pdf

Turingův stroj pro otočení slova turing_otoceni_slova.pdf

Jeden velký a užitečný knedlík tříd: knedlik.pdf

Třídy složitosti a Turingovy stroje

http://en.wikipedia.org/wiki/List_of_complexity_classes

Complexity ZOO

Problém obchodního cestujícího

Problém batohu

Nezávislé množiny → Vrcholové pokrytí

Kliky → Nezávislé množiny

Subset sum → Dělení kořisti

SAT → 3-CNF SAT

Slidy v AJ: Lu > MPCP > PCP

http://xkcd.com/505/

http://www.youtube.com/watch?v=cYw2ewoO6c4

Plánek tříd (A3), konzultovaný s pí. Demlovou

Travelling salesman problem:

TAL v NTK

Casto je tady videt tvrzeni, ze diagonalni jazyk je doplnek univerzalniho jazyka - neni to pravda!

  • Jazyk Ld se sklada ze vsech binarnich slov „w“ takovych, ze TM popsany slovem „w“ neprijima slovo „w“ (sam sebe).
  • Jazyk Lu se sklada ze slov tvaru “<M>w“, kde “<M>“ prijima „w.“

Odpověď na otázku typu dokažte:

courses/a4m01tal.txt · Poslední úprava: 2020/05/31 21:15 autor: anatra
Nahoru
chimeric.de = chi`s home Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0