od madvorak » 21. 1. 2016 22:36
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.
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.