Книга
← К списку книгЗагрузка разделов…
активнаАктивные записи участвуют в каталоге и синках. Неактивная книга скрыта, но не удалена из базы.
Книга
такой системы выбираются как определенные выше элементарные преобразования, так и составные преобразования, полученные в результате- объединении тех элементарных преобразований, области значений которых попарно не пересекаются. В результате минимизаций набор микроопераций машины, вообще говоря, изменяется (хотя и остается в пределах ограниченных фиксированной максимальной сложностью).
Дальнейшее уточнение рассматриваемой проблемы состоит в том* что наряду с эквивалентными преобразованиями в полугруппе для упрощения микропрограмм можно применять ряд дополнительных преобразований. Прежде всего, на практике смысл эквивалентных преобразований микропрограмм состоит не в абсолютной тождественности соответствующих им операций (преобразований многорегистрового устройства). Важно, чтобы совпали выходные сигналы (обычно векторные), полученные в результате выполнения последовательностей микроопераций, составляющих рассматриваемые микропрограммы. Иными словами, допускаются взаимные замены микропрограмм, представляющихся одним и тем же заключительным выходным сигналом операционного устройства.
Вторая дополнительная возможность минимизации получается при варьировании множества выходных сигналов операционного устройства. На языке микропрограмм это означает введение новых распознавателей и ^обуславливаемых ими так называемых внутренних микроопераций [2, 3]. Наконец, возможна постановка задачи, учитывающая не только длину микропрограммы, но и сложность применяемых для ее реализации микроопераций. При этом необходимо пользоваться в качестве универсального критерия оптимальности критерием цены эффективного быстродействия машины [2].
Одна из типичных формализованных схем, которая возникает из задачи оптимизации микропрограмм работы операционного устройства* может быть описана следующим образом. Дана полугруппа F с конечным числом образующих /1? /2, ..., /п и с конечным числом определяющих соотношений. Каждому подмножеству множества М всех образующих полугруппы сопоставляется неотрицательное вещественное число т (Р^ — мера этого множества. Эта мера не обладает, вообще говоря, свойством аддитивности, но возрастает при любом расширении множества.
Далее задается конечное число к подмножеств Rv R^ .... Rh элементов (вообще говоря, не образующих) рассматриваемой полугруппы и система из к положительных вещественных чисел аХ1 а21 ..., а^, удовлетворяющих соотношению сц + #2 + ••• + ^ = 1. Рассматриваются различные системы произведений РуР^-Рк-» образующих полугруппы* такие, что для любого t = 1, 2, ....к Pi $ R^ Мерой каждой такой системы назовем меру множества всех тех образующих, которые входят хотя бы к
в одно из произведений pvp2...pk, а ее весом — число V a^l кРгУ гДе ^ ^Pt) — число сомножителей в произведении р^ (длина слова р*).
Требуется, пользуясь системой определяющих соотношений, найти такую систему произведений рхр2...р^, для которой произведение меры на вес было бы минимальным.
Каждое из множеств R^ задается обычно как множество всех элементов х полугруппы F, которые удовлетворяют соотношению xsi = г^ где (si, ri) — фиксированная (для данного О пара элементов полугруппы F <1 = 1, 2, ..., к).
Вторая проблема, возникающая при оптимизации логической структуры машины,— это задача уменьшения числа регистров или числа со- 188
ставляющих их элементов. Обычно она ставится применительно к реальным условиям, когда все рассматриваемые регистры предполагаются конечными. Кроме того, в реальных условиях операционное устройство настраивается на выполнение вполне определенного числа различных микропрограмм, которым снабжает его устройство управления. В таком случае, применительно к каждому регистру или даже к каждому элементу, можно составить диаграмму их занятости, отметив те участки микропрограмм, на протяжении которых данный регистр (или элемент) используется либо для выполнения операций, либо для хранения информации, используемой следующими микрооперациями. В остальных случаях состояние регистра или элемента может быть любым.
Пусть Nt — максимальное число элементов операционного устрой* ства, задействованных в указанном выше смысле при выполнении какой- то микрооперации, a N — общее число элементов этого устройства. Если NT < N1 то, вводя операции пересылки информации от одних элементов к другим, можно сделать ряд элементов излишним и, следовательно, исключить их из рассматриваемого устройства. Наконец, если какой-либо регистр используется для переноса информации (без ее изменения) сквозь достаточно длинные участки микропрограммы, то можно отсылать эту информацию для хранения в одно из запоминающих устройств, вводя для этой цели дополнительные участки. Возникающие здесь задачи, как показал ученик автора А. И. Никитин, формализуются в терминах целочисленного линейного программирования и могут успешно решаться на электронных вычислительных машинах, приводя к большой экономии оборудования.
Третья важная проблема — это проблема минимизации устройства управления. Устройство управления представляет собой конечный автомат с относительно небольшим числом состояний, равным суммарному числу микроопераций во всех микропрограммах. Поэтому для его минимизации можно использовать обычные методы абстрактной теории автоматов [3]. Однако этим проблема еще далеко не исчерпывается, поскольку остается очень трудная задача минимизации функций переходов и выходов автомата.
В классической схеме микропрограммирования [4] функции переходов и выходов строятся фактически наименее экономным способом — путем помещения в постоянную память для каждого состояния автомата его следующего состояния (зависящего или не зависящего от входа) и соответствующего выходного сигнала. Можно, однако, существенно сократить память, поместив в нее только коды попарно-различных выходных сигналов и коды следующих состояний в случае, когда в микропрограмме имеет место скачок. При этом изменяется (в сторону упрощения) дешифратор, открывающий доступ в требуемые ячейки постоянной памяти. В частности, все состояния, которым соответствует один и тот же выходной сигнал, должны генерировать один и тот же сигнал на выходе дешифратора.
Возникает задача выбора кодов для состояния автомата и выполнения эквивалентных преобразований микропрограмм таким образом, чтобы максимально упростить дешифратор. В случае двоичного кодирования для этого нужно, очевидно, чтобы коды состояний, которым соответствует один и тот же выходной сигнал, были бы возможно более близкими друг к другу (в смысле естественной метрики на n-мерном кубе). Второй дешифратор должен выделять те состояния, которым соответствуют прыжки в микропрограмме, причем состояниям, из которых прыжки
совершаются в одни и те же места, должен соответствовать один и тот же выходной сигнал дешифратора. Что же касается переходов при отсутствии скачков (на линейных участках микропрограмм), то они должны выполняться на регистре микроопераций с помощью той или иной фиксированной схемы, осуществляющей пересчет состояний. В качестве таких схем могут употребляться схемы счетчиков, сдвиговых регистров или промежуточные между ними схемы.
При практическом решении указанных задач большую помощь оказывает предварительно проведенная ступенчатая организация микропрограмм. Тогда в микропрограммах верхних ступеней могут использоваться сложные микрооперации, представляющие собой целые микропрограммы (или их части) из более низких ступеней. Как и в случае обычного программирования, уход из микропрограммы более высокого уровня на подмикропрограмму более низкого требует организации хранения кода того состояния (в основной микропрограмме), к которому следует перейти после выполнения подмикропрограммы. Возникает задача экономной организации подобного хранения.
Решить указанную задачу возможно двумя способами. Первый можно применять в случае наличия свободных (на время выполнения подмикропрограммы) регистров в операционном устройстве. Он заключается в том, что свободные регистры организуются в магазинную память (с помощью поперечного сдвига с регистра на регистр), а код состояния, к которому необходимо возвратиться, засылается в эту память и возвращается в необходимый момент на регистр микроопераций. Второй способ состоит в применении сокращенных кодов, достаточных для дешифрования полного состояния. В этом случае задача решается совместно с синтезом дешифратора, реализующего функцию переходов в устройстве управления. ~
Еще одна проблема, возникающая при синтезе электронных вычислительных машин, заключается в распознавании микропрограммы, на которую должно быть выведено устройство управления после выборки из запоминающего устройства соответствующего командного слова или последовательности командных слов, кодирующих ту или иную операцию основной программы, помещенной в памяти машины. На первом этапе развития электронной вычислительной техники такая проблема не возникала ввиду того, что командные слова совпадали с кодом соответствующего начального состояния в устройстве управления. Поэтому достаточно было простой передачи считанного командного слова (кода операции) в устройство управления.
Но по мере усложнения внутреннего языка машины положение существенно меняется. В этом случае оказывается целесообразным выделить еще одно устройство машины — распознающий автомат. Его задача — воспринимать последовательности командных слов и переводить их в коды начальных состояний соответствующих микропрограмм. Если допустить возможность вариаций в языке программирования, то задача сведется к представлению некоторого события в автомате. В отличие от использования трансляторов, в случае распознающего автомата кажущееся усложнение задачи (за счет допущения вариаций) может не только не усложнить, но даже упростить автомат. Необходим лишь рациональный выбор соответствующих вариаций.
Формальная постановка задачи состоит в следующем: в полугруппе входных слов автомата выделено конечное число слов pv р^ ...^ рп, которые необходимо представить различными состояниями автомата. Требу- 190
ется включить эти слова в попарно непересекающиеся события рг, р^ ..., рп. так, чтобы автомат, представляющий полученные события, имел минимальное число состояний. Метод решения этой задачи — синтез частичного автомата, представляющий заданные слова и их желательные модификации, и последующая минимизация полученного автомата одним из известных методов [5].
СПИСОК ЛИТЕРАТУРЫ'
Evey R. J. The theory and application of pushdown store machines//The comput. Lab. Harvard Report.— 1963.— n. 3, F — 10.
Глушков В. M. Введение в кибернетику.— Киев, 1964.
Глушков В. М. О применении абстрактной теории автоматов для минимизации микропрограмм//Изв. АН СССР. Техническая кибернетика.— 1964.— 1.— С. 3—8.
Wilkes М. V., Stringer J. В. Microprogramming and the design of the control cirquits in an electronic digital computer // Proc. Cambridge Phil. Soc.— 1953.— 49, N 2.
Глушков В, M. Синтез цифровых автоматов.— М.} 1962.
РАЗДЕЛ 3
ТЕОРИЯ ДИСКРЕТНЫХ ПРЕОБРАЗОВАТЕЛЕЙ, ВЫЧИСЛИТЕЛЬНЫХ МАШИН И ИХ МАТЕМАТИЧЕСКОГО ОБЕСПЕЧЕНИЯ
ОБ ОДНОМ МЕТОДЕ АВТОМАТИЗАЦИИ ПРОГРАММИРОВАНИЯ
[Проблемы кибернетики.— 1959.—№ 2]
Процесс решения любой научной или инженернотехнической задачи, сведенной к задаче вычислительной математики, состоит из двух основных этапов. Первый (подготовительный) заключается в выборе метода решения задачи и схемы счета, второй — в производстве собственно вычислений.
Современные электронные вычислительные машины -позволяют полностью автоматизировать второй, собственно вычислительный этап, подняв производительность труда (по сравнению с ручным счетом) на этом этапе в десятки тысяч раз. Вместе с тем требования к подготовительному этапу с введением автоматизированных машинных расчетов не только не понизились, а, наоборот, возросли. Причину нетрудно понять, если вспомнить, что набор основных элементарных операций, которыми располагает машина, весьма ограничен.
Задача математика, разрабатывающего программу вычислений на машине, заключается в том, чтобы расчленить предстоящие вычисления на отдельные элементарные операции. Более того, в отличие от человека- вычислителя машина требует также указаний и относительно того, где будут храниться те или иные величины, например, результаты промежуточных вычислений. Поэтому выдача задания машине является гораздо более трудоемким делом, чем составление указаний вычислителем при ручном счете.
Положение может быть несколько облегчено за счет создания библиотек стандартных подпрограмм для тех или иных часто встречающихся комбинаций элементарных операций. Однако даже при этом условии подготовительный этап в случае использования машины остается значительно более трудоемким по сравнению с этим этапом при ручном счете.
Из сказанного ясно, что пути дальнейшего увеличения производительности труда в области научных и инженерно-технических расчетов заключаются не только и даже не столько в дальнейшем росте скорости работы электронных вычислительных машин, сколько в автоматизации процесса постановки задач на них, в автоматизации процесса программирования.
Значительным событием в развитии теории автоматического программирования явился предложенный в 1953 г. А. А. Ляпуновым операторный метод и созданные в 1954—1955 г. на его основе универсальные программирующие программы. Их использование значительно облегчает труд программистов и позволяет приблизить трудоемкость подготовки машинного решения задачи и трудоемкости подготовки соответствующего задания для вычислителей. Однако полной автоматизации программирования при этом не достигается, ибо наиболее квалифицированная часть
работы, включающая выбор метода решения задачи и разработку общего плана вычислений (схемы программы), должна выполняться человеком.
Между тем процесс автоматизации программирования принципиально возможно довести до его логического конца — полного уничтожения подготовительного математического этапа если не для всех, то, по крайней мере, для огромного большинства задач. Точнее говоря, можно выделить сколь угодно обширный класс «допустимых» задач, не требующих для своего решения на данном цифровом автомате никакой предварительной подготовки. Информация о задаче будет при этом иметь обычный для вычислительной математики вид и, главное, не будет зависеть от тех или иных особенностей данной машины.
Полной автоматизации программирования можно достичь на основе автоматизации процесса составления схем программ и последующего применения универсальной программирующей программы. Однако нетрудно понять, что подобный путь решения задачи не является наиболее целесообразным. Действительно, при полной автоматизации программирования информация о методах решения задач допустимого класса должна содержаться внутри машины или в автоматически присоединяемых к ней внешних устройствах. В большом числе случаев эта информация допускает достаточно экономную запись в таком виде, что некоторые части ее оказываются, по существу, готовыми подпрограммами. Ясно, что возвращаться от такой записи информации к схеме программы было бы нецелесообразно. Гораздо эффективнее для каждого метода вычислительной математики, применяющегося для решения задач из допустимого класса, разработать свою собственную упрощенную специализированную программирующую программу. Тем самым мы приходим к методу автоматизации программирования, который естественно назвать методом библиотеки программирующих программ. Сущность его заключается в следующем:
Выбирается некоторое (конечное) множество типов задач вычислительной математики, называемое классом допустимых задач. Элементами этого множества являются именно типы задач (состоящие, вообще говоря, из бесконечного множества частных задач), а не отдельные частные задачи.
Для каждого из выделенных типов задач составляется специализированная программирующая программа, использующая минимум входной информации, заданной притом в общепонятной естественной форме, не учитывающей специфику данной электронной вычислительной машины и даже специфику электронных цифровых машин вообще (информация должна быть, разумеется, закодированной, однако закодированной не каким-либо особым способом, а просто побуквенно).
Каждая из построенных программирующих программ должна предусматривать программирование какого-либо метода контроля вычислений и автоматическое включение его в основную (счетную) программу. Случаи, когда решение той или иной задачи данного типа невозможно ввиду недостаточной емкости внутреннего запоминающего устройства (ЗУ) машины, желательно выявлять с помощью специального блока программирующей программы в самом начале ее работы и сопровождать такое выявление остановом машины с соответствующей сигнализацией.
Различные специализированные программирующие программы могут содержать некоторые общие блоки, например блок арифметического оператора или блок экономии рабочих ячеек. Такие блоки естественно хранить в одном экземпляре (желательно в ЗУ с относительно малым временем ожидания), а в специализированных программирующих
программах предусматривать вызов их в нужное время. Набор этих блоков составит обычную библиотеку стандартных подпрограмм. Однако ввиду того, что сочетание блоков в программу производится автоматически, особое внимание должно быть уделено проблеме рационального кодирования входной и выходной информации стандартных подпрограмм с целью обеспечить возможность различных их сочетаний наипростейшим образом.
Наряду с программирующими программами для численных (арифметических) методов в библиотеке желательно иметь также программирующие программы и для некоторых неарифметических (точнее, не вполне арифметических) методов, например для аналитических методов решения дифференциальных уравнений. В качестве стандартных блоков в таких программах будут использоваться программы дифференцирования и интегрирования элементарных функций, программы преобразования и упрощения и т. п.
Объединение частных задач в один тип до известной степени произвольно. При таком объединении следует исходить прежде всего из общности методов решения соответствующих частных задач. Естественно, например, объединить в один тип задачи численного интегрирования, скажем, по методу Адамса — Штермера (на любом конечном интервале и с любым шагом) произвольной системы обыкновенных дифференциальных уравнений вида
-^- = А (ж, //1, • • •, у») А = 1, • • •, п),
где п — любое натуральное число, а /1? ..., fn — произвольные кусочноэлементарные функции (программирующая программа для такого типа задач составлена по заданию автора А. А. Стогнием).
Другой пример дает программирующая программа для решения по методу сеток задачи Дирихле для произвольного линейного эллиптического дифференциального уравнения с постоянными коэффициентами в пространстве любой размерности. Нужно предполагать при этом, что как граничные значения, так и уравнения (параметрические) границы (контура) заданы с помощью кусочно-элементарных функций.
Заметим, что объединение какого-либо множества частных задач в один тип не исключает, вообще говоря, объединения в новый тип задач какого-либо собственного подмножества этого множества. Поступать таким образом целесообразно во всех тех случаях, когда вновь выделяемый более узкий тип задач часто встречается на практике, а программирующая программа для него оказывается существенно более простой по сравнению с программирующей программой для охватывающего его более широкого типа задачи. Так, во втором из рассмотренных выше примеров целесообразно особо выделить случай уравнения Лапласа в пространстве двух и трех измерений.
На первом этапе автоматизации программирования можно ограничиться только библиотекой специализированных программирующих программ. Уже в этом случае для класса допустимых задач достигается более высокий уровень автоматизации программирования по сравнению с универсальной программирующей программой: отпадает необходимость в каждом отдельном случае составлять схему программы, таблицы заполнения памяти и т. п. Выбор метода (номера специализированной программирующей программы) и кодирование формул производится, правда, еще человеком, но и при этом условии подготовка задачи (из класса допусти-
мых задач) для машинного решения проще, чем подготовка той же задачи для ручного счета вычислителями средней квалификации.
Для задач, не являющихся допустимыми, должно, разумеется, применяться либо ручное программирование, либо универсальная программирующая программа. Впрочем, с наращиванием библиотеки программирующих программ такие «особые» случаи будут становиться все более и более редкими.
Заметим, что специализированные программирующие программы оказываются значительно более короткими, чем универсальная программирующая программа, что позволяет применять их в машинах с относительно малыми объемом запоминающих устройств. По мере готовности специализированных программирующих программ для тех или иных классов задач они сразу поступают в работу, не дожидаясь окончания заполнения библиотеки. Возможна также специализация машин или даже целых вычислительных центров на каких-либо определенных типах задач.
Наконец, важным достоинством метода библиотеки программирующих программ является относительная простота и очевидность путей дальнейшей автоматизации процесса подготовки задач на его основе: после того как библиотека программирующих программ сделается достаточно обширной, ее можно разбить на отделы и построить специальную программу выбора метода. Такая программа должна по закодированным словесным пояснениям во входной информации (например: «проинтегрировать систему обыкновенных дифференциальных уравнений») и по виду формул определять сначала отдел библиотеки, а затем, по специальной подпрограмме, относящейся к данному отделу, анализировать включенные в эту программу критерии, позволяющие отдать предпочтение тому или иному вычислительному методу (номеру специализированной программирующей программы). В случае отсутствия предпочтительного должен быть выбран первый пригодный для решения данной задачи метод. В конце работы программы выбора метода через специальное релейное устройство должно осуществляться автоматическое включение того из внешних накопителей, который содержит выбранную программирующую программу, и автоматический ввод первого блока этой программы в оперативную память машины.
Вопрос автоматизации кодирования входной информации также может быть решен с помощью особой читающей программы, позволяющей читать и (побуквенно) кодировать печатный и даже рукописный текст, проектирующийся, например, на экран кинескопа.
В случае реализации метода во всей его полноте машине достаточно будет «показать» лист бумаги с напечатанным на нем заданием, чтобы машина без дальнейшего вмешательства человека начала решать задачу и выдала через некоторое время ответ.
К ВОПРОСУ О МИНИМИЗАЦИИ МИКРОПРОГРАММ И СХЕМ АЛГОРИТМОВ
[Кибернетика.— 1966.— № 5]
Работа любой микропрограммы сводится к схеме взаимодействия двух автоматов А и В [1]. Первый из них, называемый операционным, представляет собой конечный или бесконечный автомат Мура, второй, называемый управляющим, есть конечный автомат Мили. Выходные сигналы (хь а2, ..., Хт) автомата А служат входными сигналами для автомата В, а выходные сигналы (микрооперации yv у^ --^Уп) автомата В — входными сигналами для автомата А.
Начальное состояние 60 автомата В представляется фиксированным, что же касается начального состояния автомата А, то оно может варьироваться в тех или иных пределах.
Взаимная связь в работе двух автоматов приводит к тому, что даже с учетом возможности выбора в качестве начального любого состояния автомата А на входе автомата В могут появляться, вообще говоря, не все мыслимые априори последовательности входных сигналов. Это обстоятельство дает, как легко видеть, дополнительные возможности для минимизации управляющего автомата В, а следовательно, и для представляемой этим автоматом микропрограммы.
Рассмотрим один из наиболее естественных путей реализации указанной возможности. С этой целью прежде всего отождествим выходные сигналы Хг автомата Мура А с множеством отмеченных этими сигналами состояний. Для любого сигнала Хг и любой микрооперации у, через х^ обозначим объединение всех тех множеств ж^, которые содержат состояния вида ау^ где а £ $г-
Для любого множества М = ^Хгх1 Хгг1 ..., хХк\ выходных сигналов автомата А через М^. обозначим объединение всех множеств Хгх1 уп ...t х^у^. Тем самым определен конечный автомат С без выходных сигналов с входным алфавитом, аналогичным автомату А, состояниями которого служат произвольные множества выходных сигналов этого последнего автомата. Построенный таким образом автомат С будем называть редукцией автомата А. Он однозначно определяется автоматом Айв случае его конечности может быть построен из него конструктивным образом.
При наличии автомата С построим автоматы D и F без выходных сигналов с множествами состояний, аналогичных автомату С. Входными сигналами автомата D будут служить всевозможные пары (xi, у^ выходных и входных сигналов автомата А, а входными сигналами автомата Р — любые множества таких пар. Для любого состояния d автомата D произведение d (Xi, у^ полагается равным х^у^ если ж £ d, и 0 в противном случае. Произведение dN, где N — любое множество пар (функция переходов в автомате F), определяется как объединение произведений dq для всех вар q^ входящих в N.
Вернемся теперь к рассмотрению управляющего автомата В. Для любой пары (6s, 6Г) состояний этого автомата обозначим через Bs множество всех пар (жг, у5У таких, что под действием входного сигнала х^ автомат В переходит из состояния 6S в состояние 6Г, выдавая при этом выходной сигнал У). Пусть каждое состояние к (к = 1, 2, ..., р) автомата В отмечено каким-либо множеством Мк выходных сигналов Хг автомата А. Определим новые отмечающие множества Мк по формулам
М'к = Мк и и М,В,к (к = 1, 2, .. . , Ру (1) г=Э
Переход от отметок Мк к отметкам Мк назовем итерацией отметок.
Построим последовательность систем отметок {М^} (J = 0,1, ...), полагая Мк = 0 для всех к ^ 1 и выбирая в качестве нулевой отметки начального (1-го) состояния множество М? всех тех выходных сигналов автомата Л, которые он выдает, находясь в любом из своих возможных начальных состояний. Переход от ^М^ к {Af{+1} определим как итерацию отметок. В силу определения итерации и конечности множества выходных сигналов Хг наша последовательность стабилизируется на некотором шаге (т. е. Мк совпадает с М{+1 для всех ку Обозначим полученные на последнем шаге этого процесса (стабилизированные) отметки через Мк ук = 1, ..., рУ Легко заметить, что для В имеет место следующее предложение.
При совместной работе с автоматом А на входе автомата В, находящегося в состоянии к, не может появиться ни один из тех сигналов х^ которые не входят в Мк. Из этого предложения очевидным образом вытекает следующее следствие.
Результат совместной работы операционного и управляющего автоматов не изменится, если в управляющем автомате В сделать неопределенными все переходы кх^ (с соответствующими им выходными сигналами), для которых входной сигнал Хг не входит в стабилизированное множество отметок Мк состояния к.
Для иллюстрации приведенных общих построений рассмотрим следующий пример.
Пусть управляющий автомат Мили В задан таблицами переходов и выходов:
1
2
3
1
2
3
2
2
3
Я1
Ух
У1
Уг
^2
1
3
1
ж2
У1
У^
Уз -
Предположим далее, что имеют место соотношения хгуг — х^ х^х = = х^ хгу2 = (я^, х2У х2у2 — ^и которые полностью определяют редукцию автомата В. Пусть, наконец, в начальный момент времени на вход автомата В может поступать лишь входной сигнал хг.
Теперь для автомата В запишем множества Вгк-
5ц = Ух21 у^у В12 = (,г17 угу 513 = 0;
52i = 0, В22 = (^1? У\У 523 = (.т2, У2У
53i = (ж2, у2у В32 = 01 533 = (^1? У2У
Взяв в качестве начальных отметок состояний множества Мл = = (•£]), М2 = 0t Мз = 0 и применив к ним преобразование итерации,
приходим последовательно к системам отметок:
М? = fo), Ml = (z2), Ml = 0;
М2 = (^), Ml = (я2), М2 = fo);
М3 = (а^), Ма = (я2), Мз = ^г, х2у,
Mi = t^), Ml = (х2), М^ = ^xv т^.
Ввиду совпадения отметок, полученных на 3-м и 4-м шагах, можем принять их за окончательную систему отметок: Мх = (ж!), М2 = (ж2), М3 = (я17 ж2).
Теперь, на основании предложения В, можем заменить автомат В частичным автоматом В'9 задаваемым следующими таблицами переходов и выходов:
123У1—Уъ—^2#2•123У1—Уъ—^2#2•|123
123
У1—Уъ
—^2#2•
123
У1—Уъ
—^2#2•
хг 2—3
х2 —31
В этом автомате, в отличие от автомата В, имеется пара совместимых состояний (состояния 1 и 2). После их объединения в одно придем к автомату С, имеющему только два состояния
| । 2 12
*1 12 2^ ух уа
■^ 2 1 х2 у2 у2 .
В известной работе Ю. И. Янова [2] построена теория равносильности логических схем алгоритмов. Нетрудно проверить, что рассматриваемая Ю. И. Яновым конструкция сводится, по существу, к рассмотренной выше схеме взаимодействия двух автоматов. При этом входными сигналами управляющего автомата В будут двоичные векторы (кортежи) значений логических переменных ри р2, ..., р^ а его выходными сигналами — операторы Ап А2, ..., Ап. Таблицы переходов и выходов автомата Рпредставляют схему алгоритма. Определенное же в 1.2] так называемое распределение сдвигов представляет собою не что иное, как способ задания редукции операционного автомата, причем редукции специального вида. А именно, если, например, оператор А может менять значения лишь логических переменных р1: р2 (т. е. имеется распределение сдвигов {Ах — — (Рп Ра) •••>})> то в языке данной работы это означает, что произведение любого из входных сигналов автомата В хг = (0, 0, сс3, ..., ay), х2 = = (0, 1, а3, ..., а&>, х^ = (1,0, а3, ..., а^^ х4 = (1,1, а3, ..., а^> на входной сигнал А равняется множеству (ж17 х21 ж3, х^. Наконец, начальное состояние отмечается множеством всех входных сигналов.
Пусть Вх и 52 — два управляющих автомата, соответствующих в описанном смысле схемам алгоритмов с общими операторами и логическими условиями. Действуя в соответствии с описанным выше приемом, преобразуем эти автоматы в частичные автоматы В\ и В2. Обозначим через Вг и Н2 события, представленные в частичных автоматах В\ и 52 множествами всех выходных сигналов, а через Р, и Qi — события, представленные в полных автоматах Вг и В2 выходным сигналом Ai (£ = 1, 2, ..., п\ Из [3] известно, что множества Rv R21 Pi, Qi регулярны. Равносильность схем алгоритмов в смысле Ю. И. Янова означает совпадение отображений.
индуцируемых автоматами Sx и 52 на множестве 8 = RT |J R^ последовательностей входных сигналов. Используя хорошо известную связь между отображениями и событиями, представимыми в автоматах [3], придем к следующему предложению.
Схемы алгоритмов, представляемые автоматами Bv и В^ тогда и только тогда равносильны, когда для всех г = 1, 2, ..., п имеют место соотношения: Pi п 8 = Qi Q 8.
Поскольку пересечение регулярных событий регулярно, а проверка равенства или неравенства двух регулярных событий выполняется конструктивно, то предложение 3 является автоматным аналогом результатов Ю. И. Янова о равносильности схем алгоритмов. Разумеется, рассматриваемые нами схемы могут иметь повторяющиеся операторы, т. е., иными словами, могут иметь место соотношения типа (22) из [2]. Аналогично могут быть получены и условия для частичной равносильности схем алгоритмов.
СПИСОК ЛИТЕРАТУРЫ
Глушков В. М. Теория автоматов и формальные преобразования микропрограмм // Кибернетика,— 1965,— № 5,— С. 1—9.
Янов Ю. И. О логических схемах алгоритмов И Пробл. кибернетики.— 1958.— № 1.— С. 75—127.
Глушков В. М. Абстрактная теория автоматов И Успехи матем. наук.— 1961,— 16, вып. 5.— С. 3—62.
ОБ ОПРЕДЕЛЯЮЩИХ СООТНОШЕНИЯХ В ДВУХСУММАТОРНОМ ОПЕРАЦИОННОМ УСТРОЙСТВЕ
[Кибернетика.— 1968.— № 1]
Обычно применяемые на практике операционные устройства ЭВМ параллельного действия обладают одним (параллельным) сумматором. Образующими элементами в соответствующей операторной алгебре [1] являются, помимо единственного оператора суммирования, операторы сдвига на регистрах, прибавления и вычитания единицы из содержимого этих регистров, операции установки регистров в нуль и, наконец, операции пересылки из одних регистров на другие. Некоторые из определяющих соотношений между такими образующими рассмотрены в [1].
В случае наличия нескольких переменных сумматоров положение усложняется. Наиболее сложный случай возникает тогда, когда регистры, на которых выполняются различные операции суммирования, переплетены между собой. Иными словами, результаты суммирования при одних операциях получаются на тех регистрах, на которых хранятся слагаемые при выполнении других операций, и наоборот. При простейшем двухрегистровом операционном устройстве соответствующие операции суммирования могут быть представлены в виде:
$1,2: ^2: = Ж1 + ж^ Ж1: = xv$2.1 • ^1 • == *^1 "4” *^2>^2 е === *^2е
Здесь через хг и х2 обозначены коды чисел, хранящихся соответственно в первом и во втором регистрах рассматриваемого операционного устройства. Ограничимся случаем, когда эти числа — целые, и поставим перед собой задачу найти полную систему определяющих в полугруппе, порожденной элементарными операциями s12, s^1, s21, s^1. Нетрудно видеть, что эта полугруппа G будет в действительности группой с двумя образующими элементами 512 и 521. Изменив соответственно постановку задачи, будем искать полную систему определяющих соотношений для образующих $12 и $21 в группе G.
Группа G изоморфна, очевидно, группе матриц, порождаемых матрицами
Первая из этих матриц соответствует при этом оператору S12, а вторая — оператору 521. Известно [2], что матрицы А и С = |® q| порождают группу U2 всех целочисленных унимодулярпых (с единичным определителем) матриц второго порядка. Вместе с тем легко проверить, что С = А^ВА”^. Таким образом, матрицы А и В также составляют систему образующих для группы U2.
В работе [2] (стр. 278—281) доказано, что фактор-группа группы U^ по подгруппе Z второго порядка, состоящей из матриц Е “ |g Jl (единица группы) и Е = | ^ ®|, разлагается в свободное произведение циклических групп второго и третьего порядка, порожденных смежными классами Z • С и Z . D, где D = А • С — В • Л-1.
Легко проверить, что С2 = —Е и D3 = — Е. Из всего сказанного выше вытекает, что для системы образующих {С, D} группы U^ можно записать полную систему определяющих соотношений: С2 = 7)3; С4 = Е.
В самом деле, отсюда непосредственно вытекает, что D6 = Е и элемент С2 перестановочен с элементом D, а элемент D3 — с элементом С. Но тогда любое произведение, составленное из элементов С^х и Z^1 (повторенных любое конечное число раз), с помощью этих соотношений можно записать: D3nC2m d^C^D^C^D^C^D^C1^, где 0 < Ц < 3, О < кг < 3 (I = 1, 2, ..., г); 0 ^ к0 < 3, 0 < Zr+1 < 3.
Что же касается произведения В3пС2т, то в силу соотношений С4 = = Е и DQ = Е оно приводится к одному из следующих видов: Е, С2, В3, В3, С2. Однако С2 = D3, a В3С2 = В3В3 = D^ = Е. Таким образом, любое произведение элементов В и С с помощью соотношений С2 — В3 и С4 — Е приводится либо к ЕР, либо к С2Р, где Р = D^olv^XQi2^k2 ... ... С1тВНтС1т^ с приведенными выше неравенствами для показателей. Если два произведения Q и R после приведения к описанному виду не будут тождественны, то они представляют собой различные элементы группы U2. Действительно, если Q = ЕР и R = С2Р, то, поскольку С2 = —Е, имеем Q = Р =^ R = — Р. Если же для произведений Q и R окажутся различными соответствующие приведенные произведения Р, то смежные классы ZQ и ZR в фактор-группе U^iZ обязательно различны (это следует непосредственно из определения свободного произведения). Тем самым наше утверждение о полноте системы соотношений С2 = В3, С4 = Е доказано.
Применительно к исходной группе G и образующим элементам 512 и S21 запишем эту систему соотношений следующим образом:
(STsS^? = (ЗД2)3; (ST^S?^ = Е.
Это и будет искомая система определяющих соотношений для группы преобразований в простейшем двухсумматорном операционном устройстве.
СПИСОК ЛИТЕРАТУРЫ
Глушков В. М. Теория автоматов и формальные преобразования микропрограмм И Кибернетика.— 1965.— № 5.
Курош Л. Г. Теория групп.— М. : ОГИЗ, 1944.
О ПОЛНОТЕ СИСТЕМ ОПЕРАЦИЙ
В ЭЛЕКТРОННЫХ ВЫЧИСЛИТЕЛЬНЫХ МАШИНАХ
[Кибернетика.— 1968.— № 2]
Понятие полноты систем операций в вычислительных машинах определялось до сих пор лишь в абстрактно-алгоритмическом плане [1]. Иными словами, считалось, что система операций ЭВМ полна, если с ее помощью можно моделировать любой алгоритм преобразования информации при надлежащем кодировании этой информации. В то же время в ряде случаев (особенно, когда вместо операций рассматриваются микрооперации) представляет интерес другой подход к понятию полноты системы операций машины, который естественно назвать абстрактно-автоматным.
Этот подход основывается на предложенной автором [2] схеме преобразования информации как системы взаимодействия двух автоматов, (рис. 1). Преобразуемая информация отождествляется в этой схеме с состояниями одного из взаимодействующих автоматов В^ называемого операционным. Выходные сигналы у^ другого автомата А, называемого управляющим автоматом, отождествляются с преобразованиями на множестве М состояний операционного автомата, т. е. отображениями множества М в себя. Выходные сигналы х^ автомата В (являющиеся в то же время входными сигналами для автомата Л) отождествляются с некоторыми подмножествами состояний автомата В. Обычным способом задания этих подмножеств является способ, основанный на определении строчки логических условий (а17 а2, ..., ап) на множестве М, которое в дальнейшем будем называть информационным множеством. Любое конкретное значение этой строчки условий представляет собою некоторый выходной сигнал х^ автомата В. Предполагается, что его выходные сигналы не зависят от входных и являются функцией лишь состояний этого автомата, В таком случае каждому выходному сигналу х^ автомата В отвечает множество порождающих этот сигнал состояний.
Управляющий автомат Л (предполагаемый конечным) естественно задавать программой его работы. При этом его состояния отождествляются с отдельными командами, из которых состоит программа. Каждая же команда включает в себя в общем случае две операции: элементарную операцию преобразования информации (состояния операционного автомата), задаваемую одним из выходных сигналов уг автомата Л, и операцию управления, задающую переход к следующей команде,— эта операция определяется входным сигналом х^ управляющего автомата А и его функцией переходов а' — f (х, а). Одна из команд соответствует заключительному состоянию автомата А и вызывает окончание работы пары автоматов Л, В.
Пусть теперь фиксировано произвольное информационное множество М, а также множество Р элементарных операций у^ (отображений множества М в себя) и Q элементарных логических условий aj. Тем самым за-
УхРис. 1.УхРис. 1.дается операционный автомат У, входными сигналами которого служат операции ^г, а выходные сигналы хк отс ж- дествляются с различными значениями
У
х
Рис. 1.
У
х
Рис. 1.
строки логических условий aj.
Будем говорить, что множество Р элементарных операций полно относительно множества Q элементарных логических условий и некоторого множества R отображений М в себя, если для любого отображения / из 7? можно построить управляющий автомат А с конечным числом состояний, который, взаимодействуя с автоматом В по описанной выше схеме, осуществит преобразование / (для любого начального состояния автомата 5) после первого достижения автоматом А заключительного состояния.
Иными словами, полнота системы операций Р относительно множества условий и множества операций Q означает возможность построения программы для любого преобразования заданного информационного множества, принадлежащего данному классу 7?.
Заметим, что требование конечности относится только к числу состояний автомата А. Что же касается множеств Р и Q, то они могут быть и бесконечными. Целесообразно рассматривать два основных вида полноты: всеобщую, когда множество R охватывает все отображения множества М в себя, и конструктивную, когда R составляется лишь из конструктивно задаваемых отображений (с помощью рекурсивных функций). В случае конечности информационного множества М оба эти понятия совпадают.
Наконец, будем говорить, что система элементарных операций Р абсолютно полна, если она обладает свойством всеобщей полноты по отношению к любому множеству логических условий, в том числе и к пустому.
Рассмотрим в качестве примера одну важную абсолютно полную систему операций для конечного информационного множества М. Этот
пример очень важен для случая, когда в качестве операционного автомата В рассматривается арифметическое устройство ЭВМ, а в качестве автомата А — устройство управления этой машины. Разумеется, интерес представляет лишь тот случай, когда число элементов информационного
множества не меньше двух.
Занумеровав элементы информационного множества М последовательными натуральными числами 1, 2, ..., N (N ^ 2), сводим поставленную задачу к известной алгебраической задаче нахождения систем обра
зующих элементов в подгруппе всех подстановок
/12 ... N\
где kv к21 ..., kN — числа от 1 до N (не обязательно различные). Обозначим через уг циклическую подстановку
/1 2 3 ... N — 1 7V\
(2 3 4 N1
через уг — транспозицию
"/1 2 3 4 N\
\2 1 3 4 ... N;
т. е. перестановку лишь двух первых символов 1 и 2, и через у3 — подстановку
1 2 3 4 ... ДГ\
2 2 3 4... Nj
Нетрудно увидеть, что система Р, состоящая из элементарных операций yv у2, у3, обладает свойством абсолютной полноты.
Действительно, во-первых, (W — 1)-я степень подстановки уг представляет собою обратную подстановку уТ^- Во-вторых, транспозиция у2 = = (1,2) — перестановка символов 1 и 2 — при умножении слева на у”^к—1\ а справа — на ук~ дает транспозицию (Л, к + 1), которую обозначим через zh Ч Далее, zp_\ ... z3z2y2z2z3 ... zp_\ = (1, р) (2 ^ р ^ N\ т. е. имеем возможность получить любую транспозицию (1, р) (для 2 ^ р ^ vV), которую обозначим через ир. Теперь очевидно, что y'x^^UpyV1 = = (г, Р Н- г — 1) (г ^^ 1). 1ем самым доказана возможность с помощью преобразований yv и у2 построить любую транспозицию двух символов из множества (1, 2, ..., NY Поскольку же любая взаимно однозначная подстановка разлагается в произведение транспозиций [3], то операции ут и у2 составляют полную систему относительно всех взаимно однозначных отображений множества М в себя.
Обозначим через игл ^ ^ &) подстановку, переводящую г в к и сохраняющую неизменными все остальные символы. Легко проверить, что Vtk = (1, 0 (2, к) у3 (2, к) (1, Z) (если г =/= 2 или к ^= 1 и v^ i = (1,2) Уз (1,2)). *
Таким образом, все подстановки щ^ выражаются через исходные подстановки yv у21 у3.
Пусть теперь w — произвольная подстановка N символов. Обозначим через t число различных символов в области значений этой подстановки. Если t — N, то w взаимно однозначна и, следовательно, выразима через базовые подстановки yv у2, у3. Предположим теперь, что t < N и что уже доказана выразимость через уХ1 у21 Уз любой подстановки, у которой число символов в области значений больше, чем t. Обозначим через kv к21 ...^kt все символы из области значений подстановки w. Поскольку t < N, то найдется такой символ, скажем kv в который подстановка w переводит два различных символа р и q. Пусть к0 — какой-нибудь символ из множества {1, 2, ..., NY отличный от всех ki (I = 1, 2, ..., tY Обозначим через w^ подстановку, отличающуюся от w только тем, что она переводит символ р не в kv а в к0. Область значений этой подстановки состоит из t + 1 символов. Согласно нашему предположению, это означает, что можно выразить через базовые подстановки уъ у21 у3. Но, как легко заметить, w = woVkOlkt- Тем самым доказана выразимость через базовые подстановки также и подстановки w. По индукции (вниз по £) мы доказали тем самым возможность выразить через базовые — любую (не обязательно взаимно однозначную) подстановку.
Что же представляет собой найденная абсолютно полная система операций с точки зрения конструктора ЭВМ? Разумеется, здесь возможны различные интерпретации за счет изменения способа нумерации состояний операционного автомата. Наиболее естественная интерпретация получается, если все запоминающие элементы (триггеры) операционного (арифметического устройства) ЭВМ мысленно объединить в один длинный регистр, а номер состояния задавать хранящимся на этом регистре двоичным кодом. В таком случае операция yY представляет собой не что иное, как операцию циклического прибавления единицы к содержимому этого
регистра. Если п — число двоичных разрядов в регистре, то при прибавлении единицы к коду 2П — 1 на регистре должен установиться нулевой код.
Операция у2 не изменяет содержимого регистра, за исключением двух случаев: код ООО...О она переводит в код ООО...01, и наоборот. Наконец, операция у3 преобразует нулевой код в код ООО...01, а остальные (в том числе и код ООО...01) — не изменяет.
Из этих трех операций можно построить микропрограммы любых операций на заданном операционном устройстве без применения каких- либо дополнительных логических условий и условных переходов по ним. Разумеется, такие микропрограммы могут оказаться чрезмерно длинными и не пригодными для практической реализации. Введение новых операций и логических условий позволяет существенно сократить записи интересующих конструктора микропрограмм. Поэтому представляет интерес исследование полноты системы операций с различного рода ограничениями,, накладываемыми на длины минимальных микропрограмм, которые реализуют преобразования заданного класса R.
Произведем оценку длины микропрограмм для абсолютно полной системы операций (pF1, Ун У^ Уз^ Тогда из приведенного выше доказательства следует, что транспозиции z^ = (к, к + 1) (к ^ N — 1) представляются микропрограммами длины не большей, чем 2к — 1 < 2N — 1.
Для транспозиций ир = (1, р) (р ^ N) длина микропрограмм не пре- /р—1 \
восходит 2 2 (2г — 1) + 1) = 2р (р — 2) + 1 = 2 (р — I)2 — 1 < \ г=1 /
< 2 (N — I)2, а для (г, р + г — 1) (р ^ 2, г *^ 1) эта длина не превосходит (2г — 2) + 2р (р — 2) + 1 = 2р (р — 2) + 2г — 1. Заметим, что любая транспозиция (пг, п) при п — т ^ 2, исключая транспозиции Up, может быть представлена в виде (г, р + г —- 1) при дополнительных условиях г ^ W — 1, р + г ^ N + 1, р ^ N. Проверка в граничных точках приводит к наихудшей оценке 2 (N — I)2 — 1. Во всяком случае это означает, что длина микропрограммы для любой транспозиции (включая zk и ир) меньше, чем 2 (N — I)2.
В то же время, как известно из теории групп, всякая взаимно однозначная подстановка N символов разлагается в произведение не более N — 1 транспозиций. Таким образом, в системе базовых преобразований {Pi, pF1, У^ всякая взаимно однозначная подстановка может быть представлена микропрограммой длины не большей, чем 2 (N — I)3
Переходя к случаю не взаимно однозначных подстановок, прежде всего заметим, что длина микропрограммы для подстановок вида Рг;_ не превосходит 8 (N — I)2 + 1, ибо они получаются умножением подстановки Уз не более чем на 4 транспозиции. Из приведенного выше доказательства по индукции вытекает, что любая не взаимно однозначная подстановка $ получается в виде произведения некоторой взаимно однозначной подстановки и не более чемТУ — 1 подстановок вида и^к* Это приводит нас к следующей оценке для длины I (s) микропрограммы подстановки s:
I (S) ^ (N — 1) [8 (N— I)2 + 1] + 2 (N — I)3 < 107V3.
Таким образом, в выбранной системе базовых операций (pF1, Pi, р2, р3} любая (всюду определенная) операция может быть представлена микропрограммой длины не большей, чем 10 N3.
Напомним, что N — число различных элементов в информационном множестве М или, что то же самое, число состояний в операционном автомате В. Если обозначить через п число двоичных запоминающих элементов (триггеров) в операционном автомате (например, в арифметическом устройстве ЭВМ), то N = 2П и выведенная выше оценка для длин микропрограмм представляется в виде 10 • 23п. Поскольку число п в арифметических устройствах ЭВМ достаточно велико (в случае^ параллельных арифметических устройств оно исчисляется сотнями), то эта оценка приводит к чрезвычайно большим величинам.
Не следует забывать, однако, что речь идет об оценке для микропрограммы любых однозначных (но не обязательно взаимно однозначных) вполне определенных операций па информационном множестве мощности N. Число таких операций равно Nn, что в нашем случае приводит к результату, равному 2п2П. Число же теоретически различных микропрограмм длины Л: из 4 операций (без операций перехода) равно 4к. Для 10 • 23п это приводит к результату 220 23п. Учитывая такое обстоятельство, можно сказать, что найденная нами оценка не столь уж плоха. Тем не менее представляет определенный интерес задача дальнейшего улучшения этой оценки. Из только что приведенного соображения о количестве различных операций вытекает, что во всяком случае эта оценка не может быть лучше, чем cN log N. (Возможность использования микропрограмм длины меньшей, чем к, вполне компенсируется наличием соотношений между базовыми преобразованиями). Разумеется, совершенно не обязательно связывать свой выбор только с рассмотренной выше системой образующих (?/Г\ Ун Уъ, Уз} конечной симметрической полугруппы степени N. С точки зрения проблем, затронутых в настоящей статье, представляет интерес следующая абстрактно-алгебраическая задача.
Пусть в симметрической полугруппе Pn степени N выбрана некоторая система образующих 8 = {gx, g^ ..., gm\. Для каждого элемента р из Pn обозначим через I (р) длину одного из кратчайших выражений элемента р через образующие элементы. Пусть I — максимальная из длин I (рУ когда р пробегает все значения элементов из Pn. Мерой информационной избыточности системы 8 будем считать произведение числа I на число т элементов в этой системе.
В настоящей статье найдена система образующих в Pn с мерой информационной избыточности 10 N3 X 4 = 407V3. Алгебраическая задача, о которой идет речь, состоит в нахождении систем образующих симметрической полугруппы, обладающей минимальной информационной избыточностью.
Разумеется, нужно иметь в виду, что конструкторов ЭВМ интересуют не произвольные, а некоторые вполне определенные преобразования информационного множества (например, арифметические операции над кодами чисел, составляющими информационное множество). Эти операции должны особенно просто выражаться через выбранную систему образующих. С другой стороны, нужно заботиться о том, чтобы базовые подстановки, входящие в выбранную систему образующих, были достаточно просто реализуемы с технической точки зрения. Предложенная выше система ^уТ1, у^ у^ у^\ в полной мере удовлетворяет второму и в значительной степени — первому из этих условий.
В самом деле, чтобы реализовать выбранную нами систему образующих, достаточно, очевидно, иметь составленный из всех регистров опера- 208
ционного устройства ЭВМ реверсивный счетчик (это дает непосредственную реализацию операций уг и г/Г1) и уметь отличать какой-нибудь из запоминаемых на этом устройстве кодов, например нулевой, от всех остальных кодов. Иными словами, надо организовать проверку логического условия а, истинного тогда и только тогда, когда содержимое всех регистров операционного устройства равно нулю.
В таком случае, обозначая через I тождественное преобразование, не изменяющее содержимое регистров, легко записать микропрограммы операций. Для г/ это будет следующая: если а, то у^ иначе — е. Для Уз микропрограмма составляется из двух операторов ST: первый из них (5): если а, то yt и конец, иначе — yj"1; второй (Т): если а, то 5, иначе —yv ~
Попутно мы доказали предположение о том, что система операций {У1, уГ1} обладает свойством всеобщей полноты относительно логического условия а.
Поскольку уГ1 = уГ~\ то свойством всеобщей полноты по отношению к логическому условию а обладает система, состоящая из одной единственной операции yv
Таким образом, чтобы построить универсальное операционное устройство (на котором можно выполнить любое преобразование хранящейся в нем информации), имеющее заданное число п двоичных запоминающих элементов, достаточно организовать эти элементы в один общий регистр 7? и построить лишь две логические схемы: схему, превращающую регистр 7? в счетчик (с переходом от кода 2П — 1 снова к коду 0), и схему,, осуществляющую проверку на равенство нулю содержимого этого регистра.
Аналогичный результат мы будем иметь по отношению к любым запоминающим элементам с конечным числом состояний. Не обязательно,, чтобы счетчик пробегал все коды в естественной последовательности (от Одо 2П — I)2. Важно лишь, чтобы за 2П тактов перебирались все коды (без повторений) на данном регистре 7?. Не обязательно осуществлять проверку именно нулевого кода. Им может быть любой другой (но обязательно единственный) код.
Нетрудно проверить также, что если операционное устройство состоит из конечного числа регистров, каждый из которых превращен в счетчик и на нем возможна проверка нулевого (или любого другого) кода, то такое операционное устройство тоже будет обладать свойством всеобщей полноты. Иными словами, комбинируя операции счета на регистрах с проверкой равенства нулю их содержимого, можно построить микропрограммный автомат (управляющее устройство), выполняющий любую наперед заданную систему операций.
Разумеется, при этом нет никакой гарантии, что построенный автомат будет реализовывать требуемые операции, в том числе даже операцию сложения кодов на двух регистрах сколько-нибудь экономным образом. Для получения достаточно эффективных (в практическом плане) систем базовых операций и логических условий эти системы существенно расширяются за счет внедрения новых операций и условий.
В то же время системы элементарных операций, обычно реализуемых
в арифметических устройствах современных ЭВМ, как правило, не обладают свойством всеобщей полноты. Они полны лишь в некотором классе преобразований, и чаще всего полнота имеет место только на части операционного устройства. Остальная же часть этого устройства используется в качестве буфера для хранения промежуточных результатов преобразований, выполняемых в основной части.
СПИСОК ЛИТЕРАТУРЫ
Глушков В. М. Введение в кибернетику.— Киев : Наук, думка, 1964.
Глушков В. М. Теория автоматов и формальные преобразования микропрограмм И Кибернетика.— 1965.— № 5.
Холл М. Теория групп.— М. : ИЛ, 1962»
ОЦЕНКА ЭФФЕКТИВНОСТИ СЛОЖНЫХ СИСТЕМ И ОРГАНИЗАЦИИ ВЫЧИСЛИТЕЛЬНЫХ ПРОЦЕССОВ
[Математическое обеспечение ЭЦВМ.— Киев, 1972]
Для того чтобы говорить об эффективности вычислительных систем, прежде всего необходимо научиться измерять их производительность .
В настоящее время существуют разные методы оценки производительности и сложности вычислительных алгоритмов. Они основываются, главным образом, на разложении алгоритмов в дискретные системы операций, которые были определены развитием электронной вычислительной техники и вычислительной математики. Этот подход достаточно удобен для многих вычислительных алгоритмов. Однако когда мы хотим учитывать при определении эффективности алгоритмов и систем такие характеристики, как эффективность транслирующих систем, эффективность операционных систем, управляющих вычислительным процессом, или эффективность такого рода операций, которые связаны с новыми применениями ЭВМ (например, формульные преобразования, обработка рисунков и картинок и т. п.), то этот подход неудобен, потому что представление новых алгоритмов и оценка их сложности в арифметических операциях — нечто совершенно противоестественное.
Следует напомнить, что существует возможность абсолютной оценки сложности алгоритмов, которая хотя и имеет чисто теоретическое значение, тем не менее может быть использована для того, чтобы, отправляясь от нее, можно было наметить практические шаги в разработке единых методов измерения сложности алгоритмов и эффективности вычислительных систем.
Реальные системы всегда имеют дело с конечным, хотя и очень большим, количеством задач. Поэтому можно характеризовать каждый класс задач некоторым конечным числом параметров. Например, для матриц — это размерность, точность, коэффициент заполнения и т. п.
Итак, пусть класс некоторых задач обработки матриц характеризуется следующими параметрами: п — размерность, т — точность, 1!к — коэффициент ненулевого заполнения матрицы, 5 (п, тп, к^ — сложность.
Рассмотрим для примера задачу обращения матриц, закодируем кэеффициенты с соответствующей степенью точности тем или иным способом в двоичной системе исчисления. Двоичная система диктуется развитием вычислительной математики и цифровой вычислительной техники. Заметим, что, несмотря на многочисленные попытки находить многоустойчивые элементы, использовать недвоичные переключательные функции простых физических явлений, которые позволили бы реализовать такого рода операции, не найдено. В то же время сложность вычислительных процессов очень тесно связана с технологией, потому что от технологии в значительной степени зависит понятие сложности базисных систем операций. И с этим ничего не поделаешь. Раз мы используем ЭВМ,
значит мы должны понятие сложности вычислений привязывать к тому, что просто и что сложно на данном уровне развития технологии ЭВМ. В настоящее время большинство ЭВМ работают с битами, т. е. двоичными единицами информации. После того, как закодированы коэффициенты условия задачи и коэффициенты решения, задача превращается в следующую.
Имеем п2, коэффициентов, записываемых с помощью т десятичных знаков, каждый из которых, в свою очередь, кодируется четырьмя двоичными. Тогда у нас будет 4п?тп входных сигналов. Если речь идет об обращении матриц, соответственно таким же будет число выходных сигналов. Построим не вычислительный алгоритм, а схему, на вход которой подадим закодированные входные сигналы, а на выходе получим их обращение. Эта задача может быть описана с помощью системы булевых функций, она конечна. Количество вариантов построения булевых функций определяется разложением этой схемы на отдельные элементы, которые возьмем не более чем с двумя входами. Любую булеву функцию от двух переменных (дизъюнкцию, конъюнкцию, штрих Шеффера и т. д.) будем считать функцией элементарной сложности. Будем говорить, что это — единица переключательной сложности задачи. Задача состоит в ом, чтобы минимизировать количество единиц переключательной сложности в полученной системе булевых функций. Это сугубо теоретический подход. В большинстве реальных задач вычислительной математики довести все это до конца таким прямым способом нельзя, однако на этом пути можно использовать разные оценки, которые есть в теории булевых функций, чтобы оценить хотя бы приблизительно переключательную сложность задачи. Она равна количеству бинарных элементов в минимальной схеме, реализующей решение задачи в один такт работы схемы.
Для того чтобы теперь перейти к оценке сложности произвольного алгоритма, нужно ввести еще некий закон распределения для значений параметров, потому что, в действительности, в потоке задач, которые будет решать машина, встретятся задачи с разными значениями п, ш и т. д. Задание закона распределения для этих параметров — это задача, которая может решаться либо «априорно», либо «апостериорно», когда этот закон может быть подтвержден для какого-то класса задач наблюдателями.
_ Если функция распределения задана (пусть это дискретная функция,, поскольку у нас целочисленные параметры), то, взяв сумму по всем значениям параметров, получим сложность соответствующей задачи. Это будет переключательная сложность задачи при заданной гипотезе о законе распределения параметров.
Естественно, что провести такие оценки до конца достаточно точно можно только для самых простых операций, например, для обычных арифметических операций сложения, умножения, а уже потом можно попытаться оценивать сложность алгоритмов, к примеру, обращения матриц в этих операциях и переводить ее в переключательную сложность.
Какие же мы будем иметь преимущества от того, что использовали понятие «переключательная сложность»? Никаких, до тех пор, пока будем в выборе элементарных операций опираться не на технологию разработки и изготовления вычислительной техники, а на интуицию и опыт математиков в домашинную эпоху. Во избежание этого нам необходимо иметь некий алгоритм порождения операций как привычных математикам, так и непривычных им, которые обладали бы одним свойством — свойством простоты реализации этих операций в виде реальных схем из
реальных переключательных элементов, простых в смысле уровня технологии сегодняшнего дня или технологии ближайшего будущего.
В настоящее время для развития вычислительной техники характерен период использования больших и средних интегральных схем. Особенности их технологии состоят в том, что реализация связей между соседними элементами технологически намного дешевле, чем между удаленными. Поэтому развиваются идеи, так называемой «целлюлярной» или ячеистой логики.
Рассмотрим простой пример.
Пусть имеется какой-то набор двоичных запоминающих элементок (триггеров), которые составляют регистр. Выполняющиеся на этом регистре операции естественно называть простыми, если они реализуются простыми многократно повторяющимися схемами, при условии малой длины соединительных проводов.
Пронумеруем элементы регистра, и для нулевого элемента построим некоторую схему
где xtJ— соседние х0 разряды. Эту функцию можно распространить на любой элемент регистра путем простого сдвига:
^i = / (Xi1_|_i, Хг24-г? • • • , ^i^+i)-
Назовем такую функцию периодически определенной. В действительности, целлюлярная логика, которая сейчас строится, не исчерпывается только таким классом функций, потому что здесь возможны достаточно сложные связи. Например, переносы в сложении описываются уже более сложными выражениями, но для иллюстрации можно ограничиться представленным выше.
Можно теперь построить некий функционал, зависящий от применяемой технологии в классе таких функций. Этот функционал, грубо говоря, измеряет сложность самой булевой функции. Поскольку это функция от ограниченного числа переменных, то задача оценки сложности реализации вполне посильна современным методам анализа и синтеза схем с использованием машин. Значит, мы имеем возможность оценивать переключательную сложность функции. Но этого недостаточно, поскольку мы имеем дело не только с переключательной сложностью, но и оцениваем сложность функции с точки зрения сложности соединений. Сложность соединений — это, грубо говоря, максимальная длина соединительных проводов. Если^переключательная сложность функции будет обозначена через 7?, а соединительная — S, то соответствующий функционал можно представить как линейную функцию от двух составляющих:
L = L(S, Д).
Это очень грубая оценка, но для первых выводов — достаточная. Когда такой функционал построен, поступаем следующим образом. Рассматриваем класс соответствующих функций и используем алгоритм, который порождает одну за другой переключательные функции (а им соответствуют некоторые операции, выполняемые на регистрах уже над числами) с возрастающей сложностью реализации. Задаемся некоторым порогом сложности, зависящим от технологии. По мере того, как совершенствуется технология производства интегральных схем и уменьшается их стоимость, можно увеличивать этот порог. Когда элементы были ламповые, дорогие, нельзя было брать слишком высокий порог сложности, потому
что устройства получались громоздкими, стоимость была колоссальная. Для интегральных схем такой порог можно значительно увеличить.
Пусть алгоритм породил некоторое множество операций, которые назовем микрооперациями. Чем этот набор микроопераций лучше предыдущего? Ранее набор содержал в себе только такие микрооперации,, которые, с одной стороны, возникали в связи с анализом развития арифметики, и, с другой — были легко реализованы на соответствующем этапе развития вычислительной техники. При рассматриваемом подходе мы получаем полный набор микроопераций, многие из которых для инженеров-проектировщиков являются совершенно необычными. Опыта их использования у них нет.
За тысячи лет развития вычислительной математики были придуманы действительно хорошие арифметические операции, которые должны были остаться и при машинной реализации вычислительных алгоритмов, но задача, которую мы ставим,— это задача оценки произвольных алгоритмов. В частности, задача оценки алгоритмов формульных преобразований, вспомогательных алгоритмов подготовки данных, управления, распознавания, т. е. таких, над анализом которых человек никогда не задумывался.
Если попытаться оценивать их сложность в терминах только привычных микроопераций, то такие оценки вряд ли дадут действительную картину, поскольку используемые микрооперации не являются естественными для всякого алгоритма. С другой стороны, поскольку опыта работы с новыми микрооперациями нет, приходится все же программировать алгоритмы в привычных микрооперациях. Но как же тогда быть? Вот здесь и выступает вторая соответствующая часть теории основ вычислительных процессов — теория формальных преобразований алгоритмов.
Допустим, мы проектируем систему команд какой-то машины, а потом — микрокоманд и иерархию стандартных программ. Попытаемся разложить и запрограммировать эти операции в микрооперациях, которые у нас есть и которые легко реализуются на данном уровне технологии. Среди этих микроопераций наверняка оказываются все традиционные (сдвиг, сравнение и т. д.), но есть и много новых. Проектировщик машины, который программирует систему команд, пишет первый вариант микропрограмм не со всеми микрооперациями, а только с теми, которые он хорошо знает. Естественно, программа получается менее экономной, чем тогда, когда он использует все богатство представленных ему возможностей. Для получения экономной программы можно теперь использовать систему преобразований в алгебре программ или микропрограмм. В настоящее время найден способ, с помощью которого можно всякую программу представить как элемент некоторой алгебры, а затем, путем применения соотношений в этой алгебре, можно преобразовывать программу, как обычную формулу. Конечно, преобразования в этой алгебре намного сложнее, чем в обычной алгебре или даже алгебре математического анализа. Но тем не менее привыкнуть к такой алгебре и работать с нею можно.
Построив соответствующий алгоритм порождения, определяющие соотношения можно искать автоматически методом простого перебора выражений из всех имеющихся в наличии микроопераций. Эту же задачу можно решать и на другом уровне, например на уровне определения системы команд.
Как же выбрать систему команд машины?
Зададим класс задач и попробуем построить систему команд. Что такое команда машины? Это удачно найденная группа последовательных микроопераций^ которая обеспечена определенным образом и выведена на 214
другой уровень управления. Сначала возьмем традиционную систему команд, с которой мы привыкли работать и которую хорошо принимаем. Записав эти команды в виде выражений в алгебре микроопераций, получаем микропрограммы. Если есть алгебра, то мы можем теперь начать перерабатывать эти микропрограммы с единственной целью: получить как можно больше одинаковых групп микроопераций. Это задача большой вычислительной сложности, и пока не видно никаких разумных подходов, кроме организации совместной работы человека и машины, когда человек подает идеи относительно применения определяющих соотношений в программной алгебре, ограничивающих перебор.
Если мы преуспели в этом отношении, то перегруппировав микрооперации по-другому, получим совершенно новые группы микроопераций, более экономичные, которые и принимаются в качестве команд машины для данного класса задач. А дальше подобные преобразования могут быть повторены на любом уровне.
После того как система команд выбрана, возникает вопрос о иерархическом построении программной реализации.
Как мы этот вопрос решаем сейчас? Мы используем, фактически, иерархическое построение, т. е. стандартные программы более высокого уровня. Но откуда мы извлекаем эту иерархию? Прежде всего из истории развития вычислительной математики. Например, программа вычисления sin х может быть использована в сложной программе, где производится, например, разложение функции в ряды Фурье. Но ведь этот подход придуман не программистами, не системщиками, а задолго до них в области вычислительной математики. Опыт программирования привел к появлению целого ряда стандартных процедур, относящихся к управлению вычислительным процессом и организации данных. Здесь тоже рождается некий универсальный базис — кирпичи, которые используются при программировании на более высоком уровне.
Уверены ли мы в том, что небольшой опыт программистов привел к разумному построению базиса. Нет... Даже в наиболее хорошо изученных вычислительных алгоритмах существуют не только стандартные блоки sin х, cos х и др., но и такие, которые упорядочивают, сортируют, выбирают данные. Эти операции также выносятся на новый уровень иерархии, имеют свое название и входят в рабочий багаж программиста.
Представим себе, что мы пытаемся построить «умную» машину, в которой весь набор стандартных программ занесен в ПЗУ и зашит в матрицах. Если в целом ряде программ повторяется какой-то кусок, то нахождение его и вынесение на более высокий уровень иерархии существенно экономит память машины. Задача иерархической реализации набора программ является задачей такого же типа, как и рассмотренные выше.
Если мы уверены в том, что на соответствующем уровне иерархии обладаем полным набором операций (команд), который выведен в конечном счете из технологии, можно воспользоваться тем же приемом. Расписываем какую-то сложную программу с использованием стандартных процедур, которые будем называть сейчас макрокомандами, а потом ставим задачу, правильно ли выбран этот набор макрокоманд. Чтобы в этом убедиться, нужно переписать все программы, которые записаны со стандартными процедурами (макрокомандами), вернуться на один уровень иерархии вниз (командный уровень), применить соотношения в алгебре программ и попытаться перекомпоновать команды так, чтобы получить дополнительные, новые процедуры^ а затем выделить их в новый список макрокоманд. '
Приведенные выше рассуждения иллюстрируют общую идеологию подхода к решению целого ряда практических задач, связанных с проблемой оценки сложности алгоритмов.
В действительности таким образом трудно решать эту задачу до конца. Тем не менее работать в данном направлении можно и нужно, о чем свидетельствует опыт реализации математического обеспечения машин класса «МИР».
Сравнение с соответствующими программами для машин IBM-490, которое проводилось нашими специалистами, показало, что подавляющее большинство задач машина «МИР» решает быстрее, несмотря на разницу в классе. Это объясняется тем, что при создании «МИР» набор ее операций и иерархия матобеспечения, вложенного в память машины, хорошо учитывали особенности задач, для которых она проектировалась. Хотя «полной» теоретической картины дать мы еще не можем, тем не менее практические подходы к решению этой проблемы имеются. Эта проблема имеет существенное значение для разработок по машинам третьего и особенно четвертого поколения. В Институте кибернетики уже есть опыт разработки большого количества разных операционных систем: специализированные системы управления технологическими процессами, автоматизированная система проектирования ЭВМ (Ю. В. Капитонова, «Вопросы организации специализированных систем программирования») (см. настоящий сборник) и др.
Мы понимаем, что операционная система, как, впрочем, и транслирующая, должна разрабатываться в тесном единстве с разработкой машины. Имеющиеся в настоящее время операционные системы позволили отделить процесс решения задачи от процесса подготовки данных, кроме того, именно операционные системы позволяют осуществить динамическую реализацию процесса вычислений для разных конфигураций центрального процессора с внешними устройствами.
При анализе сделанного стало ясно, что при имеющемся уровне организации системы команд и организации управления процессом вычислений операционная система получается чрезвычайно сложной. Поэтому в идеологии машин четвертого поколения намечаются следующие сдвиги. Это, прежде всего, реализация значительных частей операционной системы в hardware и использование параллельных вычислений. Известно, что благодаря революции в hardware появилась возможность делать схемы ЭВМ гораздо большей переключательной сложности, чем раньше. Если раньше, предположим, 103—104 логических активных элементов типа триггеров в машине было более или менее обычным явлением, то в машинах четвертого поколения это число вырастет до 106—107 активных элементов. Эти десятки миллионов элементов нужно разумным образом организовать. Существует два способа такой организации. Первый — увеличение возможностей набора команд машины, т. е. богатство системы микроопераций, и за счет этого — увеличение вычислительной мощности машины, что не приводит к существенному увеличению быстродействия элементов. Машина выполняет такое же количество арифметических операций, но вычислительная ее мощность по решению действительных потоков' (задач, связанных с их транслированием и решением нетрадиционных математических задач, резко возрастает.
Второй способ — распараллеливание решения сложных задач. Такое направление в настоящее время успешно развивается. Уже появились мультипроцессорные системы для машин третьего поколения, что ведет к увеличению количества центральных процессоров в одной вычис-
лительной системе. По-видимому, в машинах четвертого поколения цифра будет в пределах нескольких сотен, а может быть, тысяч. Поэтому предъявляются совершенно новые требования к организации работы машины.
Если для решения задачи сначала создавать hardware, а потом для него строить software, это приведет к тяжелым последствиям. Уже сейчас в ОС-360 около двух миллионов команд, ее работа в зависимости от задач занимает от 25 до 85 % машинного времени. Если к задачам организации вычислительного процесса в одном процессоре добавить еще очень сложную задачу распараллеливания процессов, то это приведет к еще большему использованию машинного времени ОС. Поэтому для машин четвертого поколения разумно поставить требования алгоритмического распараллеливания процессов. Может быть, не в полной мере, какая-то часть работы должна быть вынесена в hardware.
Диспетчер и распределитель ресурсов сильно усложняются из-за того, что к задаче мультипрограммирования добавляется выдача мультипроцессирования. Если провести оценки, то следует ожидать увеличения всех показателей времени работы операционной системы примерно на порядок.
Делаем вывод, что традиционный подход к созданию традиционных систем software на основе выбранной архитектуры какой-то машины совершенно не пригоден. Следовательно, необходимо операционную систему проектировать одновременно с hardware. Для этой цели имеются два подхода. Можно сделать так, что все процессоры будут унифицированы, но набор команд, который в них вкладывается, рассматривается не только исходя из класса задач, связанных с рабочими задачами (обращение матриц, распознавание образов), но и с точки зрения задач управления системой. Тогда каждый процессор — взаимозаменяем, но каждый процесс включает в себя реализацию системы команд, которые позволяют ему, скажем, не тратить оперативную память на содержание таблицы ресурсов занятости, для эффективного управления буферными фондами, не организовывать для этого специальных таблиц по буферному кубу слежения за ними в оперативной памяти, а выносить это на специальные автоматы и т. д.
Все это — усложнение устройства управления. Таким образом, к понятию «состояние программы» для машин третьего поколения прибавилось понятие «состояние системы» для машин четвертого поколения. Все перераспределения очередей к ресурсам и т. д. должны производиться в результате анализа их на каких-то логических схемах прямо в устройстве управления, без обращения к соответствующему блоку операционной системы, что очень важно для машин с ограниченной памятью.
Второй путь, который нам кажется более целесообразным,— создание специализированных процессоров, специализированных на классы применений. Это — сверхбыстродействующие арифметические процессоры, на которых, в основном, решаются задачи математического и численного анализа; процессоры, ориентированные на обработку картинок, чертежей, графической информации, формульные преобразования и т. д.; коммуникационные процессоры.
Коммуникационные процессоры в машинах четвертого поколения должны взять на себя дополнительные функции. Дело в том, что существуют такие процессоры обработки информации, в которых небольшое количество операций производится с записью на массивах внешней памяти, и они не могут выполняться под управлением коммуникационных процессоров. Требуется подключение центрального процессора. Поэтому
следует усложнить коммуникационный процессор таким образом, чтобы он мог выполнять простейшие процедуры обработки данных, типа сортировок, различных выборок из массивов, редактирования и т. д.
Очень важной задачей для машин четвертого поколения является унификация операционных систем. На первый взгляд, она находится в противоречии с изменением технологии, что вызывает необходимость изменения набора команд, которые, в свою очередь, меняют возможности систем прерывания в машинах. Операционная система существенно зависит от всех этих особенностей архитектуры машины. Для решения такой, на первый взгляд, неразрешимой задачи унифицирования software необходимо его разработать так, чтобы он мог быть применим к любой машине; машина изменяется, a software переносится практически без изменений.
Один из подходов аналогичен подобному в системе IBM-360, только распространен он на более высокий уровень. Смысл его заключается в разработке специальных генераторов software. Генераторы операционной системы IBM-360 позволяют получить действительные программы операционной системы применительно к разным ее конфигурациям. Можно купить машину не в полном комплекте, скажем, без десятичной арифметики или какого-то комплекта дисков, и т. д. В соответствии с этим меняются некоторые части программы по управлению системой. Идея заключается в том, что разрабатываются не действительные программы операционной системы, а генераторы этих программ и дается описание конфигурации машины. Используя информацию о конфигурации машины и генерирующую программу, генератор на минимальном комплекте вырабатывает программу операционной системы для комплекта, который описан.
Таким образом, в системе команд и в организации системы прерываний имеется некоторая устанавливающая часть, которую назовем минимальным комплектом команд и минимальным комплектом возможностей системы прерывания и других, организующих согласование систем. Затем разрабатывается язык, на котором описываются все изменения этого минимального стандарта, а также возможности расширения архитектуры машин. Далее строится генератор операционных систем, который по описанию минимального стандарта и комплекта машины, фактически описанных конструктором, порождают конкретную операционную систему. Эта задача очень трудная и непривычная для конструкторов, успех ее заключается в хорошем взаимодействии конструкторов операционных систем и разработчиков hardware машин.
ФУНДАМЕНТАЛЬНЫЕ ИССЛЕДОВАНИЯ И ТЕХНОЛОГИЯ ПРОГРАММИРОВАНИЯ
[Технология программирования. Тезисы докл.
11 Всесоюзн. конференции. Пленарные доклады.— Киев: ИК АН УССР, 1979]
Развитие программирования в настоящее время называется искусством. Методологическая основа и результаты в программировании излагаются скорее на эмоциональном, чем на строго научном уровне. Основные понятия программирования — модуль, структура, уровень проектирования и т. д.— даже для широко распространенных (модных) технологий остаются не строго определенными.
Следствием этого является индивидуальный, творческий характер труда программистов. Стоимость программного обеспечения в настоящее время в несколько раз превышает стоимость аппаратуры ЭВМ. Тенденция такова, что через 10 лет соотношение между ними будет такое, как между стоимостью товара и упаковки (рис. 1). Кроме того, такая организация труда программистов приводит к тому, что 70—80 % работ по программированию функционально дублируют друг друга. Качество получаемого в результате программного продукта настолько низкое, что на его сопровождение затрачивается 60—70 % всех средств (рис. 2). Отсутствие хорошей, составленной в едином стиле документации приводит к низкой познаваемости программных систем, и в результате к тому, что из всего объема функционирующего программного обеспечения активно используется лишь 1—3 %.
В настоящее время резко изменился характер обрабатываемой на ЭВМ информации. Достаточно сказать, что банк данных современной АСУ для организационного управления экономическими объектами (крупным заводом, торговым центром, научным объединением и т. д.) должен содержать IO16 -J- 1016 бит информации. Эта информация имеет сложную иерархическую структуру, отражающую современную тенденцию к интеграции и интенсификации производства. Сложность задач управления в масштабах всей страны оценивается 1016—1017 эквивалентными арифметическими операциями в год. Самой сложной проблемой является создание программного обеспечения для накопления и обработки такого количества информации. С появлением микропроцессорной техники еще более обострилась проблема создания конвейерных способов производства программной продукции.
В Институте кибернетики АН УССР на протяжении последних 20 лет фундаментальные исследования были сосредоточены по трем основным направлениям:
теория автоматов и алгоритмов;
новые принципы построения ЭВМ;
принципы построения АСУ.
Основная идея доклада применительно к проблематике конференции заключается в том, что теоретические результаты, полученные в указанных направлениях^ могут послужить хорошей основой и базой для работ
60-е годы60-е годыПрогноз на 1985 г.Прогноз на 1985 г.
60-е годы
60-е годы
Прогноз на 1985 г.
Прогноз на 1985 г.
по технологии программирования в современном ее понимании. Причем указанная идея будет особенно конструктивна, если в качестве рабочего тезиса будет использоваться наш — о единстве проблем проектирования программного и аппаратного обеспечения ЭВМ. Этот тезис последовательно пропагандируется нами с 60-х годов, с момента начала работ над машинами серии МИР. Целесообразность не различать проблемы создания программного и аппаратного обеспечения ЭВМ обусловлена, по крайней мере, следующими обстоятельствами: "
Общность математических моделей, которые возникают при построении методов проектирования схемного и программного оборудования ЭВМ;
Взаимное проникновение идей и методов проектирования устройств и программ.
Единая технология проектирования аппаратуры и математического обеспечения особенно важна для развития микропроцессорной техники, где эти вопросы особенно тесно переплетаются. Для программирования такое единство обеспечит конструктивный переход от индивидуальных методов проектирования программных систем к промышленным методам их создания. В этом вопросе технология проектирования аппаратуры ЭВМ находится далеко впереди и программистам есть чему поучиться у конструкторов ЭВМ.
Основу единой технологии проектирования программных и аппаратных средств составляет методология синтеза цифровых автоматов, созданная в институте еще в начале 60-х годов и впоследствии распространенная на задачи программирования. Согласно этой методологии, весь процесс проектирования программной системы представляется в виде последовательности этапов, на каждом из которых мы имеем дело с естественными математическими моделями, описываемыми соответствующими автомата-
РазрадоткаРазрадоткаРис. 2.Рис. 2.
Разрадотка
Разрадотка
Рис. 2.
Рис. 2.
ми в некотором алфавите. Задачи проектирования таких систем можно представить как задачи анализа, синтеза и оптимизации соответствующих семейств автоматов. Математические модели, используемые на различных этапах проектирования, имеют различные уровни детализации. Задача синтеза или проектирования — это переход от моделей верхнего уровня к более детализированным моделям нижнего уровня, движение сверху вниз. Начинать следует с создания моделей обрабатываемых данных. Задача анализа — построение моделей высокого уровня, движение снизу вверх.
На каждом этапе проектирования необходимо обосновывать правильность результата путем установления соответствия между моделью системы и ее реализацией, а также установления различных свойств проектируемого объекта. Анализ результатов проектирования проводится путем математического исследования и доказательства соответствующих утверждений, либо путем моделирования с использованием машинных экспериментов. Соответствующая техника достаточно хорошо проработана в общей теории и практике проектирования автоматов.
Исследования по новым принципам построения ЭВМ начались в начале 60-х годов с машин серии МИР. В связи с тематикой конференции интересно проанализировать применение этих машин как инструментальных средств для анализа и разработки программ. Одним из основных назначений машин данной серии была отработка в диалоговом режиме алгоритмов и методов решения инженерных задач и задач вычислительной математики. В машине МИР-2 был схемно реализован аппарат аналитических преобразований, позволяющий решать задачи как численными, так и аналитическими методами. В связи с развитием методов доказательства утверждений о программах выяснилось, что аппарат аналитических преобразований может быть успешно применен для решения задач анализа и преобразования программ, например, с целью их оптимизации и доказательства корректности. В последнем случае почти ничего не надо программировать за счет схемного проведения вычислений с аналитическими выражениями и использования процедур приведения аналитических выражений к каноническим формам,, а также реализованных в аппаратуре машины МИР-2. Проведение подобных экспериментов через программный интерфейс на ЭВМ с традиционной структурой требует гораздо большего объема работ по программированию и искусства исполнителя. Не исключено, что проведение этих работ для тонких аналитических преобразований с целью доказательства правильности программных систем будет вообще невозможно через интерфейс современных операционных систем из-за чрезмерного усложнения работ по программированию.
Известно, что технология программирования усложняется в большей степени по причине ограниченности ресурсов ЭВМ и их операционных систем: разрядная сетка, объем памяти, фиксированные и простейшие механизмы доступа к ресурсам и т. д. В настоящее время, учитывая успехи микроэлектроники, на повестку дня выдвигаются вопросы построения таких структур ЭВМ, в которых основным является не технологичность конструкции, а технологичность проектирования программных систем. Машина должна строиться для программиста, для решения его задач по максимально простой технологии, поэтому она должна иметь простую рекурсивно перенастраиваемую структуру. В таких машинах не задача должна перекодироваться для реализации на ЭВМ неизменной структуры, а структура машины должна с минимальным участием программиста перенастраиваться на решение задач максимально простым способом.
Профессиональный программист сегодня должен уметь ставить задачу инженерам-электронщикам на построение таких нужных для себя вычислительных систем.
Технология программирования, как новое и прогрессивное направление промышленного изготовления больших программных систем, в настоящее время не использует огромный задел в области построения автоматизированных систем управления (АСУ). Многие прописные истины организации автоматизированного управления в новом направлении открываются заново. АСУ для производства программной продукции, как и обычно, должна решать три основные задачи: сбор и передачу информации об объекте управления (о состоянии разработки программной системы), переработка информации и, наконец, выдача управляющих воздействий на объект управления, т. е. управляющему звену и разработчикам соответствующей программной системы. Такие АСУ имеют две особенности. Во-первых, большая часть информации об объекте управления может быть получена автоматически из программ, введенных в ЭВМ для обработки. Для эффективного функционирования такой АСУ требуется минимальная дополнительная информация об объекте управления. Во-вторых, АСУ для производства программ максимально удовлетворяют принципу новых задач, так как сам объект управления — технология программирования — находится в начальной стадии своего формирования.
Еще совсем недавно, лет двадцать назад, делать вычислительную машину «у себя на фирме» считалось нормальным. Все, кому нужна была вычислительная машина, делали ее сами и всем убедительно доказывали целесообразность именно такого пути развития. Сейчас это кажется диким, поскольку машины делают специализированные подразделения, и культура их изготовления резко повысилась. Но то, что для вычислительной техники является уже вчерашним днем, для программирования — самые что ни есть будни. Все делают программы ...
Сейчас сделано много для преодоления этого этапа развития и повышения общей культуры программирования в стране: заканчивается переход на единые вычислительные средства; закуплено и освоено большое число хороших и полезных пакетов и систем математического обеспечения; начинается становление национальной технологии программирования; созданы институты централизованного обслуживания средств вычислительной техники и централизованные фонды алгоритмов и программ. Задачей сегодняшнего дня является сосредоточенное представление рассредоточенных действий программистов. На этом пути представляется целесообразным создание межведомственного центра производства программ, задачей которого должно быть проектирование типовых технологий изготовления программной продукции в ведомственных организациях.
О ФОРМАЛЬНЫХ ПРЕОБРАЗОВАНИЯХ АЛГОРИТМОВ
(Алгоритмы в современной математике
и ее приложениях.— Ч. 2.— ВЦ СО АН СССР.— 1982 г.)
Современные формы представления алгоритмов в виде программ в алгоритмических языках можно рассматривать как естественное развитие формульного аппарата классической математики, используемого для конструктивного представления математических объектов. Это приводит к идее разработки методов формальных преобразований алгоритмов, рассматриваемых как алгебраические выражения. С этой целью автором в 1965 году была предложена алгебра алгоритмов и доказана теорема анализа, показывающая возможность представления в этой алгебре произвольных программ [1]. В этой же работе был рассмотрен пример построения эффективного алгоритма путем преобразования начального описания с помощью соотношений в алгебре алгоритмов.
В дальнейшем продолжалось изучение соотношений в алгебре алгоритмов. Она использовалась при создании ряда систем автоматизации проектирования схемного и программного оборудования ЭВМ. В работе [2] были выведены формулы алгебры алгоритмов, которые могут быть использованы для ускорения итерации монотонных операторов. Эти формулы обобщают метод, использованный в [1] для ускорения умножения, и позволяют использовать его для ускорения других алгоритмов. Рассмотрим это обобщение.
Пусть рассматриваемая алгебра алгоритмов порождается элементарными операторами и условиями, действующими на информационном множестве В. Как известно, эта алгебра является двухосновной, составленной из двух компонент: алгебры операторов и алгебры условий. Элементами первой алгебры являются операторы, т. е. частичные преобразования множества В, элементами второй — условия, т. е. частичные функции, заданные на В и принимающие значения 0, 1* Операциями алгебры операторов являются произведение, а-дизъюнкция и а-итерация. В алгебре условий определены булевские операции и операция умножения оператора на условие. Эту операцию мы будем обозначать аР (а после Р\
Оператор Y называется монотонным относительно условия а, если из а (Ь) = 1 следует, что а (у (Ь)) = 1. Будем предполагать, что множество В состояний информационной среды состоит из двух компонент С и С\ т. е. В = С X С*. Операторы Р и Q называются С-эквивалентными, если они имеют одинаковые области определения и для любого состояния b = (с, с') из Р (с, с') = (сх, с^) и Q (с, с') = (с2, сг) следует сг = с2. Иными словами, С-эквивалентность означает одинаковые действия на компоненте С. Будем говорить, что оператор Y (условие а) действует на компоненте С если существует частичная функция ф из С в С (из С в {0, 1}) такая, что для любых с 5 С, с' £ С" У (с, с') = (ф (с), с'), (а (с, с^ = ф (с)).
Аналогично можно говорить о действии на компоненте С..
Основной результат работы [2] может быть сформулирован следующим образом. Пусть оператор Y и условие а действуют на компоненте С, операторы z0 и и действуют на компоненте С" информационной среды В = = С X С", а в полугруппе операторов алгебры алгоритмов^ действующих
на В, выполняются соотношения:
zoz = z0Y;
ZqU^^z = ZqU^u, m = 0, 1, ... lV
MZ0 = z0.
Тогда, если оператор Y монотонен относительно условия аЛ то следующие операторы С-эк швалентны:
{У};(!)
(20{u}z};(2)
а
zjj^z},(3>
Zo {(е v z) “), где р = a-“z<z}.(4)
Если, кроме того, в полугруппе операторов есть оператор и S действующий на компоненте С и удовлетворяющий соотношениям
zoum^u—v = zoum, m = 0, 1, ... t
а также оператор У-1, действующий на Си такой, что УУ-1 = е, то операторы (1) — (4) С-эквивалентны оператору
{ u~4z}.(5)
az a azy--1
Применение метода ускорения итераций монотонных операторов происходит обычно в условиях, когда итерация определена для алгебры алгоритмов, действующей на информационной среде С. Для построения эффективной программы С расширяется до множества С X О', где С' выбирается таким образом, чтобы можно было определить операторы zOl и, z, а если возможно, то и-1 и У-1. После этого выбирается одна из программ (2) — (5) и реализуется в используемом алгоритмическом языке. Для перехода к обычной программе достаточно реализовать проверку условий. Если простая итерация работает на некотором состоянии информационной среды п раз, то программа, построенная по формуле (2), работает в течение времени, пропорционального (log п)2, а программы (3) — (5) — log п.
Методы формального преобразования алгоритмов широко используются в развиваемой в Институте кибернетики АН УССР технологии проектирования, получившей название метода формализованных технических заданий [3, 4]. Рассмотрим несколько примеров формальных преобразований алгоритмов в процессе их проектирования с помощью этого метода, выполненных в последнее время.
Первый пример возьмем из работы [5]. Рассмотрим задачу вычисления числа компонент связности неориентированного графа Г = (G, Р)я определенного множеством вершин G и симметричным отношением смежности р cz G2. Рефлексивное и транзитивное замыкание отношения р дает 224
отношение достижимости р : g и g' достижимы, если g = g' или существует последовательность g = gv g^, ..., gm = g' (m ^ 1) вершин такая, что g-^и. gt+i смежны для i = 1, ..., m — 1. Отношение достижимости является эквивалентностью. Классы этого отношения эквивалентности будем называть компонентами связности. Компоненту связности, содержащую вершину g, обозначим через р (g).
Следующая программа описывает в теоретико-множественных терминах простой алгоритм решения этой задачи: BEGIN
к : = О
FOR ALL g £ G DO ф (g) : = О
LOOP BEGIN
FIND g € G SUCH THAT ф (g) = 0
IF NOT THEN GO OUT
к: = к + 1
FOR ALL h e p (g) DO ф (h) : = к
END LOOP
END
Корректность этой программы легко может быть доказана обычными методами. Представив рассматриваемую программу в виде BEGIN к : = О Р
LOOP BEGIN
Q
к : = к + 1
R
END LOOP
END
и выполняя последовательное уточнение операторов Р, Q, R, получим программу на АЛГОЛе. Для построения этой программы выберем следующий способ представления графа. Пусть G — целочисленный массив размером [1: п; 1: ml, где п — число вершин графа Г, m — не меньше, чем максимальное число вершин, смежных с любой данной вершиной графа Г. Массив G представляет граф Г, если G [г, /] =# 0 тогда и только тогда, когда вершины gt и gciva смежны, i = 1, ..., п; / = 1, ..., m; G = = lgv ..., gnl- Функцию ф реализуем с помощью целочисленного массива FI [1 : nl, полагая ф (gt) = FI [t] для i = 1, ..., п. Программа на языке АЛГОЛ имеет следующий вид: PROCEDURE COMP (G, М, N, К); INTEGER ARRAY G; INTEGER N, M, K; VALUE M, N;
BEGIN INTEGER ARRAY FI [1 : N], INTEGER I, J, S; BOO
LEAN CHANGE;
p Г k : = 0;
r [FOR I : = 1 STEP 1 UNTILL N DO FI [I] : = 0;
n[L : FOR I : = 1 STEP 1 UNTILL N DO IF [I] = 0 THENBEGIN S : = I; GO TO FOUND END; GO TO FINE;
- FI [S] : = k;REPEAT : CHANGE : = FALSE;FOR I : = 1 STEP 1 UNTILL N DO IF FI [II = k THENFOR J : = 1 STEP 1 UNTILL M DO IF G [I, J] #= 0 THEN- FI [S] : = k;REPEAT : CHANGE : = FALSE;FOR I : = 1 STEP 1 UNTILL N DO IF FI [II = k THENFOR J : = 1 STEP 1 UNTILL M DO IF G [I, J] #= 0 THENRRFOUND : k : = k + 1;
- FI [S] : = k;
REPEAT : CHANGE : = FALSE;
FOR I : = 1 STEP 1 UNTILL N DO IF FI [II = k THEN
FOR J : = 1 STEP 1 UNTILL M DO IF G [I, J] #= 0 THEN
- FI [S] : = k;
REPEAT : CHANGE : = FALSE;
FOR I : = 1 STEP 1 UNTILL N DO IF FI [II = k THEN
FOR J : = 1 STEP 1 UNTILL M DO IF G [I, J] #= 0 THEN
R
R
15 — 9-3609
IF FI [G [I, JJ] Ф к THEN BEGIN FI [G [I, J]] : = k;
CHANGE : = TRUE; END;
_ IF CHANGE THEN GO TO REPEAT; GOTO L; FINE : END.
Первая программа рассматривается как формализованное техническое задание, реализацией которого является вторая программа. Полученная программа неудовлетворительна, поскольку работает в течение времени^ пропорциональном mn2. Для того чтобы сократить время ее работы, вернемся на теоретико-множественный уровень^ сохранив представление данных. BEGIN
к : = О
[FOR ALL i = 1, ..., n DO FI [i] : = 0 LOOP BEGIN
n [FIND s SUCH THAT FI [s] = 0
^ [IF not then go out
к : = к + 1
"FI [s] : = к
DO UNTILL CHANGE
BEGIN CHANGE : = FALSE
„FOR ALL i = 1, ..., n SUCH THAT FI [i] = к DO
KFOR ALL j = 1, ..., m SUCH THAT G [i, j] # 0
AND FI [G [i, j]] к DO
(FI [G [i, j]] : = к CHANGE : = TRUE)
_END UNTILL
END LOOP
END
Введем новые структуры данных: множество Уо cz {1, ..., п} и множество W cz {1, ..., п). Добавим в рассматриваемую программу вычисления над этими множествами, построив их таким образом, чтобы при каждом прохождении внешнего цикла выполнялось условие Уо = (1 ^ г ^ ^ п | FI [г] = 0}, а при каждом прохождении внутреннего цикла — условие FI [i] = к, и существовало 1 ^ у ^ m такое, что G [Z, у] =# 0 и FI [G [Z, у’П #= к « i ^ W. Теперь оператор Q можно заменить оператором
IF Vo = 0 THEN GO OUT ELSE GET s FROM Vo, а заголовок цикла no Z — заголовком FOR ALL i £ W DO. Выполнение оператора GET X FROM А сопровождается удалением элемента X из А, а оператор FOR ALL i f W DO T эквивалентен следующей последовательности операторов:
WHILE W Ф 0 DO BEGIN
GET i FROM W
T
END WHILE
Для того чтобы перед выполнением этой последовательности выполнялось условие для множества W, достаточно в операторе Т добавлять к этому множеству индекс всякой новой вершины в момент, когда она впервые отмечается числом к. После соответствующих преобразований станет ясно, что при втором прохождении внутреннего цикла множество W будет пустым и скобки цикла можно опустить. Мы можем также удалить переменную CHANGE. Измененная программа имеет следующий вид:
BEGIN
к : = 0
FOR ALL i = 1г .... n DO Fl [i] : = 0
< Vo: = (1, ..., n} >
WHILE Vo ^ 0 DO BEGIN
GET s FROM Vo
к : = к + 1 FI [s] : = к
<W : = {s} >
FOR ALL i g W DO
FOR ALL j = 1, ..., m SUCH THAT G [i, j] 0 AND FI [G [i,;
j]] ^kDO
(FI [G [i, j]J : = к <DELETE G [i, j] FROM Vo
INCLUDE G fi, j] IN W>)
END WHILE
END
В этой программе вставленные операторы взяты в скобки ( ). Полученная программа будет работать линейное время, если удаление и добавление элементов множеств Fo и Wосуществляется за ограниченное время. Этого легко добиться, реализовав представление с помощью списков. Аналогичным образом можно было бы получить экономный алгоритм подсчета числа компонент связности для ориентированных графов, с временной оценкой такой же, как в известной работе Тарьяна [6]. Подобным же методом в [5] осуществлено получение алгоритма Хопкрофта [7] приведения автомата за время nlog п из классического алгоритма приведения, имеющего временную характеристику п?.
Следующий пример также относится к теоретико-множественному программированию и связан с реализацией рекурсивных определений.
Пусть Q есть n-местное отношение, заданное рекурсивным определением
Р (xv ..., хп) => Q (^, ..., xnY Q {х^ .... х^ и 7? ^v .... zm) Q (уг, ...
Q есть наименьшее отношение, удовлетворяющее первым двум условиям для всех хХ1 .... хпи иХ1 ..., и^ таких, что S (uv ..., ик\ Здесь R и 5 — заданные отношения, zv .,., zmi уг1 .... Уп — алгебраические выражения, зависящие от переменных xv ..., хП1 uv ..., ик.
От этого определения легко перейти к теоретико-множественной программе, которая строит множество Q, если все отношения, используемые в определении, конечны. Программа имеет следующий вид:
BEGIN Q : = 0 Qo : =
LOOP BEGIN Q : = 0
FOR ALL (x1? ..., xn) 5 Q0DO
FOR ALL (u17 ..., uk) gs SUCH THAT R (z17 ..., zm) DO IF(y17 ...7 yn)£Q U Qo U Qi THEN INCLUDE (У1, ..., yn) IN Qt
Q : - Q V Qo-
IF Q, = 0 THEN GO OUT
Qo: = Qi
END LOOP
END
Обычно такая программа работает неэффективно, перебирая лишние элементы множеств Р, R и 5 по нескольку раз. Поэтому ее следует оптимизировать, пользуясь конкретными свойствами множеств Р, R и S.
Рассмотрим хорошо известную задачу определения существенных переменных в состоянии схемы программы — одну из основных задач анализа потоков данных в программах. Рассмотрим необходимые определения. Схема программы над памятью R — это множество состояний
схемы вместе с множеством Т переходов, каждый из которых представляет собой четверку (а, и, у, a'Y где а — состояние схемы, и — условие перехода, у — оператор, выполняемый во время этого перехода, а' — состояние после этого перехода. Если (а, и, у, а') есть переход, то пишем а-^а'. Для каждого из операторов заданы два множества: множество используемых и множество вырабатываемых оператором переменных из Я, а для каждого условия задано множество переменных, которое в нем используется. Пусть в схеме из а в а' есть последовательность переходов р = tv .... tu такая, ЧТО ti = (tlj, Ui, Уг^ ^г), ^i = U, #п = а', аг+i = #ь I = 1, ..., и —
гР г
— 1. Если р есть путь из а в а . то пишем а-^а . Если переход t = (а8 и, у. а) такой, что и и у используют г, то говорим, что состояние а и переход t используют г. Переход t вырабатывает г, если у вырабатывает г. Основное определение формулируется следующим образом: переменная г существенно в а » а использует г или существует путь р и состояние а' рг
такие, что а -> а , состояние а использует г и ни один из переходов пути р не вырабатывает г. Для того чтобы получить конструктивное определение понятия существенной переменной, рассмотрим отношение Q с А X R$ которое определяется как наименьшее отношение такое, что
а использует г =>(а, г) £ Q;
(а, г) g ^ и а -> а для некоторого перехода р. который не вырабатывает г => (а', г) ^ Q.
Легко доказывается следующее предложение: переменная г существенна в а « (а, г) £ Q.
Применяя описанное выше построение, легко получим следующую программу, которая генерирует множество Q.
BEGIN Q : - 0 Qo : = {(а, г) | a USES г}
LOOP BEGIN Qi : = 0
FOR ALL (a, r) £ Qo DO
FOR ALL a' £ A SUCH THAT FOR SOME p £ T
(a' 4 a AND p DOES NOT GENERATE r) DO
IF (a', r) 5 Q U Qo U Qi THEN INCLUDE (a', r) IN Q, Q : = Q U Qo
IF Qr = 0 THEN GO OUT
Qo ’• = Qi
END LOOP END
Принимая во внимание способ представления схем программ, можно оценить эффективность реализации построенного алгоритма и выбрать подходящие способы представления множеств Q. QOl Q^ Предположим, что множество А состояний схемы программы задается списком, а множество Т переходов — с помощью функции Т1, заданной на Л и принимающей
значение в множестве Т. причем р С 1\ (а) <=> р £ Т и а —> а для некоторого а* ^ А. Оценим время работы программы в зависимости от числа п состояний схемы А. При этом будем считать, что число переменных и число переходов в каждом состоянии ограничено, т. е. мало по сравнению с п. которое может быть сколь угодно большим. Тогда, если Q. Qo и QT задаются обычными списками, то время работы будет пропорционально п3. Сокращение времени может произойти за счет ускорения условия (а, г) ^ Q Ц U Qo U ^i и за счет ограничения области изменения параметра цикла.
Первое может быть сделано, если множества Q, Qo и QT представлять с помощью функций F, Fq и Fv заданных на Л и принимающих значения в 2R. При этом, (а, г) ^ Q <=> г £ F (а). Аналогично определяются Fo и Fv Для ускорения порождения элементов множеств Qo и Qx удобно использовать вспомогательные множества So и Вг такие, что a £ Во о Fo (а) ф 0, a £ € Бг « Рг (а) #= 0. Для того чтобы ограничить множество значений параметра а , удобно предварительно построить функцию G, заданную на А и принимающую значения в 2А. а' £ G (а) и существует р £ Т такой, что р
а а . Тогда цикл с параметром а' можно будет выполнять только по элементам множества G (а), а не по всему множеству А. Выполнив формально все необходимые подстановки и преобразования, получим следующую программу:
BEGIN Во : = 0
FOR ALL а £ A DO
BEGIN F (а) : = 0
FOR ALL г £ R DO
IF a USES r THEN INCLUDE r IN Fo (a)
IF Fo (a) 0 THEN INCLUDE a IN Bo
END
LOOP BEGIN
FOR ALL a £ Bo DO
FOR ALL r E F (a) DO
FOR ALL a' £ G (a) DO
p
IF FOR SOME p £ T, (a') (a' -> a AND p DOES NOT GENERATE r) THEN IF r £ F (a) OR Fo (a) OR F, (a) THEN INCLUDE r INF, (a'), a'IN B,
FOR ALL a £ Bo DO F (a) : = F (a) U Fo (a)
IF B, 0 THEN OUT
FOR ALL a £ Bo J B, DO
IF a £ Bo/Bi THEN Fo (a) : = 0 ELSE
IF a £ Bi THEN Fo (a) : = FT (a)
FOR ALL a £ Вг DO FT (a) : = 0 END LOOP
END
Во всех рассмотренных примерах использован один и тот же прием, который мы называем введением и удалением избыточных вычислений. Этот прием состоит в следующем. В алгоритм вводятся новые структуры данных и действия над этими структурами. Новые действия не влияют на результат работы алгоритма и первоначально являются избыточными,; однако они прив°Дят к тому, что в алгоритме появляются новые полезные соотношения межДУ данными. Эти соотношения используются для выполнения оптимизирующих преобразований. После этих преобразований некоторые операторы становятся избыточными и убираются обычным путем. Формально метод введения и удаления избыточных вычислений можно сформулировать как применение определенного набора формальных преобразований, которые могут быть точно сформулированы.
Методы формальных преобразований, проиллюстрированные здесь на конкретных примерах, работают и на больших программах. Например, в одной из последних работ оптимизировалась программа в языке PL/I, объемом порядка 2 тыс. операторов, разработанная методом формализованных технических заданий. Применение метода введения и удаления из-
быточных вычислений позволило ускорить эту программу почти в 10 раз.
Применение метода формального преобразования к большим программам связано с большим объемом рутинной работы по анализу текстов программ и фактическому выполнению преобразований. Выполнение такой работы может быть облегчено использованием интерактивного преобразования программ в автоматизированных системах проектирования. Такие средства были реализованы в системе ПРОЕКТ автоматизации проектирования схемного и программного оборудования ЭВМ, разработанной в ИК АН УССР, и развиваются в настоящее время в системе теоретикомножественного программирования для решения задач искусственного интеллекта [8].
СПИСОК ЛИТЕРАТУРЫ
Глушков В. М. Теория автоматов и формальные преобразования микропрограмм// Кибернетика.— 1965.— № 5.
Летичевсский А. А. Об ускорении итерации монотонных операторов И Там же.— 1976.— № 4.
Глушков В. М., Капитонова Ю. В., Летичевский А. А. Теоретические основы проектирования дискретных систем И Там же.— 1977.— № 6.
Глушков В. М., Капитонова Ю. В., Летичевский А. А. О применении метода формализованных технических заданий к проектированию программ обработки структур данных И Программирование.— 1978.— № 6.
Летичевский А. А., Годлевский А. Б. Оптимизация алгоритмов в процессе их проектирования методом формализованных технических заданий И Автоматизация проектирования ЭВМ и их компонентов.— Киев, 1977.
Tarjan В. Е. Depth first search and linear graph algorithms H SIAM J. Comput.— 1972.— 1, N 2.
Hopcroft J. E. An nlogn algorithm for minimizing states in a finite automata in Kohavi (edes) 11 Theory of machines and computations.— Acad. Press.— 1971.— N 4.
Глушков В. M., Капитонова Ю. В., Летичевский А. А. Инструментальные средства проектирования программ обработки математических текстов // Кибернетика.— 1979.— № 2.
эаз.
>ам- эог- кой >ра- Та- сти- ной ско- ин->ам- эог- кой >ра- Та- сти- ной ско- ин-ИМ// Там овы года бот-s их 1ТИ-L —iata 8.—ИМ// Там овы года бот-s их 1ТИ-L —iata 8.—
>ам- эог- кой >ра- Та- сти- ной ско- ин-
>ам- эог- кой >ра- Та- сти- ной ско- ин-
ИМ// Там овы года бот-
s их 1ТИ-
L —
iata 8.—
ИМ// Там овы года бот-
s их 1ТИ-
L —
iata 8.—
РАЗДЕЛ 4
МАТЕМАТИЧЕСКИЙ ИНСТРУМЕНТАРИЙ В СИСТЕМАХ УПРАВЛЕНИЯ
иые Ки-
О ПРОГНОЗИРОВАНИИ НА ОСНОВЕ ЭКСПЕРТНЫХ ОЦЕНОК
[Кибернетика.— 1969.— № 2.)
Рассмотрим основные идеи методики прогнозирования на основе экспертных оценок, являющейся обобщением, с одной стороны, известного американского метода «Делфи», а с другой — не менее известного метода «Перт». Предлагаемый нами метод служит для определения вероятности наступления тех или иных событий и оценок вероятного их наступления. '
Исходные предпосылки и постановка задачи
Перед началом применения метода следует иметь классификатор (перечень типов) событий, с которыми предстоит работать, и начальный список экспертов по проблемам, к которым могут быть отнесены эти события. Для каждого типа проблем (событий) необходимо указать априорный вес каждого эксперта, например, по стобалльной системе. Первоначально эти веса определяются самими экспертами, в последующем они могут уточняться с помощью объективных методов.
Первый шаг применения метода — постановка задачи, т. е. перечисление событий, время и вероятность наступления которых предстоит оценить. События, которые мы будем называть заключительными, классифицируются вручную и рассылаются тем экспертам, вес которых по данному классу проблем превосходит некоторый (устанавливаемый априори) порог. В задачу эксперта входит прежде всего определение условий, позволяющих ему оценить то или иное событие. При этом эксперт должен по возможности ставить себя в положение не наблюдателя, а непосредственного участника событий.
Предположим, например, что событие 5, вероятность и время наступления которого предстоит оценить, есть осуществление высадки людей на Марс. Эксперт должен представить себя в роли конструктора, которому реально поручено выполнить эту задачу. Тогда в качестве условий он может, например, выставить выполнение событий 5Х и S2. Событие St представляет собой наличие обитаемой станции на орбите спутника Земли, а событие 52 — наличие ионного движения с энергетической установкой, обладающей определенными параметрами в отношении веса, тяги и т. п.
Для повышения ответственности экспертов можно принять, что факт выставления ими тех или иных условий при оценке события является одновременно и обязательством (в случае выполнения этих условий в будущем) взяться за реальное осуществление оцениваемого события. Подобное соглашение способствовало бы одновременно повышению объективности оценки экспертами своих собственных весовых коэффициентов.
В общем виде условие Р осуществления события S может представлять собой произвольную логическую функцию / (51? 52, ...А 5^) от неко-
торых независимых (с точки зрения эксперта) событий S1? S2, ..., 5д. Она строится с помощью конечного числа дизъюнкций, конъюнкций и отрицаний.
Далее, эксперт должен оценить условную вероятность РР (S) наступления события S при выполнении условия Р и наиболее вероятную величину времени ТР (S) между временем выполнения условия Р и временем наступления события S (если оно вообще наступит). При этом, разумеется, не исключается (и даже желательна) возможность оценки безусловной вероятности наступления события S и полного времени, считая от настоящего момента до его наступления. Этот случай соответствует обращению условия Р в тождественно истинное событие (пустому множеству событий Sv S2, ..., Sh).
Сеть событий и ее стабилизация
Анкеты экспертов служат прежде всего для построения сети событий, аналогичной пертовской сети. При этом каждой оценке эксперта РР (S) и ТР (S) соответствует «работа» на пертовской сети; ТР (5) представляет собой оценку продолжительности этой работы. События S^ S2, ..., 5д, входящие в условие Р = f (S^ S2, ..., S^, соединяются с событием S фиктивными работами нулевой продолжительности. Для упрощения предположим, что получающаяся сеть удовлетворяет обычным пертовским требованиям, в частности, требованию отсутствия петель. С этой целью при обработке анкет экспертов принимаются специальные меры: возвращение анкет для исключения тех или иных условий, аннулирование частей анкет и т. п. Впрочем, в отличие от классического «Перта» предлагаемая методика может быть расширена таким образом, чтобы включить в рассмотрение .также и сети с петлями.
Ввиду того что ответы экспертов вводят, вообще говоря, новые события, последние посылаются для оценок новым экспертам и т. д., пока сеть не стабилизируется. В каждом последующем туре оценок участвуют и эксперты, принявшие участие в предыдущем туре, в связи с чем им посылается фрагмент сети, полученной также на предыдущем туре. Этот фрагмент (1-окрестность события 5) включает перечень всех элементарных событий 5Х, 52, ..., 5П, выставленных в числе условий хотя бы одним экспертом, принимавшим участие в оценке данного события S. Эксперты по данному событию S в новом туре могут менять свои условия, включая в них любые элементарные события 51? 52, ..., Sn (и меняя соответственно свои оценки). В ряде случаев возможно пользоваться расширенными фрагментами, включая в них не только события 5Х, 52, ..., 5П, но и события,; их обуславливающие (2-окрестность события 5) и т. д. Эксперт, выставивший те или иные условия Sn 52, ..., 5Д, должен указать в анкете имена возможных экспертов для оценки этих условий. Тем самым список экспертов будет расширяться до тех пор, пока не произойдет стабилизация сети.
Обработка стабилизированной сети событий
В стабилизированной сети без петель все события разбиваются на слои. В первый входят все события, получившие только безусловные оценки вероятности (и ожидаемого времени) своего наступления. А для оценки событий, лежащих в i-m слое (/ > 2), в качестве условий используются лишь события из слоев с номерами, меньшими, чем I.
Дальнейшая обработка построенной сети производится следующим образом. Последовательно, слой за слоем, вычисляются абсолютные вероятности наступления всех составляющих слой событий и распределение абсолютного времени ожидаемого их наступления, а также оценки разброса этих величин (среднеквадратичные ошибки или квантили).
Распределение абсолютного времени с практической точки зрения наиболее удобно задавать, фиксируя заранее конечное число моментов времени, например: tx = 1970, £2 1975, Ц = 1980, £4 = 1990, t5 = = 2000, Z6 = 2025, Z7 = 2050, t8 = 2100 г., добавляя к ним всегда бесконечное время (в данном случае Z9 = оо).
' Распределение абсолютного времени наступления любого события S рассматриваемой сети будет характеризоваться вектором вероятностей (Рх, Р2, ..., Р^ Pooh где Pi (5) представляет собой оценку вероятности наступления события 5 до момента времени ^. В частности, Р^ = Р представляет собой оценку безусловной вероятности наступления события за неограниченное время. Через (о1, о2, ... ад, Ооо) будет обозначаться вектор среднеквадратичных погрешностей соответствующих оценок.
Оценка вероятностей Рч производится на основе обычного усреднения (с учетом весов экспертов) оценок, даваемых отдельными экспертами. Что же касается этих последних, то они получаются последовательно^ слой за слоем.
Для события S из первого слоя экспертом дается оценка абсолютной вероятности Р и абсолютного времени t наступления этого события. Тогда соответствующие (одиночные) оценки данного эксперта дадут значение Pt = 0 для всех ti <L t и Pi = Р для всех h ^ I. Если же событие S не из первого слоя и для него дана оценка условий вероятности q и относительного времени выполнения т данного события S при условии Р = = / (5Х, 52, ..., S^Y то Для событий Sn 52, ..., 5д по принятому нами соглашению должны уже быть известны абсолютные (усредненные) оценки вероятностей их наступления и соответствующие оценки для всех других компонент вектора вероятностей. Для любой из этих компонент Pi (включая и Роо) будут иметь место соотношения:
Рг №^R) = Pt (Q)Pi (7?),
Pi OQ^l-Pt «?),
Pi (Q\/R) = Pi «?) + Pi (R) - Pi (Q) Pi (R),
где Q и R — любая пара независимых событий. Эти соотношения, в силу нашего предположения о независимости событий 5Х, 52, ..., S^ дают возможность подсчитать значение соответствующей компоненты Р^ (S) вектора вероятностей для события S.
Пусть теперь Р (I) — вероятность того, что событие Si произойдет не позже, чем в момент времени ;, a q (т) — что событие S произойдет не позже, чем через время т после наступления события St. Тогда вероятность г (t) того, что событие S наступит не позже, чем в момент времени Z, выразится формулой
i
г (0 = j q V — т) d (Р (т)).
о
Используя соответствующую дискретную аппроксимацию этой формулы, мы получаем возможность вычислять значение любой компоненты вектора вероятностей рассматриваемого события S по оценке данного эксперта.
Повторяя этот процесс и проводя необходимые усреднения, мы получим, в конце концов, оценку вектора вероятностей и разброса его значений для интересующего нас заключительного события.
Дальнейшее уточнение результатов
При дальнейшей работе с сетью опросы экспертов можно систематически повторять. Изучая динамику изменения оценок вместе с информацией о действительном времени наступления тех или иных событий, можно предложить различные приемы внесения поправок в веса экспертов. Выбор того или иного из этих приемов зависит от степени предпочтительности правильности начальных оценок по сравнению с более поздними, от желания учитывать степень правильности не только конечного результата (оценки времени), но и путей его достижения (правильности выбора условий). Поэтому мы не будем пока уточнять эти приемы.
Работа с построенной сетью может предусматривать возможность уточнения тех или иных частных оценок для составляющих ее событий (например, путем привлечения новых экспертов или постановкой новых исследований). Для каждого события это уточнение будет требовать определенных затрат (вообще говоря, тем больших, чем выше слой, которому принадлежит данное событие). Необходимо поэтому разработать методику нахождения рационального выбора этих уточнений.
Предположим, что из какого-либо соображения, находящегося вне сферы наших рассмотрений, установлено, что наибольший интерес представляет уточнение оценки вероятности Рг (S) наступления заключительного события 5 до момента времени tt- Для каждого события 5;, входящего в построенную сеть, определим изменение оценки вероятности Рг (S') при максимальных изменениях компонент вектора вероятностей события Sy& допускаемых имеющимися экспертными оценками. Стоимость эксперимента по уточнению оценки вектора вероятностей для события Sj, отнесенную к величине указанного изменения (удельную стоимость), естественно выбрать в качестве критерия для выбора события Sj, оценка вектора вероятностей которого подлежит уточнению в первую очередь.
ОБОБЩЕННЫЕ ДИНАМИЧЕСКИЕ СИСТЕМЫ И ПРОЦЕССИОННОЕ ПРОГНОЗИРОВАНИЕ
[Проблемы прикладной математики и механики.— М.: Наука, 1971]
Существуют два основных подхода к постановке задачи прогнозирования, которые мы будем называть событийным и процессионным. При событийном подходе требуется оценить время наступления того или иного события, процессионный имеет своей целью оценку состояния того или иного объекта в заранее заданные моменты времени. Один из методов прогнозирования применительно к событийному подходу уже рассматривался в работе [1]. Целью настоящей работы является описание одной из перспективных форм организации прогнозирования, использующей процессионный подход. Предлагаемый метод представляет собой развитие так называемого метода сценариев, широко применяющегося для прогнозирования развития конфликтных ситуаций.
Основу прогнозной модели составляет описание прогнозируемого объекта и условий, в которых он существует, в виде обобщенной динамической системы. Состояние объекта задается системой параметров у1У у2, ..., уП1 являющихся функциями времени. Однако в отличие от обычных динамических систем среди этих параметров могут быть не только обычные вещественные величины, но также целочисленные и так называемые качественные параметры. Последние представляют собой переменные с конечными областями определения.
Таким образом, каждый из параметров описывается своим типом (вещественный, целочисленный или качественный) и областью определения, задаваемой либо соответствующим числовым интервалом, либо перечислением всех возможных значений. Примерами описаний параметров могут служить: а — вещественный [0, оо]; b — целочисленный [—2, 4]; d — целочисленный [—2, 4]; d — качественный (плохо, удовлетворительно, хорошо).
Легко понять, что всякий качественный параметр может быть отождествлен с целочисленным параметром, применяющим значения на конечном отрезке. Например, упомянутый выше параметр d заменяется целочисленным параметром dx с областью определения [1, 3]. Условимся, что отождествление областей определения для параметров d и dY производится слева направо, так что 1 соответствует значению «плохо», 2 — «удовлетворительно» и 3 — «хорошо».
Описание развития рассматриваемой динамической системы во времени определяется множеством ограничений (закономерностей) нескольких основных типов. Для числовых параметров (вещественных и целочисленных) такие ограничения могут быть в виде систем обыкновенных алгебраических или конечноразностных уравнений и неравенств. В случае, если зависимость между вещественными параметрами выражается в действительности дифференциальными уравнениями, ее можно представить в рамках требуемой точности конечноразностными уравнениями.
Для качественных параметров запишем ограничения: если А, то В, где А и В — некоторые условия. Простейшие условия имеют вид а ^ = = с. а (^) = b ^Y где I, tXl Z2 — некоторые моменты времени; а (£), а (^), b (£2) — значения параметров в эти моменты, ас — постоянное значение. Для числовых параметров простейшие условия могут строиться следующим образом:
а(^)>^, а^^с, a(t)<Zc, a(t)^.c, а (у > b (t2Y a (t^)^ b (t2Ya (Ы < b (<2), a (t^ ^ b (t^).
Сложные условия строятся в виде логических функций (используются конъюнкции, дизъюнкции и отрицания) от простейших условий.
Отношения > и < могут быть введены также и для значений качественных параметров. Мы будем предполагать, что такие отношения введены и имеют обычный смысл всякий раз, когда значения качественных параметров представляются числами. В этом случае мы будем определять операции сложения и вычитания. Однако, имея в виду некоторые практические аспекты проблемы, все суммы, превосходящие верхнюю грань возможных значений параметра, будем считать равными этой грани. Аналогичное соглашение принимается в случае вычитания для разностей, меньших соответствующей нижней грани. Например, если область определения параметра состоит из целых чисел от 1 до 5 включительно, то принимается, что 3 + 3 = 5, 3 + 4 = 5, 2 — 3 = 1 и т. д.
Используя в качестве первичных термов значения параметров в те или иные моменты времени (постоянные или переменные вида t, t + Аг, I — MY константы, и опираясь на введенные операции (сложение и вычитание для всех параметров, умножение — для целочисленных и вещественных и деление для вещественных параметров), мы будем строить простые арифметические выражения.
Наконец, с помощью рассмотренных выше условий, по аналогии с АЛГОЛ-60, можно строить произвольные арифметические выражения. Тогда уравнения и неравенства в системе ограничений, о которой шла речь выше, записываются в виде А = В или А > В, А < В, А ^ В, А ^ В, где А и В — арифметические выражения со значениями одного и того же типа. Разумеется, в случае необходимости для вещественных параметров можно использовать возведение в степень, тригонометрические функции, логарифмы и т. п.
Все ограничения, о которых идет речь, задаются экспертами. Каждый из экспертов, как правило, ограничивает область своих заключений относительно небольшой группой параметров. Поскольку, однако, общее число экспертов достаточно велико (оно может достигать многих тысяч и даже десятков тысяч), в системе достигается получение необходимых ограничений для всех параметров. Для каждого из введенных ограничений эксперт производит оценку степени своей уверенности (выражаемую в процентах) в том, что данное ограничение действительно имеет место.
Для осуществления прогнозирования в ЭВМ вводится прежде всего начальное состояние изучаемой системы, т. е. совокупность значений всех определяющих ее параметров в исходный момент. Далее в ЭВМ помещаются все ограничения и в соответствии с ними проводится выбор последовательных моментов времени tv t2l ..., t^ в которое будет производиться прогнозирование состояний рассматриваемой системы. Выбор указанных моментов определяется заданными шагами в конечноразностных уравнениях, а также величиной запаздывания М в зависимостях для качествен-
ных параметров вида: если А (£), то В (t + Д£). Например, если a (t) = = aY и Ъ (/) = Bv то с (t + АО = Cv
Специальная программа, просматривая все введенные ограничения^ производит случайный выбор параметров для следующего момента времени так, чтобы этот выбор удовлетворял соответствующим ограничениям» Таким образом, получается случайная реализация траектории рассматриваемой динамической системы. Этот процесс повторяется для получения достаточного числа таких реализаций, причем если степень уверенности эксперта в каком-либо введенном им ограничении равна, скажем, 80 %, то лишь в восьми траекториях (или шагах) из десяти это ограничение будет приниматься во внимание. В остальных двух случаях выбор значений параметров будет производиться так, как если бы его просто не существовало.
Наличие достаточного количества случайных траекторий позволяет провести статистическую обработку значений тех или иных параметров в интересующие нас моменты времени, т. е. найти их математические ожидания и вероятные отклонения. Результаты такой обработки и будут представлять собой требуемый прогноз. При этом, несмотря на возможные большие вариации траекторий в целом, значения отдельных параметров могут получить достаточно устойчивые (с малыми вероятностными отклонениями) оценки.
В ряде случаев может оказаться, что выбор значений тех или иных параметров (называемых управляющими) целиком или частично зависит от лица или лиц, управляющих ходом развития рассматриваемой динамической системы. Например, если речь идет о человеческом организме, к числу таких параметров относится степень интенсивности тех или иных лечебных процедур (физических упражнений, частоты и доз приема лекарств и т. п.).
В таком случае задача прогнозирования перерастает в задачу управления рассматриваемой системой. В случае, если на множестве состояний S системы построена та или иная оценочная функция / (5), может быть поставлена задача нахождения оптимального управления, т. е. выбора значений управляющих параметров во все рассматриваемые моменты времени, при котором математическое ожидание величины / (5*), где 8* — состояние системы в конце рассматриваемого промежутка времени, будет наибольшим или наименьшим. Возможна также постановка краевой задачи управления, где требуется найти управление, обеспечивающее максимальную вероятность попадания заключительного состояния S* в некоторую фиксированную заранее область.
В принципе решение подобных задач могло бы быть обеспечено случайным перебором всех возможных управлений (или, по крайней мере, достаточно большого их числа). Однако на практике подобный метод для сколько-нибудь сложных систем не может быть реализован даже при использовании самых мощных ЭВМ. Поэтому в современных условиях наиболее перспективными являются человеко-машинные методы, когда человек на основании своего опыта предлагает те или иные варианты управлений, кажущиеся ему лучшими, а ЭВМ производит их оценку, развивая описанным выше путем случайные реализации траекторий при выбранном управлении.
Эффективная реализация подобных методов требует разработки специальных языков и операционных систем для управления процессами общения человека с ЭВМ. В результате такого общения в рассматриваемой модели могут меняться не только предлагаемые управления^ ко и те или 238
иные из введенных ограничений, а также может увеличиваться или уменьшаться степень уверенности в правильности отдельных ограничений и т. д.
Развитая операционная система для работы с моделью должна позволять задавать не только описанные выше простейшие управления, т. е. фиксированную последовательность управляющих воздействий, но и произвольные алгоритмы управления. В частности, должна быть предусмотрена возможность обусловливать применение тех или иных управляющих воздействий состоянием объекта и т. п.
СПИСОК ЛИТЕРАТУРЫ
Глушков В. М. О прогнозировании на основе экспертных оценок // Кибернетика.— 1969.— № 2.
О ПОСЛЕДОВАТЕЛЬНОЙ ДЕЗАГРЕГАЦИИ
В СТАТИСТИЧЕСКОЙ МАКРОЭКОНОМИЧЕСКОЙ МОДЕЛИ
[УСиМ.—1972,—№ 21
Рассмотрим статистическую модель Леонтьева X'™ = Ах + <р, где (х = хг, х2, ..., хп) — вектор выпуска продукции, включающий полный (не агрегированный) перечень продуктов, выпускаемых рассматриваемой макроэкономической системой; ф = (фь ф2, ..., фп) — вектор потребления; А = || а^ || — соответствующая технологическая матрица.
Предположим, что все продукты агрегированы в т групп: уг = = (^ + Х2 + ... + Х^ у2 = (^il+i + Жг|+2 + ... + Жг2),..., ут =
— ^^„^i + х^^^ + ... + ^гт)- Компоненты вектора потребления ф2 ~ (4*17 4*27 • ••♦ Фт) для агрегированных таким образом продуктов представляются, очевидно, в виде сумм Ф1 = фх + Ф2 + ••• + фгР ф2 ™ = фг1+1 + ... + фг2, ..., фт = Ф^-! + ••• + Tiw- Коэффициенты ТвХНО- логической матрицы В = II Ьм || агрегированной модели у = Ву + ф задаются очевидными формулами:
Ьм = 5 S ^аи №’ 1 = ^ 2’ • ’ т)'(1)
г=гк_^Н ^i^j-t-l
Здесь через а.^ обозначены коэффициенты, показывающие относительную долю /-го первичного продукта в Z-м (агрегированном) продукте:
“^ = ^iz_1^l +^i,_1+2+ - +®iz (Xit-' < Xj ^ Xil’ l = v^ , my
(2)
Идея метода последовательной дезагрегации состоит в том, что на каждом шаге дезагрегируется лишь один агрегированный продукт, после чего полученная система линейных уравнений используется с целью уточнения требуемого выпуска первичных продуктов для рассматриваемой дезагрегированной группы. Уточнение производится путем подстановки в правую часть системы старых значений х^ и ук, т. е., иными словами, путем выполнения одного шага решения полученной системы итерационным методом.
Такое уточнение производится последовательно для всех т агрегированных продуктов. При этом можно проводить вычисления двумя различными путями. В первом случае улучшенные значения Хг (а, значит, и соответствующие уку полученные на предыдущих шагах, используются па всех последующих шагах. Во втором случае для вычислений на всех шагах используются одни и те же (старые) значения xt и у к* В дальнейшем мы будем придерживаться второго способа вычислений^ более легкого для исследования.
Легко видеть, что выполнение всех т уточнений по второму способу эквивалентно одному шагу решения итерационным методом первичной {полностью дезагрегированной) системы х = Ах + ср. Обозначая старое значение вектора х через ж', а новое — х", получим: х = Ах + ф. Если xQ есть точное решение уравнения х = Ах + Ф, то х" — х° = А (х' — — х0), откуда I х" — х° I = I А I • | х — х° |.
Поскольку определитель технологической матрицы А всегда меньше единицы^ то уточненное значение вектора х будет ближе к истинному его значению, чем начальное приближение х". Это обстоятельство в только что высказанном виде хорошо известно в теории статических линейных моделей. Новый элемент, специфический для метода последовательной дезагрегации, выявляется при переходе к управлению на основе непрерывного уточнения ранее составленного плана.
Такое уточнение делается каждый раз, когда происходит то или иное изменение в первичной (дезагрегированной) системе х = Ах + ф, т. е. изменение вектора потребления ф или коэффициентов технологической матрицы А. Как видно, такие изменения приводят к сколько-нибудь существенным изменениям лишь относительно небольшой части компонент первичного вектора выпуска ж, которые мы будем называть варьируемыми компонентами.
Удаляя последние из агрегированных переменных yv у21 ..., yms придем к новым агрегированным переменным У^ у^ - Ут1 (#h ^ ^)- Если теперь добавить к этим переменным дезагрегированную часть, состоящую из всех варьируемых компонент х^ х^, ..., хН1 и решить соответствующую систему уравнений, то, вследствие проведенных выше рассмотрений, получим более или менее точное (в рамках сделанных предположений) приближение для нового, скорректированного плана. Степень этого приближения зависит, очевидно, от тонкости критерия, на основании которого производится отделение варьируемых компонент от неварьируемых.
Абсолютным критерием является полный просмотр системы х = = Ах + Ф с выделением всех параметров, затрагиваемых заданной начальной вариацией. Однако при таком подходе число варьируемых параметров может оказаться непомерно большим, охватывая практически все первичные продукты. Поэтому приходится обрывать цепи зависимостей, ориентируясь на ту или иную заданную точность. Чтобы понять сущность этого приема, предположим, например, что начальная вариация состоит в том, что потребление фг первого продукта увеличивается на 10 %. Величина выпуска хг первого продукта будет таким образом варьируемым параметром.
Рассмотрим какой-либо продукт ^, необходимый для выпуска первого продукта. Из имевшегося ранее (до вариации) решения известна относительная доля продукта г1? затрачивавшегося на выпуск первого продукта. Если эта доля мала (скажем, меньше, чем 0.01), то естественно не считать продукт 1г варьируемым. Такой прием приводит к достаточно хорошим результатам в случае, когда коэффициенты полных затрат имеют тот же порядок, что и соответствующие коэффициенты прямых затрат. А для макроэкономических задач это обычно имеет место.
Другой прием сокращения числа варьируемых параметров основан на следующем: пусть начальная вариация, в отличие от рассмотренного примера, вызывает значительное изменение группы параметров xit1 Жг2, ... ..., Хгт1 составляющих одну или несколько групп, агрегируемых в укрупненные параметры у$0 ..., yjb. Если на основании тех или иных соображе-
ний известно, что ожидаемые приращения параметров хг внутри каждой группы уг примерно пропорциональны имевшимся до вариации значениям^ то соответствующие параметры xt можно, очевидно, не включать в число варьируемых. Варьироваться будет лишь соответствующий агрегированный параметр у^ а новые значения х> можно вычислить по их старым относительным долям в объединяющем их агрегированном продукте у^. Дальнейшее усовершенствование этого приема основано на изменении групп агрегируемых продуктов с целью добиться выполнения используемого в нем условия.
Использование описанных методов уточнения плана много раз подряд на протяжении достаточно большого промежутка времени может приводить к накоплению ошибок (малых на каждом отдельном шаге, но значительных в совокупности). Поэтому необходимым дополнением к методу последовательной дезагрегации, превращающим его в действительный инструмент управления, является современное внесение поправок при возникновении сколько-нибудь заметных систематических дефицитов или избытков тех или иных первичных продуктов х^
Идея управления на основе процесса постоянного уточнения плана применима не только к статическим, но и к динамическим моделям. В этом случае в дополнение к уточнениям, вызываемым теми или иными вариациями, должно производиться постоянное перемещение конечной точки заданного планового периода. При этом, например, годовой плане составленный 1 января, при уточнении, производящемся в феврале, должен охватить период до февраля следующего года, в феврале — до марта и т. д. Тем самым план получает два новых важных свойства: непрерывность, заключающуюся в непрерывном пролонгировании планового периода, и динамичность, означающую возможность внесения любых необходимых поправок без полного пересчета всего плана в целом.
О ПОСЛЕДОВАТЕЛЬНОЙ ОПТИМИЗАЦИИ В ЛИНЕЙНЫХ МАКРОЭКОНОМИЧЕСКИХ МОДЕЛЯХ
[УСиМ,— 1973,— № 4]
Рассмотрим линейную макроэкономическую модель х = Ах + с, где А — неотрицательная (и X п)-матрица;
ci
с = С.2
есть вектор конечного выпуска, который пока также будет считаться неотрицательным. В дальнейшем будем предполагать, что матрица Л* = = (Е — Л)”1 существует и неотрицательна. Неотрицательные матрицы Л, удовлетворяющие этому дополнительному условию, условимся называть вполне продуктивными..
Для вполне продуктивной матрицы Л система уравнений х = Ах + + с имеет решение при любом с. Это решение, равное Л*с, обозначим через с* и назовем вектором полного выпуска.
Элементы матрицы А = || а^ || представляют собой так называемые нормативы прямых затрат: элемент аг? равен расходу t-ro продукта в /-й отрасли при производстве одной единицы /-го продукта (i, / = 1,2, ..., nY Обычно предполагают, что а^ = 0 для всех г = 1, 2, ..., п, что, как известно, не нарушает общности, поскольку всегда возможно отнести все затраты atj к чистому выпуску, исключив прямые затраты продукта на производство самого себя.
Элементы матрицы Л* = || а^ || — это нормативы полных затрат: элемент а^ равен суммарным затратам f-ro продукта, которые надо произвести во всех отраслях с целью обеспечения выпуска одной единицы /-го продукта (/, / = 1, 2, ..., nY
Для вполне продуктивных матриц имеет место следующее предложение:
Лемма 1. Если матрица А вполне продуктивна, то ряд Е + А + + Л2 + ... + Ак + ... сходится к матрице А* = (Е — Л)-1.
Доказательство. Поскольку матрица А вполне продуктивна, то из х = Ах + с вытекает, что вектор х = А*с неотрицателен при любом неотрицательном векторе с. Вместе с тем из х = Ах + с следует, что
х = А ^Ах + с) + с = А^х + Ас + с, х — А2х 4- А2с + Ас + с + • • • д
х = Awx + Akc + Ak~xc + • • • + Ac 4- с
или (£ + А 4~ Л2 + • • • 4~ ^h) с = х — Ак+'х.
Вектор Л^ неотрицателен; поэтому (Е + А + А2 + ... + Л^) с ^ х при любых к = 1, 2, ... и с ^ 0. Полагая, что с; = 1, а с7- = 0 при / 5^= 1, в левой части получим сумму i-x столбцов матриц Е. А. .... Ак. Поскольку она не убывает с ростом к и ограничена, a i может пробегать все значения от 1 до п. то тем самым доказана сходимость ряда Е + А + А2 + ... ... 4- Ак + ... Из элементов матричной алгебры следует, что суммой ряда будет матрица ^Е — Л)"1, что и требовалось доказать.
Введем теперь в рассмотрение матрицу В = || Ь^ || прямых затрат ресурсов: элемент Ь^ этой матрицы представляет собой затраты к-го ресурса (человеко-дней, станко-часов и т. п.) в /-й отрасли, необходимые для производства одной единицы /-го продукта. Через В* || Ъ^з || обозначим матрицу полных затрат ресурсов: элемент bh- равен суммарным затратам к-го ресурса, которые необходимо произвести во всех отраслях для обеспечения выпуска одной единицы /-го продукта. Ресурсы предполагаются внешними по отношению к системе х = Ах + с. Их число т не обязательно совпадает с числом продуктов п. Поэтому матрицы В и В* в отличие от матриц Л и Л* в общем случае будут не квадратными, а прямоугольными. В случае, когда имеется лишь один учитываемый ресурс, матрицы В и В* вырождаются в вектор-строки, для которых мы, однако, сохраним те же обозначения, что и для общего случая.
Из определения матриц В и В* вытекает, что
В* = В А*. (1)
Ъ* = В* с — Вс* = ВА*с.Ъ* = В* с — Вс* = ВА*с.(2)(2)Вектор Ъ* полных затрат ресурсов для обеспечения конечного выпуска с представится формулой
Ъ* = В* с — Вс* = ВА*с.
Ъ* = В* с — Вс* = ВА*с.
(2)
(2)
При планировании выпуска предполагается
также заданный вектор
61
6п
имеющихся запасов ресурсов рассматриваемого планового выполняться неравенствоимеющихся запасов ресурсов рассматриваемого планового выполняться неравенствоЬ*Ь*(с учетом вновь вводимых) на протяжении периода. Для допустимого плана должно
имеющихся запасов ресурсов рассматриваемого планового выполняться неравенство
имеющихся запасов ресурсов рассматриваемого планового выполняться неравенство
Ь*
Ь*
(3)
В случае, если оно не выполняется, имеются так называемые кри
тические ресурсы, для которых у соответствующих им компонент имеет
место противоположное неравенство
/* 6j.(4)*
План С конечного выпуска всегда можно сделать допустимым путем его умножения на положительную константу, меньшую единицы, т. е. путем пропорционального уменьшения выпуска всех продуктов. Оставляя подобное тривиальное решение на крайний случай, будем пытаться сделать первоначально заданный план допустимым за счет изменения нормативных матриц А и В на некоторые величины ДЛ и ДБ в рамках возможных технологических усовершенствований. Сюда входит применение технологических процессов или конструкций с более экономными затратами продуктов и ресурсов, а также изменение относительных долей первичных продуктов в агрегированных продуктах, которые обычно рассматриваются в макроэкономических моделях.
К нетривиальным решениям отнесем также изменения вектора с на некоторую величину Ас без изменения потребительской ценности суммарного конечного выпуска. Это может происходить за счет замены одних продуктов другими или за счет подключения внешней торговли. Поскольку эти изменения касаются непроизводственного потребления, назовем их потребительскими, в отличие от технологических изменений АЛ, А5.
Технологические изменения составляются из первичных технологических изменений, каждое из которых касается технологии производства одного из продуктов, например, f-го. Соответствующее приращение (А;Л, А^В) обычно затрагивает обе матрицы А и В одновременно, но действует лишь на их Z-e столбцы. Приращения такого рода назовем одностолбцовыми. В частном случае подобное парное приращение может вырождаться в приращение лишь одной из матриц: (А;Л, 0), (0, Aj5). В дальнейшем рассматриваются произвольные технологические приращения (АЛ, А5), которые сохраняют неотрицательность матриц Л и В и полную продуктивность матрицы А.
Первичные потребительские предложения могут приводить к произвольным изменениям Ас вектора конечного выпуска с. При включении внешней торговли эти изменения могут привести даже к тому, что отдельные компоненты вектора с делаются отрицательными (в случае, когда за счет внешней торговли удовлетворяется нужда не только в конечном продукте, но и в продукте, используемом в процессе производства). В то же время, если не делаются ненужные закупки, вектор с* полного выпуска при любых изменениях должен оставаться неотрицательным. В дальнейшем будем предполагать это условие выполненным:
с* > 0. (5)
Можно предполагать к тому же, что до начала процесса улучшения плана (за счет технологических и потребительских изменений) все компоненты вектора полного выпуска строго положительны:
с*>0 (г = 1, 2, . .. , га). (6)
Действительно, нулевой компоненте соответствует в этом случае продукт, который не производится, а при отсутствии внешней торговли (что имеет место вначале) и не потребляется. Заметим, что такой продукт можно просто исключить из дальнейшего рассмотрения. Любые изменения, о которых идет речь, приводят к некоторому приращению вектора ДЬ*. Если АЬ* ^ 0, причем хотя бы для одной компоненты это неравенство строгое, то изменение приводит к экономии затрат ресурсов и должно рассматриваться как полезное. При ДЬ* ^ 0 соответствующее предложение бесполезно, а в случае строгости неравенства хотя бы для одной компоненты даже вредно. При наличии более одного ресурса могут иметь место неопределенные изменения, дающие экономию одних ресурсов и увеличивающие расход других.
При оптимизации плана обычно имеют дело с одним критическим ресурсом (например, с суммарными трудозатратами). В таком случае целью является получение плана, обеспечивающего минимум расхода именно этого ресурса. Существует два различных подхода к решению задачи оптимизации: разовый и последовательный. При разовом подходе, собрав все возможные первичные изменения, пытаются сразу найти такую их комбинацию, которая обеспечит минимум расхода критического ресурса. Этот подход требует применения методов линейного и даже нелинейного (поскольку меняется одновременно А, В и с) программирования и, как
правило, приводит к весьма сложным вычислениям. Кроме того, при ре" альном планировании в момент составления плана обычно не располага" ют всей суммой возможных первичных изменений: предложения такого рода поступают и после составления плана, требуя его непрерывной коррекции. Нельзя не учитывать также и того, что предлагаемые изменения не даются даром и может просто не хватить сил и средств для их одновременной реализации.
При последовательном подходе первичные изменения анализируются поодиночке, последовательно включаются в план и реализуются. Этот подход позволяет осуществлять непрерывное планирование за счет постоянной коррекции и пролонгирования плана. Он хорошо увязывается с процессом последовательного развития наших знаний и научно-техническим прогрессом.
Все эти особенности делают последовательный подход наиболее предпочтительным, а иногда (при быстрых темпах научно-технического прогресса) единственно возможным. Его преимущество сделалось бы особенно весомым, если бы удалось решить две проблемы: во-первых, осуществлять быстрый (по сравнению с первоначальным расчетом) перерасчет плана для любого первичного изменения, а во-вторых, иметь уверенность, что при последовательной оптимизации можно достичь действительно наилучшего плана. Последний вопрос является тем более весомым, что для случая не вполне продуктивных матриц нетрудно построить пример, когда любое из имеющихся первичных изменений приводит к ухудшению плана, а их комбинация его улучшает.
В самом деле, пусть
л = |° °Д1 II 0,5 0 IIл = |° °Д1 II 0,5 0 IIS = l|l,4 с =S = l|l,4 с =1ill1illи пусть в нашем распоряжении имеются два зывающие приращенияи пусть в нашем распоряжении имеются два зывающие приращенияпервичных изменения, вы-первичных изменения, вы-0 01 00 01 0и Д2Л =и Д2Л =0 1о о0 1о о
л = |° °Д1 II 0,5 0 II
л = |° °Д1 II 0,5 0 II
S = l|l,4 с =
S = l|l,4 с =
1ill
1ill
и пусть в нашем распоряжении имеются два зывающие приращения
и пусть в нашем распоряжении имеются два зывающие приращения
первичных изменения, вы-
первичных изменения, вы-
0 0
1 0
0 0
1 0
и Д2Л =
и Д2Л =
0 1
о о
0 1
о о
матрицы А.Матрица В предполагается неизменной. В чины 6* полных затрат ресурсов (котораяматрицы А.Матрица В предполагается неизменной. В чины 6* полных затрат ресурсов (котораяром)ром)исходном состоянии для вели- в этом случае является скаля-исходном состоянии для вели- в этом случае является скаля-имеем следующее значение:имеем следующее значение:
матрицы А.
Матрица В предполагается неизменной. В чины 6* полных затрат ресурсов (которая
матрицы А.
Матрица В предполагается неизменной. В чины 6* полных затрат ресурсов (которая
ром)
ром)
исходном состоянии для вели- в этом случае является скаля-
исходном состоянии для вели- в этом случае является скаля-
имеем следующее значение:
имеем следующее значение:
г»; = 5Л*С = II 1,1 «41^г»; = 5Л*С = II 1,1 «41^0,510,51= 4.= 4.
г»; = 5Л*С = II 1,1 «41^
г»; = 5Л*С = II 1,1 «41^
0,5
1
0,5
1
= 4.
= 4.
При принятии первого первичного предложения эта величина приобретает значение•
6i*=s^c=iii,im-|Д °:50,51
Такое же значение величина Ъ* приобретает и при принятии (в одиночку) второго первичного предложения: Ь- = 16. Поскольку затраты ресурса возрастают, оба указанных предложения, взятые поодиночке, вредны. В то же время при принятии обоих предложений одновременно затраты ресурса 61,2 сделаются отрицательными:
Ь^-ВА^с =|| 1,11|- (- 4/6).Ь^-ВА^с =|| 1,11|- (- 4/6).11,51,5111,51,51:н-:н-
Ь^-ВА^с =|| 1,11|- (- 4/6).
Ь^-ВА^с =|| 1,11|- (- 4/6).
11,5
1,51
11,5
1,51
:н-
:н-
Поскольку 61,2 < b*, то формально (отвлекаясь от экономического смысла вопроса) составное предложение следует считать полезным.
Покажем, однако, что в реальных экономических моделях при учете полной продуктивности матрицы А положение меняется: составное предложение не может быть полезным, если не будет полезным хотя бы одно из составляющих его первичных предложений. Перед тем как доказывать справедливость этого факта, покажем, как решается первая из сформулированных выше проблем. Установим прежде всего справедливость следующей теоремы.
Теорема 1. Если АгЛ — одностолбцовое приращение (для i-го столбца вполне продуктивной матрицы А), а матрица А1 = А + ^гА также вполне продуктивна, то соответствующее приращение АгЛ* матрицы А* — {Е — Л)-1 может быть найдено по формулеv
Д^* = т=т л*д-лл*>(7)
где а — элемент матрицы Di = Л* АгЛ, стоящий на пересечении 1-го столбца и i-й строки. Этот элемент меньше единицы:
а<1.(8)
Доказательство. Из А* (Е — А) = Евытекает, что А*А = = А* — Е. Тогда Е — А*М = Е — А^А' + Л*Л = Е — А^А' + + Л* — Е = А* (Е — Л'), или (Е — Di) = А* (Е — А'). Отсюда (Е — Di) А'* = Л*. Поскольку в матрице Di все столбцы, кроме Z-ro, нулевые, то в Z-й строке матрицы Е — D все элементы, кроме Z-ro, равны нулю, Z-й же элемент равен, очевидно, 1 — а. Но тогда ЦЕ — Di) А'*]ц = = (1 — а) ан = [Л*In = ац. Поскольку для вполне продуктивной ма- рицы А имеет место разложение А* = Е + А + Л2 + ... (лемма 1), то ан > 1. Аналогично а*н ^ 1. Отсюда 1 — а =>0 и, следовательно,
а < 1.
Легко видеть, что для матрицы Di имеет соотношение D^ = aDn Используя его, получим (Е — Di) ^5 + ^^.^ D^ = Е. Таким образом$ (Е — Dt)-1 = Е + Di- Далее,
Д{Л* = [£ — (Л + Д,Л)Г'(5—Л)-‘= №-(Е- АГ1 ДчАГЧЕ — АГ1-
— (Е — АГХ= Ф — Di)-1 А* — А* = ^Е + -р^- Pi) А* — А* =
= -j-i— DtA* = -f-J— A*AtAA*.1 — a1 — a
Тем самым АгЛ* = a Л * А^ЛЛ * и a < 1, что полностью доказывает теорему.
Вычисление приращения А,Л* следует проводить в следующем по- (/1V \
A* q-_a АгЛ «Л* При этом в первой (внутренней) скобке следует выполнить п умножений, во второй (объемлющей) — пг умножений и п (п — 1) сложений. Последнее умножение /"матриц j~ a ^’
и Л*^ требует п2 умножений. В общей сложности вычисление Д[Л* по формуле (7) требует Зга2 арифметических операций. При попытке прямого счета приращения Д;Л* по формуле ДгЛ* = (В — Л — ДгЛ)-1 — (Е — Л)-1 потребовалось бы обращение матрицы Е — Л — ДгЛ (обращение матрицы Е — Л известно), что в общем случае требует порядка ^3 операций. При больших п Зтг2 существенно меньше, чем ^3.
Если изменение затрагивает лишь матрицу Л, то приращение ресурса Ь* будет найдено по формуле ^Ь* — В\{А *с. Для одного критического ресурса вычисления по этой формуле потребуют ^2 + п умножений и п (^ — 1) + (^ — 1) сложений, т. е. всего 2гс2 + п — 1 арифметических операций. Но поскольку для оценки первичного предложения нам надо знать лишь знак величины Дгб*, то вычисления могут быть еще более упрощены: \^Ъ* = В fA.a ВгА*с = ВВг ^Ац с*\ Вычисление ВВг требует п умножений и п — 1 сложений, поскольку все элементы вектора ВВг, кроме г-го, равны нулю. В силу этого же обстоятельства, а также в силу того, что все элементы вектора с* положительны (вследствие неравенств (6) и (8)), знак Д;6* совпадает со знаком f-ro элемента в ВВг = = В (Л*ДгЛ). Таким образом, для решения вопроса о полезности рассматриваемого первичного предложения достаточно всего ^2 + ^ (^ — 1) + + п + п — 1 = 2тг2 + п — 1 арифметических операций. Для вычисления нового значения матрицы Л*, равного А* + ДгЛ* = А* + X X (ВВг) А* (в случае полезности рассматриваемого предложения), необходимо еще п + п2 умножений и п2 сложений. В целом все вычисления в случае полезности предложения потребуют 4гс2 + 2п — 1 арифметических операций, а в случае его бесполезности — 2п2 + п — 1.
Для вычисления плана с* + Дс* — с* + ДгЛ*Дс потребуется еще 2п2 операций. Иными словами, доказанная теорема при больших п дает решение проблемы существенного сокращения вычислений при коррекции планов в частном случае, когда рассматриваемые первичные изменения затрагивают лишь матрицу Л.
Для общего случая решение проблемы дается следующей теоремой: Теорема 2. Для произвольных (как первичных, так и составных) изменений ДЛ, ДВ, Дс при условии существования матриц А* = (Е — — Л)-1 и (Е — А — ДЛ)-1 = А* + ДЛ* приращение \Ъ* вектора полных затрат ресурсов задается формулой
\Ъ* = (ДВ + ВЛ*ДЛ) (Л* + ДЛ*) (с + ДС) + ВА*\с.(9)
Доказательство. (В + ДВ) (Л* + ДЛ*) — ВЛ* = (В + 4- ДВ - ВА* (Л* 4- АЛ*)-1 (Л* + ДЛ*) = (В + ДВ - В (Е — Л)-1 х X (Е - А - ДЛ) (Л* + ДЛ*) = (В + ВЛ*ДЛ) (Л* + ДЛ*). Далее ДЬ* = (В + ДВ) (Л* + ДЛ*) (с + Дс) + ВА* \с = ((В + ДВ) (4* 44- ДЛ*) - ВЛ*) (с 4- Де) + ВА*\с = (В 4- ВЛ*ДЛ) (Л* 4- ДЛ*) (с 4+ Де) + ВА*^с, что и требовалось доказать.
При одном критическом ресурсе для первичного технологического изменения (ДгЛ, Д{В), как и в рассмотренном выше частном случае, знак ДЬ* совпадает со знаком единственного ненулевого элемента в векторе ДгВ + ВЛ*Д|Л, для вычисления которого достаточно 2п2 + п арифметических операций. В случае полезности предложения новые значе-
ния матриц В и Л* находятся по формулам В = В + ХгВ, А * = А * + + ^ТГ^ ^*ХгАА*, что, по сравнению с рассмотренным частным случаем, требует дополнительно лишь т • п сложений, необходимых для вычисления нового значения матрицы В. Для первичного потребительского предложения Ас вычисления проводятся по формулам Xb* = BA*Xct с* + Ас* = с* + Л* Ас, что потребует еще более простых вычислений.
Тем самым первая из сформулированных выше проблем оказывается полностью решенной. Решение втор ой дается следующим предложением, которое назовем принципом последовательной оптимизации.
Теорема 3. Пусть А — вполне продуктивная матрица, В — вектор затрат критического ресурса, с — вектор конечного выпуска, такой, что все компоненты вектора с* = А*с с полного выпуска положительны, (АЛ, ХВ), Ас — составное изменение, распадающееся в сумму первичных технологических изменений (А^Л, Х^В) и первичных потребительских изменений XjC. Если при всех этих изменениях матрица А остается вполне продуктивной, вектор полного выпуска с* неотрицательным, а составное изменение приводит к экономии критического ресурса, то среди составляющих это изменение первичных изменений найдется хотя бы одно, которое тоже приводит к экономии, критического ресурса.
Доказательство. Приращение затрат критического ресурса вычисляется по формуле (9): Xb* = (А5 + ЕЛ*АЛ) (Л* + АЛ*) (с + + Ас) + BA* Хс = (ХВ + В* ХА) с* + В*Хс, где вектор с* = (Л* 4+ АЛ*) (с + Ас) ^ 0. Разлагая составное приращение в сумму первичных, получим ХЬ* = 5 (А^ + B*XtA) с* + S В* Х5С. Поскольку по г7
условию теоремы эта сумма строго меньше нуля, то хотя бы одно слагаемое должно быть строго меньше нуля. Если таким слагаемым является В*Х^с^ то для первичного приращения (0, 0), Х^с по формуле (9) Х'Ь* = В* Х^с << < 0. Значит, в этом случае теорема справедлива.
Если таким слагаемым является (XtB + 5* АгЛ) с*,- то ввиду неотрицательности с* единственная ненулевая (/-я) компонента рг вектора ХгВ + B*XiA должна быть отрицательна: pi < 0. Для первичного изменения (АгЛ, Х^В), соответствующее приращение Х"Ъ* затрат критического ресурса по формуле (9) равно Х"Ь* = (АгЕ + В*Х^А) (Л* + + А^Л*) с = ргУг, где уг — /-я компонента вектора (Л* + АгЛ*) с.
Но по теореме 2 (Л* + А;Л*) с = ^Л* + j"a А* Х^АА *jc = ^Е + + f"^ А * А;Л ^ с* г-н компонента этого последнего вектора равна скалярному произведению ьй строки В^ матрицы Е + а А*Х^А на вектор с*. Но в строке Вг все элементы равны нулю, кроме /-го, который равняется величине 1 + у__а = f_Za- Поскольку в силу теоремы 2 этот элемент положителен и /-й элемент вектора с* (как, впрочем, и все остальные его элементы) также положителен, то yt > 0. Но тогда Х"Ь* = = РгУг < 0, что и требовалось доказать.
Используя только что доказанную теорему, легко построить следующий алгоритм последовательной оптимизации. Пусть у нас имеется набор допустимых (т. е. сохраняющих полную продуктивность матрицы А и неотрицательность вектора с*) первичных предложений на изменения (АгЛ, ХгВ) (Z = 1, ..., k), XjC у = 1, 2, ..., 1). Если имеющееся решение
А, В, с может быть улучшено (по критерию минимума расхода критического ресурса 6*) за счет какой-либо комбинации первичных изменений, то, перебирая эти изменения одно за другим в произвольном порядке, по теореме 3 мы рано или поздно придем к первичному изменению, улучшающему исходное решение А, В, с. Если после этого возможны дальнейшие улучшения, то может быть повторена та же самая процедура. Правда, в этом случае может уже не выполняться условие (6). Однако тогда можно продукты с нулевым полным выпуском временно исключить из рассмотрения, после чего описанная выше процедура оказывается вновь применимой Ч Из сказанного ясно, что имеет место следующая теорема.
Теорема 4. Алгоритм последовательной оптимизации через конечное число шагов приводит к получению оптимального допустимого решения, обеспечивающего минимум затрат критического ресурса.
В алгоритме последовательной оптимизации возможны дальнейшие усовершенствования. Можно, например, вводить индивидуально полезные первичные изменения не поодиночке, а целыми группами, хотя в этом случае для вычисления приращения матрицы А * уже нельзя пользоваться формулой (9).
Следует заметить, что, хотя в общем случае прямое вычисление приращения АЛ* путем обращения матрицы Е — А — АЛ и вычитания из нее матрицы А* достаточно громоздко, оно может быть существенно упрощено при большой разреженности матрицы А (т. е. при наличии у нее большого числа нулевых элементов).
Впрочем, даже в этом случае вычисления по формуле (7) могут оказаться более эффективными, особенно, если матрицы Л и Л* хранятся на магнитных лентах. Если А* полностью размещается на одной ленте, а для АгЛ отводится место в оперативной памяти, то вычисления по формуле (7) требуют всего лишь двух рабочих прогонов ленты (матрица А^Л* при этом записывается на другую ленту). Для прямых вычислений расположение информации на магнитной ленте сильно снижает скорость вычислений. Нужно иметь также в виду, что разреженность матрицы А имеет тенденцию уменьшаться со временем постоянного увеличения числа связей между отраслями, которое вызывается увеличением сложности выпускаемых продуктов и технологии их производства.
1 На практике обычно более удобно предполагать неравенства (6) выполненными на всех этапах оптимизации. Иными словами, потребительские предложения не должны быть столь радикальными, чтобы приводить к необходимости полного уничтожения производства какого-либо продукта.
О ДИАЛОГОВОМ МЕТОДЕ РЕШЕНИЯ ОПТИМИЗАЦИОННЫХ ЗАДАЧ
[Кибернетика.— 1975.— № 4.]
Во многих современных задачах оптимизации точка оптимума оказывается лежащей на границе области определения изучаемой функции. Особенно много примеров такого рода задач дает экономика, где довольно часто задачи оптимизации ставятся и решаются на линейных моделях.
Точное задание границ области даже в линейном случае представляет собой обычно нелегкую задачу. Трудности здесь возникают прежде всего ввиду высокой размерности, свойственной большинству практически важных экономических задач (например, задаче оптимизации межотраслевого баланса). Кроме того, коэффициенты линейных уравнений, задающих границы области, часто могут быть получены лишь на основании статистической обработки и усреднения огромного числа первичных данных, получаемых в результате экспериментов или расчетов технологического характера. Такое положение имеет место, например, при определении технологических коэффициентов в линейных макроэкономических моделях.
В классических постановках оптимизационных задач труд, который необходимо затратить для точного задания границ области, не принимается во внимание. Между тем этот труд далеко не полностью поддается процессу формализации и автоматизации и зачастую оказывается гораздо более громоздким и длительным, чем последующие решения на ЭВМ самой оптимизационной задачи.
Положение усугубляется тем, что исходные данные для оптимизационных задач обычно подготавливаются специалистами, имеющими приближенные интуитивные представления о районе границы, в котором должен находиться оптимум. Между тем математик-оптимизатор не обладает интуицией, вытекающей из содержательной (а не формальной) постановки задачи, исходные данные которой одинаково точно определили бы всю границу. Однако очевидно, что, например, в классической задаче линейного программирования бессмысленно сколько-нибудь точно определять гиперплоскости, задающие участки границы вдали от района ожидаемого оптимума. Чувствуя, что их время тратится на бессмысленную работу, постановщики задачи теряют к ней интерес и, как следствии, выполняют свою часть работы небрежно. В результате исходные данные задаются неточно, новые технологические возможности (особенно наиболее новые и перспективные, поскольку они обычно требуют больших затрат труда) просто не учитываются. Иными словами, граница области, незыблемая с точки зрения математика-оптимизатора, в действительности может подвергнуться значительным вариациям. Размер этих вариаций таков, что получаемый с их помощью эффект может значительно превысить эффект, полученный за счет первичной оптимизации. Неудивительно,
что постановщики задачи в таких условиях иногда относятся скептически ж самой идее оптимизации, не говоря уже о результатах конкретных оптимизационных расчетов.
Для практически эффективного решения оптимизационных задач в большинстве случаев необходимо, чтобы применяемые методы удовлетворяли двум дополнительным условиям. Во-первых, они должны минимизировать (в разумных пределах) труд постановщиков задачи, не допуская по возможности его растрачивания на подготовку ненужной исходной информации. Во-вторых, они должны возбуждать и поддерживать творческую инициативу постановщиков задачи для поисков принципиально новых неформальных возможностей улучшения решения за счет изменения границы области (обычно лишь в районе уже найденной ранее точки оптимума). В экономике такие возможности возникают наиболее часто за счет принципиально новых технологических идей и решений.
Метод, удовлетворяющий выдвинутым условиям, в силу природы этих условий должен быть по необходимости диалоговым: последовательное улучшение решения должно возникать в результате диалога ЭВМ и коллектива экспертов-постановщиков задачи, обладающих специальными содержательными знаниями о решаемой задаче. Процесс решения при этом проходит следующие стадии: первоначально постановщики задачи грубо очерчивают границы области, в которой ищется решение, допуская их большее уточнение лишь в районе, в котором в соответствии с их представлением должен находиться оптимум; затем ЭВМ решает оптимизационную задачу, находя точное положение точки оптимума на заданной границе. Постановщикам задачи выдается новый (уточненный) район границы, в котором находится полученная точка, а также, возможно, и другая информация, которая ориентирует их в направлении неформальных попыток дальнейшего улучшения полученного решения. Поступающие от них предложения оцениваются ЭВМ и либо принимаются, либо отвергаются х. Процесс оканчивается, когда иссякает поток предложений либо когда исчерпывается время, отведенное на решение задачи. Количество времени, отводимое на оптимизацию, обычно определяется достаточно естественным образом при рассмотрении содержательного смысла задачи, которая, как правило, является задачей планирования и управления в реальных временных циклах.
Практика показывает, что для эффективного вовлечения в диалог с ЭВМ экспертов-постановщиков задачи время, за которое ЭВМ производит оценку каждого поступающего предложения, не должно превышать некоторого порога.
Величина этого порога определяется временем, в течение которого человек, давший предложение, сохраняет к нему интерес и не переключается на другую работу. В конкретной макроэкономической задаче, о которой пойдет речь ниже, этот порог может быть оценен в 15—20 мин. Само собой разумеется, что идеалом являлся бы мгновенный ответ ЭВМ, однако для сколько-нибудь серьезных оптимизационных задач, находящихся на границе возможностей применяемых ЭВМ, этот идеал недостижим.
Необходимость иметь малую задержку в реакции системы на поступающие предложения требует разработки таких методов оптимизации, при которых уточнение (за счет изменения границы) уже полученного
Не исключено, что ранее отвергнутые предложения при их повторном высказывании через несколько последующих шагов будут приняты.
решения производится гораздо проще и быстрее, чем нахождение решения заново. На первый взгляд, такому условию удовлетворяет ряд классических методов оптимизации, например градиентный. Однако следует подчеркнуть, что в большинстве современных задач оптимизации понятие «район точки оптимума», употребленное выше, отнюдь не равнозначно классическому понятию «малая окрестность». Например, для задачи оптимизации межотраслевого баланса естественно считать, что сколь угодно большие изменения технологических коэффициентов одной из рассматриваемых технологий не выводят нас из района ранее найденного оптимума. Поэтому создание эффективных методов диалогового решения оптимизационных задач требует определенного усовершенствования классических методов.
Рассмотрим в качестве примера классическую задачу линейного программирования.
Найти минимум (максимум) линейной функции z = сххг + с2^2 + • •• е.. сихп + d при ограничениях:
4- Q-mn^n 4~ Ьт ^ О,4- Q-mn^n 4~ Ьт ^ О,У1 — а11ж1 4" ^12^2 4" * * * 4“ й^ть 4" ^1 ^ О»^2 = аА 4- «22^2 4- • • • 4- «2п^п 4- ^2 > °.
4- Q-mn^n 4~ Ьт ^ О,
4- Q-mn^n 4~ Ьт ^ О,
Ут — ^ml^i 4“ ^m2*^2 4~ * * *
где т ^ п. Как известно, искомая точки минимума (максимума) в случае, если она существует, совпадает с точкой пересечения некоторых п гиперплоскостей г/^ = 0, yi2 = 0, ..., ytn = 0. Пусть это будут гиперплоскости ут = 0, у2 = 0, ..., уп — 0. Совершим аффинное преобразование с матрицей
#11 #12 • * • а\и ^1
Атак, что векторАтак, что вектор#nl #п2 • • • &пп Ьп00 ... 01#nl #п2 • • • &пп Ьп00 ... 01•^1 ^2^п 1•^1 ^2^п 1преобразуется в векторпреобразуется в вектор^'1^'1
А
так, что вектор
А
так, что вектор
#nl #п2 • • • &пп Ьп
00 ... 01
#nl #п2 • • • &пп Ьп
00 ... 01
•^1 ^2
^п 1
•^1 ^2
^п 1
преобразуется в вектор
преобразуется в вектор
^'1
^'1
Искомая точка оптимума лежит в новом начале координат х^ = х^ = = ... = хп 0.
Преобразование х -> х = Ах переводит произвольную линейную функцию р'х = рххх + р^ + ... + Рп^п 4- Ро в линейную функцию р'х' = рх = рА^х*. Таким образом, вектор р коэффициентов линейной функции преобразуется в вектор р'— рА"1»
Значение оптимизируемой функции z — сх в ючке оптимума оудет, очевиднод равно СА-^
О
О
О
или, что то же самое, последнему (/г + 1)-му элементу вектора сЛ-1, где с = || ct1 с2, ..., cnd || — вектор коэффициентов линейной функции z.
В соответствии с общей идеей диалогового метода начальные ограничения уг ^ 0, ..., ут ^ 0 могут задаваться с определенными погрешностями (приближенно). После нахождения точки оптимума при этих ограничениях мы начинаем анализировать возможность их изменения с целью улучшения достигнутого оптимума. Заметим, что это может быть достигнуто лишь за счет изменения ограничений, с помощью которых образована новая система координат (в данном случае ограничения ух 0, ... ..., уп ^ 0), ибо все допустимые решения лежат в конусе ух ^ 0, ..., уп ^ 0.
Предположим, что для некоторого г (1 ^ i^ п) ограничение yt = = сцх ^ 0 удалось заменить ограничением у^ + ^Уг = кал + ^а^ х ^ ^ 0, где <2j — вектор || а^ аш ••• , ^т, bn ||, а А а, — его произвольное приращение. Заменяя координатную гиперплоскость уг = 0 новой гиперплоскостью у} + \y-i = 0, мы переходим от аффинного преобразования х -^ х' с матрицей Аг к аффинному преобразованию с матрицей А + + At Л. Здесь через АгЛ обозначена «однострочечная» матрица
00... 00
Аа71 Aau . . . A<2j?) A6i
о о ... о о
у которой все строки, кроме z-й, заполнены нулями.
Для того чтобы начало новой системы координат совпадало с новой точкой оптимума, достаточно, чтобы соблюдались два условия: 1) свободные члены линейных функций г/п-н, ..., Ут в новой системе координат должны быть неотрицательными; 2) все коэффициенты при неизвестных функции z = сх в новой системе координат имеют один и тот же знак (плюс в случае минимума и минус в случае максимума). Но поскольку векторы коэффициентов линейных функций преобразуются с помощью обратной матрицы, то проверка обоих высказанных условий сводится к нахождению новой обратной матрицы (Л -- А^)""1 = Л“1 + А, (Л-1).
Пользуясь тем, что матрица А^Л «однострочеяная», можно пока агь, что
Ai (Л-1) = Л-1 -Л— Di = -Л— Л-'АгЛЛ-1.(1)
х1 — al — а г7
Здесь через Di обозначена «однюстрочечная» матрица А ^4 Л-1, а через a — элемент этой матрицы, стоящий на пересечении Лй ее строки и z-го столбца. Вычисление матрицы -^^ Di требует выполнения (п + + I)2 умножений^ п (п -f- 1) сложений и п + 1 делений^ т. е, 2 (п + I)2 254
арифметических операций. При умножении матриц А и р_— Di к ним добавляются еще (п + I)2 умножений, так что общее число операций при вычислении приращения Aj (А-1) составит 3 (n + I)2, если не считать операции вычитания а из 1.
Зная приращения обратной матрицы, можно еще с помощью 2п +1 операций вычислить приращение вектора коэффициентов любой линейной функции. Тем самым появляется возможность проверки высказанных выше двух условий. Если они выполняются, находим приращение Az зна
чения критериячения критерияz : Az = cAj (Аz : Az = cAj (АО ОО1О ОО1
чения критерия
чения критерия
z : Az = cAj (А
z : Az = cAj (А
О О
О
1
О О
О
1
При Az < 0 — в случае поиска минимума и Az > О — в случае поиска максимума мы достигаем желаемого улучшения оптимума, в противном же случае либо происходит его ухудшение, либо значение оптимума остается неизменным.
В случае, когда хотя бы одно из высказанных выше двух условий не выполняется, в соответствии с общей идеей симплекс-метода осуществляем переход к новой системе координат (с началом в точке оптимума) путем последовательных модифицированных жордановских преобразований. Поскольку любое такое преобразование задается «однострочечной» матрицей, при вычислении обратной матрицы на каждом из шагов может быть использована формула (1). Подобный же последовательный метод вычисления обратной матрицы можно применять и при нахождении начального значения оптимума (с неуточненными граничными условиями).
Аналогичный метод уточнения решения можно применять и в том случае, когда уточнению подвергаются ограничивающие гиперплоскости ?/n4-i, ..., ут. Хотя, разумеется, в этом случае найденное первоначальное значение оптимума заведомо не улучшается. При решении конкретных практических задач интуиция постановщиков задач обычно позволяет избежать ненужной работы по уточнению условий, не меняющих значения оптимума.
Следует особо подчеркнуть, что в большом числе приложений линейного программирования к задачам экономики многие ограничения определяются особенностями используемой технологии и могут поэтому меняться целенаправленно, а не просто уточняться. Поэтому за счет выбора (или изобретения) подходящей технологии постановщик задачи часто может осуществлять сознательное многошаговое улучшение первоначально найденного оптимума. В то же время простое уточнение ограничений, будучи объективным процессом, не зависящим от воли постановщика задачи, может менять начальное значение оптимума в любом направлении. Сознательное управление процессом улучшения оптимума также должно опираться на интуицию постановщиков задачи, за счет чего удается избежать многих заведомо бесполезных попыток изменить начальные ограничения.
Хорошей иллюстрацией преимуществ диалогового метода может служить задача оптимизации межотраслевого баланса. В каждой из заданных п отраслей первоначально фиксируется по одной определенной тех-
нологии. Эти технологии определяют матрицу А = || а^ || прямых затрат продуктов (элемент а^ матрицы А определяет количество продукта, производимого Z-й отраслью и который затрачивается в /-й отрасли на производство единицы выпускаемого ею продукта). Обозначим через b = || btba ... bn || вектор прямых затрат какого-либо внешнего по отношению к рассматриваемой системе продуктов ресурса, например затрат труда. Через bj здесь обозначаются затраты этого ресурса в /-й отрасли на производство единицы продукта, выпускаемого этой отраслью. Как и элементы а^ матрицы А, элементы bj вектора b определяются заданным набором технологий.
Из теории статических макроэкономических моделей вектор Ь* = = || &1, Ь^ ..., Ьп || полных затрат рассматриваемого ресурса определяется формулой
Ь* = ЬА*=Ъ(Е — Л)-1. (2)
Компонента bj вектора Ь* равна полным затратам ресурса (с учетом всех его затрат в других отраслях), необходимых для выпуска единицы /-го продукта. Обозначим через
Сп
вектор конечного (или чистого) выпуска. Компонента Сг этого вектора определяет полное количество продукта, производимого t-й отраслью, за вычетом той его части, которая потребляется при производстве всех остальных продуктов.
Количество внешнего ресурса, которое необходимо затратить для обеспечения чистого выпуска с, определяется формулой
z = Ь*с = Ь(Е — Л)-1 с. (3)
Предположим теперь, что для каждой отрасли имеется не одна, а несколько возможных технологий. Замена технологии в /-й отрасли приводит к изменению /-го столбца матрицы А и /-го элемента вектора b и вызывает изменение величины критерия z. Задача состоит в том, чтобы определить такой выбор технологий, при котором величина критерия z достигает минимума. Она может быть сведена к задаче линейного программирования [1], однако не в исходном пространстве размерности п, а в пространстве, размерность которого равна общему количеству всех возможных технологий. В исходном же пространстве, как видно из формулы (3), задача оптимизации не является линейной.
Автором [2] было доказано, что искомый минимум может быть получен в результате последовательной замены технологий (по одной за каждый шаг) так, чтобы каждая замена уменьшала значение критерия z. Невозможность дальнейшего его уменьшения за счет любого изменения одной из технологий означает, что достигнут абсолютный минимум.
Поскольку приращения матрицы А, а значит и матрицы Е — А, являются «одностолбцовыми» (все столбцы приращения АА матрицы Ад за исключением одного, нулевые), то по аналогии с формулой (1) получаем
ДЛ* = т-!— DA* А* • АЛ- Л*4 (4) 1 — а 1 — а • ' '
где а — элемент в ненулевом столбце матрицы D^ стоящий на пересечении этого столбца с главной диагональю матрицы.
Приращение величины критерия
Az = (Аб + ЬА*^А) (Л* + ААЬ) с.(5)
Метод решения задачи заключается в следующем. Выбрав начальный набор технологий и определив для него матрицы А, А* = (Е — А)-\ а также вектор б, организуют диалог с постановщиками задачи. Они вносят одно за другим элементарные предложения, направленные на экономию рассматриваемого ресурса. Элементарность предложения означает, что замене подвергается лишь одна какая-нибудь технология. Каждое из внесенных предложений проверяется на ЭВМ по формуле (5). В случае, если Az < 0, предложение принимается, в противном — отвергается. В принципе не исключена возможность, что какая-то технология, замененная другой, на последующих шагах может быть введена вновь. Однако при этом нет необходимости хранить в памяти ЭВМ все сделанные ранее шаги, достаточно помнить лишь значения А, А*, b и z, полученные на последнем шаге.
Вычисления по формуле (4) и (5) производятся гораздо быстрее, чем нахождение первоначального значения матрицы А*, поскольку количество выполняемых операций имеет порядок квадрата размерности задачи (az), а не куба размерности, как это имеет место при вычислении матрицы А*. Поэтому даже при достаточной высокой размерности (п = 1200) проверка любого вносимого элементарного предложения занимает всего 15—18 мин работы даже такой относительно малопроизводительной машины, как «Минск-32». Этот показатель вполне согласуется с приведенными выше требованиями к скорости ответа системы, обеспечивающими эффективное ведение диалога.
Заметим, что описанный выше общий подход к решению задач линейного программирования в диалоговом режиме для только что рассмотренной задачи неприменим. В самом деле, при линеаризации этой задачи введение каждой новой технологии означает не увеличение числа ограничений, а увеличение размерности пространства (числа переменных), в котором производится оптимизация. Случай же роста размерности в описанном выше методе не предусмотрен. Он требует дополнительных рассмотрений.
СПИСОК ЛИТЕРАТУРЫ
Ланкастер К. Математическая экономика.— М. : Сов. радио, 1972.
Глушков В. М. О последовательной оптимизации в линейных макроэкономических моделях И Управляющие системы и машины.— 1973.— № 4.
О СИСТЕМНОЙ ОПТИМИЗАЦИИ
[Кибернетика.— 1980.— № 5]
Современные теория и практика оптимизации строятся на основе классической постановки оптимизационных задач. Как известно, суть этой постановки состоит в нахождении в наперед заданной неизменной допустимой области Р точки (или множества точек) р, в которой заданная скалярная целевая функция / (р) принимает экстремальное значение.
Для большого числа планово-экономических и проектно-конструкторских задач такая постановка является неудовлетворительной по крайней мере в двух отношениях. Во-первых, целевая функция / (ж) в таких задачах является не скалярной, а векторной. При этом она оказывается практически не сводимой к скалярной функции путем той или иной априорной процедуры (например, процедуры взвешивания различных компонент исходной векторной функции). Во-вторых, допустимая область Р может меняться в процессе оптимизации. Более того, в ее целенаправленном изменении как раз и заключается основная содержательная сущность процесса оптимизации для рассматриваемого класса задач.
' Поскольку законы возможных изменений допустимой области Р задаются обычно системой моделей, то описываемый подход к оптимизационным задачам естественно называть системным. Заметим, что при системном подходе изменения ограничений, задающих допустимую область в пространстве тех или иных параметров, происходят, как правило, в результате последовательности решений, выбираемых из дискретного множества возможных. Причем, само это множество в начале процесса оптимизации обычно бывает полностью не заданным и пополняется в процессе диалога с людьми (плановиками или конструкторами), владеющими не до конца формализованными приемами выработки новых решений.
Приведем одну из характерных формализованных постановок задачи системной оптимизации. Для того чтобы лучше уяснить идею, проиллюстрировав ее графически, рассмотрим двукритериальный случай. Предположим также, что выбором значений этих критериев однозначно определяется соответствующее решение. Иными словами, искомое решение ищется непосредственно в пространстве К критериев оптимизации, которые мы обозначим хА и х^ (рис. 1).
Процесс решения начинается с того, что в заданном пространстве К выбирается некоторая точка Ло с координатами а0 и Ьо — желательное решение задачи. Далее, строятся начальные ограничения F^ (£г, х^ ^ ^ 0, ..., Е^ ^хХч х^ ^ 0, задающие начальную допустимую область Ро. Прямой проверкой устанавливается факт принадлежности или непринадлежности точки Ло области Ро. В первом случае в принципе может быть применена обычная (классическая) процедура оптимизации либо по одно
му из критериев xv х^ либо по той или иной их комбинации. Однако при системном подходе применяется обычно совершенно другой прием, а именно: в соответствии с моделью М высшего уровня, управляющей выбором критериев, точка Ло выводится из пределов допустимой области Р^ как это и показано на рис. 1.
Затем выделяются те ограничения, которые не выполняются в точке Ло (в рассматриваемом случае ими будут Е^ и F^Y Обращаясь к моделям М^ и М41 формирующим эти ограничения, в диалоговом режиме апробируются те или иные решения, изменяющие соответствующие ограничения в нужном направлении (если такое изменение оказывается возможным). Нужным при этом считается то направление, которое уменьшает абсолютную величину отрицательных невязок F^ (ц0, b0) (в рассматриваемом случае Е^ (а0, 50) и Е^ ^а^ Ь^.
Следует иметь в виду, что во многих случаях ограничения Е^ оказываются взаимосвязанными, так что изменение одного из них приводит к изменению определенной части двух ограничений. Управление выбором решений для изменения ограничений определяется при этом минимизацией некоторой функции штрафа g0 ^aQl Ъ^. В качестве такой функции выбирается обычно максимальная абсолютная величина отрицательных невязок %^^0; (б/0, Ь^ (где Х< — некоторые положительные весовые коэффициенты). Если таких невязок нет, то по определению g0 (а0, Ьо) = 0.
В результате управления появляется ряд решений Rv ..., Rm, приводящих к уменьшению значения функции штрафа, которое после т-то решения обозначим g,„ (а0, b0L Изменяя ограничения, каждое из принятых решений приводит к соответствующему изменению допустимой области. На рис. 1 показаны два таких изменения. Первое из них изменяет ограничения Е^ и Е^\ заменяя их соответственно ограничениями Е^ и Е^Р. Второе затрагивает лишь Е(^\ заменяя его ограничением Е^\ Получающаяся после этих изменений допустимая область Р2 ограничена линиями ЕТ, Е^\ Е^ и Е^ а соответствующее значение функции штрафа равно g2 (а0, b0Y Заметим, что заблаговременный выбор конечной допустимой области невозможен ввиду того, что последовательность областей PqP^ ... может быть не упорядочена по вложению. Кроме того, огромная трудоемкость формирования новых ограничений не позволяет выполнить ату работу заблаговременно, поскольку при этом потребовалось бы сделать много лишней работы по изменению несущественных ограничений.
Если g2 (а0, 60) ^ 0 (см. рис. 1), а решений, приводящих к дальнейшему уменьшению значения функции штрафа, не имеется, то происходит возвращение к высшей модели М, управляющей выбором желательного решения задачи А (а, Ь). Путем ряда последовательных решений D^ D^ .... Dk на изменение начального решения задачи Ло (а0, 60), оно последовательно заменяется на Аг (ах, 6J, ... Ак (а^ Ь^ пока очередная точка Ак (dk, bk) не окажется в допустимой области (на рисунке к = 1). Решения на изменения выбираются из допустимого множества решений с целью минимизации функции штрафа. Этот процесс близок к классическому процессу оптимизации за исключением лишь того обстоятельства, что шаги выбираются не произвольно, а в соответствии с допустимыми (моделью И) решениями.
Наконец, после попадания точки Ак в заключительную допустимую область Рт может быть применена дополнительная процедура оптимизации по каким-либо комбинациям критериев ^ и ^2 в пределах этой допустимой области. Такая процедура отличается от классической лишь тем^ что выбор шагов оптимизации не произволен, а управляется моделью М высшего уровня. Если дальнейшему улучшению избранного критерия мешают некоторые ограничения, поддающиеся дальнейшим изменениям в нужную сторону, то процесс оптимизации может быть продолжен за счет включения в него последовательных решений на такие изменения.
Заметим, что однозначное определение решения задачи выбором значений всех критериев оптимизации встречается не столь редко, как это может показаться на первый взгляд. Оно имеет, например, место для планово-экономических задач, где критерием (векторным) является чистый выпуск продукции разных видов, а решением задачи — полный выпуск [1]. В случае, когда такая однозначность отсутствует, пространство, в котором ищется решение, помимо координат, соответствующих критериям оптимизации, может иметь и другие. Описанный выше процесс оптимизации при этом усложняется за счет того, что точки А г ^^ Ь^ заменяются гиперплоскостями. Усложняется и определение функции штрафа: в качестве нее может быть выбрано, например, расстояние от выбранной гиперплоскости до очередной допустимой области в пространстве с заданными сжатиями (растяжениями) вдоль осей, соответствующих критериям оптимизации.
В самом общем случае вместо гиперплоскостей могут фигурировать точечные множества произвольного вида. Возможны постановки, при которых на этих множествах значения критериев определены неоднозначно, а для различения более или менее предпочтительных решений на множествах задаются (моделью высшего уровня М^ соответствующие весовые функции. Однако важной чертой системной оптимизации, сохраняющейся при всех подходах, помимо многокритериальности и возможности изменения допустимой области, является взаимодействие моделей различных уровней. В случае планово-экономических задач решения в этих моделях производятся управляющими различных уровней, а в случае проектно-конструкторских задач — проектантами, работающими над различными частями проекта.
Автором разработана одна из конкретных схем оптимизации, основанная на изложенных принципах, реализованных в системе «Дисплан» [1L
СПИСОК ЛИТЕРАТУРЫ
1. Глушков В. М. Макроэкономические модели и принципы построения О Г АС.» М. : Статистика, 1975,
СОДЕРЖАНИЕ
От редакционной коллегии 3
Виктор Михайлович Глушков. Краткий очерк о жизни и научной деятельности 4
Предисловие 11
РАЗДЕЛ 1. РЕЗУЛЬТАТЫ АЛГЕБРАИЧЕСКИХ ИССЛЕДО
ВАНИЙ 13
О нормализаторах полных подгрупп в полной группе 14
К теории ZA-rpynn 18
О локально-нильпотентных группах без кручения 22
Об одном классе некоммутативных локально-бикомпактных групп 26
Точные треугольные представления Z-алгебр Ли 30
Строение локально-бикомпактных групп и пятая проблема Гильберта 34
Проективно-лиевы группы 35
Полугруппа Глисона и’ вспомогательные функции .43
Аппроксимация группами без малых подгрупп . . . .48
Группы без малых подгрупп 52
Строение локально-бикомпактных групп’64
К теории специальных локально-компактных групп 70
О строении связных локально-бикомпактных групп 74
Введение 74
Бикомпактно-лиевы разложения 74
Связные локально-бикомпактные группы с изоморфными алгебрами Ли 81
Локально связные группы 85
РАЗДЕЛ 2. ТЕОРИЯ АВТОМАТОВ И ЕЕ ПРИМЕНЕНИЯ . .91
О некоторых задачах вычислительной техники и связанных с 'ними задачах математики . .92
Абстрактные автоматы и разбиение свободных полугрупп . . . . 100
Некоторые проблемы синтеза цифровых автоматов103
Абстрактные автоматы и автоматные соответствия . . . 105
События и представление событий в автоматах . . . . 110
Анализ конечных автоматов115
Абстрактный синтез конечных автоматов119
Минимизация абстрактных автоматов 125
Структурный синтез конечных автоматов130
О применении абстрактной теории автоматов для минимизации микропрограмм 140
Теория автоматов и некоторые ее приложения 146
Теория автоматов и формальные преобразования микропрограмм 152' О простых алгоритмах анализа и синтеза магазинных автоматов 164 Проблемы синтеза цифровых автоматов176
Теория автоматов и вопросы проектирования структур цифровых машин179
РАЗДЕЛ 3. ТЕОРИЯ ДИСКРЕТНЫХ ПРЕОБРАЗОВАТЕЛЕЙ, ВЫЧИСЛИТЕЛЬНЫХ МАШИН И ИХ МАТЕМАТИЧЕСКОГО ОБЕСПЕЧЕНИЯ 193
Об одном методе автоматизации программирования194
К вопросу о минимизации микропрограмм и схем алгоритмов . . 198 Об определяющих соотношениях в двухсумматорном операционном устройстве 202:
О полноте систем операций в электронных вычислительных машинах 204
Оценка эффективности сложных систем и организации вычислительных процессов211
Фундаментальные исследования и технология программирования 219* О формальных преобразованиях алгоритмов223
РАЗДЕЛ 4. МАТЕМАТИЧЕСКИЙ ИНСТРУМЕНТАРИЙ В СИСТЕМАХ УПРАВЛЕНИЯ231
О прогнозировании на основе экспертных оценок 232
Исходные предпосылки и постановка задачи232
Сеть событий и ее стабилизация233
Обработка стабилизированной сети событий2/3
Дальнейшее уточнение результатов235
Обобщенные динамические системы и процессионное прогнозирование 236
О последовательной дезагрегации в статистической макроэкономической модели240
О последовательной оптимизации в линейных макроэкономических моделях243
О диалоговом методе решения оптимизационных задач251
О системной оптимизации 258
НАУЧНОЕ ИЗДАНИЕ
ГЛУШКОВ Виктор Михайлович
КИБЕРНЕТИКА, ВЫЧИСЛИТЕЛЬНАЯ ТЕХНИКА, ИНФОРМАТИКА
Избранные труды в трех томах
Том 1
МАТЕМАТИЧЕСКИЕ ВОПРОСЫ КИБЕРНЕТИКИ
Художественный редактор И. П. Антонюк
Технический редактор Г. М. Ковалева
Корректоры В. Н. Семенюк, Л. Г. Вуз нате или..
ИБ 10478
Сдано в набор 30.10.89. Подп. в печ. 15.06.90. БФ 08085, Формат 70x100/16. Бум. тип. № 1. Обыкн. нов. гари# Выс. печ. Физ. печ. л. 16,5+0,125 вкл. на мел. бум. Усл, печ. л. 21,61. Усл. кр.-отт. 21.61. Уч.-изд. л. 20,04. Тираж 2930 экз. Заказ 9—3609. Цена 4 р. 10 к.
Издательство «Наукова думка». 252601 Киев 4, ул. Репина, 3.
Отпечатано с матриц Головного предприятия республиканского производственного объединения «Полиграфкни- га». 252057 Киев 57. vn. Довженко, 3. в Киевской типографии научной книги, 252004 Киев 4, ул. Репина, 4.- Зак. 0-460.