Компьютерные науки

Последнее изменение: 17/01/2019 06:37:28

Обязательный курс для первого курса магистратуры направления "Математика". В осеннем семестре 2018/19 учебного года читается по четвергам 3-й парой (12:50-14:20) в ауд. 513.

Зачет состоится 22-го января с 9:00 в ауд. 540.

Внимание: выложены вопросы и задачи к зачету

Программа курса

  • Понятие о полиномиальных и экспоненциальных алгоритмах. Устойчивость полиномиальности относительно варьирования моделей вычислений и способов организации данных.
  • Общая задача распознавания. Классы P и NP. Принадлежность классу NP задач с полиномиальной проверкой.
  • Полиномиальная сводимость. NP-полные задачи. NP-полнота задачи ВЫПОЛНИМОСТЬ.
  • Основные NP-полные задачи: 3-ВЫПОЛНИМОСТЬ, 3-СОЧЕТАНИЕ, ВЕРШИННОЕ ПОКРЫТИЕ, КЛИКА, ГАМИЛЬТОНОВ ЦИКЛ, РАЗБИЕНИЕ.
  • Сильная NP-полнота.
  • Сводимость по Тьюрингу. Примеры NP-трудных задач.
  • Эквивалентность задач оптимизации и распознавания на примере задачи коммивояжера.
  • Типы приближенных алгоритмов. Несуществование "хороших" приближенных алгоритмов для некоторых NP-полных задач.
  • L-сводимость. Класс MAXSNP. Существование приближенного полиномиального алгоритма с конечной погрешностью для задач из класса MAXSNP.

Рекомендуемая литература

  • М. Гэри, Д. Джонсон: Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982.
  • C. H. Papadimitriou: Computational Complexity. Addison Wesley, 1994.
  • S. Arora, B.Barak: Computational Complexity - A Modern Approach. Cambridge University Press, 2009.

Смотрите также: