Вычислимость и сложность

2020/2021

Статус: Майнор

Кто читает: Факультет математики

Где читается: Факультет математики

Когда читается: 3, 4 модуль

Преподаватели: Колмаков Евгений Александрович, Оноприенко Анастасия Александровна, Шамканов Данияр Салкарбекович

Язык: русский

Кредиты: 5

Контактные часы: 80

Полная версия программы учебной дисциплины Задать вопрос

Аннотация

В курсе будут обсуждаться примеры неразрешимых проблем и сведение одних проблем к другим. Слушатели научатся быстро оценивать время и память, требуемые данному алгоритму при его реализации на данной вычислительной модели, различать различные виды трудности задач. Для освоения учебной дисциплины студенты должны владеть следующими знаниями и компетенциями: Математика в объеме программы средней школы.

Цель освоения дисциплины

Целями освоения дисциплины «Вычислимость и сложность» являются: знакомство с ос-новными вычислительными моделями, используемыми в теории вычислений (машины Тьюринга, частично-рекурсивные функции, машины с неограниченными регистрами), знакомство с понятиями алгоритма, вычислимой функции, разрешимых и перечислимых множеств.

Планируемые результаты обучения

В результате студент должен знать основные вычислительные модели, используемыми в теории вычислений (многоленточные машины Тьюринга, частично-рекурсивные функции, машины с неограниченными регистрами).
В результате студент должен знать понятия алгоритма, вычислимой функции, разрешимых и перечислимых множеств, нумерации вычислимых функций.
В результате студент должен уметь строить алгоритмы для решения задач.
В результате студент должен уметь приводить примеры неразрешимых проблем и научить сводимости одних проблем к другим.
В результате студент должен уметь быстро оценивать время и память, требуемые данному алгоритму при его реализации на данной вычислительной модели.
В результате студент должен владеть методами установления вычислительной трудности задач различного типа: давать представление о том, как устанавливается "эталонные задачи", и научиться сводить данную задачу к одной из эталонных трудных задач.

Содержание учебной дисциплины

Вычислительные модели: многоленточные машины Тьюринга, частично-рекурсивные функции, машины с неограниченными регистрами. Оценка времени и памяти, необходимых для реализации основных арифметических алгоритмов. Тезис Чёрча.
Понятие вычислимой функции, разрешимого множества.
Перечислимые множества.
Перечислимость и разрешимость (теорема Поста, теорема о проекции разреши-мого множества).
Теорема о графике вычислимой функции.
Универсальные вычислимые функции.
Построение перечислимого неразрешимого множества.
Алгоритмически неразрешимые проблемы в теории алгоритмов.
Примеры других алгоритмически неразрешимых проблем в алгебре и теории чисел.
m-Сводимость, m-полные перечислимые множества.
Полиномиальная эквивалентность по времени и памяти вычислительных моде-лей. Класс P функций, вычислимых за полиномиальное время.
Сводимость одной задачи к другой. Полные в данном классе задачи.
Класс NP функций, вычислимых за полиномиальное время, и эквивалентные определения.
NP-трудные и NP-полные задачи. Проблема перебора (P=NP?) и предположи-тельная трудность NP-трудных задач.
Теорема Кука-Левина об NP-полноте проблемы выполнимости нулевых функ-ций.
NP-полнота других задач: 3-КНФ, 3-РАСКРАСКА, КЛИКА, ВЕРШИННОЕ ПОКРЫТИЕ, ГАМИЛЬТОНОВ ЦИКЛ.
Класс PSPACE функций, вычислимых за полиномиальное количество памяти, и эквивалентные определения.
Теорема Савича.
PSPACE полнота задачи TQBF и других.

Элементы контроля

Первое индивидуальное домашнее задание
Первая контрольная работа
Второе домашнее задание
Вторая контрольная работа
Первое индивидуальное домашнее задание
Первая контрольная работа
Второе домашнее задание
Вторая контрольная работа

Промежуточная аттестация

Промежуточная аттестация (4 модуль)
0.3 * Вторая контрольная работа + 0.2 * Второе домашнее задание + 0.3 * Первая контрольная работа + 0.2 * Первое индивидуальное домашнее задание

Программа дисциплины