| Course Unit Code | 460-4065/01 |
|---|
| Number of ECTS Credits Allocated | 6 ECTS credits |
|---|
| Type of Course Unit * | Compulsory |
|---|
| Level of Course Unit * | Second Cycle |
|---|
| Year of Study * | First Year |
|---|
| Semester when the Course Unit is delivered | Winter Semester |
|---|
| Mode of Delivery | Face-to-face |
|---|
| Language of Instruction | Czech |
|---|
| Prerequisites and Co-Requisites | There are no prerequisites or co-requisites for this course unit |
|---|
| Name of Lecturer(s) | Personal ID | Name |
|---|
| SAW75 | doc. Ing. Zdeněk Sawa, Ph.D. |
| KOT06 | Ing. Martin Kot, Ph.D. |
| Summary |
|---|
The course extends the theoretical background for computer science
gained in bachelor studies, in particular in the areas of automata,
languages, computability and complexity. |
| Learning Outcomes of the Course Unit |
|---|
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 |
| Course Contents |
|---|
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.
|
| Recommended or Required Reading |
|---|
| Required Reading: |
|---|
[1] Michael Sipser: Introduction to the Theory of Computation, Thomson
2006 |
| [1] Petr Jančar: Teoretická informatika, VŠB-TU, Ostrava, 2007 (dostupná z web-stránky předmětu). |
| Recommended Reading: |
|---|
[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. |
[2] Sipser, M.: Introduction to the Theory of Computation, PWS Publishing Company, 1997.
[3] Kozen, D.: Automata and Computability, Undergraduate Text in Computer Science, Springer-Verlag, 1997.
[4] Arora, S., Barak, B.: Computational Complexity: A Modern Approach, Cambridge University Press, 2009.
[5] Papadimitriou, C.: Computational Complexity, Addison Wesley, 1993.
[6] Kozen, D.: Theory of computation, Springer 2006.
[7] Cormen, T., Leiserson, C., Rivest, R., Stein, C.: Introduction to Algorithms, Second Edition, The MIT Press, 2001.
[8] Hromkovič, J.: Theoretical Computer Science: Introduction to Automata, Computability, Complexity, Algorithmics, Randomization, Communication, and Cryptography, Springer, 2003.
[9] Hopcroft, J.E., Motwani, R., Ullman, J, D.: Introduction to Automata Theory, Languages, and Computation, (3rd edition), Addison Wesley, 2006. |
| Planned learning activities and teaching methods |
|---|
| Lectures, Tutorials |
| Assesment methods and criteria |
|---|
| Task Title | Task Type | Maximum Number of Points
(Act. for Subtasks) | Minimum Number of Points for Task Passing |
|---|
| Credit and Examination | Credit and Examination | 100 (100) | 51 |
| Credit | Credit | 38 (38) | 8 |
| referát | Other task type | 10 | 1 |
| záp. písemka | Written test | 21 | 7 |
| aktivita na cvičení | Other task type | 7 | 0 |
| Examination | Examination | 62 (62) | 25 |
| první část | Written test | 31 | 11 |
| druhá část | Written test | 31 | 11 |