Редактирование: Методы оптимизации, обозначения

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

Внимание: Вы не представились системе. Ваш IP-адрес будет записан в историю изменений этой страницы.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.

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

== Сокращения ==

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

Пожалуйста, обратите внимание, что все ваши добавления могут быть отредактированы или удалены другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. eSyr's_wiki:Авторское право).
НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Описание изменений:

Отменить | Справка по редактированию (в новом окне)

Шаблоны, использованные на этой странице:

Шаблон:Курс Методы оптимизации

Получено с 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

Редактирование: Методы оптимизации, обозначения

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

Просмотры

Личные инструменты

Навигация

инструменты

Разделы

Спецкурсы

9 семестр

7 семестр

5 семестр

3 семестр

Поиск

Инструменты

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