NETB157 Автомати и изчислимост
Анотация:
The course presents a short introduction to the theory of computation. In studying this subject we seek to determine what can and cannot be computed, how quickly, with how much memory, and on which type of computational model. The subject has obvious connections with engineering practice, and, as in many sciences, it also has purely philosophical aspects. The theory of computability requires a precise definition of a computer. So the course focuses on definitions and properties of mathematical model of computations such as finite automata, pushdown automata, formal grammars and Turing machine. Using these models the problems could be classified as those that are solvable and those that are not. In the end of the course we concern the Halting problem as an example of algorithmically unsolvable problem.
Преподавател(и):
гл. ас. Стоян Боев д-р
проф. Иван Ланджев д.н.
Описание на курса:
Компетенции:
The graduated students
1) know:
• fundamental capabilities and limitations of computers;
• basic terminology in the theory of computation – alphabet, string, language;
• fundamental computational models (finite automata, pushdown automata, Turing machine and formal grammars)
• Chomsky hierarchy of formal grammars
2) can:
• design DFA and NDFA;
• build an equivalent DFA by given NDFA;
• build a DFA from regular expression and inverse;
• prove that a language is nonregular;
• build a PDA by given context-free language;
• build a parse tree by given context-free grammar;
• make computations with Turing machine.
Предварителни изисквания:
• basic knowledge of definitions and statements in set theory;
• basic knowledge of relations and functions;
• basic knowledge of operations with sets and functions.
Форми на провеждане:
Редовен
Учебни форми:
Лекция
Език, на който се води курса:
Английски
Теми, които се разглеждат в курса:
Литература по темите:
• Lecture notes and presentations in Moodle, chief assist. prof. Stoyan Boev
• M.Sipser, Introduction to the theory of computation, Thomson Course Technology, 2006
• Kenneth H. Rosen, Descrete mathematics and its applications, 2007
Средства за оценяване:
The assesment for the course is based on two online tests and one attendence test. The average mark must be at least 4.