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

При построении алгоритма для сложной задачи используют системный подход с использованием декомпозиции (нисходящее проектирование сверху-вниз) и синтеза (восходящее программирование снизу-вверх). Как и при разработке структуры любой сложной системы, при формировании алгоритма используют дедуктивный и индуктивный методы. При дедуктивном подходе рассматривается частный случай общеизвестных алгоритмических моделей. Здесь при заданных предположениях известный алгоритм приспосабливается к условиям решаемой задачи. В настоящее время получили распространение специализированные пакеты, позволяющие решать многие задачи (mathcad, eureka, reduce, autocad и т. п.). Индуктивный способ предполагает эвристический системный подход (декомпозиция — анализ — синтез). В этом случае общих и наиболее удачных методов не существует. Возможны некоторые подходы, позволяющие в каждом конкретном случае находить и строить алгоритмы. Методы разработки алгоритмов можно разбить на методы частных целей, подъема, отрабатывания назад, ветвей и границ и т. п. Одним из системных методов разработки алгоритмов является структурное программирование. Структурное программирование основано на использовании блок-схем, формируемых с помощью управляющих структурных элементов. Выделяют три базовых структурных элемента (управляющие структуры): композицию, альтернативу, итерацию.

Рис. 5. Функциональные (а), предикатные (б) и объединяющие (в) вершины.

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

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

Рис. 7. Структура «альтернатива». Здесь в — условие (логическое выражение).

Итерация — это циклическая конструкция алгоритма, которая, вообще говоря, является составной структурой, состоящей из композиции и альтернативы. Итерации, могут быть представлены в двух формах: с предусловием (а) и с постусловием (б) (рис.8). Каждая из рассмотренных структур имеет один вход и один выход. Поэтому любая компьютерная программа может быть представлена блок-схемой, сформированной из представленных трех управляющих структур.

Рис. 8. Структура «итерация» .

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

Заметим, что для начального шага разработки программы чрезвычайно важным и необходимым является определение исходных (ввод) и выходных (вывод) данных задачи. С этого этапа начинается разработка практически любого алгоритма. Метод разработки программы сверху-вниз предполагает процесс пошагового разбиения алгоритма (блок-схемы) на все более мелкие части до уровня элементарных конструкций, для которых можно составить конкретные команды. Идея структурного программирования сверху-вниз состоит в том, что, если для некоторой функции f существует ее композиция через две другие функции g и h, т. е. F=h (g (x)), то проблема разработки алгоритма для f сводится к проблемам разработки алгоритмов для h и g. В структурном программировании сверху-вниз на каждом шаге пытаются текущую функцию выразить как композицию двух (или более) других функций, которые представимы в виде рассмотренных выше управляющих структур. Зачастую используют метод структурного программирования снизу-вверх. По сути, мы приходим к конечному результату системным методом. Сначала разбиваем задачу на отдельные блоки (модули) с их связями между собой (декомпозиция), затем, после их разработки, проводим сборку блоков в единую программу (синтез). Принцип снизу-вверх широко распространен среди программистов, которые предпочитают модульный подход, предполагающий максимальное использование стандартных и специализированных библиотек процедур, функций, модулей и объектов.