Методы оптимизации, определения
Материал из eSyr's wiki.
(Различия между версиями)
(Новая: == Лекция 1 == <div class="definition">'''Решить задачу оптимизации''' — ...) |
м (Spellcheck.) |
||
| Строка 1: | Строка 1: | ||
== [[Методы оптимизации, 01 лекция (от 08 февраля)|Лекция 1]] == | == [[Методы оптимизации, 01 лекция (от 08 февраля)|Лекция 1]] == | ||
| - | <div class="definition">'''Решить задачу оптимизации''' — не значит, что нужно решить конкретную задачу, типа «посчитать высоту | + | <div class="definition">'''Решить задачу оптимизации''' — не значит, что нужно решить конкретную задачу, типа «посчитать высоту Университета», это значит написать программу решения определённого класса задач.</div> |
<div class="definition">'''Массовая задача''' — набор, класс индивидуальных задач (I), П = {I}. Индивидуальная задача получается из массовой путём конкретизации. То есть, у массовой задачи есть свободные параметры.</div> | <div class="definition">'''Массовая задача''' — набор, класс индивидуальных задач (I), П = {I}. Индивидуальная задача получается из массовой путём конкретизации. То есть, у массовой задачи есть свободные параметры.</div> | ||
Текущая версия
[править] Лекция 1
Решить задачу оптимизации — не значит, что нужно решить конкретную задачу, типа «посчитать высоту Университета», это значит написать программу решения определённого класса задач.
Массовая задача — набор, класс индивидуальных задач (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 решения задчи П — функция TA(.): TA = 
Определение 3. Класс полиномиально разрешимых задач 
= {L(Π, e) | ∃ A решающий Π с кодировкой e, ∃p(.) — полином: 
= {L(Π, e) | ∃ A решающий Π с кодировкой e, ∃p(.) — полином: Труднорешаемые задачи — задачи, для которых нет полиномиального алгоритма.
