Skládání obdélníků
| Thesis title in Czech: | Skládání obdélníků |
|---|---|
| Thesis title in English: | Packing rectangles |
| Key words: | skládání, obdélník, algoritmus, kombinatorická geometrie |
| English key words: | packing, rectangle, algorithm, combinatorial geometry |
| Academic year of topic announcement: | 2013/2014 |
| Thesis type: | diploma thesis |
| Thesis language: | čeština |
| Department: | Computer Science Institute of Charles University (32-IUUK) |
| Supervisor: | doc. Mgr. Robert Šámal, Ph.D. |
| Author: | hidden - assigned and confirmed by the Study Dept. |
| Date of registration: | 30.09.2014 |
| Date of assignment: | 30.09.2014 |
| Confirmed by Study dept. on: | 06.10.2014 |
| Date and time of defence: | 11.02.2016 00:00 |
| Date of electronic submission: | 04.12.2015 |
| Date of submission of printed version: | 04.12.2015 |
| Date of proceeded defence: | 11.02.2016 |
| Opponents: | Mgr. Martin Mareš, Ph.D. |
| Guidelines |
| Cílem práce je posunout poznání v oblasti skládání geometrických útvarů do malých oblastí, v duchu tohoto problému:
je možné naskládat obdélníky rozměrů 1/n x 1/(n+1) (pro n=1, 2, ...) do čtverce 1x1? Obsah obdélníků je 1 a výsledky v článku [1] naznačují, že by to opravdu jít mohlo. V článku je navržen algoritmus, kterým lze obdélníky naskládat do čtverce o něco většího. Předmětem práce by mělo být prozkoumat tento algoritmus a pokusit se zlepšit jeho analýzu, a tím (v ideálním případě) problém vyřešit. Případně objevit, jaké podmínky skládání obdélníků omezují. V článku [1] jsou analyzovány dva další příbuzné problémy, student bude pracovat na libovolném z nich podle svého zájmu. |
| References |
| [1] Marc M. Paulhus: An Algorithm for Packing Squares, Journal of Combinatorial Theory, Series A 82, 147-157 (1997)
[2] Karen Ball: On Packing Unequal Squares, Journal of Combinatorial Theory, Series A 75, 353-357 (1996) Další literatura podle doporučení školitele. |