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 | Compulsory |

Year | 2 | Semester | summer |

Study language | Czech | ||

Year of introduction | 1999/2000 | Year of cancellation | 2009/2010 |

Intended for the faculties | FEI | Intended for study types | Bachelor |

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

Login | Name | Tuitor | Teacher giving lectures |

CIH053 | PhDr. Martina Číhalová, Ph.D. | ||

CIP016 | Ing. Nikola Ciprich | ||

SNE10 | Mgr. Pavla Dráždilová, Ph.D. | ||

FRY057 | Ing. Tomáš Frydrych | ||

KOT06 | Ing. Martin Kot, Ph.D. | ||

KUC275 | Ing. Štěpán Kuchař, Ph.D. | ||

MEN059 | Mgr. Marek Menšík, Ph.D. | ||

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

TAK003 | Ing. Ondřej Takács |

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

Form of study | Way of compl. | Extent |

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

Combined | Credit and Examination | 10+0 |

The goal is to teach students to work with the basic terms of theoretical
computer science, and to use them in programming. Moreover, the subject
gives necessary background for further study of computer science at higher
levels.

Lectures

Tutorials

Project work

The subject is an indroductory course of some basic areas of theoretical
computer science. Students get acquainted with essentials of logic, formal languages, automata,
and computational complexity, together with some of their applications for solving problems in programming.
In particular, students will learn essentials of propositional and predicate logic. They will be able to formalize propositions in terms of these logics and to use some of methods of logical deduction.
They will learn about the use of finite automata, regular expressions and context-free grammars in the construction of compilers (in lexical and syntax analysis) and also for searching in text data. Students will learn some basics of the theory of computation and of the complexity theory. They will be able to analyze the computational complexity of algorithms and to use the asymptotic notation. Also the computational complexity of algorithmic problems and complexity classes will be mentioned briefly. Students will learn that some problems are computationally undecidable and how this
can be proved.

- Sipser, M.: Introduction to the Theory of Computation, PWS Publishing Company, 1997.
- Kozen, D.: Automata and Computability. Undergraduate Text in Computer Science,
Springer Verlag, 1997.
- Hopcroft, J.E., Motwani, R., Ullman, J, D.: Introduction to Automata Theory, Languages,
and Computation (3rd Edition), Addison Wesley, 2006.
- Huth, M., Ryan, M.: Logic in Computer Science: Modelling and Reasoning about Systems,
Cambridge University Press, 2004.

- Papadimitriou, C.: Computational Complexity, Addison Wesley, 1993.
- Gruska, J.: Foundation of Computing. International Thomson Computer Press, 1997.

Requirements during a semester:
- Two test during a semester (each for 10 points)
- A written report, which must be also presented to a tutor (15 points)
(topics will be assigned to students at the beginning of a semester).
Requirements for a credit:
- To get a credit, a student must obtain from two tests and a report together
at least 20 points.
Exam:
- The exam is of a written form.
The exam consists of three parts devoted to the following areas:
- theory of formal languages and automata
- computability and complexity
- introduction to logic
It is possible to get 65 points for the exam.
To pass out the exam it is necessary to get at least 5 points from each of its parts.

Subject has no prerequisities.

Subject has no co-requisities.

Lectures:
- Basics of propositional and predicate logic.
- Analysis of sentences of a natural language in the language of propositional and predicate logic.
- Deduction of consequences. Set theoretical / semantic proofs.
- Basics of resolution method.
- Formal languages - basic notions (an alphabet, a word, a language). Operations
on languages. Finite automata.
- Construction of finite automata. Nondeterinistic finite automata.
- Transformation of nondeterministic finite automata to deterministic.
Regular expressions.
- Context-free grammar and languages.
- Algorithmic problems. Models of computation (Turing machines and RAM machines).
- Asymptotic notation. Complexity of algorithms.
- Complexity of problems. Complexity classes. Reductions between problems. NP-complete
problems.
- Algorithmically undecidable problems.
Tutorials:
- Recalling of basics of the set theory, relations, functions and the graph theory.
- Propositional and predicate logic.
- Analysis of sentences of a natural language in the language of propositional and predicate logic.
- Deduction of consequences. Set theoretical / semantic proofs.
- Resolution method.
- Operations with languages.
- Construction of finite automata.
- Transformation of nondeterministic automata to deterministic.
- Regular expressions.
- Context-free grammars.
- Turing machines and RAM machines.
- Asymptotic notation. Complexity of algorithms.
- Complexity of problems. Complexity classes.

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

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

Examination | Examination | 65 (65) | 15 |

Matematická logika | Written examination | 22 | 5 |

Jazyky a automaty | Written examination | 22 | 5 |

Vyčíslitelnost a složitost | Written examination | 21 | 5 |

Exercises evaluation | Credit | 35 (35) | 20 |

1. zápočtová písemka | Written test | 10 | 0 |

2. zápočtová písemka | Written test | 10 | 0 |

Referát | Project | 15 | 0 |

Show history

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

2009/2010 | (B2646) Information Technology | (2612R025) Computer Science and Technology | P | Czech | Ostrava | 2 | Compulsory | study plan | ||||

2009/2010 | (B2646) Information Technology | (2612R059) Mobile Technology | P | Czech | Ostrava | 2 | Compulsory | study plan | ||||

2009/2010 | (B2647) Information and Communication Technology | (1103R031) Computational Mathematics | P | Czech | Ostrava | 2 | Compulsory | study plan | ||||

2009/2010 | (B2647) Information and Communication Technology | (2601R013) Telecommunication Technology | P | Czech | Ostrava | 2 | Compulsory | study plan | ||||

2009/2010 | (B2647) Information and Communication Technology | (2612R025) Computer Science and Technology | P | Czech | Ostrava | 2 | Compulsory | study plan | ||||

2009/2010 | (B2647) Information and Communication Technology | (2612R059) Mobile Technology | P | Czech | Ostrava | 2 | Compulsory | study plan | ||||

2009/2010 | (B2646) Information Technology | (2612R025) Computer Science and Technology | K | Czech | Ostrava | 2 | Compulsory | study plan | ||||

2009/2010 | (B2646) Information Technology | (2612R059) Mobile Technology | K | Czech | Ostrava | 2 | Compulsory | study plan | ||||

2009/2010 | (B2647) Information and Communication Technology | (1103R031) Computational Mathematics | K | Czech | Ostrava | 2 | Compulsory | study plan | ||||

2009/2010 | (B2647) Information and Communication Technology | (2601R013) Telecommunication Technology | K | Czech | Ostrava | 2 | Compulsory | study plan | ||||

2009/2010 | (B2647) Information and Communication Technology | (2612R025) Computer Science and Technology | K | Czech | Ostrava | 2 | Compulsory | study plan | ||||

2009/2010 | (B2647) Information and Communication Technology | (2612R059) Mobile Technology | K | Czech | Ostrava | 2 | Compulsory | study plan | ||||

2009/2010 | (B2646) Information Technology | (1103R021) Computation Mathematics | K | Czech | Ostrava | 2 | Compulsory | study plan | ||||

2009/2010 | (B2646) Information Technology | (1103R021) Computation Mathematics | P | Czech | Ostrava | 2 | Compulsory | study plan | ||||

2008/2009 | (B2646) Information Technology | (1103R021) Computation Mathematics | P | Czech | Ostrava | 2 | Compulsory | study plan | ||||

2008/2009 | (B2646) Information Technology | (1103R021) Computation Mathematics | K | Czech | Ostrava | 2 | Compulsory | study plan | ||||

2008/2009 | (B2646) Information Technology | (2612R025) Computer Science and Technology | P | Czech | Ostrava | 2 | Compulsory | study plan | ||||

2008/2009 | (B2646) Information Technology | (2612R025) Computer Science and Technology | K | Czech | Ostrava | 2 | Compulsory | study plan | ||||

2008/2009 | (B2646) Information Technology | (2612R059) Mobile Technology | P | Czech | Ostrava | 2 | Compulsory | study plan | ||||

2008/2009 | (B2646) Information Technology | (2612R059) Mobile Technology | K | Czech | Ostrava | 2 | Compulsory | study plan | ||||

2008/2009 | (B2647) Information and Communication Technology | (1103R031) Computational Mathematics | P | Czech | Ostrava | 2 | Compulsory | study plan | ||||

2008/2009 | (B2647) Information and Communication Technology | (1103R031) Computational Mathematics | K | Czech | Ostrava | 2 | Compulsory | study plan | ||||

2008/2009 | (B2647) Information and Communication Technology | (2601R013) Telecommunication Technology | P | Czech | Ostrava | 2 | Compulsory | study plan | ||||

2008/2009 | (B2647) Information and Communication Technology | (2601R013) Telecommunication Technology | K | Czech | Ostrava | 2 | Compulsory | study plan | ||||

2008/2009 | (B2647) Information and Communication Technology | (2612R025) Computer Science and Technology | P | Czech | Ostrava | 2 | Compulsory | study plan | ||||

2008/2009 | (B2647) Information and Communication Technology | (2612R025) Computer Science and Technology | K | Czech | Ostrava | 2 | Compulsory | study plan | ||||

2008/2009 | (B2647) Information and Communication Technology | (2612R059) Mobile Technology | P | Czech | Ostrava | 2 | Compulsory | study plan | ||||

2008/2009 | (B2647) Information and Communication Technology | (2612R059) Mobile Technology | K | Czech | Ostrava | 2 | Compulsory | study plan | ||||

2007/2008 | (B2646) Information Technology | (1103R021) Computation Mathematics | P | Czech | Ostrava | 2 | Compulsory | study plan | ||||

2007/2008 | (B2646) Information Technology | (1103R021) Computation Mathematics | K | Czech | Ostrava | 2 | Compulsory | study plan | ||||

2007/2008 | (B2646) Information Technology | (2612R025) Computer Science and Technology | P | Czech | Ostrava | 2 | Compulsory | study plan | ||||

2007/2008 | (B2646) Information Technology | (2612R025) Computer Science and Technology | K | Czech | Ostrava | 2 | Compulsory | study plan | ||||

2007/2008 | (B2646) Information Technology | (2612R059) Mobile Technology | P | Czech | Ostrava | 2 | Compulsory | study plan | ||||

2007/2008 | (B2646) Information Technology | (2612R059) Mobile Technology | K | Czech | Ostrava | 2 | Compulsory | study plan | ||||

2007/2008 | (B2647) Information and Communication Technology | (1103R031) Computational Mathematics | P | Czech | Ostrava | 2 | Compulsory | study plan | ||||

2007/2008 | (B2647) Information and Communication Technology | (1103R031) Computational Mathematics | K | Czech | Ostrava | 2 | Compulsory | study plan | ||||

2007/2008 | (B2647) Information and Communication Technology | (2601R013) Telecommunication Technology | P | Czech | Ostrava | 2 | Compulsory | study plan | ||||

2007/2008 | (B2647) Information and Communication Technology | (2601R013) Telecommunication Technology | K | Czech | Ostrava | 2 | Compulsory | study plan | ||||

2007/2008 | (B2647) Information and Communication Technology | (2612R025) Computer Science and Technology | P | Czech | Ostrava | 2 | Compulsory | study plan | ||||

2007/2008 | (B2647) Information and Communication Technology | (2612R025) Computer Science and Technology | K | Czech | Ostrava | 2 | Compulsory | study plan | ||||

2007/2008 | (B2647) Information and Communication Technology | (2612R059) Mobile Technology | P | Czech | Ostrava | 2 | Compulsory | study plan | ||||

2007/2008 | (B2647) Information and Communication Technology | (2612R059) Mobile Technology | K | Czech | Ostrava | 2 | Compulsory | study plan | ||||

2006/2007 | (B2646) Information Technology | (1103R021) Computation Mathematics | P | Czech | Ostrava | 2 | Compulsory | study plan | ||||

2006/2007 | (B2646) Information Technology | (1103R021) Computation Mathematics | K | Czech | Ostrava | 2 | Compulsory | study plan | ||||

2006/2007 | (B2646) Information Technology | (2612R025) Computer Science and Technology | P | Czech | Ostrava | 2 | Compulsory | study plan | ||||

2006/2007 | (B2646) Information Technology | (2612R025) Computer Science and Technology | K | Czech | Ostrava | 2 | Compulsory | study plan | ||||

2006/2007 | (B2646) Information Technology | (2612R059) Mobile Technology | P | Czech | Ostrava | 2 | Compulsory | study plan | ||||

2006/2007 | (B2646) Information Technology | (2612R059) Mobile Technology | K | Czech | Ostrava | 2 | Compulsory | study plan | ||||

2006/2007 | (B2647) Information and Communication Technology | (1103R031) Computational Mathematics | P | Czech | Ostrava | 2 | Compulsory | study plan | ||||

2006/2007 | (B2647) Information and Communication Technology | (1103R031) Computational Mathematics | K | Czech | Ostrava | 2 | Compulsory | study plan | ||||

2006/2007 | (B2647) Information and Communication Technology | (2601R013) Telecommunication Technology | P | Czech | Ostrava | 2 | Compulsory | study plan | ||||

2006/2007 | (B2647) Information and Communication Technology | (2601R013) Telecommunication Technology | K | Czech | Ostrava | 2 | Compulsory | study plan | ||||

2006/2007 | (B2647) Information and Communication Technology | (2612R025) Computer Science and Technology | P | Czech | Ostrava | 2 | Compulsory | study plan | ||||

2006/2007 | (B2647) Information and Communication Technology | (2612R025) Computer Science and Technology | K | Czech | Ostrava | 2 | Compulsory | study plan | ||||

2006/2007 | (B2647) Information and Communication Technology | (2612R059) Mobile Technology | P | Czech | Ostrava | 2 | Compulsory | study plan | ||||

2006/2007 | (B2647) Information and Communication Technology | (2612R059) Mobile Technology | K | Czech | Ostrava | 2 | Compulsory | study plan | ||||

2005/2006 | (N2646) Information Technology | (2612T025) Computer Science and Technology | P | Czech | Ostrava | 1 | Compulsory | study plan | ||||

2005/2006 | (B2646) Information Technology | (1103R021) Computation Mathematics | P | Czech | Ostrava | 2 | Compulsory | study plan | ||||

2005/2006 | (B2646) Information Technology | (2612R025) Computer Science and Technology | P | Czech | Ostrava | 2 | Compulsory | study plan | ||||

2005/2006 | (N2646) Information Technology | (1103T021) Computational Mathematics | P | Czech | Ostrava | 1 | Compulsory | study plan | ||||

2005/2006 | (B2646) Information Technology | (2612R025) Computer Science and Technology | K | Czech | Ostrava | 2 | Compulsory | study plan | ||||

2005/2006 | (B2646) Information Technology | (1103R021) Computation Mathematics | K | Czech | Ostrava | 2 | Compulsory | study plan | ||||

2005/2006 | (N2646) Information Technology | (2612T025) Computer Science and Technology | K | Czech | Ostrava | 1 | Compulsory | study plan | ||||

2005/2006 | (N2646) Information Technology | (1103T021) Computational Mathematics | K | Czech | Ostrava | 1 | Compulsory | study plan | ||||

2005/2006 | (B2646) Information Technology | (2612R059) Mobile Technology | P | Czech | Ostrava | 2 | Compulsory | study plan | ||||

2005/2006 | (B2646) Information Technology | (2612R059) Mobile Technology | K | Czech | Ostrava | 2 | Compulsory | study plan | ||||

2004/2005 | (N2646) Information Technology | (2612T025) Computer Science and Technology | P | Czech | Ostrava | 1 | Compulsory | study plan | ||||

2004/2005 | (B2646) Information Technology | (1103R021) Computation Mathematics | P | Czech | Ostrava | 2 | Compulsory | study plan | ||||

2004/2005 | (B2646) Information Technology | (2612R025) Computer Science and Technology | P | Czech | Ostrava | 2 | Compulsory | study plan | ||||

2004/2005 | (N2646) Information Technology | (1103T021) Computational Mathematics | P | Czech | Ostrava | 1 | Compulsory | study plan | ||||

2004/2005 | (B2646) Information Technology | (2612R025) Computer Science and Technology | K | Czech | Ostrava | 2 | Compulsory | study plan | ||||

2004/2005 | (B2646) Information Technology | (1103R021) Computation Mathematics | K | Czech | Ostrava | 2 | Compulsory | study plan | ||||

2004/2005 | (N2646) Information Technology | (2612T025) Computer Science and Technology | K | Czech | Ostrava | 1 | Compulsory | study plan | ||||

2004/2005 | (N2646) Information Technology | (1103T021) Computational Mathematics | K | Czech | Ostrava | 1 | Compulsory | study plan | ||||

2004/2005 | (B2646) Information Technology | (2612R059) Mobile Technology | P | Czech | Ostrava | 2 | Compulsory | study plan | ||||

2004/2005 | (B2646) Information Technology | (2612R059) Mobile Technology | K | Czech | Ostrava | 2 | Compulsory | study plan | ||||

2003/2004 | (N2646) Information Technology | (2612T025) Computer Science and Technology | P | Czech | Ostrava | 1 | Compulsory | study plan | ||||

2003/2004 | (B2646) Information Technology | (1103R021) Computation Mathematics | P | Czech | Ostrava | 2 | Compulsory | study plan | ||||

2003/2004 | (B2646) Information Technology | (2612R025) Computer Science and Technology | P | Czech | Ostrava | 2 | Compulsory | study plan | ||||

2003/2004 | (N2646) Information Technology | (1103T021) Computational Mathematics | P | Czech | Ostrava | 1 | Compulsory | study plan | ||||

2003/2004 | (B2646) Information Technology | (2612R025) Computer Science and Technology | K | Czech | Ostrava | 2 | Compulsory | study plan | ||||

2003/2004 | (B2646) Information Technology | (1103R021) Computation Mathematics | K | Czech | Ostrava | 2 | Compulsory | study plan | ||||

2003/2004 | (N2646) Information Technology | (2612T025) Computer Science and Technology | K | Czech | Ostrava | 1 | Compulsory | study plan | ||||

2003/2004 | (N2646) Information Technology | (1103T021) Computational Mathematics | K | Czech | Ostrava | 1 | Compulsory | study plan |

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