Конспекты лекций
(2-й курс, 4-й семестр, ИУ-9)
pdf Часть 1. Алгебра высказываний. Введение. Алгебра логики. Тавтологии и эквивалентность формул. Функции алгебры логики.
pdf Часть 2. Исчисление высказываний. Основные положения теории N. Правила естественного вывода. Глобальные свойства теории N.
pdf Часть 3. Алгебра предикатов. Предикаты и кванторы. Логико-математические языки. Переименования и подстановки. Семантика логико-математического языка. Логические законы. Замены. Упрощение формул.
pdf Часть 4. Исчисление предикатов. Построение теории P. Правила естественного вывода. Глобальные свойства теории P.
pdf Часть 5. Генценовские формальные системы. Исчисление GV. Исчисление GP.
pdf Часть 6. Примеры формальных теорий. Теория групп. Формальная арифметика.
pdf Часть 7. Метод резолюций. Скулемовские функции. Метод резолюций для исчисления высказываний. Метод резолюций для исчисления предикатов.
pdf Часть 8. Основные характеристики алгоритма. Интуитивное понятие алгоритма. Его отличительные черты: дискретность, детерминированность, элементарность шагов, направленность, массовость). Работа алгоритма как вычисление функции. Понятие вычислимой функции. Алгоритм как функционирование абстрактной машины.
pdf Часть 9. Нормальные алгорифмы Маркова. Алфавит и подстановки. Схемы. Нормальный алгорифм Маркова. Терминология. Примеры НА. Эквивалентные НА. Принцип нормализации.
pdf Часть 10. Нормальные алгорифмы Маркова. Основные понятия. Сочетания машин Тьюринга. Эквивалентность машин Тьюринга и нормальных алгорифмов. Обобщения машин Тьюринга
pdf Часть 11. Рекурсивные функции. Примитивно рекурсивные функции. Предикаты, простые числа и возвратная рекурсия. Частично рекурсивные функции. Универсальные рекурсивные функции. Разрешимые и перечислимые множества.
pdf Части 12 и 13. Неразрешимые алгоритмические проблемы. Сложность алгоритмов. Массовые алгоритмические проблемы. Проблема распознавания самоприменимости. Проблема распознавания применимости алгоритма к слову. Теорема Райса. Сложность нормальных алгорифмов. Сложность машин Тьюринга. Теорема Блюма об ускорении. Полиномиальные функции и класс P. Недетерминированная машина Тьюринга и классы сложности NP. Проблема P = NP. NP-полные языки.