Подробности
Категория: Конспекты лекций

Конспекты лекций

(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-полные языки.