Лекция 14 (15)


Скачать 120.93 Kb.
НазваниеЛекция 14 (15)
Дата07.11.2012
Размер120.93 Kb.
ТипЛекция
Лекция 14 (15).


Размер задач и сложность алгоритмов. Временная и пространственная сложность. Полиномиальные и экспоненциальные алгоритмы. Трудноразрешимые задачи. Недетерминированные машины и NP-полные задачи. Сложность машин Тьюринга.


Размер задач и сложность алгоритмов.

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


Временная и пространственная сложность.

Временной сложностью алгоритма T(x) называется число его шагов, необходимых для решения данной задачи размера x в худшем случае (сложность в худшем).

Пространственная сложность S(x) - это число единиц памяти, необходимых для решения задачи размера n в худшем случае.


Введем понятие верхнего и нижнего порядка функции относительно другой функции. Рассмотрим арифметические функции. Идет счет на шаги вычислительного процесса и единицы времени и пространства.


Определение Назовем арифметическую функцию f(x) функцией одного верхнего порядка с функцией g(x) и пишем f(x) = O(g(x)), если существует такое натуральное число c > 0, что, в конце концов (т. е. начиная с некоторого N) функция ||f(x)|| c |g(x)|. Функция сложности заведомо неотрицательная. Значит f(x)  cg(x).

Пример: ln n = O(n); при n > 0 ln n < n.

Можно записать 2n + 3 = O(n2).

Решим уравнение, т. е. неравенство 2n + 3  n2 .

Решим подбором:



n

2n+3

n2

0

3

0

1

5

1

2

7

4

3

9

9


Таким образом, n2 обгонит любую линейную функцию.


Определение Назовем арифметическую функцию f(x) функцией одного нижнего порядка с функцией g(x) и пишем f(x) = (g(x)), если существует такое c > 0, что |f(x)|  c|g(x)|, f(x)  cg(x).

Например: ex = (x + 2).

ex - рано или поздно станет больше любого полинома. При малых размерах экспоненциальный алгоритм лучше полиномиального алгоритма; f(x) = o(g(x)).


Определение: f(x) одного порядка с функцией g(x), если она одного верхнего и одного нижнего порядка с функцией g(x), если она одного верхнего и одного нижнего порядка: = f(x) = o(g(x)) & f(x) = (g(x)).

Пример: x 10x + 2.


Определение. Функция одного верхнего порядка с полиномиальными функциями называется полиномиальной функцией. Это не только все полиномы, но и некоторые трансцендентные функции. Все остальные функции есть экспоненциальные в широком смысле этого слова. Но в строгом смысле слова экспоненциальными называются функции одного нижнего порядка с экспонентой. Тогда функции между экспоненциальными и полиномиальными называются субэкспоненциальными функциями. Обычно их не рассматривают! Экспоненциальные функции выделяются по скорости еще на несколько классов.


Определение. Арифметические функции f(x) и g(x) называются полиномиально-связанными или полиномиально-эквивалентнтными, если существуют такие многочлены P1(x) и P2(x), что, в конце концов (начиная с некоторого числа) f(x)P1g(x) и g(x)P2f(x).

Пример: f(x)=2x+3 p1(x)=2x+3 p2(x)=x3 g(x)=x3 2x+32x3+3 x3(2x+3)3 => f(x) и g(x) полиномиально связаны или эквивалентны.


Ясно, что полиномиальная эквивалентность сохраняет тип алгоритма! Т. е. при полиномиальном преобразовании функции сложности полиномиальный алгоритм переходит в полиномиальный, а экспоненциальный - в экспоненциальный.

Это дает возможность подвергать машины полиномиальным преобразованиям. Практически, сложность алгоритма должна рассчитываться применительно для данной реальной машины, через длительность ее операций и емкость ее ячеек памяти. Однако, типы можно определять на более удобных моделях машин (на машинах Тьюринга или идеальных вычислительных машинах, например). Теория сложности алгоритмов дает возможность определить типы алгоритмов и задач, независимо от конкретных машин.


Полиномиальные и экспоненциальные алгоритмы.

В конечном счете, функции пространственной и временной сложности должны определятся для конкретных машин (в операциях). Но теория сложности алгоритмов определяет общие типы алгоритмов по сложности:

1) полиномиальные алгоритмы;

2) экспоненциальные алгоритмы.

Алгоритм, обе функции сложности которого полиномиальные, называется полиномиальным алгоритмом. Такой алгоритм считается хорошим, быстрым (практика).

Алгоритм, у которого хотя бы одна из двух функций сложности экспоненциальная называется экспоненциальным алгоритмом. Такой алгоритм считается плохим, медленным. (При больших размерах задач, т. к. при малых может оказаться наоборот!).


Трудноразрешимые задачи.

Задача, решаемая полиномиальным алгоритмом, называется легкоразрешимой задачей. Задача, которую нельзя решить полиномиальным алгоритмом называется трудноразрешимой. В число трудных задач входят алгоритмически неразрешимые задачи. Неразрешимость есть крайний случай экспоненциальности.

Для наглядности рассмотрим таблицу возможностей алгоритмов.


Объем вычислений.


Тип алгоритма


Размер задачи


Полиномиальный



Экспоненциальный


малый



малый


малый


большой



большой


сверхбольшой


сверхбольшой



сверхбольшой


сверхбольшой

(выделенное жирным курсивом - не доступно!)


Вычисление сверхбольших чисел требует миллионов лет.


Недетерминированные машины и NP-полные задачи

Теория NP - полных задач - задачи с недетерминированным полиномиальным временем. Детерминированные машины Тьюринга заменяются недетерминированными, в которых одна конфигурация может иметь несколько ответов. Каждый ответ обрабатывается другой машиной. Или машина сама выбирает наилучший ответ. Вводится операция выбора. Такая машина возможна, но требует экспоненциального размножения конструкции. Существует класс NP – задач (недетерминированные задачи решаются за полиномиальное время). NP - задача, которую можно полиномиально преобразовать в любую данную NP задачу. Если можно решать полную NP задачу, то можно решить и все NP задачи. Класс NP охватывает многие задачи: минимизация, проверка булевых функций на общезначимость и выполнимость, поиск гамильтоновых линий в графе и т. д. Все они решаются на детерминированных задачах экспоненциально. Они трудны, но не доказано, что их нельзя упростить. Если хотя бы одну из них решим полиномиально, то все другие решим полиномиально. Общие подзадачи NP задач могут быть легкоразрешимыми.


Сложность машин Тьюринга.


Обычно не нужно точное определение функции сложности, а надо найти ее верхний или нижний порядок.

Для одноленточных машин Тьюринга временная сложность оценивается в тактах работы, а пространственная числом клеток, пройденных машиной в ходе работы. S(n)T(n) (пространственная  временная).

Для многоленточной машины Тьюринга временная сложность также определяется в тактах работы машины, но за один такт машина обрабатывает все свои ленты, поэтому S(n)=O(T(n)). Пространственная сложность имеет один верхний порядок с временной сложностью. Допустим, что машина имеет k лент, тогда такое условие проходит.


Теорема: многоленточная машина полиномиально преобразуется в одноленточную машину.

Док-во:

k-ленточную машину Tk преобразуем в одноленточную так: лента машины T делится на 2k дорожек. Лента T будет иметь следующий вид:




.....................................


Нечетные дорожки изображают ленты многоленточной машины. В нечетных дорожках изображается особой меткой положение машины Tk на соответствующей ленте; имеем 2k подклеток. Знак машины T состоит из 2k частичных знаков. Все, что записано в одной вертикальной колонке есть только один знак машины T. Теперь смоделируем такт машины Tk на T. Предположим, что в начале моделируемая машина T находится не более чем на две клетки влево от самой левой метки положения, но не правее ее. Машина T движется вправо, считая все метки положения и запоминая соответствующие знаки лент. Меток - конечное число, следовательно, через конечное время машина T дойдет до последней метки и восстановит конфигурацию машины Tk. T через конечное время узнает конфигурацию машины Tk. (За время T(n) - сложность машины Tk). На ленте машины T будет записано не более, чем kT(n) символов. Конфигурация будет определятся за O(T(n)) тактов. Машина T моделирует ответ, она идет влево и обрабатывает каждую встреченную метку и соответствующим образом ее передвигает. В конце концов она дойдет до самой левой метки. В самом левом воспринимаемом поле может быть сразу несколько меток. Одни пойдут вправо, другие влево.

Тем самым мы вернемся в предполагаемое положение. Тактов столько же. O(T(n))+O(T(1))=O(T(n)), всего тактов: T(n)O(T(n))=O(T2(n)). Новая функция сложности полиномиально эквивалентна старой.


Сложность машины Тьюринга для вычисления функции f(n)=2n+3.


Вычисления производятся в так называемом «унарном коде». Натуральные числа представляются палочками: 0-одной палочкой ,1-двумя палочками; 2-тремя и т.д. Значение аргумента n записывается на машинной ленте n+1 палочками после начальной метки  ; значение функции f(n)=2n+3 записывается 2n+4 палочками через клетку от значения аргумента. Закончив запись значения функции, машина возвращается в начальную клетку и останавливается. Значения аргумента и функции остаются на ленте.

Машина работает так:

  1. Копирует каждую палочку в значении аргумента дважды, что дает 2n+2 палочек в значении функции .

  2. Прибавляет к ним еще две палочки и возвращается в начальную клетку.



Таблица машины:



Команды



Команды

1

A   R A

12

E Я Я L C

2

A 1 X R B

13

F 1 1 L F

3

B 1 T L C

14

F Я Я L F

4

B Я Я R D

15

F T T L F

5

C 1 1 L C

16

F  1 R E

6

C X X R E

17

F I T R E

7

C T 1 R B

18

F X 1 L F

8

D 1 1 R D

19

F   S F

9

D Я 1 L F

20

G 1 1 R G

10

E 1  R G

21

G T T R G

11

E T I R G

22

G Я Я R D


При построении машины объединялись внутренние состояния, которые допускали объединение, т.е. не участвовали в противоречащих конфигурациях.


Первый этап состоит из n+1 циклов. Палочка, копируемая в данном цикле, заменяется меткой . В следующем цикле эта метка передвигается вправо.

Первый цикл:

копирование

 А 1 1 1 Я,   В 1 1 Я,   1 В 1 Я,   1 1 В Я,   1 1 Я С,   1 1 Я 1 D,

  1 1 Я E 1 1

возвращение

  1 1 Е Я 1 1,   1 Е 1 Я 1 1,    1 1 Я 1 1,    1 1 Я 1 1 .


Второй цикл:

копирование

 1 А 1 1 Я 1 1,  1  В 1 Я 1 1,  1  1 В Я 1 1,  1  1 Я С 1 1,  1  1 Я 1 С,

 1  1 Я 1 1 С,  1  1 Я 1 1 1 D,  1  1 Я 1 1 Е 1 1;

возвращение

 1  1 Я 1 Е 1 1 1,  1  1 Я Е 1 1 1 1,  1  1 Е Я 1 1 1 1,  1  Е 1 Я 1 1 1 1,  1 Е  1 Я 1 1 1 1.


Третий цикл:

копирование

 1 1 А 1 Я 1 1 1 1,  1 1  В Я 1 1 1 1,  1 1  Я С 1 1 1 1,  1 1  Я 1 С 1 1 1,

 1 1  Я 1 1 С 1 1,  1 1  Я 1 1 1 С 1,  1 1  Я 1 1 1 1 С,  1 1  Я 1 1 1 1 1 D

 1 1  Я 1 1 1 1 Е 1 1;

возвращение

 1 1  Я 1 1 1 Е 1 1 1,  1 1  Я 1 1 Е 1 1 1 1,  1 1  Я 1 Е 1 1 1 1 1,

 1 1  Я Е 1 1 1 1 1 1,  1 1  Е Я 1 1 1 1 1 1,  1 1 Е  Я 1 1 1 1 1 1.


Второй этап:

Прибавление двух палочек

 1 1 1 А Я 1 1 1 1 1 1,  1 1 1 Я С 1 1 1 1 1 1,  1 1 1 Я 1 С 1 1 1 1 1,

 1 1 1 Я 1 1 С 1 1 1 1,  1 1 1 Я 1 1 1 С 1 1 1,  1 1 1 Я 1 1 1 1 С 1 1,

 1 1 1 Я 1 1 1 1 1 С 1,  1 1 1 Я 1 1 1 1 1 1 С,  1 1 1 Я 1 1 1 1 1 1 D,

 1 1 1 Я 1 1 1 1 1 1 Е 1 1 ;

Возвращение

 1 1 1 Я 1 1 1 1 1 Е 1 1 1,  1 1 1 Я 1 1 1 1 Е 1 1 1 1,  1 1 1 Я 1 1 1 Е 1 1 1 1 1,

 1 1 1 Я 1 1 Е 1 1 1 1 1 1,  1 1 1 Я 1 Е 1 1 1 1 1 1 1,  1 1 1 Я Е 1 1 1 1 1 1 1 1,

 1 1 1 Е Я 1 1 1 1 1 1 1 1,  1 1 Е 1 Я 1 1 1 1 1 1 1 1,  1 Е 1 1 Я 1 1 1 1 1 1 1 1,

 Е 1 1 1 Я 1 1 1 1 1 1 1 1, Е  1 1 1 Я 1 1 1 1 1 1 1 1.

Машина вернулась в начальную клетку и остановилась. Первый этап занял 1+11+13+15=40 тактов, второй 10+11=21 такт, вся работа 61 такт.

Точный расчет сложности

Размер задачи - значение аргумента n. Копирование i-n палочки занимает n+1-( i -1)+1+2i+1=n+i+4 единиц времени(тактов), возвращение к ней 2i-1+1+n+1-i=n+i+1, а весь i-n цикл 2n+2i+5. Следовательно, n+1 циклов выполняется за время

2n(n+1)+2i+5(n+1)=3n*n+10n+7,

а весь первый этап-за время 3n*n+10n+8.

Прибавление двух палочек на втором этапе требует 2+2(n+1)+2=2n+6 единиц времени, возвращение в начальную клетку

2(n+1)+1+n+1+1=3n+5.

Следовательно, второй этап выполняется за время 5n+11, а все решение задачи - за время 3n*n+15n+19.

В общем случае задача может иметь много входных слов данного размера. Временная сложность Т(n) машины есть наибольшее время её работы при входных словах размера n. В нашем случае существует только одно входное слово данного размера, поэтому T(n)=3n*n+15n+19.

Пространственная, сложность S(n) машины есть наибольший путь (наибольше число клеток), проходимой ею при входных словах размера n. Нетрудно видеть, что в нашем случае S(n)=1+n+1+1+2(n+1)+2=3n+7. При n=2 получим: Т(2)=61, S(2)=13, в согласии с разобранным примером.

Функции Т(n) и S(n) здесь суть многочлены (полиномы). Следовательно, машина имеет полиномиальную сложность и реализует хороший, быстрый алгоритм. Вычисление функции f(n)=2n+3 – легко разрешимая задача, с точки зрения объема вычислений.

Приближенный расчет сложности

i-ый цикл первого этапа требует O(n) единиц времени, а весь первый этап (n+1)O(n)+1=O(n*n). Второй этап требует О(n) единиц, откуда T(n)=O(n*n)+O(n)=O(n*n ). Ясно также, что S(n)=O(n). Функции T(n) и S(n) суть полиномиальные функции. Задача легко разрешима.

Добавить документ в свой блог или на сайт

Похожие:

Разместите кнопку на своём сайте:
cat.convdocs.org


База данных защищена авторским правом ©cat.convdocs.org 2012
обратиться к администрации
cat.convdocs.org
Главная страница