5,6 семестры
Цель курса - изучения основного материала из математической логики, теории алгоритмов и теории языков, который создает граммотность, необходимую для осмысленного изучения программирования, а также содержит материал, используемый в дальнейших спецкурсах кафедры, таких как построение трансляторов, сложность алгоритмов, интеллектуальные системы, автоматическое доказательство теорем и другие.
Программа курса
1. Языки и автоматы
1.1. Задание языка грамматикой. Вывод в грамматике. Примеры. Грамматика, задающая правильную расстановку скобок.
1.2. Конечные автоматы. Свойства замкнутости автоматных языков. Автоматные грамматики. Эквивалентность детерминированных и недетерминированных конечных автоматов. Минимизация конечных автоматов.
1.3. Регулярные выражения и регулярные множества. Теорема о совпадении классов языков, задающихся конечными автоматами и регулярными выражениями. Свойства замкнутости регулярных языков.
1.4. Контекстно свободные языки. Каноническая форма контекстно свободной грамматики. Избавление от рекурсии. Нормальные формы Грейбах и Хомского.
1.5. Автоматы с магазином. Эквивалентность языков, представимых в автоматах с магазином и задаваемых контекстно свободной грамматикой.
1.6. Свойства замкнутости для контекстно свободных языков.
1.7. Теорема о разрастании для регулярных языков. Примеры нерегулярных языков.
1.8. Теорема Огдена о разрастании для контекстно свободных языков. Примеры языков, не являющихся контекстно свободными. Примеры контекстно свободных языков, пересечение которых не является контекстно свободным. Незамкнутость класса контекстно свободных языков относительно дополнения.
1.9. Детерминированные магазинные автоматы и кс-языки. Несовпадение классов кс-языков и детерминированных кс-языков. Замкнутость класса детерминированных кс-языков относительно дополнения.
1.10. Неоднозначные кс-грамматики и языки.
2. Алгоритмы
2.1. Машины Тьюринга. Арифметические функции, вычислимые машинами Тьюринга. Методы программирования на Машинах Тьюринга: односторонние вычисления, композиция, ветвление, повторение (цикл).
2.2. Рекурсивные функции. Рекурсивность основных арифметических функций. Теорема о совместной рекурсии.
2.3. Теоремы о вычислимости рекурсивных функций на машинах Тьюринга и о рекурсивности функций, вычислимых на машинах Тьюринга. Тезис Черча-Тьюринга.
2.4. Геделева нумерация машин Тьюринга и вычислимых функций. Существования универсальной функции и машины Тьюринга. Примеры алгоритмически неразрешимых проблем. Неразрешимость проблемы остановки. Сводимость алгоритмических проблем. Рекурсивные (разрешимые) и рекурсивно перечислимые множества.
2.5. Машины прямого доступа (RAM). Программы. Функции, вычислимые программой. Программная вычислимость рекурсивных функций. Моделирование вычислений программ на машинах Тьюринга.
3. Логические исчисления
3.1. Исчисление высказываний. Алфавит, формулы, секвенции. Схемы аксиом и правил вывода. Доказательство. Примеры доказуемых секвенций. Эквивалентность линейного доказательства и доказательства в виде дерева.
3.2. Эквивалентность формул. Булевы эквивалентности.
3.3. Теорема о замене. Нормальные формы.
3.4. Полнота и непротиворечивость.
3.5. Алгебраические системы. Язык логики предикатов. Формулы и термы. Истинность формулы в системе.
3.6. Исчисление предикатов.
3.7. Теоремы о равенстве.
3.8. Теорема о замене.
3.9. Предваренные формы. Приведение к предваренной форме.
3.10. Непротиворечивость исчисления предикатов.
3.11. Теорема Геделя о полноте исчисления предикатов.
3.12. Неразрешимость исчисления предикатов. Теорема Черча.
3.13. Формальная арифметика. Теорема Геделя о неполноте арифметики (формулировка).
3.14. Применения логики предикатов в информатике.
4. Сложность вычислений
4.1. Геделевские нумерации алгоритмов (абстрактные языки программирования) и абстрактные меры сложности вычислений.
4.2. Существование сколь угодно сложных функций (диагонали Цейтина и Рабина). Взаимная мажорируемость разных мер сложности. Теорема Блюма об ускорении (формулировка).
4.3. Меры сложности Тьюринговых вычислений. Примеры верхних оценок сигнализирующих.
4.4. Метод следов. Леммы о следах. Нижние оценки сложности для задачи перевода из унарной системы счсления в двоичную и для распознавания симметрии.
4.5. Соотношения между различными сигнализирующими одной машины Тьюринга.
4.6. Теоремы об уменьшении емкости и времени в константу раз.
4.7. Варианты вычислительных автоматов: а) многоленточые, многоголовочные и многомерные машины Тьюринга; б) автоматы Неймана, примеры Неймановых программ, задача о стрелках; в) машины с произвольным доступом к памяти. Сложность их моделирования обычными машинами Тьюринга. Класс P и его инвариантность относительно модели вычисления.
4.8. Недетерминированные машины Тьюринга. Класс NP. NP-полные (универсальные переборные) задачи. Теорема Кука-Левина о NP- полноте задачи SAT (выполнимость булевых формул).
Л и т е р а т у р а
1. А.П.Столбоушкин, М.А.Тайцлин. Математические основания информатики., Части1, 2. 3. Тверской госуниверситет, Тверь, 1998. Это пособие содержит весь материал курса и материал для упражнений.
2. А.Ахо, Дж.Ульман. Теория синтаксического анализа,перевода и компиляции, том 1. Синтаксический анализ, Москва, Мир,1978. Это пособие содержит материал раздела 1 и упражнения к этому разделу.
3. Ю.Л.Ершов, Е.А.Палютин. Математическая логика, Москва, Наука,1979. Это пособие содержит материал раздела 3.
4. И.А.Лавров, Л.Л.Максимова. Задачи по теории множеств, математической логике и теории алгоритмов, Москва, Наука,1975. Это пособие содержит материал для упражнений по разделам 2 и 3.
5. Б.А.Трахтенброт. Алгоритмы и вычислительные автоматы.- М.:"Сов. радио", 1974. Эта книга содержит материал разделов 2 и 4 (кроме 2.5. и 4.8)