Методы оптимизации, определения
Материал из eSyr's wiki.
[править] Лекция 1
Решить задачу оптимизации — не значит, что нужно решить конкретную задачу, типа «посчитать высоту Университета», это значит написать программу решения определённого класса задач.
Массовая задача — набор, класс индивидуальных задач (I), П = {I}. Индивидуальная задача получается из массовой путём конкретизации. То есть, у массовой задачи есть свободные параметры.
Алгоритм (А) — программа для машины Тьюринга.
П — задача распознавания свойств, если в качестве требования к решению является ответ «да» или «нет».
Алфавит Σ — множество, состоящее из конечного числа символов ![{|\sigma_i}|_{i=1}^k, k < \infin](/w/images/math/2/1/d/21db348930f10619268b01cf2ff44fba.png)
![{|\sigma_i}|_{i=1}^k, k < \infin](/w/images/math/2/1/d/21db348930f10619268b01cf2ff44fba.png)
Слово — конечный набор букв, слово будем обозначать &sigma = {σi, σj, σk, …}
Схема кодирования (кодировка) — e: П → Σ*, ∀I ⇒ e(I) = σ ∈ Σ* — отображение массовой задачи в множество слов, индивидуальная задача отображается в слово.
Язык — множество слов, соответствующих правильным решениям: L(Π, e) = у(Н) = {σ ∈ Σ* | Σ — алфавит e, σ = e(I), I ∈ Y}
Определение 1. A решает задачу П с кодировкой e, если язык алгоритма совпадает с задачей П в кодировке E: L(A) = L(Π, e), и для любого слова из их множества алгоритм останавливается: ∀ σ ∈ Σ* A(σ) останавливается
Определение 2. Временна'я сложность алгоритма A решения задчи П — функция TA(.): TA = ![max_{\sigma \isin \Sigma^*: |\sigma| \le n} t_A(\sigma), n \in \mathbb{Z}_+](/w/images/math/3/2/3/323d5d85f3bf9d96cdc0f144837f842b.png)
![max_{\sigma \isin \Sigma^*: |\sigma| \le n} t_A(\sigma), n \in \mathbb{Z}_+](/w/images/math/3/2/3/323d5d85f3bf9d96cdc0f144837f842b.png)
Определение 3. Класс полиномиально разрешимых задач
= {L(Π, e) | ∃ A решающий Π с кодировкой e, ∃p(.) — полином: ![T_{A(n)} \le p(n) \forall n \in \mathbb{Z}_+](/w/images/math/d/3/8/d38c412a2505077d84d7ae23fe43b186.png)
![\mathbb{P}](/w/images/math/6/2/3/623709596363008e89cf20b6caba4df7.png)
![T_{A(n)} \le p(n) \forall n \in \mathbb{Z}_+](/w/images/math/d/3/8/d38c412a2505077d84d7ae23fe43b186.png)
Труднорешаемые задачи — задачи, для которых нет полиномиального алгоритма.