# Zkouska 25.5.2015 - Holan

<{ForumPost(poster="darthdeus", timestamp=2015-05-25 22:20:12)}>
Program simuluje vystaviste knih (jestli dobre pamatuju), ktere je reprezentovane 20x20 mrizkou. Na vystavisti se pohybuji spisovatele, od kterych sbirame autogramy. Kazdy autogram ma jinou cenu, a nasim cilem je nasbirat autogramy co nejvetsi ceny, a pokud je vic takovych, tak za co nejmensi vzdalenost.  
  
- Celkovy cas "simulace" je 1-5000 "tahu" - coz znamena, ze muzete udelat 5000 kroku.  
- Kazdy spisovatel ma svoji vlastni trasu kudy se pohybuje, a ujde 1-100 kroku, celkem je 10 spisovatelu.  
- Pohyb po mrizce je nahoru/dolu/doleva/doprava/stat - vzdy pohyb o jedno policko.  
- K dispozici je 27MB pameti.  
  
Spisovatele tedy chodi po mrizce 20x20, objevi se nekdy mezi 1-5000 "tahy", a pak zase po 1-100 "tazich" zmizi. Na vstupu dostanete soubor, kde je popsane chovani spisovatelu (format neni asi relevantni), tj. cas prichodu a trasa. Cilem ulohy je planovat svoji cestu tak, aby se nasbiralo co nejvic autogramu.  
  
Reseni - tj. jak jsme ho meli vypracovat:  
  
0) Predpoklady - pokud narazite na problem kde je vic moznosti, muzete jednu zvolit (za predpokladu ze to nezlehci zadani)  
1) Postrehy - pokud napr. zjistite, ze problem jde prevest na jiny problem, nebo cokoliv ohledne zadani/reseni co je relevantni zminit  
2) Zduvodneni vyberu algoritmu - popsat vybrany algoritmus a proc ho chcete pouzit  
3) Rozlozeni programu - popsat jak bude vas program fungovat  
4) Organizace dat - popsat jake datove struktury se pouziji  
5) Diskuse - nejaky zaver o reseni ulohy  
  
Meli jsme celkem 2 hodiny, informace o ustnim doplnim az nejake budou (jdu tam zitra :).)
<{/ForumPost}>

<{ForumPost(poster="petrroll", timestamp=2015-05-25 22:27:52)}>
Ústní je ze dvou částí: A) diskuze algoritmu, B) teoretická část  
  
A)   
-Zdálo se, že naše papíry s řešením prakticky nečetl, tj. šlo o to, mu celý algoritmus od základu vysvětlit.  
-Občas se pro kontrolu zeptal, jestli to co říkáme máme taky v papírech.  
-Opravdu se snažil algoritmus pochopit (tj. i když člověk neumí moc vysvětlovat tak to jde).  
-V algoritmu se ovšem snaží (a jde mu to) najít prakticky všechny možné chyby.  
--Není špatné si je uvědomit a upozornit na ně sám, i kdyby to v papíru nebylo (to ovšem nezatajovat!)).  
-Paměť se opravdu řeší a stojí za to si jí umět spočítat.  
-Hodnocení je rozumně mírné.  
  
B)   
-Teoretická část je rozhodně důležitější než jsem si (IMHO nejen já) myslel, IMHO tak 30 - 50 % známky.  
-Témata o kterých vím:   
--Dynamické programování (princip, alespoň dva případy použití dle vkusu, ...)  
--Binární vyhledávácí stromy (?)  
--QuickSort (Princip, jak udělat in-place, složitost, jiné nlogn sorty)  
  
PS: Stejný příklad: [26.5.2008](/NPRG031/Zkouska%20-%2026.5.2008)
<{/ForumPost}>