Методы оптимизации - теормин (1125564)
Текст из файла
Методы оптимизациии. Теормин.1. Массовая задача.Формально массовая задача П определяется:1) общим списком всех параметров задачи (свободных параметров, значения которыхне заданы),2) формулировкой свойств, которым должен удовлетворять ответ (решение задачи).2. Индивидуальная задача.Индивидуальная задача I ∈ П получается из П, если всем параметрам присвоитьконкретные значения.3.
Алгоритм решения задачи.Будем говорить, что алгоритм А решает массовую задачу П, если для ∀I ∈ Палгоритм А применим к I (т. е. останавливается за конечное число шагов) и для ∀I ∈П алгоритм А дает решение задачи I.4. Полиномиальные алгоритмы решения массовой задачи.Алгоритмы, решающие произвольную I ∈ П за время, ограниченное полиномом от“размера” I. Полиномиальные задачи - задачи, для которых существуютполиномиальные алгоритмы решения.5.
Задачи распознавания свойств.Массовые задачи, предполагающие ответ “да” или “нет” в качестве решения.6. Кодировка задачи.Введем конечное множество - алфавит ∑ = { i}, а также множество ∑* слов надалфавитом ∑ - произвольных конечных последовательностей, составленных изсимволов алфавита, возможно повторяющихся, = i1 i2...
in, ij ∈ ∑ ∀ij. Число nназывается длиной слова и обозначается | |. Кодировкой задачи П назовемтакое отображение e: П → ∑*, ставящее в соответствие любой индивидуальнойзадаче I ∈ П ее код e(I) = ∈ ∑* (слово из алфавита ∑*), что1) Возможно однозначное декодирование: ∀I1 ≠ I2 e(I1) ≠ e(I2)2) e, e-1 полиномиально вычислимы: существует алгоритм, реализующий e, e-1 иполином p(), для которого ∀I ∈ П время определения e(I), e-1(e(I)) не превосходитp(|e(I)|)3) Кодировка неизбыточна: для любой другой кодировки e’, удовлетворяющейусловиям 1) и 2), найдется полином p’, такой что ∀I ∈ П |e(I)| < p’(|e’(I)|).7.
Временная сложность алгоритма.Алгоритм А решает массовую задачу П, если L(A) = L(П, e) и ∀∈ Σ∗ Аостанавливается. Обозначим tA(σ) – время работы над словом σ (число шагов).Временной сложностью алгоритма А решения массовой задачи П назовемфункциюT ( )=max∈ ∗ :| |( ) ∀ ∈8. Класс полиномиально разрешимых задач (P)P = {L(П, e) | ∃ , решающий П с кодировкой , ∃ () − полином: ( ) < ( )∀ ∈}Если для задачи П существует такая кодировка e, что (П, ) ∈ , то будем называтьП полиномиальной.9.
Недетерминированная машина Тьюринга (НДМТ)Определяется как набор обычных (детерминированных) машин Тьюринга A(S) салфавитом Σ, где S пробегает все множество слов из Σ*: = { ( )} ∈ ∗НДМТ останавливается, когда останавливается первая из ДМТ A(S), принимающаявходное слово. Соответствующее конечное состояние – qY.Язык НДМТ – множество слов, принимаемых хотя бы одной ДМТ.10.
НДМТ решает массовую задачу П с кодировкой еНДМТ решает массовую задачу П с кодировкой е, если L(П, e) = L(Â)∀σ ∈ L(П, ) ∃ ∈ Σ ∗ : ( ) останавливается в∀σ ∈ Σ ∗ \L(П, ) ∀ ∈ Σ ∗ A(S)не останавливается или останавливается в11. Время работы НДМТ Â над словом σМинимальное из времен работы ДМТ A(S) над словом σ с учетом времени прочтенияслова St̂ (σ) =min{ | ∈{|S| + t( )}( ) (σ)}12. Временная сложность НДМТ Â решения массовой задачи ПФункция T (n) =∈max:| |t̂ (σ)13.
Класс недерминированно полиномиальных задач (NP)NP = {L(П, )| ∃ − НДМТ, решающая П с кодировкой , ∃ ( ) − полином:T (n) < (n)∀n ∈ Z }14. Теорема об экспоненциальной оценке временной сложности NP∀П ∈∃ () − полином, ∃ ДМТ : решает П и ( ) < 2 ( ) ∀ ∈15.
Дополнительная массовая задачаДополнительная к П массовая задача П получается из П распознавания свойствзаменой альтернативного вопроса, определяющего ответ в задаче его отрицанием.D(П) = D(П); Y(П) = D(П)\Y(П)16. Классы co-P и co-NPco-P = {П | П ∈ P}co-NP = {П | П ∈ NP}Утверждение: co-P = P.17. Задача, имеющая хорошую характеризациюП имеет хорошую характеризацию, если П ∈ NP ∩ co − NP, П – распознаваниясвойств.18. Полиномиальная сводимостьП’ распознавания свойств с кодировкой e’ полиномиально сводится к П с кодировкойe, если ∀I′ ∈ П′ может быть сведена за полиномиальное от ее длины время кнекоторой I ∈ П с сохранением ответа.19.
УтвержденияЕсли П ∝ П и П ∝ П , то П ∝ ПЕсли П ∝ П и П ∈ P, то П ∈ PЕсли П′ ∝ П и П ∈ NP, то П′ ∈ NP20. NP-полная задачаМассовая задача П называется NP-полной (универсальной), еслиП ∈ NP и ∀П ∈ NP П′ ∝ ПКласс NP-полных задач – NPC (NP-complete).21. Задача о выполнимости (ВЫП)Выяснить выполнимость КНФ (существует ли набор входных данных, на которых КНФравна 1).22. Теорема КукаВЫП ∈ NPC23. УтвержденияЕсли P ∩ NPC ≠ ∅, то P = NPЕсли NPC ∩ (NP\P) ≠ ∅, то NPC ⊆ NP\P24. Критерий NP-полнотыМассовая задача П NP-полна тогда и только тогда, когда она принадлежит классу NP,и к ней полиномиально сводится какая-либо NP-полная задача.{П ∈ NPC} ⟺ {П ∈ NP и ∃П ∈ NPC: П ∝ П}25. Задача ЦЛНЗадача о существовании целочисленного решения системы линейных неравенств сцелыми коэффициентами. Принадлежит классу NPC.26. Задача БЛНЗадача о существовании булева решения системы линейных неравенств с целымикоэффициентами.
Принадлежит классу NPC.27. Задача 3-ВЫПЧастный случай ВЫП, когда функции от 3-х переменных.28. УтверждениеВЫП ∝ 3 − ВЫП29. УтверждениеЕсли для некоторой NP-полной задачи П дополнительная к ней принадлежит классуNP, то NP = co-NP.30. Класс NP-трудных задачКласс NP-трудных задач объемлет NPC. Он содержит:′1) П распознавания свойств, для которых доказано, что П ∝ П для П′ ∈ NPC, но недоказано, что П ∈ NP2) П оптимизации, для которых соответствующие П распознавания свойтсв NP-полны3) Остальные массовые задачи, к которым сводятся по Тьюринту какие-либо NPполные задачи.31.
NP-эквивалентные задачиП, для которых ∃П ∈ NPC: П′ ∝ П и ∃П ∈ NP: П ∝ П′′32. Класс PSPACEКласс задач, для решения которых существуют алгоритмы, требующие не более чемполиномиальной памяти.33. Псевдополиномиальный алгоритмОбозначим:num(I) – максимальное по модулю число (или 0), фигурирующее при заданиичисловых параметров индивидуальной задачи I|I| = |e(I)| – длину записи I.Алгоритм А решения массовой задачи П называется псевдополиномиальным, еслидля некоторого полинома p() выполненоe(I) < p(|I|, num(I)) ∀I ∈ П34.
Полиномиальное сужение массовой задачиМножество индивидуальных задач, числовые параметры которых не превосходятполинома от длины входа.35. Сильно NP-полная задачаМассовая задача П распознавания свойств называется сильно NP-полной, если ееполиномиальное сужение NP-полно.36. ТеоремаЕсли P ≠ NP, то ни для какой сильно NP-полной задачи не существуетпсевдополиномиального алгоритма.37. Задачи дискретной (комбинаторной) оптимизацииДля оптимизационной постановки задачи П решением каждой I ∈ П являетсяпроизвольная оптимизация Opt П (I) = max fП (I, z)∈ П( )SП – область допустимых значений дискретной (целочисленной) переменной z.fП (I, z): SП → Z – целевая функция задачи I.38. Приближенный алгоритм решенияАлгоритм А называется приближенным алгоритмом решения массовой задачи Поптимизации, если ∀I ∈ П он находит некоторую точку из допустимой областиzA(I) ∈ SП(I), принимаемую за приближенное решение.
Значение fП(I, zA(I)) называетсяприближенным значением оптимума и обозначается A(I).39. Утверждение о погрешностиЕсли P ≠ NP, то ни для какой константы C > 0 не существует полиномиальногоприближенного алгоритма А решения задачи о рюкзаке ЗР с оценкой|Opt ЗР (I) − A(I)| ≤ ∀I ∈ ЗР40. ε-приближенный алгоритмПриближенный алгоритм А решения массовой задачи П называется ε-приближеннымдля некоторого ε > 0, еслиП(||)( )|П ( )|<41. ТеоремаПусть для задачи П оптимизации1) Существует псевдополиномиальный алгоритм ее решения2) ∀I ∈ П |Opt П (I)| < p |I|, num(I) и num(I) < p (|I|, Opt П (I)) для некоторыхполиномов p1 и p23) σ = e(I), I ∈ П, параметры σS, задающие ограничения, и σf, задающие целевуюфункцию, не пересекающиеся и z ∈ SП(σ) функция цели fП(σ, z) линейно зависит отпараметров σf.
Тогда∃ () − полином: ∀ > 0 ∃ε-приближенный алгоритм Аε решения П с временнойсложностью T (|I|) < (|I|, 1⁄ε)42. Полностью полиномиальная приближенная схема (ПППС)Набор алгоритмов из теоремы в пункте 41.43. ТеоремаЕсли для П оптимизации соответствующая ей П распознавания свойств являетсясильно NP-полной, и ∃ ′ () − полином: |Opt П (I)| < ′ num(I) ∀I ∈ П, то, при условиичто P ≠ NP, для П не существует ПППС.44. УтверждениеЕсли P ≠ NP, то ни для какого ε > 0 не существует полиномиального ε-приближенногоалгоритма решения оптимизационной постановки задачи коммивояжера.45.
Основная задача линейного программирования (озЛП)Состоит в нахождении такого решения системы ЛН≤ , которое максимизируетцелевую функцию.46. Каноническая задача ЛПmax,< ,>47. Принцип граничных решенийЕсли задача max < , > имеет решение, то найдется такая подматрица AI∈:матрицы А, что любое решение системы уравнений AIx = bI реализует максимум в∈max:< ,>48. Симплекс-методМетод направленного перебора смежных вершин в направлении возрастанияцелевой функции.49. Функции алгебраической и битовой сложностиФункция алгебраической сложности: оценивает число арифметических операций взависимости от размерности, не учитывает длину кода элементов.Функция битовой сложности: оценивает число арифметических операций с битами(или конечными порциями – по размеру машинного регистра) цифровой записипараметров задачи в зависимости от длины входного слова.50.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
