Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

FAQ по курсу "Методы оптимизации"

ВМиК МГУ, 8-й семестр

Лектор: Новикова В.М. (ВЦ РАН)

Ответы: Андреев А.Н. (alex@guru.ru)

См. http://cmc.cs.msu.su/curr/

1. Определения индивидуальной и массовой задачи, кодировки задачи, алгоритма решения массовой задачи, временной сложности алгоритма.

Массовая задача П: (1) список свободных параметров; (2) формулировка свойств, которым должно удовлетворять решение задачи. П есть множество индивидуальных задач IП.

Пусть E - конечный алфавит, а E^* - множество слов в этом алфавите. Отображение e: ПE^* называется кодировкой задачи П.

Алгоритм А решает массовую задачу П, если для любой IП : AI удовлетворяет заданным условиям. t_A() - число шагов алгоритма А для входа E^*. Временная сложность T_A­(n) = max {t_A() для ||n}.

2. Задачи распознавания свойств. Классы P и NP.

Задача распознавания свойств - массовая задача П, предполагающая ответ "да" или "нет". Определяется парой [D(П),Y(П)], где D - множество всех наборов параметров, Y - множество наборов параметров с ответом "да".

НДМТ A - набор "параллельно работающих" ДМТ {A(S)}, где S - "подсказки", слова в алфавите E^*. НДМТ решает данную массовую задачу, если для любой индивидуальной задачи какая-нибудь из A(S) останавливается в состоянии q_Y.

Временная сложность решения индивидуальной задачи:

t_A() = min{|S|+t_A(S)() по всем S, для которых A(S) дает q_Y}.

P - класс полиномиально-разрешимых задач, т.е. таких массовых задач П, для которых существует алгоритм А: T_A(n)<p(n) (n - длина записи задачи в некоторой кодировке е).

NP - класс недетерминированно полиномиальных задач, т.е. задач, полиномиально-разрешимых на счетном числе процессоров.

Пример: КМNP.

3. Теорема об экспоненциальной временной оценке для задач из класса NP.

Теорема. Для любой ПNP существует ДМТ A, решающая ее с не более чем экспоненциальной временной сложностью: T_A(n) 2^p(n).

4. Определение полиномиальной сводимости. Класс NPC. Теорема Кука.

Пусть П и П₁ - массовые задачи распознавания свойств. П₁ полиномиально сводится к П (П₁П), если существует функция сводимости f : D(П₁)D(П), такая что f (Y(П₁)) = Y(П), и f реализуется некоторой ДМТ за полиномиальное время.

Утверждение (транзитивность ). Если П₁П₂ и П₂П₃, то П₁П₃.

Утверждение (замкнутость классов P и NP относительно ). Если П₁П, ПР, то П₁Р. Аналогично, если ПNР, то П₁NР.

Массовая задача П называется NP-полной (ПNРC), если П NР и любая другая задача П­₁ из класса NP полиномиально сводится к П. Универсальность задач из класса NPC состоит в том, что основные нерешенные вопросы для класса NP достаточно решить хотя бы для одной NP-полной задачи.

Задача о выполнимости (ВЫП): для заданной КНФ выяснить, существует ли набор, на котором она обращается в 1.

Теорема (Кук). Задача ВЫП является NP-полной.Таким образом, класс NPC является непустым.

5. Критерий NP-полноты. Доказательство NP-полноты задачи ЦЛН.

Стр. 15.

Теорема. ПNРC  (ПNР и существует П₁NРC, полиномиально сводящаяся к П).

ЦЛН - задача о существовании целочисленного решения системы линейных неравенств (с целочисленными коэффициентами).

Утверждение. ЦЛНNРC.

6. Доказательство NP-полноты задачи 3-ВЫП. NP-трудные задачи.

3-ВЫП - частный случай задачи о выпоонимости (ВЫП), когда в КНФ могут входить только дизьюнктивные функции трех переменных.

Утверждение. ВЫП  3-ВЫП. Следовательно, 3-ВЫПNРC.

Любую дизъюктивную функцию k переменных можно представить в виде коньюнкции дизъюктивных функций от 3 переменных.

NP-трудные задачи:

1) задачи П, для которых доказано, что к ним сводятся NP-полные задачи, но не показано, что ПNP.

2) задачи оптимизации, для которых соответствующие задачи распознавания свойств NP-полны.

3) остальные массовые задачи, к которым сводятся по Тьюрингу какие-либо NP-полные задачи.

Пример: задача о рюкзаке (ЗР).

7. Класс co-NP. Пример задачи, допускающей хорошую характеризацию. Доказательство утверждения о взаимоотношении классов NPC и co-NP.

Дополнительная задача доп(П) получается из задачи распознавания свойств П заменой вопроса на его отрицание.

Утверждение. co-P = { доп(П) | П P } = P.

co-NP = { доп(П) | П NP }.

Задача П имеет хорошую характеризацию если ПNPco-NP. Для этих задач есть основания надеяться построить полиномиальные алгоритмы. Пример: задача распознавания простоты числа ПЧco-NP, ПЧ NP.

8. Взаимоотношение классов P, NP и NPC; NP и co-NP. Класс PSPACE.

Утверждение. Если для некоторой ПNPС: доп(П) NP, то NP=co-NP.

В класс PSPACE включаются задачи, требующие не более чем полиномиальной памяти.

9. Псевдополиномиальные алгоритмы. Пример для задачи о рюкзаке.

Решение задачи о рюкзаке методом динамического программирования имеет временную сложность nK, где n - число предметов, а K - максимальный вес рюкзака. Алгоритм не является полиномиальным, так как для записи числа K требуется log₂K битов.

Обозначим через num(I) максимальное целое число, фигурирующее при задании параметров для индивидуальной задачи I, |I| - длина записи задачи в некоторой неизбыточной кодировке. Алгоритм А решения массовой задачи П называется псевдополиномиальным, если существует полином p(x,y) такой, что для любой индивидуальной задачи I выполнено t_A(I)<p(|I|,num(I)).

10. Сильная NP-полнота. Теорема о связи сильной NP-полноты задачи с существованием псевдополиномиального алгоритма ее решения.

Полиномиальное сужение массовой задачи П - множество П_р тех индивидуальных задач IП, числовые параметры в записи которых не превосходят полинома от длины входа.

Массовая задача П называется сильно NP-полной, если ее полиномиальное сужение П_р NP-полно.

Примеры сильно NP-полных задач: ВЫП, 3-ВЫП, ЦЛН, КМ.

Теорема. Если предположить, что P  NP, то ни для какой сильно NP-полной задачи не существует псевдополиномиального алгоритма ее решения.

11. Определение комбинаторной задачи оптимизации и приближенного алгоритма ее решения. Утверждение о разнице между приближенным и точным оптимумом для задачи о рюкзаке.

Стр. 22.

Для оптимизационной постановки массовой задачи П решением любой индивидуальной задачи I является произвольная реализация z^*(I) оптимума Opt(I)=max[f_П(I,z)]. zS(I) - область допустимых значений дискретной переменной z, f_П: S(I)Z. Алгоритм А называется приближенным алгоритмом решения массовой задачи П, если для любой индивидуальной задачи I он находит некоторую точку z_A(I)S(I), принимаемую за приближенное решение. Значение f_П в этой точке называется приближенным значением оптимума и обозначается A(I).

Утверждение. Если предположить, что P  NP, то ни для какой константы C>0 не существует полиномиального приближенного алгоритма А с гарантированной погрешностью не более С.

12. Определение -приближенного алгоритма и полностью полиномиальной приближенной схемы. Связь между существованием ПППС и псевдополиномиальностью.

Стр. 23.

Алгоритм А решения задачи оптимизации П называется -приближенным, если для любой индивидуальной задачи I, его относительная погрешность не превосходит .

Пусть вход состоит из двух непересекающихся частей =[_s,_f], задающих соответственно ограничения на S(I) и целевую функцию f.

Теорема. Пусть для задачи оптимизации П существует псевдополиномиальный алгоритм ее решения. Если 1) величины Opt(I) и num(I) полиномиально связаны друг с другом и с длиной входа |I|, и 2) функция цели f_П(,z) линейно зависит от параметров _f. Тогда для любого >0 существует -приближенный алгоритм A_ решения данной задачи с временной сложностью T_(|I|)<p(|I|,1/), где p - некоторый фиксированный полином. Набор алгоритмов {A_} называется полностью полиномиальной приближенной схемой (ПППС) решения задачи оптимизации П.

13. Теорема об отсутствии ПППС для задач оптимизации, соответствующих сильно NP-полным задачам распознавания.

Теорема. Предположим, что P  NP. Если для задачи оптимизации П соответствующая задача распознавания свойств является сильно NP-полной и |Opt(I)|<p'(num(I)) (p - полином), то для П не существует ПППС.

14. Определени озЛП. Принцип граничных решений. Алгебраическая и битовая сложность ЛП. Результаты о сложности для задач, близких к ЛП.

Общая задача ЛП: 1) Ax  b (ограничения), 2) opt = max {c(x) = <c,x>}

Утверждение (принцип граничных решений). Если озЛП имеет решение, то найдется такая подматрица A_I матрицы А, что любое решение системы уравнений A_Ix = b_I реализует максимум c(x).

Алгебраическая сложность - количество арифметических операций. Битовая сложность - количество операций с битами. Битовая сложность задач ЛП, ЛН полиномиальна. Задачи ЦЛН, БЛН являются NP-полными. Вопрос о существовании алгебраически-полиномиального алгоритма для ЛП остается открытым. Существует неполиномиальное обобщение ЛП - задача проверки истинности для Q₁x₁…Q_nx_n F(<a₁,x>  b₁, … , <a_m,x>  b_m).

Каноническая задача ЛП: Ax=b, x  0, opt = max <c,x>.

15. Теорема о границах решений задач ЛП с целыми коэффициентами.

Введем обозначение (D)=max |det D'| (по всем D' - квадратным подматрицам D).

Теорема. Если озЛП размерности (n,m) с целыми коэффициентами разрешима, то у нее существует рациональное решение x^* в шаре ||x||n^½([A|b]), а значением оптимума d^*=<c,x^*> является рациональное число t/s со знаменателем s, ограниченным величиной (A).

16. Теорема о мере несовместности систем линейных неравенств с целыми коэффициентами.

Точка x^ называется -приближенным решением CЛН (Ax  b), если

<a_i,x^>  b_i+.

Теорема. Если СЛН имеет ₁-приближенное решение для ₁=1/[(n+2)(A)], то эта система имеет и точное решение.

17. Следствия систем линейных неравенств. Афинная лемма Фаркаша.

Стр. 35.

Лемма Фаркаша (афинная). Линейное неравенство <c,x>  d является следствием разрешимой в вещественных переменных СЛН Ax  b  существует вектор , такой, что:

с = _ia_i , d  _ib_i , _i  0.

18. Лемма Фаркаша о неразрешимости.

Лемма. СЛН Ax  b неразрешима 

разрешима система _ia_i = 0, _ib_i  -1, _i  0.

19. Теорема двойственности ЛП.

Двойственной к озЛП называется следующая задача на минимум в канонической форме:

opt = min {_ib_i }, _ia_i = c, _i  0.

Теорема. Задача ЛП разрешима  разрешима двойственная к ней, причем значения оптимумов в этих задачах совпадают.

20. Сведение озЛП к однородной СЛАУ с ограничением x > 0.

21. Классификация задач математического программирования.

Общий вид задачи МП: min {f(x), xX}. Математическое программирование - задачи оптимизации в вещественных переменных.

Классификация:

1) X = Rⁿ ? безусловная / условная оптимизация.

2) задачи ЛП, выпуклого программирования, гладкие / негладкие.

3) локальная / глобальная оптимизация.

22. Необходимые условия локального минимума при ограничениях-неравенствах для дифференцируемых функций.

K(X,x) - контингентный конус к множеству X в точке x (множество допустимых направлений y: x+tyX для t[0;t_o(y)]). Для внутренних точек x' : K(X,x)=Rⁿ.

Функция f называется дифференцируемой по Адамару в точке x, если существует вектор f(x), такой что для любого y:

lim (f(x+ty')-f(x))/t = <f(x),y> при (t,y')(+0,y)

Теорема. Пусть функция f дифференцируема по Адамару, а x₀ - точка локального минимума, тогда для любого вектора y из K(X,x):

<f(x₀),y>  0.

То есть среди допустимых направлений не должно быть направлений убывания целевой функции.

Пусть ограничения на X задаются в виде неравенств: g_i(x)  0.

Теорема. Пусть функции f, g_i дифференцируемы по Адамару, а x₀ - точка локального минимума, и множество X регулярно в точке X. Тогда для любых неотрицательных _i  0: {f(x₀)+_jg_j(x₀)} = 0.

23. Понятие о регулярности ограничений-неравенств в задаче математического программирования.

Пусть множество Х задается ограничениями-неравенствами вида {g_i(x)0}. Пусть J(x) - множество индексов "активных ограничений", т.е. тех неравенств, которые выполнены как равенства: g_i(x)=0 для iJ(x). Для произвольной точки х из Х введем множество (конус)

G(x) = {yRⁿ | <g_j(x),y>  0}.

Множество X = {xRⁿ | g_i(x)0 } называется регулярным в точке x, если G(x)K(X,x).

24. Теорема о целочисленности решения задачи ЛП с целыми коэффициентами для вполне унимодулярных матриц ограничений.

Матрица называется вполне унимодулярной, если определитель любой ее квадратной подматрицы равен по модулю 1. Очевидно, что матрица может состоять только из чисел 0, 1. Этот узкий класс матриц соответствует достаточно широкому классу задач оптимизации на графах и сетях.

Утверждение. Если матрица ограничений разрешимой задачи ЛП с целыми коэффициентами вполне унимодулярна, то у нее существует целочисленное решение.

Характеристики

Тип файла документ

Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.

Будьте внимательны на мобильных устройствах, так как там используются упрощённый функционал даже в официальном приложении от Microsoft, поэтому для просмотра скачивайте PDF-версию. А если нужно редактировать файл, то используйте оригинальный файл.

Файлы такого типа обычно разбиты на страницы, а текст может быть форматированным (жирный, курсив, выбор шрифта, таблицы и т.п.), а также в него можно добавлять изображения. Формат идеально подходит для рефератов, докладов и РПЗ курсовых проектов, которые необходимо распечатать. Кстати перед печатью также сохраняйте файл в PDF, так как принтер может начудить со шрифтами.

Список файлов учебной работы