Теория вычислимости и вычислительной сложности

Кафедра информатики и автоматизации научных исследований

Специальность: Прикладная информатика

Преподаватель: Афраймович Л.Г.

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

В результате освоения дисциплины обучающийся должен:

Знать: основные понятия теории вычислимости и вычислительной сложности.

Уметь: Уметь доказывать алгоритмическую неразрешимость языков. Уметь строить оценки вычислительной сложности алгоритмов. Уметь доказывать полиномиальную разрешимость языков. Уметь доказывать NP-полноту и NP-трудность языков и задач на основе сводимости известных NP-языков. Уметь анализировать пространственную сложность языков и алгоритмов.

Владеть: представлениями (навыками)  об анализе сложности задач и алгоритмов.

Содержание

1. Вычислимость. 

2. Вычислительная сложность. 

3. Пространственная сложность.

4. Вероятностные алгоритмы.

5. Иерархические теоремы.

 

Литература

а) основная литература:

  1. Пападимитриу Х., Стайглиц К. Комбинаторная  оптимизация. Алгоритмы и сложность. -  М.: Мир, 1985.
  2. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. - М.: Мир, 1982.
  3. Батищев Д. И., Коган Д. И. вычислительная сложность экстремальных задач. Учебное пособие. Н. Новгород. ННГУ. 1994.

 

б) дополнительная литература:

  1. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. - М.: Мир. 1989.
  2. Т. Кормен, Ч. Лейзерсон, Р. Ривест. Алгоримты: построение и анализ. -М.: МЦНМО, 2001.
  3. Китаев, А., Шень, А., Вялый, М, Классические и квантовые вычисления. - М.: МЦНМО, 1999.

 

Отчетность

  • Семестр 5: Экз