|
|
O nemožnosti elementární integrace
Zelina, Michael ; Pražák, Dalibor (vedoucí práce) ; Kazda, Alexandr (oponent)
Předložená práce je věnována studiu problému (ne)existence elementární primitivní funkce k zadané funkci. V prvé řadě zavedeme strukturu diferenciálního tělesa a na- jdeme vhodný způsob formalizování pojmu elementární funkce. S tímto aparátem se nám otevře možnost formulovat a dokázat klíčovou větu říkající, v jakém tvaru musí nutně být elementární primitivní funkce, jestliže taková existuje. Následně s její po- mocí nalezneme podmínky pro existenci elementárních integrálů ze dvou funkcí v jis- tém speciálním, ale přesto dosti obecném tvaru. Jejich konkrétní aplikací prokážeme neelementárnost celé řady více či méně známých integrálů. 3
|
|
|
Bezpečnost šifrování zpráv závisejících na klíči
Hostáková, Kristina ; Hojsík, Michal (vedoucí práce) ; Kazda, Alexandr (oponent)
V této práci se zabýváme šifrovacími schématy, která jsou dokazatelně bez- pečná i v případě, kdy šifrujeme zprávy, které závisejí na tajném klíči. Taková schémata nazýváme KDM-bezpečná. Nejprve zavádíme pojem KDM-bezpečnosti obecně a zkoumáme jeho vztah s jinými druhy bezpečnosti, zejména s IND-CPA-bezpečností. Poté popisujeme asymetrické i symetrické šifrovací schéma autorů Applebaum et al. (CRYPTO 2009) a dokazujeme KDM-bezpečnost těchto schémat s ohledem na množinu afinních funkcí. Klíčovým předpokladem bezpečnosti sestrojených schémat je těžkost pro- blému LWE, respektive jeho speciálního případu LPN. Tyto problémy blíže zkoumáme a rozebíráme jejich varianty. Dále se věnujeme i mřížkám a těžkým problémům na mřížkách, protože se redukují na problém LWE. 1
|
|
|
Homomorfní šifrovací schémata
Titěrová, Anežka ; Kazda, Alexandr (vedoucí práce) ; Hojsík, Michal (oponent)
Název práce: Homomorfní šifrovací schémata Autor: Anežka Titěrová Katedra: Katedra algebry Vedoucí bakalářské práce: RNDr. Alexandr Kazda, Katedra algebry Abstrakt: V roce 1978 publikoval Rivest a kol. kryptografický problém, jak počítat libovolné funkce nad zašifrovanými daty, aniž by bylo nutné data dešifrovat. Tento problém lze vyřešit použitím plně homomorfního schématu, které objevil a jako první popsal Craig Gentry v roce 2009. Tato práce shrnuje současné znalosti v oblasti homomorfního šifrování. Sou- středíme se zejména na obecný přehled se zaměřením na bezpečnost sché- matu. Získané znalosti aplikujeme v počítačové implementaci částečně ho- momorfního šifrovacího schématu. Plně homomorfní schéma může být využito v mnoha aplikacích, například v implementacích bezpečného cloud-computingu. Nicméně zbývá mnoho prá- ce v oblasti konstrukce dostatečně efektivního algoritmu, poněvadž dosud známé implementace nejsou tak rychlé, aby mohly být použity v každodenní komunikaci. Klíčová slova: homomorfní šifry, plně homomorfní šifrovací schéma, krypto- grafie na mřížkách, logický obvod
|
|
|
Constraint Satisfaction Problem and Universal Algebra
Kazda, Alexandr ; Barto, Libor (vedoucí práce) ; Růžička, Pavel (oponent) ; Valeriote, Matt (oponent)
Práce sestává ze souboru mých příspěvků v oblasti univerzální algebry. Naší hlavní oblastí zájmu jsou algebry polymorfismů relačních struktur, motivací pak především složitost problému splnitelnosti omezení (CSP). Nejprve ukážeme pomocí univerzální algebry (a stopového množství analýzy), že CSP náhodné relační struktury je skoro jistě NP-úplný. Pokračujeme studiem orientovaných grafů, které mají Mal'cevův polymorfismus. Ukážeme, že takové grafy už nutně musí mít majoritu. Dále pak demonstrujeme použití techniky absorpce: Přinášíme nový důkaz faktu, že kongruenčně modulární reflexivní ori- entované grafy mají vždy NU polymorfismus. Na závěr práce prezentujeme alge- braický důkaz výsledku (poprvé dokázaného kombinatoriky), že 3-konzervativní relační struktury s nejvýše binárními relacemi se vyznačují jednoduchou dicho- tomií: Jejich CSP je bud' NP-úplné, nebo je lze řešit pomocí metody lokální konzistence. 1
|
|
|
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.
|
|
| |
|
|
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.
|
|
| |
|
| |
|
| |
host ::
RSS.