====== Teorie algoritmů ====== * Stránky předmětu: [[http://math.feld.cvut.cz/demlova/teaching/tal_vyuka.html|Teorie algoritmů]] * Stránky Scholtzové s úkoly [[http://math.feld.cvut.cz/scholtzova/|Jiřina Scholtzová]] * Přednášející: Demlová * Cvičící: Demlová, Scholtzová ===== Cvičení ===== **2014/2015** \\ [[courses/a4m01tal/ukol1_ls1415|5. úkol (Scholtzová)]] **2013/2014** \\ [[courses/a4m01tal/ukol1_ls1314|1. úkol (Demlová)]] [[courses/a4m01tal/ukol1|1. úkol]] | [[courses/a4m01tal/ukol2|2. úkol]] | [[courses/a4m01tal/ukol4|4. úkol]] | [[courses/a4m01tal/ukol5|5. úkol]] {{:courses:redukce_npc_zednicky_metr_.pdf| redukce NPC (zednický metr)}} ===== 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). [[https://docs.google.com/document/d/1z_V0m3zSVl-_ckbd1mbUHATLXfBqJ7FYz_xVq3Vrd-k/edit#|řešení testů z minulých let]] [[http://uloz.to/5072455/a4m16tal-all.pdf|Přednášky - vše v jednom]] [[http://uloz.to/xXGvBNb/tal-prednasky-2012-pdf|Přednášky - vše v jednom včetně doplňků a prolinkování dle výkladu]] [[courses/a4m01tal/zkouska-2010-06-07|Zkouška 7. 6. 2010]] [[courses/a4m01tal/zkouska-2010-06-14|Zkouška 14. 6. 2010]] [[courses/a4m01tal/zkouska-2010-06-24|Zkouška 24. 6. 2010]] [[courses/a4m01tal/zkouska-2010-06-30|Zkouška 30. 6. 2010]] [[courses/a4m01tal/zkouska-2011-05-26|Zkouška 26. 5. 2011]] [[courses/a4m01tal/zkouska-2011-06-16|Zkouška 16. 6. 2011]] [[courses/a4m01tal/zkouska-2011-06-23|Zkouška 23. 6. 2011]] [[courses/a4m01tal/zkouska-2012-15-21|Zkouška 21. 5. 2012]] [[courses/a4m01tal/zkouska-2012-06-05|Zkouška 5. 6. 2012]] [[courses/a4m01tal/zkouska-2012-06-19|Zkouška 19. 6. 2012]] [[courses/a4m01tal/zkouska-2012-06-25|Zkouška 25. 6. 2012]] [[courses/a4m01tal/zkouska-2012-08-24|Zkouška 24. 8. 2012]] [[courses/a4m01tal/zkouska-2013-06-13|Zkouška 13. 6. 2013]] [[courses/a4m01tal/zkouska-2014-05-21|Zkouška 21. 5. 2014]] [[courses/a4m01tal/zkouska-2014-06-05|Zkouška 5. 6. 2014]] [[courses/a4m01tal/zkouska-2014-06-12|Zkouška 12. 6. 2014]] [[courses/a4m01tal/zkouska-2015-06-04|Zkouška 4. 6. 2015]] [[courses/a4m01tal/zkouska-2015-06-08|Zkouška 8. 6. 2015]] [[courses/a4m01tal/zkouska-2016-06-16|Zkouška 16. 6. 2016]] [[courses/a4m01tal/zkouska-2016-06-30|Zkouška 30. 6. 2016]] [[courses/a4m01tal/zkouska-2016-09-07|Zkouška 7. 9. 2016]] -- [[http://ideone.com/DWUXfX | sourhn otazek ze zkousek 2010-2012]] ===== Materiály ===== Kvalitny strucny prehlad toho co sa vzdy opakuje na skuskach, a co je dolezite: {{:courses:p0_prehladtal.pdf|}} Příklady na master theorem se všemožnými zradami : {{:courses:a4m01tal:master_theorem.pdf}} Turingův stroj pro otočení slova {{:courses:turing_otoceni_slova.pdf|}} Jeden velký a užitečný knedlík tříd: {{:courses:knedlik.pdf|}} [[http://www.algoritmy.net/article/5774/Tridy-slozitosti|Třídy složitosti a Turingovy stroje]] [[http://en.wikipedia.org/wiki/List_of_complexity_classes]] [[http://www.complexityzoo.com | Complexity ZOO]] [[http://www.algoritmy.net/article/5407/Obchodni-cestujici|Problém obchodního cestujícího]] [[http://www.algoritmy.net/article/5521/Batoh|Problém batohu]] [[http://www.algoritmy.net/article/7303/Nezavisle-mnoziny--Vrcholove-pokryti|Nezávislé množiny → Vrcholové pokrytí]] [[http://www.algoritmy.net/article/7351/Kliky---Nezavisle-mnoziny|Kliky → Nezávislé množiny]] [[http://www.algoritmy.net/article/7682/Subset-sum--Deleni-koristi|Subset sum → Dělení kořisti]] [[http://www.algoritmy.net/article/7510/SAT--3-CNF-SAT|SAT → 3-CNF SAT]] [[https://www.slideshare.net/rajendranjrf/posts-correspondence-problem|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 {{:courses:tal_plan.png?600|}} Travelling salesman problem: {{:courses:travelling_salesman_problem.png|}} {{:courses:npc.png|TAL v NTK}} ---- Odpověď na otázku typu dokažte: {{:courses:it-is-known.gif|}} ~~DISCUSSION~~