Zkouska 25.5.2015 - Holan

Pokračování základního kursu programování pro studenty 1. ročníku bakalářského studia informatiky a učitelství informatiky. Výuka bezprostředně navazuje na předmět PRG030 Programování I výkladem dalších algoritmů a jejich programové realizace, postupů a technik užívaných při tvorbě programů. Posluchači se seznámi se základy objektového programování a práce v současných vývojových prostředích. Předpokládají se vstupní znalosti v rozsahu předmětu PRG030 Programování I.
darthdeus
Matfyz(ák|ačka) level I
Příspěvky: 6
Registrován: 24. 2. 2014 16:49
Typ studia: Informatika Ph.D.
Bydliště: Praha
Kontaktovat uživatele:

Zkouska 25.5.2015 - Holan

Příspěvek od darthdeus »

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 :).)
Uživatelský avatar
petrroll
Matfyz(ák|ačka) level I
Příspěvky: 12
Registrován: 23. 5. 2015 22:27
Typ studia: Informatika Bc.

Re: Zkouska 25.5.2015 - Holan

Příspěvek od petrroll »

Ú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: http://forum.matfyz.info/viewtopic.php?f=247&t=4425
Odpovědět

Zpět na „PRG031 Programování II“