Faculty of Electrical Engineering

Czech Technical University in Prague

CTU in Prague

State doctoral exam topics

Information Science and Computer Engineering

 

General topics

Communication and Computers

Properties of communication channels, methods and protocols for protection from errors, description, and verification of communication protocols. Shared medium, behavior of access methods in local and wireless networks. Addressing, routing algorithms and their use in polygonal networks.  Network behavior under load , requirements for quality of services, protection from network congestion, internal and terminal network flow,  flow bifurcation. Cryptographic methods for data transfer and authentication methods.

Mobile Systems

Architecture of mobile systems, networks with infrastructure and ad-hoc networks, topology optimization. Technical means for mobile networks, networks build-up and their (re)configuration. Routing in mobile networks with infrastructure and in ad-hoc networks. Consumption optimization, network transfer capacity, delay, use of communication in groups. Mobility in Internet and VoIP networks. Mobility support in middleware systems – mobile agents, mobile transactions. Efficient storing, retrieval and management of information in large mobile systems. Autonomy and cooperation in mobile systems, consistency control. Security and reliability aspects of mobile systems.

Algorithms and Data Structures

Formal models and computability,  undecidability, formal languages and grammars, computational models, methods for algorithm design (divide and conquer, backtracking, greedy algorithms, dynamic programming), complexity analysis of algorithms, specification and implementation of data structures, probabilistic algorithms, string searching algorithms, algorithms for graphs and networks, algorithms in computational geometry, fundamental algebraic algorithms, complexity theory, parallel algorithms.

Distributed Computing

Communication tools – message exchange, procedural communication (RPC, ORB, SOAP), distributed shared memory. Execution models - cooperating automata, transition networks. Petri nets, process algebras – CSP, CCS and pi-calculus. Distributed computation, global snapshot, causality, logical time. Algorithm of exclusive access, selection, detection and prevention of deadlock, termination of calculation. Drop-outs, error resistence, quorum algorithms, replication, mobility. Cloud and grid architectures.

Programming Languages and Styles

Principles of object oriented paradigm and basic terms in object oriented programming (object, message, class, sending messages, polymorfism, inheritance, late binding), possible relations between objects (is a, has a) and classes. Functional programming, lambda calculus, fundamentals of theory of recursive functions, fixed point theory, logical programming, principles of LISP and PROLOG programming languages and their implementation.

Formal Languages and Semantics

Syntactic analysis, LL and LR grammars. Formal translation directed by LL and LR parsing. Attributed translation directed by  LL and LR parsing. Translation of non-trivial language constructs. Error recovery. Optimization. Generation of target program. Mathematical models of semantic domains. Semantic interpretation of syntactic constructs. Examples of semantics in typical language constructs. Relation between semantics and translation, translation correctness. 

Databases and Information Systems

Conceptual data models, E-R model, entities, attributes, definition of attribute domains, relationships, integrity constraints, graphical notations. Logical data models, relational model, object model, functional dependencies, normal forms. Design of relation scheme in the 3rd NF by means of decomposition from universal relation. Design of relation scheme by means of Bernstein decomposition. Integrity constraints for entities and relationships. Primary key, unique key, foreign key, referential integrity. Query languages, query as an expression in relational algebra, SQL language. Architecture of database systems, centralized and decentralized systems, DB server, DB client, data distribution, data replication, multiuser database systems. Transaction processing, commitment and revocation of changes, data consistency by parallel processing. Physical data representation, record, file, table, index, methods for record storage and retrieval, B-trees.

Software Engineering

Life cycle of software products, requirement specification, analysis, design, implementation, deployment and maintenance. Data-oriented analysis. Function-oriented  analysis.  Conceptual models used in analytical documentation and their mutual dependencies. Logical models used for design documentation, their inference from analytical models. Software documentation, implementation. Methodologies and presentation techniques of software engineering. Transformation of conceptual models  to logical ones and their implementation. Structured technologies, object oriented technologies, component technologies, technologies for network applications. Testing, validation and verification, exploitation and maintenance of software product. Software development as the discipline of  software engineering, software documentation, methods of project management, risk analysis, risk analysis, management of project quality, metrics.

 

Special topics

Artificial Intelligence and Automatic Planning

Graphs. Combinatorial algorithms and their complexity.  Propositional calculus and predicate first-order logic. Formal system, theories - their validity and completeness. Definition, representation and complexity of planning problem. Search algorithms (DFS, BFS, BestFS, A*,  CSP). Heuristics – consistency/monotonicity, admissibility, relaxation and abstraction. Graph oriented planning. Evolution techniques. Simulated annealing. Swarm intelligence – optimization by means of particle swarms and ant colonies. Sequential decision problems – MDP, POMDP and their solution.

Multiagent Systems and Game Theory

Formal models of autonomous agents and multiagent systems. Agent control architecture, BDI architecture. Distributed task solving, DCSP and DCOP. Multiagent planning. Games in normal and extensive form. Game solution concepts, their complexity and algorithms. Systematic and sampling algorithms for game tree search. Coalition game theory. Mechanism design. Auction mechanisms and their properties. Public choice, voting protocols. Sequential decision making in multiagent systems (DEC-POMDP). Agent modelling and simulation.  

Computational Robotics

Computational complexity. Turing and Kolmogorov machines. Approximation algorithms. Probability planning and sample planning.  Motion planning with consideration of kinematic, kinodynamic and dynamic constraints. Space representation (discrete, geometric, C-space). Potential field and navigation function.  Sensor models. Behavioral models of autonomous robot behavior. Optimal sampling design, sensor distribution planning, data gathering. Self-organization and swarm intelligence in optimisation tasks for collective autonomous systems.

Machine Learning and Data Analysis

Learning and its definition. Inductive concept learning and its role in biased learning. Computational theory of learning, PAC learnability, finite and infinite hypothesis spaces. Evaluation of hypothesis, empirical and structural risk, regularization, statistical comparison of classification algorithms. Learning algorithms: linear regression, rule models, neural networks, bayesian networks, support vector machines and compound models. Some basic approaches to learning exceeding inductive learning from examples (analytic deductive learning, reinforcement learning, unsupervised learning). Simulated annealing.

Computer Graphics

Proximity problems, Voronoi diagrams construction in multidimensional spaces, higher-order Voronoi diagrams, search in Voronoi diagrams. 2D and 3D triangulation, Delaunay triangulation, minimal weight triangulation. Inverse and dual geometric transformation. Multiuser virtual reality. Global illumination. GPU calculations, GPU architecture, parallelization of graphical algorithms.

User Interfaces

User interface design in cooperation with users (User Centered Design). Architecture of user interface modules. Formal description of user interfaces and their use for user interface design. Graphical information perception and its processing by a user. Representation of 2D and 3D information from the point of view of sophisticated user interface design. Data structures for data visualization. User interfaces for data visualization (Visualization of volume data, Visualization of dynamic phenomena, Information visualization). Design of special user interfaces (impaired users, mobile applications, multimodal user interfaces). Standards for user interfaces. Special text entry methods (e.g. in mobile environment, iDTV, impaired users). Adaptive user interfaces controlled by context. Nomadic applications.

Neural and Fuzzy Systems

Analog and hybrid implementation of neural networks, network function implementation, learning algorithms – perturbation methods. Digital implementation of neural networks. Neurochips with binary neurons, perceptrons and RBF neurons. Implementation of neuron activation functions and of learning methods. Circuit based implementation of fuzzy logic, fuzzy processors.

Neural Networks

Theoretical foundations of neural networks, paradigm classification. Training of artificial neural networks. Supervised and unsupervised learning. Local minimum traps and its solution. Data mining and inductive modelling. Selforganization as a mean for discovery of relations between objects. Visualization of extensive and multidimensional data sets. Automatic model construction by means of artificial intelligence methods.

Computational Geometry

Vector, affine and Euclidean space, homogeneous coordinate system, affine mapping. General algorithmic techniques plane sweep, Divide&Conquer, Prune and search, Locus approach, Dynamic programming, Genetic algorithms,. Data structures for multidimensional searching, Geometric searching, Convex Hulls in 2D and 3D, Proximity problem, Voronoi diagrams, Higher-order Voronoi diagrams, Delaunay triangulation, Minimal weight triangulation.

Intersections of geometric objects, Algebra of polygons. Geometry of rectangles. Dual geometrical transformations.

Virtual Reality and Rendering

Virtual reality (VR) systems, multi-user VR, hardware support for VR, humanoid modeling and animation. VRML and X3D standards, EAI interface, web-based 3D graphics and visualization. Advanced rendering techniques, ray-tracing, radiosity, auxiliary spatial data structures, collision detection algorithms. 3D graphics accelerators

Web Engineering

Hypermedia systems, basic models. Intelligent searching, adaptive navigation, access personalization to web. Web intelligence, semantic web. Web engineering, topics and principles. Modern technologies for web applications design.

 

 

Responsible person: RNDr. Patrik Mottl, Ph.D.