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

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

(Различия между версиями)
Перейти к: навигация, поиск
(Определения индивидуальной и массовой задачи, кодировки задачи, алгоритма решения массовой задачи, временной сложности алгоритма.)
(Определения индивидуальной и массовой задачи, кодировки задачи, алгоритма решения массовой задачи, временной сложности алгоритма.)
Строка 1: Строка 1:
-
== Определения индивидуальной и массовой задачи, кодировки задачи, алгоритма решения массовой задачи, временной сложности алгоритма. ==
+
== Введение в теорию сложности ==
-
 
+
=== Индивидуальная и массовая задачи, кодировка задачи, алгоритм решения массовой задачи, временная сложность алгоритма. ===
-
'''Массовая задача П''':
+
 +
'''Массовая задача <math>\Pi</math>''':
* список свободных параметров;
* список свободных параметров;
* формулировка свойств, которым должно удовлетворять решение задачи.
* формулировка свойств, которым должно удовлетворять решение задачи.
-
P есть множество индивидуальных задач <math>I \in P</math>. Индивидуальная задача получается, если всем параметрам присвоить конкретные значения.
+
<math>\Pi</math> есть множество индивидуальных задач <math>I \in \Pi</math>. '''Индивидуальная задача''' получается, если всем параметрам присвоить конкретные значения.
Пусть E - конечный алфавит, а E* - множество слов в этом алфавите. Отображение e: <math>P \rightarrow E*</math> называется кодировкой задачи П.
Пусть E - конечный алфавит, а E* - множество слов в этом алфавите. Отображение e: <math>P \rightarrow E*</math> называется кодировкой задачи П.
-
'''Алгоритм А решает массовую задачу''' П, если для любой <math>I \in P</math> : А применим к I, то есть останавливается за конечное число шагов .
+
'''Алгоритм <math>A</math> решает массовую задачу''' <math>\Pi</math>, если для любой индивидуальной задачи <math>I \in \Pi</math> :
 +
* <math>A</math> применим к <math>I</math>, то есть останавливается за конечное число шагов
 +
* <math>A</math> дает решение <math>I</math>
-
'''Кодировка задачи P''':
+
'''Задача распознавания свойств''' -- массовая задача, предполагающая ответ "да" или "нет", в качестве своего решения.
-
Отобраение <math>e: P \rightarrow E* </math>, обладающее следующими свойствами:
+
* <math>D(\Pi)</math> -- множество всех возможных значений параметров массовой задачи.
 +
* <math>Y(\Pi)</math> -- множество всех индивидуальных задач, ответом на которые является "да".
 +
'''Кодировка задачи P''' -- такое отобраение <math>e: P \rightarrow \Sigma^* </math>, обладающее следующими свойствами:
* Возможность однозначно декодировать, то есть у двух различных ИЗ не может быть одинаковых кодировок.
* Возможность однозначно декодировать, то есть у двух различных ИЗ не может быть одинаковых кодировок.
* <math>e, e^{-1}</math> -- полиномиально вычислимы
* <math>e, e^{-1}</math> -- полиномиально вычислимы
* Кодировка не избыточна, то есть для любой другой кодировки <math>e_1</math>, удовлетворяющей 1 и 2 условиям справедливо:
* Кодировка не избыточна, то есть для любой другой кодировки <math>e_1</math>, удовлетворяющей 1 и 2 условиям справедливо:
-
<math>\exists p(.): \forall I 'in P |e(I)| < p(e_{1}(I))</math>
+
<math>\exists p(.): \forall I \in P |e(I)| < p(e_{1}(I))</math>
-
'''Язык массовой задачи''' -- это множество правильных слов, то есть слов, соответствующих ИЗ, имеющим положительный ответ(подразумевается задача распознавания):
+
'''Язык массовой задачи''' -- это множество правильных слов, то есть слов, соответствующих ИЗ, имеющим положительный ответ(подразумевается задача распознавания): <math>L(\Pi, e) = e(Y(\Pi)) = {s \in \Sigma^*| s = e(I), I \in Y(\Pi)}</math>
-
<math>L(P, e) = e(Y(P)) = {s \in E*| s = e(I), I \in Y(I)}</math>
+
'''Язык алгоритма''' -- множество слов, принимаемых А
'''Язык алгоритма''' -- множество слов, принимаемых А
-
Алгоритм A '''решает''' массовую задачу П, с кодировкой e, если <math>L(e, P) = L(A)</math>
+
Алгоритм <math>A</math> '''решает''' массовую задачу <math>\Pi</math>, с кодировкой <math>e</math>, если <math>L(e, \Pi) = L(A)</math>
<math>t{A}(s)</math> - число шагов алгоритма А для входа<math>s \in E*</math> (число шагов).
<math>t{A}(s)</math> - число шагов алгоритма А для входа<math>s \in E*</math> (число шагов).

Версия 14:12, 7 июня 2009

Содержание

Введение в теорию сложности

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

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

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

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

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

Алгоритм A решает массовую задачу Π, если для любой индивидуальной задачи I \in \Pi :

  • A применим к I, то есть останавливается за конечное число шагов
  • A дает решение I

Задача распознавания свойств -- массовая задача, предполагающая ответ "да" или "нет", в качестве своего решения.

  • D(Π) -- множество всех возможных значений параметров массовой задачи.
  • Y(Π) -- множество всех индивидуальных задач, ответом на которые является "да".

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

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

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

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

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

Алгоритм A решает массовую задачу Π, с кодировкой e, если L(e,Π) = 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, решающая ее с не более чем экспоненциальной временной сложностью: TA(n) < = 2p(n).

Класс co-NP. Пример задачи, допускающей хорошую характеризацию. Доказательство утверждения о взаимоотношении классов NPC и co-NP.

Задачи, допускающие хорошую характеристику -- это хадачи, входящие в класс: пересечение NP и co-Np

Пример такой задачи -- это задача определения простоты числа.

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