Back

Introduction to Theoretical Computer Science

Guarantor: Lecturer: Teaching Assistants: Tutor for students in the combined form:

News


Infomation for Students in the Combined Form

Tutor: Ing. Martin Kot, Ph.D (room: EA413, e-mail: martin.kot@vsb.cz)


Content of the Course

The aim of the course is to introduce students to some basics of the following areas of theoretical computer science:

Preliminary Program of Lectures

  1. Introduction. What are the main topics of theoretical computer science (algorithms, algorithmic problems, formal languages, ...). Formal languages - basic notions (alphabet, word, language). Operations on languages.
  2. Regular expressions. Deterministic finite automata (DFA). Construction of DFA. Some language operations on DFA.
  3. Nondeterministic finite automata (NFA). Transformation of NFA to DFA. Language operations on NFA. Relation between regular expressions and finite automata.
  4. Context-free grammars and languages.
  5. Algorithmic problems. Models of computation (Turing machines and RAM machines).
  6. Algorithms. Church-Turing thesis. Correctness of algorithms. Methods for proving correctness of algorithms.
  7. Computational complexity of algorithms. Asymptotic notation. Analysis of computational complexity of algorithms.
  8. Undecidable problems (e.g., halting problem).
  9. Complexity of problems. Complexity classes (in particular classes P and NP). Reductions between problems. NP-complete problems.
  10. Examples of NP-complete problems and reductions between problems.

Requirements for a Credit

Written Test

There will be a written test during the semester. It will be possible to get up to 24 points from this test, while the minimum necessary to obtain a credit is 12 points.

The test will be written on some of tutorials. Particular date will be specified during the semester.

There will be some alternative date specified for students that due to some important reasons (e.g., illness) can not attend the written test in the regular date.

Students that do not obtain the necessary 12 points from the written test will have the possibility to obtain these points on a correcting test. However, it will be possible to obtain at most 20 points from the correcting test. (Points for a credit will be assigned according to the correcting test in this case.)

Activity on Tutorials

It is possible to obtain up to 6 points for the actiovity on tutorials, while 3 points are the required minimum.

Requirements for Obtaining a Credit

To obtain a credit, it is necessary to obtain at least 12 points from the written test and at least 3 points for the activity on tutorials.

Students that repeat the course and got their credit last year can choose one of the following two possibilities:

Students that either

must inform the guarantor of the course if they want their credit or not at the latest during the first two weeks of the semester. Later claims will not be considered.

Students that want their credit and have it already written in Edison do not need to do anything.

No points from the last year will be assigned to students that repeat the course but do not have a credit from the last year. They must do everything once more.


Exam

It is possible to obtain up to 70 points for an exam. The exam will be in a written form.

The exam consists of two parts devoted to the following areas, it is possible to obtain up to 35 points from each part:

It is necessary to obtain at least 12 points from each of these parts.

For students, which are in the 3rd year, repeat the course and want to go to the state exam this year, there will be a special term for an exam. The content of the exam will be the same as for exams in regular terms.


Tutorials


Materials

Main Texts


Lectures

Slides from lectures from the school year 2023/2024 will be published here during the semester.
  • Lecture 1
    Topic: Introduction. What are the main topics of theoretical computer science (algorithms, algorithmic problems, formal languages, ...). Formal languages. Operations on words and on languages.
    Slides: in Czech, in English

  • Lecture 2
    Topic: Regular expressions. Deterministic finite automata. Language operations on finite automata.
    Slides: in Czech, in English

  • Lecture 3
    Topic: Nondeterministic finite automata. Relationship between regular expressions and finite automata. Nonregular languages.
    Slides: in Czech, in English

  • Lecture 4
    Topic: Context-free grammars.
    Slides: in Czech, in English

  • Lecture 5
    Topic: Pushdown automata.
    Slides: in Czech, in English

  • Lecture 6
    Topic: Turing machines. Chomsky hierarchy.
    Slides: in Czech, in English

All slides from lectures from the school year 2022/2023: in Czech, in English


Exercises for tutorials

Exercises for tutorials for the school year 2023/2024 will be published during the semester:

Animations


Other Texts


Supplemental Literature


Back