Разработка и исследование статического и динамического методов управления точностью в системе синтеза алгоритмов тема диссертации и автореферата по ВАК РФ 01.01.10, кандидат физико-математических наук Кулида, Сергей Владимирович

• Кулида, Сергей Владимирович
• кандидат физико-математических наук
• 1984

Оглавление диссертации кандидат физико-математических наук Кулида, Сергей Владимирович

ВВЕДЕНИЕ.

ГЛАВА I. СТАТИЧЕСКИЙ МЕТОД УПРАВЛЕНИЯ ТОЧНОСТЬЮ.

1.1. Постановка задачи.

1.2. Существование решения.

1.3. Многошаговый процесс решения.

1.4. Обсуждение практических аспектов.

ГЛАВА 2. ДИНАМИЧЕСКИЙ МЕТОД УПРАВЛЕНИЯ ТОЧНОСТЬЮ.

2.1. Постановка задачи. Достаточные условия сходимости метода регуляризации.

2.2. Построение метода регуляризации при более слабых условиях.

1 2.3. Обсуждение результатов.

2.4. Обсуждение практических аспектов.

Введение диссертации (часть автореферата) на тему «Разработка и исследование статического и динамического методов управления точностью в системе синтеза алгоритмов»

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

Особенно актуальными становятся исследования в области автоматизации программирования. К этому разделу программирования, разрабатывающему методы автоматического составления программ, относится большой круг работ по созданию таких языковых средств и программного обеспечения современных ЭВМ, которые обеспечивали бы реализацию задач пользователей при возможно меньших затратах труда программиста, см. например [ 18, 22, 24, 46 , 47, 53, 58, 59, 60-64]. Рассмотрим некоторые вопросы, касающиеся данного направления исследований.

За время эксплуатации ЭВМ создано большое количество научных и прикладных программ. В связи с продолжающимся накоплением программ ставится задача их эффективного использования. Во избежание дублирования работ наиболее употребительные программы собраны в библиотеки программ [53, 54]. Обычно в таких библиотеках имеется несколько различных программ, предназначенных для решения одной и той же задачи. Возникает проблема выбора, при которой пользователь (программист) должен ознакомиться со структурой и семантикой формальных параметров всех программ, относящихся к его задаче, а затем отсеять неприменимые программы и выбрать среди оставшихся наиболее соответствующие, по его мнению, решаемой задаче. Этот выбор субъективен и основан, как правило, на личном опыте и квалификации программиста-математика. Кроме того, описания библиотек обычно очень обширны, а программы, содержащиеся в них,столь разнотипны, что для их изучения требуется немало труда. Этим в значительной мере объясняется недостаточно эффективное использование библиотек программ. Следовательно, естественны попытки в какой-то мере автоматизировать процесс выбора. Данную цель и преследуют различные пакеты прикладных программ и системы синтеза алгоритмов.

Системы автоматизации программирования призваны так же предоставить пользователю максимально удобные средства работы в избранной области, освободить человека от рутинной работы при оформлении программы для счета на ЭВМ. Создаваемая на факультете ВМиК МГУ система автоматизированной генерации алгоритмов с гарантированной точностью результатов (САГАТ) [28, 29, 40-43, 52-54] преследует такие же цели. Первая версия системы называлась САИБ (система автоматизации использования библиотек). Поскольку система осуществляет точностной анализ алгоритмов, она переименована в САГАТ. Система предназначена для синтеза алгоритмов решения задач вычислительного характера. Основу синтезируемого алгоритма составляют программы, реализующие численные методы математического анализа и организованные в единый банк. Система должна обеспечить выбор этих программ из группы конкурирующих, их настройку на выполнение задачи пользователя и компоновку всех информационных связей.

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

1) гарантировать точность решения поставленной пользователем задачи;

2) получить решение с минимальными вычислительными затратами, что повысит эффективность использования программного обеспечения.

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

Целью диссертационной работы является:

- разработка теоретических основ блока точностного анализа, осуществляющего контроль и управление погрешностями вычислений в системах автоматической генерации алгоритмов;

- программная реализация этого блока в системе САГАТ (САИБ) на ЭВМ БЭСМ-6.

Для выяснения места создаваемой системы и ее отличий от имеющихся систем генерации и пакетов прикладных программ следу

- б ет подробнее остановиться на нескольких программных комплексах описанного типа. Существующие системы и пакеты прикладных программ (ППП) в основном различаются: областью применения (класс решаемых задач) ; типом и структурой модулей, из которых конструируется объектная программа; способом связи и взаимодействия модулей; принципами генерации объектной программы; базовыми возможностями, предоставляемыми пользователю. Область применения систем варьируется от узкой области численного анализа, например, уравнений в частных производных, как в системе P2>£L [57], до произвольных задач численного анализа, как в генераторе программ ГП [ 2, з]; от специальных инженерных или учебных расчетов, определяемых моделью, как в системе синтеза вычислительных алгоритмов (ССВА)[32, ЗЗ] и ПРИЗ [45], до более широкого спектра инженерно-научных задач, решаемых системами POSE [64], и АМТШ[65, 69] и особенно NAPSS [бб-бв].

Тип и структура модулей, из которых конструируется объектная программа, представлены различными объектами - от элементарных преобразований первичных отношений в системах ССВА [33] и ПРИЗ [45, 50, 51] , более сложных модулей (конструирующих модулей или шаблонов программ) в ГП [2] до крупных программных единиц в Р05Е [64] , BAL [5б] , /ШТМ[б5, 69] , АПРОП [44] и полиалгоритмов в iMPtf [63, 68].

Конструирование программ может происходить с помощью модели, задающей семантику типичных задач из рассматриваемого класса и характеризующейся совокупностью отношений между объектами модели [50] , а также с помощью заложенных в систему (фиксированных) схем вычислений [ 32, 47]. Кроме того,пользователем может явно указываться последовательность модулей [2, 3, 37, 60, 6l]. Допускается применение смешанного метода задания логики вычислений. Возможен и комбинированный способ .'идентификации объектов, когда одна часть модулей задается пользователем явно (по конкретному имени), а другая - неявно (по абстрактному имени) [32, Зб].

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

Система синтеза вычислительных алгоритмов (CGBA) позволяет эффективно моделировать исследуемые инженерные объекты в термич нах элементарных преобразований. Но следует заметить, что слишком большая детализация процедур не приводит к упрощению программирования. Так, в начале работы по исследованию свойств (моделированию) технической детали пользователь должен описать модель исследуемого объекта, либо досконально ознакомиться с содержанием имеющейся модели. Это предполагает знание имеющихся в системе процедур, списков зависимых и выходных переменных, а также составление информационной таблицы. Строки таблицы содержат код преобразования, условия выбора процедур и условия, определяющие правила вычисления аргументов [32, ЗЗ].

В системе ПРИЗ элементарные преобразования "спрятаны" внутри системы, а пользователю предлагается вместо явного задания последовательности процедур писать предложение

НА М ВЫЧИСЛИТЬ У1, ., УК ПО XI, хм, по которому на модели М, исходя из знания входных величин XI, ., ХМ, выбирается нужная цепочка вызовов модулей для вычисления величин У1, УК [50]. В системе строятся вычислительные модели, задающие семантику типичных задач определенного класса. Эффективность работы пользователя определяется, в основном, полнотой задания семантических моделей, а также степенью ознакомленности с ними пользователя и знания им возможностей входного языка УТОПИСТ [35].

Созданный в НИЩ М1У генератор программ (HI) позволяет сделать более эффективным процесс составления новых программ, используя хранящиеся в системе шаблоны (или комодули). ГП может применяться как инструментальная система для автоматизированной генерации пакетов библиотечных фортранных подпрограмм для той или иной предметной области [2,з]. Сборка программ осуществляется на основе обработки операторов IN5ERT языка МАКФОР [2], Для облегчения доступа к ЭВМ пользователям-непрограммистам был разработан непроцедурный язык запросных анкет ФОРЛАН [з], предложена методика создания проблемно-ориентированных языков типа EIGENflO], которые могут использоваться и автономно (вне ГП). Во всех случаях вычислительные модули либо выбираются самим пользователем, либо жестко фиксированы.

Как и ГП, система ВAL [56] может рассматриваться как средство для генерации пакетов программ, но основное ее назначение -обеспечить "технических" пользователей (то есть непрофессиональных программистов) легким и эффективным доступом к программному обеспечению и в то же время снабдить профессиональных программистов гибким и мощным инструментом для производства программ. Система базируется на использовании программ, хранимых в так называемом "банке алгоритмов". Доступ к программным единицам в системе В A L более гибок и разнообразен, чем в традиционных библиотеках программ, что достигается наличием препроцессора, специальных утилитов EXEC и НЕАД и довольно развитого макроязыка системы, включающего в себя операторы вызова алгоритмов ( + CALL , + ВУММЕ )» размещения этих алгоритмов в памяти (с помощью загрузчика операционной системы), а также операторы управления распределением памяти (+ ALLOCATE, + LIBERATE) и организации процесса вычислений (+IF THEN и+ CASE OF).

Система автоматизации производства программ (АПРОЩ [44] представляет собой некоторую мониторную систему, предназначенную для сборки и объединения разноязыковых модулей, макрогенерации в соответствующих языках, отладки и диалога с пользователем. Для этой цели создан язык конструирования программ (СУПЕРЯЗЫК), основными объектами (операционными элементами) которого являются исходные модули (программы) и макромодули, переменные периода генерации и модули данных.

В системах POSE [64] и ДМТШ[65, 69] были сделаны попытки приблизить входные языки систем к математической записи введением таких операторов, как INTEfr/Щ, INSERT , SCOPE , Ш1У9 SOIVE, TRANSPOSE, INTERPOLATE, APPROXIMATE, и т.д. Каждый такой оператор высокого уровня снабжен зафиксированным алгоритмом (методом) его реализации. В основном эти системы использовались для учебных целей и решения относительно несложных инженерных задач либо в интерактивном режиме (/IMTRAty, либо в пакетном (РОЗЕ). Входной язык системы /1MTRAN содержит элементы языков ФОРТРАН и АЛГ0Л-60 с некоторыми дополнительными операторами высокого уровня. Эти операторы обеспечивают пользователю возможность добавлять свои собственные специализированные операторы, работать со списками, строками, таблицами. Имеются широкие возможности графического вывода. Язык системы РОЗЕ - язык декларативного типа. Задание на нем состоит из логических подразделений, называемых программными сегментами, которые выполняются друг за другом. Изменение порядка выполнения сегментов может задаваться как внутри сегментов оператором EXECUTE с указанием номера следующего выполняемого сегмента, так и с помощью особого программного сегмента CALCUIATJON 5EQI/6NCE, задающего последовательность выполнения сегментов.

Более мощной и развитой, чем Р05Е иДМТК/Ш, но преследующей в общем-то те же цели (декларативность и приближение к математической нотации) является система j\MP5£ [62, 63, 66-68]. Здесь каждый раздел численных методов, задействованный в операторе высокого уровня, снабжен одним алгоритмом, но этот алгоритм, называемый полиалгоритмом, представляет собой не просто отдельный метод из данного раздела численного анализа, а синтез группы численных методов (из данного раздела), объединенных в один алгоритм с помощью логической структуры. Логическая структура полиалгоритма управляет ходом внутреннего вычислительного процесса, решая на основании промежуточных вычислений, какой численный метод имеет преимущества перед остальными в данной ситуации [63, 66]. В системе используется мощный язык, базирующийся на языках МГ0Л-60 и ФОРТРАН, но существенно обобщающий и расширяющий многие их операторы. Наряду с алгоритмическими конструкциями имеются и декларативные операторы описания действий. Основным оператором языка NAP,S£, обеспечивающим автоматическое вычисление некоторого математического объекта с помощью полиалгоритма, является оператор $0LVE\ имеющий ввд

SOLVE < уравнения> FOR <переменные> [<опции>] , где под "опциями" ( OPTIONS) понимается дополнительная информация, задающая тип уравнений, число искомых решений, начальные значения, погрешность вычисления результатов и другие сведения о вычисляемом объекте, например: WITH - назначение переменным начальных значений;

ON - указание интервала, на котором ищется решение; NUMBER - число искомых решений;

USING - указание по использованию конкретного метода, а не полиалгоритма;

ТУРЕ - указание типа уравнений (линейная система, дифференциальное уравнение и т.д.) ; ACCI/RAC!/- абсолютная или относительная погрешность; STEP - величина начального шага и т.п.

Таким образом, при использовании полиалгоритмов отпадает необходимость выбора наилучшего, метода для решения конкретной задачи из некоторой области численного анализа, так как основные методы "зашиты" в полиалгоритме. Однако такое решение проблемы имеет свои недостатки:

I) если для отдельных методов имеются аналитические оценки точности вычисляемых приближенных решений, то для полиалгоритма их получение чрезвычайно затруднено из-за объединения в одном алгоритме стратегий разных методов. В силу этого возникают трудности в оценке затрат на достижение необходимой точности вычислений. Значит, эффективность полиалгоритма может быть оценена лишь качественно, а это приводит к преобладанию качественных критериев при построении управляющей структуры полиалгоритма. Ясно, что такая управляющая структура на практике не всегда будет обеспечивать построение эффективного алгоритма решения задачи пользователя [68];

2) для сложных логических структур не доказана сходимость полиалгоритмов;

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

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

К рассмотренным выше системам генерации программ (СГП) вплотную примыкают (по своим целям и возможностям) некоторые наиболее развитые пакеты прикладных программ (ППП). Так же, как и СГП, крупные пакеты программ обладают своим специфическим входным языком и на выходе производят (генерируют) программу, готовую к выполнению в соответствующем системном окружении. В то же время ППП, как правило, более узко направлены, проблемно -ориентированы. Основные сферы их применения - задачи той или иной области численного анализа, например: линейные алгебраические уравнения, различные классы дифференциальных уравнений, задачи на нахождение собственных значений, интерполирование, численное интегрирование. В сферу применения ППП входят также прикладные и научные задачи (статистическая обработка данных, реакторные расчеты, обработка данных физического эксперимента), разного рода задачи управления и экономики [20, 22 , 38 , 55].

Пакеты программ разнятся также по идеологии их построения и функционирования (методо-ориентированные и проблемно-ориентированные), по типам и структуре модулей, способам связи модулей и их взаимодействию (задание информационных и управляющих связей), принципам сборки результирующей программы [20, 22, 36, 38].

ППП повышают эффективность применения ЭВМ. Дальнейшее развитие ППП, вероятно, пойдет по пути приближения пакетов к системам автоматического синтеза программ. Работы в данном направлении призваны способствовать более рациональному и эффективному использованию имеющегося программного обеспечения, что соответствует главной задаче экономической политики КПСС, выработанной ХХУ1 съездом партии.

Среди ППП вычислительного характера, то есть ППП, предназначенных для решения задач, в которых основные затраты ресурсов вычислительной системы приходятся на реализацию методов численного анализа, можно вьщелить системы ФЙХАР [55] , 2)ЕМ0$ [30], САФРА [20, 38]. Сюда же можно отнести такие системы генерации программ, как POSE, AMTRAN, BAL , NAPSS, ГП. В отмеченN ных системах последовательность вычислений задается пользователем. Правда, степень детализации может быть различной. В одних случаях задается только функциональное имя класса модулей, в других указывается конкретное архивное имя (в терминологии системы САФРА), то есть иногда планирование (установление соответствия мевду именами или выбор графа управления по информационному графу задачи) возлагается на саму систему. Однако такое планирование нередко состоит в определении цепочки модулей, определяющих правильный, но не самый эффективный вычислительный процесс (исключение составляет лишь, быть может, система NAPSS). Конструктивные подходы к решению этой проблемы изложены в работах [26, 28, 40-43, 53].

Другое сильное средство оптимизации синтезируемого алгоритма, которое не отражено в СГП, - оптимизационный анализ погрешностей, с которыми надо вычислять промежуточные величины задачи, чтобы достичь требуемой точности вычислений с минимальными затратами вычислительных ресурсов. Именно этот анализ является одним из средств оптимизации в системе САГАТ [25-29, 40, 43].

ППП и СГП обычно имеют ограниченную область применения, связанную с классом решаемых задач и типом элементарных (конструирующих) модулей. Полнота покрытия области применения зависит не только от объема функционального (прикладного) наполнения, но и от системных возможностей пакета (СГП) по связыванию базовых модулей. Системы, работающие с крупными модулями, труднее адаптировать (без появления избыточности) для реализации новых ситуаций в покрываемой ими предметной области, а мелкоблочная организация хотя и более мобильна, но зачастую громоздка и требует немалых затрат при модификации и при работе. В целях устранения этих недостатков либо используют макросредства для организации многоуровневых иерархических модулей, либо останавливаются на некотором среднем по объему семантически завершенном модуле/. Например, такими "средними" модулями могут быть стандартные программы из библиотек общего доступа, входящих в состав МО ЭВМ.

Рассматриваемая в данной работе система САГАТ ориентирована на широкий класс задач вычислительного характера, решаемых с использованием методов численного анализа. Охват различных ситуаций, возникающих при решении вычислительных задач, осуществляется при помощи стандартных программ из общих библиотек для ЭВМ БЭСМ-6, реализующих различные численные методы математического анализа и собранных в единый банк программ системы САГАТ. Расширение библиотек естественным образом увеличивает полноту набора вычислительных модулей, участвующих в конструировании объектных программ. Средства формализации параметров стандартных подпрограмм позволяют в системе САГАТ расширять библиотеки или менять функциональное наполнение без перестройки системных связей, поскольку в системе достаточно описать формальные параметры добавляемых программ [52, 541. Система предназначена для решения задач вычисления функций вида у (х) с заданным ограничением на погрешность вычисления выходной функции | fy U£° (0.1) Здесь ^ - произвольная функция, дифференцируемая всюду в области изменения аргумента X . Величины .f ХНа) вычисляются численными методами математического анализа. Введем переменный вектор Д = (д1у Att., ANo), Aj >0f j = ifNa

В дальнейшем под словами: "Величина Xj вычислена с погрешностью Aj ", - будем понимать, что полная погрешность вычисления величины Xj не превосходит Aj . Погрешности вычисления величин X заранее не известны, поэтому возникает задача назначения погрешностей вычисления этих величин таким образом, чтобы погрешность выходной функции удовлетворяла соотношениям (0.1). Ясно, что необоснованное назначение погрешностей величинам X может привести как к тому, что погрешность результата будет больше заданного <5° , так и к тому, что результат будет вычислен с погрешностью гораздо меньшей 6° . Последнее приведет i к неоправданному увеличению затрат ресурсов вычислительной системы и снижению эффективности генерируемого алгоритма [26, 28, 42]. Для предотвращения таких ситуаций и ставится задача снабдить систему средствами управления погрешностями, когда по заданной погрешности результата необходимо выбрать погрешности вычисления промежуточных величин так, чтобы достичь требуемой точности вычислений с минимальными затратами вычислительных ресурсов.

Способность вычислительной системы гарантировать заданную точность решения поставленной задачи, во-первых, существенно повысит производительность труда программиста, освободив его от трудоемкой и сложной работы по оценке погрешностей получаемых решений, во-вторых, повысит степень надежности результата и, в-третьих, придаст системам генерации программ новые интеллектуальные возможности, позволит значительно расширить область их применения [25-29,40,41,43,54].

Кратко опишем основное содержание работы.

Необходимость работы вызвана практическими потребностями создаваемой на кафедре автоматизации систем вычислительных комплексов факультета вычислительной математики и кибернетики Московского Государственного университета системы автоматизации синтеза алгоритмов вычислительных задач с гарантированной точностью результатов.

В главе I задача поставлена математически. Исследовано существование решения. Задача свелась к минимизации функции затрат &(£) на некотором множестве U . Принадлежность A^U гарантирует выполнение условия (0.1), а минимизация затрат обеспечит оптимальность алгоритма. Предложен алгоритм ее решения, основанный на методе динамического программирования. Метод обеспечивает решение этой задачи на специально выбранном множестве I/т^ , которое является частью множества V . Так как V^с I/ , то тиь &(а) ^ я-wt/ (}(л) . Отсюда вытекает, что синтезируемый If Vftiilb с помощью предложенного метода динамического программирования алгоритм, вообще говоря, может отличаться от оптимального, но так как с U , то он будет обеспечивать главную цель гарантировать погрешность вычисления задачи пользователя не более заданной. Этот метод статический, он использует информацию о'задаче пользователя априори, до начала ее решения. В конце главы I ставится задание усилить полученный результат, то есть предложить метод, с помощью которого можно синтезировать алгоритм более оптимальный, чем тот, который получится, если следовать результатам главы I. Это задание выполнено в главе П.

Показано, что из-за трудностей построения множества V , задачу управления погрешностью можно решать на приближенно заданных но множеству U множествах VK , которые гораздо легче построить, чем множество V . Показано, что такая задача некорректна по Тихонову. Для ее решения множества Ик расширены до множеств 1УК з 1/к , причем множество WK построено так, что Vе WK я- VK с WK . Для этой некорректной задачи построен регуляризатор. Получены достаточные условия, при которых последовательность { ДСк)} , полученная по методу регуляризации, является минимизирующей и регулярной. Достаточные условия получены для случая как выпуклых 17 и O-(Z) , так и не выпуклых.

- 18

С использованием полученных методов регуляризации разработан алгоритм динамического управления погрешностью, когда мы от шага к шагу подправляем погрешности промежуточных величин в за- висимости от информации, полученной от предццущего шага. Вычислив Xlf Хц,,., с погрешностями А(± 7 А^.^ д^ уточняем полученные погрешности с помощью предложенных методов регуляризации. В результате получаем значения A(fy л}?,., Aj^

Довычисляем Xly я*,., хЫо с этими погрешностями a[z\

А (*) Л гт

АЪу.1 Далее опять проводим метод регуляризации, подправляя

Д^ Af, . у А® , в результате чего получаем

А Ф л ®

Аз, -, \ И т.д.

Показано, что предложенный алгоритм динамического управления погрешностями даст лишь конечное число шагов в направлении оптимального А . Пусть А^ е VI^ - последнее приближение.

Предложенный алгоритм, вообще говоря, не гарантирует того, что € U. На практике это означает, что вычисление величин xi> . , с погрешностями л/*^. ? л^ не гарантирует того, что погрешность решения задачи пользователя будет не больше заданного С . Чтобы применить полученное квазирешение на практике, используем его в качестве уточненных исходных данных для метода динамического программирования, описанного в главе I. В результате получим более оптимальный набор погрешностей и численных методов, так как будем использовать для метода Ееллмана начальные данные, уточненные методом регуляризации Тихонова. Полученный таким образом набор погрешностей будет обеспечивать синтез более эффективного по затратам вычислительных ресурсов алгоритма.

- 19

Заметим, что в случае выпуклых &(л) и U и не выпуклых (г(а) и U мы получили различные методы регуляризации. В первом случае метод более эффективен, во втором - более общ. Поэтому разработкой метода регуляризации, свободного от требования выпуклости, мы значительно расширили класс задач, к которым применим алгоритм динамического управления погрешностью. Это в свою очередь дает возможность строить более эффективные алгоритмы решения этих задач, чем те, которые были построены с помощью только метода Беллмана. ,

Освободиться от требования выпуклости позволила доказанная в диссертации важная теорема, модифицирующая метод регуляризации Тихонова для решения задач минимизации на приближенно заданных множествах. Главной идеей такой модификации явилось построение регуляризатора Q (д) и его приближения (^а) так, что (а) само стало регуляризатором для задачи минимизации £ (а) на множестве Wk .

Доказанная теорема имеет самостоятельное значение и может применяться для решения других задач минимизации на приближенно заданных множествах, а не только той прикладной задачи, для решения которой она была доказана [ 27, 29].

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

Приложение 2 содержит листинги примеров работы системы.

- 20

В заключении приводятся основные результаты диссертационной работы.

Блок контроля и управления погрешностями вставлен в систему САГАТ (САИБ) и работает под управлением ОС ДИСДАК в монитор-ной системе ДУБНА. Система САГАТ (САИБ) внедрена в двух организациях в качестве компоненты программного обеспечения ЭВМ БЭСМ-6.

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

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

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

- 21

I. СТАТИЧЕСКИЙ МЕТОД УПРАВЛЕНИЯ ТОЧНОСТИ)

I.I. Постановка задачи

Целью этой главы является разработка и обоснование метода, позволяющего решить проблему точностного анализа для задачи вычисления сложной функции, когда вычисления проводятся методами численного анализа. Указанная проблема имеет важное значение при решении задачи автоматизации создания алгоритмов с заданными требованиями по точности. Еще более ценные результаты можно получить, если потребовать, чтобы алгоритм не только удовлетворял точностным требованиям задачи пользователя, но был оптимальным или возможно более близким к таковому в смысле затрат вычислительных ресурсов фиксированного вида. Решение этой проблемы позволит освободить пользователя от точностного анализа его задачи, который в большинстве случаев провести аналитическими методами не удается [25, 27, 28 , 40, 41]. Если под прямой задачей теории погрешности понимать задачу, когда по заданным погрешностям величин CCj , нужно определить, какова погрешность вычисления величины , то задача управления погрешностью - это обратная задача теории погрешностей, а именно:

1) по заданному назначить погрешности вычисления величин Xj , , которые бы гарантировали, что погрешность вычисления функции XNo) будет не более заданной;

2) указанные погрешности должны обладать тем свойством, что затраты вычислительных ресурсов на вычисление величины yfai^b,.,^) должны быть оптимальными или близкими к таковым.

Заметим, что часть 2) постановки задачи, несомненно, важна и ее решение даст новый инструмент построения оптимальных алгоритмов, однако, принципиальной является часть I), так как до сих пор контроль за погрешностью результата полностью ложился на человека, и даже вычисление всех промежуточных величин с максимальной для данной ЭВМ точностью не позволяет гарантировать точность результата*

Решение задачи управления погрешностью должно лечь в основу "Оптимизатора" см. рис. I.I системы автоматической генерации алгоритмов с гарантированной точностью результата. Общая архитектура системы изложена в [28] и выглядит следующим образом:

Описание задачи на языке пользователя

М о н и т о р

-f> 1

Г-с --- «. захи^ м

-V интим) изатор v У

Генератор

Результирующая программа ъЖ р х и в с и с т е м ы к д м и н и с т р а т о р

--- —

Блок статистики и документации

Задание на работу с архивом системы

Рис. I.I. Архитектура системы

Монитор /5/ управляет работой основных блоков системы. Архив системы /4/ состоит из банка численных методов и информационной части, содержащей оглавление банка, информацию об условиях применимости методов, формализованное описание параметров прикладных программ, оценки погрешностей методов и различные типы функций затрат.

Блок анализа /I/ производит синтаксический анализ задания пользователя и перевод текста задачи во внутреннее представление и построение ориентированного графа вычислительного процесса.

Блок /2/ - оптимизатор, выполняет собственно точностней анализ алгоритма и производит назначение для каждой величины Xj.j-Щ численного метода ее реализации и погрешность, с которой она должна быть вычислена. Назначение численного метода происходит, исходя из соображений повышения эффективности алгоритма путем минимизации затрат вычислительных ресурсов. Создание теоретических основ и практической реализации "Оптимизатора" и посвящена данная работа. Для целостности картины кратко опишем остальные блоки системы. Генератор /3/ по информации, полученной из блоков /1/ и /2/ производит компоновку результирующей программы и представление ее в виде, готовом к выполнению.

Администратор /6/ с помощью языка манипулирования данными обеспечивает проведение сервисных работ с архивом системы /4/ и блоком статистики и документации /7/. Возможность обратиться к системе из ФОРТРАН-программы позволяет пользователю, при желании, часть алгоритма своей задачи написать самому, а остальные части поручить системе [53, 54].

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

- 24 кая модель. ^

В рамках модели предполагается, что

1. функции uj(. непрерывно дифференцируемы на множестве V0 » которое будет описано ниже. Заметим, что если у (ocif не является непрерывной, то бесконечно малые погрешности Aj, j = l) Не вычисления величины j= не гарантировали бы бесконечно малого изменения tj-(xb xNo) » а следовательно и требуемой погрешности

5° . Дифференцируемо сть функции существенно используется ниже при математической постановке задачи.

2. Для каждого Xj существует Kj конкурирующих численных методов Mij , Ь - i^Kj f j = . Каждый метод может дать приближение величины Xj } j = J^7/0 с погрешностью Aj>0 д д (пик) fx) где Aj изменяется на некотором отрезке A .j 4 Aj < Aj , характеризующем собой максимальную и минимальную точность метода.

На этом отрезке для метода Мц существует функция вычисли. v d тельных затрат Uy \Aj) > используемая при построении оптимальных алгоритмов. Заметим, что для всех Xj функции Му (Ар должны быть одной физической размерности или приведены к таковой.

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

3. Относительно функций Uij (Aj) сделаем также предположения, что они убывающие и положительные. Ясно, что все эти ограничения скорее отражают природу функций затрат, чем являются ограничениями в собственном смысле слова. функции затрат, вообще говоря, дискретны и принимают значения в узлах некоторой решетки, но мы доопределим их непрерывным образом, сохраняя монотонность. Если в результате рещения задачи управления погрешностями величине Xj будет назначена погрешность вычисления Л.- , лежащая мевду узлами решетки, то а эта величина будет вычислена численным методом с погрешностью

§ >0 » где 6j - ближайший не превосходящий Aj узел решетки, в котором функция затрат определена. Это хорошо отвечает практике работы с численными методами.

Предположим также, что функции Uy (Aj) непрерывны везде fay v) (l) (тоС) на отрезке Г Аи , д.- ] , кроме точки А , в которой fUtQ иц ( а = + оо . Величина A Lj определяется точностными возa J а можностями метода Мц . Существование А^^ >0 означает, что Ч величина Xj не может быть вычислена методом MLj с погрешностью непревосходящей

4. Предположим также, что затраты на весь алгоритм получаются как сумма затрат ресурсов, истраченных на получение каждого

Обозначим через V0 некоторое множество из пространства В ° , содержащее точку X* - точное значение величин xfj xtj ХЪ} . Заметим, что множество V0 можно считать ограниченным, замкнутым параллелепипедом.

Действительно, при помощи численных методов можно получить I некоторое приближение к решению Xх с погрешностью

Аа) = .} А^ ) . Имея эту информацию, всегда можно локализовать X* следующим образом:

Ясно, что неравенства (1.3) задают ограниченный замкнутый параллелепипед из пространства ЕМо , который можно принять в качестве множества VQ .

Рассмотрим непрерывно дифференцируемую на множестве Va функцию хх,г) Пусть требуется, чтобы погрешность вычисления этой функции не превосходила заданного £° . Применим теорему Лагранжа для оценки модуля разности

IAjj= || А: (л) Aj I 0±д Н Здесь dj(2) =Ц-(х* + в1)

В этих обозначениях введем множество V тех А , для которых выполнено неравенство | 71 Л\ С&) А" I ^ ^' j-f 1

1.4)

Здесь U0 - ограниченное множество в пространстве Ем* , задаваемое неравенствами

1*0О (А (тек) (fnin)

Aj Ad \ где Aj = /у*/ ALj- f j = tf„ (1.5)

Г> Л С1"**) A

Величины Ai , определяются точностными возможностями имеющихся численных методов. На практике сущестmik) вование А- Ф- 0 означает, что величина X: не может быть

J d вычислена имеющимися численными методами с погрешностью меньшей, пик) чем А; d ,

Как видно из задания множества JJ , принадлежность Л ко множеству U гарантирует погрешность вычисления функции не превосходящую 6° .Мы будем предполагать, что из всех д g UQ , то есть тех, для которых выполнено (1.5) существует хотя бы одно А т* такое, что справедливо неравенство = а)\~ 6° £0 из (1.4). Если бы таких не существовало, то это означало бы, что имеющиеся численные методы не могут решить задачу вычисления функции с заданной точностью. В этом случае множество 17 пусто или состоит из единственной точки Л , и задача управления погрешностями вырождается, так как достижимые погрешности промежуточных величин не обеспечивают получение результата с погрешностью не более заданной.

Предположим, что для каждой величины Xj из группы конкурирующих выбран метод М,- ; i^h ^ К; , с помощью коj d > d ® торого будет производиться вычисление этой величины. Как уже было отмечено, каждому методу М^. ; соответствует функция за о трат И;. ; (а5) , и суммарные затраты на вычисление всех величин d <} d

Xj} j = будут равны сумме затрат на вычисление каждого JCj.

Исходя из этого, введем функцию затрат всего алгоритма. tW-fc (Ю = Ш + + " + «i*,* (Л J «-6)

Пусть Д* = (д*, Д*, •■•» л n„ ) ~ точка минимума функции (rki 6 (а ) на множестве 17 . Вопросы существования точки минимума на множестве U будут обсуждены ниже. Пока предположим, что такая точка существует. Тогда принадлежность Л* ко множеству 17 гарантирует, что погрешность вычисления функции yCxi, хfa) $УДет не больше заданного , а минимизация затрат на этом множестве обеспечит оптимальность алгоритма. Однако, найденный вектор Д* будет оптимальным только для набора численных методов с номерами ily . f lUa. Если же хотя бы для одной величины Xj выбрать другой численный метод, то тем самым поменяется j -ое слагаемое функции (1.6) и, следовательно получится другая задача минимизации, для которой оптимальным будет другой набор погрешностей. Возможно он будет лучше предыдущего в том смысле, что будет обеспечивать меньшие затраты вычислительных ресурсов. Итак мы приходим к проблеме выбора наилучшей комбинации численных методов для вычиследача целочисленного программирования с очень большим количеством ч переборов, и, вообще говоря, ее можно было бы решать следующим образом. Составим таблицу, в которой j -ая строка будет состоять из Kj функций затрат для вычисления величины Xj .

Теперь действуем методом перебора: из каждой строки таблицы (1.7) выбираем по одной функции затрат (и, следовательно, по одному методу), формируя таким образом функцию (1.6), и находим ее минимум на множестве JJ . Затем опять из каждой строки выбираем по одной функции затрат, но так, чтобы новый набор отличался от предвдущего хотя бы одним слагаемым. Ищем теперь минимум этой вновь полученной функции затрат и т.д. пока не переберем все возможные наборы функций (методов). Этих наборов будет в точности Kj .KNo , и значит столько надо будет решить задач минимизации. Теперь среди всех решений этих задач выбираем то, которое дает самые минимальные затраты из минимальных. ния функции с погрешностью £° . Это за

Набор функций (а значит и методов), дающий этот minimum- тст-мюпщуи, и будет оптимальным набором методов, а вектор А* ? являющийся решением соответствующей задачи минимизации, будет оптимальным набором для назначения погрешностей.

Ясно, однако, что с ростом Н0 число • К#о очень быстро возрастает и метод перебора крайне не эффективен. Чтобы не решать такого огромного количества задач минимизации, предлагается пойти по другому пути.

В связи с практической непригодностью метода перебора, возникла идея каждую строку функций в таблице (1.7) заменить одной функцией (Aj) : gf(Aj)= пил by (А;) (1.8)

В силу предположений о функциях My (&J) функции ^ (Aj) положительные, убывающие и непрерывны всюду на отрезке [а^] aJ'J, кроме точки Л/^ , в которой ^ (aJ^) - + оо .

Практически эта функция имеет "рекомендательный" характер, как бы указывая для каждого заданного Aj лучшую функцию, а значит и лучший метод, дающий для данного Aj меньше всего затрат. Графически это будет выглядеть так: берем j -ю строку таблицы (1.7) и на одной системе координат строим графики всех функций этой строки. Затем из всех полученных кривых берем кусочки тех, которые лежат на графике ниже остальных, получается следующая картина:

Рис. 1.2. Вычисление функции ^ (aj)

Пунктиром показаны вертикальные асимптоты для методов, которые tnin) Л могут вычислить величину Xj лишь с погрешностью А у 40. Жирной линией обведена функция ^ (aj) . Какие бы значения переменная JSj ни принимала, функция ^ (aj) как бы указывает, какая же функция затрат, а значит и метод, являются наилучшими для данного значения Aj . С использованием функций ^-(аД задача управления погрешностями для непрерывно-дифференцируемой функции будет поставлена так: ьф я С*А leU={2 A eV0; к (А) Иначе говоря, надо минимизировать функцию 6-(а) на множестве U,

1.9)

- 31

Ясно, что решение задачи (1,9) избавляет нас от перебора. Справедлива

Лемма I.I. Пусть А* решение задачи (1.9), тогда л* является решением задачи точностного анализа методом перебора. Доказательство. В силу (1.8) для любых номеров ilf 4,V» справедливо следующее соотношение: (1Л0)

Используя полученные А* , найдем, согласно (1.8) соответствующий набор функций затрат: U,L* i (л{)у ui£l (лД. , ^ (aJ

No °

Очеввдно, что

УУШЬ (г (л) = /ШК> (г.* (I.II)

Ц 1 ? LНо

Это следует из определения функции &(&) и определения

Сравнивая (1.10) и (I.II) получаем, что 2* дает самые минимальные из минимальных затраты (млишип, мштожт ). Это и означает, что есть также решение задачи точностного анализа методом перебора. Таким образом мы целое семейство задач минимизации функций (1.6) на множестве (1.4) заменили одной задачей минимизации (1.9) [26].

Обозначим через 17* множество векторов ~д*~ , являющихся решением задачи (1.9):

1Л = {2: Д61/; <г(2)=£*= (I.I2)

Определение I.I. Вектор Л*с у* назовем нормальным решением, если он удовлетворяет следующему соотношению wf j&(£)(= I леи*

Можно дополнить постановку задачи (1.9) требованием найти среди всех решений - нормальное. Это требование не обязательное, так как безразлично какой из векторов А* в V* взять в качестве решения задачи (1.9). Все они в равной степени будут обеспечивать оптимальность алгоритма при выполнении точностных требований задачи. Однако, физический смысл нормального решения заключается в том, что оно дает погрешность вычисления функции не превосходящую 8° и наиболее близкую к 6° . Это вытекает из определения функции £ (л) , используемой в определении множества U , см. (1.4). Подчеркнем еще раз, что требование нормальности решения не является обязательным и не во всех дальнейших результатах будет достигнуто.

Решение задачи (1.9) позволяет избежать перебора, однако, при ее решении мы столкнемся со следующими серьезными трудностями: а) функции Cfj (Aj) , j = Iу Но уже не являются дифференцируемыми по Aj и,следовательно, градиентные методы поиска экстремума не применимы; б) функция (г(а) вообще говоря не выпукла и не дифференцируема, следовательно, необходимое условие для применения градиентных методов также не соблюдается [il, 131; в) множество U имеет довольно сложную структуру, в силу чего проверка принадлежности точки А ко множеству V крайне затруднительна.

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

Заключение диссертации по теме «Математическое обеспечение вычислительных машин и систем», Кулида, Сергей Владимирович

Результаты работы могут быть использованы при проведении дорогостоящих вычислительных экспериментов или полунатурного моделирования, когда важно гарантировать заданную точность ре k зультата при минимальном расходовании вычислительных ресурсов заданного ввда. Результаты работы позволяют снизить стоимость эксперимента и в то же время гарантировать заданную точность решения.

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

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

Реализованный блок контроля и управления погрешностями вставлен в систему САГАТ и работает под управлением ОС ДИСПАК в мони-торной системе ДУБНА.

Система внедрена во Львовском производственном объединении "Кинескоп" и в НИБЦ МГУ.

По материалам диссертации опубликовано пять печатныь работ.

ЗАКЛЮЧЕНИЕ

Необходимость работы вызвана практическими потребностями создаваемой на кафедре автоматизации систем вычислительных комплексов факультета вычислительной математики и кибернетики Московского государственного университета системы автоматизированного синтеза алгоритмов с гарантированной точностью результата (САГАТ).

Целью работы является:

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

2) программная реализация этого блока в системе САГАТ на ЭВМ БЭСМ-6.

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

Список литературы диссертационного исследования кандидат физико-математических наук Кулида, Сергей Владимирович, 1984 год

1. Антипин A.G. Метод регуляризации в задачах выпуклого программирования. - Экономика и математические методы, 1975, 1., № 2, с. 336-342.

2. Арушанян О.Б., Гайсарян С.С., Кабанов М.И. МАКФОР: язык описания макромодулей Генератора Программ. В кн.: Численный анализ на ФОРТРАНе (под общей редакцией В.В.Воеводина. - М.: Изд-во Моск. ун-та, 1973, вып. I, с. 14-33.

3. Арушанян О.Б., Гайсарян С.С., Кабанов М.И. ФОРЛАН -язык описания запросных анкет Генератора Программ. В кн.: Численный анализ на ФОРТРАНе (под общ. ред. В.В.Воеводина. -М.: Изд-во Моск. ун-та, 1975, вып. 10, с. 3-32.

4. Бахвалов Н.С, Численные методы, т. I. М.: Наука,1973.

5. Беллман Р. Динамическое программирование. М., ИЛ, 1962.

6. Беллман Р., Энджел Э. Динамическое программирование и уравнения в частных производных. М.: Мир, 1974.

7. Беллман Р. Прикладные задачи динамического программирования. М.: Наука, 1965.

8. Березин И.О., Жвдков Н.П. Методы вычислений, т. I. -М.: Наука, 1966.

9. Березин И.С., Жидков Н.П. Методы вычислений, т. П. -М.: Наука, 1962.

10. Борисов В.М. Методика разработки проблемно-ориентированных языков на примере языка Et&EN . В кн.: Автоматизация конструирования библиотек программ (под. ред. Е.А.Гребенникова). - М»: Изд-во Моск. ун-та, 1979, с. 57-71.

11. Будак Б.М., Васильев Ф.П. Приближенные методы решениязадач оптимального управления (Тезисы лекций), вып. 2. М.: Изд-во Моск. ун-та, 1969.

12. Булатов В.П. Методы погружения в задачах оптимизации. Новосибирск: Наука, 1977.

13. Васильев Ф.П. Лекции по методам решения экстремальных * задач. М.: Изд-во Моск. ун-та, 1974.

14. Васильев Ф.П, Методы решения экстремальных задач. М,: Наука, 1961.

15. Васильев Ф.П, 0 методе квазирешений в некорректных экстремальных задачах. В сб.: Вычислительные методы и программирование (НИВЦ. М.: Изд-во Моск. ун-та, 1977, вып. 26, с. 119126.

16. Васильев Ф.П. О регуляризации некорректных задач минимизации на множествах, заданных приближенно. Ж. вычислит, матем. и матем. физики, 1980, 20, № I, с. 38-50.

17. Васильев Ф.П. Численные методы решения экстремальных задач. М.: Наука, 1980.

18. Воеводин В.В., Гайсарян G.G., Кабанов М.И. Автоматизированная генерация программ. В кн.: Вычислительные методыи программирование. М.: Изд-во Моск. ун-та, 1974, № 2, с.З-П.

19. Габасов Р., Кириллова Ф.М. Основы динамического программирования. Минск: Изд-во Белорусского ун-та, 1975.

20. Горбунов-Посадов М.М., Корягин Д.А., Красотченко В.В. Реализация системного наполнения пакета прикладных программ САФРА (верия 2.0). М.: ИПМ АН СССР, 1979, препринт $ 186. -19 с.

21. Демьянов В.Ф., Рубинов A.M. Приближенные методы решения экстремальных задач. Л.: Изд-во Ленинградск. ун-та, 1968.

22. Ершов А.П, Ильин В.П. Пакеты программ технология ре- 80 шения прикладных задач. Новосибирск: ВЦ GO АН СССР, 1978, препринт К5 121. - 22 с.

23. Ильин В.А., Позняк Э.Г. Основы математического анализа. М., Наука, 1971, ч. I.

24. Королев Л.Н. Проблемы прикладного и теоретического программирования. Веетн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн., 1979, № 4, с. 30-37.

25. Кулвда С.В. Исследование вопросов управления погрешностью решения вычислительных задач. М., 1983, - 14 с. - Рукопись представлена Моск. ун-том. Деп. в ВИНИТИ 13.07.83,3884-83.

26. Кулвда С.В. О выборе численных методов при создании оптимальных алгоритмов решения вычислительных задач. В кн.: Вопросы теоретического и прикладного программирования. - М.: Изд-во Моск. ун-та, 1980, с. 100-116»

27. Кулида С.В. Решение задачи управления погрешностью в системе синтеза алгоритмов методом регуляризации Тихонова. -Вестн. Моск. ун-та. Сер. вычислит, матем. и киберн., 1984, № 3, с. 48-53.

28. Кулида С.В. Управление погрешностью в системе автоматизации построения алгоритмов. В кн.: Программное обеспечение вычислительных комплексов. М., Изд-во Москв. ун-та (в печати).

29. Купцов В.И., Курильская Н.А. Язык программного задания системы 2)ЕМО$. В кн.: Труды 1У Всесоюзного семинара по комплексам программ математической физики (под ред. Н.Н.Янен-ко. - Новосибирск: ВЦ СО АН СССР, 1976, с. 89-96.

30. Куржанский А. Б. Управление и наблюдение в условиях неопределенности. М.: Наука, 1977.

31. Ламбин Л.Н., Цымбал Г.Я. Система синтеза вычислительных алгоритмов. В кн.: Автоматизация проектирования сложных систем. - Минск: Ин-т техн. киб. АН БССР, 1976, вып. 2, с. 103 НО.

32. Ламбин Л.Н., Цымбал Г.Я. Входной язык системы синтеза вычислительных алгоритмов. В кн.: Вычислительная техника в машиностроении. - Минск: Ин-т техн. киб. АН БССР, 1978, № 2, с. 132-139.

33. Морозов В.А. Регулярные методы решения некорректно поставленных задач. М.: Изд-во Моск. ун-та, 1974.

34. Мяннисалу М.А., Тыугу Э.Х. Язык описания задач УТОПИСТ. Управляющие системы и машины, 1974, № I, с. 80-84.

35. Об одном подходе к разработке интеллектуальных пакетов (Бухштаб Ю.А., Горлин А.И., Камынин С.С. и др. М.: ИПМ АН СССР, 1983, препринт № 70. - 24 с.

36. Об одном методе планирования расчетных цепочек. (Бухштаб Ю.А., Горлин А.И., Камынин С.С. и др. Программирование, 1981,3, с. 34-38 .

37. Пакет прикладных программ САФРА. Системное наполнение. ' (Горбунов-Посадов М.М., Карпов В.Я., Корягин Д.А. и др. М.: ИПМ АН СССР, 1977, препринт № 85. - 27 с.

38. Пшеничный Б.Н., Данилин Ю.М. Численные методы в экстремальных задачах. М.: Наука, 1975.

39. Разумовский С.Н. О системе программирования, выполниющей синтез алгоритмов с гарантированной точностью результатов. Вестн. Моск. ун-та. Сер. 15. Вычис. матем. и киберн. 1982, № 2, с. 56-63.

40. Разумовский С.Н., Васюкова Н.Д., Уласик О.А. Об алгоритмизации вычислительных процессов. Вопросы радиоэлектроники. Сер. общетехническая, 1976, вып. П, с. II5-I25.

41. Разумовский С.Н. Об информационном обеспечении системы синтеза алгоритмов с гарантированной точностью результатов, Программирование, !98I4 № I, с. 66-73.

42. Разумовский С.Н. О системе программирования, выполняющей синтез алгоритмов с гарантированной точностью результатов. Вестн. Моск. ун-та. Сер. 15. Вычислит, матем. и киберн. 1982,2, с. 56-63.

43. Система автоматизации производства программ АПРОП. -Киев: ИК АН УССР, спец. конструкт, бюро математ. машин и систем, 1976. 134 с.

44. Система программирования ПРИЗ / Кахро М.И., Мяннисалу М.А., Саан Ю.П., Тыугу Э.Х. Программирование, 1976, № I,с. 38-46.

45. Соловьева Л.А., Корнилова Г.§. Способы организации пакетов прикладных программ ППП. Свердловск: Урал, научн. центр АН GCCP. Ин-т механики и математики, 1979. - 678 с.

46. Столяров Л.Н. Краткий обзор принципов организации пакетов прикладных программ. В кн.: Труды 1У Всесоюзного Семинара по комплексам программ математической физики. - Новосибирск: ВЦ СО АН СССР, 1976, с. II2-I24.

47. Тихонов А.Н., Арсенин В.Я. Методы решения некорректных задач. М,: Наука, 1979.- 83

48. Тихонов А.Н., Васильев Ф.П., Потапов М.М., Юрий А.Д. О регуляризации задач минимизации на множествах, заданных приближенно. Вестн. Моск. ун-та. Сер.tf вычислит. матем. и киберн. 1977, № I, с. 4-19.

49. Тыугу Э.Х. Решение задач на вычислительных моделях. -Ж. вычислит, матем. и матем. физики, 1970, № 3, с. 716-733.

50. Тыугу Э.Х., Харф М.Я. Алгоритмы структурного синтеза программ. Программирование, 1980, № 4, с. 3-13.

51. Уманец П. В. Автоматическая генерация вызовов программ в системе синтеза алгоритмов. М., 1981. - II с. - Рукопись представлена Моск. ун-том. Деп. в ВИНИТИ 03.07.81, № 3459-81.

52. Уманец П. В. Концепции построения системы использования библиотек программ. В кн.: Некоторые вопросы прикладной математики и программного обеспечения ЭВМ. - М.: Изд-во Моск. ун-та, 1982, с. 38-39.

53. Уманец П.В. 0 реализации системной надстройки над библиотеками программ. В кн.: Некоторые вопросы системного программирования. - М.: Изд-во Моск. ун-та, 1982.

54. ФИХАР модульная система программ для реакторных расчетов. / Башмачников А.Н. - В кн.: Труды Ш семинара по комплексам программ математической физики (под ред. Н.Н.Яненко.- Новосибирск: ВЦ СО АН СССР, 1973, с. 17-26.

55. МсОл, oCOIoa^ Л., ЗЬмМ. Х-С., ЯсмлЖб Щ ^wvwtnfJuj. Р BAL : cuv aid to -MimtiifcC'pbot^iouyimlh^. ёал&£ и^оъ Co of (^gwtJwuy1314, p. S41-S5L

56. СлесЛр.6bo£&tvi> So&ist<2 — fliOTxekswttf dC№> Tiat. (Щ. Опре&ь,1. J966, p. Я-SG.63. On, Me Сотг^гш^пу efiа/<руиМ*п<ь> fib JbUoryvovhc, Tlccntcblcccfi 1*1,: Л^бему fiyc Jlppj&ed

57. THc^zrncdixA, Ot. Рглль, -/968, p. 304-315.1. M. POSE Д,fits

58. K^i^W c^ Jfa, ЛСШ; v. /о, J? 5,6S. Uvfy Art, C.I. AMTRAN:

59. Ct^OTncdic Ша^/ьстс&ссоС J^aM^ctfaoris. ~ JWffciUь Лс. W. Г, 436S, jj, 4<f~6G.3g. dc. оогггсм cr^

60. XjOH^Ucc^ ^yi^ c*s 'flumxbcccoC U^icu^^i^

61. Mzwtcd ЖаЖг&ьа&с^. — de. 71. JSCS,p. в*-ч*.61. dyrnxs £ OMeAo^t £. /£ СстуЩг ^

62. PZK~ IEEE ^tcuvsrcx^iicn^y cjitx^icATcuuo S^lnxc^i^j -f9Wy iT. Цy p 306-30S. Si. 0&£гЛо^ сигЖ-Svj^araruZ' Shoev6ic&< ооегХfm, f- 3S3-3M.

63. WbvX <?. dzlnftlcL' J, dzofy- C&sns <?a°,

64. AMTRAtt lysderru ^cUu^vo^ioru^ J96v. ^ A/40, p. 2,1-XI