Теория алгоритмов. Зюзысов В.М. - 61 стр.

UptoLike

ВУЗ: 

ТГУ | Томск

Составители: 

Рубрика: 

Основной вопрос теории сложности: насколько успешно или с какой стоимостью
может быть решена заданная проблема Q? Мы не имеем в виду никакого конкретного
алгоритма решения Q. Наша цель – рассмотреть все возможные алгоритмы решения Q и
попытаться сформулировать утверждение о вычислительной сложности, внутренне
присущей Q. В то время как всякий алгоритм
A для Q дает верхнюю оценку величины
сложности Q, нас интересует нижняя оценка. Знание нижней оценки представляет интерес
математически и, кроме того, руководит нами в поиске хороших алгоритмов, указывая,
какие попытки заведомо будут безуспешны.
Быстрыми являются линейные алгоритмы, которые обладают сложностью
порядка Ο(n), где n – размерность входных данных. К линейным
алгоритмам относится
школьный алгоритм нахождения суммы десятичных чисел, состоящих из n
1
и n
2
цифр.
Сложность этого алгоритма – Ο(n
1
+ n
2
). Есть алгоритмы, которые быстрее линейных,
например, алгоритм двоичного поиска в линейном упорядоченном массиве имеет
сложность Ο(log n), n – длина массива.
Другие хорошо известные алгоритмы – деление, извлечение квадратного корня,
решение систем линейных уравнений и др. – попадают в более общий класс
полиномиальных алгоритмов.
Полиномиальным алгоритмом (или алгоритмом полиномиальной временной
сложности, или алгоритмом
принадлежащим классу P) называется алгоритм, у которого
временная сложность равна Ο(n
k
), где k – положительное целое число. Алгоритмы, для
временной сложности которых не существует такой оценки, называются
экспоненциальными и такие задачи считаются труднорешаемыми. Понятие
полиномиально разрешимой задачи принято считать уточнением идеи «практически
разрешимой» задачи. Чем объясняется такое соглашение?
Во-первых, используемые на практике полиномиальные алгоритмы обычно
действительно работают довольно быстро. Конечно, трудно
назвать практически
разрешимой задачу, которая требует времени Θ(n
100
). Однако полиномы такой степени в
реальных задачах почти не встречаются.
Второй аргумент в пользу рассмотрения класса полиномиальных алгоритмов – тот
факт, что объем этого класса не зависит от выбора конкретной модели вычислений (для
достаточно широкого класса моделей) [13]. Например, класс задач, которые могут быть
решены за полиномиальное время на последовательной машине с
произвольным доступом
(RAM), совпадает с классом задач, полиномиально разрешимых на машинах Тьюринга.
Класс будет тем же и для моделей параллельных вычислений, если, конечно, число
процессоров ограничено полиномом от длины входа.
В-третьих, класс полиномиально разрешимых задач обладает естественными
свойствами замкнутости. Например, композиция двух полиномиальных алгоритмов
(выход первого алгоритма подается на вход
второго) также работает полиномиальное
время. Объясняется это тем, что сумма, произведение и композиция многочленов снова
есть многочлен.
Приведем примеры классификации задач по их сложности.
Класс P
Рассортировать множество из n чисел. Сложность поведения в среднем порядка
Ο(n log n) для быстрого алгоритма Хоара [22, стр.316–321].
•
•
•
Найти эйлеровый цикл на графе
из m ребер. В силу теоремы Эйлера мы имеем
необходимое и достаточное условие для существования эйлерова цикла и проверка
этого условия есть алгоритм порядка Ο(m).
Задача Прима-Краскала. Дана плоская страна и в ней n городов. Нужно соединить все
города телефонной связью так, чтобы общая длина телефонных линий была
минимальной. В терминах теории графов задача Прима-Краскала выглядит следующим
образом: Дан граф с n вершинами; длины ребер заданы матрицей (d[i,j]), i,j = 1,...,n.

Страницы