Інфопакет

Автомати та формальні мови

ВК.3.02

Вибіркова дисципліна для ОП

Перший

2022/2023

6 Семестр

3

ПРН18.3. Знати математичний апарат та принципи програмування та вміти застосовувати їх у створенні програмних систем.

1. Знати основні поняття з галузі теорії множин, теорії графів, булевих функцій; основні поняття, засоби і методи теорії алгоритмів; основні формальні моделі алгоритмів; основні нерозв’язні алгоритмічні проблеми. 2. Вміти проводити комбінаторні обчислення; будувати формальні моделі алгоритмів (машини Тьюрінга). 3. Володіти елементарними навичками використання логіко-математичної символіки та програмування високорівневими мовами програмування.

Дисципліна розглядає алгоритмічні пристрої, формальні мови та складність алгоритмів. Протягом вивчення студенти мають поглибити знання апарату скінченних автоматів та регулярних виразів, навчитись використовувати регулярні вирази в практичних задачах, отримати поглиблені знання з теорії контекстно-вільних мов, синтаксичного аналізу та складності алгоритмів. Отримані знання дозволять ефективно працювати з регулярними виразами та скінченними автоматами; розуміти проблеми, пов’язані з NP-повнотою, та межі практичної застосовності теорії регулярних та контекстно-вільних мов. Викладається в 6 семестрі 3 курсу в обсязі – 90 год. (3 кредити ECTS), зокрема: лекції –42 год., консультації – 2 год., самостійна робота – 46 год.

Основні: 1. Hopcroft J. Introduction to automata theory, languages and computation / J. Hopcroft, J. Ullman. – Addison-Wesley publishing company, 1979. https://www.dropbox.com/sh/vznral3awh628f4/AACKTD-dYcsIF9z8jPQaOtsOa?dl=0 2. Основи дискретної математики: підруч. [для студ. вищ. навч. закл.] / Ю. В. Капітонова [та ін.]. – К.: Наукова думка, 2002. 3. Vardi, M.Y. Nontraditional applications of automata theory. / M.Y. Vardi [Internet] 4. Бюхи, Д.Р. Слабая арифметика второго порядка и конечные автоматы. // Кибернетический сборник. – 1964. – Вип. 8. – С.42-77. 5. Лисовик, Л.П. Алгоритмические вопросы для реальных функций // Кибернетика .– 1987.– №1. – С.12-17. 6. Jena, S.R. Theory of computation and application. / S.R.Jena, S.K.Swain .– 2nd ed. – New Delhi: Laxmi Publications, 2020.– URL:https://www.researchgate.net/publication/337840420_Theory_of_Computation_and_Application-_2nd_Edition_Automata_Formal_Languages_Computational_Complexity-_SR_Jena_SK_Swain ..

Лекції, консультації, самостійна робота

1. Контрольна робота 1: РН1.1, РН2.3 – 20 балів/10 балів. 2. Контрольна робота 2: РН1.1, РН1.2, РН1.3, РН2.3 – 20 балів/10 балів. 3. Практичне завдання: РН1.1, РН1.2, РН 2.1, РН2.2 – 60 балів/36 балів.

Українська