|
|
Structure and complexity of homomorphisms
Bok, Jan ; Nešetřil, Jaroslav (vedoucí práce)
Tato práce se zabývá výpočetními problémy okolo grafových homomorfismů a příbuz- ných konceptů. Především se zabýváme složitostními dichotomiemi, které rozlišují mezi polynomiálními a NP-úplnými problémy. Výsledky tohoto typu jsou velmi populární, a to jak díky klasickému výsledku Hella a Nešetřila, tak i díky nedávnému vyřešení hypotézy o dichotomii pro problémy s omezujícími podmínkami (CSP). Práce se dělí na tři části, jejichž společným pojítkem je cíl prozkoumat složitost a následně určit dichotomii různých problémů speciálních typů či zobecnění grafových ho- momorfismů. První část se zabývá signed grafy, kde dokazujeme složitostní dichotomii listové, do- sud nezkoumané varianty homomorfismu pro případ, že cílový graf je strom anebo graf tzv. cyklově- nebo cestově-separovatelný. Druhá část se zabývá problémem grafového na- krytí, který je známý jak v algebraické, tak v algoritmické teorii grafů. Tato část práce si klade za cíl rozšířit zkoumání složitosti na grafy s povolenými vícenásobnými hranami, smyčkami a s půlhranami. Zde zkoumáme (a) klasifikaci složitosti pro jednovrcholové a dvouvrcholové cíle, (b) jaká je správná definice grafového nakrytí pro nesouvislé cíle a (c) co se stane, když přidáme do problému listové podmínky. Poslední část se zabývá acyklickými barveními a složitostí hledání...
|
|
|
Structure and complexity of homomorphisms
Bok, Jan ; Nešetřil, Jaroslav (vedoucí práce) ; Golovach, Petr (oponent) ; Proskurowski, Andrzej (oponent)
Tato práce se zabývá výpočetními problémy okolo grafových homomorfismů a příbuz- ných konceptů. Především se zabýváme složitostními dichotomiemi, které rozlišují mezi polynomiálními a NP-úplnými problémy. Výsledky tohoto typu jsou velmi populární, a to jak díky klasickému výsledku Hella a Nešetřila, tak i díky nedávnému vyřešení hypotézy o dichotomii pro problémy s omezujícími podmínkami (CSP). Práce se dělí na tři části, jejichž společným pojítkem je cíl prozkoumat složitost a následně určit dichotomii různých problémů speciálních typů či zobecnění grafových ho- momorfismů. První část se zabývá signed grafy, kde dokazujeme složitostní dichotomii listové, do- sud nezkoumané varianty homomorfismu pro případ, že cílový graf je strom anebo graf tzv. cyklově- nebo cestově-separovatelný. Druhá část se zabývá problémem grafového na- krytí, který je známý jak v algebraické, tak v algoritmické teorii grafů. Tato část práce si klade za cíl rozšířit zkoumání složitosti na grafy s povolenými vícenásobnými hranami, smyčkami a s půlhranami. Zde zkoumáme (a) klasifikaci složitosti pro jednovrcholové a dvouvrcholové cíle, (b) jaká je správná definice grafového nakrytí pro nesouvislé cíle a (c) co se stane, když přidáme do problému listové podmínky. Poslední část se zabývá acyklickými barveními a složitostí hledání...
|
|
|
Cooperative games with partial information
Černý, Martin ; Bok, Jan (vedoucí práce)
(česky) 21. května 2021 Částečně definované kooperativní hry jsou zobecněným modelem klasických kooperativních her, ve kterém je známa hodnota pouze některých koalic. Proto se dá na tento model nahlížet jako na jeden z možných přístupů k modelování neurčitosti. Hlavním cílem této práce je shrnout a rozšířit existující výsledky této teorie. Práce obsahuje výsledky týkající se superaditivity, konvexity, pozitivity a 1- konvexity neúplných her. Pro všechny tyto vlastnosti studujeme popis množiny všech extenzí (úplných her rozšiřujících danou neúplnou hru). V rámci toho se soustředíme na několik tříd neúplných her. Mezi dalšími se jedná o neúplné hry s minimální informací, neúplné hry s definovaným horním vektorem nebo symetrické neúplné hry. Uvádíme i několik výsledků k obecným neúplným hrám. V rámci studia superaditivity a 1-konvexity definujeme a studujeme koncepty řešení (definované pouze na částečné informaci). Konkrétně pro 1-konvexitu na- bízíme rozsáhlou analýzu zadefinovaných konceptů, zahrnující několik ekviva- lentních charakterizací. 1
|
|
|
Cooperative games with partial information
Černý, Martin ; Bok, Jan (vedoucí práce) ; Zimmermann, Karel (oponent)
(česky) 21. května 2021 Částečně definované kooperativní hry jsou zobecněným modelem klasických kooperativních her, ve kterém je známa hodnota pouze některých koalic. Proto se dá na tento model nahlížet jako na jeden z možných přístupů k modelování neurčitosti. Hlavním cílem této práce je shrnout a rozšířit existující výsledky této teorie. Práce obsahuje výsledky týkající se superaditivity, konvexity, pozitivity a 1- konvexity neúplných her. Pro všechny tyto vlastnosti studujeme popis množiny všech extenzí (úplných her rozšiřujících danou neúplnou hru). V rámci toho se soustředíme na několik tříd neúplných her. Mezi dalšími se jedná o neúplné hry s minimální informací, neúplné hry s definovaným horním vektorem nebo symetrické neúplné hry. Uvádíme i několik výsledků k obecným neúplným hrám. V rámci studia superaditivity a 1-konvexity definujeme a studujeme koncepty řešení (definované pouze na částečné informaci). Konkrétně pro 1-konvexitu na- bízíme rozsáhlou analýzu zadefinovaných konceptů, zahrnující několik ekviva- lentních charakterizací. 1
|
|
|
Stuctural Aspects of Graph Homomorphisms
Bok, Jan ; Nešetřil, Jaroslav (vedoucí práce) ; Hubička, Jan (oponent)
Tato diplomová práce se zabývá náhodnými procházkami, Lipschitzovskými zobrazeními a grafovými homomorfismy. Diskutujeme propojení těchto pojmů, dáváme přehled dosavadních výsledků a ukazujeme nové výsledky. Grafový homomorfismus je zobrazení mezi dvěma grafy zachovávající sousednost. Hlavním předmětem zkoumání jsou pro nás homomorfismy grafů do nekonečných cest. Konkrétně nás zajímají dva parametry: maximální rozsah a průměrný rozsah. Průměrný rozsah grafu je očekávaná velikost obrazu uniformně a náhodně zvoleného homomorfismu do nekonečné cesty. Ukazujeme, jak odvodit vztahy pro výpočet průměrného rozsahu na různých třídách grafů a zabýváme se hlavními hypotézami, které se týkají tohoto parametru. Pro maximální rozsah ukazujeme přesný vztah a způsob výpočtu na obecném grafu. Kromě toho studujeme problém rozšiřování částečného homomorfismu, kde ukážeme jeho polynomialitu pro některé případy. 1
|
|
|
Cooperative interval games
Bok, Jan ; Hladík, Milan (vedoucí práce) ; Valla, Tomáš (oponent)
V této práci studujeme kooperativní intervalové hry, zobecněný model kooperativních her ve kterém hodnota každé koalice koresponduje s uzavřeným intervalem, reprezentujícím všechny možné výsledky jejich kooperace. Nejprve dáváme stručné úvody do klasické kooperativní teorie her a intervalové analýzy a následně uvádíme čtenáře do kooperativních intervalových her, a to se speciálním důrazem na selekce, což jsou všechny možné výsledky hry ve kterých už není žádná další neurčitost. Představujeme nové třídy her podle vlastností jejich selekcí a dokazujeme jejich charakterizace a vztahy s již existujícími třídami. Ukazujeme nové výsledky týkající se imputací a jader. Zavádíme definici silné imputace a silného jádra a zkoumáme problém rovnosti dvou různých typů jader -- hlavního stabilního řešení kooperativních intervalových her. Nakonec ukazujeme nová pozorování ohledně Shapleyho hodnoty intervalových her.
|
|
|
Phyllotactic Model Linking Nano and Macro World
Horáček, Miroslav ; Meluzín, Petr ; Krátký, Stanislav ; Urbánek, Michal ; Bok, Jan ; Kolařík, Vladimír
Recently, the arrangement of diffraction primitives according to a phyllotactic model was presented. This arrangement was used to benchmarking purposes of the e-beam writer nano patterning. The phyllotactic arrangement has several interesting properties. One of them is related with the coherence between the nanoor microscopic domain of individual optical primitives and the properties of visually perceived images crated by these structures in the macro domain. This paper presents theoretical analysis of the phyllotactic arrangement in the referred context. Different approaches enabling the creation of diffractive optically variable images are proposed. The practical part of the presented work deals with the nano patterning of such structures using two different types of the e-beam pattern generators. One of them is a system with a variable shaped beam of electrons, while the other one is a system with a Gaussian-shaped beam. E-beam writing strategies and the use of inherent spiral patterns for exposure ordering and partitioning are also discussed.
|
|
|
Large-area gray-scale structures in e-beam writer versus area current homogeneity and deflection uniformity
Kolařík, Vladimír ; Horáček, Miroslav ; Matějka, Milan ; Krátký, Stanislav ; Bok, Jan
The high stability and good current homogeneity in the spot of the e-beam writer is crucial to the exposure quality, particularly in the case of large-area structures when gray-scale lithography is used. Even though the deflection field distortion is calibrated regularly and beam focus and beam astigmatism is dynamically corrected over the entire deflection field,\nwe can observe disturbances in the exposed relief for both nowadays types of e-beam writers, the shaped e-beam writing system and the Gaussian e-beam writing system. A stable and homogeneous angular current density distribution in the spot is important especially in the case of shaped e-beam lithography systems. A non-homogeneity of the spot over deflection field is seen alongside the field boundaries of both lithography systems.
|
|
|
Structural Color of Metallic Surfaces
Kolařík, Vladimír ; Horáček, Miroslav ; Urbánek, Michal ; Matějka, Milan ; Krátký, Stanislav ; Chlumská, Jana ; Bok, Jan
Nano structuring of metallic surfaces shows surface colors unusual for a given material. This study presents an overview of possible approaches to achieve desirable color changes. The nano structured relief structures prepared by means of electron beam lithography process are presented. Optical design and simulation of optical properties, data preparation for e-beam patterning, parameters of the writing process, and technological issues are presented in detail. Finally, real examples of structures that exhibit surface color changes are presented and discussed.
|
|
|
Some Other Gratings: Benchmarks for Large-Area E-Beam Nanopatterning
Meluzín, Petr ; Horáček, Miroslav ; Urbánek, Michal ; Bok, Jan ; Krátký, Stanislav ; Matějka, Milan ; Chlumská, Jana ; Kolařík, Vladimír
E-beam lithography is a flexible technology for diffraction gratings origination. Nevertheless, requirements of the high optical quality of large area diffractive structures imply various severe challenges to e-beam delineating processes. This paper summarizes the e-beam process parameters that influence the quality of large area grating structures. Next, we propose some new methods to prepare diffraction gratings that were found to be useful for testing and benchmarking purposes. Those methods include single line gratings, labyrinth structures, fractional structures, tiling patterns, quasi regular filling structures and forked line structures. Various samples were prepared with the standard and newly developed e-beam patterning processes using both e-beam writers available: one with the Gaussian beam at 100 keV and another one with the shaped beam at 15 keV. Some of the results are presented further in this paper, their variants and parameters are discussed as well as their usefulness as benchmarking e-beam patterns for large area optical structures, elements and devices.
|
host ::
RSS.