Методы Оптимизации, Теормин

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

(Различия между версиями)
Перейти к: навигация, поиск
(→Задачи распознавания свойств. Классы P и NP.)
(→Теорема об экспоненциальной временной оценке для задач из класса NP.)
Строка 50: Строка 50:
== Теорема об экспоненциальной временной оценке для задач из класса NP. ==
== Теорема об экспоненциальной временной оценке для задач из класса NP. ==
-
Для любой П из NP существует ДМТ A, решающая ее с не более чем экспоненциальной временной сложностью: <math>T_{A}(n) <= 2{{p(n)}</math>.
+
Для любой П из NP существует ДМТ A, решающая ее с не более чем экспоненциальной временной сложностью: <math>T_{A}(n) <= 2^{p(n)</math>.

Версия 06:53, 7 июня 2009

Определения индивидуальной и массовой задачи, кодировки задачи, алгоритма решения массовой задачи, временной сложности алгоритма.

Массовая задача П:

  • список свободных параметров;
  • формулировка свойств, которым должно удовлетворять решение задачи.

P есть множество индивидуальных задач I \in P. Индивидуальная задача получается, всем всем параметрам присвоить конкретные значения.

Пусть E - конечный алфавит, а E* - множество слов в этом алфавите. Отображение e: P \rightarrow E* называется кодировкой задачи П.

Алгоритм А решает массовую задачу П, если для любой I \in P : А применим к I, то есть останавливается за конечное число шагов .

Кодировка задачи P: Отобраение e: P \rightarrow E* , обладающее следующими свойствами:

  • Возможность однозначно декодировать, то есть у двух различных ИЗ не может быть одинаковых кодировок.
  • e,e − 1 -- полиномиально вычислимы
  • Кодировка не избыточна, то есть для любой другой кодировки e1, удовлетворяющей 1 и 2 условиям справедливо:

\exists p(.): \forall I 'in P |e(I)| < p(e_{1}(I))

Язык массовой задачи -- это множество правильных слов, то есть слов, соответствующих ИЗ, имеющим положительный ответ(подразумевается задача распознавания): L(P, e) = e(Y(P)) = {s \in E*| s = e(I), I \in Y(I)}

Язык алгоритма -- множество слов, принимаемых А

Алгоритм A решает массовую задачу П, с кодировкой e, если L(e,P) = L(A)

tA(s) - число шагов алгоритма А для входаs \in E* (число шагов).

Временная сложность T_{A}(n) = max \{t_{A}(s)\}, s \in E*, |s| < n .

Задачи распознавания свойств. Классы P и NP.

Задача расползавания свойств: Это задачи ответ на которые должен быть -- "да", "нет"

Из ИЗ выделим такие задачи, которые дают ответ -- "да". Обозначим множество таких задач -- Y

Пусть D -- всевозможное значенте параметров задачи.

Формально ЗРС определяются следующей парой: [D(П), Y(П)]

Класс полиномиально разрешимых задач

Это такие задачи, временной сложность алгоритма решения которых ограниченна полиномом.

Например, к таким задачам отосится задача распознавания четности числа.

Теорема об экспоненциальной временной оценке для задач из класса NP.

Для любой П из NP существует ДМТ A, решающая ее с не более чем экспоненциальной временной сложностью: Невозможно разобрать выражение (неизвестная ошибка): T_{A}(n) <= 2^{p(n) .

Получено с http://esyr.org/wiki/%D0%9C%D0%B5%D1%82%D0%BE%D0%B4%D1%8B_%D0%9E%D0%BF%D1%82%D0%B8%D0%BC%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D0%B8%2C_%D0%A2%D0%B5%D0%BE%D1%80%D0%BC%D0%B8%D0%BD
Разделы