Файл: Matlog.doc

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 символов, то размерность задачи равна n2ⁿ и скорость роста будет экспоненциальной. В задаче решения системы линейных алгебраических уравнений методом исключения Гаусса наиболее быстро растет число элементов матрицы системы уравнений размером 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.5n! Следовательно, сложность точного решения, основанного на переборе всех вариантов, равна f(n) = n!

Пример 5.3.

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

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

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

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

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

5.2. Машина Тьюринга

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

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

Первые работы по уточнению понятия алгоритм появились в 1936 – 1937 годах. Это были работы Тьюринга, Поста, Маркова, Чёрча. Было предложено несколько определений понятия алгоритм. Впоследствии было показано, что все они равносильны.

Одной из первых и весьма удачных попыток дать точный математический эквивалент интуитивного представления об алгоритме было введение понятия машины Тьюринга в 1937 году, за 9 лет до появления первой ЭВМ.

Машина Тьюринга – абстрактная машина. Это математическая модель идеализированного вычислительного устройства.

Машина Тьюринга состоит из ленты и управляющего устройства со считывающей и записывающей головки (каретки) (рис. 5.1).

Рис. 5.1

Лента жестко закреплена слева и бесконечна справа. Иногда считают, что лента не ограничена справа и слева. Лента разделена на ячейки, которые нумеруются натуральными числами 1, 2, … .

В каждую ячейку ленты заносятся символы внешнего алфавита машины Тьюринга

A = {a₀, a₁,... a_n}. (5.1)