автореферат диссертации по приборостроению, метрологии и информационно-измерительным приборам и системам, 05.11.16, диссертация на тему:Разработка алгоритмов проектирования бортовых измерительно-вычислительных систем

САНКТ-ИЬТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ ЭЛЕКТРОТЕХНИЧЕСКИЙ

УНИВЕРСИТЕТ

На правах рукописи

Королев Павел Геннадьевич

РАЗРАЮТКА АЛГОРИТМОВ ПРОЕКТИРОВАНИЯ БОРТОВЫХ ИЗМЕРИТЕШЮ-ВЫЧЖЛИГМЬНЫХ СИСТИЛ

Специальность: 05.II.16 - Информационно-измерительные системы

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

I

Санкт-Петербург - 1993

Работа выполнена в Санкт-Петербургском государственном электротехническом университете.

Научный руководитель -

доктор технических наук профессор Чернявский Е.А. Официальные оппоненты:

доктор технических наук профессор Кондрашкова Г.А. кандидат технических наук доцент Ерастов В.Д.

Ведущая организация - Научно-исследовательский институт электронного приборостроения, г.Санкт-Петербург.

Защита состоится г. в>часов

на заседании специализированного совета К 063.36.04:Санкт-Петер-бургского государственного электротехнического университета по адресу.' 197376, Санкт-Петербург, ул.Проф .Попова, 5."

С диссертацией можно ознакомиться в библиотеке- университета

Автореферат разослан " ХЭ9_? г.

Ученый секретарь

специализированного совета ЮРКОВ Ю.В.

-1 -

ОБЩАЯ ХАРАКТЕРЖТИКА РАБОТА

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

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

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

Цель работы. Рассмотрение существующих методов проектирования систем, разработка критериев эффективности при проектировании

ИВС, разработка и применение новых алгоритмов проектирования'оптимальных ИВС на этапе выбора состава измерительных средств, оце-нна эффективности применяемых алгоритмов, практическая реализация жадных алгоритмов (ЖА) для задач выбора Номенклатуры и составлен ния расписаний.

Методы исследования. Результаты исследований, включенных в диссертацию, базируются на методах математического программирования, теории исследования операций, комбинаторике, теории точности, а также на накопленном опыте и результатах в области проектирования ИВС для испытаний летательных аппаратов (ДА) при выполнении НИР на базе кафедры Ш СПбГЭТУ, ШО "Сфера", НПО "Красная Заря".

Научная новизна. Основные научные результаты, выдвинутые на чащиту состоят в том, что исследованы и разработаны:

1) Методика построения эффективных алгоритмов проектирования ИВС, включающая следующие этапы:

- анализ исходных данных проектирования, определение вида критериальных функций и функции полезности, определение множества возможных решений;

. - сужение пространства поиска с помощью сепарабельного критерия и безусловного критерия предпочтения;

- упорядочение множества потенциальных возможностей (ШВ) в зависимости от показателя важности сигнала и от функции полезности;

- проверка независимости возможных решений от критерия эффективности; реализация жадного алгоритма;

• доказательство оптимальности полученного решения.

2) Алгоритмы выбора состава измерительных средств и составления расписания их работы на основании предложенной классификации задач.

Проанализированы также возможности применения 'комбинаторных алгоритмов для проектирования ИВС.

Практическая ценность. Разработанный алгоритм реализован в качестве фрагмента пакета программ для автоматизированной подготовки структуры измерительной системы и составления расписаний работы измерительных модулей. Работы выполнены в рамках НИР И1ТГ-124, МГ-139, внедрены на НПО "Сфера" с экономическим эффек-

трм 500 тысяч рублей, на Ш0 "Красная Заря" - 70 тысяч рублей и в Щ "Экобазис".

Апробация результатов работы. Основные результаты работы обсуждались на:

- XII Всесоюзной НТК по измерительным информационным системам ИИС-91, Ленинград 1991,

- Городском научно-техническом семинаре "Применение средств вычислительной техники в измерительной технике", Ленинград, 1990,

- НТКППС ЛЭТИ им .В. И. Ульянова (Ленина), Ленинград, 1992,

- Всесоюзной НТК "Измерительные системы, приборы и преобразователи", Москва, МЛЭМ, 1988.

Публикации по работе. К основным публикациям по теме диссертации относятся 6 печатных работ, из которых I статься в межвузовском издании, 3 тезисов докладов на всесоюзных НТК, I депонированная рукопись и 1 авторское свидетельство.

Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения, списка литературы, включающего 108 наименований, и трех приложений. Основная часть работы изложена на • 163 страницах машинописного текста. Работа содержит 7 рисунков, 5 таблиц.

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

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

Проектирование ИВС - сложный творческий процесс, который распадается на задачи, поддающиеся формализации, и неформализуе-мне. К первой группе относятся задачи выбора структуры системы и выбора структуры измерительного тракта (ВСС и ВСИТ). К задачам, поддающимся решению вычислительными катодами, можно отнести выбор параметров элементов тракта (ВПЭТ), выбор состава измерительных средств (ВСЮ) и выбор состава и характеристик вычислительных средств (ШВС). По уровню сложности задачи проектирования ИВС классифицируются как задачи измерений без датирования (НИ) и из-

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

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

Применение классических методов Ш (линейное программирование, градиентные методы) при проектировании ИБС затруднено, так как' они требуют линейности пространства параметров и дифференцируемое™ целевой функции. Показано, что задачи ВСИС классифицируются как дискретные оптимизационные задачи, решаемые методами комбинаторного программирования. Задачи выбора номенклатуры (ВН) и составления расписаний (СР) являются труднорешаемыми задачами, однако для них могут быть построены эффективные алгоритмы, т.е. такие, которые могут быть решены за полиномиальное время. Эти алгоритмы разрабатываются в третьей главе.

Вторая глава посвящена постановке задачи и анализу задания.

, Задание на проектирование формулируется в виде множества сигналов ~ "¿»м■> критериальных функций целевой функции I/- и множества измерительных моду-

лей М1={Ми ], где ИСк - номер ре-

жима работы С модуля, <9 - номер характеристики модуля.

Проанализированы возможные способы задания метрологических характеристик множества сигналов задания ■/'. Параметры матрицы Я 1 которые необходимо проанализировать при выборе МХ ИМ - это диапазон измеряемого сигнала, выходное сопротивление преобразователя, требуемая погрешность измерения.

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

следующим образом:

# = [Ш•*>/.Ф.А.....Л (1 >

где ¿->/4у - статическая характеристика погрешности измерения сигнала. При этом ¿Лу может быть задана различными способами:

1) - & у - предельная абсолютная погрешность;

2) ^уг - у5/ - относительная погрешность;

3) -х - ереднеквадратическое отклонение.

В свою очередь, в векторе характеристик ИМ содержатся его метрологические характеристики и>р1

Если задан предел допускаемой абсолютной погрешности, может быть задано одним числом Ах-* я или деумя числами Лх * в 11 + ¿'х) ; если задан предел допускаемой приведенной погрешности (-)р--¿Г-- - -Р ] если задан предел допускаемой относительной погрешности и в зависимости от того, как определена абсолютная погрешность с^р< =г йг/х ^рс или

^ = - [с * с/(!

Если же погрешность ММ носит сложный функциональный характер, вектор характеристик ИМ должен содержать ссылку на формулу, на алгоритм ее вычисления или на таблицу. Греоование многокгшальнос-ти приводит к тему, что МХ ИБС имеют векторный характер, причем каждый элемент этого вектора равноправен

р5 = .. . .. . со?«,] у

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

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

Для измерений с датированием в векторе характеристик сигнала задаются: I) требуемая частота измерений сигнала Ру (или максимальная частота в спектре сигнала); 2) параметр привязки к конкретному моменту измерения С/ относительно начала периода измерений Ти ; 3) динамическая погрешность второго рода Для

модулей А/с" должны быть известны следующие динамические характеристики: I) время преобразования 2) максимальная частота измерений /<><гг 3) погрешность датирования отсчета и) .

При наличии на входе Ш (многоканального АЦП) устройства выборки и хранения (УВХ) но из-за многоканальности ИБС и необходимости запуска на одном такте синхронизации £ модулей,

9 может возникнуть погрешность датирования из-за "дрожа-

ния" частот опроса.

Количество модулей, которое может быть запущено йа одном такте синхронизации

о ± ,

где ¿лоя - время выполнения процессором команд запуска ИМ. Показано, что для оптимизации ИБС необходимо удовлетворись все ограничения и организовать такой критерий качества,' который бы позволил, с одной стороны, утверждать, что система построена' наилучшим образом, а с другой стороны - строить эффективные алгоритмы. Учитывая то, что конфигурация системы выбирается для измерения перечня сигналов, находившегося в «Г необходимо пользоваться функцией полезности (ФП), т.е. таким критерием эффективности, который учитывает не только технические характеристики ИМ, но и их влияние на возможность измерения сигналов из В основу ФП автор считает целесообразным положить аддитивный критерий эффективности, который, несмотря на известные недостатки, может быть использован для небольшого числа оптимизируемых параметров (реально - 4-5). Функция полезности

V- Кп • У\

где- А"п - коэффициент полезности, У - аддитивный критерий

Д^сА "(¿У

^ С / 4 >

где - коэффициент важности параметра качества, определяющийся по методу экспертных оценок с применением ранжирования,

, ^/¡^ - нормированное значение •&■ параметра ка-, чества I Ш, позволяющего измерить / сигнал, ^с - коэффициент выбора I ИМ к реализации из множества ИМ, позволяющих измерить / сигнал ( уз,- £ если Ш выбран, в противном случае).

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

ти всей системы суммируются, таких как аппаратные затраты, стоимость, потребительская мощность, масса, габариты, объем.

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

При измерениях без датирования параметром ИМ, влияющим на его способность измерять сигналы, является число его входов.

Коэффициент полезности вычисляется по следующей формуле:

К„г = /фмтл< } (3)

С?^ - /¿/¿] /У , (4)

где Фи? - количество модулей, необходимое для того, чтобы измерить все сигналы из задания, которые зтот модуль может измерить по своим параметрам, - количество сигналов из «V, которое может измерить I модуль, А/с - число его входов.

Если предполагается использовать проектируемую систему на серийных ЛА, целесообразно воспользоваться "критерием обобщенной стоимости"

При проектировании ИБС для измерений с датированием необходимо классифицировать сигналы задания в соответствии с жесткостью требований, предъявляемых к их измерениям, т.е. в зависимости от привязки к конкретному моменту времени Еу, от требуемой частоты измерения ^ и от требования для измерений спецмодуля (прецизионного источника тока или напряжения для занитки измерительного преобразователя) /7/.

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

где , Ту - время измерительного эксперимента, п - количество део-ачных разрядов, необходимое для представления числа возможных измерений за %?~<г>"'> - весовые коэффициенты, приводящие зна-1ения параметров и /7/ (эти параметры могут быть равными О 1Ли I) к старшим разрядам двоичного кода ПВО.

Если целью составления расписания является максимальное

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

¿1

7 ¿¿г

Vр -

Р тР.

где -7/, _ время работы процессора по предобработке ре-

зультатов, которое может достигнуть теоретического максимума при ^¿-^-¡тох:, — /псп, т.е. при минимальном числе интервалов . для вычисления и при их максимальной длительности.

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

Оптимизировать в последнем случае можно, как и в задаче ВН, состав Щ в соответствии с критерием минимума аппаратных затрат или минимума погрешности датирования.

.На полезность ИМ в задаче составления расписаний влияют: I) число входов Ш; 2) соотношение времени преобразования . и периода эксперимента % , иначе говоря, число тактов синхронизации измерительной части системы, занимаемых одним щитом измерения; 3) частота измерений j сигнала Д; 4) совпадение или несовпадение параметра различных сигналов, которые может измерить данный модуль; 5) число сигналов из «5* которые Ш можес измерить в соответствии со своими метрологическими характеристиками.

Для определения качества модулей при составлении расписаний к вычислении значений функции полезности введены функции занятости для измерительного канала и измерительного модуля, использующие единичную ступенчатую функцию. Функция занятости модуля выглядит следующим образом:

/У = г Р* у/2 - - - П& и) -- и(ь - еь -л&Ъ ~ й,

где /С - номер канала в модуле, Рь = / если к К. -му входу ИМ подключен какой-либо сигнал, Я^-о в противном случае, £к~ число тактов "начального сдвига" для сигналов с дё*. -

число тактов синхронизации, занятых преобразованием модуля, д£-1/ - длительность такта синхронизации, Д- периодичность запуска ИМ на преобразование, Мкк, - число измерений по -с -му входу за период 7и ■

Для разработки эффективных 'Оптимальных алгоритмов задачи выбора номенклатура и составления¡расписаний классифицированы в зависимости от соотношения числа сигналов в задании /и и числа доступных модулей а также от числа входов Ш Д/оМг--^] > ■

А/^А/м^'п)- л/4-М*/л >/п) .

Для расширения функциональных возможностей ИБС при решении задач СР введен еще один признак классификации - возможность параллельной работы приборов (при их недостаточном быстродействии, но. при входном сопротивлении," удовлетворяющем ограничениям) ( ' параллельная работа приборов запрещена, - разрешена).

,/1о[л--т>-б) ; А г - /¡„С"*»Ь ./Ь = А* ) \

Аг'/. Ас*-&»{/»■<», 4)] /}; .

Задачи и А представляют собой хорошо описанную в литературе задачу назначения.

Наибольший интерес для проектирования ИБС представляют задачи ' и 4(,-т /1г.

3 соответствии с принятым подходом к проектированию ИВС необходимо выполнить следующие этапы:

1. Подготовка технического задания на измерительный эксперимент и технических ограничений на систему V/.

2. Выбор оптимизируемых параметров в виде функции полезности

V,

3. Формирование множества возможных решений путем "логического умножения" матрицы М на транспонированную матрицу (У

«л ^ ■

где PiJ = С ¿с - вектор характеристик I модуля в /с режиме, если л/<> ■ т.е. каждый элемент вектора "покрывается"

соответствующим элементом вектора ЛЛ'/с и -Ау = о в противном случае.

Под "покрытием" одного элемента другим здесь понимается то, что каждый параметр е т.е. каждый параметр каче-

ства ИМ удовлетворяет требованиям измерительного сигнала.

4. Анализ характеристик ИМ, попавших в матрицу Р' на непротиворечие ограничениям И/ с учетом их сепарабельности.

-//а- ■ /А//,

<,„„ ¿¿¿Г^ Г £ „¿,^¿0 ¿.¡Л ^

¿1Рей/ / а <

- ;

«/* ^ если /,#""'" (г-у)'

I "

1Л/б>,]] ^ ¿а^е .

Мр - множество допустимых решений ВДР, т.е. множество моДу- , лей, оставшихся для дальнейшей обработки.

5. Удаление из безусловно худших модулей на основании безусловного критерия предпочтения (БКП).

* 1 . /и Ф Р, если ?

и если ^ыг > ) = /

В результате формируется множество Р называемое множеством потенциальных возможностей.

6. Упорядочение столбцов МГ1В, т.е. сортировка сигналов по степени сложности их измерения - эта задается видом решаемой задачи - // или А

1. Вычисление для каждого ИМ, попавшего в ШВ, аначения функции полезности.

8. Упорядочение строк ШВ в соответствги со значениями И. Э. Реализация жадного алгоритма в соответствии с типом реша-

емой задачи - Мх или Ах .

Доказано, что подмножество £ множества Р должно быть независимым относительно критерия эффективности.

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

В третьей главе в соответствии с предложенной классификацией разработаны жадные алгоритмы для решения задач ВН > , и А/^ и для решения задач СР д/, А*, А*, АЛ А*; значок

^ соответствует критерию эффективности, связанному с точностью или быстродействием модулей, значок А - критерию, связанному с аппаратными затратами (масса, габариты, объем, стоимость, энергопотребление).

Для каждой из перечисленных задач выполнена проверка условий, позволяющих утверждать, что множества Р и С) (ШВ и множество' возможных решений) образуют матроид, что в соответствии с теоремой Радо-Эдмондса доказывает возможность отыскания оптимального решения с помощью жадного алгоритма..

Все разработанные в третьей главе алгоритмы записаны на некотором "алголоподобном" языке с применением знаков операций на^ множествами. Такая-запись позволяет, с одной стороны, избежать неоднозначностей естественного языка, а о другой - применять общеизвестные понятия различных циклов, встречающихся в вычислительных алгоритмах, а упрощенная запись операций над множествами дает возможность без требующейся для написания программ строгости и детальности, "не затемняя" алгоритм, описать его укрупненные • части.

Однако для понимания идеи алгоритмов предлагается следующая формальная запись. ^

Алгоритм решения задачи

£42 Ср) = р[р0ы(¿тп(рс- Фо)$0К (р))1\

где РФ* - функция определения числа однотипных модулей, включенных в конфигурацию системы, £/пй? - функция поиска первого ненулевого элемента в столбце, д/^ - упорядочение сигналов по неубыванию числа ИМ, которые данный сигнал могут измерить, 4 - упорядочение строк Р по неубыванию значений функции полезности.

Наибольший практический интерес представляют задачи У/ и . Для их решения применяются усложненные жадные алгоритмы,

переупорядочивающие пространство поиска в соответствии с изменяющимся значением функции полезности.

= Фо)!¿¡(^(РЩ, Ру ^

£ - ¿7 [{РО«(ры - ^ ¿) А >0)р

" ""У.

ч =

Р> = и [(гс?* (ри ¿О>о)ргк :--0} г ¿¿> г ^ 1

-/ >

где функция отвечает за переупорядочение.

г/Ядуиие,

£А7ф)--и1&[^(ш;п(р;;¥о){£*(7;(4 К/Р. Рз - Д [(рс* Ф о)!~(ри = 0) е< ¿.> о)^

^ Л**^¿Г"', 2-/¿у7

где Р-д - упорядочение сигналов по неубыванию погрешности датирования, - упорядочение сигналов по невозрастанию показателя важности сигнала (5), tfBij>) - проверка несовпадения моментов измерения разных сигналов одним модулем.

Для всех разрабатываемых алгоритмов оценена вычислительная

СЛОЖНОСТЬ. Л /* 2 г )

где Л - число тактов синхронизации за период Ти .

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

Четвертая главз посвящена разработке информационной базы проектирования ИВС и разработке обобщенной методики проектирования.

Каждый измерительный модуль в X режиме характеризуется следующими параметрами:

Мс'г. йс, Я ®/п;,

. ¿С, 7С, ,

где

Шс - вид носителя информации

с - вид измеряемой характеристики физической величины 2) г к- диапазон измерения

все. - вид нормированной характеристики погрешности ■ - численное значение погрешности - время преобразования Дс/с . - значение входного сопротивления О'ь - потребляемая мощность модуля , /т7с - масса модуля 6с, Сс - габариты модуля ¿г^/ - вид питающих напряжений

- численные значения питающих напряжений с: тип интерфейса {С ¿а.] - управляющие слова 2 ' - стоимость модуля /Уй - количество входов ИМ.

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

Предложена методика решения задач, связанных с выбором оптимального состава измерительных средств ИВС, включающая следующие этапы:

I. Определение назначения объекта, яа котором будет установлена измерительная система, и определение цели применения системы (испытания, исследования или контроль). На данном этапе необходимо определить перечень свойств, по которым оценивается полезность

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

2. Формирование функции полезности на основании.оптимизируемых параметров

3. Формирование множества возможных решений на основании правил анализа параметров-ограничений

4. Сужение пространства поиска решений с учетом сепарабельности свойств.

5. Сужение пространства поиска с помощью безусловного критерия предпочтения.

6. Проверка независимости множества возможных решений от • критерия независимости, при этом необходимо произвести отдельно проверку независимости элементов строки и независимость строк.

7. Если ^Р> У? образуют матроид, то после упорядочения множества Р оптимальное решение формируется простейшим жадным алгоритмом, в противном случае применяются следующие способы поиску, решения:

1) реализация переборного алгоритма,

2) реализация приближенного эффективного алгоритма с соответствующей оценкой погрешности,

3) реализация усложненного жадного" алгоритма на каждом шаге переупорядочивающего пространства поиска.

- Для задач составления расписаний вычислительная сложность оценивается полиномом пятой степени от размерности задачи и реально время выполнения таких задач составляет несколько десятков секунд. Разработанные алгоритмы реализованы в виде пакета программ. На начальных стадиях методики использована система управления базами данных С&'ррег реляционного типа, жадные алгоритмы реализованы на языке Тиъбо-с

Результатом выполнения алгоритма являются таблицы данных для

и параметров, влияющих на полезность ИМ

Кш - гг /сои «Зг /¿>2 е , П&г

£п; ■ К/

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

Основные результаты работы.

1.! Сформированы, требования к описанию характеристик сигналов/ которые необходимо определить при постановке задания на проектирование .

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

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

4. Разработана методика построения алгоритмов решения задач проектирования' ИВС на этапе выбора состава измерительных средств.

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

6. Алгоритмы реализованы в виде прикладных программ,' внедренных на трех предприятиях Санкт-Петербурга.

Основные научные результаты работы опубликованы в следующих зечатных трудах:

1. Алексеев В.В., Королев П.Г. Оптимизация измерительно-вы-гаслительной системы в условиях жестких временных ограничений/ Тезисы докладов ИИС-91. С.-Петербург, 1991. - с.44-45.

2. Алексеев В.В., Комаров Б.Г., Королев П.Г. Интерфейсный 5лок для бортовой ИШУ/ Тез.докл.Всесоюзк.науч н.-техк.конф. ^мерительные системы, приборы и преобразователи. - М,: МИЭМ, [988. с.27-28.

3. Алексеев В.В., Комаров Б.Г., Королев П.Г. Расширение лирического диапазона микропроцессорного измерительного модуля// ?езисы докладов ИИЗ-89. Ульяновск, 1989. ч.1. - с.44.

4. Алексеев В.В., Королев П.Г. Оптимизация режимов и состав-

ление расписания работы модулей измерительной системы/ Санкт-Пз-тербургск.аяектротехи.ун-т. СПб., 1993. - 25 с. Деп. в Информ-прибор Ю.Ов.93, f5I32.np. 93.

5. Королев П.Г. Составление расписаний работы многоканальных модулей ИБС/ Известия ЭТИ, вып.446, с.29-33. - СПб.: ЭТИ, 1992.

6. A.c. 1508249 СССР, ЫКИ 06 7/26, Аналого-цифровой функциональный преобразователь/ В.В.Алексеев, Н.И.Бятюгова, Б.Г.Комаров, П.Г.Королев (СССР). - 434163/24-24; Заявл.25.02.88; Опубл. 15.09.89, Бюл. Ш.

Подл, к печ. I2.II.9J г.

Печ.л. 1,0

Тираж 100 экз. Зак. й 247

Формат 60x84 1/16 Уч.-изд.л. 1,0 • Бесплатно

Ротапринт СПбГЭТУ 1197376, Санкт-Петербург, ул.Проф.Попова, 5.