Просмотр исходного текста страницы Модели вычислений

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

[[Категория:Лекционные курсы кафедры МК]]

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

=== Конечные автоматы и регулярные выражения ===
<ol>
<li> Формальные языки. Операции над языками. Проблемы принадлежности слова языку, пустоты, тотальности, равенства, включения.
<li> Недетерминированные конечные автоматы. Вычисления автоматов. Автоматные языки.
<li> Детерминированные конечные автоматы. Эквивалентные состояния и эквивалентные автоматы. Алгоритм проверки эквивалентности детерминированных конечных автоматов.
<li> Минимальные детерминированные конечные автоматы. Теорема о существовании и единственности минимального детерминированного конечного автомата. Алгоритм минимизации детерминированных конечных автоматов. 
<li> Алгоритм преобразования конечного автомата к детерминированному виду. Замкнутость класса автоматных языков относительно операций над языками.
<li> Теорема о разрастании для автоматных языков. Примеры неавтоматных языков.
<li> Регулярные выражения. Алгебра регулярных выражений. Уравнения в регулярных выражениях. Теорема Клини о соответствии между регулярными выражениями и конечными автоматами.
<li> Задача проверки соответствия текста шаблону и теоретико-автоматный подход к ее решению. Задача поиска подстроки в строке. Алгоритм Ахо-Карасик.
<li> Двусторонние конечные автоматы. Теорема о соответствии между односторонними и двусторонними конечными автоматами.
</ol>

=== Вычислимые функции и рекурсивные множества ===
<ol start="8">
<li> Машины Тьюринга: основные понятия. Арифметические функции, вычислимые по Тьюрингу.
<li> Моделирование многоленточных машин Тьюринга одноленточными машинами Тьюринга.
<li> Универсальная машина Тьюринга. Теорема Клини о совпадение класса арифметических функций, вычислимых по Тьюрингу, и частично-рекурсивных функций.
<li> Существование частично-рекурсивной функции, не имеющей рекурсивных доопределений. Неразрешимость проблем самоприменимости и останова для машин Тьюринга.
<li> Сводимость алгоритмических задач. Примеры алгоритмически неразрешимых задач анализа поведения программ.
<li> Теорема Райса и примеры ее применения.
<li> Рекурсивные множества. Замкнутость класса рекурсивных множеств относительно операций объединения, пересечения и дополнения.
<li> Рекурсивно-перечислимые множества. Замкнутость класса рекурсивных множеств относительно операций объединения, пересечения. Незамкнутость класса рекурсивно-перечислимых множеств относительно дополнения.
<li> Теоремы о характеристических свойствах рекурсивно-перечислимых множеств относительно рекурсивных функций.
</ol>

=== Формальные грамматики и языки ===
<ol start="17">
<li> Формальные грамматики: основные понятия. Классификация Хомского формальных грамматик (иерархия Хомского).
<li> Праволинейные грамматики и языки. Совпадением класса праволинейных языков и класса автоматных языков. Разрешимость проблем принадлежности и эквивалентности для класса праволинейных языков.
<li> Теорема о разрастании (лемма о накачке) для автоматных языков. Примеры языков, не являющихся автоматными.
<li> Контекстно-свободные грамматики и языки. Примеры контекстно-свободных языков. Замкнутость класса контекстно-свободных языков относительно операции объединения. Разрешимость проблемы принадлежности для контекстно-свободных языков.
<li> Нормальная форма Хомского для контекстно-свободных грамматик. Приведение контекстно-свободных грамматик к нормальной форме Хомского.
<li> Теорема о разрастании (лемма о накачке) для контекстно-свободных языков. Примеры языков, не являющихся контекстно-свободными.
<li> Автоматы с магазинной памятью. Теорема о совпадении класса контекстно-свободных языков и класса языков, распознаваемых автоматами с магазинной памятью.
<li> Алгоритм Кока-Янгера-Касами синтаксического анализа контекстно-свободных языков.
<li> Незамкнутость класса контекстно-свободных языков относительно операций пересечения и дополнения.
<li> Контекстно-зависимые грамматики и языки. Примеры контекстно-зависимых языков. Разрешимость проблемы принадлежности для контекстно-зависимых языков.
<li> Грамматики типа 0 и рекурсивно-перечислимые языки. 
</ol>

=== Алгоритмически неразрешимые математические задачи ===
<ol start="28">
<li> Проблема соответствий Поста. Теорема об алгоритмической неразрешимости проблемы соответствий Поста.
<li> Алгоритмическая неразрешимость проблемы непустоты пересечения, проблемы тотальности и проблемы эквивалентности для контекстно-свободных грамматик.
<li> Примеры алгоритмически неразрешимых проблем арифметики, алгебры, комбинаторики.
</ol>

=== Литература ===

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

== Правила проведения экзамена ==

Экзамен проводится в форме письменной контрольной работы. Время, отведенное на решение задач, составляет 120 мин. Письменная контрольная работа состоит из 10 заданий. 

Задания 1-4 - это задачи требующие применения стандартных алгоритмов и методов решения. Правильное решение каждой такой задачи оценивается 2 баллами.

В заданиях 5-8 требуется сформулировать определения основных понятий, введенных в лекционном курсе. Правильное решение каждой такой задачи оценивается 1 баллом.

В задании 9 требуется сформулировать и доказать одну из теорем, рассмотренных в лекционном курсе. Правильное решение каждой такой задачи оценивается 2 баллами. 

В задании 10 требуется решить теоретическую задачу, опираясь на сведения, представленные в лекционном курсе. Правильное решение каждой такой задачи оценивается 3 баллами.

Оценка контрольной работы проводится по следующим критериям:

14-17 баллов - '''отлично''',

10-15 баллов - '''отлично''',

7-9 баллов -  '''удовлетворительно'''.