|
|
Algoritmy pro Minkowského součet mnohoúhelníků
Šimek, Daniel ; Patáková, Zuzana (vedoucí práce) ; Příhoda, Pavel (oponent)
Tato bakalářská práce se zabývá Minkowského součtem dvou nekonvexních mnoho- úhelníků v rovině, konkrétně pak popisem a porovnáním dvou metod pro výpočet Min- kowského součtu: rozkladové metody a konvoluční metody. V této práci jsou obě tyto metody blíže představeny, včetně potřebných definic a ilustrativních obrázků. V závě- rečné kapitole jsou pak obě metody porovnány za pomoci C++ knihovny CGAL na různých vstupech. 1
|
|
|
MDS matice
Vlášková, Šárka ; Žemlička, Jan (vedoucí práce) ; Patáková, Zuzana (oponent)
MDS matice jsou hojně využívané v teorii kódování a v kryptografii (například v difuzních vrstvách blokových šifer či hashovacích funkcí), avšak konstrukce MDS matic není vůbec triviální, zvláště pokud po zkonstruované matici vyžadujeme i další vhodné vlastnosti (involučnost, efektivitu implementace). Proto se právě konstrukcí MDS ma- tic (s dalšími vlastnostmi) budeme v této práci zabývat. Postupně budeme konstruovat MDS matice pomocí Cauchyho matic a pomocí Vandermondových matic. Poté uvedeme algoritmus na testování, zda je daná matice MDS. A nakonec budeme konstruovat MDS matice pomocí Sériových matic, což je velmi výhodné pro lehkou kryptografii. 1
|
|
|
Hypertělesa a jejich aplikace v tropické geometrii či teorii matroidů
Andr, Břetislav ; Patáková, Zuzana (vedoucí práce) ; Šťovíček, Jan (oponent)
Hypertělesa jsou algebraickou strukturou zobecňující pojem algebraického tělesa. Na rozdíl od klasických těles, operace sčítání v hypertělese je mnohoznačná, tzn. výsledkem součtu dvou prvků není pouze jeden prvek, ale celá množina prvků. Hypertělesa nacházejí praktické využití v teorii matroidů a v tropické geometrii, odnoži algebraické geometrie. Matroid je algebraická struktura zobecňující pojem lineární nezávislosti. Existuje více typů matroidů rozšiřující základní definici matroidu, např. matroid orientovaný či valuo- vaný. Všechny tyto definice lze zastřešit pod jeden pojem tzv. F-matroidu, kde F zastává hypertěleso. Tropická geometrie se zabývá podobnými otázkami jako algebraická geo- metrie, pouze nad tzv. tropickým polotělesem. Díky své kombinatorické povaze nachází mnoho aplikací. Tropická geometrie a algebraická geometrie jsou úzce propojené pomocí tzv. Litvinovy-Maslovy dekvantizace a hypertělesa lze použít k popisu její zobecněné verze. 1
|
|
|
Hlídání galerie
Smolíková, Natálie ; Patáková, Zuzana (vedoucí práce) ; Žemlička, Jan (oponent)
V této práci se budeme zabývat klasickým problémem z výpočetní geometrie, a to problémem hlídání galerie, též známého pod anglickým názvem The Art Gallery Problem. Hlídání galerie se zabývá otázkou, jaký je nejmenší počet strážců, aby dohromady viděli celý půdorys galerie o n vrcholech. Hlavním cílem práce je nastudovat důkazy, že stačí ⌊n 3 ⌋ strážců v případě obecného polygonu a že stačí ⌊n 4 ⌋ strážců v případě ortogonálního polygonu. Náš důkaz ortogonální verze je oprava důkazu od Jorgeho Urrutii. Taktéž se zaměříme na optimalitu výsledků a na umístění strážců. 1
|
|
|
Nonassociativity in two operations
Lehká, Martina ; Drápal, Aleš (vedoucí práce) ; Patáková, Zuzana (oponent)
Tato práce navazuje především na výzkum Drápala a Valenta, kteří se zabývali neaso- ciativitou jedné kvazigrupové operace. Jejím hlavním cílem je zkoumat počet trojic (x, y, z) ∈ Q3 takových, že (x∗y)◦z = x∗(y ◦z), kde (Q, ∗) a (Q, ◦) jsou dvě kvazigrupy, |Q| = n. Nechť a2(C) je počet takových trojic v kvazigrupovém páru C. Toto číslo nazývejme index asociativity C. Označme a2(n) minimální a2(C), kde C je pár řádu n. Průměrováním indexu asociativity přes všechny hlavní izotopy kvazigrupového páru dokážeme, že a2(n) ≤ n2 (1 + 1/(n − 1)), n > 2. Poté charakterizujeme páry C, které v průměru dosahují a2(C) = n2 , a ukážeme, že tato hodnota je vylepšenou horní mezí pro a2(n), n > 2. Dále se věnujeme zkoumání párů kvazigrup izotopních grupám. Na závěr uvádíme výpočetní výsledky s příklady, včetně a2(4) = 8 a a2(5) = 9. 1
|
|
|
Problems in discrete geometry
Patáková, Zuzana ; Matoušek, Jiří (vedoucí práce) ; Bárány, Imre (oponent) ; Valtr, Pavel (oponent)
dizertační práce Problémy diskrétní geometrie Zuzana Patáková V této práci se věnujeme třem různým problémům z oblasti diskrétní geometrie. Společným pojítkem těchto problémů je, že jejich řešení využívá algebraické metody. První problém se zabývá tzv. polynomiální metodou, která konečnou množinu bodů rozdělí pomocí nulové množinu polynomu. Limitujícím fak- torem této metody je, co dělat s body, které leží v nulové množině získaného polynomu? V práci představujeme obecnou verzi, která řeší popsanou situaci, a jako aplikaci uvádíme nový algoritmus pro tzv. semialgebraický range searching problém. V druhé části práce se věnujeme studiu Ramseyových funkcí semialge- braických predikátů. Conlon, Fox, Pach, Sudakov a Suk zkonstruovali první příklady semialgebraických predikátů s Ramseyovou funkcí zespoda odhad- nutou věžovitou funkcí. My snížíme dimenzi příslušného prostoru v jejich konstrukci a jako důsledek ukážeme novou geometrickou větu Ramseyova typu s velkou Ramseyovou funkcí. V poslední části se zabýváme samodlážditelnými simplexy. Simplex S je k-samodlážditelný, pokud je sjednocením k navzájem shodných simplexů s disjunktními vnitřky, které jsou navíc podobné simplexu S. V...
|
|
|
The Helly numbers of systems of sets with bounded algebraic and topological complexity
Sosnovec, Jakub ; Tancer, Martin (vedoucí práce) ; Patáková, Zuzana (oponent)
Maehara dokázal, že je-li F systém alespoň d+3 sfér v Rd takový, že každých d+1 sfér z F má neprázdný průnik, pak celý systém F má neprázdný průnik. V této práci rozšiřujeme jeho výsledek Hellyho typu ve dvou směrech. Nejprve ukážeme platnost analogické věty pro systémy pseudosfér, tedy systémy množin splňující, že průnik každého neprázdného podsystému je homeomorfní sféře nějaké dimenze nebo je prázdný. Dále využijeme toho, že sféru v Rd lze vyjádřit jako nulovou množinu reálného polynomu. Je-li P množina polynomů, pak Hellyho číslo systému nulových množin polynomů z P je omezeno dimenzí vektorového prostoru generovaného P. Pro systémy sfér ovšem Maeharův výsledek dává silnější odhad. Ukážeme některé obecné postačující podmínky pro lepší odhad Hellyho čísel v tomto kontextu. Powered by TCPDF (www.tcpdf.org)
|
|
|
Deriving a pseudomanifold of dimension 3 from nonassociative triples
Spišák, Martin ; Drápal, Aleš (vedoucí práce) ; Patáková, Zuzana (oponent)
Neasociativita kvázigrúp je užitočná vlastnosť pre kryptografiu. A. Drápal and I. M. Wanless vo svojej nedávnej práci študovali existenciu maximálne neasociatı́vnych kvázigrúp, no táto otázka ostáva pre niektoré rády nezopove- daná. Táto práca je úvodom do novej metódy riešenia tejto otázky. Po rekapitulácii najnovšı́ch zistenı́ a naznačenı́ využitia v kryptografii vyložı́ práca konštrukciu abstraktného simpliciálneho komplexu dimenzie 3 z neasociatı́vnych trojı́c konečnej kvázigrupy. Ukážeme, že tento komplex má formu zjednotenia uzavretých orientovateľných pseudovariet dimenzie 3. Pre rády do 6 nezávisle overı́me zistenia Ježka and Kepku o spektre asociati- vity a klasifikujeme možné rozklady komplexu neasociativity na silne súvislé komponenty analýzou ich duálnych grafov. Hlavným výsledok práce je prvý krok k riešeniu singuları́t v komplexe neasociativity. Ukážeme, že linky vrcholov v komplexe majú riešiteľné sin- gularity, čo nám umožnı́ normalizovať ich algoritmicky. Nakoniec spočı́tame rody komponent v linkoch a ilustrujeme typy linkov na prı́kladoch malých kvázigrúp. 1
|
|
|
Problems in discrete geometry
Patáková, Zuzana ; Matoušek, Jiří (vedoucí práce) ; Bárány, Imre (oponent) ; Valtr, Pavel (oponent)
dizertační práce Problémy diskrétní geometrie Zuzana Patáková V této práci se věnujeme třem různým problémům z oblasti diskrétní geometrie. Společným pojítkem těchto problémů je, že jejich řešení využívá algebraické metody. První problém se zabývá tzv. polynomiální metodou, která konečnou množinu bodů rozdělí pomocí nulové množinu polynomu. Limitujícím fak- torem této metody je, co dělat s body, které leží v nulové množině získaného polynomu? V práci představujeme obecnou verzi, která řeší popsanou situaci, a jako aplikaci uvádíme nový algoritmus pro tzv. semialgebraický range searching problém. V druhé části práce se věnujeme studiu Ramseyových funkcí semialge- braických predikátů. Conlon, Fox, Pach, Sudakov a Suk zkonstruovali první příklady semialgebraických predikátů s Ramseyovou funkcí zespoda odhad- nutou věžovitou funkcí. My snížíme dimenzi příslušného prostoru v jejich konstrukci a jako důsledek ukážeme novou geometrickou větu Ramseyova typu s velkou Ramseyovou funkcí. V poslední části se zabýváme samodlážditelnými simplexy. Simplex S je k-samodlážditelný, pokud je sjednocením k navzájem shodných simplexů s disjunktními vnitřky, které jsou navíc podobné simplexu S. V...
|
|
|
The Helly numbers of systems of sets with bounded algebraic and topological complexity
Sosnovec, Jakub ; Tancer, Martin (vedoucí práce) ; Patáková, Zuzana (oponent)
Maehara dokázal, že je-li F systém alespoň d+3 sfér v Rd takový, že každých d+1 sfér z F má neprázdný průnik, pak celý systém F má neprázdný průnik. V této práci rozšiřujeme jeho výsledek Hellyho typu ve dvou směrech. Nejprve ukážeme platnost analogické věty pro systémy pseudosfér, tedy systémy množin splňující, že průnik každého neprázdného podsystému je homeomorfní sféře nějaké dimenze nebo je prázdný. Dále využijeme toho, že sféru v Rd lze vyjádřit jako nulovou množinu reálného polynomu. Je-li P množina polynomů, pak Hellyho číslo systému nulových množin polynomů z P je omezeno dimenzí vektorového prostoru generovaného P. Pro systémy sfér ovšem Maeharův výsledek dává silnější odhad. Ukážeme některé obecné postačující podmínky pro lepší odhad Hellyho čísel v tomto kontextu. Powered by TCPDF (www.tcpdf.org)
|
host ::
RSS.