Математическая логика и теория алгоритмов
2 курс 1,2 семестр
Преподаватель: Стеценко В.А., доцент кафедры ТИДМ, к.ф.м.н., доцент
4. Структура и содержание дисциплины
Общая трудоемкость дисциплины составляет 8 зачетных единиц, 288 часов из них 4 зачетные единицы (144 часа) в 3 семестре и 4 зачетные единицы (144 часа) в 4 семестре. Основными видами учебных занятий являются лекции и семинарские занятия. Аудиторные занятия составляют 54 часа в 3 семестре и 72 часа во 2 семестре.
Содержание дисциплины
№п/п
|
Наименование раздела дисциплины
|
Содержание раздела
(дидактические единицы)
|
1
|
Основные понятия формальных теорий
|
Алфавит, слова, языки. Формулы. Структура формальных теорий. Понятие интерпретации формальной теории. Способы задания формальных теорий (семантический и синтаксический). Теоремы теории (тождественно истинные формулы в данной интерпретации). Понятие полноты и непротиворечивости формальной теории.
|
2
|
Семантика исчисления высказываний
|
Язык исчисления высказываний. Формулы исчисления высказываний. Семантика исчисления высказываний. Выполнимые и общезначимые формулы. Булева алгебра. Основные равносильности булевой алгебры. Булевы функции. Фиктивные и существенные переменные булевой функции. Основные булевы функции. Расширение понятия формулы исчисления высказываний (формулы в произвольном базисе). Представление булевых функций формулами исчисления высказываний. Понятие схемы из функциональных элементов. Типовые логические элементы ЭВМ. Принцип двойственности. Представление булевых функций совершенными дизъюнктивными и конъюнктивными нормальными формами. Полиномы Жегалкина. Представление булевых функций полиномами Жегалкина. Замыкание системы булевых функций. Основные свойства замыкания. Замкнутые и полные классы в  . Примеры замкнутых классов. Полнота системы  . Достаточное условие полноты в . Классы самодвойственных, монотонных и линейных булевых функций, их замкнутость. Леммы о несамодвойственной, немонотонной и нелинейной булевой функции. Критерий полноты в . Понятие о результатах Поста.
|
3
|
Синтаксис исчисления высказываний
|
Синтаксическое задание исчисления высказываний. Аксиомы и правила вывода в исчислении высказываний. Понятия доказательства и вывода из совокупности формул в исчислении высказываний. Теорема дедукции, правило силлогизма, закон контрапозиции, приведение к абсурду. Полнота исчисления высказываний. Непротиворечивость исчисления высказываний.
|
4
|
Семантика исчисления предикатов
|
Язык исчисления предикатов. Понятие сигнатуры языка. Понятие предиката. Алгебра предикатов. Основные равносильности алгебры предикатов. Термы и формулы исчисления предикатов. Понятие алгебраической системы. Примеры алгебраических систем. Изоморфизм алгебраических систем. Интерпретация термов и формул исчисления предикатов. Выполнимые и общезначимые формулы исчисления предикатов. Понятие замкнутой формулы исчисления предикатов. Понятие модели совокупности замкнутых формул исчисления предикатов
|
5
|
Синтаксис исчисления предикатов
|
Синтаксическое задание исчисления предикатов. Аксиомы и правила вывода в исчислении предикатов. Понятия доказательства и вывода в исчислении предикатов. Теорема дедукции в исчислении предикатов. Теоремы исчисления предикатов. Непротиворечивость исчисления предикатов
|
6
|
Элементарные теории
| Понят Понятие элементарной теории. Примеры элементарных теорий Понятие непротиворечивости и полноты элементарной теории. Теорема Линденбаума. Существование модели у любой непротиворечивой элементарной теории. Полнота исчисления предикатов. Теорема Сколема - Левенгейма. Формальная арифметика. Парадокс Ришара. Арифметизация выводов. Понятие о результатах Геделя.
|
7
|
Метод резолюций
|
Метод резолюций для логики высказываний. Подстановка и унификация. Алгоритм унификации. Метод резолюций для логики предикатов. Полнота метода резолюций. Примеры использования метода резолюций.
|
8
|
Начальные понятия теории алгоритмов
|
Общее понятие алгоритма. Основные свойства алгоритма. Понятие модели вычисления (исполнителя алгоритма). Частичные функции. Вычислимые числовые функции, примеры. Разрешимые и неразрешимые предикаты. Примеры разрешимых предикатов. Понятие нумерации. Сведение любого алгоритма к вычислению числовой функции.
|
9
|
Основные модели вычислений
|
Машина с неограниченными регистрами (МНР). Понятие программы, конфигурации и вычисления. Программирование на МНР. Функции вычислимые на МНР, примеры. Основные операции над МНР. Операции суперпозиции, примитивной рекурсии и минимизации. Рекурсивные функции. Понятие о машинах Тьюринга. Формализм Мак-Карти. Диофантовы множества. Тезис Черча, доводы в его справедливость.
|
10
|
Нумерации вычислимых функций
|
Эффективная нумерация пар и троек натуральных чисел. Эффективная нумерация конечных последовательностей натуральных чисел. Эффективная нумерация программ для МНР. Существование универсальной программы. Эффективная нумерация функций вычислимых на МНР.
|
11
|
Алгоритмическая теория множеств
|
Разрешимые множества, их свойства. Перечислимые множества, их свойства. Теорема Поста. Теорема о представлении произвольного перечислимого множества как области определения некоторой вычислимой функции. Теорема о представлении произвольного перечислимого множества как области значений некоторой вычислимой функции. Пример неразрешимого перечислимого множества. Пример множества, не являющегося перечислимым. Теорема о графике вычислимой функции.
|
12
|
Неразрешимые алгоритмические проблемы
|
Диагональный метод. Доказательство существования функции не вычислимой на МНП. Массовые и индивидуальные проблемы. Алгоритмически разрешимые и алгоритмически неразрешимые проблемы. Проблема самоприменимости и проблема останова, их алгоритмическая неразрешимость. Теорема о параметризации. Алгоритмическая сводимость проблем. Теорема Успенского-Райса. Примеры алгоритмически неразрешимых проблем в информатике.
|
13
|
Введение в теорию сложности алгоритмов
|
Сложность алгоритма как функция числового аргумента. Сложность в худшем случае. Необходимость оценки сложности алгоритма с точностью до мультипликативной константы. Асимптотические обозначения. Понятие сложности в среднем. Сортировка и конечные вероятностные пространства. Применение формулы полного математического ожидания. Понятие нижней границы сложности. Оптимальные алгоритмы. Рекуррентные соотношения как средство анализа сложности алгоритмов. Реально выполнимые и реально невыполнимые алгоритмы. Понятие полиномиального алгоритма. Полиномиальный алгоритм как формализация понятия реально выполнимого алгоритма. Теорема об ускорении. Понятие класса сложности. Теорема об иерархии. Задачи распознавания. Классы P, NP и EXPTIME. Примеры задач, принадлежащих классам P и NP. Полиномиальная сводимость. NP-полные задачи. Задача о выполнимости. Теорема Кука. Задача о покрытии и задача о клике, их NP-полнота. Понятие комбинаторной задачи оптимизации, примеры. Связь между задачами распознавания и комбинаторными задачами оптимизации. Важность теории NP-полноты для практического программирования.
|
14
|
Приближенные алгоритмы
|
Понятие приближенного алгоритма для комбинаторных задач оптимизации, его точность. Жадные алгоритмы. Точность жадного алгоритма в задачи о покрытии.
|
ТЕМАТИКА РЕФЕРАТОВ, КУРСОВЫХ РАБОТ
Конечная порожденность замкнутых классов в .
Описание замкнутых классов в .
Функции многозначной логики. Основные отличия от  при k > 2.
Логики Лукасевича и простые числа.
Независимость аксиом исчисления высказываний.
Конечная базируемость классов тождеств над конечными системами булевых функций.
Критерии полноты по неявной выразимости в трехзначной логике.
Классы функций k-значной логики, замкнутые относительно операции суперпозиции.
Конечная порожденность предполных классов монотонных функций многозначной логики.
Полиномиальные представления булевых функций.
Вероятностные значения случайных булевых выражений.
Теорема Геделя о выполнимости.
Примеры разрешимых элементарных теорий.
Неразрешимость логики предикатов.
Эффективный способ проверки тождественной истинности формул, содержащих только одноместные предикаты.
Формальные модели компьютеров и вычислений.
3). Промежуточная аттестация
3 семестр – экзамен, 4 семестр - экзамен
ПЕРЕЧЕНЬ ВОПРОСОВ К ЭКЗАМЕНУ (3 семестр)
Структура формальных теорий. Понятие интерпретации формальной теории. Способы задания формальных теорий.
Язык исчисления высказываний. Формулы исчисления высказываний. Семантика исчисления высказываний. Выполнимые и общезначимые формулы.
Алгебра высказываний. Основные равносильности алгебры высказываний.
Булевы функции. Основные булевы функции. Расширение понятия формулы исчисления высказываний (формулы в произвольном базисе). Представление булевых функций формулами.
Принцип двойственности. Представление булевых функций совершенными дизъюнктивными нормальными формами.
Полиномы Жегалкина. Представление булевой функции полиномом Жегалкина.
Замкнутые и полные классы в  . Примеры замкнутых классов.
Полнота системы  . Достаточное условие полноты в .
Классы самодвойственных, монотонных и линейных булевых функций, их замкнутость.
Леммы о несамодвойственной, немонотонной и нелинейной булевых функциях
Критерий полноты в . Понятие о результатах Поста.
Синтаксическое задание исчисления высказываний. Аксиомы и правила вывода в исчислении высказываний. Понятия доказательства и вывода из совокупности формул в исчислении высказываний. Теорема дедукции.
.Полнота исчисления высказываний. Непротиворечивость исчисления высказываний.
Понятие предиката. Алгебра предикатов. Основные равносильности алгебры предикатов.
Язык исчисления предикатов. Термы и формулы исчисления предикатов. Интерпретация термов и формул исчисления предикатов. Выполнимые и общезначимые формулы исчисления предикатов. Понятие замкнутой формулы исчисления предикатов. Понятие модели совокупности замкнутых формул исчисления предикатов.
Аксиомы и правила вывода в исчислении предикатов. Теоремы исчисления предикатов. Непротиворечивость исчисления предикатов.
Метод резолюций для логики высказываний. Алгоритм унификации.
Метод резолюций для логики предикатов. Полнота метода резолюций.
ПЕРЕЧЕНЬ ВОПРОСОВ К ЭКЗАМЕНУ (4 семестр)
Общее понятие алгоритма. Основные свойства алгоритма. Вычислимые числовые функции.
Полиномиальная сводимость.
.Машина с неограниченными регистрами. Понятие программы, конфигурации и вычисления.
NP-полные задачи. Теорема Кука.
Функции, вычислимые на МНР. Тезис Черча.
NP-полнота задачи о клике.
Понятие нумерации. Эффективная нумерация пар и троек натуральных чисел.
Комбинаторные задачи оптимизации, примеры
Разрешимые и неразрешимые предикаты. Примеры разрешимых предикатов.
Понятие сложности алгоритма.
Эффективная нумерация конечных последовательностей натуральных чисел.
Реально выполнимые и реально невыполнимые алгоритмы.
Эффективная нумерация программ для МНР.
Примеры числовых невычислимых функций.
Универсальная программа. Теорема о параметризации.
Связь комбинаторных задач оптимизации с задачами распознавания.
Разрешимые и неразрешимые проблемы. Проблема самоприменимости, ее неразрешимость.
Понятие класса сложности.
Разрешимые и неразрешимые проблемы. Проблема останова, ее неразрешимость.
Понятие о верхних и нижних оценках сложности задачи
Эквивалентные программы. Инвариантные и нетривиальные свойства программ. Теорема Успенского-Райса.
Разрешимые множества и их свойства.
Классы P и EXPTIME. Примеры задач из класса P.
Перечислимые множества и их свойства.
Класс NP. Примеры задач из класса NP.
Теорема Поста.
Теорема о графике вычислимой функции
Важность теории NP-полноты для практического программирования.
Учебно-методическое и информационное обеспечение дисциплины
а) основная литература:
Конспект лекций О.Б.Лупанова по курсу «Введение в математическую логику», М.: МГУ, 2007. (http://mech.math.msu.su/department/dm/dmmc/index.htm)
Н.К Верещагин, А.Шень Языки и исчисления, М.:МЦНМО, 2000.
И.А. Лавров Математическая логика, М.: Академия, 2006.
Н. Катленд Вычислимость. Введение в теорию рекурсивных функций, М.: Мир, 1983.
В.Н. Крупский, В.Е. Плиско Теория алгоритмов, М.: Академия, 2006.
В.Л. Матросов Теория алгоритмов, М.: Прометей, МГПИ, 1989.
Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математической логике и теории алгоритмов, 3-е изд. - М.: Наука, 1995.
б) дополнительная литература:
Э. Мендельсон «Введение в математическую логику», М.: Наука, 1976.
Ю.Л. Ершов, Е.А. Палютин Математическая логика, М.: Наука, 1979.
А.В. Гладкий Математическая логика, М.: РГГУ, 1998.
Н.Н. Непейвода Прикладная логика, Новосибирск, НГУ, 2000.
А.И. Мальцев Алгоритмы и рекурсивный функции, Наука, 1965.
В.Н. Крупский Введение в сложность вычислений, М.: ФАКТОРИАЛ ПРЕСС, 2006.
С.А. Абрамов Лекции о сложности алгоритмов, М.:МЦНМО, 2009.
М. Гэри, Д. Джонсон Вычислительные машины и труднорешаемые задачи, М.: Мир, 1982.
В. Босс Перебор и эффективные алгоритмы, Лекции по математике т.10, М.: ЛКИ, 2008.
|
