Методы оптимизации, обозначения

Материал из eSyr's wiki.

(Различия между версиями)
Перейти к: навигация, поиск
(→Классы сложности задач - +NC)
Строка 45: Строка 45:
* '''co-P''' -- класс задач, дополнительных к полиномиально разрешимым задачам (стр. 12)
* '''co-P''' -- класс задач, дополнительных к полиномиально разрешимым задачам (стр. 12)
* '''co-NP''' -- класс задач, дополнительных к недетерменированно полиномиально разрешимым задачам (стр. 12)
* '''co-NP''' -- класс задач, дополнительных к недетерменированно полиномиально разрешимым задачам (стр. 12)
 +
* '''NC''' (Nick Сlass) -- класс задач, решаемых за время, ограниченное полиномом от длины входа и требующих полиномиальной памяти.
* '''NPC''' -- класс '''NP'''-полных задач (стр. 14)
* '''NPC''' -- класс '''NP'''-полных задач (стр. 14)
* '''PSPACE''' -- класс задач, требующих для решения не более чем полиномиальной памяти (стр. 19)
* '''PSPACE''' -- класс задач, требующих для решения не более чем полиномиальной памяти (стр. 19)

Версия 18:46, 8 июня 2009

К каждому определению в скобочках указывается номер страницы в методичке, на которой впервые данное определение встречается

Сокращения

  • КМ (ЗК) -- коммивояжёр (задача о коммивояжёре) (стр. 6)
  • ПЧ -- задача распознавания простоты числа (стр. 8)
  • ДМТ -- детерминированная машина Тьюринга (стр. 9)
  • НДМТ -- недетерминированная машина Тьюринга (стр. 9)
  • ВЫП -- проверить на выполнимость конечной КНФ (стр. 14)
  • ЦЛН -- задача о целочисленном решении сислемы линейных неравенств (стр. 15)
  • БЛН -- задача о булевом решении сислемы линейных неравенств (стр. 16)
  • 3-ВЫП -- проверить на выполнимость конечной КНФ от ровно трёх переменных (стр. 17)
  • ЗР -- задача о рюкзаке (стр. 19)
  • ПППС -- полностью полиномиальная приближенная схема (стр. 24)
  • ЛП -- линейное программирование (стр. 25)
  • озЛП -- основная задача линейного программирования (стр. 25)
  • ЗМП -- задача математического программирования (стр. 39)
  • МВГ -- метод ветвей и границ (стр. 54)
  • ЦЛП -- целочисленное линейное программирование (стр. 55)
  • БЛП -- булево линейное программирование (стр. ??)
  • ДП -- динамическое программирование (стр. 59)

Математические обозначения

  • Π -- массовая задача (стр. 4)
  • I \in \Pi -- индивидуальная задача (стр. 4)
  • Σ -- алфавит кодирования (стр. 7)
  • e -- кодировка задачи Π (стр. 7)
  • L(Π,e) -- язык задачи (стр. 7)
  • TA(n) -- временная сложность алгоритма A (стр. 8)
  • \overline{\Pi} -- дополнительная задача к массовой задача Π (стр. 12)
  • \Pi' \propto \Pi --массовой задача Π' полиномиально сводится к задаче Π (стр. 13)
  • num(I) -- максимальное по модулю число, фигурирующее в условии в задачи или 0, если числовых параметров нет. (стр. 21)
  • p(\cdot); p(\cdot, \cdot) -- полином от одной, двух переменных (стр. ??)
  • Δ(D) = max | det(D1) | , где D1 -- квадратная подматрица D (стр. 28)
  • \left[A | b \right] -- матрица, составленная из матрицы A, и дописанного справа столбца b (стр. 28)
  • \langle x,y \rangle -- скалярное произведение векторов x,y : \langle x,y \rangle = x_1 y_1 + x_2 y_2 + \dots x_n y_n (стр. ??)
  • \varepsilon_1 -- минимальное приближение, при котором система линейных неравенств имеет решение (стр. 29)


Классы сложности задач

  • P -- класс полиномиальных разрешимых задач (стр. 8)
  • NP -- класс недетерминированно полиномиальных разрешимых задач (стр. 9, 10)
  • co-P -- класс задач, дополнительных к полиномиально разрешимым задачам (стр. 12)
  • co-NP -- класс задач, дополнительных к недетерменированно полиномиально разрешимым задачам (стр. 12)
  • NC (Nick Сlass) -- класс задач, решаемых за время, ограниченное полиномом от длины входа и требующих полиномиальной памяти.
  • NPC -- класс NP-полных задач (стр. 14)
  • PSPACE -- класс задач, требующих для решения не более чем полиномиальной памяти (стр. 19)
Получено с http://esyr.name/wiki/%D0%9C%D0%B5%D1%82%D0%BE%D0%B4%D1%8B_%D0%BE%D0%BF%D1%82%D0%B8%D0%BC%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D0%B8%2C_%D0%BE%D0%B1%D0%BE%D0%B7%D0%BD%D0%B0%D1%87%D0%B5%D0%BD%D0%B8%D1%8F
Личные инструменты
Разделы