Gurantor department | Department of Computer Science | Credits | 6 |

Subject guarantor | doc. Ing. Zdeněk Sawa, Ph.D. | Subject version guarantor | doc. Ing. Zdeněk Sawa, Ph.D. |

Study level | undergraduate or graduate | Requirement | Optional |

Year | 1 | Semester | winter |

Study language | English | ||

Year of introduction | 2015/2016 | Year of cancellation | |

Intended for the faculties | FEI | Intended for study types | Follow-up Master |

Instruction secured by | |||
---|---|---|---|

Login | Name | Tuitor | Teacher giving lectures |

SAW75 | doc. Ing. Zdeněk Sawa, Ph.D. |

Extent of instruction for forms of study | ||
---|---|---|

Form of study | Way of compl. | Extent |

Full-time | Credit and Examination | 3+3 |

Part-time | Credit and Examination | 15+0 |

On successful completion of the course, the student
- is able to evaluate the possible extent of using the methods of
finite automata, context-free grammars etc. by solving concrete
practical problems, and is able to design, analyse and compare the
respective solutions
- is able to analyse computational complexity of practical problems,
and to design algorithms for their solution
- understands the notions like approximation algorithms, probabilistic
algorithms, etc. and can evaluate the possibilities of their use in
concrete practical situations

Lectures

Tutorials

The course extends the theoretical background for computer science
gained in bachelor studies, in particular in the areas of automata,
languages, computability and complexity.

[1] Michael Sipser: Introduction to the Theory of Computation, Thomson
2006

[2] Kozen, D.: Automata and Computability, Undergraduate Text in Computer Science, Springer-Verlag, 1997.
[3] Arora, S., Barak, B.: Computational Complexity: A Modern Approach, Cambridge University Press, 2009.
[4] Papadimitriou, C.: Computational Complexity, Addison Wesley, 1993.
[5] Kozen, D.: Theory of computation, Springer 2006.
[6] Cormen, T., Leiserson, C., Rivest, R., Stein, C.: Introduction to Algorithms, Second Edition, The MIT Press, 2001.
[7] Hromkovič, J.: Theoretical Computer Science: Introduction to Automata, Computability, Complexity, Algorithmics, Randomization, Communication, and Cryptography, Springer, 2003.
[8] Hopcroft, J.E., Motwani, R., Ullman, J, D.: Introduction to Automata Theory, Languages, and Computation, (3rd edition), Addison Wesley, 2006.

No additional requirements are placed on students.

Subject has no prerequisities.

Subject has no co-requisities.

Lectures:
1. Course overview.
Recalling basic set theory notions, equivalence relations and orders,
graphs, formalisms of propositional and predicate logics, proofs by
induction and by contradiction.
(All these notions and methods will be used during the whole course.)
2. Formal languages, operations on languages,
regular expressions as language representations,
a pattern-search algorithm presented as (deterministic) finite
automaton. Modular design of finite automata (FA).
3. Deterministic and nondeterministic
finite automata, operations with finite automata,
transforming nondeterministic FA to deterministic ones,
constructing an FA to a given regular expression (RE).
4. Minimization of DFA, the canonical form, automata isomorphism.
FA and RE define the same class, so called regular languages.
Characterizations of regular languages enabling to show
non-regularity.
5. Context-free grammars, their (un)ambiguity, using for
specifications of (fragments of) programming languages.
(Nondeterministic) pushdown automata (PDA).
Syntactic analysis (by recursive descent).
6. Context-free languages and their subclass defined by deterministic
PDA. A basic compiler (constructing an FA to a given RE).
7. Non-context-free languages, Chomsky hierarchy.
Formal languages as computational problems.
The notion of algorithms, computational models
(Turing machine, RAM).
8. Church-Turing thesis. Universal machine.
(Algorithmic) undecidability, the halting problem,
reductions among problems.
Rice's Theorem (each nontrivial input/output property of programs is
undecidable).
9. Computational complexity of algorithms,
general methods of designing polynomial algorithms: "clever" search,
the "divide-and-conquer" method, greedy algorithms for optimization
problems, dynamic programming.
10. Computational complexity of problems, complexity classes,
polynomial reducibility.
Problem SAT (satisfiability of boolean formulas) and nondeterministic
polynomial algorithms. Class NPTIME. NP-completeness.
11. Class PSPACE=NPSPACE, PSPACE-complete problems, higher complexity
classes.
12. Approximation algorithms, i.e., polynomial algorithms
approximating optimal solutions of optimization problems.
(Non)approximability of concrete problems.
13. Randomized algorithms, e.g. for primality, which is a basis of
cryptographic algorithms.
14. Examples of parallel algorithms and of
non-parallelizable (inherently sequential) problems.
Exercises:
The topics of relevant lectures are subjecy of concrete exercises.

Task name | Type of task | Max. number of points
(act. for subtasks) | Min. number of points |
---|---|---|---|

Credit and Examination | Credit and Examination | 100 (100) | 51 |

Credit | Credit | 45 | 20 |

Examination | Examination | 55 | 6 |

Show history

Academic year | Programme | Field of study | Spec. | Zaměření | Form | Study language | Tut. centre | Year | W | S | Type of duty | |
---|---|---|---|---|---|---|---|---|---|---|---|---|

2021/2022 | (N2647) Information and Communication Technology | (2612T059) Mobile Technology | P | English | Ostrava | 1 | Optional | study plan | ||||

2021/2022 | (N2647) Information and Communication Technology | (2612T025) Computer Science and Technology | P | English | Ostrava | 1 | Compulsory | study plan | ||||

2020/2021 | (N2647) Information and Communication Technology | (2612T025) Computer Science and Technology | P | English | Ostrava | 1 | Compulsory | study plan | ||||

2020/2021 | (N2647) Information and Communication Technology | (2612T059) Mobile Technology | P | English | Ostrava | 1 | Optional | study plan | ||||

2019/2020 | (N2647) Information and Communication Technology | (2612T025) Computer Science and Technology | P | English | Ostrava | 1 | Compulsory | study plan | ||||

2019/2020 | (N2647) Information and Communication Technology | (2612T059) Mobile Technology | P | English | Ostrava | 1 | Optional | study plan | ||||

2019/2020 | (N2647) Information and Communication Technology | (2612T025) Computer Science and Technology | K | English | Ostrava | 1 | Compulsory | study plan | ||||

2019/2020 | (N2647) Information and Communication Technology | (2612T059) Mobile Technology | K | English | Ostrava | 1 | Optional | study plan | ||||

2018/2019 | (N2647) Information and Communication Technology | (2612T025) Computer Science and Technology | P | English | Ostrava | 1 | Compulsory | study plan | ||||

2018/2019 | (N2647) Information and Communication Technology | (2612T059) Mobile Technology | P | English | Ostrava | 1 | Optional | study plan | ||||

2018/2019 | (N2647) Information and Communication Technology | (2612T025) Computer Science and Technology | K | English | Ostrava | 1 | Compulsory | study plan | ||||

2018/2019 | (N2647) Information and Communication Technology | (2612T059) Mobile Technology | K | English | Ostrava | 1 | Optional | study plan | ||||

2017/2018 | (N2647) Information and Communication Technology | (2612T025) Computer Science and Technology | P | English | Ostrava | 1 | Compulsory | study plan | ||||

2017/2018 | (N2647) Information and Communication Technology | (2612T025) Computer Science and Technology | K | English | Ostrava | 1 | Compulsory | study plan | ||||

2017/2018 | (N2647) Information and Communication Technology | (2612T059) Mobile Technology | P | English | Ostrava | 1 | Optional | study plan | ||||

2017/2018 | (N2647) Information and Communication Technology | (2612T059) Mobile Technology | K | English | Ostrava | 1 | Optional | study plan | ||||

2016/2017 | (N2647) Information and Communication Technology | (2612T025) Computer Science and Technology | P | English | Ostrava | 1 | Compulsory | study plan | ||||

2016/2017 | (N2647) Information and Communication Technology | (2612T025) Computer Science and Technology | K | English | Ostrava | 1 | Compulsory | study plan | ||||

2016/2017 | (N2647) Information and Communication Technology | (2612T059) Mobile Technology | P | English | Ostrava | 1 | Optional | study plan | ||||

2016/2017 | (N2647) Information and Communication Technology | (2612T059) Mobile Technology | K | English | Ostrava | 1 | Optional | study plan | ||||

2015/2016 | (N2647) Information and Communication Technology | (2612T025) Computer Science and Technology | P | English | Ostrava | 1 | Compulsory | study plan | ||||

2015/2016 | (N2647) Information and Communication Technology | (2612T025) Computer Science and Technology | K | English | Ostrava | 1 | Compulsory | study plan | ||||

2015/2016 | (N2647) Information and Communication Technology | (2612T059) Mobile Technology | P | English | Ostrava | 1 | Optional | study plan | ||||

2015/2016 | (N2647) Information and Communication Technology | (2612T059) Mobile Technology | K | English | Ostrava | 1 | Optional | study plan |

Block name | Academic year | Form of study | Study language | Year | W | S | Type of block | Block owner |
---|