Мета курсу:
Ознайомити студентів з основними поняттями і методами теорії автоматів та формальних мов, навчити їх синтезувати автомати, розпізнавати складність масових проблем.
Приблизний перелік тем курсу:
Детерміновані й недетерміновані скінченні автомати.
Формальні мови, їх зв'язок з автоматами.
Граматики, їх класифікація.
Контекстно-вільні граматики,їх властивості й приклади.
Автомати з магазинною пам'яттю, їх зв'язки з контекстно-вільними граматиками.
Машини Т'юрінґа, їх зв'язок з комп'ютерними обчисленнями.
Розв'язні й нерозв'язні масові проблеми.
Класи складності масових проблем. P і NP класи. Приклади.
NP-повні класи. Приклади.
Ієрархія класів складності.
Література:
Дж.Хопкрофт, Р.Мотвани, Дж.Ульман. Введение в теорию автоматов, языков и вычислений. Вильямс, 2008.
Короткова М.А. Математическая теория автоматов. Учебное посо- бие. М.: МИФИ, 2008.
P.Linz. An Introduction to Formal Languages and Automata. Johnes & Barlett Learning, 2012.
J.A.Anderson. Automata Theory with Modern Applications. Cambridge University Press, 2006.
Передумови навчання:
Знання елементів формальної логіки, теорії груп і напівгруп.