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

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

(Различия между версиями)
Перейти к: навигация, поиск
Строка 12: Строка 12:
* ''' 3-ВЫП ''' -- проверить на выполнимость конечной КНФ от ровно трёх переменных (стр. 17)
* ''' 3-ВЫП ''' -- проверить на выполнимость конечной КНФ от ровно трёх переменных (стр. 17)
* ''' ЗР ''' -- задача о рюкзаке (стр. 19)
* ''' ЗР ''' -- задача о рюкзаке (стр. 19)
 +
* ''' ПППС ''' -- полностью полиномиальная приближенная схема (стр. 24)
* ''' ЛП ''' -- линейное программирование (стр. 25)
* ''' ЛП ''' -- линейное программирование (стр. 25)
* '''озЛП''' -- основная задача линейного программирования (стр. 25)
* '''озЛП''' -- основная задача линейного программирования (стр. 25)
Строка 17: Строка 18:
* '''ЦЛП''' -- целочисленное линейное программирование (стр. 55)
* '''ЦЛП''' -- целочисленное линейное программирование (стр. 55)
* '''БЛП''' -- булево линейное программирование (стр. ??)
* '''БЛП''' -- булево линейное программирование (стр. ??)
 +
* '''ЗМП''' -- задачи математического программирования (стр. 39)
== Математические обозначения ==
== Математические обозначения ==
Строка 28: Строка 30:
* <math>\overline{\Pi}</math> -- дополнительная задача к массовой задача <math>\Pi</math> (стр. 12)
* <math>\overline{\Pi}</math> -- дополнительная задача к массовой задача <math>\Pi</math> (стр. 12)
* <math>\Pi' \propto \Pi</math> --массовой задача <math>\Pi'</math> полиномиально сводится к задаче <math>\Pi</math> (стр. 13)
* <math>\Pi' \propto \Pi</math> --массовой задача <math>\Pi'</math> полиномиально сводится к задаче <math>\Pi</math> (стр. 13)
 +
* <math>\mathrm{num}(I)</math> -- максимальное по модулю число, фигурирующее в условии в задачи или 0, если числовых параметров нет. (стр. 21)
 +
* <math>p(\cdot); p(\cdot, \cdot)</math> -- полином от одной, двух переменных (стр. ??)
 +
* <math>\Delta(D) = \max | \det(D_1) | </math>, где <math>D_1</math> -- квадратная подматрица <math>D</math> (стр. 28)
 +
* <math>\left[A | b \right]</math> -- матрица, составленная из матрицы <math>A</math>, и дописанного справа столбца <math>b</math> (стр. 28)
 +
* <math>\langle x,y \rangle</math> -- скалярное произведение векторов <math>x,y</math> : <math>\langle x,y \rangle = x_1 y_1 + x_2 y_2 + \dots x_n y_n</math> (стр. ??)
 +
* <math>\varepsilon_1</math> -- минимальное приближение, при котором система линейных неравенств имеет решение (стр. 29)
 +

Версия 17:26, 8 июня 2009

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

Сокращения

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

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

  • Π -- массовая задача (стр. 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)
  • NPC -- класс NP-полных задач (стр. 14)
  • PSPACE -- класс задач, требующих для решения не более чем полиномиальной памяти (стр. 19)
Личные инструменты
Разделы