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

Материал из Кафедра математической кибернетики
Перейти к: навигация, поиск
(→‎Литература)
 
(не показаны 92 промежуточных версий 2 участников)
Строка 1: Строка 1:
−
Лектор - профессор [[Захаров Владимир Анатольевич]].
+
Обязательный курс для студентов 418 группы на 8 семестре обучения.
 +
 
 +
Лекционная нагрузка — 24 ч., семинары — 8 ч.
 +
 
 +
== Информация 2024 года ==
 +
 
 +
Курс читает [[Савицкий Игорь Владимирович|И. В. Савицкий]].
 +
 
 +
Занятия проходят очно.
 +
 
 +
== Информация 2023 года ==
 +
 
 +
Курс читает [[Савицкий Игорь Владимирович|И. В. Савицкий]].
 +
 
 +
Занятия проходят очно.
 +
 
 +
== Информация 2022 года ==
 +
 
 +
Курс читает профессор [[Захаров Владимир Анатольевич|В. А. Захаров]].
 +
 
 +
<!--'''ПЛАН ЗАНЯТИЙ В ПЕРИОД 21.03 - 27.03'''
 +
 
 +
<ol>
 +
<li> Слушатели курса прочитывают слайды лекций 8, 9 и решают задачи, приложенные к этим лекциям, в любое удобное для них время 20.03 -- 26.03.
 +
<li> 27.03 с 10.30 до 12.00 преподаватель готов ответить на вопросы по материалам курса
 +
 
 +
по skype (login: vladimir_zakharov_msu)
 +
 
 +
и
 +
 
 +
по WhatsApp (916 220 44 24)
 +
<li> 27.03 с 12.00 до 20.00 слушатели присылают по электронной почте преподавателю решения задач 1, 3(4), 5(1,3,5,7,9,11,13,15), 7(1,2) из списка задач, приложенных к лекции.
 +
</ol>
 +
-->
 +
 
 +
В весеннем семестре 2022 года учебные занятия по курсу "Модели вычислений" будут проводиться дистанционно в разных форматах.
 +
 
 +
Лекции будут проводиться заочно.
 +
 
 +
Видеозаписи и материалы (слайды) лекций размещены в репозитории (хранилище) всех учебных материалов ф-та ВМК по адресу https://m.cs.msu.ru/index.php/s/N6FkcmFbxQkS8z9 в разделе '''ЗахаровВА''' в папке "Модели вычислений" [https://m.cs.msu.ru/index.php/s/N6FkcmFbxQkS8z9?path=%2FЗахаровВА%2FМодели%20вычислений]
 +
 
 +
Слайды всех лекций также размещены на данной странице учебного курса.
 +
 
 +
В случае необходимости будут организованы консультации в виде Zoom-конференции.
 +
 
 +
Семинарские занятия будут проводиться очно в формате Zoom-конференции.
 +
 
 +
'''ПЛАН ПРОВЕДЕНИЯ СЕМИНАРСКИХ ЗАНЯТИЙ'''
 +
 
 +
<ol>
 +
<li> Семинар 1: 18 февраля, 12.15-13.50. Тема: "Конечные автоматы и регулярные языки".
 +
<li> Семинар 2: 4 марта, 12.15-13.50. Тема: "Рекурсивные и рекурсивно перечислимые множества".
 +
<li> Семинар 3: 18 марта, 12.15-13.50. Тема: "Магазинные автоматы и контекстно-свободные языки".
 +
<li> Семинар 4: 1 апреля, 12.15-13.50. Тема: "Конечные автоматы-преобразователи, автоматы над бесконечными словами и логика S1S".
 +
</ol>
 +
 
 +
Экзамен по учебному курсу запланирован на 15 апреля 2022 г.
 +
 
 +
<!--'''[[Media: Exam-418-2019.pdf| Результаты экзамена (10.04.2019)]]'''
 +
 
 +
Вторая попытка сдачи экзамена состоится 24 апреля в 9.30 в ауд. 582.
 +
 
 +
Оценки за экзамен будут выставлены в зачетную книжку 10 апреля,
 +
в 18.00 - 19.00 в аудитории 591.
 +
-->
  
 
[[Категория:Лекционные курсы кафедры МК]]
 
[[Категория:Лекционные курсы кафедры МК]]
 +
 +
== Лекции ==
 +
 +
'''[[Media: Lecture_CM_1.pdf| Лекция 1.]]''' Формальные языки. Операции над языками.Разнообразие моделей вычислений. Конечные автоматы Рабина-Скотта. Автоматные языки. Упрощение конечных автоматов. Детерминированные конечные автоматы. Минимизация детерминированных конечных автоматов.
 +
 +
'''[[Media: Lecture_CM_2.pdf| Лекция 2.]]''' Алгоритм преобразования конечного автомата к детерминированному виду. Замкнутость класса автоматных языков относительно операций над языками. Теорема о разрастании для автоматных языков.
 +
Примеры неавтоматных языков.
 +
 +
'''[[Media: Lecture_3.pdf| Лекция 3.]]''' Регулярные выражения. Алгебра регулярных выражений. Уравнения в регулярных выражениях. Теорема Клини о соответствии между регулярными выражениями и конечными автоматами. Задача проверки соответствия текста шаблону и теоретико-автоматный подход к ее решению. Задача поиска подстроки в строке. Алгоритм Ахо-Карасик. Двусторонние конечные автоматы. Теорема о соответствии между односторонними и двусторонними конечными автоматами.
 +
 +
'''[[Media: Lecture_4.pdf| Лекция 4.]]''' Одноленточные машины Тьюринга. Вычисления машин Тьюринга. Рекурсивные и рекурсивно-перечислимые языки. Моделирование односторонних и многоленточных машин Тьюринга одноленточными машинами Тьюринга. Арифметические функции, вычислимые по Тьюрингу. Характеристические теоремы для рекурсивных и рекурсивно-перечислимых языки. Массовые алгоритмические проблемы и их связь с рекурсивными языками. Замкнутость классов рекурсивных и рекурсивно перечислимых языков относительно теоретико-множественных операций.
 +
 +
'''[[Media: Lecture_5.pdf| Лекция 5.]]''' Универсальные машины Тьюринга. Неразрешимость проблемы останова для машин Тьюринга. Сводимость алгоритмических проблем. Примеры алгоритмически неразрешимых проблем программирования. Функциональные (семантические) свойства программ. Теорема Райса.
 +
 +
'''[[Media: Lecture_6.pdf| Лекция 6.]]''' Проблема соответствий Поста. Алгоритмическая неразрешимость проблемы соответствий Поста. Многоголовочные конечные автоматы. Алгоритмическая неразрешимость проблемы останова для многоголовочных конечных автоматов. Ассоциативные исчисления. Алгоритмическая неразрешимость проблемы достижимости для полусистем Туэ. Примеры алгоритмически неразрешимых проблем математики: проблема разрешимости диофантовых уравнений, проблема мозаики.  Машины Минского. Универсальность модели вычислений машин Минского.
 +
 +
'''[[Media: Lecture_7.pdf| Лекция 7.]]''' Формальные грамматики. Классификация формальных грамматик. Иерархия Хомского формальных языков. Неограниченные грамматики и рекурсивно перечислимые языки. Праволинейные грамматики. Совпадение класса автоматных языков и класса праволинейных языков. Контекстно-свободные грамматики. Устранение недостижимых и &epsilon;-правил. Нормальная форма Хомского контекстно-свободных грамматик. Приведение контекстно-свободных грамматик к нормальной форме Хомского.
 +
 +
'''[[Media: Seminar_3-1.pdf| Задачи по теме Лекции 7.]]'''
 +
 +
'''[[Media: Lecture_8.pdf| Лекция 8.]]''' Деревья синтаксического разбора. Теорема о разрастании для контекстно-свободных языков. Примеры языков, не являющихся контекстно-свободными. Автоматы с магазинной памятью и их свойства. Взаимосвязь контекстно-свободных языков и автоматов с магазинной памятью. Детерминированные магазинные автоматы.
 +
 +
'''[[Media: Lecture_9-full.pdf| Лекция 9.]]''' Свойства замкнутости контекстно-свободных языков. Алгоритмические проблемы для КС-языков. Неразрешимость проблемы эквивалентности для контекстно-свободных грамматик. Алгоритм Кока-Касами-Янгера синтаксического анализа контекстно-свободных языков. Детерминированные КС-языки и синтаксические анализаторы. LL(k)-грамматики. Контекстно-зависимые грамматики.
 +
 +
'''[[Media: Seminar_3-2.pdf| Задачи по теме Лекций 8 и 9.]]'''
 +
 +
'''[[Media: Lecture_10.pdf| Лекция 10.]]''' Конечные автоматы-преобразователи. Рациональные отношения и их свойства. Описание рациональных отношений регулярными выражениями. Свойства замкнутости класса рациональных отношений. Неразрешимость проблемы эквивалентности для недетерминированных автоматов-преобразователей. Разрешимость проблемы эквивалентности для детерминированных автоматов-преобразователей.
 +
 +
'''[[Media: Seminar_4-1.pdf| Задачи по теме Лекции 10.]]'''
 +
 +
'''[[Media: Lecture_11a.pdf| Лекция 11.]]''' Реагирующие системы вычислений. Автоматы Бюхи. &omega;-регулярные языки. Свойства замкнутости класса &omega;-регулярных языков. Алгоритмические проблемы для автоматов Бюхи. Другие виды &omega;-автоматов: автоматы Рабина, автоматы Маллера. Взаимосвязь детерминированных и недетерминированных &omega;-автоматов. Применение &omega;-автоматов для верификации реагирующих систем.
 +
 +
'''[[Media: Lecture_12a.pdf| Лекция 12.]]''' Логический способ описания языков. Монадическая предикатов логика второго порядка S1S. Взаимосвязь логики S1S и &omega;-автоматов. Другие логики предикатов второго порядка.
 +
 +
'''[[Media: Seminar_4-2.pdf| Задачи по теме Лекциям 11 и 12.]]'''
 +
 +
== Семинарские занятия ==
 +
 +
'''[[Media: Seminar_1.pdf| Семинар 1]]''' (после лекции 3). Построение конечных автоматов для заданных языков. Преобразование недетерминированных автоматов к детерминированным. Минимизация детерминированных автоматов. Распознавание автоматности языков, полученных при помощи теоретико-множественных и алгебраических операций над автоматными языками. Доказательство неавтоматности языков. Построение регулярных выражений для автоматных языков. Построение автоматов, соответствующих регулярным выражениям.
 +
 +
'''[[Media: Seminar_2.pdf| Семинар 2]]''' (после лекции 6). Доказательство нерекурсивности и рекурсивной перечислимости языков. Использование метода сводимости для доказательства алгоритмической неразрешимости массовых проблем.
 +
 +
'''[[Media: Seminar_3.pdf| Семинар 3]]''' (после лекции 9). Построение контекстно-свободных грамматик и магазинных автоматов. Приведение контекстно-свободных грамматик к нормальной форме Хомского. Применение алгоритма Кока-Касами-Янгера для проверки принадлежности заданного слова заданному контекстно-свободному языку. Применение теорем о разрастании для классификации языков.
 +
 +
'''[[Media: Seminar_4.pdf| Семинар 4]]''' (после лекции 12). Построение конечных автоматов-преобразователей, распознающих заданные рациональные отношения. Построение автоматов Бюхи и формул логики S1S, задающих регулярные omega-языки.
  
 
== Программа курса ==   
 
== Программа курса ==   
Строка 7: Строка 116:
 
=== Конечные автоматы и регулярные выражения ===
 
=== Конечные автоматы и регулярные выражения ===
 
<ol>
 
<ol>
−
<li> Конечные автоматы: определения основных понятий. Языки, распознаваемые конечными автоматами. Замкнутость класса автоматных языков относительно операций объединения, пересечения и дополнения.
+
<li> Формальные языки. Операции над языками. Проблемы принадлежности слова языку, пустоты, тотальности, равенства, включения.
−
<li> Детерминированные конечные автоматы. Метод детерминизации конечных автоматов.
+
<li> Недетерминированные конечные автоматы. Вычисления автоматов. Автоматные языки.
−
<li> Алгоритм проверки эквивалентности детерминированных конечных автоматов.
+
<li> Детерминированные конечные автоматы. Эквивалентные состояния и эквивалентные автоматы. Алгоритм проверки эквивалентности детерминированных конечных автоматов.
−
<li> Минимальные детерминированные конечные автоматы. Алгоритм минимизации детерминированных конечных автоматов.  
+
<li> Минимальные детерминированные конечные автоматы. Теорема о существовании и единственности минимального детерминированного конечного автомата. Алгоритм минимизации детерминированных конечных автоматов.  
−
<li> Алгебра регулярных выражений. Примеры тождеств в алгебре регулярных выражений. Регулярные языки.
+
<li> Алгоритм преобразования конечного автомата к детерминированному виду. Замкнутость класса автоматных языков относительно операций над языками.
−
<li> Алгоритм построения регулярного выражения, определяющего язык, распознаваемый заданным конечным автоматом.
+
<li> Теорема о разрастании для автоматных языков. Примеры неавтоматных языков.
−
<li> Алгоритм построения конечного автомата, распознающего язык, определяемый заданным регулярным выражением. Теорема Клини о совпадении класса автоматных языков и класса регулярных языков.
+
<li> Регулярные выражения. Алгебра регулярных выражений. Уравнения в регулярных выражениях. Теорема Клини о соответствии между регулярными выражениями и конечными автоматами.
 +
<li> Задача проверки соответствия текста шаблону и теоретико-автоматный подход к ее решению. Задача поиска подстроки в строке. Алгоритм Ахо-Карасик.
 +
<li> Двусторонние конечные автоматы. Теорема о соответствии между односторонними и двусторонними конечными автоматами.
 
</ol>
 
</ol>
−
=== Вычислимые функции и рекурсивные множества ===
+
 
−
<ol start="8">
+
=== Машины Тьюринга и рекурсивно перечислимые языки ===
−
<li> Машины Тьюринга: основные понятия. Арифметические функции, вычислимые по Тьюрингу.
+
<ol start="10">
−
<li> Моделирование многоленточных машин Тьюринга одноленточными машинами Тьюринга.
+
<li> Одноленточные машины Тьюринга. Вычисления машин Тьюринга. Рекурсивные и рекурсивно-перечислимые языки.
−
<li> Универсальная машина Тьюринга. Теорема Клини о совпадение класса арифметических функций, вычислимых по Тьюрингу, и частично-рекурсивных функций.
+
<li> Моделирование односторонних и многоленточных машин Тьюринга одноленточными машинами Тьюринга.  
−
<li> Существование частично-рекурсивной функции, не имеющей рекурсивных доопределений. Неразрешимость проблем самоприменимости и останова для машин Тьюринга.
+
<li> Арифметические функции, вычислимые по Тьюрингу. Характеристические теоремы для рекурсивных и рекурсивно-перечислимых языки.
−
<li> Сводимость алгоритмических задач. Примеры алгоритмически неразрешимых задач анализа поведения программ.
+
<li> Массовые алгоритмические проблемы и их связь с рекурсивными языками
−
<li> Теорема Райса и примеры ее применения.
+
<li> Универсальные машины Тьюринга. Неразрешимость проблемы останова для машин Тьюринга.  
−
<li> Рекурсивные множества. Замкнутость класса рекурсивных множеств относительно операций объединения, пересечения и дополнения.
+
<li> Сводимость алгоритмических проблем. Примеры алгоритмически неразрешимых проблем программирования.  
−
<li> Рекурсивно-перечислимые множества. Замкнутость класса рекурсивных множеств относительно операций объединения, пересечения. Незамкнутость класса рекурсивно-перечислимых множеств относительно дополнения.
+
<li> Функциональные (семантические) свойства программ. Теорема Райса.
−
<li> Теоремы о характеристических свойствах рекурсивно-перечислимых множеств относительно рекурсивных функций.
+
<li> Замкнутость классов рекурсивных и рекурсивно перечислимых языков относительно теоретико-множественных операций.  
 +
<li> Проблема соответствий Поста. Алгоритмическая неразрешимость проблемы соответствий Поста.
 +
<li> Многоголовочные конечные автоматы. Алгоритмическая неразрешимость проблемы останова для многоголовочных конечных автоматов.  
 +
<li> Ассоциативные исчисления. Алгоритмическая неразрешимость проблемы достижимости для полусистем Туэ.
 +
<li> Примеры алгоритмически неразрешимых проблем математики: проблема разрешимости диофантовых уравнений, проблема мозаики.  Машины Минского. Универсальность модели вычислений машин Минского.
 
</ol>
 
</ol>
  
−
=== Формальные грамматики и языки ===
+
=== Контекстно-свободные языки и автоматы с магазинной памятью===
−
<ol start="17">
+
<ol start="22">
−
<li> Формальные грамматики: основные понятия. Классификация Хомского формальных грамматик (иерархия Хомского).
+
<li> Формальные грамматики. Классификация формальных грамматик. Иерархия Хомского формальных языков.
−
<li> Праволинейные грамматики и языки. Совпадением класса праволинейных языков и класса автоматных языков. Разрешимость проблем принадлежности и эквивалентности для класса праволинейных языков.
+
<li> Праволинейные грамматики. Совпадение класса автоматных языков и класса праволинейных языков.
−
<li> Теорема о разрастании (лемма о накачке) для автоматных языков. Примеры языков, не являющихся автоматными.
+
<li> Неограниченные грамматики и рекурсивно перечислимые языки.
−
<li> Контекстно-свободные грамматики и языки. Примеры контекстно-свободных языков. Замкнутость класса контекстно-свободных языков относительно операции объединения. Разрешимость проблемы принадлежности для контекстно-свободных языков.
+
<li> Контекстно-свободные грамматики. Устранение недостижимых и &epsilon;-правил. Нормальная форма Хомского контекстно-свободных грамматик. Приведение контекстно-свободных грамматик к нормальной форме Хомского.
−
<li> Нормальная форма Хомского для контекстно-свободных грамматик. Приведение контекстно-свободных грамматик к нормальной форме Хомского.
+
<li> Деревья синтаксического разбора. Теорема о разрастании для контекстно-свободных языков. Примеры языков, не являющихся контекстно-свободными.
−
<li> Теорема о разрастании (лемма о накачке) для контекстно-свободных языков. Примеры языков, не являющихся контекстно-свободными.
+
<li> Автоматы с магазинной памятью и их свойства. Взаимосвязь контекстно-свободных языков и автоматов с магазинной памятью.
−
<li> Автоматы с магазинной памятью. Теорема о совпадении класса контекстно-свободных языков и класса языков, распознаваемых автоматами с магазинной памятью.
+
<li> Теоремы о замкнутости и незамкнутости класса контекстно-свободных языков относительно операций над формальными языками. Алгоритм проверки пустоты для контекстно-свободных грамматик.
−
<li> Алгоритм Кока-Янгера-Касами синтаксического анализа контекстно-свободных языков.
+
<li> Алгоритмическая неразрешимость проблем эквивалентности и тотальности для контекстно-свободных грамматик.
−
<li> Незамкнутость класса контекстно-свободных языков относительно операций пересечения и дополнения.
+
<li> Задача синтаксического анализа. Алгоритм Кока-Касами-Янгера проверки принадлежности слова контекстно-свободному языку. Детерминированные автоматы с магазинной памятью и LL(1) грамматики.
−
<li> Контекстно-зависимые грамматики и языки. Примеры контекстно-зависимых языков. Разрешимость проблемы принадлежности для контекстно-зависимых языков.
+
<li> Контекстно-зависимые грамматики. Взаимосвязь контекстно-зависимых грамматик и машин Тьюринга с линейно-ограниченной памятью.
−
<li> Грамматики типа 0 и рекурсивно-перечислимые языки.  
+
 
</ol>
 
</ol>
  
−
=== Алгоритмически неразрешимые математические задачи ===
+
=== Автоматы над бесконечными словами и темпоральные логики ===
−
<ol start="28">
+
<ol start="32">
−
<li> Проблема соответствий Поста. Теорема об алгоритмической неразрешимости проблемы соответствий Поста.
+
<li> Конечные автоматы-преобразователи (трансдьюсеры) и рациональные отношения. Детерминированные трансдьюсеры.
−
<li> Алгоритмическая неразрешимость проблемы непустоты пересечения, проблемы тотальности и проблемы эквивалентности для контекстно-свободных грамматик.
+
<li> Свойства замкнутости класса рациональных отношений.
−
<li> Примеры алгоритмически неразрешимых проблем арифметики, алгебры, комбинаторики.
+
<li> Алгоритм проверки эквивалентности детерминированных трансдьюсеров.  
 +
<li> Алгоритмическая неразрешимость проблемы эквивалентности недетерминированных трансдьюсеров.
 +
<li> Конечные автоматы над бесконечными словами (автоматы Бюхи, Рабина, Мюллера) и их свойства. 
 +
<li> &omega;-регулярные языки. Алгоритм проверки пустоты для &omega;-автоматов.
 +
<li> Замкнутость класса &omega;-регулярных языков относительно теоретико-множественных операций.
 +
<li> Монадическая логика 2-го порядка S1S
 +
<li> Взаимосвязь логики S1S с &omega;-регулярными языками.  
 
</ol>
 
</ol>
  
Строка 66: Строка 186:
 
== Правила проведения экзамена ==
 
== Правила проведения экзамена ==
  
−
Экзамен проводится в форме письменной контрольной работы. Время, отведенное на решение задач, составляет 120 мин. Письменная контрольная работа состоит из 10 заданий.  
+
<!-- Экзамен состоится 22 апреля. Начало экзамена 9.00 в ауд. 505
 +
 
 +
Консультация состоится 21 апреля в 10.30, в ауд. 503
 +
 
 +
Выставление оценок будет проведено 25 апреля, в 12.30, в ауд. 591.
 +
 
 +
'''Бонусные баллы:'''
 +
<ol>
 +
<li> Савицкий И. 30 баллов
 +
<li> Вершинин 20 баллов
 +
<li> Мельник М. 5 баллов
 +
</ol>
 +
 
 +
'''[[Media: Exam-418-2016.docx| Результаты экзамена 22.04.2016.]]'''
 +
 
 +
'''Студенты Бежовец и Кравцов имеют право на вторую попытку сдачи экзамена 10 мая, в 11.00 в ауд. 591.''' -->
 +
 
 +
Экзамен проводится в форме письменной контрольной работы. Время, отведенное на решение задач, составляет 180 мин. Письменная контрольная работа состоит из 16 заданий, которые разделены на 4 блока, по четыре задания в каждом.
  
−
Задания 1-4 - это задачи требующие применения стандартных алгоритмов и методов решения. Правильное решение каждой такой задачи оценивается 2 баллами.
+
В каждом блоке для решения предлагаются следующие задания.
  
−
В заданиях 5-8 требуется сформулировать определения основных понятий, введенных в лекционном курсе. Правильное решение каждой такой задачи оценивается 1 баллом.
+
Задания 1, 2 - стандартные практические задачи, аналогичные тем, которые рассматривались на семинарских занятиях. Правильное решение каждой такой задачи оценивается 2 баллами.
  
−
В задании 9 требуется сформулировать и доказать одну из теорем, рассмотренных в лекционном курсе. Правильное решение каждой такой задачи оценивается 2 баллами.  
+
В задании 3 требуется сформулировать определения основных понятий, сформулировать и доказать основные утверждения и теоремы, введенные в лекционном курсе. Правильное решение каждой такой задачи оценивается 2 баллами.
  
−
В задании 10 требуется решить теоретическую задачу, опираясь на сведения, представленные в лекционном курсе. Правильное решение каждой такой задачи оценивается 3 баллами.
+
В задании 4 требуется решить теоретическую задачу, опираясь на сведения, представленные в лекционном курсе. Правильное решение каждой такой задачи оценивается 3 баллами.
  
 
Оценка контрольной работы проводится по следующим критериям:
 
Оценка контрольной работы проводится по следующим критериям:
  
−
14-17 баллов - '''отлично''',
+
28-36 баллов - '''отлично''',
  
−
10-15 баллов - '''отлично''',
+
20-27 баллов - '''хорошо''',
  
−
7-9 баллов -  '''удовлетворительно'''.
+
13-19 баллов -  '''удовлетворительно'''.

Текущая версия на 18:57, 6 февраля 2024

Обязательный курс для студентов 418 группы на 8 семестре обучения.

Лекционная нагрузка — 24 ч., семинары — 8 ч.

Информация 2024 года

Курс читает И. В. Савицкий.

Занятия проходят очно.

Информация 2023 года

Курс читает И. В. Савицкий.

Занятия проходят очно.

Информация 2022 года

Курс читает профессор В. А. Захаров.


В весеннем семестре 2022 года учебные занятия по курсу "Модели вычислений" будут проводиться дистанционно в разных форматах.

Лекции будут проводиться заочно.

Видеозаписи и материалы (слайды) лекций размещены в репозитории (хранилище) всех учебных материалов ф-та ВМК по адресу https://m.cs.msu.ru/index.php/s/N6FkcmFbxQkS8z9 в разделе ЗахаровВА в папке "Модели вычислений" [1]

Слайды всех лекций также размещены на данной странице учебного курса.

В случае необходимости будут организованы консультации в виде Zoom-конференции.

Семинарские занятия будут проводиться очно в формате Zoom-конференции.

ПЛАН ПРОВЕДЕНИЯ СЕМИНАРСКИХ ЗАНЯТИЙ

  1. Семинар 1: 18 февраля, 12.15-13.50. Тема: "Конечные автоматы и регулярные языки".
  2. Семинар 2: 4 марта, 12.15-13.50. Тема: "Рекурсивные и рекурсивно перечислимые множества".
  3. Семинар 3: 18 марта, 12.15-13.50. Тема: "Магазинные автоматы и контекстно-свободные языки".
  4. Семинар 4: 1 апреля, 12.15-13.50. Тема: "Конечные автоматы-преобразователи, автоматы над бесконечными словами и логика S1S".

Экзамен по учебному курсу запланирован на 15 апреля 2022 г.

Лекции

Лекция 1. Формальные языки. Операции над языками.Разнообразие моделей вычислений. Конечные автоматы Рабина-Скотта. Автоматные языки. Упрощение конечных автоматов. Детерминированные конечные автоматы. Минимизация детерминированных конечных автоматов.

Лекция 2. Алгоритм преобразования конечного автомата к детерминированному виду. Замкнутость класса автоматных языков относительно операций над языками. Теорема о разрастании для автоматных языков. Примеры неавтоматных языков.

Лекция 3. Регулярные выражения. Алгебра регулярных выражений. Уравнения в регулярных выражениях. Теорема Клини о соответствии между регулярными выражениями и конечными автоматами. Задача проверки соответствия текста шаблону и теоретико-автоматный подход к ее решению. Задача поиска подстроки в строке. Алгоритм Ахо-Карасик. Двусторонние конечные автоматы. Теорема о соответствии между односторонними и двусторонними конечными автоматами.

Лекция 4. Одноленточные машины Тьюринга. Вычисления машин Тьюринга. Рекурсивные и рекурсивно-перечислимые языки. Моделирование односторонних и многоленточных машин Тьюринга одноленточными машинами Тьюринга. Арифметические функции, вычислимые по Тьюрингу. Характеристические теоремы для рекурсивных и рекурсивно-перечислимых языки. Массовые алгоритмические проблемы и их связь с рекурсивными языками. Замкнутость классов рекурсивных и рекурсивно перечислимых языков относительно теоретико-множественных операций.

Лекция 5. Универсальные машины Тьюринга. Неразрешимость проблемы останова для машин Тьюринга. Сводимость алгоритмических проблем. Примеры алгоритмически неразрешимых проблем программирования. Функциональные (семантические) свойства программ. Теорема Райса.

Лекция 6. Проблема соответствий Поста. Алгоритмическая неразрешимость проблемы соответствий Поста. Многоголовочные конечные автоматы. Алгоритмическая неразрешимость проблемы останова для многоголовочных конечных автоматов. Ассоциативные исчисления. Алгоритмическая неразрешимость проблемы достижимости для полусистем Туэ. Примеры алгоритмически неразрешимых проблем математики: проблема разрешимости диофантовых уравнений, проблема мозаики. Машины Минского. Универсальность модели вычислений машин Минского.

Лекция 7. Формальные грамматики. Классификация формальных грамматик. Иерархия Хомского формальных языков. Неограниченные грамматики и рекурсивно перечислимые языки. Праволинейные грамматики. Совпадение класса автоматных языков и класса праволинейных языков. Контекстно-свободные грамматики. Устранение недостижимых и ε-правил. Нормальная форма Хомского контекстно-свободных грамматик. Приведение контекстно-свободных грамматик к нормальной форме Хомского.

Задачи по теме Лекции 7.

Лекция 8. Деревья синтаксического разбора. Теорема о разрастании для контекстно-свободных языков. Примеры языков, не являющихся контекстно-свободными. Автоматы с магазинной памятью и их свойства. Взаимосвязь контекстно-свободных языков и автоматов с магазинной памятью. Детерминированные магазинные автоматы.

Лекция 9. Свойства замкнутости контекстно-свободных языков. Алгоритмические проблемы для КС-языков. Неразрешимость проблемы эквивалентности для контекстно-свободных грамматик. Алгоритм Кока-Касами-Янгера синтаксического анализа контекстно-свободных языков. Детерминированные КС-языки и синтаксические анализаторы. LL(k)-грамматики. Контекстно-зависимые грамматики.

Задачи по теме Лекций 8 и 9.

Лекция 10. Конечные автоматы-преобразователи. Рациональные отношения и их свойства. Описание рациональных отношений регулярными выражениями. Свойства замкнутости класса рациональных отношений. Неразрешимость проблемы эквивалентности для недетерминированных автоматов-преобразователей. Разрешимость проблемы эквивалентности для детерминированных автоматов-преобразователей.

Задачи по теме Лекции 10.

Лекция 11. Реагирующие системы вычислений. Автоматы Бюхи. ω-регулярные языки. Свойства замкнутости класса ω-регулярных языков. Алгоритмические проблемы для автоматов Бюхи. Другие виды ω-автоматов: автоматы Рабина, автоматы Маллера. Взаимосвязь детерминированных и недетерминированных ω-автоматов. Применение ω-автоматов для верификации реагирующих систем.

Лекция 12. Логический способ описания языков. Монадическая предикатов логика второго порядка S1S. Взаимосвязь логики S1S и ω-автоматов. Другие логики предикатов второго порядка.

Задачи по теме Лекциям 11 и 12.

Семинарские занятия

Семинар 1 (после лекции 3). Построение конечных автоматов для заданных языков. Преобразование недетерминированных автоматов к детерминированным. Минимизация детерминированных автоматов. Распознавание автоматности языков, полученных при помощи теоретико-множественных и алгебраических операций над автоматными языками. Доказательство неавтоматности языков. Построение регулярных выражений для автоматных языков. Построение автоматов, соответствующих регулярным выражениям.

Семинар 2 (после лекции 6). Доказательство нерекурсивности и рекурсивной перечислимости языков. Использование метода сводимости для доказательства алгоритмической неразрешимости массовых проблем.

Семинар 3 (после лекции 9). Построение контекстно-свободных грамматик и магазинных автоматов. Приведение контекстно-свободных грамматик к нормальной форме Хомского. Применение алгоритма Кока-Касами-Янгера для проверки принадлежности заданного слова заданному контекстно-свободному языку. Применение теорем о разрастании для классификации языков.

Семинар 4 (после лекции 12). Построение конечных автоматов-преобразователей, распознающих заданные рациональные отношения. Построение автоматов Бюхи и формул логики S1S, задающих регулярные omega-языки.

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

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

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

Машины Тьюринга и рекурсивно перечислимые языки

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

Контекстно-свободные языки и автоматы с магазинной памятью

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

Автоматы над бесконечными словами и темпоральные логики

  1. Конечные автоматы-преобразователи (трансдьюсеры) и рациональные отношения. Детерминированные трансдьюсеры.
  2. Свойства замкнутости класса рациональных отношений.
  3. Алгоритм проверки эквивалентности детерминированных трансдьюсеров.
  4. Алгоритмическая неразрешимость проблемы эквивалентности недетерминированных трансдьюсеров.
  5. Конечные автоматы над бесконечными словами (автоматы Бюхи, Рабина, Мюллера) и их свойства.
  6. ω-регулярные языки. Алгоритм проверки пустоты для ω-автоматов.
  7. Замкнутость класса ω-регулярных языков относительно теоретико-множественных операций.
  8. Монадическая логика 2-го порядка S1S
  9. Взаимосвязь логики S1S с ω-регулярными языками.

Литература

  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 с.

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

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

В каждом блоке для решения предлагаются следующие задания.

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

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

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

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

28-36 баллов - отлично,

20-27 баллов - хорошо,

13-19 баллов - удовлетворительно.

Источник — «https://mk.cs.msu.ru/index.php?title=Модели_вычислений&oldid=10900»