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