navigation
hledat
Teorie algoritmů
- Stránky předmětu: Teorie algoritmů
- Stránky Natalie Žukovec Natalie Žukovec
- Přednášející: Demlová
- Cvičící: Demlová, Žukovec
Cvičení
Semestrální testy
V semestru se píší dva testy za 15 a za 20 bodů.
Test 1
20.3.2019 - 1. Test
- 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).
- 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).
- 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).
- Posledni priklad byl master teorem za 4 body.
20.3.2019 - 2. Test (Stejné bodové hodnocení jako v 1. testu)
- Stejný jako v 1. testu
- Stejný jako v 1. testu
- 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.
- Také příklad na Master Theorem.
29.5.2020 - 1. test
Test 2
15. dubna 2020 test2-20.pdf
14.4.2021 Test Turingove stroje
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.
Přednášky - vše v jednom včetně doplňků a prolinkování dle výkladu
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
TAL přehled + vysvětlené redukce: tal_vytazky.pdf - POZOR: Nutno zkontrolovat, může obsahovat chyby.
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
Problém obchodního cestujícího
Nezávislé množiny → Vrcholové pokrytí
http://www.youtube.com/watch?v=cYw2ewoO6c4
Třídy složitosti (Nutno občas zkontrolovat)
Travelling salesman problem:
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:
