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