Нисходящее проектирование

6.1. Технология проектирования алгоритмов

Процесс решения задачи на ЭВМ можно разбить на ряд этапов:

1) постановка задачи;

2) математическое описание задачи — создание математи­ческой модели задачи;

3) составление алгоритма решения задачи;

4) составление программы;

5) разработка тестовой задачи;

6) отладка программы;

7) расчет на ЭВМ, получение и анализ результатов.

    Существенным шагом на пути снижения трудоемкости процесса программирования стал структурный подход к проектированию алгоритмов. Его основными принципами яв­ляются нисходящее проектирование и модульное програм­мирование. Нисходящее проектирование заключается в по­следовательном разбиении задачи на все более мелкие уча­стки, т.е. процесс программирования идет «сверху вниз». Модульное программирование предполагает создание для ка­ждого такого участка отдельной автономной программы — модуля. Специально созданная программа объединяет все модули в целое и управляет их работой.

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

6.2. Принципы нисходящего проектирования:

1. Для каждого проектируемого модуля, на каждом шаге проектирования должны быть специфицированные входы, функции и выходы. Это и есть внешняя спецификация модуля.

2. В процессе проектирования не следует обращаться к деталям реализации до самого последнего момента.

3. На каждом шаге проектирования функцию каждого модуля следует излагать самое большее на одной странице текста или схемы. На верхнем уровне – весь проект должен быть описан в виде, максимум, 10 строк инструкций.

4. Документирование нисходящего проектирования осуществляется в виде комбинации повествовательной и графической форм.

 

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

            

Рис. 14

               

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

 Рис. 15

 

    Все вершины дерева обозначим через Cij. Первый индекс i обозначает уровень подзадачи, а второй j ‑ порядковый номер подзадачи на этом уровне. В таком дереве имеются: корневая (C01), внутренние (C12, C13) и концевые (C21, C22, C23, C24) вершины. Корневая вершина соответствует решаемой задаче, внутренние – подзадачам, которые, в свою очередь, разбивают в дальнейшем на подзадачи; концевые – подзадачам, которые могут быть без труда записаны на языке программирования. Процесс декомпозиции внутренних и окончательная реализация концевых подзадач начинаются с разработки требований к подзадаче. Описание этих требований составляет внутреннюю спецификацию подзадачи. Состав внутренних спецификаций такой же, как и внешней спецификации. Внутренняя спецификация вместе с алгоритмом должна иметь небольшой объем, который должен следует разместить на одной странице в следующей форме:

 

Входные данные Выходные данные Промежуточные данные Метод Аномалии

{<имя подзадачи>} <алгоритм>

 

    При проектировании алгоритма подзадача может быть реализована в виде подзадачи-функции либо подзадачи-блока.

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

 

Входные данные Выходные данные Промежуточные данные Метод Аномалии

{<имя подзадачи>} <тип рез> функция <имя> (<список параметров>) арг <описание входных параметров> нач <описание промежуточных данных> <тело функции> кон возврат <тип рез>

 

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

 

{<раскрываемая подзадача>} рез= <имя> (<список фактических параметров>)

 

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

 

 

Входные данные Выходные данные Промежуточные данные Метод Аномалии

{<имя подзадачи>} <алгоритм>

 

    После разработки подзадачу-блок подставляют целиком (без внутренних спецификаций) в порождающую подзадачу. Сама же она в порождающей подзадаче остается в виде комментария. Описание промежуточных и исходных данных добавляется к соответствующим описаниям порождающей задачи.

    Совокупность подзадач-функций и подзадач-блоков вместе с корневой задачей составляет рабочий проект программы. В дереве подчинения задачи-блоки будем обозначать в виде квадратов, а подзадачи-фунцкии – в виде кружков. Например, пусть имеется некоторый рабочий проект программы (рис. 16):

 Рис. 16

 

Тогда после подстановки подзадач-блоков в порождающие их подзадачи получится следующий окончательный проект (рис. 17):

 Рис. 17

7. Варианты заданий для курсовой работы

    В качестве расчетного задания студент получает задачу различения двух графов, т.е. определения эквивалентности или неэквивалентности графов на основе заданной характеристики. В результате ему необходимо разработать и отладить программу, оформленную в виде выполняемого файла (*.exe), для решения задачи различения двух графов. При отладке программы рекомендуется применять графы с четным числом вершин не более 20 и числом дуг (ребер) не более 50.

Каждому студенту выдается инвариант графа и дополнительная информация, включающая в себя класс графов, семейство графов и типовую форму представления графа в памяти ЭВМ.