Tematické okruhy otázek ke státní doktorské zkoušce
Informatika a výpočetní technika

Společný teoretický základ

Počítačová komunikace

Vlastnosti komunikačních kanálů, mechanizmy a protokoly ochrany proti chybám, popis, ověřování a verifikace komunikačních protokolů. Sdílení přenosového média, chování metod přístupu v lokálních a bezdrátových sítích. Adresace, směrovací algoritmy a jejich využití v přepojovacích sítích. Chování sítě při zátěži, požadavky na kvalitu služby, ochrana proti zahlcení, interní a koncové řízení toku, rozklad datových toků. Mechanismy kryptografické ochrany přenosu dat a mechanismy autentizace.

Mobilita

Architektura mobilních systémů, sítě s infrastrukturou a ad-hoc sítě, optimalizace topologie. Technické prostředky mobilních sítí, výstavba a automatická (re)konfigurace. Směrování v mobilních sítích s infrastrukturou a v ad-hoc sítích, optimalizace spotřeby, přenosové kapacity, zpoždění, využití skupinové komunikace. Podpora mobility v Internetu a VoIP sítích. Podpora mobility v systémech middleware - mobilní agenti, mobilní transakce. Efektivní ukládání, vyhledávání a správa informace v rozsáhlých mobilních systémech. Autonomie a kooperace v mobilních systémech, zajištění konzistence. Spolehlivostní a bezpečnostní aspekty mobilních systémů.

Algoritmy a datové struktury

Formální modely a vyčíslitelnost, nerozhodnutelnost, formální jazyky a gramatiky, výpočetní modely, techniky návrhu algoritmů (rozděl a panuj, hledání s návratem, hladové algoritmy, dynamické programování), analýza složitosti algoritmů, specifikace a implementace datových struktur, pravděpodobnostní algoritmy, algoritmy pro vyhledávání v textu, grafové a síťové algoritmy, algoritmy výpočetní geometrie, základní algebraické algoritmy, teorie složitosti, třídy složitosti, paralelní algoritmy.

Distribuované výpočty

Komunikační mechanizmy - výměna zpráv, procedurální komunikace (RPC, ORB, SOAP), distribuovaná sdílená paměť. Modely výpočtu - spolupracující automaty, sítě s přechody, Petriho sítě, algebry procesů - CSP, CCS a pi-kalkul. Distribuovaný výpočet, globální stav, kauzalita, logický čas. Algoritmy výlučného přístupu, výběru, detekce a prevence zablokování, ukončení výpočtu. Výpadky prvků, odolnost proti chybám, quorum algoritmy, replikace, mobilita.Cloud a grid architektury.

Programovací jazyky a styly

Principy objektově orientovaného paradigmatu a základní pojmy objektově orientovaného programování (objekt, zpráva, třída, posílání zpráv, polymorfismus, dědičnost, pozdní vazba), možné vztahy mezi objekty (is_a, has_a) a třídami. Funkcionální programování, lambda kalkul, základy teorie rekurzivních funkcí, teorie pevného bodu, logické programování, principy jazyků LISP a PROLOG a jejich implementace.

Formální jazyky a sémantika

Syntaktická analýza, LL a LR gramatiky. Formální překlad při LL a LR analýze. Atributovaný překlad při LL a LR analýze. Překlady složitějších jazykových konstrukcí. Zpracování chyb. Optimalizace. Generování cílového programu. Matematické modely sémantických domén. Sémantické interpretace syntaktických konstrukcí. Příklady sémantiky typických jazykových konstrukcí. Vztah definice sémantiky a překladu, korektnost překladu.

Databázové a informační systémy

Konceptuální datové modely, ER-model, entity, atributy, definice domén atributů, vztahy, integritní omezení, grafické vyjádření. Logické datové modely, relační model, objektový model, funkční závislosti, normální formy. Návrh relačního schématu ve 3. NF dekompozicí z univerzální relace. Návrh relačního schématu syntézou dle Bernsteina. Vyjádření integritních omezení pro entitní typy. Vyjádření integritních omezení pro vztahové typy. Primární klíč, unikátní klíč, cizí klíč, referenční integrita. Dotazovací jazyky, vyjádření dotazu výrazem relační algebry, jazyk SQL. Architektury databázových systémů, centralizované a distribuované databázové systémy, SŘBD, DB server, DB klient, distribuce dat, replikace dat, víceuživatelské DB systémy. Transakční zpracování, transakce, potvrzování a odvolávání změn, zajištění konzistence dat při paralelním přístupu. Fyzická reprezentace dat, záznam, soubor, tabulka, index, techniky ukládání a přístupu k záznamům, B-stromy.

Softwarové inženýrství

Životní cyklus programového díla, fáze sběru požadavků, analýzy, návrhu, implementace, provozu a údržby. Datová a funkční analýza. Konceptuální modely používané pro dokumentaci analýzy a jejich souvislosti. Logické modely používané pro dokumentaci návrhu, jejich souvislosti a možnosti odvození z analytických modelů. Programová dokumentace implementace. Metodiky a prezentační techniky softwarového inženýrství. Převod konceptuálních modelů na logické a jejich implementace. Strukturované technologie, objektově-orientované technologie, komponentové technologie, technologie pro síťové aplikace. Testování, validace a verifikace, provoz a údržba programového díla. Projektování jako disciplína softwarového inženýrství, projektová dokumentace, metody řízení projektů, analýza a řízení rizik, zajištění kvality projektu, metriky.

Speciální okruhy

Umělá inteligence a automatické plánování

Grafy. Kombinatorické algoritmy a jejich složitost. Výroková logika a predikátová logika prvního řádu. Formální systém, teorie a jejich korektnost a úplnost. Definice, reprezentace a složitost plánovacího problému. Prohledávací algoritmy (DFS, BFS, BestFS, A*, CSP). Heuristiky - konzistence/monoticita, přípustnost, relaxace a abstrakce. Grafově orientované plánování. Evoluční výpočetní techniky. Simulované žíhání. Swarm inteligence - optimalizace hejnem částic a pomocí mravenčích kolonií. Sekvenční rozhodovací problémy - MDP, POMDP a jejich řešení.

Multiagentní systémy a teorie her

Formální modely autonomních agentů a multiagentních systémů. Řídicí architektury agentů, architektura BDI. Distribuované řešení úloh, DCSP a DCOP. Multiagentní plánování. Hry v normalní a extenzivní formě. Koncepty řešení her, složitost jejich výpočtu a algoritmy pro jejich nalezení. Systematické a vzorkovací algoritmy prohledávání herních stromů. Koaliční teorie her. Návrh mechanismů (mechanism design). Aukční mechanismy a jejich vlastnosti. Teorie veřejné volby, hlasovací protokoly. Sekvenční rozhodování v multiagentních systémech (DEC-POMDP). Agentní modelování a simulace.

Výpočetní robotika

Výpočetní složitost. Turingův a Kolmogorův stroj. Aproximační algoritmy. Pravděpodobnostní plánování a plánování vzorkováním. Plánování pohybu s uvažováním kinematických, kinodynamický a dynamických omezení. Reprezentace prostoru (diskrétní, geometrická, C-space). Potenciální pole a navigační funkce. Modely senzorů. Behaviorální modely autonomního chování robotů. Optimální návrh vzorkování, plánování rozmístění senzorů a sběru dat (informativní plánování pohybu). Samo-organizace a inteligence hejna v optimalizačních úlohách kolektivních autonomních systémů.

Strojové učení a analýza dat

Definice problému učení. Induktivní učení konceptů a role zaujetí v učení. Výpočetní teorie učení, PAC naučitelnost, konečné a nekonečné hypotézové prostory. Vyhodnocení hypotéz, empirické a strukturální riziko, regularizace, statistické srovnání klasifikačních algoritmů. Konkrétní algoritmy učení: lineární regrese, pravidlové modely, neuronové sítě, bayesovské sítě, support vector machines a složené modely. Základní přístupy k učení nad rámec induktivního učení z příkladů (analytické deduktivní učení, posilované učení, učení bez učitele).

Počítačová grafika

Proximity problémy, konstrukce Voronoiova diagramu ve dvou a vícerozměrném prostoru, vyhledávání ve Voronoiových diagramech, Voronoiovy diagramy vyššího řádu. 2D a 3D triangulace, Delaunayova triangulace, triangulace s minimální váhou. Inverzní a duální geometrické transformace. Víceuživatelská virtuální realita. Algoritmy globálního osvětlování. Řešení výpočtů na GPU, architektura GPU, paralelizace grafických algoritmů.

Uživatelská rozhraní

Návrh uživatelských rozhraní ve spolupráci s uživateli (User Centered Design). Architektura modulů uživatelských rozhraní. Formální popisy uživatelských rozhraní a jejich využití při jejich návrhu. Problémy vnímání grafické informace a jejího zpracování uživatelem. Reprezentace 2D a 3D informace z hlediska návrhu sofistikovaných uživatelských rozhraní. Datové struktury pro vizualizaci dat. Uživatelská rozhraní pro vizualizaci dat (Vizualizace objemových dat. Vizualizace dynamických jevů, Vizualizace informace). Problematika návrhu speciálních uživatelských rozhraní (postižení uživatelé, mobilní aplikace, multimodální rozhraní.). Problematika standardů v oblasti uživatelských rozhraní. Speciální metody vstupu textu (například v mobilním prostředí, iDTV, pro uživatele s omezením). Adaptivní uživatelská rozhraní řízená kontextem. Nomádické aplikace.

Neuronové a fuzzy systémy

Analogové a hybridní implementace neuronových sítí, realizace paměti vah, algoritmy učení - metoda perturbace. Číslicové implementace neuronových sítí. Neuročipy s binárními neurony, perceptrony a RBF neurony. Implementace aktivačních funkcí neuronů a učících metod. Obvodová implementace fuzzy logiky, fuzzy procesory.

Neuronové sítě

Teoretické základy umělých neuronových sítí, klasifikace paradigmat. Učení umělých neuronových sítí. Metody učení s učitelem i bez učitele. Metody řešení problému uváznutí v lokálním minimu. Získávání znalostí z dat, induktivní modelování. Samoorganizace jako prostředek pro objevování vztahů mezi objekty. Visualizace rozsáhlých a multidimenzionálních datových souborů. Automatická konstrukce modelů metodami umělé inteligence.

Výpočetní geometrie

Vektorový afinní a Euklidovský prostor, homogenní souřadnicová soustava, afinní transformace. Programátorská paradigmata zametací technika, rozděl a panuj, prořezávej a hledej, geometrické místo bodů, dynamické programování, genetické algoritmy, datové struktury pro vícerozměrné vyhledávání. Geometrické vyhledávání, konvexní obálka ve 2D a 3D prostoru. Proximity problémy, konstrukce Voronoiova diagramu ve dvou a vícerozměrném prostoru, vyhledávání ve Voronoiovu diagramu, Voronoiovy diagramy vyššího řádu. 2D a 3D triangulace, Delaunayova triangulace, triangulace s minimální váhou. Průsečíky geometrických objektů, algebra polygonálních oblastí, geometrie rovnoběžníků. Inverzní a duální geometrické transformace.

Virtuální realita a zobrazovací metody

Systémy virtuální reality (VR), víceuživatelská VR, technické prostředky pro VR, modelování a animace virtuálních postav. Standardy VRML a X3D, rozhraní EAI, 3D grafika a vizualizace na webu. Pokročilé metody zobrazování, sledování paprsku, radiozita, datové struktury pro urychlování výpočtů, detekce kolizí. 3D grafické akcelerátory.

Webové inženýrství

Hypermediální systémy, základní modely. Inteligentní vyhledávání, adaptivní navigace, personalizace přístupu. Webová inteligence, sémantický web. Webové inženýrství, jeho složky a východiska. Moderní technologie pro návrh webových aplikací.

Za obsah odpovídá: RNDr. Patrik Mottl, Ph.D.