Тема 5. Алгоритмы

5.1. Определение алгоритма

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

1. Сортировка массива чисел в порядке возрастания.

2. Вычисление таблицы значений булевой функции, заданной формулой.

3. Вычисление чисел Фибоначчи по рекуррентному соотношению.

4. Решение системы линейных алгебраических уравнений методом исключения Гаусса.

Основные требования к алгоритмам

1. Алгоритм применяется к исходным данным и дает результаты. Кроме того, в процессе работы алгоритма могут появляться промежуточные данные. Итак, каждый алгоритм имеет дело с данными: исходными, промежуточными и выходными. Данными могут быть числа, векторы, матрицы, массивы, формулы, рисунки (в графических системах).

2. Данные для своего размещения требуют памяти. Память состоит из ячеек, так что каждая ячейка может содержать один символ алфавита данных. Таким образом, объем данных и требуемая память согласованы.

3. Алгоритм состоит из отдельных элементарных шагов или действий. Причем множество различных шагов, из которых составлен алгоритм, конечно. Типичный пример множества элементарных действий – система команд ЭВМ.

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

5. Алгоритм должен удовлетворять требованию результативности, т. е. остановки после конечного числа шагов. В таком случае говорят, что алгоритм сходится.

Любая практическая задача требует предварительного задания исходных данных. Как правило, можно задать некоторое характерное число n. Например, для задачи сортировки массива чисел по возрастанию n – число чисел в массиве, для задачи решения системы линейных уравнений n – число уравнений. Характерное число задачи определяет размерность задачи как величину массива исходных данных.

С ростом характерного числа размерность задачи возрастает. Введем понятие скорости роста для функций, зависящих от целочисленного параметра n.

Определение 5.1. Функции f (n) и g (n) имеют одинаковую скорость роста, если при достаточно больших n, начиная с некоторого n ₀, выполняется условие:

C ₁ g (n) £ f (n) £ C ₂ g (n),

где C ₁, C ₂ – некоторые константы.

Определение 5.2. Скорость роста функции f (n) ограничена снизу скоростью роста функции g (n), если при достаточно больших n, начиная с некоторого n ₀, выполняется условие:

C ₁ g (n) £ f (n),

где C ₁ – некоторая константа.

Определение 5.3. Скорость роста функции f (n) ограничена сверху скоростью роста функции g (n), если при достаточно больших n, начиная с некоторого n ₀, выполняется условие:

f (n) £ C ₂ g (n),

где C ₂ – некоторая константа.

Определение 5.4. Скорость роста функции f (n) больше скорости роста функции g (n), если для любой сколь угодно большой константы C ₂ существует некоторое n ₀, начиная с которого выполняется условие:

f (n) ³ C ₂ g (n).

Для того чтобы более наглядно представить скорости роста функций, их сравнивают со скоростями роста хорошо известных функций. В качестве таковых чаще всего используют степенные функции n^a. При a = 1 скорость роста функции n^a называют линейной, при a = 2 – квадратичной, при a = 3 – кубической и т. д. Скорость роста вида n^a называют полиномиальной. Очевидно, что при возрастании a скорость роста тоже увеличивается. Для некоторых функций скорости роста превосходят в пределе при n ® ¥ любую полиномиальную скорость. Такими функциями являются, например, 2 ⁿ, eⁿ, n!. Скорости такого типа называют экспоненциальными.

Обозначим через r (n) скорость роста размерности задачи. В задаче вычисления таблицы значений булевой функции n переменных скорость роста определяется таблицей значений переменных. Так как различных наборов переменных 2 ⁿ, а каждый набор состоит из n символов, то размерность задачи равна n 2 ⁿ и скорость роста будет экспоненциальной. В задаче решения системы линейных алгебраических уравнений методом исключения Гаусса наиболее быстро растет число элементов матрицы системы уравнений размером n ´ n. Поэтому скорость роста размерности этой задачи будет квадратичной, r (n) = n ².

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

Рассмотрим время реализации алгоритма – время счета.

Пусть при выполнении некоторого алгоритма выполняются элементарные операции t ₁, t ₂, …, t_k (арифметические, логические и другие). Среднее время выполнения этих операций обозначим через t ₁, t ₂, …, t_k. По аналогии с размерностью задачи введем понятие скорости роста числа выполняемых операций в зависимости от характерного числа n. Обозначим их для операций t ₁, t ₂, …, t_k через g ₁(n), g ₂(n), …, g_k (n). Без доказательства приведем следующее утверждение.

При n ® ¥ скорость роста общего времени счета T (n) равна максимальной из скоростей роста числа элементарных операций g ₁(n), g ₂(n), …, g_k (n) независимо от среднего времени их выполнения t ₁, t ₂, …, t_k.

Определение 5.5. Скорость роста общего времени счета T (n) называется вычислительной сложностью или просто сложностью алгоритма.

Обозначим сложность алгоритма через f (n). В зависимости от сложности все алгоритмы делятся на несколько классов.

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

Пример 5.1.

Рассмотрим задачу определения максимального элемента в массиве из n чисел. Поскольку число операций сравнения постоянно и равно n – 1, сложность алгоритма f (n) = n.

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

В примерах 5.2 и 5.3 точные алгоритмы имеют экспоненциальную точность.

Пример 5.2.

Рассмотрим задачу коммивояжёра. Необходимо обойти n городов и вернуться в исходный пункт, так чтобы суммарный путь был минимальным. Количество всех возможных вариантов обхода равно 0.5 n! Следовательно, сложность точного решения, основанного на переборе всех вариантов, равна f (n) = n!

Пример 5.3.

Рассмотрим задачу вычисления конъюнктивной нормальной формы (КНФ) булевой функции n переменных. Количество всех наборов переменных равно 2 ⁿ. Количество всех операций при переборе всех дизъюнкций пропорционально n 2 ⁿ, Следовательно, сложность алгоритма f (n) = n 2 ⁿ.

Экспоненциальные алгоритмы практически могут быть реализованы только при малых значениях n (обычно при n < 10).

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

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

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