Лекции по дискретной математике. Глава 1 - файл n1.doc

Лекции по дискретной математике. Глава 1
скачать (109 kb.)
Доступные файлы (1):
n1.doc109kb.01.06.2012 12:06скачать

n1.doc

Глава 1

Оценка сложности алгоритма

    1. Алгоритм



Не существует четкого, исчерпывающего, общепринятого определения алгоритма.

Некоторые определения классиков математики:

«Алгоритм – это всякая система вычислений, выполняемая по строго определенным правилам, которая после какого-то числа шагов заведомо приведет к решению поставленной задачи» (А.Колмогоров).

«Алгоритм – это точное предписание, определяющее вычислительный процесс, идущий от варьируемых исходных данных к искомому результату» (А.Марков).




Слово «алгоритм» произошло от имени великого арабского математика Мухаммад ибн Муса ал-Хорезми (ал-Хорезми означает «хорезмиец»). Он жил приблизительно с 783 по 830 гг. н.э.

В латинских названиях составленные в 12 веке изложениях трудов ал-Хорезми его имя записывалось как alchorismi или algorizmi, а относящийся к тому же веку латинский перевод начинался словами «Dixit algorizmi», т.е. «Сказал ал-Хорезми». Отсюда и пошло слово «алгоритм» - сначала для обозначения десятичной позиционной арифметики и алгоритмов вычисления в этой арифметике, а затем для обозначения произвольных алгоритмов.

1

Определения

.1. Теория сложности



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

Эта стоимость обычно измеряется в терминах абстрактных параметров, таких, как время и пространство.

Время представляет количество шагов, необходимое для решения проблемы, а пространство - объем памяти, необходимый для решения проблемы. Часто время и пространство неразрывно связаны в оценке стоимости вычислений.

Могут рассматриваться также другие ресурсы (например, число применяемых параллельных процессоров).
    1. Проблема решения



В теории вычислений проблема решения является вопросом в некоторой формальной системе с ответом «да или нет». Проблемы с более сложными ответами называются функциональными проблемами.

Необходимо отделять проблему решения от методов, используемых для решения этой проблемы. Последние называются процедурами решения или алгоритмами.
Проблемой решения будет проблема: «заданы два числа x и y, делится ли нацело число x на y?». Это типичный «да или нет» вопрос, и ответ на него зависит от значений x и y. Алгоритм для этой проблемы решения задает как для заданных x и y определить, что x делится на x нацело.



В теории сложности проблемы решения разбиваются на категории (классы) в зависимости насколько «трудными» они являются.

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

1.3. Обозначение «большое О»




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

Формальное определение «большого О»:

Пусть функции f и h будут функциями преобразования положительных целых чисел в неотрицательные действительные числа. Говорят, что h(n) является O(f(n)), если существует положительная константа B, такая, что

h(n) ? Bf(n)

для всех достаточно больших n.

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

Замечание



Ф

Пример

раза « s является истинными при достаточно больших n» означает, что имеется некоторое целое N такое, что s(n) является истинным всякий раз, когда n ? N. Например, говоря, что что-то является O(f(n)), то этим дается оценка верхней границы этого при достаточно больших значениях n.




Заданы полиномы:

f(x)=6x4 –2x3 + 5

h(x)=x4.

f(x) имеет порядок O(h(x)) или O(x4).

Доказательство следует из определения h(n) ? Bf(n) для всех x>1:

|6x4 –2x3 + 5| 6x4 + 2x3 +5, где x>1,

|6x4 –2x3 + 5| 6x4 + 2x4 +5x4, потому что x34 и т.д.,

|6x4 –2x3 + 5| 13x4 ,

|6x4 –2x3 + 5| 13|x|4, в этом примере B=13.

1.3.1. Специальные названия


При оценке асимптотической временной сложности алгоритмов за некоторыми обозначениями О закреплены следующие названия:


Специалисты в области вычислений считают алгоритм приемлемым для практики, если его сложность оценивается не выше полиномиального времени.

Замечание




Кроме «большого О», используемого наиболее часто, имеются другие записи асимптотического поведения функций (например, o, ?, ?, ?):


Запись

Определение

Математическое определение

f(n)O(h(n))

асимптотическая верхняя граница

||<

f(n)о(h(n))

асимптотически пренебрежительно малый

||=0

f(n)?(h(n))

асимптотическая нижняя граница

||>0

f(n)?(h(n))

асимптотически доминирующий

||=

f(n)?(h(n))

асимптотически сжатая граница

0<||<

1.4.1. Классы сложности


Определения



Проблемы решения разбиваются на классы сложности, каждый из которых имеет свои ограничения на время и пространство решения проблемы.

В теории вычислимости выделяют большое число классов сложности (P,NP,NP-тяжелая, Co-NP и т.д.). Ниже приводятся определения лишь нескольких классов сложности.

Класс сложности P - проблема может быть решена за полиномиальное время на обычном компьютере.

NP класс (NP - недетерминистское полиномиальное время):

NP-тяжелой класс:

NP-полный класс:



Замечания



Широко распространено мнение, что NP и NP-тяжелые проблемы решаются за время, большее, чем полиномиальное время, однако строго это не было доказано.

Традиционная «атака» на NP-тяжелые проблемы состоит в следующем:

1.5. Проблемы оптимизации


Определения






Если в проблеме задается вопрос имеется ли решение, то проблема оптимизации спрашивает: а что будет лучшим решением?

Каждое решение имеет положительную стоимость (или качество). В зависимости от формулировки проблемы оптимальное решение может иметь:

В связи с трудностями решения проблем оптимизации широко используют аппроксимационные алгоритмы.

Говорят, что алгоритм имеет аппроксимационное отношение (n), если для любого размера входа n стоимость С решений отвечает отношению:

max (C*/C, C/C*)  (n),

где С* - оптимальное решение;

C*/C – алгоритм решает проблему максимизации;

C/C* - алгоритм решает проблему минимизации.

Алгоритм с гарантированным аппроксимационным отношением (n) называется (n)-аппроксимационным алгоритмом.

1-аппроксимационный алгоритм является оптимальным, а чем больше (n), тем хуже решение.

Можно выделить несколько случаев:

- -


Глава 1 Оценка сложности алгоритма
Учебный материал
© nashaucheba.ru
При копировании укажите ссылку.
обратиться к администрации