Методы разработки и анализа алгоритмов
Нисходящим проектированием алгоритмов, проектированием алгоритмов "сверху вниз" или методом последовательной (пошаговой) нисходящей разработки алгоритмов называется такой метод составления алгоритмов, когда исходная задача (алгоритм) разбивается на ряд вспомогательных подзадач, формулируемых и решаемых в терминах более простых и элементарных операций (процедур). Последние, в свою очередь, вновь разбиваются на более простые и элементарные, и так до тех пор, пока не дойдём до команд исполнителя. В терминах этих команд можно представить и выполнить полученные на последнем шаге разбиений подзадачи.
Восходящий метод, наоборот, опираясь на некоторый, заранее определяемый корректный набор подзадач, строит функционально завершенные подзадачи более общего назначения, от них переходит к более общим, и так далее, до тех пор, пока не дойдем до уровня, на котором можно записать решение поставленной задачи. Этот метод известен как метод проектирования "снизу вверх".
Структурные принципы алгоритмизации (структурные методы алгоритмизации) – это принципы формирования алгоритмов из базовых структурных алгоритмических единиц (следование, ветвление, повторение), используя их последовательное соединение или вложение друг в друга с соблюдением определённых правил, гарантирующих читабельность и исполнимость алгоритма сверху вниз и последовательно.
Структурированный алгоритм – это алгоритм, представляемый как алгоритм следования и вложения базовых алгоритмических структур. При структурированной разработке алгоритмов правильность алгоритма можно проследить на каждом этапе его построения и выполнения.
Теорема (о структурировании). Любой алгоритм может быть эквивалентно представлен структурированным алгоритмом, состоящим из базовых алгоритмических структур.
Одним из широко используемых методов проектирования и разработки алгоритмов (программ) является модульный метод.
Модуль – это некоторый алгоритм или его блок, имеющий конкретное наименование, по которому его можно выделить и актуализировать. Иногда модуль называется вспомогательным алгоритмом. В программировании используются синонимы – процедура, функция.
Свойства модулей:
- функциональная целостность и завершенность (каждый модуль реализует одну функцию);
- автономность и независимость от других модулей (независимость работы модуля-преемника от работы модуля-предшественника; при этом их связь осуществляется только на уровне передачи/приема параметров и управления);
- эволюционируемость (развиваемость);
- открытость для пользователей и разработчиков (для модернизации и использования);
- корректность и надежность;
- ссылка на тело модуля происходит только по имени модуля, то есть вызов модуля возможен только через его заголовок.
Свойства (преимущества) модульного проектирования алгоритмов:
- возможность разработки алгоритма большого объема (алгоритмического комплекса) различными исполнителями;
- возможность создания и ведения библиотеки наиболее часто используемых алгоритмов (функций);
- облегчение тестирования алгоритмов;
- упрощение проектирования и модификации алгоритмов;
- наблюдаемость вычислительного процесса при реализации алгоритмов.
Тестирование алгоритма – это проверка правильности или неправильности работы алгоритма на специально заданных тестах или тестовых примерах – задачах с известными входными данными и результатами. Тестовый набор должен быть минимальным и полным, то есть обеспечивающим проверку каждого отдельного типа наборов входных данных, особенно исключительных случаев.
Например, для задачи решения квадратного уравнения ax2 + bx + c = 0 такими исключительными случаями, например, будут: 1) a = b = c = 0; 2) a = 0, b, c – отличны от нуля; 3) D = b2 – 4ac < 0 и др.
Тестирование алгоритма не может дать полной (100%-ой) гарантии правильности алгоритма для всех возможных наборов входных данных, особенно для сложных алгоритмов.
Полную гарантию правильности алгоритма может дать описание работы и результатов алгоритма с помощью системы аксиом и правил вывода или верификация алгоритма.
Рассмотрим алгоритм нахождения числа всех различных двоичных сообщений (двоичных последовательностей) длины n битов, используя при этом не более одной операции умножения, и докажем правильность этого алгоритма. Вначале найдем число всех таких сообщений. Число двоичных сообщений длины 1 равно 2 = 21 (это "0" и "1"), длины 2 равно 4 = 22 ("00", "01", "10", "11"). Отправляясь от этих частных фактов, методом математической индукции докажем, что число различных сообщений длины n равно 2n. Этот индуктивный вывод докажет правильность алгоритма.
Пусть это наше утверждение верно для n = k. Тогда для n = k + 1 получаем, что добавление каждого бита (0 или 1) к любому из 2k сообщений длины k приведет к увеличению числа сообщений в 2 раза, то есть их число будет равно 2 x 2k = 2k+1, что и доказывает наше индуктивное предположение.
Составим теперь алгоритм вычисления числа x = 2n с использованием операции умножения только один раз.
Прологарифмируем последнее равенство. Получим ln(x) = ln(2n) = n ln(2) .
Используя равенство exp(ln(x)) = x, получим, что exp(ln(x)) = x = exp(n ln(2)).
Для несложных алгоритмов грамотный подбор тестов и полное тестирование может дать полную картину работоспособности (неработоспособности).
Трассировка– это метод пошаговой фиксации динамического состояния алгоритма на некотором тесте. Часто осуществляется с помощью трассировочных таблиц, в которых каждая строка соответствует определённому состоянию алгоритма, а столбец – определённому состоянию параметров алгоритма (входных, выходных и промежуточных). Трассировка облегчает отладку и понимание алгоритма.
Процесс поиска и исправления (явных или неявных) ошибок в алгоритме называется отладкой алгоритма.
Некоторые (скрытые, трудно обнаруживаемые) ошибки в сложных программных комплексах могут выявиться только в процессе их эксплуатации, на последнем этапе поиска и исправления ошибок – этапе сопровождения. На этом этапе также уточняют и улучшают документацию, обучают персонал использованию алгоритма (программы).
Пример. Определить функцию фрагмента алгоритма вида:
x[1]=4;
x[2]=9;
s=x[1];
for( i=1; i<= n; i++)
{
if (s<x[i])
{
s=x[i];
k=i; // индекс большего числа
}
}
cout<<k;
Если выписать трассировочную таблицу вида
| i | x[i] | K | s<x[i] | S | i<=n |
| Нет | Да | ||||
| Да | Да | ||||
| — | — | — | — | Нет |
то функция алгоритма становится более понятной – эта функция состоит в нахождении индекса максимального элемента ряда.
В заключение данного раздела приведем общую структуру алгоритмического обеспечения. Критерии, по которым алгоритмы могут быть классифицированы, бывают разными, поэтому предлагаемая ниже схема отражает основные элементы структуры и в некоторых случаях является условной, в том смысле, что блоки приведенной на рис. 9.1 структуры могут "перекрываться".
Рис. 9.1. Структура алгоритмического обеспечения
Основные формы использования алгоритмов – автономное, библиотечное, пакетное.
Автономный алгоритм определяется решаемой задачей, структурой используемых данных, структурой логических связей частей (модулей) алгоритма и языком псевдокодов, на котором представлен, описан алгоритм.
Библиотека алгоритмов определяется множеством задач, решаемых с помощью библиотеки, множеством алгоритмов для решения типовых задач предметной области и структурой используемых данных.
Пакет алгоритмов, как и библиотека, определяется множеством задач, решаемых с помощью пакета, набором алгоритмов для решения типовых задач или их составных частей из предметной области, структурой используемых данных и обменом данными между задачами (модулями), специальным языком, на котором формулируется задание (последовательность этапов решаемой задачи, последовательность задач задания).