Master Degree Exam Requirements

Applied Informatics

Theoretical Informatics and Programming

2013/2014

1. Finite automata and regular grammars

Finite automata, iteration lemma, reduction and normalization of finite automata, non-deterministic finite automata. Regular expressions, Kleene’s theorem, transformation of regular expression into automata and transformation of finite automata into regular expression.

2. Pushdown automata and context-free grammars

Chomsky hierarchy, context-free languages, derivation trees, pushdown automata, iteration (pumping) lemma for context-free languages, interrelationship of pushdown automata and context-free languages.

3. Turing machines and non-context-free grammars

Non-context-free languages, Turing machines, variants of Turing machines, definition of algorithm, universal Turing machine, decidable problems, the halting problem, undecidable problems and their implications.

4. Theory of complexity

Time complexity, algorithm analysis, definition of P and NP classes, polynomial reducibility, NP-complexity, examples of NP-complete problems and NP-hard problems.

5. Inversion of Control (IoC)

Principles, objectives and usage of such approach, relationship between IoC and Dependency Injection. Examples of usage, tools that support IoC.

6. Service Oriented Architecture (SOA) and Web Services (WS)

Principles of SOA and WS, relationship between them. Most widely used standards WS, SOAP, XML, XML-Schema, WSDL. Tools that support WS development.

7. Mathematical Principles of Computer Graphics

Vector space, basis, affine space, coordinate systems, linear transformation, projection, matrices and quaternions

8. HW Principles of Computer Graphics

Rendering pipeline, vertex and pixel shader, APIs, data formats, computational performance, general purpose usage

9. Data Visualization

Data structures and representation, volume data visualization, particle systems, level of detail, scene complexity reduction

10. Image Data

Raster representation, pixel interpretation, sampling and aliasing, image processing, filtering, mathematical morphology

11. Multi-agent systems

Agent, its properties and environment, reactive agent, emergence, agents inspired by biological models. Reasoning agent, its architectures, learning in agent system. Application areas of multi-agent systems, RoboCup, RoboRescue.

12. Decision making, communication and coordination in multi-agent system

Game theory, types of games, representation of game, prisoner’s dilemma, strategy, Nash equilibrium, partially observable world, reactive communication, speech act theory, KQML andFIPA-ACL, coordination techniques, auctions, blackboard architecture, negotiation.