|
|
Konstrukce modelů pomocí CSP
Peterová, Alena ; Stanovský, David (vedoucí práce) ; Kazda, Alexandr (oponent)
V této práci se věnujeme algoritmům na konstrukci konečných modelů pro množiny axiomů logiky 1. řádu s cílem navrhnout a implementovat novou metodu, založenou na převodu na problém splnitelnosti omezení (CSP). V teoretické části představíme standardní metodu MACE, používající převod úloh na SAT, a pokročilejší techniky zvyšující její efektivitu: dělení klauzulí, definici termů a statickou redukci symetrií. Následuje návrh alternativní metody, která podobným způsobem převádí úlohy na CSP. Nově navrhujeme techniku redukce symetrií i pro binární funkce. Poté popíšeme implementaci alternativní metody pomocí CSP-modelovacího jazyka MiniZinc a CSP-solveru Gecode. Na závěr porovnáme výkonnost vytvořeného nástroje na hledání modelů s nejúspěšnějšími zástupci standardních metod, systémy Paradox a Mace4.
|
|
|
Topological properties of algebraic curves
Hudec, Pavel ; Šťovíček, Jan (vedoucí práce) ; Kazda, Alexandr (oponent)
Tato práce si klade za cíl představit teorii o algebraických křivkách nad komplexními čísly z topologického pohledu. Hlavním výsledkem dokázaným v práci je klasická věta zvaná degree-genus formula, která tvrdí, že v projektivním případě jsou nesingulární algebraické křivky kompaktní plochy, jejichž rod závisí pouze na stupni dané křivky. Předložený důkaz je do značné míry založený na algebraické topologii. Ukážeme, že křivka působí jako nakrývající prostor pro projektivní přímku (bez konečné množiny obrazů ramifikovaných bodů), pak zvedneme vhodnou triangulaci projektivní přímky na danou křivku. Později zjistíme, jak náš výsledek souvisí s populární definicí rodu jako počtu uší připojených ke sféře. Nakonec krátce projdeme singulární křivky, kde ukážeme, že obecně na ně nelze větu degree-genus formula aplikovat. 1
|
|
|
Symbolické reprezentace kompaktních prostorů
Kazda, Alexandr
Název práce: Symbolické reprezentace kompaktních prostorů Autor: Alexandr Kazda Katedra (ústav): Katedra algebry Vedoucí diplomové práce: prof. RNDr. Petr Kůrka, CSc. E-mail vedoucího: kurka@cts.cuni.cz Abstrakt: Práce se zabývá reprezentací čísel pomocí möbiovských číselných systé- mů. Tyto systémy reprezentují body pomocí posloupností Möbiových transformací. V práci se věnujeme převážně reprezentacím jednotkové kružnice (které jsou ekvi- valentní reprezentacím množiny R ∪ {∞}). Zaměřujeme se především na vylepšování již známých nástrojů pro dokazovaní, že daný posun je möbiovským číselným systémem pro daný möbiovský iterativní systém. Dále studujeme otázku, jak charakterizovat iterativní systémy, pro které existuje posun tvořící möbiovský číselný systém, a naopak, jak popsat posuny, pro které lze najít iterativní systém, že výsledná dvojice je möbiovský číselný systém. Úplnou charakterizaci se nám nepodařilo najít, avšak nabízíme několik pozitivních i negativních částečných výsledků. Krátce se také věnujeme otázce, kdy je daný möbiovský číselný systém sofickým posunem.
|
|
|
Komplexní algebraické křivky
Zvěřina, Adam ; Šťovíček, Jan (vedoucí práce) ; Kazda, Alexandr (oponent)
Práce popisuje vztah mezi algebraickými křivkami a Riemannovými plochami. Za- vedeme Weierstrassovu ℘-funkci a dokážeme některé její vlastnosti. Dále nahlédneme, že každou komplexní algebraickou křivku lze chápat jako Riemannovu plochu. Nakonec ukážeme, že eliptickou křivku lze parametrizovat pomocí Weierstrassovy ℘-funkce. 1
|
|
|
Logic circuits as models of computation
Naumenko, Mykhailo ; Kazda, Alexandr (vedoucí práce) ; Kompatscher, Michael (oponent)
Tato práce se zaměřuje na studium logických obvodů. Vykládáme v ní teorii logických obvodů podle učebnice "Models of Computation" od Johna E. Savage a řešíme některé úlohy a cvičení z této učebnice. V této práci najdete klíčové pojmy související s logickými obvody. Věnovali jsme znač- nou pozornost hlavně odhadům dolních mezí velikostí obvodů a velikostí formulí obecných booleovských funkcí. Sestrojili jsme také několik jednoduchých příkladů známých obvodů a ukázali jsme, jak lze navrhnout další obvody. 1
|
|
|
Minimální pokrytí párů trojicemi
Hladíková, Veronika ; Krump, Lukáš (vedoucí práce) ; Kazda, Alexandr (oponent)
Práce je řešením kombinatorického problému, kdy pro danou konečnou množinu A hledáme minimální množinu trojic prvků z A, neboli minimální A-pokrytí, tak, aby každá dvojice prvků byla obsažena v některé trojici. Spočítáme, jak velké toto pokrytí musí být v závislosti na velikosti A, a ukážeme více způsobů, jak takové minimální množiny trojic zkonstruovat. Dále je k práci přiložený program, který umí vygenerovat A-pokrytí pro danou množinu. 1
|
|
|
Image reconstruction using graphical models
Ficová, Klára ; Kazda, Alexandr (vedoucí práce) ; Bulín, Jakub (oponent)
Grafické modely slúžia na reprezentáciu pravdepodobnostných vzťahov medzi náhodnými veličinami pomocou grafu . Ponúkajú dobrý spôsob na vyjadrenie reálnych situácií a preto sa často využívajú v strojovom učení a štatistickom uvažovaní. Cieľom práce je popísať a implementovať spôsoby, ako grafickým mo- delom odstrániť z obrazu šum. Za grafický model zvolíme faktorgraf, v ktorom reprezentujeme ako vrcholy pixely v obraze a interakcie medzi nimi. Pomocou algoritmov popísaných na grafe budeme hľadať najpravdepodobnejší pôvodný obraz. Bližšie sa budeme venovať algoritmu belief propagation, ktorý je založený na vzájomnom posielaní správ medzi susednými vrcholmi. Teoretické metódy aplikujeme na obrazy so šumom a porovnáme výsledky. 1
|
|
|
Properties of delta-matroids
Šíma, Lucien ; Kazda, Alexandr (vedoucí práce) ; Rolínek, Michal (oponent)
We investigate delta-matroids which are formed by families of subsets of a finite ground set such that the exchange axiom is satisfied. We deal with some natural classes of delta-matroids. The main result of this thesis establishes sev- eral relations between even, linear, and matching-realizable delta-matroids. Fol- lowing up on the ideas due to Geelena, Iwatab, and Murota [2003], and apply- ing the properties of field extensions from algebra, we prove that the class of strictly matching-realizable delta-matroids, the subclass of matching-realizable delta-matroids, is included in the class of linear delta-matroids. We also show that not every linear delta-matroid is matching-realizable by giving a skew-symmetric matrix representation to the non matching-realizable delta-matroid constructed by Kazda, Kolmogorov, and Rol'ınek [2019].
|
|
|
Prezentace podgrup
Jakubec, Tomáš ; Růžička, Pavel (vedoucí práce) ; Kazda, Alexandr (oponent)
Tato bakalářská práce ukazuje, jak vytvořit prezentaci podgrupy, když známe prezentaci původní grupy. K tomu využívá tzv. Reidemeister-Schreierovu metodu. V textu se nejdříve definuje pojem prezentace grupy a ukáže se, jak z prezentace získat zpětně grupu isomorfní původní grupě a jak se dá prezen- tace grupy upravovat, aniž by se změnilo, jakou grupu prezentuje. Následně se na základě prezentace grupy najde prezentace podgrupy, která se však v praxi nedá efektivně použít. Ta se potom zjednoduší pomocí Reidemeisterovy věty a Schreierovy věty vhodnou volbou generujících prvků podgrupy. Součástí práce jsou také řešené příklady na použití Reidemeister-Schreierovy metody. Text je určen hlavně jako studijní pomůcka pro studenty kombinatorické teorie grup. 1
|
|
| |
host ::
RSS.