Раздел 1. Программирование,  объектно-ориентированное программирование.

В1. Оценка сложности алгоритмов. Классы P, NP. NP – полные задачи.

Основные определения:

Сложность алгоритма - Кол-во операций зав. от входных данных.

Аргумент ф-ии - размер входных данных.

Результат - кол-во элементарных операций.

Оценка сложности: функция характеризующая рост сложности с размером входных данных.

f(n)=O(g(n))

сущ-т C : f(n) <= C*g(n), для люб. n>N

это означает, что f(n) принадлежит классу функций, которые растут не быстрее, чем функция g(n) с точностью до постоянного множителя.

Класс P

Если сложность O(полином) - полиномиальная сложность (принадлежит классу P).

практически выполнимы, если более высокая (экспоненциальная, факториальная) трудно решаемая.

К ним относятся задачи, которые могут быть решены за время, полиномиально зависящее от объема исходных данных, с помощью детерминированной вычислительной машины (например, машины Тьюринга)

NP класс - выше чем полиномиальная.

Опредиление через недетрменированную машину тьюринга. класс NP - задачи, которые могут быть решены за полиномиально выраженное время с помощью недетерминированной вычислительной машины, то есть машины, следующее состояние которой не всегда однозначно определяется предыдущими. Работу такой машины можно представить как разветвляющийся на каждой неоднозначности процесс: задача считается решенной, если хотя бы одна ветвь процесса пришла к ответу.

Класс NP включает в себя класс P.
NP-полная задача — задача из класса NP, к которой можно свести любую другую задачу из класса NP за полиномиальное время. Таким образом, NP-полные задачи образуют в некотором смысле подмножество «самых сложных» задач в классе NP; и если для какой-то из них будет найден «быстрый» алгоритм решения, то и любая другая задача из класса NP может быть решена так же «быстро».
Полиномиальная сводимость

Задача A полиномиально сводится к алгоритму B если для зад A сущ-т полиномиальный алгоритм эл. операцию в котором можно заменить на алгоритм В.
Шпаргалка:
Оценка сложности

Пусть: A - алг-м реш-я некоторого класса зад. и n-размерность одной зад. из этого класса (в частном случае n может быть, например, длиной последовательности, количеством слов в анализируемом тексте и т.д.);

- функция fA(n) даст верхнюю границу для максимального числа основных операций, которые должен выполнить алгоритм A для решения любой задачи размерности n.

Тогда алгоритм называется полиномиальным, если fA(n) растет не быстрее чем полином от n.

Время, затраченное на реализацию алгоритма, как функция размерности задачи называется временной сложностью алгоритма и обозначается как O[fA(n)].

Сложность можно характеризовать числом операций N и общим объемом информации P, то есть общим количеством слов, используемых при выполнении алгоритма. Тогда, время его выполнения на конкретной ЭВМ связано с числом операций, а объем информации связан с объемом памяти, необходимой машине для реализации соответствующей программы. Следовательно, время реализации алгоритма есть функция T=f(N). При таком подходе значение T и P называют соответственно вычислительной емкостной сложностью алгоритма.

Анализ трудоёмкости алгоритмов

Цель - нах-е опт-ого алг-ма для решения данной зад. Критерий оптимальности - трудоемкость алгоритма. Функцией трудоемкости называется отношение, связывающие входные данные алгоритма с количеством элементарных операций.

Для некоторых алгоритмов трудоемкость зависит только от объема данных, для других алгоритмов — от значений данных, в некоторых случаях порядок поступления данных может влиять на трудоемкость. Трудоёмкость многих алгоритмов может в той или иной мере зависеть от всех перечисленных выше факторов.
Асимптотический анализ алгоритмов

Целью асимптотического анализа является сравнение затрат времени и других ресурсов различными алгоритмами, предназначенными для решения одной и той же задачи, при больших объемах входных данных. Используемая в асимптотическом анализе оценка функции трудоёмкости, называемая сложностью алгоритма, позволяет определить, как быстро растет трудоёмкость алгоритма с увеличением объема данных.

Задача распознавания – для индивидуальной задачи и заданной константы L найти ответ на вопрос существует ли решение стоимость которого не больше (не меньше) заданной границы L.
Для того чтобы задача содержалась в классе NP, мы не требуем, чтобы ответ в каждой индивидуальной задаче мог быть получен за полиномиальное время с помощью некоторого алгоритма. Мы требуем просто, чтобы в том случае, когда в индивидуальной задаче х ответ был да, существовало бы краткое (т. е. с длиной, ограниченной полиномом от размера х) удостоверение для х, справедливость которого можно было бы проверить за полиномиальное время.
Задача распознавания: для даной формулы определить может ли она быть истинной для какого-либо набора переменных.

Удостоверение: может служить набор значений истинности.

Док-во удостоверения: будет просто проверять, что формула истинная на данном наборе значений.

Дополнение задачи коммивояжера: определить что в данном графе нет обходов меньше L. Эта задача не относиться к классу NP, т.е. перебрать все существующие обходы и доказать, что они меньше L, нельзя за полиномиальное время.

Если задача распознавания относится к NP, то сама индивидуальная задача называется NP-трудной.

Задача называется NP-полной, если она принадлежит к классу NP и любая задача из NP полиномиально сводиться к ней.

Теорема Кука: задача о выполнимости является NP полной.

Еще ряд задач из NP(Клика и ЗК) являются NP- полными, для доказательства этого рассматриваемую задачу преобразуют в задачу ВЫПОЛНИМОСТЬ или какую-нибудь другую задачу, NP-полнота которой уже доказана.

Примеры NP-полных задач

Задача о выполнимости булевых формул

Кратчайшее решение «пятнашек» размера

Задача коммивояжёра

Проблема Штейнера

Проблема раскраски графа

Задача о вершинном покрытии

Задача о покрытии множества

Задача о клике

Задача о независимом множестве

Сапер (игра)

Тетрис[2]