Přístupnostní navigace
E-application
Search Search Close
Course detail
FIT-TINAcad. year: 2023/2024
An overview of the applications of the formal language theory in modern computer science and engineering (compilers, system modelling and analysis, linguistics, etc.), the modelling and decision power of formalisms, regular languages and their properties, minimalization of finite-state automata, context-free languages and their properties, Turing machines, properties of recursively enumerable and recursive languages, computable functions, undecidability, undecidable problems of the formal language theory, and the introduction to complexity theory.
Language of instruction
Number of ECTS credits
Mode of study
Guarantor
Department
Entry knowledge
Basic knowledge of discrete mathematics concepts including algebra, mathematical logic, graph theory and formal languages concepts, and basic concepts of algorithmic complexity.
Rules for evaluation and completion of the course
The evaluation of the course consists of the test in the 4th week (max. 15 points) and the test in the 9th week (max. 15 points), the assignments (max 3-times 5 points), and the final exam (max 60 points).
The written test in the 4th week focuses on the regular languages and on a basic knowledge of the context-free languages. The written test in the 9th week focuses on advance topics in the context-free languages, and on the area of decidability and undecidability including constructions of Turing machines.
The requirements to obtain the accreditation that is required for the final exam: The minimal total score of 18 points achieved from the assignments and from the tests in the 4th and 9th week (i.e. out of 40 points).
The final exam has 4 parts. Students have to achieve at least 4 points from each part and at least 25 points in total, otherwise the exam is evaluated by 0 points.
Aims
To acquaint students with more advanced parts of the formal language theory, with basics of the theory of computability, and with basic terms of the complexity theory.
The students are acquainted with basic as well as more advanced terms, approaches, and results of the theory of automata and formal languages and with basics of the theory of computability and complexity allowing them to better understand the nature of the various ways of describing and implementing computer-aided systems. The students acquire basic capabilities for theoretical research activities.
Study aids
Prerequisites and corequisites
Basic literature
Recommended literature
Elearning
Classification of course in study plans
branch MBS , 1 year of study, winter semester, compulsorybranch MPV , 1 year of study, winter semester, compulsorybranch MIS , 1 year of study, winter semester, compulsorybranch MIN , 1 year of study, winter semester, compulsorybranch MGM , 1 year of study, winter semester, compulsorybranch MBI , 1 year of study, winter semester, compulsorybranch MSK , 1 year of study, winter semester, compulsorybranch MMM , 1 year of study, winter semester, compulsory
specialization NSPE , 1 year of study, winter semester, compulsoryspecialization NBIO , 1 year of study, winter semester, compulsoryspecialization NSEN , 1 year of study, winter semester, compulsoryspecialization NVIZ , 1 year of study, winter semester, compulsoryspecialization NGRI , 1 year of study, winter semester, compulsoryspecialization NADE , 1 year of study, winter semester, compulsoryspecialization NISD , 1 year of study, winter semester, compulsoryspecialization NMAT , 1 year of study, winter semester, compulsoryspecialization NSEC , 1 year of study, winter semester, compulsoryspecialization NISY up to 2020/21 , 1 year of study, winter semester, compulsoryspecialization NCPS , 1 year of study, winter semester, compulsoryspecialization NHPC , 1 year of study, winter semester, compulsoryspecialization NNET , 1 year of study, winter semester, compulsoryspecialization NMAL , 1 year of study, winter semester, compulsoryspecialization NVER , 1 year of study, winter semester, compulsoryspecialization NIDE , 1 year of study, winter semester, compulsoryspecialization NEMB , 1 year of study, winter semester, compulsoryspecialization NISY , 1 year of study, winter semester, compulsoryspecialization NEMB up to 2021/22 , 1 year of study, winter semester, compulsory
Lecture
Teacher / Lecturer
Syllabus
Seminar
Fundamentals seminar
Project