Сложность вычислений

Последнее изменение: 03/02/2017 12:18:53

Желающие сдать зачет/экзамен могут это сделать 18.01.17 в ауд. 513 с 9:00 или 25.01.17 в ауд. 607 с 10:00. Если эти даты Вам неудобны, напишите мне, и мы договоримся об альтернативном времени.

Вопросы к зачету/экзамену

Задачи к зачету/экзамену

О спецкурсе

Почему узнать, есть ли в графе эйлеров цикл, легко, а узнать, есть в графе гамильтонов цикл, трудно? Вообще, почему одни задачи легкие, а другие трудные? Можно ли априори, не приступая к решению задачи, оценить степень ее трудности? И главное, что делать, если жизненно необходимо решить задачу, хотя про нее точно известно, что она трудна?

Эти принципиальные для любого разработчика алгоритмов вопросы изучает направление фундаментальной информатики, традиционно (хотя и не совсем точно) именуемое «Computational Complexity», т.е. «Сложность вычислений». Возникнув относительно недавно, в начале 70-х годов прошлого века, это направление стремительно превратилось в главный центр роста современных компьютерных наук и оказало кардинальное идейное влияние на математику и ее индустриальные приложения. Спецкурс призван дать быстрое, но вполне строгое введение в основные идеи сложности вычислений. Формально говоря, для понимания материала спецкурса не требуется никаких предварительных знаний, но от слушателей ожидается определенный уровень математической зрелости.

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

  • Понятие о полиномиальных и экспоненциальных алгоритмах. Устойчивость полиномиальности относительно варьирования моделей вычислений и способов организации данных.
  • Общая задача распознавания. Классы 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.

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