Приложение 1
Разработка алгоритмов в САПР
В данном приложении очень кратко рассматриваются методы разработки программных систем, как влияющие на методы разработки алгоритмов. Далее основное внимание уделено способам описания алгоритмов на псевдокоде, так как на псевдокоде записано большинство алгоритмов, изложенных в учебнике.
Методы проектирования систем
Выделим следующие основные методы проектирования программных систем:
Метод "сверху - вниз " предполагает разработку общей идеи с последующей ее детализацией. Метод " снизу - вверх" предполагает синтез системы на основе готовых модулей низшего уровня путем последовательного их соединения в модули более высокого уровня.
Смешанный метод предусматривает совместное использование указанных методов, т. е. разработка идет сверху вниз, однако на низшем уровне используются готовые модули. Смешанный метод проектирования характерен для современной технологии создания программных систем. В этих технологиях используют развитые программные среды, имеющие языки высокого уровня и возможности объектно-ориентированного программирования. Накоплены большие библиотеки классов объектов для быстрого программирования пользовательского интерфейса, для работы с базами данных, для работы на основе Web - технологии. В каждой среде имеется набор конструкторов для визуального программирования различных экранных форм и меню, позволяющих на основе алгоритмов верхнего уровня быстро создавать программные системы высокого качества.
Проектирование на основе расширяющегося ядра заключается в том, что сначала смешанным методом создают ядро системы, которое хотя и имеет ограниченные функциональные возможности, но его возможно эксплуатировать. Далее система последовательно развивается путем добавления новых модулей, реализующих недостающие функции. По мере своего развития система становится полнофункциональной действующей системой.
Способы описания алгоритмов.
После разработки технического задания на систему начинается разработка технического проекта. Одним из основных этапов технического проекта является разработка алгоритмов поставленных задач. В первую очередь разрабатываются алгоритмы высокого уровня. Для этого система сначала рассматривается как "черный ящик", т. е. как система, содержание которой неизвестно, и определяется состав входных и выходных параметров. Далее выполняется декомпозиция системы, т. е. система разделяется на части ( подсистемы, модули, блоки и т. д.) и определяется способ их управления.
Управление модулями может выполняться на основе жесткой логики, на основе управления данными и на основе управления событиями. Возможна комбинация способов управления модулями. Таким образом, устанавливаются функциональные связи между модулями. К каждой части системы применяют тот же подход: определяют входные и выходные параметры, а затем выполняют ее декомпозицию. Процесс декомпозиции ведут до уровня, когда уже можно применять готовые процедуры из соответствующих библиотек.
При разработке алгоритмов очень важно определить способы их описания, позволяющие обеспечить необходимую наглядность, простоту и возможность быстрой модификации алгоритма.
В настоящее время используют следующие формы записи алгоритмов:
Графические схемы позволяют записывать алгоритм с помощью стандартизованных графических символов (ГОСТ 19.002-80 и ГОСТ 19.003-80).
Достоинства графических схем:
- простота;
-
наглядность;
Недостатки:
- сложность сопровождения (сложно
корректировать, пополнять, развивать);
- неудобство хранения (алгоритм на
бумажном носителе неудобно корректировать, а на магнитном носителе - неудобно
просматривать большие графические файлы).
Алгоритмические языки: позволяют записывать алгоритмы в текстовом виде, обычно называемом псевдокодом. Примером такого языка является алгоритмический язык, предложенный акад. А. Ершовым [17], [18].
Достоинства псевдокодов:
- компактность;
- возможность строгой записи
алгоритма;
- удобство раннего программирования по алгоритму (использование
имитаторов);
- возможность записи с любой степенью детализации;
- легко
корректировать и дополнять алгоритм на основе текстовых редакторов (легко
сопровождать).
К недостаткам псевдокодоа относится необходимость знания алгоритмического языка, который может быть достаточно сложным.
Табличные алгоритмы (ТА) представляют собой таблицы, фиксирующие определенные способы принятия решений. Иначе говоря, ТА - это декларативное представление алгоритма, позволяющее непроцедурным образом выразить алгоритм и записать его в базу знаний. Принятие решений выполняется с помощью универсального модуля, который выбирает таблицу из базы знаний, обрабатывает ее и принимает решение, соответствующее входным данным.
Достоинства табличных алгоритмов:
- простота;
-
возможность использования без программирования;
- легко сопровождать
(изменения выполняются путем корректировки базы знаний).
Основным недостатком табличных алгоритмов является ограниченная сфера действия, так как не все алгоритмические действия можно выразить с помощью табличного алгоритма. Более подробно табличные алгоритмы рассмотрены в разделе "Табличный процессор".
Алгоритмический язык
Алгоритмический язык в данной работе является основным средством для выражения алгоритмов, поэтому необходимо кратко рассмотреть этот язык. Будем использовать алгоритмический язык Ершова (Е-язык), модифицированный автором применительно особенностям САПР. Предполагается, что читатель знаком с основами программирования, поэтому не будем уточнять такие понятия как - "алгоритм", "символы", "слово", "выражение", "описание", "оператор", "блок" и т. д. Отметим лишь некоторые синтаксические особенности записи алгоритмов. Будем различать терминальные и нетерминальные символы.
Терминальные символы - это символы, с помощью которых записывают операторы, служебные слова, переменные и массивы. Таким образом, с помощью терминальных символов образуют выражения, которые можно программировать.
Нетерминальные символы - это символы, которые при дальнейшем уточнении будут заменены на терминальные или останутся в программе как комментарии. Эти символы заключают в угловые скобки "<" и ">".
Квадратные скобки "[" и "]" означают необязательность заключенного в них выражения. Символ "|" используется как логическая связка "или". Символ ";" означает продолжение с новой строки слишком длинного выражения. Текстовые константы заключаются в апострофы. Выражение, идущее после служебное слово КОМ, рассматривается как комментарий. Операторы и служебные слова можно сокращать до четырех символов.
АЛГ <обозначение алгоритма>
КОМ <название алгоритма>
АРГ
<список входных параметров (аргументы)>
РЕЗ
<список выходных параметров>
ЛОК
< список локальных параметров >
НАЧ <тело алгоритмов>
КОН
Списки аргументов, выходных параметров и локальных переменных образуют спецификацию алгоритма.
Обозначение алгоритма это текст из латинских букв и цифр, например:
АЛГ prim1
или
АЛГ optimvod
или
АЛГ opt-12
или
АЛГ prim1
Список входных, выходных и локальных параметров (аргументы) выражается в следующем виде:
ЦЕЛ <имя целой переменной или массива> - <название переменной>
ВЕЩ <имя вещественной переменной> - <название переменной>
ЛОГ <имя логической переменной> - <название переменной>
ТЕКС <имя текстовой переменной> - <название переменной>
Пример:
ЦЕЛ n - количество ступеней
ЦЕЛ kx - количество входных переменных
ВЕЩ vx(12,10) - входной массив
ТЕКС im(20) - массив с номером чертежа детали из 20 символов
ВЕЩ mx(kx) - входной массив переменной размерности из kx элементов.
Если необходимо обратится к другому блоку или модулю, то это выполняется с помощью конструкции:
ВЫП <имя алгоритма> [(список параметров)]
Рассмотрим следующие группы операторов управления: ветвление и циклы.
Ветвление: конструкция ЕСЛИ : ТО
Указанная конструкция имеет вид:
ЕСЛИ <условие> ТО <выполняемый оператор, если условие истинно> КЕ
Пример схемы для данного оператора показан на рис.П-1
Для указанной схемы можно записать:
ЕСЛИ (a > 0) ТО b = 1 КЕ
Другой вариант этой конструкции:
ЕСЛИ <условие>
ТО <выполняемые действия, если условие истинно >
КЕ
Пример схемы для данного оператора показан на рис.П-2
.gif)
Для указанной схемы можно записать:
ЕСЛИ (L=3)
ТО В=3
М(I)=4
КЕ
Если имеет место схема, показанная на рис. П-3,
.gif)
то для записи на псевдокоде необходимо изменить условие с b = 1 на b &nequal; 1, тогда можно записать:
ЕСЛИ b &nequal; 1
ТО l = 3
k = 4
КЕ
Ветвление: конструкция ЕСЛИ : ТО: ИНАЧЕ
Указанная конструкция имеет вид:
ЕСЛИ <условие>
ТО <действия, если условие истинно>
ИНАЧЕ <действия, если условие ложно>
КЕ
Пример схемы для данного оператора показан на рис.П-4.
.gif)
Для указанной схемы можно записать:
ЕСЛИ b > 0)
ТО l = l+2
ИНАЧЕ l = i+1
КЕ
Пример более сложной схемы для данной конструкции приведен на рис. П-5.
.gif)
Для указанной схемы можно записать:
ЕСЛИ m > l
ТО ЕСЛИ m = 2
ТО t = 6
ИНАЧЕ t = t+1
КЕ
ИНАЧЕ t = 2
КЕ
Другой пример схемы для данной конструкции приведен на рис. П-6.
.gif)
Для указанной схемы можно записать:
ЕСЛИ m > l
ТО ЕСЛИ l = 3)
ТО t = 1
КЕ
КЕ
Ветвление: переключательная конструкция
Эта конструкция применяется взамен многократного применения конструкции ЕСЛИ : ТО:КЦ и имеет вид:
ВЫБОР
ПРИ <условие
1>
<действия, если условие 1 истинно
>
...
ПРИ <условие n>
<действия, если условие n истинно >
[ОСТ
<условие
>
<действия, если условия от 1 до n ложны>]
КВ
Пример схемы для данной конструкции показан на рис.П-7.
.gif)
Для указанной схемы можно записать:
ВЫБОР
ПРИ a <
0
T=?корней нет?
ПРИ a =
0
Т= ?один корень?
ПРИ a >
0
Т=?два корня?
КВ
Ветвление: конструкция ЦИКЛ ПОКА:
Эта конструкция предназначена для организации цикла с предусловием и имеет вид:
ЦИКЛ ПОКА (<условие>)
<тело цикла>
КЦ
"Тело цикла" ( действия, выполняемые в цикле) повторяется до тех пор, пока "условие" истинно.
Пример схемы в двух вариантах для данной конструкции показан на рис.П-8.
.gif)
Для указанной схемы можно записать:
ЦИКЛ ПОКА h < amax
b=b + 1
:
h=COS(l+b)
КЦ
Ветвление: конструкция ЦИКЛ ДЛЯ:
Эта конструкция предназначена для организации цикла с переменной
и имеет вид:
ЦИКЛ ДЛЯ <имя переменной> ОТ <начальное значение> ДО <конечное значение> [ШАГ<величина шага>]
<тело цикла>
КЦ
Если шаг не задан, то по умолчанию принимается равным 1.
Пример схемы в двух вариантах для данной конструкции показан на рис.П-9.
.gif)
Для указанной схемы можно записать:
ЦИКЛ ДЛЯ i ОТ 1 ДО n ШАГ 2
<тело цикла>
КЦ
Рассмотрим операторы вывода данных.
Вывод на принтер задается оператором ПЕЧАТЬ < список
переменных >. Например:
ПЕЧАТЬ a, b, c.
Вывод на экран задается оператором ВЫВОД < список переменных
>. Например:
ВЫВОД k(a), m, t, " Резец ".
Работа с файлами
Рассмотрим работу с файлами реляционного типа, состоящими из однородных записей. Файл можно открыть в какой-либо рабочей области с номером от 1 до 256 и присвоить псевдоним. Использование псевдонима позволяет файлы с одинаковой структурой, но с разными обозначениями обрабатывать по единому алгоритму.
Конструкция для открытия файла:
ОТКРЫТЬ <полное имя файла> РО <номер рабочей области> [ПСЕВДОНИМ <обозначение псевдонима>]
Одновременно может быть открыто несколько рабочих областей. Для перехода к нужной рабочей области используется конструкция:
РАБОБЛ <номер рабочей области> | <псевдоним>
Закрытие файла выполняется с помощью следующего оператора:
ЗАКРЫТЬ <номер рабочей области> | <псевдоним>
Для работы с записями используется комплекс операторов, главными из которых являются следующие. При открытии файла указатель записи неявно устанавливается на первую запись. Для перехода к другим записям используется операторы:
перехода к заданной записи
ИДТИ К <номер
записи>
Удаление записей выполняется в два этапа. На первом этапе текущая запись помечается на удалением оператором ПОМЕТИТЬ. На втором этапе оператором УДАЛЗАП удаляются все помеченные в файле записи. Если нужно снять метку с текущей записи, то используют оператор СНЯТЬ МЕТКУ.
| С помощью указанного набора операторов можно выразить алгоритм практически любой сложности |