9.2. Основные свойства алгоритмов

Основными свойствами алгоритмов являются массовость и результативность.

Массовость — это свойство алгоритма быть применимым для множества исходных данных. Термин “массовость” является расплывчатым, т.к. существуют алгоритмы, имеющие единственный вариант исходных данных.

Отметим, что для каждого алгоритма существует класс объектов, которые могут быть допустимы в качестве исходных данных. Тогда под массовостью понимают допустимость всех объектов этого класса, а не некоторого их числа.

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

Формулировка алгоритма должна быть точной и полностью определять все действия. Это свойство называется определенностью алгоритма.

Существуют два вида определений в алгоритмах. Первый вид определения называется прямым определением. В них новые понятия выражаются через одно или несколько известных. Второй вид называется “порочный круг”. Это определения, в которых новое понятие выводится либо из самого себя, либо из другого понятия, которое было из него выведено.

Часто используют рекурсивные определения. Они состоят из двух частей: 1-я — циклическая, 2-я — прямая часть определения. Она является входом в циклическую.

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

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

Для установления корректности алгоритмов используют три приема:

• конструирование новых алгоритмов путем комбинирования корректных алгоритмов;

• эквивалентные преобразования корректных алгоритмов;

• сужающие преобразования корректных алгоритмов.

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

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

Каждый алгоритм обычно связан с двумя алфавитами (иногда их называют языками). На основании одного языка формулируется алгоритм, а предложения другого являются допустимыми для алгоритма вариантами исходных данных.

Первый язык называется алгоритмическим, а второй - языком операндов.

Операнды — это объекты, над которыми выполняются операции, предписываемые алгоритмами.

9.3. Классификация алгоритмов

Существует довольно большое число различных классификаций алгоритмов. Рассмотрим некоторые из них. В отдельные классы выделяют имитирующие и эмпирические алгоритмы.

Имитирующие алгоритмы создаются на основе описаний действий объектов, наблюдений, зависимости исходных данных от изменяющихся условий.

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

Выделяют также случайные и самоизменяющиеся алгоритмы.

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

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

Эвристические алгоритмы (или эвристики) - это алгоритмы теоретически не обоснованные, но позволяющие сократить количество переборов в пространстве поиска. Они характеризуются как алгоритмы:

• находящие обычно «хорошие», но не обязательно наилучшие (оптимальные) решения;

• имеющие более простую реализацию, чем любой известный алгоритм, гарантирующий оптимальное решение.

Понятие «хороший» меняется от задачи к задаче. Универсальной структуры описания эвристических алгоритмов не существует.

Например, во многих задачах информатики требуется выборка А предметов из множества В предметов. Один эвристический подход состоит в том, чтобы выбирать предметы с вероятностью А/В. Здесь каждый предмет принимается или отвергается в момент его просмотра и можно делать только один просмотр вдоль всего набора предметов. В общем виде эта процедура не гарантирует, что будет выбрано в точности А предметов. Другой эвристический подход при выборе А чисел из В состоит в том, чтобы многократно генерировать случайные целые числа до тех пор, пока не окажется А различных чисел.

Приведем другую классификацию. Согласно ей все алгоритмы можно разделить на три группы:

• линейные;

• разветвляющиеся;

• циклические.

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

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

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

• на последовательные, с явно заданным числом повторений цикла;

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

• поисковые (иерархические), когда исходная задача разбивается на некоторое число подзадач и делаются попытки решить каждую из них.

На рис. 9.2 а – в приведена условная структура последовательных, итерационных и поисковых алгоритмов.

а) б)

в)

Рис. 9.2. Условная структура алгоритмов а) последовательная; б) итерационная; в) иерархическая (поисковая)

Во многих случаях эффективное решение задачи получают при использовании иерархического алгоритма. При этом исходная задача Z₀ разбивается на некоторое число подзадач Z₁, Z₂, ..., Z_k и делаются попытки решить каждую из них. Такое разбиение обычно описывается деревом поиска решения. Смысл разбиения на подзадачи состоит в том, что после разбиения за счет снижения объема конкретной подзадачи и возможного изменения ее структуры затраты на решение отдельной подзадачи значительно меньше, нежели на решение исходной задачи в целом. Важной проблемой при использовании иерархических алгоритмов является поиск оптимального решения, реализуемого на основе перебора путей на дереве решений. Выделяют следующие базовые виды поиска:

• в глубину;

• в ширину.

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

Поиск в ширину предусматривает ветвление на дереве решений от уровня к уровню, причем все подзадачи уровня i исследуются раньше, чем любая подзадача уровня (i - 1).

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

Выделяют следующие виды алгоритмов: логические; обработки данных; регулирования; эволюционные; оптимизации; решения задач вычислительной математики; проблемно-ориентированные; предметно-ориентированные; решения системных задач и др.

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

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

Алгоритмы регулирования связаны с управлением технологическими процессами и применяются в задачах автоматического управления и регулирования технических систем.

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

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

Алгоритмы решения задач вычислительной математики представляют собой комплексные алгоритмы решения конечных уравнений вида F(x) = 0, однородных дифференциальных уравнений ∂x/∂t = f(x(t), t), линейных уравнений вида Ах = В, и т.д. Обычно эти алгоритмы оформляются в виде стандартных программ.

Проблемно-ориентированные алгоритмы связаны с решением задач общенаучной тематики (например, статистической обработки информации).

Предметно-ориентированные алгоритмы направлены на решение задач, относящихся к определенному виду предметной области (например, расчет математических моделей объектов проектирования).

Алгоритмы решения системных задач связаны с организацией работы операционной системы, диспетчеризации, управления программами и данными в ЭВМ.

ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ

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

Вход: последовательность чисел (а_1, а_2, а_3,…,а_n).

Выход: перестановка (а^’_1, а^’_2, а^’_3,…,а^’_n) исходной последовательности, для которой а^’_{1 ≤} а^’₂ ≤ … _≤ а^’_n. Например, для входной последовательности (31, 59, 26, 58) алгоритм сортировки должен выдать (26, 31, 58, 59).

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

Рассмотрим один из важных методов сортировки вставками, описанный Корменом Т., Лейзерсоном Ч., Ривестом Р. Он эффективен при сортировке коротких числовых последовательностей. Метод основан на выборе очередного числа и вставки его в нужное место, сравнивая с имеющимися и передвигаясь справа налево. Исходными данными алгоритма является массив А[0, …, n] (последовательность элементов (чисел) длины n, подлежащая сортировке). Число элементов в массиве А обозначается через length [A]. Последовательность сортируется без дополнительной памяти. Здесь используется входной массив и фиксированное число ячеек памяти.

На рис. 9.3 показана работа алгоритма сортировки Кормена Т., Лейзерсона Ч., Ривеста Р на примере числовой последовательности А = (4, 1, 3, 5, 0, 2).

Рис. 9.3. Работа процедуры сортировки

Приведем описание алгоритма на верхнем уровне с пояснениями. Такое описание эффективно используется на практике при решении задач информатики и вычислительной техники и называется псевдокодом алгоритма.

ПСЕВДОКОД АЛГОРИТМА СОРТИРОВКИ:

1 for j ← 2 to length [A]

2 do key ← A[j]

3 “добавить A[j] к отсортированной части A[0, …, j - 1]”

4. i ← j - 1

5. while i > 0 and A[i] > key

6 do A[i + 1] ← A[i]

7 i ← j - 1

8 A[i + 1] ← key

Индекс j указывает выбранный очередной элемент. Часть массива A[0, …, j - 1] составляют уже просмотренные элементы, a - A[j + 1, …, n] — еще не просмотренные элементы. После выполнения процедуры сортировки массив А упорядочен по возрастанию.

В цикле for индекс j проходит массив слева направо. Просматривается элемент A[j] (строка 2 алгоритма) и производится сдвиг стоящих перед ним больших по величине элементов (начиная с (j - 1)-го) вправо, освобождая место для выбранного элемента (строки 4-7). В строке 8 элемент A[j] помещается на свободное место.

Комментарий:

1. Отступ от левого поля указывает на уровень вложения. Например, тело цикла for (строка 1) состоит из строк 2-8, а тело цикла while (строка 5) содержит строки 6-7.

2. Циклы while, for, repeat и условные конструкции if – then - else имеют тот же смысл, что и в языке программирования «Паскаль».

3. Кавычки начинают и заканчивают комментарий (идущий до конца строки).

4. Одновременное присваивание i ← j ← е (переменные i и j получают значение е) заменяет два присваивания j ← е и i ← j (в этом порядке).

5. Переменные (в данном случае i, j, key) локализуются внутри описанной процедуры (если не оговорено иное).

6. Индекс массива пишется в квадратных скобках, то есть запись A[v] соответствует v-му элементу в массиве А.