Zkouška 21. 01. 2016 - Mareš

Pokračování přednášky TIN060 Algoritmy a datové struktury I
madvorak
Matfyz(ák|ačka) level I
Příspěvky: 8
Registrován: 2. 9. 2015 19:50
Typ studia: Informatika Bc.

Zkouška 21. 01. 2016 - Mareš

Příspěvek od madvorak »

MJ byl na zkoušce velice příjemný. Otázky byly 3 a k tomu jeden bonus, který nebyl potřeba řešit.

1) Třídící síť. Cílem je dosáhnout časové složitosti O((log n)^2), čili nejsnáz použít bitonickou třídičku z přednášky.
2) Jsou dány dva konvexní mnohoúhelníky. Rozhodněte, zda mají neprázdný průnik. Mnohoúhelník je myšlen i s jeho vnitřkem, takže pokud je malý mnohoúhelník uvnitř velkého mnohoúhelníku, ale strany se neprotínají, tak také mají neprázdný průnik. Výstupem programu je buď NE, nebo souřadnice jednoho libovolného bodu v průniku. Cílem je dosáhnout časové složitosti O(n), kde n je celkový počet vrcholů obou mnohoúhelníků.
3) Převeďte 3D párování na SAT (tedy opačný směr než byl na přednášce, ale je mnohem snazší).

Bonus: Je dána hromada prken. Prkno je kvádr o celočíselných rozměrech w, h a tloušťce 1. Prkna lze otáčet (místo w x h možno mít h x w), lepit na sebe a ořezávat. Rozhodněte, jaký největší kvádr (o co největším objemu) lze z nich vyrobit.
Odpovědět

Zpět na „TIN061 Algoritmy a datové struktury II“