|
|
Extremal Polyominoes
Steffanová, Veronika ; Valtr, Pavel (vedoucí práce) ; Cibulka, Josef (oponent)
Název práce: Extremal Polyominoes Autor: Veronika Steffanová Katedra: Katedra aplikované matematiky Vedoucí diplomové práce: Doc. RNDr. Pavel Valtr, Dr. Abstrakt: Práce se zabývá tématem polymin a dalších rovinných obrazců, které se skládají z pravidelných mnohoúhelníků, konkrétně polyiamondů a polyhexů. Zaměřili jsme se na základní geometrické vlastnosti: obvod, kon- vexní obal a ohraničující čtverec/šestiúhelník. Tyto parametry minimal- izujeme nebo maximalizujeme pro pevně danou velikost polymina, kterou značíme jako n. Vzhledem k n odvozujeme vzorec pro maximální a minimální hodnoty zvoleného parametru a také se snažíme vyjmenovat všechna polymina, která tohoto maxima dosahují. Některé problémy už byly vyřešeny dříve jinými autory a my přinášíme shrnutí jejich výsledků. Jiné jsme vyřešili my, jmenovitě problém maximálního ohraničujícího čtverce/šestiúhelníku a maximálního konvexního obalu pro polyiamondy. Některé otázky zůstávají i nadále otevřeny a my nabízíme alespoň pozorování, která mohou posloužit v dalším výzkumu. Klíčová slova: Polymino, konvexní obal, extremální otázky, rovina 1
|
|
|
Softwarový balík pro práci s polyedry
Steffanová, Veronika ; Hladík, Milan (vedoucí práce) ; Cibulka, Josef (oponent)
Název práce: Softwarový balík pro práci s polyedry Autor: Veronika Steffanová Katedra: Katedra aplikované matematiky Vedoucí bakalářské práce: Mgr. Milan Hladík, Ph.D., Katedra aplikované matema- tiky Abstrakt: V práci jsme se zaměřili na téma polyedrů a základních algoritmů pro práci s nimi. Nejdříve je předložena věta o ekvivalenci vrcholové a nerovnicové reprezen- tace a poté jsou popsány vybrané algoritmy, které řeší jejich vzájemný převod. Prak- tická část se pak týká implementace tří funkcí založených na zvolených algoritmech a několika dalších, které jsou jejich přímým důsledkem. Výsledkem je knihovna funkcí pro MATLAB, která obsahuje nástroje pro převod mezi jednotlivými reprezentacemi, konvexní sjednocení dvou polyedrů, průnik dvou polyedrů a odstranění redundantních vrcholů (resp. nerovnic) z vrcholové (resp. nerovnicové) reprezentace. Kromě toho jsme porovnali dva námi implementované algoritmy pro převod z vrcholové do ne- rovnicové reprezentace, a to jak z hlediska časové, tak i prostorové a implementační náročnosti. Klíčová slova: polyedr, MATLAB, lineární programování, konvexní obal 1
|
host ::
RSS.