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

Материал из 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.us/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 семестр

Поиск

Инструменты

@@ Строка 48: / Строка 48: @@
 * '''NPC''' -- класс '''NP'''-полных задач (стр. 14)
 * '''PSPACE''' -- класс задач, требующих для решения не более чем полиномиальной памяти (стр. 19)
-{{Курс Методы оптимизации}}