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

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

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

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

Рис. 6. Структура «композиция»

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

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

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

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

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

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

Дата добавления: 2014-01-06