V sobotu dne 19. 10. 2024 dojde k odstávce některých součástí informačního systému. Nedostupná bude zejména práce se soubory v modulech závěrečných prací. Svoje požadavky, prosím, odložte na pozdější dobu. |
Hlídání galerie
Název práce v češtině: | Hlídání galerie |
---|---|
Název v anglickém jazyce: | Art gallery problem |
Klíčová slova: | galerie|triangulace|ortogonální polygon|polygon|strážci |
Klíčová slova anglicky: | art gallery|triangulation|orthogonal polygon|polygon|guards |
Akademický rok vypsání: | 2022/2023 |
Typ práce: | bakalářská práce |
Jazyk práce: | čeština |
Ústav: | Katedra algebry (32-KA) |
Vedoucí / školitel: | RNDr. Zuzana Patáková, Ph.D. |
Řešitel: | Bc. Natálie Smolíková - zadáno a potvrzeno stud. odd. |
Datum přihlášení: | 19.03.2023 |
Datum zadání: | 11.04.2023 |
Datum potvrzení stud. oddělením: | 21.04.2023 |
Datum a čas obhajoby: | 21.06.2023 10:00 |
Datum odevzdání elektronické podoby: | 08.05.2023 |
Datum odevzdání tištěné podoby: | 15.05.2023 |
Datum proběhlé obhajoby: | 21.06.2023 |
Oponenti: | doc. Mgr. et Mgr. Jan Žemlička, Ph.D. |
Zásady pro vypracování |
Art gallery problém se zabývá jednoduchou otázkou, jaký je nejmenší počet strážců, kteří dohromady uvidí celou galerii? Jde o klasický problém z výpočetní geometrie s praktickým využitím například v robotice.
V práci se omezíme na galerie s n stěnami, kde půdorys je mnohoúhelník. Ví se, že vždy stačí nejvýše n/3 strážců. V případě, že jsou všechny stěny navzájem ortogonální, lze počet strážců snížit na n/4. Cílem práce je oba tyto důkazy nastudovat a srozumitelně vysvětlit, včetně jejich optimality. Studentka se bude rovněž zabývat otázkou, jak moc situaci ovlivňuje omezení na rozmístění strážců (pouze ve vrcholech x na hranách x kdekoli). |
Seznam odborné literatury |
V. Chvátal: A combinatorial theorem in plane geometry, Journal of Combinatorial Theory, Series B, volume 18, 39-41, 1975
S. Fisk: A short proof of Chvátal’s watchman theorem, Journal of Combinatorial Theory, Series B, volume 24, page 374, 1978 J. Kahn, M. Klawe, D. Kleitman: Traditional galleries require fewer watchmen, SIAM J. Algebr. Discrete Methods, 4(2): 194–206, 1983 J. O'Rourke: Art Gallery Theorems and Algorithms, Oxford University Press, 1987 J. Urrutia: Sixth proof of the Orthogonal Art Gallery problem, Technical report TR-97-03, Department of Computer Science, University of Ottawa, 1997 |