Главная страница | Контакты | Случайная страница Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Управление вычислениями

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

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

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

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

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

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

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

Таблица 1.1.

Метод конечного автомата находит широ­кое применение в языковых процессорах для распозна­вания цепочек символов. Поясним идею метода на конкретном примере. Пусть из всего множества слов ко­нечной длины, составленных из символов алфавита {О, П, С, Т, ¿ }, допустимым является только СТОП¿, где ¿ – символ конца слова. В задачу программы-распознавателя, использующей ме­тод конечного автомата, входит обнаружение из всего множества цепочек символов только единственной допустимой. В основе реализации конечного автомата на ЭВМ лежит таблица переходов, представленная в табл. 1.2. Ее столбцы помечены символами входного алфавита, строки – номерами состояний. Элементами таблицы являются но­мера новых состояний, в которые должен переходить ав­томат из текущего состояния при поступлении входных символов. В таблице переходов примера все пустые клет­ки должны быть заполнены номером 7 (для наглядности он опущен). Процедурная часть программы распознава­теля должна обеспечивать поиск столбца, соответствую­щего очередному входному символу, и «передвигать» указатель на строку таблицы, отвечающую новому со­стоянию.

Работа автомата начинается с некоторого исходного состояния (помеченного номером 0). Появление на вхо­де автомата символа С переводит его в состояние 1, лю­бой другой символ (за исключением ¿) вызовет переход автомата в состояние 7, откуда есть выход только по символу ¿ конца строки. Таким образом, любая цепочка символов, не начинающаяся с символа С, будет распознавателем отвергнута. Из состояния 1 допускающим бу­дет только переход в состояние 2 для символа Т, из со­стояния 2 – в состояние 3 для символа О. Работа распознавателя завершается обработкой символа ¿. В табл. 1.2 для состояний автомата 1–4 справа от таблицы записаны подцепочки символов, при­водящие в каждое из этих состояний.

Таблица 1.2.

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

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

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

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

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

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

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