Введение в теорию сложности вычислений - учебный курс | ИСТИНА – Интеллектуальная Система Тематического Исследования НАукометрических данных

Автор: Татузов А.А.
Год создания: 2015
Организация: МГУ имени М.В. Ломоносова
Описание: В курсе изучаются способы классификация вычислительных задач по вычислительной сложности. Рассматриваются однородные (машины Тьюринга) и неоднородные (СФЭ) модели вычислений. Изучаются классы задач, построенных на основе вычислений в специальных моделях (недетерминированные вычисления, интерактивные доказательства) с различными ограничениями по сложности (по времени работы алгоритма, по объему используемой памяти, по размеру СФЭ, по объему коммуникационных сообщений). Разбирается понятие эффективного вычисления, приводится и доказывается ряд теорем об иерархии и ускорении, формулируется тезис Эдмондса (полиномиальный тезис Тьюринга). Исследуются различные виды сводимостей между вычислительными задачами, приводятся условные (зависящие от предположения о несовпадении классов P и NP и тп.) нижние оценки сложности вычислений. Вводится понятие релятивизации (вычисления с оракулом) и доказываются теоремы о невозможности разрешения ряда сложностных проблем (в том числе P=NP) с помощью релятивизируемых методов. В курсе рассматриваются основные сложностные классы и доказываются теоремы об их взаимосвязи, в том числе рассматриваются классы полиномиальной иерархии, классы языков, имеющих интерактивные доказательства, экспоненциальные классы сложностей, функциональные классы сложностей, классы, связанные с понятиями параллельной и коммуникационной сложности.
Добавил в систему: Татузов Алексей Александрович

	ИСТИНА	Войти в систему Регистрация
	ИСТИНА ИНХС РАН
	Главная Поиск Статистика О проекте Помощь

ИСТИНА

ИСТИНА ИНХС РАН

Введение в теорию сложности вычисленийучебный курс

Преподавание курса