Методы оптимизации, определения

Решить задачу оптимизации — не значит, что нужно решить конкретную задачу, типа «посчитать высоту Униыерситета», это значит написать программу решения определённого класса задач.

Массовая задача — набор, класс индивидуальных задач (I), П = {I}. Индивидуальная задача получается из массовой путём конкретизации. То есть, у массовой задачи есть свободные параметры.

Алгоритм (А) — программа для машины Тьюринга.

П — задача распознавания свойств, если в качестве требования к решению является ответ «да» или «нет».

Алфавит Σ — множество, состоящее из конечного числа символов

Слово — конечный набор букв, слово будем обозначать &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 решения задчи П — функция T_A(.): T_A =

Определение 3. Класс полиномиально разрешимых задач = {L(Π, e) | ∃ A решающий Π с кодировкой e, ∃p(.) — полином:

Труднорешаемые задачи — задачи, для которых нет полиномиального алгоритма.