Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Теоретический предел трудоемкости задачи.
Рассматривая некоторую алгоритмически разрешимую задачу, и анализируя один из алгоритмов ее решения, мы можем получить оценку трудоемкости этого алгоритма в худшем случае – fa()=O(g()). Такие же оценки мы можем получить и для других известных алгоритмов решения данной задачи. Рассматривая задачу с этой точки зрения, возникает резонный вопрос – а существует ли функциональный нижний предел для g() и если «да», то существует ли алгоритм, решающий задачу с такой трудоемкостью в худшем случае. Другая, более точная формулировка, имеет следующий вид: какова оценка сложности самого «быстрого» алгоритма решения данной задачи в худшем случае? Очевидно, что это оценка самой задачи, а не какого либо алгоритма ее решения. Таким образом, мы приходим к определению понятия функционального теоретического нижнего предела трудоемкости задачи в худшем случае: = min { ( (D)) } Если мы можем на основе теоретических рассуждений доказать существование и получить оценивающую функцию, то мы можем утверждать, что любой алгоритм, решающий данную задачу работает не быстрее, чем с оценкой в худшем случае: (D) = () Приведем ряд примеров: 1. Задача поиска максимума в массиве A=(a1,…,an) – для этой задачи, очевидно должны быть просмотрены все элементы, и = (n). 2. Задача умножения матриц - для этой задачи можно сделать предположение, что необходимо выполнить некоторые арифметические операции со всеми исходными данными, теоретическое обоснование какой–либо другой оценки на сегодня не известно, что приводит нас к оценке =Q (). Отметим, что лучший алгоритм умножения матриц имеет оценку Q (). Расхождение между теоретическим пределом и оценкой лучшего известного алгоритма позволяет предположить, что либо существует, но еще не найден более быстрый алгоритм умножения матриц, либо оценка Q () должна быть доказана, как теоретический предел. Сложностные классы задач.
В начале 1960-х годов, в связи с началом широкого использования вычислительной техники для решения практических задач, возник вопрос о границах практической применимости данного алгоритма решения задачи в смысле ограничений на ее размерность. Какие задачи могут быть решены на ЭВМ за реальное время? Ответ на этот вопрос был дан в работах Кобмена (Alan Cobham, 1964), и Эдмнодса (Jack Edmonds, 1965), где были введены сложностные классы задач.
1) Класс P (задачи с полиномиальной сложностью) Задача называется полиномиальной, т.е. относится к классу P, если существует константа k и алгоритм, решающий задачу с (n)=O(), где n - длина входа алгоритма в битах n = |D| [6]. Задачи класса P – это интуитивно, задачи, решаемые за реальное время. Отметим следующие преимущества алгоритмов из этого класса: o для большинства задач из класса P константа k меньше 6; o класс P инвариантен по модели вычислений (для широкого класса моделей); o класс P обладает свойством естественной замкнутости (сумма или произведение полиномов есть полином). Таким образом, задачи класса P есть уточнение определения «практически разрешимой» задачи. 2) Класс NP (полиномиально проверяемые задачи) Представим себе, что некоторый алгоритм получает решение некоторой задачи – соответствует ли полученный ответ поставленной задаче, и насколько быстро мы можем проверить его правильность? Рассмотрим, например задачу о сумме: Дано N чисел – А = (a1,…an) и число V. Задача: Найти вектор (массив) X=(x1,…,xn), xiє{0,1}, такой, что aixi = V. Содержательно: может ли быть представлено число V в виде суммы каких-либо элементов массива А. Если какой-то алгоритм выдает результат – массив X, то проверка правильности этого результата может быть выполнена с полиномиальной сложно-стью: проверка aixi = V требует не более Q (N) операций. Формально: Dє , |D|=n поставим в соответствие сертификат Sє , такой что |S|=O () и алгоритм = (D,S), такой, что он выдает «1», если решение правильно, и «0», если решение неверно. Тогда задача принадлежит классу NP, если F ()=O (). Содержательно задача относится к классу NP, если ее решение некоторым алгоритмом может быть быстро (полиномиально) проверено.
|
|||||
Последнее изменение этой страницы: 2016-04-19; просмотров: 350; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.129.45.92 (0.006 с.) |