А) б) в)

Рис.1.5. Представление линейного списка (а) и операции над ли­нейным списком ДОБАВИТЬ (б) и УДАЛИТЬ (в)

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

Универсальность линейного списка заключается так­же и в том, что его элементы, в свою очередь, могут быть линейными списками (в предельном случае единич­ной длины); такая структура называется просто списком.

Рис. 1.7. Пример двоичного дерева (а) и его физическая реализа­ция (б)

Примечание. Список позволяет, например, экономно представлять разреженные матрицы, как это показано на рис. 1,6, а.

Записи линейного списка, изображенного на рис. 1.6, б вертикально, содержат в одном из своих полей количество ненуле­вых элементов в строке матрицы; эта информация может быть использована для перестановки строк матрицы, что требуется в ряде алгоритмов САПР. Записи линейных списков, изображен­ных горизонтально, содержат номера столбцов ненулевых эле­ментов строк матрицы.

В задачах структурного синтеза, относящихся к зада­чам искусственного интеллекта, широко используется представление информации в виде дерева, например в методе И-ИЛИ-дерева. Для организации данных в виде дерева может быть применена списковая структура. Однако чаще для этой цели используют двоичные де­ревья, к которым могут быть сведены общие деревья. Двоичное дерево — дерево, у каждой вершины которого не более двух поддеревьев. Один из способов физической реализации двоичных деревьев представлен на рис. 1.7.

Комбинация рассмотренных базовых структур данных позволяет организовывать новые структуры, отражающие сложные отношения между единицами информации, об­рабатываемой ПО САПР. Большинство современных языков программирования высокого уровня имеют разви­тые средства для создания сложных структур данных. Исключение составляет язык ФОРТРАН, среди типов данных которого отсутствует СТРОКА, а единственная «встроенная» структура данных — массив. Поэтому ор­ганизация более сложных структур при программирова­нии на этом языке является заботой разработчика ПО.

Рис.1.8

Структуры управления вычислениями.В ПОреализуются алгоритмы обработки информации. В САПР эти алгоритмы обычно являются весьма сложными и харак­теризуются итерационностью, многоуровневой вложен­ностью процедур, множеством точек выбора альтерна­тивных решений. Однако для программной реализации любых алгоритмов достаточно трех базовых структур управления: следование, цикл и ветвление.

Следование — структура из нескольких последо­вательно выполняемых операторов, причем этими опера­торами в общем случае могут быть операторы вызова подпрограмм.

Цикл — структура, назначение которой — представ­ление многократно повторяющихся вычислительных про­цессов. Различают циклы с предусловием (рис. 1.8, а),с постусловием (рис. 1.8, в) с параметром (рис. l.8, б).

Рис. 1.9. Графическое изображение ветвлений:

а — ЕСЛИ-ТО-ИНАЧЕ; б — ЕСЛИ-ТО; в — многозначно

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

Ветвление — структура, предназначенная для при­нятия решений в ходе вычислительного процесса. Про­стейшими ветвлениями являются альтернативные: ЕСЛИ-ТО-ИНАЧЕ (рис. 1.9, а) и ЕСЛИ-ТО (рис. 1.9,6). В некоторых алгоритмах возникает задача выбора не из двух, а из нескольких возможностей, в этом случае удобна структура многозначное ветвление (рис. 1.9,в). Структура ЕСЛИ-ТО-ИНАЧЕ фундаментальна, через нее могут быть представлены две другие структуры ветвления.

Важное свойство всех структур — наличие только одного входа и только одного выхода, как у простого оператора. Поэтому каждый прямоугольный блок на рис. 1.8—1.9, обозначающий какое-либо действие, может быть заменен любой из трех базовых структур. Возмож­ность представления любых алгоритмов с помощью вло­женных структур следования, цикла и ветвления состав­ляет основу метода структурного программирования (см. § 1.3).

Управление ходом вычислительного процесса с по­мощью данных.Хотя рассмотренные выше структуры управления универсальны, в некоторых практических приложениях более удобным оказывается передать часть функций по управлению ходом вычислительного процесса данным.

Таблица 1.1

Рассмотрим два метода, использующих дан­ные для управления: 1) метод таблиц решений; 2) метод конечного автомата.

Метод таблиц решений целесообразно при­менять в алгоритмах, характеризующихся большим ко­личеством условий и ограниченным набором действий, выполняемых в различных сочетаниях в зависимости от условий. Табл. 1.1— таблица решений для простейшего примера, содержащего 2 условия и 3 действия. Символ «1»в клетках таблицы для условий соответствует ситуа­ции, когда значение данного условия истинно. Символ «*» в клетках таблицы для действий означает необхо­димость выполнения соответствующего действия. Таким образом, обработка таблицы при каждом вхождении заключается в нахождении столбца, соответствующего текущему сочетанию условий, и в выполнении действий, отмеченных символом «*» в этом столбце. Достоинство этого метода управления — легкая модифицируемость ПО под новые условия применения, поскольку реоргани­зация таблицы не требует изменений в процедурной масти программного компонента.

Метод конечного автомата находит широ­кое применение в языковых процессорах для распознава­ния цепочек символов [2]. Поясним идею метода на кон­кретном примере. Пусть из всего множества слов конеч­ной длины, составленных из символов алфавита {А, К, О, П, Р, С, Т, }, допустимыми являются только СТОП и СТРОКА О, где — символ конца слова. В задачу программы распознавателя, использующей метод конеч­ного автомата, входит обнаружение из всего множества цепочек символов только двух допустимых. В основе реа­лизации конечного автомата на ЭВМ лежит таблица переходов,

Таблица 1.2

представленная в табл. 1.2. Ее столбцы помечены символами входного алфавита, строки — номерами со­стояний. Элементами таблицы являются номера новых состояний, в которые должен переходить автомат из те­кущего состояния при поступлении входных символов. В таблице переходов примера все пустые клетки должны быть заполнены номером 9 (для наглядности он опущен). Процедурная часть программы распознавателя должна обеспечивать поиск столбца, соответствующего очередно­му входному символу, и «передвигать» указатель на строку таблицы, отвечающую новому состоянию.

Работа автомата начинается с некоторого исходного состояния (помеченного номером 0). Появление на входе автомата символа С переводит его в состояние 1, любой другой символ (за исключением ) вызовет переход автомата в состояние 9, откуда есть выход только по символу > конца строки. Таким образом, любая цепочка символов, не начинающаяся с символа С, будет распознавателем отвергнута.

Из состояния 1 допускающим бу­дет только переход в состояние 2 для символа Т, из со­стояния 2 допускающих переходов два — для символов О и Р. Работа распознавателя завершается обработкой символа . В табл. 1.2 для состояний автомата 1— 8 справа от таблицы записаны подцепочки символов, при­водящие в каждое из этих состояний.

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

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

Среди структур управления, не относящихся к базо­вым, важнейшей является подпрограмма.

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

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

В дальнейшем речь будет идти в основном о подпрограммах этого типа.

Использование подпрограмм ставит проблему обмена информации между вызывающей и вызываемой подпрог­раммами. Вызов подпрограммы обычно сопровождается передачей ей фактических параметров, располагаемых в ОП, среди которых различают аргументы, результаты и модифицируемые параметры (см. рис. 1.1). Отметим, что это не единственный способ обмена данными между программой и подпрограммой (см. гл. 3). Наиболее ши­роко используются два механизма связывания фактиче­ских и формальных параметров подпрограмм: 1) по адресу; 2) по значению.

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

Большинство современных языков программирования высокого уровня допускает оба метода передачи пара­метров. В качестве фактических параметров могут вы­ступать и имена подпрограмм, передача подпрограмм всегда осуществляется передачей адреса точки входа в эти подпрограммы.

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

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

■ Примечание. Передача параметров по адресу представляет собой обобществление данных между двумя (а возможно, и бо­лее) программными компонентами.

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

Повторно-используемая подпрограмма также обеспе­чивает возможность многократного обращения, но толь­ко в том случае, если новый вызов следует после пол­ного завершения ее работы по предыдущему вызову. Повторно-используемая подпрограмма — подпрограмма, которая не сохраняет историю своих вызовов. Это усло­вие может быть легко соблюдено при разработке ком­понентов ПО на любом языке программирования. В ПО САПР все программные компоненты должны быть повторно-используемыми.

Создание реентерабельных программ часто требует от их разработчика значительных дополнительных уси­лий. Поэтому такие программы в ПО САПР находят ограниченное применение — главным образом в подсисте­мах, допускающих одновременную работу нескольких пользователей.

К понятию реентерабельности подпрограмм близко (по не тождественно) понятие рекурсивности. Рекурсив­ная подпрограмма— подпрограмма, которая вызывает гама себя (либо непосредственно, либо через цепочку модулей). Многие алгоритмы автоматизированного проектирования в области структурного синтеза и парамет­рической оптимизации по сути рекурсивные. Самым про­стым примером здесь может служить метод половинного деления, используемый для одномерного поиска экстре­мума функций. Однако не все алгоритмические языки позволяют писать непосредственно рекурсивные под программы,

так в языке ФОРТРАН программирование рекурсивных алгоритмов требует использования спе­циальных приемов, усложняющих программу.