Брагилевский В.Н. Лекции по теории алгоритмов

СПб.: Высшая школа менеджмента Санкт-Петербургского университета, 2019. — 113 с.Введение в теорию алгоритмов.
Теория алгоритмов и понятие вычисления.
Возникновение теории алгоритмов.
Структура курса.
Вычислительные парадигмы и задачи.
Вычислимые функции.
Модели вычислений.
Нормальные алгорифмы Маркова.
Алфавит, слова, конкатенация слов, иодслова и вхождения.
Марковские подстановки и их применение.
Схемы нормальных алгорифмов.
Примеры нормальных алгорифмов.
Расширение алфавита и алгорифмы над алфавитом.
Нормально вычислимые функции.
λ-исчисление Чёрча.
Определение λ-термов.
Свободные и связанные переменные.
Подстановка.
Редукция термов.
Стратегии редукции.
Представление данных в λ-исчислении.
Комбинаторы неподвижной точки и рекурсия.
Локальные объявления.
Комбинаторная логика.
Машины Тьюринга.
Машины с неограниченными регистрами.
Определение, вычислимые функции.
Примеры.
Операторы композиции, примитивной рекурсии и неограниченного поиска.
Другие модели вычислений.
Машины Поста.
Модель 𝒫′′.
Эквивалентность моделей и тезис Чёрча—Тьюринга.
Теория вычислимости.
Примитивная рекурсивность.
Примитивно рекурсивные функции.
Рекурсивные и примитивно рекурсивные отношения.
Ограниченная квантификация и ограниченный поиск.
Примеры.
Арифметизация вычислений.
Кодирование числовых последовательностей.
Кодирование регистровых машин.
Конфигурации, переходы и их кодирование.
Завершающиеся вычисления и основная теорема.
Следствия.
Полурекурсивные отношения и неразрешимые задачи.
Полурекурсивные отношения.
Разрешимые и нолуразрешимые задачи и их дополнения.
Пример неразрешимой задачи: проблема останова.
Свойства замкнутости 𝒫_*.
Сводимость.
Рекурсивная перечислимость и проблема проверки рекурсивносги.
Теорема Райса.
S-m-n-теорема Клини.
Теорема о рекурсии.
Теорема Райса.
Альтернативное построение теории вычислимости.
Неразрешимые задачи за пределами теории алгоритмов.
Задача разрешимости и теорема Гёделя о неполноте.
Примеры других неразрешимых задач.
Теория сложности.
Временная сложность: классы Р, NP и ЕХР.
Классы Р и ЕХР.
Класс NP.
Соотношение между классами Р, NP и ЕХР.
Альтернативный подход к определению класса NP.
Что если P=NP?
Сводимость по Карпу и понятие NP-полноты.
Теорема Кука—Левина.
Альтернативное доказательство теоремы Кука—Левина.
Важные примеры NP-полных задач.
Задача 3SAT.
Задача 0/1-IP.
Задача о независимом множестве.
Задача коммивояжёра.
Соотношение задач разрешения и задач поиска.
Дополнения языков из NP.
Класс coNP и coNP-полнота.
Соотношения между классами P, NP и coNP.
Альтернирующая машина Тьюринга и полиномиальная иерархия.
Классы ЕХР и NEXP.
Пространственная сложность.
Классы РSPACE и NPSPACE.
РSРАСЕ-полнота и пример РSРАСЕ-полной задачи.
Обзор других разделов теории сложности.
Задания к практическим занятиям.