Skládání obdélníků

• Název práce v češtině: Skládání obdélníků
• Název v anglickém jazyce: Packing rectangles
• Klíčová slova: skládání, obdélník, algoritmus, kombinatorická geometrie
• Klíčová slova anglicky: packing, rectangle, algorithm, combinatorial geometry
• Akademický rok vypsání: 2013/2014
• Typ práce: diplomová práce
• Jazyk práce: čeština
• Ústav: Informatický ústav Univerzity Karlovy (32-IUUK)
• Vedoucí / školitel: doc. Mgr. Robert Šámal, Ph.D.
• Řešitel: skrytý - zadáno a potvrzeno stud. odd.
• Datum přihlášení: 30.09.2014
• Datum zadání: 30.09.2014
• Datum potvrzení stud. oddělením: 06.10.2014
• Datum a čas obhajoby: 11.02.2016 00:00
• Datum odevzdání elektronické podoby: 04.12.2015
• Datum odevzdání tištěné podoby: 04.12.2015
• Datum proběhlé obhajoby: 11.02.2016
• Oponenti: Mgr. Martin Mareš, Ph.D.

Zásady pro vypracování

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.

Seznam odborné literatury

[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.