Teoretické základy informatiky
doc. RNDr. Lucie Ciencialová, Ph.D.
Teoretické základy informatiky
doc. RNDr. Lucie Ciencialová, Ph.D.
Teoretické základy informatiky

FPF: UBKINSNK06 Introduction to Theoretical Computer Science (Winter 2023)

Course objectives

The basic themes of the course are abstract machines, formal grammars and languages, the notion of computability and complexity of automata, languages and computation. The behavior of individual objects and phenomena and the consequences of collaboration collective behavior of objects will be discussed. Students will become familiar with the Turing machine, pushdown automaton and finite automaton, relatiton between machines and formal grammars. The subject of study will also limit access to machine a generative approach to solving a related concept (un) decidability.

Learning outcomes

Upon completion of the course the student will be able to:
- explain the difference between generative and machine approaches to problem solving;
- define types of Chomsky grammars;
- associate the types of languages with a machine that recognizes them;
- analyze the behavior of both grammars and machines;

Teaching methods

Interactive lecture
Lecture with a discussion

Assessment methods

Credit: written. 75 % participation in the exercises is compulsory. Examination: written.

Course syllabus

FPF: UIKSK33 Introduction to Theoretical Computer Science (Winter 2023)

Course objectives

The basic themes of the course are abstract machines, formal grammars and languages, the notion of computability and complexity of automata, languages and computation. The behavior of individual objects and phenomena and the consequences of collaboration collective behavior of objects will be discussed. Students will become familiar with the Turing machine, pushdown automaton and finite automaton, relatiton between machines and formal grammars. The subject of study will also limit access to machine a generative approach to solving a related concept (un) decidability.

Learning outcomes

Upon completion of the course the student will be able to:
- explain the difference between generative and machine approaches to problem solving;
- define types of Chomsky grammars;
- associate the types of languages with a machine that recognizes them;
- analyze the behavior of both grammars and machines;

Teaching methods

Interactive lecture
Lecture with a discussion

Assessment methods

Credit: written. 75 % participation in the exercises is compulsory. Examination: written.

Course syllabus

FPF: UBKINSNP07 Introduction to Theoretical Computer Science (Winter 2023)

Course objectives

The basic themes of the course are abstract machines, formal grammars and languages, the notion of computability and complexity of automata, languages and computation. The behavior of individual objects and phenomena and the consequences of collaboration collective behavior of objects will be discussed. Students will become familiar with the Turing machine, pushdown automaton and finite automaton, relatiton between machines and formal grammars. The subject of study will also limit access to machine a generative approach to solving a related concept (un) decidability.

Learning outcomes

Upon completion of the course the student will be able to:
- explain the difference between generative and machine approaches to problem solving;
- define types of Chomsky grammars;
- associate the types of languages with a machine that recognizes them;
- analyze the behavior of both grammars and machines;

Teaching methods

Interactive lecture
Lecture with a discussion

Assessment methods

Credit: written. 75 % participation in the exercises is compulsory. Examination: written.

Course syllabus

Základními tématy předmětu jsou abstraktní stroje, formální gramatiky a jazyky, pojem vyčíslitelnosti a složitosti automatů, jazyků a výpočtů. Bude diskutováno chování individuálních objektů i fenoménů a důsledky spolupráce kolektivního chování objektů. Studenti se seznámí s Turingovým strojem, zásobníkovým automatem a konečným automatem, se vztahem strojů a formálních gramatik. Předmětem studia bude také omezení strojového přístupu a generativního přístupu k řešení úloh a související pojem (ne)rozhodnutelnosti. 

Osnova

  1. Abeceda, slovo,  jazyk
  2. Konečná reprezentace jazyků
  3. Gramatiky
  4. Konečné automaty a regulární jazyky
  5. Zásobníkové automaty
  6. Bezkontextové gramatiky a jazyky
  7. Úvod do teorie vyčíslitelnosti

Požadavky na studenta

Zkouška probíhá formou písemného testu, který obsahuje jak otázky na teorii tak příklady k vyřešení.

Literatura

Povinná:

  1. CIENCIALOVÁ, L., Teoretické základy informatiky. Opava 2014. ISBN: 978 – 80 –7510 – 130 – 3 

Doporučená:

  1. DEMLOVÁ, M. - KOUBEK, V. Algebraická teorie automatů. Praha: SNTL, 1990. 
  2. CHYTIL, M. Automaty a gramatiky. Praha: SNTL, 1984. 
  3. GRUSKA, J. Foundations of Computing. London: International Thomson Computer Press, 1997. 
  4. MOLNÁR, Ľ. - ČEŠKA, M. - MELICHAR, B. Gramatiky a jazyky. Bratislava: Alfa, 1987. 
  5. HOPCROFT, J. E. - ULLMAN, J. D. Teória jazykov a automatov. Bratislava: Alfa, 1987.
Studijní opora
Chapter contains:
1
PDF
Previous
Next

Courses

  • FPF: UBKINSNK06 Introduction to Theoretical Computer Science (Winter 2023)
  • FPF: UIKSK33 Introduction to Theoretical Computer Science (Winter 2023)
  • FPF: UBKINSNP07 Introduction to Theoretical Computer Science (Winter 2023)
Operations
View all
Tutorial on the changes in Interactive Syllabus