Методы Оптимизации, Теормин
Материал из eSyr's wiki.
(→Определения индивидуальной и массовой задачи, кодировки задачи, алгоритма решения массовой задачи, временной сложности алгоритма.) |
(→Определения индивидуальной и массовой задачи, кодировки задачи, алгоритма решения массовой задачи, временной сложности алгоритма.) |
||
| Строка 1: | Строка 1: | ||
| - | == | + | == Введение в теорию сложности == |
| - | + | === Индивидуальная и массовая задачи, кодировка задачи, алгоритм решения массовой задачи, временная сложность алгоритма. === | |
| - | + | ||
| + | '''Массовая задача <math>\Pi</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>A</math> решает массовую задачу''' <math>\Pi</math>, если для любой индивидуальной задачи <math>I \in \Pi</math> : |
| + | * <math>A</math> применим к <math>I</math>, то есть останавливается за конечное число шагов | ||
| + | * <math>A</math> дает решение <math>I</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 | + | <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( | + | |
'''Язык алгоритма''' -- множество слов, принимаемых А | '''Язык алгоритма''' -- множество слов, принимаемых А | ||
| - | Алгоритм A '''решает''' массовую задачу | + | Алгоритм <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
Содержание |
Введение в теорию сложности
Индивидуальная и массовая задачи, кодировка задачи, алгоритм решения массовой задачи, временная сложность алгоритма.
Массовая задача Π:
- список свободных параметров;
- формулировка свойств, которым должно удовлетворять решение задачи.
Π есть множество индивидуальных задач 
. Индивидуальная задача получается, если всем параметрам присвоить конкретные значения.
Пусть E - конечный алфавит, а E* - множество слов в этом алфавите. Отображение e: 
называется кодировкой задачи П.
Алгоритм A решает массовую задачу Π, если для любой индивидуальной задачи :
- A применим к I, то есть останавливается за конечное число шагов
- A дает решение I
Задача распознавания свойств -- массовая задача, предполагающая ответ "да" или "нет", в качестве своего решения.
- D(Π) -- множество всех возможных значений параметров массовой задачи.
- Y(Π) -- множество всех индивидуальных задач, ответом на которые является "да".
Кодировка задачи P -- такое отобраение 
, обладающее следующими свойствами:
- Возможность однозначно декодировать, то есть у двух различных ИЗ не может быть одинаковых кодировок.
- e,e − 1 -- полиномиально вычислимы
- Кодировка не избыточна, то есть для любой другой кодировки e1, удовлетворяющей 1 и 2 условиям справедливо:
Язык массовой задачи -- это множество правильных слов, то есть слов, соответствующих ИЗ, имеющим положительный ответ(подразумевается задача распознавания): 
Язык алгоритма -- множество слов, принимаемых А
Алгоритм A решает массовую задачу Π, с кодировкой e, если L(e,Π) = L(A)
tA(s) - число шагов алгоритма А для входа
(число шагов).
Временная сложность 
.
Задачи распознавания свойств. Классы P и NP.
Задача расползавания свойств: Это задачи ответ на которые должен быть -- "да", "нет"
Из ИЗ выделим такие задачи, которые дают ответ -- "да". Обозначим множество таких задач -- Y
Пусть D -- всевозможное значенте параметров задачи.
Формально ЗРС определяются следующей парой: [D(П), Y(П)]
Класс полиномиально разрешимых задач
Это такие задачи, временной сложность алгоритма решения которых ограниченна полиномом.
Например, к таким задачам отосится задача распознавания четности числа.
Теорема об экспоненциальной временной оценке для задач из класса NP.
Для любой П из NP существует ДМТ A, решающая ее с не более чем экспоненциальной временной сложностью: TA(n) < = 2p(n).
Класс co-NP. Пример задачи, допускающей хорошую характеризацию. Доказательство утверждения о взаимоотношении классов NPC и co-NP.
Задачи, допускающие хорошую характеристику -- это хадачи, входящие в класс: пересечение NP и co-Np
Пример такой задачи -- это задача определения простоты числа.
