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

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

(Различия между версиями)
Перейти к: навигация, поиск
(→Сокращения)
 
(9 промежуточных версий не показаны.)
Строка 3: Строка 3:
== Сокращения ==
== Сокращения ==
 +
* ''' КМ (ЗК) ''' -- коммивояжёр (задача о коммивояжёре) (стр. 6)
 +
* ''' ПЧ ''' -- задача распознавания простоты числа (стр. 8)
 +
* ''' ДМТ ''' -- детерминированная машина Тьюринга (стр. 9)
 +
* ''' НДМТ ''' -- недетерминированная машина Тьюринга (стр. 9)
 +
* ''' ВЫП ''' -- проверить на выполнимость конечной КНФ (стр. 14)
 +
* ''' ЦЛН ''' -- задача о целочисленном решении сислемы линейных неравенств (стр. 15)
 +
* ''' БЛН ''' -- задача о булевом решении сислемы линейных неравенств (стр. 16)
 +
* ''' 3-ВЫП ''' -- проверить на выполнимость конечной КНФ от ровно трёх переменных (стр. 17)
 +
* ''' ЗР ''' -- задача о рюкзаке (стр. 19)
 +
* ''' ПППС ''' -- полностью полиномиальная приближенная схема (стр. 24)
* ''' ЛП ''' -- линейное программирование (стр. 25)
* ''' ЛП ''' -- линейное программирование (стр. 25)
* '''озЛП''' -- основная задача линейного программирования (стр. 25)
* '''озЛП''' -- основная задача линейного программирования (стр. 25)
* '''ЗМП''' -- задача математического программирования (стр. 39)
* '''ЗМП''' -- задача математического программирования (стр. 39)
 +
* '''МВГ''' -- метод ветвей и границ (стр. 54)
 +
* '''ЦЛП''' -- целочисленное линейное программирование (стр. 55)
 +
* '''БЛП''' -- булево линейное программирование (стр. ??)
 +
* '''ДП''' -- динамическое программирование (стр. 59)
 +
 +
== Математические обозначения ==
 +
 +
* <math>\Pi</math> -- массовая задача (стр. 4)
 +
* <math>I \in \Pi</math> -- индивидуальная задача (стр. 4)
 +
* <math>\Sigma</math> -- алфавит кодирования (стр. 7)
 +
* <math>e</math> -- кодировка задачи <math>\Pi</math> (стр. 7)
 +
* <math>L(\Pi, e)</math> -- язык задачи (стр. 7)
 +
* <math>T_A(n)</math> -- временная сложность алгоритма <math>A</math> (стр. 8)
 +
* <math>\overline{\Pi}</math> -- дополнительная задача к массовой задача <math>\Pi</math> (стр. 12)
 +
* <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)
 +
 +
 +
 +
== Классы сложности задач ==
 +
* '''P''' -- класс полиномиальных разрешимых задач (стр. 8)
 +
* '''NP''' -- класс недетерминированно полиномиальных разрешимых задач (стр. 9, 10)
 +
* '''co-P''' -- класс задач, дополнительных к полиномиально разрешимым задачам (стр. 12)
 +
* '''co-NP''' -- класс задач, дополнительных к недетерменированно полиномиально разрешимым задачам (стр. 12)
 +
* '''NC''' (Nick Сlass) -- класс задач, решаемых за время, ограниченное полиномом от '''логарифма''' длины входа и требующих полиномиальной памяти.(стр. 19)
 +
* '''NPC''' -- класс '''NP'''-полных задач (стр. 14)
 +
* '''PSPACE''' -- класс задач, требующих для решения не более чем полиномиальной памяти (стр. 19)
 +
{{Курс Методы оптимизации}}

Текущая версия

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

[править] Сокращения

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


Методы оптимизации

01 02 03 04 05 06 07 08 09 10 11 12 13 14 15

Календарь

пт пт пт пт пт
Февраль
   08 15 22 29
Март
06 13 20 27
Апрель
04 11 18 25
Май
02   16 23

Материалы
Упражнения || Задачи | Определения | Утверждения | Теоремы || Теормин | Обозначения

Получено с http://esyr.org/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
Личные инструменты
Разделы