|
|
Distinguishing pairs of words using finite automata
Bilan, Daria ; Koucký, Michal (vedoucí práce) ; Šámal, Robert (oponent)
V této práci se zaměřujeme na jeden ze základních otevřených problémů v in- formatice - rozlišování dvou slov pomocí deterministického konečného automatu s co nejmenším počtem stavů. Nejprve představíme existující výzkum, kde se prokázané dolní a horní meze vzhledem k délce slov liší exponenciálně. Následně empiricky zkoušíme dva dosud neprozkoumané přístupy: analýzu rozlišujících množin a použití náhodně generovaných automatů. Ukážeme, že první přístup nepřispívá ke zlepšení mezí pro daný problém, zatímco náhodné automaty mo- hou být úspěšné pro náhodně vybrané páry slov, avšak ne pro všechny. Kom- binace náhodně generovaného automatu s již známým nenáhodným přístupem však pomáhá snížit průměrný počet stavů o několik řádů. Na základě získaných experimentálních výsledků navrhujeme několik témat pro další výzkum. 1
|
|
|
Výskyt hlavních porodnických komplikací u žen s primární trombofilií ve srovnání s kontrolní skupinou žen
Pechrová, Viktorie ; Koucký, Michal (vedoucí práce) ; Čábela, Radek (oponent)
Leidenská mutace a mutace protrombinu se řadí mezi primární trombofilní onemocnění postihující faktory hemokoagulační vnitřní kaskády krve. Vyšší incidenci zaznamenáváme spíše u europoidní rasy. Tato onemocnění označujeme nejen jako rizikové faktory tromboembolických onemocnění, ale též jako rizikové faktory některých porodnických komplikací. Tato bakalářská práce shrnuje teoretické znalosti o Leidenské mutaci a mutaci protrombinu. Následně se věnuje porodnickým komplikacím, které se v souvislosti s těmito trombofilními mutacemi objevují. Výzkumná část práce se zabývá souvislostí zmíněných mutací a vyššího výskytu habituálních potratů. Tedy, zda ženy, které některou z těchto vrozených trombofilií mají, mají častější historii dvou a více spontánních potratů, oproti ženám, kterým tato mutace diagnostikována nebyl. Na počátku jsem určila hypotézu, že u žen s vrozenou trombofilií je oproti v kontrolní skupině žen bez trombofilie, vyšší výskyt habituálních potratů. Ověření hypotézy probíhalo přes retrospektivní procházení databáze Ústavu lékařské diagnostiky a biochemie Všeobecné fakultní nemocnice v Praze a 1. lékařské fakulty Univerzity Karlovy, kde byla sestavena výzkumná skupina z žen, kterým byla primární trombofilie potvrzena. Kontrolní skupina pak byla sestavena z žen rodících v březnu 2023 v...
|
|
|
Complexity of dynamic data structures
Král, Karel ; Koucký, Michal (vedoucí práce) ; Drucker, Andrew (oponent) ; Ishai, Yuval (oponent)
Třídění je jedním z fundamentálních problémů informatiky. V této práci prezentujeme tři výsledky. Asymptoticky optimální třídící sítě byly popsány v článku Ajtai a kol. [1983]. Ale Asharov a kol. [2021] ukázali, že booleovské obvody vytvořené z třídících sítí nejsou optimální pro třídění krátkých celých čísel. My ukazujeme konstrukci ještě menších obvodů pro třídění krátkých celých čísel. Dolní odhady pro offline Oblivious RAM byly spojeny s dolními odhady pro třídící booleovské obvody v článku Boyle a Naor [2016]. Larsen a Nielsen [2018] ukázali dolní odhad pro online Oblivious RAM. My ukazujeme dolní odhad pro online Oblivious RAM v obecnějším modelu. Nakonec ukazujeme algoritmus se střední dobou běhu O(n log log(n)) pro třídění celých čísel na RAM s délkou slov mezi log(n) a log(n) na třetí. Tento algoritmus ne- dosahuje střední doby běhu algoritmu z článku Han a Thorup [2002], ale náš algoritmus je mnohem jednodušší na implementaci i analýzu. 1
|
|
|
Limits of Data Structures, Communication, and Cards
Dvořák, Pavel ; Koucký, Michal (vedoucí práce) ; Hansen, Kristoffer Arnsfelt (oponent) ; Chakrabarti, Amit (oponent)
Limity datových struktur, komunikace a karet - abstrakt V této práci studujeme několik aspektů výpočetní složitosti. Jedno z hlavních témat je složitost datových struktur, což jsou algoritmy pro efektivní ukládání dat podporující efektivní dotazy na daná data. Dynamické datové struktury také umožňují měnit data před dotazem. Dlouho otevřený problém v této oblasti je dokázat nepodmíněný polynomiální dolní odhad na porovnání času na editaci a času na dotaz adaptivní dynamické struktury počítající nějakou explicitní funkci. Ukazujeme nepodmíněný polynomiální dolní odhad pro omezenou třídu semi-adaptivních dy- namických datových struktur počítající funkce s velkou korupční mezí, což zobecňuje výsledek od Ko a Weinsteina [FOCS '20], kteří ukázali takový dolní odhad pro datové struktury počítající funkci disjunkce. Dále ukazujeme podmíněný dolní odhad pro určité statické datové struktury počítající inverzi permutací, a vyhodnocení a interpolaci polynomů. Tyto dolní odhady jsou lepší než nejlepší známé nepodmíněné dolní odhady pro dané problémy. Dále studujeme komunikační složitost eliminačního problému, který je velmi blízký problému přímého součtu. U eliminačního problému, Alenka a...
|
|
|
Ošetřovatelská péče o ženu s preeklampsií, perinatologické výsledky ve vztahu k hladinám kreatininu v mateřské krvi
Šmejkalová, Tereza ; Koucký, Michal (vedoucí práce) ; Čábela, Radek (oponent)
Preeklampsie (PE) je závažné multiorgánové onemocnění komplikující těhotenství. Celosvětově se vyskytuje u 2-8 % gravidit a přibližně 50 000 žen ročně umírá na její následky. Tato bakalářská práce shrnuje teoretické znalosti o PE - konkrétně etiopatogenezi, klasifikaci a symptomy onemocnění, management léčby, pravděpodobné komplikace a další aspekty, které jsou důležité v rámci ošetřovatelské péče. Výzkumná část práce se zabývá využitím hladin sérového kreatininu (S-kreatininu) k určení závažnosti stavu pacientky a pravděpodobných následků pro plod. Hlavním cílem bakalářské práce je zjistit korelaci mezi hladinou S-kreatininu matky před porodem a perinatologickými výsledky. Dílčím cílem je sledování hladiny sérové urey (S-urey) ve vztahu k délce těhotenství. Naší hypotézou bylo, že se vzrůstající hladinou S-kreatininu matky před porodem se zkracuje délka těhotenství, klesá porodní váha novorozence, zhoršuje se poporodní adaptace a prodlužuje se délka hospitalizace matky. Pro realizaci výzkumu byla retrospektivně získávána data těhotných žen s diagnózou PE, které porodily v roce 2020 na Gynekologicko-porodnické klinice 1. LF UK a VFN v Praze. Ze sledovaných dat jsme vypozorovali, že vysoká hladina S-kreatininu negativně koreluje s délkou trvání gestace, s porodní váhou novorozence a hodnotou APGAR...
|
|
|
DPLL algorithm and propositional proofs
Hrnčiar, Maroš ; Krajíček, Jan (vedoucí práce) ; Koucký, Michal (oponent)
Dôkazová zložitosť je zaujímavá súčasť matematiky nachádzajúca sa na pomedzí obrovskej oblasti logiky a teórie zložitosti. Skúma aké dôkazové systémy sú potrebné na efektívne dokazovanie rôznych matematických tvrdení. Predmetom tejto práce je spojenie medzi dôkazovými systémami a algoritmami na SAT. Uvidíme, že beh algoritmu na nesplniteľnej formule môže byť nahliadnutý ako výrokový dôkaz jej nesplniteľnosti, čím samotný algoritmus prakticky definuje celý dôkazový systém. Práca je určená najmä čitateľom so záujmom o dôkazovú zložitosť, ale dokáže aj samostatne objasniť princíp rezolúcie, či ponúknuť menej obvyklý pohľad na SAT, no zároveň predpokladá čitateľovu znalosť základov výrokovej logiky, teórie grafov a zložitosti.
|
|
| |
|
|
The Online Labeling Problem
Bulánek, Jan ; Koucký, Michal (vedoucí práce) ; Brodal, Gerth (oponent) ; Iacono, John (oponent)
Setříděné pole je zásadní algoritmický koncept, jehož online varianta je základem pro problém online labelingu. Problém online labelingu je definován následovně. Vstupem je pole velikosti m a posloupnost celých čísel z universa {1,...,r} v libovolném pořadí délky n. Naším úkolem je udržovat všechna přijatá čísla setříděná v poli. Mezi vloženými čísly mohou být mezery. Protože závěrečné pořadí čísel nelze určit, dokud nejsou vložena všechna, je povoleno čísla v poli přesouvat. Cílem je minimalizovat počet přesunů. Ukážeme dva algoritmy, které společně poskytují optimální řešení pro téměř všechny hodnoty m coby funkce n. Dokážeme těsné dolní odhady pro téměř všechny hodnoty m. Zavedeme notaci omezeného universa vstupní množiny čísel a dokážeme dolní odhady i pro tuto variantu. Dokážeme dolní odhady i pro případ randomizovaných algoritmů. Powered by TCPDF (www.tcpdf.org)
|
|
|
Functional Data Stuctures and Algorithms
Straka, Milan ; Dvořák, Zdeněk (vedoucí práce) ; Koucký, Michal (oponent) ; Brodal, Gerth (oponent)
Název práce: Funkcionální datové struktury a algoritmy Autor: Milan Straka Ústav: Informatický ústav Univerzity Karlovy Vedoucí doktorské práce: doc. Mgr. Zdeněk Dvořák, Ph.D, Informatický ústav Univerzity Karlovy Abstrakt: Funkcionální programování je rozšířené a stále více oblíbené programo- vací paradigma, které nachází své uplatnění i v průmyslových aplikacích. Datové struktury používané ve funkcionálních jazycích jsou převážně perzistentní, což znamená, že pokud jsou změněny, zachovávají své předchozí verze. Cílem této práce je rozšířit teorii perzistentních datových struktur a navrhnout efektivní implementace těchto datových struktur pro funkcionální jazyky. Bezpochyby nejpoužívanější datovou strukturou je pole. Ačkoli se jedná o vel- mi jednoduchou strukturu, neexistuje jeho perzistentní protějšek s konstantní složitostí přístupu k prvku. V této práci popíšeme zjednodušenou implementaci perzistentního pole s asymptoticky optimální amortizovanou časovou složitostí Θ(log log n) a především téměř optimální implementaci se složitostí v nejhorším případě. Také ukážeme, jak efektivně rozpoznat a uvolnit nepoužívané verze per- zistentního pole. Nejvýkonnější datové struktury nemusí být vždy ty, které jsou založeny na asymptoticky nejlepších strukturách. Z toho důvodu se také zaměříme na imple- mentaci...
|
|
|
Komunikační složitost
Wagner, Vojtěch ; Krajíček, Jan (vedoucí práce) ; Koucký, Michal (oponent)
Název práce: Komunikační složitost Autor: Vojtěch Wagner Katedra: Katedra algebry Vedoucí bakalářské práce: prof. RNDr. Jan Krajíček, DrSc. Abstrakt: Práce se zabývá teorií komunikační složitosti, která uvažuje model dvou (popř. více) hráčů, každý z nich vlastní binární vstup (x, resp. y), o němž má informaci pouze on sám. Jejich společným cílem je spočítat hodnotu něja- ké funkce f(x, y) na daných vstupech. Komunikační složitost pak měří množství informace vyměněné mezi hráči při jejich snaze spočítat f(x, y). Práce zkoumá především dva hlavní modely - deterministický model, v němž je rozhodování hráčů vždy jednoznačné a hráči spočítají vždy správnou hodnotu a pravděpo- dobnostní přístup, ve kterém je povolena náhodnost a snahou hráčů je spočítat hodnotu f(x, y) s dostatečně velkou pravděpodobností. Jsou uvedeny základní pojmy modelů a metody spodních odhadů pro dokazování komunikační složitosti funkcí. Vše je ilustrováno na příkladech několika základních funkcí. Další část je věnována příkladům náročnějším a v praxi použitelným, u nichž je řešena otázka jejich komunikačí složitosti jak deterministické, tak pravděpodobnostní. Klíčová slova: komunikační složitost, deterministický model, pravděpodobnost- ní model, spodní odhady komunikační složitosti. 1
|
host ::
RSS.