Otázky ke státní závěrečné zkoušce magisterského studia Aplikovaná informatika

Teoretická informatika a programování (TIP) 

Akademický rok 2013/2014

1. Regulární gramatiky a konečné automaty

Základní pojmy teorie formálních jazyků, regulární výrazy, regulární gramatiky. Deterministické a nedeterministické konečné automaty, reprezentace konečných automatů. Vzájemný vztah regulárních jazyků a konečných automatů, iterační lemma, praktické využití regulárních jazyků.

2. Zásobníkové automaty a bezkontextové gramatiky

Chomského hierarchie gramatik, bezkontextové gramatiky, derivační stromy, zásobníkové automaty, přijímání prázdným zásobníkem a koncovým stavem, iterační (pumping) lemma, vzájemný vztah bezkontextových jazyků a zásobníkových automatů.

3. Turingovy stroje

Turingův stroj, varianty Turingových strojů, univerzální Turingův stroj. Rozhodnutelnost vs. rozpoznatelnost jazyka, Church-Turingova teze, problém zastavení Turingova stroje a další algoritmicky nerozhodnutelné problémy.

4. Teorie složitosti

Časová složitost, analýza algoritmu, asymptotická složitost algoritmu. Definice tříd P a NP, polynomiální převoditelnost problémů, pojem NP-úplnosti, příklady NP-úplných úloh, praktické důsledky.

5. Inversion of Control (IoC)

Principy, význam a použití přístupu, vztah IoC a  Dependency Injection. Příklady použití, nástroje podporující IoC.

6.  Servisně orientovaná architektura (SOA) a webové služby

Principy SOA a WS, vzájemný vztah. Nejpoužívanější standardy WS, SOAP, XML, XML-Schema, WSDL. Nástroje pro tvorbu WS.

7. Matematické principy počítačové grafiky

Vektorový prostor, báze, afinní prostor, soustavy souřadnic, lineární transformace, projekce, matice a kvaternióny.

8. HW principy zobrazování

Zobrazovací řetězec, vertex a pixel shader, softwarové prostředky pro využití, způsoby předávání dat, výpočetní výkon, využití pro negrafické výpočty.

9. Vizualizace dat

Datové struktury a reprezentace, vizualizace objemových dat, částicové systémy, úroveň detailu, redukce složitosti scény.

10. Obrazová data

Rastrová reprezentace, interpretace pixelu, vzorkování a alias, zpracování a úprava obrazu, filtrace, matematická morfologie

11. Multiagentové systémy

Agent, jeho charakteristiky, prostředí agenta. Reaktivní agent, emergence, modely inspirované biologií. Uvažující agent a jeho architektura, učení agenta. Aplikační oblasti multiagentovýchsystémů, RoboCup a RoboRescue.

12. Rozhodování, komunikace a koordinace v multi-agentovém systému

Teorie her, druhy her, reprezentace hry, vězňovo dilema, volba strategie, Nashova rovnováha. Částečně pozorovatelný svět, reaktivní komunikace, teorie řečových aktů, KQML a FIPA-ACL, koordinační mechanismy, aukce, tabulová architektura, negociace.