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

Материал из eSyr's wiki.

Перейти к: навигация, поиск

[править] Лекция 1

Решить задачу оптимизации — не значит, что нужно решить конкретную задачу, типа «посчитать высоту Университета», это значит написать программу решения определённого класса задач.
Массовая задача — набор, класс индивидуальных задач (I), П = {I}. Индивидуальная задача получается из массовой путём конкретизации. То есть, у массовой задачи есть свободные параметры.
Алгоритм (А) — программа для машины Тьюринга.
П — задача распознавания свойств, если в качестве требования к решению является ответ «да» или «нет».
Алфавит Σ — множество, состоящее из конечного числа символов {|\sigma_i}|_{i=1}^k, k < \infin
Слово — конечный набор букв, слово будем обозначать &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}_+
Определение 3. Класс полиномиально разрешимых задач \mathbb{P} = {L(Π, e) | ∃ A решающий Π с кодировкой e, ∃p(.) — полином: T_{A(n)} \le p(n) \forall n \in \mathbb{Z}_+
Труднорешаемые задачи — задачи, для которых нет полиномиального алгоритма.


Методы оптимизации


01 02 03 04 05 06 07 08 09 10 11 12 13 14 15


Календарь

пт пт пт пт пт
Февраль
  08 15 22 29
Март
06 13 20 27
Апрель
04 11 18 25
Май
02   16 23

Материалы
Упражнения || Задачи | Определения | Утверждения | Теоремы || Теормин | Обозначения

Личные инструменты
Разделы