|
|
Applications of graph theory in protein function prediction
Kalábová, Nikola ; Hartman, David (vedoucí práce) ; Kratochvíl, Miroslav (oponent)
Rapidní vývoj celogenomových sekvenačních metod a jejich snižující se cena za- příčinila existenci velkého množství osekvenovaných genomů. Vývoj spolehlivých in-silico metod pro anotaci rychle rostoucího počtu osekvenovaných genomů představuje výzvu pro moderní biologii. V práci představujeme způsob predikce funkce proteinů, založený na aplikaci teorie grafů v protein-protein interakčních sítích a identifikujeme jeho silné a slabé stránky. Tento přístup poté ilustrujeme na vybraných algoritmech založených na různých myšlenkách. Představené algoritmy porovnáváme a vyhodnocujeme jejich spolehlivost. 1
|
|
|
Lotkův-Volterrův model soutěže na grafech
Skácelová, Radka ; Šremr, Jiří (oponent) ; Čermák, Jan (vedoucí práce)
Tato bakalářská práce se zabývá analýzou několika matematických modelů popisujících koexistenci dvou druhů, konkrétně klasickým Lotkovým-Volterrovým modelem a rozšířeními z něj vycházejících. Tyto modely jsou popsány soustavou nelineárních diferenciálních rovnic. Cílem této práce je sestavení rozšířeného modelu dravec-kořist užitím teorie grafů, následné nalezení stacionárních řešení tohoto modelu a analýza jejich stability. Práce je také věnována porovnání výsledků získaných pro tento grafový model se známými výsledky pro grafový model konkurence.
|
|
|
Analýza bezpečnostních vazeb v síti entit
Kuklisová, Anikó ; Nečaský, Martin (vedoucí práce) ; Kopecký, Michal (oponent)
Cílem diplomovépráce je navrhnout a vytvořitanalytickouaplikaci pro Bezpečnostníinformační službu ve formě softwarového prototypu. Navržené řešení má umožnit bezpečnostním analytikům vizualizovat, analyzovat a spravovat objekty a vazby sítě, které jsou ukládané v relační databázi. V rámci práce si projdeme celý proces vývoje, kde se nejdřív seznámíme se stávajícím softwarem a požadavky zákazníka. Potom navrhneme architekturu podporující rozšíření řešení o další moduly, vybereme vhodnou a spolehlivou knihovnu a implementujeme aplikaci. Následně představíme práci Bezpečnostní informační službě a provedeme uživatelské testování softwaru. Nakonec porovnáme existující aplikaci s novou verzí.
|
|
|
Algorithmic aspects of intersection-defined graph classes
Jedličková, Nikola ; Kratochvíl, Jan (vedoucí práce) ; Fiala, Jiří (oponent)
Geometricky reprezentovatel'né triedy grafov sú intenzívne študovanou oblast'ou výskumu v súčasnej literatúre, a to kvôli ich štrukturálnym charakterizáciám a efektívnym algoritmom. Najštudovanejšou triedou takých grafov je trieda intervalových grafov. V tejto práci sa za- meriame na dva problémy, zovšeobecňujúce problém rozpoznávania, pre triedy súvisiace s triedou intervalových grafov. V prvej časti sa zaoberáme tzv. zarovnanými intervalovými digrafmi. Táto trieda bola skúmaná ako správna analógia intervalových grafov. Pre intervalové grafy sú známe algo- ritmy pre rozširovanie čiastočných reprezentácií daných intervalov na úplnú intervalovú re- prezentáciu. My predstavíme podobný problém - rozširovanie čiastočných usporiadaní - a ukážeme polynomiálny algoritmus pre rozširovanie čiastočných usporiadaní zarovnaných intervalových digrafov. V druhej časti práce dokážeme NP-úplnost' pre dva špeciálne prípady problému simultánnych reprezentácií grafov, ktorý predstavil Jampani a Lubiw. Problém simultánnych reprezentácií pre danú triedu grafov sa pýta, či k grafov môže byt' reprezentovaných tak, že každý vrchol je reprezentovaný rovnakým objektom v každej reprezentácii. Dokázali sme, že tento problém je...
|
|
|
Compact I/O-Efficient Graph Representations
Tětek, Jakub ; Gavenčiak, Tomáš (vedoucí práce) ; Mareš, Martin (oponent)
Cílem této práce je vyvinout rychlou pamět'ově efektivní reprezentaci někte- rých grafů, které se vyskytují v praktických problémech. Uvažujeme separovatelné třídy grafů (např. rovinné grafy nebo grafy s ome- zeným rodem) a ukazujeme, jak grafy z takových tříd reprezentovat způsobem, který (1) dovoluje v průměru I/O-efektivní přístup k vrcholům při procházce a (2) používá málo paměti. Konkrétně ukazujeme kompaktní reprezentaci grafů ze separovatelných tříd s počtem I/O-přístupů při náhodné procházce délky k rovným O(K/(Bw)1−c ) s vysokou pravděpodobností. V druhé části práce se zabýváme rozložením vrcholů stromu v paměti. Uka- zujeme rozložení, které má optimální počet I/O-přístupů v nejhorším případě při procházení z kořene do listu. Dále ukazujeme aditivní (+1)-aproximaci op- timálního kompaktního rozložení vrcholů a dáváme tento výsledek do kontrastu s důkazem NP-těžkosti přesného řešení. Dále v této práci dokazujeme zobecnění věty o rekurzivních separátorech. První zobecnění rozšiřuje větu pro vážené grafy a druhé zobecnění nahrazuje ve znění věty minimální velikost regionu za průměrnou velikost. 1
|
|
|
Evropské letecké uzly v kontextu sítě a její odolnosti vůči narušení
Šulc, David ; Marada, Miroslav (vedoucí práce) ; Kraft, Stanislav (oponent)
EVROPSKÉ LETECKÉ UZLY V KONTEXTU SÍTĚ A JEJÍ ODOLNOSTI VŮČI NARUŠENÍ Abstrakt Předkládaná diplomová práce se zabývá konektivitou evropské letecké sítě, jejími vlastnostmi a odolností vůči negativním vlivům, a to na základě dat z letových řádů za zimní období roku 2018. Hlavním cílem práce je analyzovat evropskou leteckou síť z hlediska konektivity, za účelem zjištění významnosti leteckých uzlů vzhledem k jejich geografickým podmínkám, komunitní struktuře a odolnosti celé sítě. Metodicky se práce opírá o teorii grafů a míry centrality jakožto ukazatele konektivity. Empirická část práce je rozdělena na tři části. Úkolem první části je zjistit, jaká letiště jsou v evropské letecké síti nejvýznamnější. V druhé části jsou zjišťovány vlastnosti a struktura sítě jako celku. Poslední část se zaměřuje na analýzu odolnosti evropské letecké sítě z pohledu robustnosti a resilience. Mezi nejvýznamnější letecké uzly v Evropě patří letiště, která obsluhují světová města a turisticky významné lokality. Jedná se především o silnou dominanci letiště Schiphol v Amsterdamu, El Prat v Barceloně a letiště ve Frankfurtu nad Mohanem. Evropskou leteckou síť je možné klasifikovat jako tzv. "scale-free" s hierarchickou strukturou podle počtu odbavených letů a tzv. "small-world", ve které je možné se pohybovat s malým počtem přestupů....
|
|
|
Dopravní modely a jejich aplikace
Žlebek, Petr ; Nevrlý, Vlastimír (oponent) ; Pavlas, Martin (vedoucí práce)
Práce se zabývá využitím optimalizace v oblasti dopravních modelů. V první části práce jsou shrnuty teoretické poznatky z oblasti teorie grafů, matematického programování, dopravních úloh a genetického algoritmu. Tyto informace jsou následně aplikovány ve druhé části práce. V té je důkladně popsán dopravní model, který se zabývá svozem odpadu. K implementaci modelu bylo využito prostředí Matlab. Na vytvořený výpočtový aparát jsou pak aplikována reálná data pro území České republiky. V závěrečné části práce jsou shrnuty a okomentovány výsledky modelu.
|
|
|
Síťová simplexová metoda
Khýr, Lukáš ; Janošťák, František (oponent) ; Popela, Pavel (vedoucí práce)
Práce je zaměřena na shrnutí poznatků týkajících se matematického modelování v oblasti optimalizace. Budeme se podrobněji zabývat simplexovou metodou a především její síťovou modifikací, která má využití v různých praktických aplikacích. Pomocí implementace těchto dvou metod v Matlabu budou řešeny úlohy různé velikosti a budou porovnávána jejich řešení. V závěru práce se řeší úloha s reálnými daty poskytnutá Ústavem procesního inženýrství.
|
|
|
Integrated method utilizing graph theory and fuzzy logic for safety and reliability assessment of airborne systems
Janhuba, Luboš ; Hlinka, Jiří ; Koštial, Rostislav
This paper presents integrated algorithm for airborne system safety and reliability assessment. In general aviation (mostly up to EASA CS-23) and non-military unmanned aerial vehicles industry, safety and reliability assessment process still relays almost exclusively on human judgment. Recommended practices define processes for system modelling and safety assessing are based on analyst understanding of a particular system. That is difficult and time-consuming process. Commercial computation aids are extremely expensive with restricted (or closed) access to the solution algorithms. Together with this problem, rapid development of modern airborne systems, their increasing complexity, elevates level of interconnection. Therefore, safety and reliability analyses have to continuously evolve and adapt to the extending complexity. Growing expansion brings in the field of unnamed aerial vehicles systems which consist of items without relevant reliability testing. Presented algorithm utilizes graph theory and fuzzy logic in order to develop integrated computerized mean for reliability analysis of sophisticated, highly interconnected airborne systems. Through the usage of graph theory, it is possible to create model of particular systems and its sub-systems in the form of universal data structure. Algorithm is conceived as fuzzy expert system, that emulates decision making of a human expert. That brings opportunity to partially quantify system attributes and criticality. Criticality evaluation increases level of assessment correlation with real state of system and its attributes.
|
|
|
The Integrated Method Utilizing Graph Theory and Fuzzy Logic for Safety and Reliability Assessment
Janhuba, Luboš ; Vališ, David (oponent) ; Třetina, Karel (oponent) ; Hlinka, Jiří (vedoucí práce)
Doctoral thesis creates an integrated algorithm for airborne system safety and reliability assessment. In ´general aviation´ (mostly up to EASA CS-23) and ´non-military unmanned aerial vehicles industry´- safety and reliability assessment process still rely almost exclusively on human judgment. Current processes of system modelling and assessing are based on analyst understanding of a particular system. That is a difficult and extremely time-consuming process. Commercial computation aids are extremely expensive with restricted or even closed access to the solution algorithms. Together with this problem, the rapid development of modern airborne systems and their increasing complexity elevates the level of interconnection, safety and reliability analyses which have to be continuously evolved and adapted to the extending complexity. The given integrated method utilizes the graph theory and fuzzy logic in order to develop integrated and partially computerized mean for reliability analysis of sophisticated and highly interconnected airborne systems. Through the use of the graph theory, it is possible to create the model of particular systems and its sub-systems in the form of universal data structure. It is even possible to assess various systems and items interrelations. And it also enables to evaluate particular item position and topology within the system and on the global level. Extended criticality evaluation is conceived as the fuzzy expert system that emulates decision making by a human expert. The integrated method also provides additional mean how to evaluate the system design. Fuzzy robustness assessment evaluates e.g. system diversity rate, redundancy, separation and environmental protection.
|
host ::
RSS.