Theory of Computation 2401-CS-21-ToC-s2

The theory of computation organizes knowledge of three main topics: automata theory, computability theory, and complexity theory. During the course, students will learn about finite automata, their applications, and their relationship with regular languages. They will also study pushdown automata, their applications, and their relationship with context-free languages. The Turing machine is the most important concept of the course, as it is a mathematical model of computation that defines an abstract machine that manipulates symbols on a tape according to a set of rules. Despite its simplicity, a Turing machine capable of simulating the logic of any computer algorithm can be constructed. Students will become familiar with the formal definition of a Turing machine.

List of topics:
- Finite automata.
- Regular launguages
- Pushdown automata.
- Context-free launguages
- Turing machine

Total student workload

Contact hours with teacher: - participation in lectures - 15 hrs - participation in tutorials - 15 hrs - consultations- 20 hrs Self-study hours: - preparation for lectures and reading literature - 30 hrs - preparation for test/examination - 20 hrs Altogether: 100 hrs (4 ECTS)

Learning outcomes - knowledge

Student W1: is familiar with finite automata - K_W02 W2: has advanced thorough knowledge of pushdown automata - K_W08 W3: is well acquainted with Turing machine - K_W05 W4: knows and understands terms time/memory complexity - K_W06

Learning outcomes - skills

Student U1: is able to recognize regular languages - K_U09 U2: can find context free grammar for a given language - K_U12 U3: has advanced skills in determining context-free launguages - K_U02, K_U03 U4: can estimate time and memory complexity of a given algorithm - K_U01, K_U10

Learning outcomes - social competencies

Student K1: is well prepared to creatively find solutions of problems - K_K01, K_K05 K2: understands the significance of the scientific method - K_K02

Teaching methods

Expository teaching methods: - informative (conventional) lecture - problem-based lecture Exploratory teaching methods: - practical

Expository teaching methods

- description
- problem-based lecture
- informative (conventional) lecture
- discussion

Exploratory teaching methods

- practical
- classic problem-solving

Type of course

compulsory course

Prerequisites

None

Course coordinators

Term 2022/23L:

Michał Komorowski

Term 2023/24Z:

Michał Komorowski

Term 2024/25Z:

Krystyna Mruczek-Nasieniewska

Assessment criteria

Assessment methods:
- written examination – W1
- test – W2
- activity – W3

Assessment criteria:
lecture: written exam with open-ended questions, with the maximum number of 50 points. The resulting mark is given as follows:
fail- <0;45 %)
satisfactory- <45%;55%)
satisfactory plus- <55%;65%)
good – <65%;78%)
good plus- <78%;88 %)
very good- <88 %;100%>

tutorial: written two tests with open-ended questions, with the maximum number of 22 points, each. The sum of these two components is the basis of the final mark according to the following scale:

fail- <0;45 %)
satisfactory- <45%;55%)
satisfactory plus- <55%;65%)
good – <65%;78%)
good plus- <78%;88 %)
very good- <88 %;100%>

Additional information

Additional information (registration calendar, class conductors, localization and schedules of classes), might be available in the USOSweb system:

Description of 2401-CS-21-ToC-s2 in USOSweb