System Programming, focused on Theoretical Computer Science (1801T047)

Abbreviations

p-sz - obligatory module of common theoretical basis, obligatory for all specialisations,
pv-ob - elective branch module, obligatory for selected branches,
pv-za - elective specialisation module, obligatory for selected specialisations,
p-hu - obligatory humanity module,
p-em - iobligatory economical-management module,
p-pr - obligatory project,
pv-hu - elective humanity module,
v - elective module.

module (abbreviation) dimension completion type of module lecturer recom. year
Statistics for Informatics ( MIE-SPI ) 4+1 z,zk p-sz Blažek, Ph.D. 1.
Parallel Computer Architectures ( MIE-PAR ) 3+1 z,zk p-sz prof. Tvrdík 1.
Systems Theory ( MIE-TES ) 2+1 z,zk p-sz prof. Moos 1.
Parsing and Compilers ( MIE-SYP ) 2+1 z,zk pv-ob prof. Melichar 1.
Linear Optimization and Methods ( MIE-LOM ) 2+1 z,zk pv-za Černý, Ph.D. 1.
Cybernality ( MIE-KYB ) 2+0 zk p-hu doc. Jirovský 1.
Mathematics for Informatics ( MIE-MPI ) 4+1 z,zk p-sz doc. Šolcová 1.
Functional and Logical Programming ( MIE-FLP ) 2+1 z,zk pv-ob Janoušek, Ph.D. 1.
Advanced Algorithms ( MIE-PAL ) 2+1 z,zk pv-za prof. Kučera 1.
Automata in Text Pattern Matching ( MIE-AVY ) 2+1 z,zk pv-za prof. Melichar 1.
elective module 2+1 z,zk v 1.
elective module 2+1 z,zk v 1.
Project Management ( MIE-PRM ) 1+2 z p-em Vala 1.
Complexity Theory ( MIE-CPX ) 3+1 z,zk pv-ob prof. Kučera 2.
Computational Intelligence Methods ( MIE-MVI ) 2+1 z,zk pv-za Kordík, Ph.D. 2.
Nonlinear Continuous Optimization and Numerical Methods ( MIE-NON ) 2+1 z,zk pv-za doc. Kruis 2.
Master Project ( MIE-MPR ) z p-pr 2.
elective module 2+1 z,zk v 2.
elective module 2+1 z,zk v 2.
Information Security ( MIE-IBE ) 2+0 zk p-em Čermák, CSc. 2.
elective module 2+1 z,zk v 2.
IT Support to Business and CIO Role ( MIE-CIO ) 3+0 zk p-em prof. Dohnal 2.
obligatory humanity module zk pv-hu 2.
Master Thesis (MIE-DIP) z p-pr 2.

MIE-AVY - Automata in Text Pattern Matching

Annotation

The module deals with automata models of algorithms for text searching. The main topics are text pattern matching and repetitions. In both cases, both exact and inexact pattern matchings are considered. The fundamental formal tool for description of the algorithms is the finite automaton. The knowledge gained in this module can be applied in analysis and design of algorithms for text pattern matching.

Lectures program

  1. Text systems, basic notions, taxonomy of text pattern matching problems.
  2. Codirectional searching, models of searching algorithms.
  3. Nondeterministic search automata.
  4. Simulation of nondeterministic search automata, bit parallelism, dynamic programming.
  5. Prefix and suffix automata.
  6. Factor automata, factor oracle, suffix oracle.
  7. Boundaries and periods in texts.
  8. Repetitions in texts, exact and inexact.
  9. Simulation of nondeterministic search automata, fail function, the MP a KMP algorithms.
  10. Simulation of nondeterministic search algorithms, fail function, the AC algorithm.
  11. Contradirectional single pattern matching, the BM algorithm, the CW algorithm.
  12. State-of-the-art in text pattern matching (e.g., matching in a multidimensional text, searching in a compressed text).

MIE-CIO - IT Support to Business and CIO Role

Annotation

Students are introduced to the trends and challenges of ICT management. The module is focused on ICT support for the company business. Students are introduced to the importance of communication with business that will be illustrated on CRM.

Lectures program

  1. Introduction. IT trends and business support. CIO and CEO relationship. ICT Management (categorization, management models, services, processes).
  2. CIO role, responsibility. CIO Decision Cycle (business goals, innovation, strategy, plan, execution, measurement).
  3. The value chain and ICT support. Marketing and selling processes, business cycle.
  4. CIO priorities: Team management. Understanding of the business environment. ICT vision. Shape ICT demand and communicate expectations. IT Governance.
  5. CIO priorities: Bring business and ICT strategies together. Communication of the ICT value to business. Risk Management.
  6. CIO priorities: Creation of a new ICT. Change in the profile of ICT people. ICT competencies (technical, business, behavioral).
  7. ICT business cases on workforce (time management, meeting management, delegation).
  8. ICT business cases on workforce (appraisal, coaching, mentor, mentee).
  9. CRM as an example of ICT support of business processes. CRM and enterprise culture.
  10. CRM processes.
  11. CRM Technology. CRM innovation and the role of ICT.
  12. Specific tasks of ICT management (sourcing, cost cutting).
  13. Invited lecturer – CIO of a selected company, discussion.

MIE-CPX - Complexity Theory

Annotation

Provide a theoretical background for deciding whether a given problem is, according to our present knowledge, solvable and what kind of computational methods could be used.

Lectures program

  1. Models of computation.\r
  2. Algorithmic undecidability.\r
  3. Nondeterminism, the class NP, the existence of an NP-complete problem.\r
  4. NP-complete problems.\r
  5. Problem P=NP, relativization, classes coNP and NP intersection coNP.\r
  6. The class PSPACE, Savitch theorem, hierarchy in PSPACE.\r
  7. PSPACE-complete problem (quantified formulae and games), complete problem for the hierarchy classes.\r
  8. Circuit and algebraic complexity.\r
  9. Randomized algorithms, complexity classes of randomized algorithms (classes BPP, ZP, RP).\r
  10. One-way functions, pseudorandom sequences, discrete logarithm, cryptography.\r
  11. Interactive proofs, probabilistically verifiable proofs, expanders, gap problem, PCP theorem, non-aproximability of 3SAT.\r

MIE-FLP - Functional and Logical Programming

Annotation

The module deals with functional and logic programming. It explains basic principles and focuses on programming in Lisp and Prolog programming languages. Students learn the principles of implementation of Lisp and Prolog programming languages.

Lectures program

  1. Declarative programming languages. Lambda calculus as a formalism for functional programming.
  2. Basic data types and functions in Lisp, lists.
  3. Variables, type predicates, recursion and iteration in Lisp.
  4. Mapping functionals, control statements.
  5. Input and output, macros.
  6. Structures, vectors, arrays, hash tables.
  7. Implementation of Lisp.
  8. Predicate logic, Horns clauses and SLD resolutions as an introduction to Prolog.
  9. Predicates, clauses, facts, operators in Prolog.
  10. Control of the computation in Prolog, lists.
  11. Data structures, input, output.
  12. Implementation of Prolog.
  13. Logic programming and proof trees - relation to attributed grammars.

MIE-IBE - Information Security

Annotation

The field of information security governance in modern organizations and companies is of growing importance. The module is to provide students a good overview of methods and standards for informstion security. The aim of the module is to let the students understand the importance of information security governance, to provide them sufficient arguments for the support of ISMS implementation process and for successfull implementation and/or management of ISMS.

Lectures program

  1. Management, management and governance, IT management.
  2. Information security management system, IS/ICT governance, international standards on IS/ICT security, legislation in the Czech Republic.
  3. Risk management.
  4. Physical security, access control system, information resource valuation, internal and external threats, evaluation of countermeasures,
  5. Administration security (guidelines, training).
  6. Disaster recovery planning, business continuity management, incident management,
  7. IS/IT audits, application security testing, penetration testing, certifications.
  8. Certification according ISO 27001, Best practises (ISO 17999),
  9. Information security trends.

MIE-KYB - Cybernality

Annotation

The goal of this module is to provide knowledge of cyberspace attacks, systems for their monitoring and analysis, and an overview of a corresponding legislative. It also familiarizes students with principles of network attacks and means how to defend against them at the organization level.

Lectures program

  1. Basic leslative norms relevant for operation of computer systems and networks, basic notions.
  2. Classification of attacks.
  3. Systems for computer network operation monitoring.
  4. Cybernetic attacks, psychologic and social aspects of a cybernetic attack, life cycle of exploiting the system weaknesses.
  5. Hackers - hacker comunity, types and motivations of the hacker behaviour.
  6. Cyberterorism, its demonstration and methods.
  7. Principles of infoware, the role of intelligent agents, strategic information warfare.
  8. Principles of attacks on the web, trends of attacks and attackers, phases of an attack, coordination and management of an attack.
  9. Basic types of attacks - DoS, forged node, manipulation with address sequences.

MIE-LOM - Linear Optimization and Methods

Annotation

The aim of the module is to familiarize students with methods and algorithms for optimization and mathematical programming. It is focused on linear and integer optimization and its applications in distribution and allocation problems, data analysis, network design, modelling of conflicts using the game theory. Within seminars students work with professional optimization software and their programming languages.

Lectures program

  1. Classification of optimization techniques: linear and integer programming, nonlinear optimization, continuous optimization, special forms of linear programs, general convex programming, multicriteria optimization.
  2. Mathematical formulation of optimization problems (optimization and combinatorics, distribution, allocation, network, statistical problems, etc.).
  3. Models of conflicting situations, introduction to the game theory.
  4. Linear algebra: matrices and linear mappings, eigenvalues and eigenvectors, basic bounds, positive (semi)definiteness, $L_k$-norms, matrix norms.
  5. Fundamentals of theory of linear and integer programming and their geometry, forms of linear programs.
  6. The simplex algorithm.
  7. Duality in linear programming.
  8. Applications of duality in combinatorics and algorithmic design.
  9. Classifications of optimization problems using the complexity theory.
  10. The ellipsoid algorithm.
  11. Interior point algorithms.
  12. Algorithms for integer programming.
  13. Implementation issues (numerical stability, sparse matrices, approximate and exact solutions, date structures).

MIE-MPI - Mathematics for Informatics

Annotation

Mathematics as a language for description of the world is a key discipline for an informatics engineer. The aim of this module is introduce students to the relevant parts of modern mathematics that form the theoretical background of many informatics disciplines.

Lectures program

  1. [2] Universal algebra: groups, finite groups, Cayley tables, group types, permutation, alternating, cyclic, and symmetry groups, normal subgroups.
  2. Finite fields, prime order of field, rings and their properties, integral domain, ideal. Lattices.
  3. Introduction to category theory, classes of objects, classes of morphisms and its properties, examples of categories: grupoid, category of all lattices, category of all commutative groups, category of all integral domains, category of all relations. Homomorphisms.
  4. Selected problems of graph theory, types of Hamiltonian problems. Algebraic solutions of combinatorial problems, Polya enumeration theorem.
  5. Algebra and algorithms (Algorithms for calculations of polynom roots - Newton' method, Lehmer-Schur's method, etc.).
  6. Convex sets, convex hull, pure convex set, theorem on partition of convex sets, Minkowski theorem on projection.
  7. Selected problems of number theory, quadratic congruence, Gauss algorithms. Special primes - factorial, palindromic, cyclic, Gauss', Eisenstein's primes. Examples of applications.
  8. Properties of Fermat primes, Little Fermat Theorem, primality tests, Pépin test, number theory and geometry, constructability of polygons.
  9. Selected numerical methods, Lagrange and Hermite interpolation, numerical integration, numerical solution of ordinary differential equations, calculating of eigenvalues of matrices, methods of solving of linear equations systems.
  10. Fast algorithms: multiplication, numerical searching of square roots, Fourier transformation, Fermat transformation.
  11. Axiomatic systems and their properties, recursive functions, proofs in the axiomatic system, examples of axiomatic systems, Peano's arithmetics, von Neumann's model of numbers.
  12. Special logics, multi-valued logics, modal logics, fuzzy logics.

MIE-MVI - Computational Intelligence Methods

Annotation

The module gives an overview of basic methods and techniques of computational intelligence that stem from the classical artificial intelligence. Computational intelligence methods are mostly nature-inspired, parallel by nature, and applicable to many problems in knowledge engineering.

Lectures program

  1. Introduction to computational intelligence, its uses.
  2. Algorithms of machine learning.
  3. Neural networks.
  4. Evolutionary algorithms, evolution of neural networks.
  5. [3] Computational intelligence methods: for clustering, for classification, for modeling and prediction.
  6. Fuzzy logic.
  7. Swarms (PSO, ACO).
  8. Model grouping and combining.
  9. Inductive modeling.
  10. Quantum and DNA computing.
  11. Case studies, new trends.

MIE-NON - Nonlinear Continuous Optimization and Numerical Methods

Annotation

The module gives an introduction to continuous optimization with respect to the solution of complicated problems, e.g., data approximation or identification of model parameters. The second part deals with several parts of computational sciences, with the emphasis on the finite element method and the finite difference method which are massively used in all engineering branches, not only in academic community but also in industry.

Lectures program

  1. Partial derivative, gradient, hessian.
  2. Continuous optimization of the 1st and 2nd order.
  3. Quasi-Newton method, conjugate gradient method.
  4. Application of methods of nonlinear continuous optimization.
  5. Introduction to ordinary and partial differential equations (taxonomy, the notion of the solution, physical interpretation).
  6. Ordinary differential equations – boundary value problem (exact solution, finite difference method, finite differences).
  7. Ordinary differential equations – boundary value problem (finite element method).
  8. Partial differential equations – stationary cases (finite difference method).
  9. Partial differential equations – stationary cases (finite element method).
  10. Ordinary differential equations – initial value problem.
  11. Partial differential equations – nonstationary problems.
  12. Iterative methods (Gauss-Seidel method, conjugate gradient method).
  13. Introduction to domain decomposition methods. Parallel solvers of sets of linear equations.

MIE-PAL - Advanced Algorithms

Annotation

The goal is to give a list of the most important algorithms in different domains of computer science, to use them to illustrate general principles of the design of effective algorithms, and to show methods to cope with problems that, according to the present knowledge, are not solvable optimally in polynomially bounded time.

Lectures program

  1. Advanced algorithms for network flows.
  2. Matching: bipartite and general, minimum cost matching, parallel randomized algorithm.
  3. Planar graphs: planarity conditions, planarity testing, isomorphism of planar graphs.
  4. Digital signal processing: FFT and spectral compression.
  5. Geometric algorithms: convex hull, Voronoi diagram, and others.
  6. Streaming algorithms.
  7. Primality: randomized a deterministic testing, proof of primality.
  8. Approximation algorithms.
  9. Approximation schemes.
  10. Online algorithms.
  11. General heuristic methods: simulated annealing, tabu search, genetic algorithms.
  12. Specialized heuristic methods: spectral heuristics, TSP.
  13. Randomized algorithms and probabilistic analysis of algorithms.

MIE-PAR - Parallel Algorithms and Systems

Annotation

The aim of the course is to provide students with the theoretical background for parallel algorithmization that lets them design and implement algorithms for parallel systems, from multicore systems and systems-on-chip to clusters, understand their behavior and estimate performance characteristics.

Lectures program

  1. Performance characteristics of parallel computations.
  2. Models of parallel systems with shared memory.
  3. Interconnection networks of parallel computers.
  4. Embeddings and simulations of interconnection networks.
  5. Models for interprocessor communication and routing.
  6. Collective communication algorithms.
  7. Fundamental parallel algorithmics.
  8. Parallel sorting algorithms.
  9. Parallel algorithms for linear algebra.
  10. Parallel combinatorial space search.

MIE-PRM - Project Management

Annotation

Project management and project thinking became an integral part of management of projects of all kinds (research, development, finances, engineering, etc.). Knowledge of this field takes an important places in the process of recruitment. The aim of this subject is to acquaint student with all of the aspects of project management, refer to the relatated areas, introduce most important methodologies of PM and prepade students for the basic certification of theoretical knowledge of PM (e.g., IPMA – D grade). The most common and important software tools used in project management will also be introduced.

Lectures program

  1. Project management, project, process. Definition of project participants, aims, metrics, quantification, planning, budget.
  2. Role of the project manager (presentation, levels of communication, duties). Life cycle and stages of a project.
  3. Project documents. Pre-business and business stages of a project.
  4. Preparation and realization stages of a project. Operation and closure of a project.
  5. Stabilization of a project, feedback, control mechanisms (methodical, contractual, or matter-of-fact supervision), risk management.
  6. Contractual arrangement of a project, business negotations, quality of delivery (SLA, security), warranty.
  7. Demand, definition of services, evaluation of proposals, the act of public contracts, evaluation criteria.
  8. Financial control.
  9. Project team management - human resources (roles, CIO, conducting a meeting, written records, tasks).
  10. Management of large projects (by area, by volume). Multiproject enviroment (reporting, coordination).
  11. Principles of methodology of poject management – Prince2, PMI. Quality management of project according to norms ISO 10006, ISO 9001.
  12. Setting up project management to company (linear x project management, process management).
  13. Particularities of project management of IS development.

MIE-SPI - Statistics for Informatics

Annotation

The aim of the module is to provide an introduction to probability, information theory and stochastic processes. Furthermore, the module brings knowledge needed for data analysis and processing. It provides students with knowledge of computational methods and gets them acquainted with the use of statistical software.

Lectures program

  1. Basics of Probability Theory: Probability Space, Definitions, Properties, Sigma-continuity, etc.
  2. Basics of Probability Theory: Conditional Probability, Independence, Commented Examples
  3. Basics of Probability Theory: Random Variables, Cumulative Distribution Function, Probability Density Function, Dependence, Random Vectors, Marginal and Joint Distribution
  4. Basics of Probability Theory: Conditional Distribution, Conditional Expectation, Characteristics of Random Variables, Selected Examples of Probability Distributions
  5. Basics of Probability Theory: Poisson Process, Simulation Methods, Generating Functions
  6. Basics of Probability Theory: Strong Law of Large Numbers (SLLN), Central Limit Theorem (CLT), Large Deviations, Entropy
  7. Discrete-time Markov Chains with Finite State Space: Basic Concepts, Irreducibility and Periodicity of States, Absorption Probability, Stopping Times
  8. Discrete-time Markov Chains: Examples: Generalized Random Walk, Random Walk on a Graph, Gambler's Ruin, Coupon Collector
  9. Discrete-time Markov Chains: Asymptotic Stationarity, Uniqueness and Existence of Stationary Distributions, Convergence
  10. Discrete-time Markov Chains: Branching Processes, Birth & Death processes
  11. Monte Carlo Methods: Markov Chain Monte Carlo (MCMC) – Basic Concepts and Examples
  12. Monte Carlo Methods: Fast convergence of MCMC, Propp-Wilson Algorithm, Sandwiching, Simulated Annealing
  13. Monte Carlo Methods: Monte Carlo Estimates, Monte Carlo Tests, Reduction of Variance
  14. Stochastic Processes: Definition, Distribution Function, Characteristics of Stochastic Processes
  15. Stochastic Processes: Characteristics and Classification of Stochastic Processes, Examples
  16. Basics of Queueing Theory: Elements of Queueing Systems, Request Arrival Process, Queueing Policy, Service Policy, Kendall Notation
  17. Stochastic Processes: Application of the Poisson Process to Model Arrivals in Queueing Systems
  18. Stochastic Processes: Application of the Poisson Process in Queueing Theory
  19. Stochastic Processes: Non-homogeneous Poisson Process, Spatial Poisson Process, M/G/infinity Queue
  20. Continuous-time Markov Chains: Jump Rates, Timing Jumps by Poisson Process Arrivals, Kolmogorov Equations
  21. Basics of Queueing Theory: M/M/m Queues, Queueing Systems
  22. Basics of Queueing Theory: Open and Closed Queueing Systems
  23. Bootstrap Methods: Properties of Bootstrap Approximations, Bootstrap Correction of Estimation Bias
  24. Bootstrap Methods: Bootstrap Confidence Intervals, Permutation Bootstrap
  25. Bootstrap Methods: Bootstrap Confidence Intervals for Parameters in Linear Regression
  26. Estimation of Probability Density Functions: Histogram, Kernel Estimates, Maximum Likelihood Estimation, Estimation by the Method of Moments

MIE-SYP - Parsing and Compilers

Annotation

Knowledge acquired in this module can be used for compiler construction or other types of programs for parsing and processing structured texts.

Lectures program

  1. Recapitulaton of basic notions, LL parsing.
  2. Classification of LR parsers.
  3. Strong LR(k) parsing.
  4. LR(0) and SLR(1) parsing.
  5. LALR(k) and LR(k) parsing.
  6. Translation directed by an LR parser.
  7. Evaluation of attributes during LR parsing.
  8. LR attributed translation.
  9. Intermediate representation.
  10. Incremental LL parsing.
  11. Incremental LR parsing.
  12. Parallel LL parsing.
  13. Parallel LR parsing.

MIE-TES - Systems Theory

Annotation

We are surrounded by phenomena and things that are too complex to be completely and in detail described, understood, and analyzed. However, it turns out that many of them, even though of various nature, show similar properties and behaviors: for example, the number of wolfs hunted down in Canada has similar time characteristics as the oscillations of an electronic relaxation oscillator. The structure of a system, i.e., the way how it is assembled from components, often plays substantial role. Students learn to work with these general rules of law both for the analysis of behavior of such systems and for their construction.

Lectures program

  1. System definition. Structural and functional concept of a system.
  2. Compositional and dynamic systems. Hard and soft systems.
  3. Identification of a system.
  4. Structural tasks of the system analysis. Paths and feedbacks.
  5. Tasks of decomposition and composition of a system and tasks of system goals.
  6. System behavior, behavior models, the notion of a process.
  7. Formalisms for the analysis of model behavior: Petri nets, decision tables.
  8. Bulk analysis and other methods of system analysis.
  9. Soft systems, methods of their analysis.
  10. Selected methodologies of system design, the SSADM method.
  11. System synthesis with discrete time.
  12. Decision and decision processes.
  13. Information in a system and in its neighborhood, system regularity, system viability.


Last modified: 11.11.2010, 19:23