Témata dizertačních prací

Se stále zvyšujícím se počtem tranzistorů na čipu se také zvyšuje počet vektorů potřebných pro testování čipu. Integrované obvody jsou poprvé testovány při výrobě, před zapouzdřením. Zde jsou testovací vektory generovány tzv. ATE (Automated Test Equipment) zařízením a přenášeny do čipu. Množství dat je zde obrovské, paměť v ATE je extrémně drahá, to samé platí o době testu. Je tudíž nutné tato data komprimovat. Dle International Technology Roadmap for Semiconductors (ITRS) [1] je požadováno, aby v roce 2020 bylo dosahováno kompresního poměru 20 000. Bohužel, současné kompresní techniky se ani zdaleka neblíží tomuto poměru. Je tedy zapotřebí intenzivního výzkumu v této oblasti a pokoušet se překonat stávající kompresní techniky.

Bylo navrženo mnoho kompresních technik, některé se používají v průmyslové praxi [2]. Většina z nich je založená na kombinaci pseudo-náhodného testu (který může být implementován na čipu) a deterministického testu. Deterministické vektory jsou algoritmicky zkomprimované a uložené v ATE a posléze dekomprimované na čipu.

Cílem doktorského studia bude navrhnout nové metody pro kompresi a dekompresi testu pro pokročilé DFT architektury [3]. To bude zahrnovat návrh nových dekompresních architektur, algoritmů pro kompresi testu a návrh celkové HW architektury.

Tento výzkum bude volně navazovat na právě dokončovanou doktorskou práci [4].

1. International Technology Roadmap for Semiconductors, http://www.itrs2.net/
2. J. Rajski et al. "Embedded Deterministic Test", IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems , vol. 23, no. 5, pp. 776-792, 2004.
3. R. Dorsch, H. Wunderlich, "Reusing Scan Chains for Test Pattern Decompression", Journal of Electronic Testing: Theory and Applications, vol. 18, no. 2, pp. 231-240, 2002.
4. J. Balcárek, P. Fišer, and J. Schmidt, "Techniques for SAT-based Constrained Test Pattern Generation," in Microprocessors and Microsystems, Elsevier, Vol. 37, Issue 2, March 2013, pp. 185-195.

Současné nástroje pro logickou syntézu a optimalizaci (komerční i akademické) z převážné míry kladou důraz na rychlost, na úkor kvality. Nedávný výzkum ukázal, že tyto nástroje mají tendenci uváznout v hlubokých lokálních minimech a často produkují velice suboptimální výsledky (plocha, zpoždění). Jedním z důvodů je deterministická povaha používaných algoritmů. Randomizované iterativní algoritmy se ukázaly být jedním z řešení tohoto problému [1], [2] – nabízejí možnost zlepšit kvalitu řešení za cenu delšího výpočetního času.

Současné studie navíc ukazují, že většina nástrojů pro logickou syntézu a optimalizaci je velice citlivá na „náhodnost“ vnesenou zvnějšku, samotným návrhářem [3], [4]. Syntéza pak při nepatrné změně zdrojového kódu (při zachování funkční ekvivalence) produkuje kvalitativně značně odlišné výsledky. Toto chování není příliš žádoucí. Je tedy záhodno analyzovat toto chování, identifikovat jeho příčiny a navrhnout efektivnější algoritmy.

Cílem výzkumu bude analýza chování dostupných nástrojů (algoritmů) pro logickou syntézu a optimalizaci [5], identifikace příčin výše zmíněného chování, identifikace bodů algoritmu, kam lze explicitně vložit náhodnost a randomizace těchto algoritmů. Bude analyzován vliv náhodnosti a navrženy algoritmy, které vliv náhodnosti minimalizují, případně ji využijí v pozitivním smyslu [1], [2].

Dále mohou být navrženy nové algoritmy, které budou minimálně citlivé na náhodnost zanešenou zvenku, při zachování akceptovatelné výpočetní složitosti.

1. P. Fišer and J. Schmidt, "Improving the Iterative Power of Resynthesis," in Proc. of 15th IEEE Symposium on Design and Diagnostics of Electronic Systems (DDECS), Tallinn (Estonia), April 18-20, 2012, pp. 30-33.
2. P. Fišer and J. Schmidt, "On Using Permutation of Variables to Improve the Iterative Power of Resynthesis," in Proc. of 10th Int. Workshop on Boolean Problems (IWSBP), Freiberg (Germany), September 19-21, 2012, pp. 107-114.
3. A. Puggelli, T. Welp, A. Kuehlmann, and A. Sangiovanni-Vincentelli, “Are Logic Synthesis Tools Robust?,” in Proc. of the 48th ACM/EDAC/IEEE Design Automation Conference (DAC), 5-9 June 2011, pp. 633-638.
4. P. Fišer, J. Schmidt, and J. Balcárek, "On Robustness of EDA Tools," in Proc. of 17th Euromicro Conference on Digital Systems Design (DSD), Verona (Italy), August 27-29, 2014, pp. 427-434.
5. Berkeley Logic Synthesis and Verification Group, “ABC: A System for Sequential Synthesis and Verification” [Online]. Available: https://people.eecs.berkeley.edu/~alanmi/abc/.

Současné nástroje pro logickou syntézu a optimalizaci (komerční i akademické) z převážné míry kladou důraz na rychlost, na úkor kvality. Nedávný výzkum ukázal, že tyto nástroje mají tendenci uváznout v hlubokých lokálních minimech a často produkují velice suboptimální výsledky (plocha, zpoždění). Jedním z důvodů je deterministická povaha používaných algoritmů. Randomizace algoritmů [1], [2] se ukázala být pouze částečným řešením tohoto problému. Druhým, důležitějším důvodem, je chybějící řízení syntézních algoritmů na nejvyšší úrovni.

Současná logická syntéza je většinou iterativní proces, ve kterém se jednotlivé syntézní kroky spouštějí spekulativně. Zavedení pokročilejších technik řízení by mohlo značně vylepšit celý syntézní proces. Cílem výzkumu je prozkoumat chování jednotlivých kroků logické syntézy (např. v nástroji ABC [3]), zjistit jejich závislost a ortogonalitu a navrhnout algoritmus pro efektivní řízení celého procesu.

Reference

1. P. Fišer and J. Schmidt, "Improving the Iterative Power of Resynthesis," in Proc. of 15th IEEE Symposium on Design and Diagnostics of Electronic Systems (DDECS), Tallinn (Estonia), April 18-20, 2012, pp. 30-33.
2. P. Fišer and J. Schmidt, "On Using Permutation of Variables to Improve the Iterative Power of Resynthesis," in Proc. of 10th Int. Workshop on Boolean Problems (IWSBP), Freiberg (Germany), September 19-21, 2012, pp. 107-114.
3. Berkeley Logic Synthesis and Verification Group, “ABC: A System for Sequential Synthesis and Verification” [Online]. Available: https://people.eecs.berkeley.edu/~alanmi/abc/.

Cílem práce je analyzovat vnímání materiálů za proměnných světelných a pozorovacích podmínek. Práce bude mít za úkol nalezení vhodných statických i dynamických vizuálních stimulů a jejich realtivního významu pro lidské vnímání a rozpoznávání odlišných materiálů.

Práce je zaměřena na studium metod rozpoznávání a modelování tvaru těles z videozáznamu pro aplikace virtuální reality. Navrhněte a implementujte v programovacím jazyce C++ vhodnou metodu automatického odhadování 3D modelu z naměřených dat pomocí videokamery. Ověřte metodu na vybraných modelech budov.

Práce je zaměřena na studium metod odhadu pokročilých reprezentací vizuálních vlastností povrchových materiálů (BTF, SVBRDF) přímo měřením 3D objektu v přirozeném osvětlení. Navrhněte a implementujte v programovacím jazyce C++ vhodnou metodu automatického odhadování vizuální reprezentace povrchového materiálu z naměřených dat pomocí videokamery. Ověřte metodu na vybraných povrchových materiálech.

Práce je zaměřena na studium metod modelování osvětlení z naměřené obrazové informace pro aplikace modelování BTF textur v modelech virtuální reality. Navrhněte a implementujte v programovacím jazyce C++ vhodnou metodu tvorby osvětlení z naměřených obrazových dat. Ověřte metodu na modelu osvětlení interiéru a exteriéru při proměnném osvětlení

Vzhled reálných materiálů se významně mění se změnou osvětlení a pohledu. Proto současné nejvyspělejší texturní reprezentace vyžadují modelovat odrazivost v širokém rozsahu parametrů osvětlení a umístění kamery pomocí složitých matematických modelů. Cílem práce bude vyvinout a ověřit nový BTF model založený na teorii markovských náhodných polí, který zlepší současný stav fyzikálně správného modelování povrchů materiálů.

Cílem práce je kriticky zhodnotit současný stav neřízené segmentace obrazových dat a vyvinutí algoritmu pro neřízenou segmentaci dynamických barevných / multispektrálních / hloubkových obrazů do jednotlivých homogenních oblastí. Algoritmus bude založen na vícerozměrných markovských modelech a testován na PTSB benchmarku.

Melanom kůže, jako nejnebezpečnější forma rakoviny kůže, je rostoucím nebezpečím v posledních desetiletích díky svému stále zvyšujícímu se výskytu. Jeho efektivní léčba vyžaduje jeho rozpoznání a chirurgické odstranění v co nejranější fázi. Cílem práce je nalezení diskriminativních obrazových příznaků a vhodného klasifikátoru, který umožní rozpoznání rakoviny kůže z barevných obrazů kůže a zároveň umožní monitorování pokroku léčby ze sekvence časově proměnných obrazů nádoru.

Online trénování označuje trénování modelů strojového učení když jsou jejich trénovací data online aktualizována. V takových situacích pravděpodobnostní rozdělení trénovacích dat typicky bývá nestacionární a vyvíjí se. Online trénování se používá s oběma hlavními typy strojového učení s učitelem – klasifikací a regresí, stejně tak jako v kontextu učení bez učitele. Kvůli online aktualizaci a vývoji trénovacích dat se online učení musí vypořádat s několika specifickými problémy, jako např. s možností posunu pojmů, která v případě nejčastějšího druhu online učení – inkrementálního online učení ­– vede k potřebě ladit správné množství zapomínání, např. výběrem časového horizontu. Dalším žádoucím cílem je redukce výpočetních nároků častých aktualizací modelu bez negativního dopadu na jeho prediktivní přenost. Konečně, neméně důležitý je požadavek, aby schéma opakovaného online trénování umožňovalo průběžně zahrnovat nově se vynořující třídy.

V tomto desetiletí jsou pravděpodobně nejpopulárnějším a nejrychleji se rozvíjejícím druhem modelů strojového učení hluboké neuronové sítě. Pro ně je však výzkum zabývající se online učením, zvláště pak online učením s učitelem, a výše zmíněnými problémy teprve v začátcích. To činí navržené téma velmi aktuálním, zvláště v oblastech, které poskytují vyvíjející se data ve velkých množstvích potřebných pro hluboké učení, jako je analýza obsahu webu, detekce proniknutí do sítě či detekce malware. Poslední zmíněná oblast je zamýšlenou oblastí aplikace navrženého výzkumu. Školitel specialista pracuje jako odborník na hluboké učení v detekci malware pro firmu Avast.

Optimalizační úlohy, se kterými se setkáváme v reálných aplikacích, stále častěji optimalizují cíle, kterými nejsou matematické funkce, ale výsledky počítačových simulací nebo experimentálních měření. Tento druh optimalizace, označovaný jako black-box optimalizace, představuje dvě velké výzvy: 1. lze získat pouze hodnoty takového black-box cíle, nikoliv jeho gradient nebo vyšší derivace, 2. vyhodnocení cíle je typicky časově náročné a/nebo drahé. Pokud jde o první výzvu, v uplynulých desetiletích se velmi úspěšnými při otimalizaci používající pouze hodnoty cíle ukázaly být evoluční algoritmy. Ty však typicky vyžadují velké množství vyhodnocování, což je v konfliktu s druhou výzvou. Tento konflikt v uplynulém desetiletí podnítil intenzivní výzkum evoluční black-box optimalizace, který s sebou přináší široké spektrum dizertabilních témat.

Semi-supervizované učení označuje učení klasifikačních a regresních modelů, pro které je k dispozici na jedné straně množina oštítkovaných dat, na druhé straně jiná, typicky mnohem větší množina neoštítkovaných dat. Vždy spočívá ve vytvoření určitého spojení mezi jednotlivými neoštítkovanými daty a jedním nebo více oštítkovanými daty. Toto spojeni může být buď ostré nebo fuzzy a vždy spočívá na nějakém druhu podobnosti mezi jednotlivými spojenými daty. Velké množství měr podobnosti, se kterými se setkáváme v tomto kontextu, sahá od vzdáleností založených na normách v eukleidovském prostoru po sémantické podobnosti reprezentované pomocí grafů. Navíc může semi-supervizované učení buď vyjít z oštítkovanýmch dat, které iniciují shlukování neoštítkovaných dat, nebo začít vytvářením shluků neoštítkovaných dat, které jsou následně přizpůsobeny dostupným oštítkovaným datům. Konečně, výzkum semi-supervizovaného učení se vzájemně ovlivňuje s výzkumem aktivního učení, které spočívá ve výběru těch neoštítkovaných dat, jejichž oštítkování je z nějakého hlediska nejužitečnější.

V tomto desetiletí jsou pravděpodobně nejpopulárnějším a nejrychleji se rozvíjejícím druhem klasifikačních i regresních modelů hluboké neuronové sítě. S nimi semi-supervizované učení dosud používalo pouze nejběžnější varianty jak přístupu vycházejícího z oštítkovaných dat, tak i přístupu vycházejícího ze shlukování neoštítkovaných dat, druhý z nich zejména pokud i shlukování je prováděno pomocí hlubokých sítí, konkrétně autoenkoderů. Výzkum důmyslnějších metod semi-supervizovaného učení je v kontextu hlubokých neuronových sítí úplně na začátku. Zvláště žádoucí by bylo využít schopnost hlubokých sítí extrahovat v průběhu učení nové, relevantnější příznaky. Důležitost výzkumu semi-supervizovaného učení hlubokých neuronových sítí je důsledkem skutečnosti, že hluboké učení potřebuje velké množství dat. Tato důležitost je zvláště vysoká v oblastech, kde je obtížné získat oštítkovaná data, buď proto, že musí být získávána experimentálně, nebo protože vyžaduje časově náročné zapojení člověka – experta, jako např. v oblastech analýza sentimentu, detekce proniknutí do sítě či detekce malware. Poslední zmíněná oblast je zamýšlenou oblastí aplikace navrženého výzkumu. Školitel specialista pracuje jako odborník na hluboké učení v detekci malware pro firmu Avast.

Evoluční algoritmy jsou v posledních 20 letech jednou z nejúspěšnějších metod pro řešení netradičních optimalizačních problémů, jako např. hledání nejvhodnějších dokumentů obsahujících požadované informace, objevování nejzajímvějších informací v dostupných datech či další typy optimalizačních úloh, při nichž lze hodnoty cílové funkce získat pouze empiricky. Protože evoluční algoritmy pracují pouze s funkčními hodnotami optimalizované funkce, blíží s k jejímu optimu podstatně pomaleji než optimalizační metody pro hladké funkce, které využívají rovněž informace o gradientu optimalizované funkce, případně o jejích druhých derivacích. Tato vlastnost evolučních algoritmů je zvláště nepříjemná ve spojení se skutečností, že empirické získání hodnoty optimalizované funkce bývá obvykle značně nákladné i časově náročné. Evoluční algoritmy však lze podstatně urychlit tím, že při vyhodnocování funkční hodnoty optimalizované funkce používají empirickou optimalizovanou funkci jen občas, zatímco většinou vyhodnocují pouze její dostatečně přesný regresní model. Právě přesnost modelu určuje, jak úspěšnou náhražkou původní empirické funkce bude. Proto se po získání každé nové generace bodů, v nichž byla empirická funkce vyhodnocena, model zpřesňuje opakovaným učením zahrnujícím tyto body. Lze však jít ještě dále a již při volbě bodů pro empirické vyhodnocení brát kromě hodnoty empirické funkce také v úvahu, jak při opakovaném učení modelu přispějí k jeho zpřesnění. Takový přístup se označuje jako aktivní učení. Používání aktivního učení k urychlení evolučních algoritmů je však teprve v úplných začátcích a měla by ho podpořit i navržená práce.

Cílem práce je nalézt efektivnější metody pro uchovávání a vyhledávání dat pro různé úlohy v bioinformatice.

Cílem práce je nalézt efektivnější metody pro kompresi přirozeného jazyka na základě částečných znalostí jazyka.

Cílem práce je nalézt efektivnější metody pro uchovávání dat ve formátu XML. Tyto metody musí zajistit i snadný a rychlý přístup k uloženým datům.

Výrazně se rozvíjejíci oblast IoT (Internet of Things) musí respektovat standardy adresace v Internetu, bezdrátových přístupových kanálech a standardy jednoznačné identifikace prvků v technologiích řízení a v IoT technologiích. Návrh výzkumného řešení se může principiálně opřít o P2P adresní databázi opírající se o dřívější řešení založené na Chord DHT technologii. Cílem výzkumné oblasti je návrh, vzorová iplementace a ověření metody pro zajištění komunikace v IoT systémech s mobilními prvky.

Cílem projektu je vyrovnat se jednak s poziční mobilitou a jednak s výraznější proměnnou vazbou v systémech se sensory, prostřednictvím distribuované aplikace řízenými prvky a přístupovými zařízeními uživatelů.

Cílem projektu je zefektivnit přístup k datům získaným senzory a k distribuci dat výkonovým prvkům v distribuovaných aplikacích. Projekt může vyjít z našeho vývoje založeného na technologii SOAP s poměrně vysokými nároky na stranu serverů, kde byl výsledkem nástroj opřený o popis rozhraní ve WSDL vytvořený z rozhraní aplikace, a o jeho převod do formy opírající se o skupinu konečných automatů realizovatelných i na relativně malém mikropočítači. Výsledky SOAP cesty byly námi sice již publikovány na konferencích IEEE a IASTEID, současné technologie se však opírají o nové popisy, jako WALD, jejichž začlenění do obdobných řešení může být přínosné.

Výrazně se rozvíjejíci oblast IoT (Internet of Things) klade odlišné požadavky na vývoj a modifikace programů jejích mobilních a ne vždy přímo dostupných prvků. Technologie přípravy a distribuce programů, vyhovující ve statických distribuovaných systémech, jednoduchých aplikací kategorie klient/server a v clouds systémech přestávají dostačovat. Cílem výzkumné oblasti je návrh, vzorová implementace a ověření metod, které potřebné požadavky podpoří.

CCA sítě vytvářejí architekturu Internetu budoucnosti podporující násobné a mobilní pozice pro servery, nebo obecně procesy distribuovaných aplikací. Cílem projektu je návrh a ověření efektivity funkčně limitovaných sítí založených na modelech CCN (Content-Centric networking).

Seřazené a neseřazené stromy. Vyhledávání, indexování, další typy zpracování. Přesné a přibližné.

Hloubkové mapy jsou snímky, kde intenzita jasu odpovídá vzdálenosti. Přesnost určení vzdálenosti čidlem je závislá na vzdálenosti snímaného objektu. Obecně platí, že čím je objekt blíž, tím je přesnost vyšší a naopak. Současně vzdálenější objekty jsou reprezentovány menším počtem pixelů a tedy i přesnost rozlišení je menší.

Cílem práce je prozkoumat možnosti zvyšování přesnosti hloubkových map použitím dvou a více senzorů. Výzkum by se měl zaměřit na analýzu různých vzájemných uspořádání čidel vůči sobě. Výsledkem by měla být exaktně podložená analýza a návrh algoritmů, které budou zohledňovat získané poznatky a na jejich základě budou zpřesňovat požadované hloubkové mapy.

Školitel specialista – Ing. et Ing. Marek Polčák

Hlavním cílem práce je navrhnout a vyvinout intuitivní ovládání pro virtuální realitu (dále jen VR). Ovládání bude navrženo na základě informací získaných z rešerše zaměřené na možnosti ovládání VR pomocí rukou, hlasu a pohybu očí.

Ovládání pomocí rukou bude realizováno pomocí 3D modelů rukou, které vzniknou na základě rozpoznávání z obrazu, a to pomocí existujících, nebo vlastních algoritmů. Pro ovládání pomocí hlasu bude použita nativní podpora v rámci operačním systému Windows 10. Pohyb očí bude měřen pomocí eye-tracking XTAL, které poskytne informace o pohledu uživatele v reálném čase.

Cílem je vývoj virtuálních prostředí, která umožní dobře pochopit reálné prostředí. Příkladem je modelování extrémních situací (např. při požárech, pádu letadla, dopravních nehodách, lavinových neštěstích atd.), záchrana životů (práce pro pohotovostní službu, resuscitace, operace atd. ), pobyt v mimozemském prostředí a ve vesmíru (práce pro NASA, kosmonautiku), digitální nesmrtelnost, prevence násilných sociálních jevů, zlepšování kognitivních schopností, výchova k informatickému myšlení (formulace, algoritmizace a řešení problémů), realizace adrenalinových žážitků, lepší osvojení obsahu odborné výuky apod.

Dalším cílem je vývoj virtuálních prostředí, která umožní propojení s reálným prostředím a vykonávání činností, které běžně provádíme v reálném prostředí. Příkladem je ovládání spotřebičů, výběr hotovostí v bankomatu, nakupování, provádění plateb, realizace konferencí, seminářů, hledání informací, zveřejňování výsledků výzkumu, pracovních schůzek apod.

V oblastech, kde je software pouze částí vypracovávaného projektu, je prototyp, případně první verze daného softwarového celku zpravidla diametrálně odlišná od jeho ideální výsledné podoby a na refactoring do tohoto stavu již často nezbývá prostředků jak materiálních, tak časových. Tato skutečnost se negativně podepíše např. na testovatelnosti systému, jeho udržitelnosti, rozšiřitelnosti a dokonce uživatelské přívětivosti, použitelnosti a funkčnosti a ve výsledném úhrnu činí systém, potažmo celý projekt nákladnějším nebo dokonce předznamenává jeho neúspěšnost. Jedním z důvodů tohoto stavu je chronický nedostatek vhledu do struktury softwarového řešení, neexistence dostatečných výrazových prostředků k zachycení myšlenky a nedostatečné soustředění pozornosti na softwarovou část v celé její šíři. Je tomu tak i v technologických oblastech, kde je kladen velký důraz na vývoj, testování a certifikaci hardwarové části produktu, avšak softwarová část bývá kamenem úrazu tohoto jinak zavedeného procesu.

Dizertační práce si klade za cíl analyzovat a modelovat potřeby a nároky na software v technologických a přírodovědných oborech, zhodnotit jeho různorodost a komplexnost a pokusí se navrhnout postupy, výrazové a programové prostředky, které mohou přispět ke zmenšení výskytu výše zmíněných negativních jevů.

Školitel specialista – Ing. Tomáš Čejka, Ph.D.

Obsahem práce bude výzkum algoritmů pro detekci, identifikaci a mitigaci bezpečnostních hrozeb a anomálií v počítačových sítích se zaměřením na oblast tzv. Internetu věcí (IoT). Z pohledu síťové bezpečnosti je nutné nahlížet na oblast IoT jako na hrozbu a to jak pro samotné IoT, tak i pro další zařízení, kdy IoT se může stát zdrojem hrozby. Je proto důležité sledovat komunikaci v těchto sítích, odvozovat z významných událostí v komunikaci další meta informace a tyto informace používat pro identifikaci zdroje hrozeb, mitigaci hrozeb a řízení strategie mitigace.

Cílem dizertační práce bude nalezení vhodných možností, jak vytvářet modely dlouhodobě uchovávající negativní či pozitivní události v komunikaci, a jak na základě těchto modelů co nejrychleji (s minimální latencí) tyto detekovat, identifikovat a odstranit zdroje problémů. Dizertabilita tématu je založena na faktech, že jde o řešení velmi netriviálních problémů, kterými jsou zpracování a filtrace velkých objemů dat společně s modelováním síťového provozu, hledání odchylek,identifikace zdrojů problémů a správné řízení mitigace těchto problémů. Na rozdíl od klasických IP sítí, IoT prostředí navíc významně využívá specifických fyzických vrstev v podobě specializovaných komunikačních protokolů, což s sebou přináší nové potenciální vektory útoků, které jsou běžnou analýzou IP provozu nedetekovatelné. Z tohoto důvodu je potřeba hledat nové způsoby monitorování IoT provozu. Základem bude výzkum v oblasti možností využití statistických metod, pravděpodobnostních modelů a využití algoritmů umělé inteligence.

Vzhledem k současným rychlostem síťových přenosů a požadavkům na on-line monitorování je nutné algoritmy navrhovat a realizovat s využitím dekompozice na hardwarovou a softwarovou část a s použitím vhodných technologií hardwarové akcelerace (např. FPGA).

Výzkum možností využití formálních metod (Petriho sítě, Markovské řetězce, UML diagramy) pro zjednodušení návrhu číslicového systému a jeho automatizaci. Předpokládejme spojení s verifikací a výpočty spolehlivostních ukazatelů ve všech návrhových fázích a úpravu a optimalizaci řešení podle různých parametrů. Cílem by měla být i vzájemná kombinace různých typů modelů a podrobný výzkum vztahů a automatizovaného přechodu mezi nimi. Dílčí výsledky a navržené metody budou průběžně ověřovány na reálných aplikacích a benchmarcích.

Výzkum způsobů a postupů v návrhu systému s předem danými spolehlivostními parametry na bázi programovatelného hardwaru (FPGA i procesorů). Výzkum vlivu redundance na různých úrovních (v prostoru, čase, SW, HW) na odolnost proti útokům. Zahrnutí možné automatizace postupů včetně vytvoření spolehlivostních modelů a výpočtů spolehlivostních parametrů. Předpokládá se průběžné ověřování výsledků na reálných aplikacích a benchmarcích.

Školitel specialista – Ing. Martin Kohlík, Ph.D.

Současné spolehlivostní modely často využívají zjednodušené postupy vedoucí k nerealistickým odhadům spolehlivosti a životnosti modelovaných systémů [1], nebo používají hrubé pesimistické odhady [2]. Cílem práce by měla být metodologie návrhu spolehlivostního modelu, který umožní rychlé a přesné výpočty spolehlivostních parametrů systému. Metodologie by měla zohlednit změny systému v čase (např. stárnutí, údržbu, opravy), strukturu systému (jednotlivé bloky a jejich případné zabezpečení proti poruchám) a možnosti získávání spolehlivostních ukazatelů z reálných dat [3].

Reference

1. Electronic Reliability Design Handbook - MIL-HDBK-338B. US Department of Defense, 1998.
2. M. Kohlík, "Hierarchical Dependability Models Based on Markov Chains", Dissertation thesis, Czech Technical University in Prague, 2015.
3. M. Daňhel, "Prediction and Analysis of Mission Critical Systems Dependability", Dissertation thesis, Czech Technical University in Prague, 2018.

Obsahem tématu je výzkum ověření možností, jak dosáhnout (a garantovat) předem určená omezení při návrhu systému (velikost, spotřebu, požadované ukazatele spolehlivosti, odolnost proti poruchám/útokům) vhodnou kombinací výběru a poměru hardwaru a softwaru. Předpokládáme využití systému pro návrh procesorů Codasip a otevřeného procesoru RISC-V (RISC-V byl specielně navržen pro široké použití nejen, pro vestavné systémy s důrazem na výkon i na spotřebu). Systém Codasip (https://codasip.com/) umožňuje navrhovat a upravovat specializované procesory, a to včetně verifikačních nástrojů.

Součástí výzkumu bude i použití a případná úprava vhodných spolehlivostních modelů pro ověření dosažení požadovaných parametrů s hlavním cílem určení nejlepší realizace vzhledem k původním požadavkům, tzn. například úprava instrukční sady přidáním kryptografických instrukcí, přidání dalšího bloku, použití více specializovaných procesorů apod.

Ověření výsledků bude možné jednak simulací a jednak implementací ve vhodné FPGA technologii.

Hluboké sítě se staly v současné době nejpoužívanější metodou v oblasti rozpoznávání obrazů, zejména vizuálních a klasifikačních úloh. Několik nedávných studií ale ukázalo, že se některé hluboké sítě dají snadno zmást malou, pro lidské oko nepostřehnutelnou, změnou obrázku, která vede k tomu, že je obrázek klasifikován jako něco úplně jiného. Je proto potřebné zkoumat robustnost neuronových sítí vzhledem k matoucím vzorům.

Cílem dizertace je navrhnout multiobjektivní algoritmy generující nepostřehnutelné perturbace obrázků vedoucí k jejich nesprávné klasifikaci. Budou vyvinuty evoluční algoritmy pro generování matoucích obrázků, které maximalizují chyby klasifikace a zachovávají co největší podobnost originálním trénovacím vzorům. Bude analyzována role hloubky sítě a lokálních vlastností výpočetních jednotek. Budou zkoumány metody pro zvýšení robustnosti neuronových sítí vzhledem k matoucím vzorům.

Kryptoanalýza je důležitou součástí kryptologie zabývající se bezpečnosti šifer. Jednou z nejzákladnějších metod kryptoanalýzy pracující s párem otevřený – šifrový text je algebraická kryptoanalýza. Metody algebraické kryptoanalýzy můžou včas odhalit principiální slabiny stávajících nebo nově vytvořených šifer.

Téma dizertační práce je studium a návrh kryptoanalytických metod založených na Gröbnerových bázích, které jsou vhodné pro paralelní implementaci. Cílem práce by měla být efektivně pracující kryptoanalytická metoda použitelná pro testování bezpečnosti různých typu šifer.

Kryptoměny jsou novým fenoménem, který je založený na decentralizaci a umožňuje nám anonymní platby. V dnešní době existuje přes tisíc kryptoměn, které jsou založené na různých konceptech, jako jsou např. proof-of-work nebo proof-of-stake.

Cílem bude navrhnout novou kryptoměnu, která by splňovala bezpečnostní požadavky i požadavky trhu jako jsou škálovatelnost, dostatečná rychlost zpracování transakcí, nízká latence a byla by šetrná k životnému prostředí.

Škodlivý kód neboli malware patří v dnešní době mezi největší bezpečnostní hrozby. Každodenně se vygeneruje ohromné množství nového škodlivého kódu, a protože není možné analyzovat každý vzorek zvlášť, je potřeba vyvinout automatické mechanismy, které by ho dokázaly detekovat. Ukazuje se, že algoritmy strojového učení jsou vhodným nástrojem pro automatickou detekci malware. Pomocí nich je možné detekovat i zero-day malware, avšak na rozdíl od standardních postupů, jako je detekce založena na signaturách, dosahují vyšší false positive (FP). Cílem dizertační práce bude vyvinout automatický systém pro detekci malware dosahující solidní přesnost klasifikace a mající minimální FP.

Školitel specialista – Ing. Jiří Buček, Ph.D.

V oblasti hardwarových kryptografických zařízeních probíhá neustálá soutěž mezi vývojem nových útoků a naopak obran proti nim. Útok má obvykle za cíl odhalit tajnou informaci, například tajný symetrický klíč, soukromý klíč nebo tanou zprávu. Jeden z relativně nových přístupů útoku je kombinace metod pasivních a aktivních útoků na kryptografické zařízení.

Cílem práce je prozkoumat nové možnosti kombinace aktivních a pasivních fyzických útoků s poznatky z lineární, diferenciální nebo algebraické kryptoanalýzy.

Řešení celočíselné soustavy lineárních rovnic (SLR) bez zaokrouhlovacích chyb lze provést pomocí rozdělení řešení do soustav lineárních kongruencí (SLK) a následného převodu výsledků do množiny řešení původní SLR. K tomuto převodu se používá tzv. MRC algoritmus, který má složitost O(nm2), kde n je dimenze matice a m je počet použitých SLK (modulů).

Cílem práce je nalézt efektivnější způsob použití MRC algoritmu, který těží ze znalosti vzájemné datové závislosti řešení SLR. Rovněž je možné navrhnout zparalelnění nově navrženého algoritmu. Výsledkem je metoda založená na MRC pracující s menší složitostí než O(nm2) pro řešení zpětného převodu výsledků SLK na výsledky SLR.

Chování různých obvodů založených na polovodičích je kromě jiných faktorů závislé taktéž na prostředí, ve kterém jsou provozovány. Žádanou informací pro uživatele různých HW zařízení je spolehlivost těchto zařízení v závislosti na stáří, a s tím do určité míry související odolnost polovodičových komponent vůči ionizujícímu záření.

Téma dizertační práce je matematické modelování chování HW polovodičových komponent na různé technologické úrovni v závislosti na ozáření ionizujícím/korpuskulárním zářením. Cílem práce je vytvořit model chování HW zařízení zahrnující faktory stárnutí a degradace materiálů vlivem ozařování. Výsledky budou využitelné pro určení spolehlivosti/doby bezchybné funkcionality obvodů vystavených ozáření nebo dlouhodobému používání.

Studium vhodných post-kvantových kryptosystémů je již dlouhodobě v zájmu kryptologů. Důvodem jsou zdárně se rozvíjející technologie kvantových počítačů, které by mohly svými vlastnostmi za použití vhodných faktorizačních algoritmů ohrozit bezpečnost asymetrických kryptosystémů.

Téma dizertační práce je studium a analýza stávajících a návrh nových metod kryptografických post-kvantových algoritmů. Cílem je vytvořit takový asymetrický kryptosystém, který by byl odolný vůči útokům za použití kvantových počítačů a byl by implementačně jednoduchý a bezpečný.

Jedním z kandidátů post-kvantových kryptosystémů vhodných pro analýzu a případnou úpravu je asymetrický šifrovací algoritmus McEliece založený na binárních Goppa kódech. Tento algoritmus vyhovuje bezpečnostním požadavkům kladeným na asymetrické kryptosystémy dnešní doby, avšak je zde problém s jeho velkou prostorovou složitostí. Snaha o zkrácení velikosti klíčů u tohoto algoritmu muže být dobrou počáteční výzvou pro další výzkum.

Cílem je návrh a implementace specializovaných hardwarových architektur pro výpočet modulárních aritmetických operací. Výsledky jsou použitelné v kryptografii eliptických křivek, stejně jako i v jiných systémech, které využívají modulární aritmetiku.

Současné hardwarové komponenty kryptografických systémů se neobejdou bez kvalitních TRNG. Rovněž jsou žádané spolehlivé generátory klíčů, které jsou založené na PUF. Takové generování klíčů je z hlediska bezpečnosti velmi žádané, a to proto, že tímto způsobem vygenerovaný klíč zůstává „tajemstvím“ samotného hardware kryptosystému.

Téma dizertační práce je studium chování navržených PUF a TRNG z hlediska jejich dlouhodobé stabilní odezvy. Cílem práce je prozkoumat stávající a navrhnout nová řešení PUF a TRNG, která jsou vhodná pro účely dlouhodobého generování kvalitního výstupu u TRNG, a která dávají rovněž garanci stabilního generování klíčů vycházejícího z odezev PUF. Práce zahrnuje studium a pochopení chování těchto komponent na statistické úrovni a taktéž na úrovni fyziklální/technologické.

Testovací vzorky jsou generovány v systému ATPG. Kromě logických hodnot 0 a 1 vzniká při generování velké množství nedefinovaných bitů. Při kompresi vzorků, které jsou přiváděny na vstupy číslicových obvodů, je výhodné využít exstenci neurčených bitů a podobnosti za sebou jdoucích vzorků. Kritériem optimality je míra redukce vzorků, složistost hardwaru nutného pro dekompresi testovací sekvence a počet hodinových cyklů nutných pro vlastní dekompresi. Optimalizace je možné provádět v prostředí MATLAB a C.

Rozvoj výpočetních prostředků a algoritmů umožňuje experimentálně ověřovat kvalitu automatů podle specifických požadavků na komplexnější úrovni než v minulosti. Pro kompresi a dekompresi testovacích vzorků se používají takové automaty, které umožňují během daného počtu hodinových taktů přejít mezi stavy, které representují jednotlivé vzorky. Vzhledem k charakteru vzorků se jako automaů používá obvodů LFSR, které mají vhodně zvolené charakteristické polynomy. Ukazuje se však, že je možné hledat jiné typy automatů, které mají lepší řiditelnost při přechodu mezi stavy reprezentujícími nejčastěji vyskytující se vzorky. Na základě experimentů pomocí řešičů soustav lineárních rovnic a vhodného algoritmu prohledávajícího prostor možných automatů předpokládáme vylepšení sledovaných kompresních vlastností tím, že vybereme obecně nejvhodnější strukturu dekompresního automatu podle zadaných charakteristik vzorků.

Školitel specialista – Ing. Michal Valenta, Ph.D.

Hlavním cílem práce je výzkum technik optimalizace dotazů nad grafovou databází ve formě atributového orientovaného grafu a též s ohledem na specifika konkrétního grafu a typických dotazů nad ním. Vhodnou aplikační doménou je analýza datových toků (data lineage).

Dalším cílem práce je výzkum a návrh metod pro dynamickou distribuci dat v distribuované grafové databázi na základě analýzy dotazů nad touto databází

Jedna z nedostatků klasických metod pro specifikaci softwarových požadavků je obtížnost ověření konzistence a adekvátnosti specifikací. Softwarové inženýrství reagovalo na tuto skutečnost různými metodami (např. model based software engineering, agile software development, executable algebraic specification), které dovolují vidět praktické chování specifikací co nejdřív ve vývojovém procesu. Tyto metody ale dělají kompromisy ohledně jiných aspektů např. týkající se expresivity anebo preciznosti. V rámci tohoto tématu student navrhne formální jazyk, který splní dva na první pohled protichůdné cíle:

• Jazyk má expresivitu tak vysokou aby mohl sloužit k pohodlnému psaní specifikací
• Specifikace v tomto jazyku se dají provést podobně jako programy v obvyklém programovacím jazyku

Klíč pro současné splnění obou cílí budou anotace, kterými uživatel jazyku poskytuje informaci o exekuci specifikace tak, aby zvýšená snaha o psaní anotací měla za důsledek zvýšenou účinnost exekuce. První krok bude vývoj nástroje pro výuku, který dovoluje studentům, kteří píšou specifikace jako úkol ve cvičeni, jejich řešení hned i spustit i otestovat.

Vyvíjíme software, teorii a algoritmy které umí řešit matematické formule obsahující nelineární rovnice a nerovnice, konjunkce, disjunkce, a logické kvantifikátory. Aplikujeme výslednou technologii v několika oblastech (např. verifikace složitých systémů, výpočet Lyapunových funkcí). Nabízíme velké množství témat v této oblasti. Podrobnosti jsou k nalezení zde: http://www.cs.cas.cz/~ratschan/theses/cz/constraint_solving.html

Vlak Pendolino z Prahy do Ostravy měl na začátku vážné problémy: občas zastavoval během jízdy kvůli chybě v softwaru. Podobné chyby způsobovaly vážná neštěstí, například havárii raketoplánu Ariane 5 v roku 1996. Náš výzkum je zaměřen na pomoc se v budoucnosti takovým problémům vyhýbat. Nabízíme velké množství témat v této oblasti. Prodrobnosti jsou k nalezení zde: http://www.cs.cas.cz/~ratschan/theses/cz/verification.html

Dizertační práce se bude zabývat vizualizací a grafickou reprezentací dat o provozu v počítačových sítích za účelem bezpečnostní analýzy a prezentace výsledků nahlášených detekcí včetně důkazního materiálu. Vzhledem ke zvyšujícím se objemům dat přenášeným po stále rychlejších síťových infrastrukturách narůstá obtížnost prezentovat informace o provozu uživateli. Na uživatelská rozhraní jsou v této oblasti kladeny nároky na automatické nebo aspoň poloautomatické „předfiltrování“ relevantních dat. Cílem je prezentovat uživateli jen dostatečné minimální množství dat tak, aby se uživateli práce zjednodušila či v některých případech dokonce umožnila. Jedná se o velké objemy dat se spoustou sémantických vazeb, jež se velice obtížně převádějí do grafické (2D) reprezentace (jde o víceúrovňovou abstrakci).

Doktorand bude volně navazovat na svou dosavadní práci v oblasti vývoje uživatelských rozhraní určených pro správu a konfiguraci síťových zařízení. Práce navazuje na dlouhodobou spolupráci s výzkumníky v oblasti monitorování sítí a síťové bezpečnosti působící na FIT ČVUT v Praze a v organizaci CESNET, z.s.p.o. Navrhovaný školitel má bohaté zkušenosti s problematikou tvorby a testování uživatelského rozhraní. Zároveň je odborníkem na oblast interakce člověk – počítač.

Navrhovaný školitel specialista se dlouhodobě věnuje síťové bezpečnosti a monitorování vysokorychlostních počítačových sítí, což dokazuje i svou intenzivní publikační činností. Školitel specialista bude cenným přínosem pro doktorandův výzkum a poskytne potřebnou zpětnou vazbu z pohledu praktické využitelnosti vyvinuté metody reprezentace dat.

Dizertabilita plánovaných výsledků je založena na faktech, že práce se bude zabývat velmi netriviálními problémy, kterými jsou jak zpracování a filtrace velkých objemů dat, tak i jejich následná prezentace uživateli.

Předpokládaným výsledkem práce budou články a studie metodologie, která umožní a zpřehlední uživatelům práci s daty. Očekávaný společenský a akademický přínos plánovaných výsledků je založen na faktu, že monitorování a následná vizualizace dat je kriticky důležitá pro provoz moderních rozsáhlých počítačových síťových infrastruktur. Výsledky výzkumu mají silný potenciál komerčního využití v existujících monitorovacích a „Intrusion Detection“ systémech.

Dosavadní metody komprese testu vycházejí z předem vygenerovaného testu. Je-li generátor testu schopen akceptovat omezení na hodnoty některých vstupních proměnných, dá se pracovat s celou množinou vektorů, pokrývajících danou poruchu najednou a vybrat podmnožinu, která vyhovuje daným omezením. Metodou překrývání vektorů dostaneme komprimovaný test.

Explicitní reprezentace množiny vektorů výčtem vede na značné výpočetní složitosti algoritmu. Množinu vektorů lze určit jako všechny vektory, které splňují jistý Booleovský výraz. K práci s takto implicitně zobrazenými množinami lze použit operace Booleovy algebry a k převodu do explicitního zobrazení řešič problému splnitelnosti Booleovy formule.

Příbuzných aplikací je více a vzniká obecná otázka, kdy a jak implicitní reprezentace a methody nasadit, jaké jsou jejich meze a jaké typy algoritmů je využijí nejlépe. Odpověď je cílem práce.

Studie naší výzkumné skupiny v posledních letech ukázaly, že existující postupy návrhu kombinačních logických obvodů se zhruba dají rozdělit do následujících dvou skupin:

1. Klasické, "učebnicové" postupy, založené na minimalizaci a dekompozici. Vlivem uniformní reprezentace Booleovy funkce (normální forma, rozhodovací diagramy) kvalita jejich výsledku nezávisí na velikosti nebo způsobu popisu zadání. Tyto postupy však nejsou škálovatelné - selhávají pro velké obvody, i když jim poskytneme úměrně mohutnější výpočetní prostředky.
2. Škálovatelné metody, založené na postupné transformaci zadání do výsledku. Pracují i na velkých obvodech. Jestliže však je popis zadání příliš rozdílný od výstupního, optimálního popisu, algoritmus postupných transformací nedokáže tuto vzdálenost přetraverzovat. V obecném případě, velikost vstupního popisu (měřená třeba v literálech) významně koreluje s velikostí výstupu (měřenou například v hradlech). Tuto nežádoucí vlastnost mají i profesionálně používané programy.

Zkoumáme cesty, jak dosáhnout obojích předností najednou. Možností je více: randomizace algoritmů, hledání výhodnějších transformací obvodu ("chytřejších", s "delším dosahem"), hledání alternativních cest ke konstrukci škálovatelných algoritmů, atd.

Toto je široké téma, které může být pokryto několika disertačními pracemi. Téma Petra Fišera "Rozšíření AIG (And-Inverter Graph) popisu logického obvodu o XOR prvky" je úžeji zaměřeným úsilím v témž směru.

Zákaznicky programovatelná hradlová pole (FPGA) nabízejí podstatné logistické výhody proti klasickým zákaznickým obvodům. Mohly by se stát prostředkem pro snížení ceny a času vývoje vestavných systémů. Zkonstruovat vysoce spolehlivý systém, který vyhoví pro bezpečnostně kritické aplikace je však obtížné, protože navrhujeme v prostředí které bylo zkonstruováno pro běžnou spolehlivost.

"Správná" metoda, jak situaci vyřešit, ja navrhnout obvod FPGA přímo určený pro spolehlivé aplikace. V rámci akademického výzkumu pochopitelně nenajdeme stovky člověkoroků potřebných pro finální návrh vyrobitelného FPGA čipu. Nicméně existuje cesta, jak je možno podstatně přispět k vývoji v tomto směru.

Systém VPR [1][2][3] byl navržen pro experimentální vyhodnocení FPGA architektur s ohledem na využití zdrojů, dosažitelnou hustotu funkce apod. Existují "virtuální" modely FPGA, na kterých tento systém umí rozmístit a propojit libovolný návrh. Tyto modely jsou dosti podrobné, aby bylo možno pracovat s poruchami na úrovni tranzistorů, a tedy vyhodnotit odolnost navržené architektury proti degradujícím vlivům. Na rozdíl od produkčního čipu, konstrukce demonstračního a ověřovacího čipu je dosti dobře možná v laboratoři IMEC (program Eurochip) nebo i jinde.

Reference

1. Vaughn Betz, Jonathan Rose and Alexander (Sandy) Marquardt: Architecture and CAD for Deep-Submicron FPGAs. ISBN 0-7923-8460-1. Kluwer, 2000
2. Vaughn Betz and Jonathan Rose: VPR: A New Packing, Placement and Routing Tool for FPGA Research. 1997 International Workshop on Field Programmable Logic and Applications, Springer, 1997
3. University of Toronto: VPR and T-VPack 5.0.2: Full CAD Flow for Heterogeneous FPGAs. http://www.eecg.utoronto.ca/vpr/

Zákaznicky programovatelná hradlová pole (FPGA) nabízejí podstatné logistické výhody proti klasickým zákaznickým obvodům. Mohly by se stát prostředkem pro snížení ceny a času vývoje vestavných systémů. Chybí však metody návrhu pro bezpečnostně kritické obvody.

Těžiště práce je v návrhu architektury nebo architektur pro konstrukci spolehlivých systémů na FPGA. Je zapotřebí pokrýt více oblastí: algoritmy rekonfigurace, výpočet spolehlivostních modelů a synchronizace stavu po rekonfiguraci.

Rentgenová strukturní analýza z práškových difrakčních dat je významná analytická metoda pro určení struktury látky v případě kdy látka neposkytuje monokrystal. Pro aplikaci metody je klíčová indexace dat – určení mřížkových parametrů. Existující algoritmy a postupy pro indexaci mají problém indexovat méně kvalitní data a směsi látek. Cílem práce je vyvinout algoritmy, které by za cenu vyšších nároků na výpočetní výkon, než stávající algoritmy, tento problém řešily. K ověření bude provedena i implementace algoritmů s využitím paralelního zpracování.

Průzkum možností provádění operací lineární algebry na výpočetní platformě typu klastru grafických karet.

The complexity of next-generation retrieval systems originates from the requirement to organize massive and ever growing volumes of heterogeneous data and meta-data, together with the need to provide distributed management prevalently based on similarity matching. The problem starts with data acquisition of weakly structured or completely unstructured data, such as images and video, which necessarily need innovative techniques for information extraction and classification to increase their findability. In principle, we consider the object findability and the actual search process as two fundamental and synergic aspects of the retrieval. Both of them pose effectiveness and efficiency challenges which need innovative theories and technologies, and must be studied together to converge to qualitatively new retrieval tools of the future. The dissertation topic is foundational in nature as it addresses the theoretical limits of similarity retrieval in context of the Big Data problem. Fundamental to the thesis is the development of scalable solutions.

Symbolické dynamické systémy jsou dynamické systémy nad množinami nekonečných posloupností (slov) s velmi jednoduchou operací posunutí (shift). Speciální podmnožinou jsou systémy vzniklé z S-adických systémů nebo systémů vícerozměrných řetězových zlomků. Mnoho algoritmů, které se zabývají zkoumáním kombinatorických vlastností těchto systémů a jejich prvků, má exponenciální složitost v délce analyzované konečné části slova (faktoru). Práce by se zabývala navrhováním efektivních datových struktur a algoritmů sloužících pro analýzu vlastností těchto systémů: například vypisování prvků konečné délky, vykreslování přidruženého dláždění, testování rozpoznatelnosti (recognizability) a souvisejích vlastností, modelování souvisejícího numeračního systému, rychlost konvergence vícerozměrného řetězového zlomku atd.

Výzkum v rámci tohoto tématu bude zaměřen na hledání řešení vybraných problémů v umělé inteligenci pomocí redukce na problém splnitelnosti [1]. Mezi problémy, které přestavují vhodné kandidáty pro tento způsob řešení, patří doménově závislé plánování (například hledání cest, plánování pro roboty) [2], rozvrhování, návrh obvodů, nebo kombinatorické úlohy. Pojem splnitelnost zde chápeme v širším smyslu, tj. nikoli pouze jako základní výrokovou splnitelnost (problém SAT), ale zahrnujeme i obecnější splňování podmínek (constraint satisfaction) [3], či kombinace splnitelnosti v různých logických teoriích (SAT-modulo theory – SMT) [4].

Reference

1. Armin Biere, Marijn Heule, Hans van Maaren, Toby Walsh: Handbook of Satisfiability. Frontiers in Artificial Intelligence and Applications 185, IOS Press 2009.
2. Pavel Surynek: Time-expanded graph-based propositional encodings for makespan-optimal solving of cooperative path finding problems. Ann. Math. Artif. Intell. 81(3-4): pp. 329-375, 2017.
3. Francesca Rossi, Peter van Beek, Toby Walsh: Handbook of Constraint Programming. Foundations of Artificial Intelligence 2, Elsevier 2006.
4. Daniel Kroening, Ofer Strichman: Decision Procedures - An Algorithmic Point of View, Second Edition. Texts in Theoretical Computer Science. An EATCS Series, Springer 2016.

Cílem výzkumu je návrh nových konceptů a souvisejících řešících algoritmů pro multi-agentní hledání cest (Multi-Agent Path Finding) [1]. V základní variantě problému MAPF hledáme cesty pro agenty pohybující se po neorientovaném grafu tak, aby každý agent dorazil do svého cíle ze zadané počáteční pozice, a přitom se nesrazil s žádným jiným agentem. Současné řešící techniky pro MAPF zahrnují škálu metod od sub-optimálních polynomiálních algoritmů [2] přes optimální algoritmy založené na prohledávání stavového prostoru [3] po transformace do jiných formalismů jako je SAT [4]. Otevřené otázky nabízejí zejména zobecněné varianty problému MAPF, kde uvažujeme navíc například komplexnější vzájemné vyhýbání, udržování formací, souvislosti či jiných globálních vlastností (vlastnost jež zahrnuje všechny agenty), zobecněné cenové funkce či více nezávislých (soupeřících) týmů agentů.

Reference

1. David Silver, “Cooperative pathfinding,” Proceedings of AIIDE, pp. 117–122, 2005.
2. Boris de Wilde, Adriaan ter Mors, Cees Witteveen: Push and Rotate: a Complete Multi-agent Pathfinding Algorithm. J. Artif. Intell. Res. 51: pp. 443-492, 2014.
3. Guni Sharon, Roni Stern, Meir Goldenberg, Ariel Felner: The increasing cost tree search for optimal multi-agent pathfinding. Artif. Intell. 195, pp. 470-495, 2013.
4. Pavel Surynek, Ariel Felner, Roni Stern, Eli Boyarski: Efficient SAT Approach to Multi-Agent Path Finding Under the Sum of Costs Objective. Proceedings of ECAI, pp. 810-818, 2016.

V současné době existují knihovny algoritmů, které umožňují řešit rozsáhlé řídké soustavy lineárních rovnic na masivně paralelních superpočítačích a klastrech. Matice koeficientů jsou rozdělené a mapované do pamětí výpočetních uzlů těchto počítačů, kde jsou uloženy pomocí paměťových formátů pro řídké matice (sparse matrix storage formats, SMSF). Problematiku SMSF jsme shrnuli v přehledovém článku Langr, Tvrdik: Evaluation Criteria for Sparse Matrix Storage Formats. IEEE Trans. Parallel Distrib. Syst. 27(2): 428-440 (2016). U většiny aplikací se rozměry matice během výpočtu nemění. Existují ale třídy problémů, kde se během typicky iteračního výpočtu soustava rovnic mění. Například dochází k expanzi soustavy vkládáním nových řádků do matice koeficientů a přidáváním odpovídajících proměnných soustavy nebo naopak redukce soustavy ubíráním řádků z matice koeficientů. V případě symetrické matice koeficientů to znamená současné vkládání či odebírání jejich sloupců. Tento proces expanze či redukce se může během paralelního iterativního výpočtu opakovat.

Cílem dizertační práce je výzkum paměťově úsporných SMSF a výpočetně efektivních a škálovatelných metod pro práci s elastickými řídkými maticemi. Úkolem je navrhnout a implementačně ověřit vhodné mapovací funkce pro elastické matice na multiprocesorovém systému s distribuovanou pamětí, vnitřní SMSF a algoritmy pro přemapování expandujících nebo redukovaných matic. Práce na tomto projektu je podpořena 5letým projektem OP VVV CRI a studenti získají přístup a budou moci pracovat na nejvýkonnějších superpočítačích na světě.

Školitel specialista – Ing. Daniel Langr, Ph.D.

Moderní superpočítače jsou charakterizovány stálým růstem výpočetního výkonu díky zvyšujícímu počtu jader na procesor a vyšší integraci, přičemž paměťová kapacita stagnuje. Pro vysoce výkonné výpočty (High-Performance Computing, HPC) to znamená, že paměťová kapacita a latence neškáluje adekvátně nárůstu výpočetního výkonu. Náročné simulační výpočty a modelovaní dnes vedou na obrovské řídké matice, které se z výše popsaných důvodů se nevejdou do jejich hlavní paměti. Tato situace vede na řadu výzkumných problémů, jak takové výpočty realizovat. Téma dizertační práce zahrnuje výzkum nových algoritmů a reprezentací takových obrovských řídkých matic řešených na superpočítačích a výpočetních klastrech. Možná dizertační výzkumná témata jsou paralelní optimalizační heuristiky pro on-the-fly výpočty prvků takových řídkých matic bez nutnosti jejich ukládání na disk a do paměti, heuristiky pro dynamické ukládání výpočetně nejnáročnějších prvků nebo heuristiky pro vyvažování těchto optimalizovaných výpočtů v rámci jader a výpočetních uzlů. Výzkum je podpořen grantem OP VVV Výzkumné centrum informatiky.

Řídké matice se ukládají do paměti počítačů v souřadnicovém (COO) nebo řádkově komprimovaném (CSR) formátu. Kromě těchto základních formátů bylo vyvinuto mnoho dalších paměťových formátů pro řídké matice (sparse matrix storage formats, SMSF). Tuto problematiku jsme shrnuli v přehledovém článku Langr, Tvrdik: Evaluation Criteria for Sparse Matrix Storage Formats. IEEE Trans. Parallel Distrib. Syst. 27(2): 428-440 (2016). Vhodnost a vlastnosti jednotlivých SMSF pro různé třídy vědeckých výpočtů závisejí na struktuře řídké matice. Abychom minimalizovali např. paměťovou náročnost uložení velké řídké matice na paralelním počítači se sdílenou nebo distribuovanou pamětí, je vhodné převést řídké matice namapované na paralelní počítač z těchto základních SMSF na úspornější blokové formáty, což typicky znamená dekompozici na pokud možno husté čtvercové submatice pokud možno podobné velikosti. Úlohu transformace SMSF je třeba řešit pro rozsáhlé řídké matice, které jsou distribuovány v pamětech uzlů paralelního počítače. Výpočty nad řídkými maticemi dat jsou ze své podstaty iterační a vyžadují několik průchodů distribuovanými daty reprezentujícími strukturu řídké matice. Jejich klíčovou komponentou je řazení. Optimalizace velikosti bloků vyžaduje opakované paralelní řazení dat popisující strukturu řídkosti matice podle různých klíčů.

Cílem dizertační práce je výzkum paralelních algoritmů pro efektivní a škálovatelné transformace velkých řídkých matic v základních SMSF na blokové. Práce na tomto projektu je podpořena 5letým projektem OP VVV CRI a studenti získají přístup a budou moci pracovat na nejvýkonnějších superpočítačích na světě.

Moderní architektornické styly pro návrh aplikací a služeb. Metody pro zajištění dobrého výkonu aplikací (škálovatelnost a dostupnost). Jazyky pro reprezentaci rozhraní aplikací na informační, procesní a technologické vrstvě. Metody pro analýzu sociálních sítí.

Principy a technologie propojených dat, životní cyklus propojených dat. Jazyky a nástroje pro publikování, propojování a využívání strukturovaných dat na webu, srovnání s webovými API. Jazyky pro reprezentaci sémantiky dat.

Odvozování v deskripční logice a jeho aplikace ve webovém prostředí. Vztah strukturovaných dat na webu a extrakce informací z textu/HTML.