Модели вычислений — различия между версиями

Материал из Кафедра математической кибернетики
Перейти к: навигация, поиск
(Вычислимые функции и рекурсивные множества)
(Формальные грамматики и языки)
Строка 36: Строка 36:
 
<li> Теорема о разрастании (лемма о накачке) для автоматных языков. Примеры языков, не являющихся контекстно-свободными.
 
<li> Теорема о разрастании (лемма о накачке) для автоматных языков. Примеры языков, не являющихся контекстно-свободными.
 
<li> Автоматы с магазинной памятью. Теорема о совпадении класса контекстно-свободных языков и класса языков, распознаваемых автоматами с магазинной памятью.
 
<li> Автоматы с магазинной памятью. Теорема о совпадении класса контекстно-свободных языков и класса языков, распознаваемых автоматами с магазинной памятью.
 +
<li> Алгоритм Кока-Янгера-Касами синтаксического анализа контекстно-свободных языков.
 
<li> Незамкнутость класса контекстно-свободных языков относительно операций пересечения и дополнения.
 
<li> Незамкнутость класса контекстно-свободных языков относительно операций пересечения и дополнения.
 
<li> Контекстно-зависимые грамматики и языки. Примеры контекстно-зависимых языков. Разрешимость проблемы принадлежности для контекстно-зависимых языков.
 
<li> Контекстно-зависимые грамматики и языки. Примеры контекстно-зависимых языков. Разрешимость проблемы принадлежности для контекстно-зависимых языков.

Версия 15:15, 30 декабря 2014

Лектор - профессор Захаров Владимир Анатольевич.

Программа курса

Конечные автоматы и регулярные выражения

  1. Конечные автоматы: определения основных понятий. Языки, распознаваемые конечными автоматами. Замкнутость класса автоматных языков относительно операций объединения, пересечения и дополнения.
  2. Детерминированные конечные автоматы. Метод детерминизации конечных автоматов.
  3. Алгоритм проверки эквивалентности детерминированных конечных автоматов.
  4. Минимальные детерминированные конечные автоматы. Алгоритм минимизации детерминированных конечных автоматов.
  5. Алгебра регулярных выражений. Примеры тождеств в алгебре регулярных выражений. Регулярные языки.
  6. Алгоритм построения регулярного выражения, определяющего язык, распознаваемый заданным конечным автоматом.
  7. Алгоритм построения конечного автомата, распознающего язык, определяемый заданным регулярным выражением. Теорема Клини о совпадении класса автоматных языков и класса регулярных языков.

Вычислимые функции и рекурсивные множества

  1. Машины Тьюринга: основные понятия. Арифметические функции, вычислимые по Тьюрингу.
  2. Моделирование многоленточных машин Тьюринга одноленточными машинами Тьюринга.
  3. Универсальная машина Тьюринга. Теорема Клини о совпадение класса арифметических функций, вычислимых по Тьюрингу, и частично-рекурсивных функций.
  4. Существование частично-рекурсивной функции, не имеющей рекурсивных доопределений. Неразрешимость проблем самоприменимости и останова для машин Тьюринга.
  5. Сводимость алгоритмических задач. Примеры алгоритмически неразрешимых задач анализа поведения программ.
  6. Теорема Райса и примеры ее применения.
  7. Рекурсивные множества. Замкнутость класса рекурсивных множеств относительно операций объединения, пересечения и дополнения.

Формальные грамматики и языки

  1. Формальные грамматики: основные понятия. Классификация Хомского формальных грамматик (иерархия Хомского).
  2. Праволинейные грамматики и языки. Совпадением класса праволинейных языков и класса автоматных языков. Разрешимость проблем принадлежности и эквивалентности для класса праволинейных языков.
  3. Теорема о разрастании (лемма о накачке) для автоматных языков. Примеры языков, не являющихся автоматными.
  4. Контекстно-свободные грамматики и языки. Примеры контекстно-свободных языков. Замкнутость класса контекстно-свободных языков относительно операции объединения. Разрешимость проблемы принадлежности для контекстно-свободных языков.
  5. Нормальная форма Хомского для контекстно-свободных грамматик. Приведение контекстно-свободных грамматик к нормальной форме Хомского.
  6. Теорема о разрастании (лемма о накачке) для автоматных языков. Примеры языков, не являющихся контекстно-свободными.
  7. Автоматы с магазинной памятью. Теорема о совпадении класса контекстно-свободных языков и класса языков, распознаваемых автоматами с магазинной памятью.
  8. Алгоритм Кока-Янгера-Касами синтаксического анализа контекстно-свободных языков.
  9. Незамкнутость класса контекстно-свободных языков относительно операций пересечения и дополнения.
  10. Контекстно-зависимые грамматики и языки. Примеры контекстно-зависимых языков. Разрешимость проблемы принадлежности для контекстно-зависимых языков.
  11. Грамматики типа 0 и рекурсивно-перечислимые языки.

Алгоритмически неразрешимые математические задачи

Литература

  1. Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. Т. 1: Синтаксический анализ. - М.: Мир, 1978. - 612 с.
  2. Ахо А., Сети Р., Ульман Дж. Компиляторы: принципы, технологии и инструменты. - М.: Вильямс, 2001. - 768 с.
  3. Верещагин Н.К., Шень А. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. - М.: МЦНМО, 1999. - 176 с.
  4. Катленд Н. Вычислимость. Введение в теорию рекурсивных функций. - М.: Мир, 1983.
  5. Льюис Ф., Розенкранц Д, Стирнз Р. Теоретические основы проектирования компиляторов. - М.: Мир, 1979.. - 656 с.
  6. Матрос Д.Ш., Поднебесова Г.Б. Теория алгоритмов. - М.: Бином, 2008. - 200 с.
  7. Пунтус А.Е., Пентус М.Р. Математическая теория формальных языков. Серия "Основы информатики и математики" - М: Бином, 2006. - 247 с.
  8. Роджерс Х. Теория рекурсивных функций и эффективная вычислимость. - М.: Мир, 1972.
  9. Хопкрофт Дж., Мотвани Р., Ульман Дж. Введение в теорию автоматов, языков и вычислений. - М.: Вильямс, 2002. - 528 с.