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

ЛЕНИНГРАДСКИЙ ОРДЕНА ЛЕНИНА И ОРДЕНА ОКТЯБРЬСКОЙ РЕВОЛЮЦИИ ЭЛЕКТРОТЕХНИЧЕСКИЙ ИНСТИТУТ имени В.И.УЛЬЯНОВА(ЛЕНИНА)

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

АНКУДИнОВ ГЕОРГИИ ИВАНОВИЧ

УДК 6Ы.5 + 6S.OII.56

МЕТОДОЛОГИЯ СТРУКТУРНОГО СИНТЕЗА СЛОЖИМ ОБЪЕКТОВ НА ОСНОВЕ ЛОГИКО-КОЬИлАТОРНОГО ПОДХОДА

Специальности:

Ob.I3.OI - Управление в технических системах, 05.13.Об - Автоматизированные системы управления

АВТОРЕФЕРАТ

диссертации на соискание ученой степени доктора технических наук

Ленинград - 1909

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

Официальные оппоне;

доктор технических наук доктор технических наух доктор технических наук

профессор ИГНАТЬЕВ Ы.Б. профессор ЛШШШЙ Ю.А. профессор ЦВИРКУН А.Д.

-Ведущая организация - Ордена Ленина Институт кибернетики ^ имени В.М.Глуикова АН УССР

Защита состоится

на заседании специализированного совета Д 063.36.04 ленинградского ордена Лепила й ордена Октябрьской Революции электротехнического института имени В.И.Ульянова (Ленина) по адресу: 197022, Ленинград, ул. Проф. Попова, 5.

С диссертацией можно ознакомиться в библиотеке института. Автореферат разослан "3 "_^ Лме/ш 1э/£>годе.

Ученый секретарь специализированного сонета

Аветов Ю.В.

I. ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

Объектом исследования являются

автоматизированные системы управления (АСУ) различных уровней, включая АСУ предприятиями, автоматизированные системы научных исследований (АСНИ), систеьи автоматизации проектирования (САПР) и АСУ технологическими процессами (АСУТП), а также отдельные компоненты указанных систем.

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

Методы структурного синтеза и репекия, принимаемые на ран-troc стадиях проеютфования нового объекта, существенным обрапом 1лиявт на вероятность успешного аазевления и техннко-зкоиоии-юский уровень разработки новой техники. Ошибки, допущенные на >талэ выбора структуры, как правило, не могут быть скомпэнеиро-тни на последующих стадиях проектирования а, в частности, за :чет оптимизации параметров объекта.

Тем или «шым аспектам проблема структурного синтеза посвя-|ены работы сарубгяных ученых Ф.Цэикки (США), В.Хубки (£FT), д.Федора (США) и других, а также работы советских учет« ¡.И.Артоболевского, Е.П.Балалюва, Я.А.Грундспенькиеа, А.М.Доо-1янкина, И.А.Лазарева, Б.С.Иихалэвкча, И.П.Норенкова, А.И.Поло-инкина, Г.С.Поспелова, Д.А.Поспелова, И.С.Потемкина, А.Д.Цвир-уна, А.Г.Чачко к других. Общее состояния теоретических основ

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

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

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

3. Отсутствуют эффективные алгоритмы, процедуры и численна« штоды репония оптимизационных задач структурного синтеза.

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

Цели и задачи исследования. Целями исследования является:

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

2. Приложение разработанных методов в задачах исследования и проектирования на ранних стадиях АСУ и их компонентов.

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

1. Анализ, систематизация и обобщение существующих подходов к постановка и решению задач структурного синтеза.

2. Исследование И-ИЛИ-графов и плекс-грамматик и разработка рекомендаций по их использованию для моделирования МАВ с учетом характера задач структурного синтеза АСУ.

3. Исследование способов построения и свойств характеристических булевых функций (ХБФ), представляющих ЫАВ в задачах структурного синтеза.

4. Исследование особенных скобочных нормальных форм (ОСНй) характеристических булевых функций, способов их построения и

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

5. Разработка методов и алгоритмов взаимного преобразования форм представления MAB: морфологических таблиц (МТ), И-ИЛИ-графов, плекс-грамматик, ОСНФ, систем булезкх уравнений (СБУ) и линейных псевдобулевых ограничений (СЛГО).

6. Разработка и исследование численных методов решения оптимизационных задач структурного синтеза на ССНЬ, нагруженных параметрическими моделями элементов.

7. Приложение методологии структурного синтеза, базирующейся на логико-комбинаторном подходе, в 'задачах управления и проектирования информационного, программного и технического обеспечения АСУ.

8. Экспериментальная проверка и оценка эффективности разработанных методов.

Предмет и метод исследования. Предметом исследования являются теоретические и прикладные вопросы создания моделей и методов структурного синтеза сложных объектов в задачах управления и проектирования на ранних стадиях с учетом характера предметной области АСУ:

1. Методы и формы исходного представления ЫАВ: морфологические таблицы, И-ИЛИ-деревья и графы общего вида, плекс-грам-матики, аппарат символической логики; формы рабочего представ- • ления MAB; алгоритмы взаимного преобразования форм представления MAB.

2. Параметры различных форм представления MAB и алгоритмов взаимного символьного преобразования этих форм.

3. ОСНФ, предложенные в диссертационной работе, как средство структурирования (частичной или полной факторизации) rmo-странства поиска в задачах структурного синтеза.

4. Модели оценки эффективности вариантов структуры ОН: формулы свертки частных коитериев (показателей качества), целевые функции и функционалы задачи структурного синтеза.

5. Человеко-машинные процедуры структурного синтеза, символьно-численные методы решения оптимизационных задач структурного синтеза с учетом степени определенности их постановки.

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

7. Эффе ктивность логико-комбинаторного подхода при решении прикладных задач структурного синтеза АСУ и их компонентов.

Метод исследования моделей представления знаний о предметной области и алгоритмов структурного синтеза основан на использовании математического аппарата символьной логики, формальных грамматик, теории графов, теории алгоритмов и дискретной оптимизации. Отдельные положения, выдвинутые в диссертационном исследовании, сформулированы в виде теорем и строго математически доказаны. Для исследованных форы представления MAB, алгоритмов их символьного преобразования и решения оптимизационных задач структурного синтеза получены приближенные оценки сложности. Теоретические выводы подтверждены экспериментами с ППП SYNVAR.

Научная новизна диссертационного исследования заключается в создании нового направления в методологии структурного синтеза сложных объектов в задачах управления и проектирования с учетом характера предметной области АСУ, названного логико-комбинатор-иьм подходом, в основе которого лежат формализация описания знаний, относящихся к конкретной предметной области стр} турного синтеза, с помощью аппарата формальных грамматик (плекс-грамма-тик), И-ИЛИ-графов и символической логики, символьные преобразования этих описаний в OCHi н символьно-численные методы решения оптимизационных задач синтеза на таких формах:

- I. Впервые с единых теоретических позиций выполнены анализ и систематизация средств представления MAB в задачах структурного синтеза: МТ, И-ИЖ-грефов, СБУ, СЛГЮ, плекс-грамматик. '

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

3, Обоснована целесообразность систематического использова-чия аппарата символической логики на этапе форлалиаации и алгоритмизации правил комбинирования, порождающих i-iAB структур. Разработаны принципы представления множества структур в виде ХБФ для шгх PUCCMOIDCHWÄ в диссертации форы исходного представления МБ и постановок задачи структурного синтеза.

4. Предложен новый вид структурированного представления гшсжества структур - OCHq, меяедоитш фу:'.дален?альуще свойства этих ферм и обоснована цздосесбразкссть их использоьания для продставлйи.<я МЛ В в га.зечах структурного синтеза.

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

для соответствующих видов исходного представления MAB.

5. Разработань эффективные символьно-числзнкые метода решения переборных задач структурного синтеза, основанные на частичной или полной факторизации пространства поиска, представленного в виде ОСНФ MAB. Эти методы заключаются в последовательном сужении исходного множества структур с помощью процедур отсеивания отдельных подмножеств с учетом ограничений технического задания (13), на основе оценок оптимального значения целевой функции м выявления парато-оптимальных решений.

6. Получены оценки сложности различных форм представления MAB, алгоритмов их взаимного преобразования и инвариантных алгоритмов суиекия MAB, представленных в виде ОCHI.

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

2. Разработаны алгоритмы, процедуры и программное обеспечение, реализующие инвариантные задачи структурного синтеза.

3. На база обвей методологии разработаны методики структурного синтеза аппаратных средств (усилителей воспроизведения, специализированных ЭВМ, вычислительных комплексов), программного и информационного обеспечений автоматизированных систем.

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

Реализапия результатов исследования. Работа выполнена на кафедре системотехники и ЭВМ Северо-Западного заочного политехнического института. Отдельные результаты исследования - логико-комбинаторные методы структурного синтеза и программное обеспечение в виде пакета прикладных программ 54 NVA R - внедрены в научно-исследовательских работах кафедры, а также в других организациях:

1. Методы структурного синтеза схем управления запоминающих устройств (усилителей воспроизведения) внедрены в научно-исследовательских и опытно-конструкторских работах НПО "Авангард".

2. Математический аппарат плекс-языков и плэкс-грпмматик

внедрены в НПО "Марс" для оптимизации состава программного обеспечения и при разработке генератора тестовых наборов данных доя испытаний программного продукта.

3. Математический аппарат преобразования И-ИЛИ-графов и решения оптимизационных задач на особенных скобочных формах внедрен е НГЮ "Авангард" при создании банков данных для САПР радиоэлектронной аппаратуры.

4. Структура автоматизированной системы переформатизации макетов гидрометеорологической информации, разработанная на основе логико-комбинаторного подхода, внедрена в 525-м научно-исследовательском океанографическом центре МО.

5. В производственном объединении "Ленинградский электромеханически;"1. завод" имени 60-летия Союза ССР логико-комбинаторный подход использоЕан при разработке основных концепций АСУ участком сборочного производства ГПС,

6. В инженерном центре ГГ1С ЛПИ кы. И.И.Калинина при разработке информационного, программного и технического обеспечения системы управления в рамках программы 0.16.10 ГКНТ "Создать и освоить ГАП на основе передовых технологических процессов, гибких переналаживаемых комплексов,, ггромьшленнщ: роботов и микропроцессорной техники" на 1935-90 гг.

Суммарный годовой экономический эффект от внедрения логико-комбинаторних методов в указанных работах составляет около 400 тыс.руб.

Отдельные элементы логико-комбинаторного подхода внедрены в научно-методическо,! работе и учебном процессе вуза при подготовке инженеров-системотехников по специальности 0608, а также в кандидатских диссертациях В.А.Победиова и А.Е.Сафонова,- защищенных по специальности C5.I3.06.

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

- Ш Всесоюзной ыехБузовской научно-технической конференции "Достижения и перспективы развития технической кибернетики" (Киев, 1975 г.);

- Научно-практическом совещании секции системотехники ЛОС НТО РдС им. А.С.Попова (Ленинград, 1975 г.);

- 1У Всесоюзном симпозиуыо по проблемам системотехники (Ленинград, 3980 г.);

- четвертой школе-семинаре по интерактивным системам

(Тбилиси, 1982 г.);

- IX Всесоюзном совещании по проблемам управления (Ереван, 1983 г.);

- Ü1 Всесоюзной конференции "Автоматизация поискового конструирования и подготовка кадров" (Иваново, 1983 г.);

- заседании семинара "Тзория автоматов" секши вычислительной техники ЮС НТО РХ им. А.С.Попсва (Ленинград, IS88 г.);

- УП научно-техническом семинаре "Системный анализ и методы проектирования АСУ в промышленности, транспорте и связи" на тему "Проблемы автоматизированных систем управления и принятия решений на базе знаний" (Ленинград, 1988 г.),

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

Структура и объем работы. Диссертационная работа излсдана на 299 страницах машинописного текста и состоит из введения, семи глаз, заключения, указателя литературы на 132 наименования н приложения; содержит 33 рисунка и 28 таблиц.

Введение посвяшено анализу подходов к тесанию ггооблеыы структурного синтеза, глава I - основным положениям логико-комбинаторного подхода к задачам структушого синтеза АСУ, глава 2 - символьным методам построения ОСНФ, глава 3 - инвариантным символьно-численным методам решения оптимизационных задач на ОСНФ, главы 4 и 5 - И-ИЛИ-графам и плекс-грамматикам для моделирования MAB оригинальных и типовых схем в задачах структурного синтеза АСУ, глава 6 - синтезу объектов с переменно^, структурой. глава 7 и приложение - внедрении результатов.

2. СОДЕРЖАНИЕ РАБОТЫ

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

Сложная система как объект проектирования представляется в виде иерархии подсистем, каждая из которых является объектом проектирования на соответствующем уровне. Сложность подсистемы как объекта проектирования (ОП) должна быть согласована с мощность!) проектирующей системы на каждом уровне.

Можно выявить множество элементарных компонентов, или элементов, которые считаются неделимыми (атомарными) на соответствующем этапе проектирования.

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

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

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

/ На стадии формализации описания MAB в отдельных случаях

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

На этапе формализации описания MAB целесообразно различать категории "компоненты закона функционирования, или функциональные компоненты (ф-компоненры)", "структура закона функционирования, или функциональная структура (ф-структура)" и "компоненты технической реализации, или технический компоненты (т-компонен-ты)", "структура технической реализации, или техническая структура (т-струкгура)". Закон функционирования сложного объекта тгхникк имеет структуру, которая соответствует структуре самого объекта, т.е. технической структуре, и отрат.ает свойства функционирования рассматриваемого объекта на требуемом уровна абстрагирования,. причем каждому экземпляру т-компонента в состава

ОП однозначно соответствует ф-компонент закона функционирования.

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

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

Структуру ОП, описанную в терминах фт-компонентов, будем называть фт-структурой. Фт-структура монет быть атомарной, блочной или смешанной, т.е. мок»? состоять только из фт-элементов, или только из фт-блоков, или состоит из лобих фт-компонентов.

Функционирование любого объекта, если его рассматривать на достаточно большом интервале времени, как плавило, включает изменения компонентного состава и связей меагду компонентами, т.е. изменения структуры рассматриваемого объекта. К классу объектов, которые в отдельных случаях 1®ласообразно рассматривать как объекты с переменной структурой, относятся, например, развивающиеся хозяйственные и другие системы, вычислительные комплексы и отдельные ЭВМ в процессе функдаонкроз&ния.

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

I. Компактная каталогизация множества типовых вариантов

построения компонентов технического и программного обеспечения АСУ.

2. Моделирование MAB оригинальных схем информационных устройств и систем автоматического регулирования с обратными связями, циклических алгоритмов и процедур решения функциональных задач АСУ.

Пример использования КСП-грамматики приведен в главе 7 при описании метода формализации MAB технических средств АСУ.

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

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

В более обшем случае могут быть использованы ИТ с дополнительными логическими ограничениями на сочетания значений признаков (И.С.Потемкин, Л.М.Поляков). Используются два вида дополнительных ограничений: запрещенные и обязательные сочетания,

И-МИ-деревья такяе широко известны как средство представления UAB (А.У.Дворянкин, А.И.Половинкнн, А.Й.Соболев, И.П.Но-ренков). Корень И-ИЖ-дерева (дерева вариантов) является ИЛИ- ' варашкой, либо И-вершиной, Каждая некорневая вершина представляет из себя либо концевую вершину (лист), либо корень некоторого поддерева.

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

Построение Н-ИЛИ-дерева осуизствпяется в результате многоуровневой многовариантной декомпозиции закона функционирования

ОП. В этом смысле И-ИЛИ-деревья можно рассматривать как обобщение метода ОТ. И-ИЛИ-деревья рекомендуется использовать как форму представления состава многоуровневых систем программного и технического обеспечения АСУ.

И-ИЛИ-графы общего вида рассматривались миопии исследователями как средство представления MAB в конкретных предметных областях'структурного синтеза (В.Т.Морозовский, И.М.Синдеев, К.Д.Рунов, И.А.Лазарев, А.Г.Мамиконов, В.В.Кульба, А.Д.Цвиркун, Я.А.Грундспенькис, Я.ГС.Теитерис). Как правило, это графы, отра-дающие избыточную ("обобаенную") структуру ОП, в которой ИЛИ-вершины представляют связи, или взаимодействия, элементов ОП. Т-элементы, имеющие а обпем случае любое число входов и выходов, представлены И-вершинаии.

И-ЯДИ-грзфы рассматриваемого вида представляют варианты преобразования потоков взаимодействий (энергии, вещества или информации) в"максимально избыточной структуре ОП (UllC), соот-ветствувщей уровня знаний, достигнутому в конкретной предмзтной области структурного синтеза. Одна из проблем, связанных с применением таких графов, заключается в учете контуров, образуемых потопами взаимодействий в МИС, при синтезе объектов с контуркьм и бесконтурным законом функционирования.

Областью использования потоковых И-ИЛИ-графов в задачах структурного синтеза АСУ является моделирование MAB оригинальных схем информационного обеспечения (баз данных), математического обеспечения (схем преобразования данных^ на уровне математических модулей), программного обеспечения (схем преобразования данных на уровне программных модулей с учетом конкретной схемы кодирования) и технического обеспечения (схем преобразования данных, представленных конкретными физическими сигналами, на уровне аппаратных модулей). В глава 7 приводится подробное описание метода формализации МАЗ вычислительной системы для АСУ ГПС с использованием И-ИЛИ-графов,' а в работе /I/ - метод оптимизации внешней модели реляционной базы данных.

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

(^{WtX , у , гдэ х = (X-Z\z<c Z ) - вектор булевых пе-

ременных, определяемых следующим образом: = i , если фт-эло-

шнт включен в фт-состав ОП: Xt » О в противном случае. Вектор у состоит из вспомогательных переменных, выражающих, например, связи между компонентами ОД и другие дополнительные условия объединения компонентов в правильные структуры с точки зрения реализации требуемого закона функционирования ОП. Переменные, составляющие Еектор vr » (iv^ | и € U ) определяются следушш образом: Wu «, I, если ф-элеыент U входит в ф-состав ОП;

«Ов противном случае.

Совокупность Rz правил комбинирования компонентов всегда ысено представить в виде системы булевых уравнений (СБУ);

¿„(и",*, у,..,) = 1 (Л*/?*).. (I)

Применение СБУ вида (I) как формы исходного представления HAB рекомендуется в тех случаях, когда затруднительно применение ИТ, И-ШШ-даревьев, либо И-ИЯК-графов обаего вида, КСП-грамматик, например, в задачах синтеза объектов с заранее заданной топологией. К такого рода задачам относится, например, задача размещения баз данных и вычислительных работ по узлам вычислительной сети, рассмотренная подробно в главе 7. ■

2.2. Характеристические булевы функции (ХМ). Во многих задачах систему логических ограничений (I) ыоано разделить на две относительно независимых подсистемы. Одна подсистема определяет UAB закона функционирования ОП:

Ьг{.\f, «1 (./♦<=/? ф), (2)

где /?ср - мноаество правил комбинирования ф-компонентов.

Другая подсистема определяет возможные фт-варианты реализации каждого ф-элемента (варианты покрытия какдого ф-элемента соответствующими фт-коипонентами):

kfa V =1 С«€¿0, (3)

zeZ«.

где U - множество ф-элементов задачи структурного синтеза (ф-бааис); 2-и - множа степ фт-элеменгов, покрывающих ф-элемент U. .

Совокупность левых частей уравнений системы (2) легко преобразуется в ХБФ, представляющую MAB закона функционирования: h{yrt и,.,,) = &> bfiWtVt...). (4)

ХБФ (4) позволяет свернуть СБУ (2) в одно характеристическое . уравнение: А(us,у , ...) = I. Совокупность левых частей (2) и (3) легко преобразуется в ХБФ . .

3 J иеи ■ zizu

соответствующую смешанному описанию MAB в терминах ф- и фт-ком-понентов, Однако, поскольку конечной целью является описание MAB в терминах фт-компоиентов, вместо ХБФ (5) целесообразно использовать преобразование фошулы (4) с помсдью системы подстановок

К. :e У_ l«€t/), (б)

zdZu

эквивалентной СБУ (3). Символическая запись такого преобразования имеет ыщ b (дг, у , ...)*« /г (*/,у , у/^, •

Если имеется описание преобразования, осуществляемого каадвм ф-эламентом, в виде перечня входных воздействий и выходного воздействия, то состав таких ф-элементов однозначно определяет способ их взаимодействия н взаимного соединения, т.е. структуру. Таким образом, в лобом случае MAB закона функционирования определяется соотношением Мф = { j А ( w, .") » 1 } , где у? (vi в ^ | в 1 , # ¿¿/J- - перечень ф-элеыентов,- представ-ляших некоторый вариант (состав или структуру) закона функционирования ОД.

Аналогично MAB фт-реализаций (фт-состава или фт-структуры) ОП определяется через ХБ® М = {лГ(х)| = i }

где = 1, г е Z} - перечень фт-элементов, состав-

ляющих некоторый вариант фт-реалнзации ОП.

Если описание каядого фт-элемента содержит перечень входных и выходных воздействий (связей), то состав г) таких фт-элементов, как правило, однозначно определяет структуру ОП. Неоднозначность может возникнуть в том случае, если {х ) содержит боле« двух фт-элементов, вырабатывавших одно и то же воздействие. Для устранения неоднозначности необходимо ввести дополнительные булевы переменные вида , символизирутгаше получение связи с выхода конкретного фт-элеменга z .

С помошьа известных соотношений алгебры логики ХБФ /; (v,,..) или 6 {X, ...) ышег быть преобразована в скобочную нормальнув форму (СНФ), т.е. такую форму в базисе {A,V, "]}, в которой действие знака 1 ограничено отдельными переменными. Поадстав-лениэ ХБ5 в СНФ соответствует структурная система подфункций:

[¿(jc)]

1 JCHf l сл Л),

если

d0i£>

С0(Х), если CQ 6 С , (7а)

'.5 <5 5,.

{ с^е С) , (76)

^ { х) = Яу ^ (х> € Ъ), С7в)

гда С, (аг), ¿4(х) - подфункции, выражаемые конъюнктивными и дизъюнктивными подформулами (6* - и V -подформулами) соответственно; СPs)> - множества & - и \/-поцфоомул [6(л')]С(<ф.

Подформулы db(x) и (а1) (<"£ /?<,) могут быть

вырожденными, или одноэлементными, вида ху и . Непосредственные составляющие невырожденных -подформул будем называть конъюнктами, а для V -подформул - дизъюнктами.

Понятие особенной формы ХБФ ЫАВ является центральным в ло-гико-коыб;шаторном подходе.

Определение!. Особенной скобочной нормальной формой (CClii5) булевой функции L (хг) называется СНФ 6 (•£•), в которой любая пара подформул-конъюнктов удовлетворяет требованию: если букьа Xj принадлежит одному конъюнкту, то эта буква или её отрицание Xj не могут принадлежать другому конъюнкту.

OCH'i ,функ:ши 6 (я- ) будем обозначать [ £ (:r ) JQ . Букву ду , входящую в конкретную СНФ будем называть неособенной, если эта CHI' не удовлетворяет определение I относительно рассматриваемого вхождения буквы Xj ,

GCHi ХВФ raise имеет структуру, выражаемому системой (7 а, б, ь). Графическим представлением такой структуры может быть И-ИЛИ-дереио, В свою очередь, если исходное представление MAB в задаче структурного синтеза имеет вид И-ИЛИ-дерева, то по такому представлению можно построить систему подфункций XBi вида (7 а, б,.-в) и СНг ХБ£ соответственно, пшчеы калдая И-вераина дерева даэт подформулу вида (7 6), а ИЛИ-вершина - (7 в). Однако, полученная по И-ЙЛИ-дереву СНФ ХБЗ> не обязательно является особенной.

Дерево вариантов хорошо структурировано, если множества концевых вершин лу, принадлежащих непосредственным ИЛИ-состав-ляшям любого й-поддерева этого дерева не пересекаются, т.е. если СНщ ХМ, отражавшая структуру дерева, является особенной. Хорошо сгюуктурирэзанше деревья вариантов на практике встречаются редко.

ПсяЕлоиие неособенных букз в СНФ ХБФ связано с тем, что при многовараантнсй декомпозиции ОП могут встретиться функционально чзодноро^ш.« альтернативные варианты построения отдельных блоков, что Агляетсп следствием многофункциональности некоторых чс-олсмеитов, .а такхе возможными запретами на сочетания

элементов.

Целесообразно рассматривать ХЕ$ MAB как частично определенную булеву функцию, что позволяет выбрать вариант доопределения ХБФ, которому соответствует 0СН2 меньшей сложности. Сложность или буквенная длина L ОСН'5 01йнивается числом букв, обозначающих переменные, в записи ОСНФ.

Например, первоначальная версия ХБФ, получанной из исходного И-ЙЛИ-дерева, как правило, является приближенной и уточняется в дальнейшем на всех шагах решения задачи структурного синтеза. Может сказаться, что для нормального функционирования фт-элемента. z- обязательно требуется наличие фг-элемента Zj . Это требование формализуется в виде булева ограничения X^Xj** 1. Возможны также запреты на сочетания элементов. Если включение фт-элемента в состав ОП не совместимо с фт-элементом Zj , то вводится дополнительнее ограничение — '¿у 1.

Большое число практических задач связано с построением множества А?н неизбыточных вариантов структуры СП. Вариант Л&М называется нэизбыточшм, если для любого яг'елг имеем М, где М - множество правильных (логически допустимых) вариантов. На основе рассмотрения состава неинвертировачных букв [¿(ar^lg вводится понятие ССНФ комбинаторной алгебры (К-аигабры) с операциям? объединения (U) и K-умножения семейств подмножеств. Доказываются теоремы, из которых следует, что ОСНЗ K-алгебры определяет Мн .

2.3. Символьные методы построения ССНФ. Эффективность методов и алгоритмов структурного синтеза, разрабатываемых а рамках логико-комбинаторного подхода, в значительной степени зависит от компактности особенных скобочных форм, равной N /L , где N -число вариантов, порождаемых скобочной формой, L - буквенная длина скобочной форлн.

Важным параметром СН5 является число /< уровней, или глубина. Конъюнктивная нормальная форма (KHS) имеет /V = I; -уровневая СНФ получается, из (/* - 1) - уровневой путем замены каждой переменной на некоторую КНФ. Буквенная длина -уровне-вой СНФ равна L - {L^ Lg У* , где L-% - средняя длина &-подформулы; ¿.¿г - средняя длина V-подформулы. Число вариантов порождаемыхß -уровневой CHJ, равно A'^-iJr^*'+ -

Теорема I. Асимптотическая верхняя оценка числа N вариантов,' порождаемых одноуровневой ОСНФ, зависит только от её буквенной длины: N~ 0 [е*-Р ( ¿-/©УЗ '

Для /и -уповневых ОСНЬ получена оценка И/ <ехр [¿. / •

Величину I, //« «окно рассматривать как "эффективную длину" ОСИФ, Общая длина скобочной формы зб. » ¿. + ¿' , рде ¿! - число скобок и символов логических опеоащй в её записи.

В программных средствах, реализующих символьные преобразования скобочных форм, используется операторно-скобочная запись, т.е. роль опештоосв V и играют V - и ^.-скобки. Для опета-торно-сксбочной записи <£. = 2( + ) + I , а при 1» 1 получена оданка^ -( 1 + 2 ( 1 + / /у* ) / 1))1. , где

(. ¿э^ - соедняя буквенная длина описания одного варианта.

Символьше преобразования неособенной СНФ к особенному виду выполняются в соответствии с алгоритмической схемой, в основе которой просмотр и преобразование к особенному виду отдельных & -подформул СШ5. Исследованы различные варианты реализации предлагаемой алгоритмической схемы. Просмотр и преобвазованиэ 6> -подформул может осуществляться начиная с внешних подформул {нисходящий порядок) и начиная с внутренних подформул (восходящий порядок). Преобразование неособенной конъюнктивной подформулы заключается в её разлоконш по переменным, относительно которых нарушено о-свойство этой подформулы, т.е. не удовлетворяется определение I. В работе исслэдсвано_разложение Шеннона

Сх « х Сха, V .v . (8)

Доказана теорема о том, что использование разложения Шеннона дает ОСНФ, длина которой ¿~ рез зависит экспоненциально от числа т неособенных переменных.

■ Теорема 2. Задача построения ОСИФ по заданной СНФ является NР -трудной,

Доказательство теоремы 2 основано на том, что проблема выполнимости КН<5, являющаяся эталонной ЫР -полной задачей., сводится непосредственно к построению ОСНФ заданной КНФ; КНФ выполнима, если ео ОСНФ отлична от логического 0.

Экспоненциальная сложность (.ЫР -трудность) задачи построения ОСНФ проявляется в различной степени в конкретных предметных областях структурного синтеза и является основным ограничением, определяющим возможность частичной факторизации пространства поиска в рассматриваемых задачах и, следовательно, применимость предлагаемого логико-комбикаторкого подхода. Поэтому в работе исслэдсшанн различные пути повышения компактности результирующей ОСНФ. Одшк из таких путей является применение предложенных в работа разложений с формальнцми булевыми производными:

Сх » х С'х V Сх-0 , где - выражение, содержащее переменную х ; ~ вьпзажение Сх , в котором выполнена подстановка X :» 0; С'х - формальная производная от Сх по х , получаемая по обычным правилам дифференцирования функций действительных переменных, если оператор V интерпретировать как +, а & - как х Например, для преобразования & -подформулы dx & ех к особенному виду применяется правило с(х<5>Сх ;•= xdxxex,{ V dx-o .

Специальные правила учета логических ограничений, выраженных импликациями вида х-*у- 1 и х-* у => I, которые часто встречаются при формализации MAB, также повышают компактность ОСНФ ХБФ MAB:

1. Цепочка импликаций вида , Уа-\ Уа ~ * моает быть учтена ггоавилом в виде подстановки х : - iji

2. Импликация х у = I может быть учтена правилом подстановки: х : ~ я у.

Доказаны теоремы о том, что приведенные выше правила замены импликаций не изменяют множество неизбыточных вариантов, которое представляет ХБФ.

Разработана процедура 5TR в составе ППП SVNVflR, которая осуществляет построение ОСНФ по исходной СН£. Основные подпрограммы этой процедуры: 5СН - поиск неособенных <3> -подформул и выбор по специальному эвристическому критерию наиболее подходящей -подформулы для преобразования на данном шаге; Б ХРАМ - выполнение разложения по неособенной переменной; SIM -освобождение полученной ОСНФ от логических констант и лишних скобок; FACT -.факторизация СНФ.

Обоснована приближенная оценка буквенной длины ОСНФ:

где L исх - длина исходной СН5; и-' - средняя относительная длина $-подформулы, содержащей неособенную переменную; / - средний коэффициент удлинения СНФ при её разложении относительно одной переменной (/<£); т. - число неособенных переменных.

Сложность построения ОСНФ определяется а основном сложностью анализа &-подформул, входящих в исходную и промежуточные формы: Qq ~ К0 /и (.лй + 1) ¿ИСх С 1 +• V С 1 ))т, где Кй - коэффициент пропорциональности. Разработаны следующие рекомендация: I. Нисходящий порядок преобразования СН5 в ОСНФ предпочтительнее восходящего. 2. Разложение (8) дает, как правило, лучшие результаты с монотонными ХБФ. 3. Правила замены иыпяикацпй (си. выше) повышают компактность ОСНШ.

Указанные рекомендации нацелены на уменьшение сложности построения и повышение компактности результирующей ОСНФ ХБФ для исходного представления MAB в виде И-ИЛИ-дерева, либо произвольной СБУ. Для исходного представления MAB в виде потокового И-ИЛИ -графа (ШС) с одной стороны необходимо учитывать особенности определения логической допустимости вариантов структуры, а с другой - дополнительные факторы, влияющие на компактность результирующей ОСНФ.

2.4. И-ИЛИ-графы в задачах структурного синтеза. Рассматриваются следующие множества: А - множество т-элементов (типовых элементов), причем описание каждого т-элемента имеет вид о. {ta ; ^а. вых5' где ' ^а вых ~ упорядоченные множества входов и

выходов рассматриваемого т-элемента; .5 - множество связей; Z - множество фт-элементов, причем описание фт-элемента zCZ имеет вид Z = а ( ;У2 ; ß>z ), где az , ßz - множества входных и выходных связей z , упорядоченные согласно описанию т-эде-мента, используемого в качестве z .

Фт-элеыенты, составляюшие множество описаний Z. , взаимодействуют посредством общих связей из множества 5 . Поэтому множеству Z. однозначно соответствует И-ИЛИ-граф, который можно рассматривать как двудольный орграф Бержа G - ( У, Е ), где V = Z U5 - множество вершин; £ - множество дуг вида (г , s. ) или ( £ , Z ), s <z Ь , z cZ . Множество Z представляет И-верши-ны, множество 5 - МИ-вершины.

Любой фт-элемент £G.Z характеризуется ф-преобразованием, или ф-парой uz = < «2 ; ßz > . Одну и ту же ф-пару могут иметь несколько различных фт-элементов из Z . Множество ¿4pß называется ф-базисом задачи структурного синтеза на И-ИЛИ-графе, если для любого zt:Z соответствующая ф-пара uz £ ¿>Ф6 , либо uz может быть представлена в виде композиции ф-пар из L/ф- G. ¿/Ф5 , причем для любой ф-пары <« , /3> £ ¿¿f6 имеет место <х с. <х~ , Ф-базис называется каноническим к обозначается , если

все ф-пары из U^ одновыходные.

Необходимым условием правильности, т.е. логической допустимости структуры, представленной набором фт-элементов тс С 2 является существование -fc'^TZ, для которого <XTl - асп и ßjz — fion » гДе • /сп ~ множества входов и выходов ОП

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

бесконтурности закона функционирования ОП. В отдельных случаях может быть установлен запрет на совместное использование некоторых фт-элементов из 2 и связей из 5.

Для построения ОСНФ по заданному И-ИЛИ-графу необходимо:

1. Построить множество И и выявить канонический ф-базис

и к-=рк •

2. Построить ХБФ /гп у ), представлявшую множество логически допустимых ф-структур ОП, быть может содержащее некоторое число неправильных контурных вариантов.

3. Построить ХБФ ?!к( у ), представляющую неправильные контурные варианты.

4. Построить ХБФ /г (»О, представлявшую множество правильных вариантов закона функционирования (ф-структур).

5. Преобразовать /( (IV ) в ХБФ Н х ), представляющую ыно-яэство А/ фт-струхтур. Преобразовать ¿> ) в ОСНФ.

Взаимосвязи всех ф-пар канонического базиса можно выразить системой соотноиений:

L ^ s1 {I0)

s<r a,

y se (II)

где ^h - 1. если ф-пара и включена в состав закона функционирования ОП и ь>и - 0 в противном случае; = 1, если связь 5 пюисутствует в законе функционирования и = 0 в противном случае.

С учетом (10) и (II). имеем: /¿по;у)=( & У« V

seacnU/3eil

( & )) С А- С ys V •)■).

Ыножество контуров закона функционирования удовлетворяет• системе:

{ wu V f = I U £¿/' ) ; V ^ = i

(12)

^ ~> V Wu и (U51)} ,

где - множество ф-пар канонического базиса . об-

разуюаих сильно связный подграф орграфа < > ; S' - мно-иестоо связей, встречавшихся а ^кфг, • ® работе приведен алгоритм построения U«<*>б ' На основе системы (12) легко построить выражение для (у ). Сформировав

¿ftCK 1) к (v; f) , преобразуем это выражение в ОСНФ, например, с помощью процедуры STR.

Последовательные алгоритмы позволяют повысить компактность результирующей ОСНФ для исходного представления MAB в виде И-ИЛИ-графа. Предложены две схемы последовательного построения ОСНФ.

В основе первой схемы - алгоритм AI, осуществляющий вывод Д№ ХБ5 у ). Элементарные конъюнкции этой ДНФ анализи-

руются на контурноеть. После отбрасывания "контурных" конъюнкций, получаем ДВФ ХМ ^(v), к которой применяется алгоритм факторизации F (\ С Т , что и дает [ А (ь") 10 . Алгоритм AI отличается простотой, но с ростом размерности задач резко возрастает сложность вычислений.

Вторая схема построения ОСНФ заключается в выполнении следующей последовательности процедур: 0RD - разбиение множества S на уровни; А2 - построение у ) с учетом уровня свя-

зей; «ОЫТ - выявление в у ) подформулы у),

представляющей простые контуры;К -построение ХБФ ^(v/) цу-тем удаления подформулы ) из V, у ); преобразо-

вание U') в ¿{sc) с помощь» системы подстановок

Н : = V х2 где zu-\z \ иъ uLb \ ;

etZ

STR - преобразование ¿Лх) к особенному виду.

Работа^А1 и А2 начинается с раскрытия исходного выражения ^scßсп ^s 0 помощью системы правил. Эти правила построены с использованием соотношений логики алетических модальностей, в которых использован оператор ^ - "необходимо". Правила развертывания в процедуре А2:

V хг , xz t & . у К & .уД,

Вводится модифицированное понятие ОСНФ для базиса (А ,V, }, 'Процедура А2 использует восходпччй порядок поеобразования промежуточных СНФ к модифицированному особенному виду на основе правил: ciy 3> е- : = у dl е~=1 V е^ ,

4 á с- ; v е~ и др.

Для преобразования в 4 используется (6).

2.5. Нормализация MAB в задачах синтеза объектов с переменной структурой. Функционирование объекта с переменной структурой рассматривается в дискретном времени, принимавдем значения I, ..., I i . Каждое дискретное значение модельного времени соответствует временному интервалу, на котором структура (состав) ОП считается фиксированной. MAB представляется в виде ХБФ, в которой каздая булева переменная имеет дополнительное множество индексов, показывающих на каких временных интервалах используется соответствующий компонент ОП. Понятие особенной формы ХБФ модифицируется с учетом характера задачи. В работе рассмотрены три случая.

В задаче синтеза структуры развивающейся системы ÜAB для каждого этапа задается в виде потокового И-ИЛИ-графа. В записи ХБЗ) MAB используются булевы переменные айда , определяемые следующим образом: -¿I = 1, если фт-элемент z включен в состав структуры на интервале t ; яг|= 0 в противном случае. Для преобразования ХБф к модифицированному особенному виду используются правила, основанные на формальных производных:

dxt*k $> ext e*xt V dxt*k ext^Q .

Смысл приведенного правила состоит в том, что включение некоторого элемента в состав структуры системы ка интервале t поглодает его включение на интервале t + к { к >/0) .

Полученная ОСНФ позволяет решать оптимизационные задачи с использованием показателей, характеризующих функционирование системы как на всей совокупности интервалов Г , так и на отдельных интервалах t Т. "

В задаче выбора комплекта ЭВМ для управляющего вычислительного комплекса заданы: - множество вычислительных работ, которые нужно выполнить на интервале t £ 7~ ; I tj - альтернативное множество ЭВМ, выполняющих работу j £ Jt % 2 - все множество ЭВМ. С использованием каждой ЭВМ i <= I связано значение критериальной функции G^ , а такав потребление А -го ресурса R^i ( h » I, ..., ). Требуется найти вариант комплектования { /V/ | i € 1) , где fy - число ЭВМ типа i , удовлетворяющий целевой функции X; g j GiN;mia и ограничениям

Uel^i^i С g

Для записи ХБФ используются булевы переменные веда Х^ , определяемые следующим образом: = 1, если t -я ЭВМ используется на множестве интервалов Т ; г. » О в противном случав.

В этой задаче используется модифицированное определение ОСНФ ХБФ и правила её построения, базирующиеся на элементарном правиле: если 0й » 0 , то х? & а е" := ,

В задаче выбора комплекта блоков специализированной ЭВМ функционирование ЭВМ описывается в виде ярусно-параллельной формы (НПФ). Процесс построения ОСНФ ХБФ комплектования ЭВМ можно разделить на два этапа. На первом этапе строится ОСНФ ХБ5, определяющей варианты размещения операторов ярусно-параллельной формы по тактам работы ЭВМ. На втором этапе осуществляется подстановка, выра^ашая варианты реализации операторов блоками ЭВМ. Полученная СНФ приводится к особенному вицу с помощью специальных правил.

2.6. Ш&кс-грамматики в задачах структурного синтеза. Плекс-грамматики являются наиболее общим математическим аппаратом для конструктивного представления МАВ структуры ОП. Они позволяют абстрагироваться от конкретного целевого назначения 011, т.е. рассматривать технические структуры на уровне абстрактной функции (абстрактного закона функционирования). Каждый вариант структуры, порождаемой некоторой плекс-граыматикой wn.seт вид плекса, или сети Р , состоящей из некоторого числа плекс-элемен-тов (П-элементов, многополюсников) а; .

Рассмотрены три способа описания плекса Р . Узловой способ имеет вид Р - V Г^ , где V" - список плекс-элементов (п-эле-шнтов), - список узлов. Узловой способ предложен Дж.Феде-ром.

Контактно-узловой способ: Я = ... (<п,{к'т), где

( ) - обозначение п-элемента щ , в котором номера контактов заменены номерами узлов плекса Р .

Матричный способ: Р- йг... , где I = I' т^гп -матрица конкатенации, в которой ^у - описание конкатенации а.; И йу .

Анализ показал, что контактно-узловой способ имеет меньшуо сложность описания плекса по сравнению с двумя другими. Сложность контактно-узлового способа оценивается формулой б-\р\С 1 + | £ I ") , где ! Р ! - число п-олементов в составе Р, |В | - среднее число выводов одного п-элемента.

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

нши) грамматиками и языками.

Плекс-языком (п-языком) над алфавитом /? называется подмножество ¿с А , где А - множество всевозможных плексов (исключая пустой) иод алфавитом /1 . Множество правильных вариантоз структуры в задача структурного синтеза можно рассматривать как п-язык = { Рк | «И}.

Формальной п-граыматикой называется четверка Р У, где % £ V - начальный символ; А - алфавит терминальных п-злементоа; V - алфавит вспомогательных п-злементов; - множество правил вывода вида Р г="Ч/ Р, где Р'£ (Л и У) - замещаемый плекс, Р € ( /\ О V) - замешавший плекс, Т - описание способа подстановки Р'1 вместо Р' .

Если правила вывода тлеют вид — "Ч^Р, где у£ У , Р £ (Л и 1/)+, то п-грамматика называется контекстно-свободной п-грашатикой (КСП грамматикой), а множество /. терминальных плексов, выводимых в этой грамматике - КСП-языко«.

В работа доказаны следующие теоремы:

Теорема 3. Всякий КСП-язык является рекурсивный ыножествоы.

Теорема 4. Класс КСП-языков является собственным подклассом класса рекурсивных п-языков.

Теорема 5. Свойства КСП-грачматики порождать пустой язык и порождать конечный язык алгоритмически распознаваемы.

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

Доказанные свойства определяют теоретически возможные ро-кшы использования КСП-граыматик как формы представления МАВ структуры ОП. В диссертации разработана процедура преобразования ОСН§ з КСП-грамматиКу и обратное преобразование.

2.7. Методы решения оптимизационных задач структурного синтеза.

Задача структурного сиктэза рассматривается как многокритериальная оптимизационная задача, решаемая, как правило, в диалоговом режима.

В отдельных случаях для решения оптимизационных задач структурного синтеза могут'быть использованы универсальные методы линейного псэвдобулева программирования. В диссертации рассмотрены методе сведения СБУ, определявшей множество логически допустимых вариантов, к СЛПО. Как показала практика ис-

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

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

В диссертации разработаны и исследованы методы решения оптимизационных задач структурного синтеза на MAB, заданном в виде ОСНФ. Достоинства предлагаемого подхода:

1. Факторизация пространства поиска в виде ОСНФ MAB позволяет расширить область применимости известных методов сокоаде-ния перебора и их эффективность, а также создать новые методы решения оптимизационных задач переборного характера,

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

Недостатком является зависимость требуемого объема памяти для размещения ОСНФ от степени факториэуемости пространства поиска, что выражается формулой (9): чем меньше v., ^ и м , тем лучше факторизовано это пространство.

Каждый вариант ОП оценивается набором показателей У = = ( ..., Утп ), состав которого связан с целевым назначением ОП. При проектировании АСУ используются следующие показатели: погрешность и время решения задачи или вероятность решения задачи с показателями не хуже заданных; объем программного обеспечения; габариты, масса, потребляемая мощность технических средств; стоимость и т.д. Будем считать, что все показатели минимизируются, поскольку оптимизационную задачу всегда всегда можно свести к этому случаю.

_ Обычно в задаче проектирования задают допустимые значения

( I ° I.....т ), что определяет область £? = {^ i

i « 1,/п } допустимых значений У . Отношение предпочтения наff реализуется либо при решении оптимизационной задачи в диалоговом режиме, либо в автоматическом режиме за счет использования специальной модели отношения предпочтения, которую будем называть сверткой показателей (частных критериев).

Свертка у(^) критериев, выражающая отношение предпочтения заказчика или проектировщика на Q , должна удовлетворять основному требованию: если набор У предпочтительнее У , то < f(^). В случае Ух * Ух\ = у (У") набо-

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

В качестве свертки в работе предлагается использовать ^ взвешенное среднее со степенной функцией G {у) = (Jki у;'*) , где у- « У[ / i/; , ^ - вес (коэффициент важности) / -го показателя, г - параметр выпуклости. В задачах минимизации

I, причем чем больше г , тем меньше степень взаимной компенсации показателей в равноценных наборах. Яри /*-» оо имеем £ (у ) = max. у, , , т.е.наборУ оценивается по худшему показателю (возможность взаимной компенсации показателей отсутствует). Разработаны диалоговые процедуры оценки г и ki ( /= I, т ).

Для каждого варианта ТГеМ должны быть заданы функциональные 'зависимости У = ( Х^), где Хя в - вектор параметров элементов, составляющих 71 ; - область допустимых значений XTl, определяемая физическими или другими объективными законами. Набор параметров структуры л: состоит из наборов параметров фт-элементов z G тс : Х^ « ( Xz j г 6 я: ), где Хг - набор параметров фт-элемента Z .

Задачу структурного синтеза можно сформулировать как задачу отыскания подмножества М* СМ :

A/'-Argrmn. 3

где --arg^ XjTl)| ^ 6 }.

М*\Лм | 4 C^eö, XirCYx).

Таким образом, задача поиска Х^ , т.е. задача параметрической оптимизации, погружена в задачу структурного синтеза. Все пространство поиска наилучшего варианта ОП можно предста-

вить как множество I/ вариантов технической реализации ОП, причем {Jl^-M )t где Vjz - множество вариантов технической реализации структуры Ж . Каждому варианту v £ V взаимно однозначно соответствует набор параметров Х^- € "Уд- объекта со структурой Ж . Если ввести в рассмотрение композицию / и ^ , а именно функционал F « $« f , то задача структурного _ синтеза заключается в отыскании V* = Afgrrun

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

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

Необходимое и достаточное 'условие соответствия варианта жеМ ограничениям ТЗ заключается в том, чтобы параметры варианта 7i удовлетворяли ограничению £ , где

-{ ^jiI^^x) € 52},Необходимые условия обеспечения требований "13 определяют некоторую область ^ 5 Y^ Достаточным условием для отсеивания варианта Ж является - 0 .

Информация об оптимальном значении q * целевой функции имеет вид ограничения $* ^ , где / - номер шага решения оптимизационной задачи (13). Такая информация означает, что на шаге ¡f установлен факт: ЭжсМ 3 : у ((. Хх)) =

fn(^-Ji) ^ . Оптимальное решение задачи (13) всегда принадлежит множеству парето-оптимальных решений Мп = {п\4(Хд>€раг-й}> где pai. 52 = { У\ У е 5? ,Э У'е £21 У*У\ У! У,i О'Ч,.,^ Я = { У | У = Чу, С Xtf, Xjj-£- область возможных значений У .

Характеристики каждого варианта структуры. ОП определяются как топологией, так и компонентным составом. Чисто топологических характеристик (связности, диаметра, степени централизации,

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

Как правило, сложнее вычисление показателей , зависящих как от компонентного состава, так и от топологии графовой модели ОП. К их числу относятся показатели ОП, реализованного в виде структуры JCQM с параметрами элементов Хх £ "У^ . Зависимость У1 ~ f^i ( X«) для таких показателей обычно задается алгоритмом общего вида.

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

В первую очередь применяются методы сжатия ОСНФ на основе отбрасывания подформул, не удовлетворяющих допускам, выводимым из ограничений ТЗ. В первую очередь имеются в виду ограничения на аддитивные и монотонные показатели. В результате такого сжатия получается "аппроксимация" [М ] 0 множества М допустимых структур ). Затем следует сжатие М по функционалу

F = де / ^совместно с учетом ограничений ТЗ, что дает "аппроксимацию" [Мн ]0 множества оптимальных решений. Метод сжатия ССНФ, предложенный в работе и названный методом долускового отсеивания компонентов (ДОК), является обобщением "метода последовательного анализа и отсеивания вариантов без их пошагового конструирования" (В.С.Михалевич, В.Л.Волкович).

Последуюшеа уточнение решения оптимизационной задачи связано с развертыванием ОСНФ [ М * ]0 путем раскрытия скобок. В процессе развертывания может применяться метод ДОК, а также отсеивание частичных решений, не являющихся парето-оптимальными.

Окончательный результат развертывания - аппроксимация множества М* в явном виде - подвергается полной, проверке на соответствие ограничениям ТЗ по всем показателям. Для уменьшения

вычислительной сложности этого этапа предлагается метод сравнения вариантов ОН с варьируемыми параметрами.

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

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

Метод ДОК реализован в виде программы О РТ на ВС ЭВМ и на СМ ЭВМ и является составной частью ППП SY Ы V А R . Для оценки эффективности метода ДОК подучено отношение вычислительной сложности ¿?д,ок метода ДОК и метода ветвей и границ QBf

где В - коэффициент пропорциональности; со - степень сокращения перебора по методу ветвей и границ ( 4 i); tt - число переменных задачи; yw - глубина ОСНФ; <£ - доля неособенных переменных ( £ ^ I); ¿1 - 'I + -jf- I), причем ыи f те же, что и в формуле (9). Из формулы (14) следует, что эффективность метода ДОК растет: при увеличении размерности задачи П- ; пси уменьшении /и ; пта уменьшении £ , что подтверждается экспериментальными данными, полученными на ППП SYNVAR . Выигрыш от использования этого метода может составить несколько порядков

В глазе 7 приведены поимеры постановки и решения оптимизационных задач размещения баз данных и вычислительных работ по узлам сети, а также выбора технических средств СУ ГПС.

Для оценки технико-экономического уровня проектного решения предложена прогнозная модель развития мирового технико-экономического уровня объектов конкретного клесса. Эффект от использования логико-комбинаторного подхода связан с ростом вероятности <°/к достижения цели проектирования, определяющей возможность получения годовой экономии 9С за счет повышения

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

3. ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ'

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

Основные результаты по специальности 05.13.01 - Управление в технических системах:

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

2. Понятие особенных скобочных нормальных форм, символьные методы их построения, опенка сложности и принципы использования для моделирования множества вариантов структуры в задачах проектирования, развития и управления сложными объектами.

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

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

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

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

• Основные результаты по специальности 05.13.06 - Автоматизированные системы управления:

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

2. Принципы и методы представления MAB типовых и оригинальных структур программного и технического обеспечения АСУ с помощью контекстно-свободных плекс-грамматик.

3. Принципы и методы представления MAB структуры информационного, программного и технического обеспечений автоматизированных систем с помощью характеристических булевых функций, И-ИЛИ-деревьев и контурных И-ШМ-графов; преобразования указанных представлений в ОСИ; постановки и решения задач оптимизации состава и структуры информационного, программного и технического обеспечений автоматизированных систем на ОСНФ на ранних стадиях проектирования.

4. Принципы использования логико-комбинаторного подхода для построения методов решения функциональных задач структурного синтеза в АСУ и САПР.

5. Экспериментальная проверка и внедрение предложенных методов на ранних стадиях проектирования при разработке схем управления ЗУ, баз данных, программного обеспечения информационно-вычислительных систем, компонентов САПР и. АСУ ГПС.

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Анкудинов Г.И. Синтез структуры сложных объектов: логико-комбинаторный подход.- Л.: ЛГУ-, 1966,- 260 с.

2. Анкудинов Г.И. Об одном общем подходе к проблеме синтеза структуры информационной системы // Проблемы системотехники/ Материалы П Всесоюзного симп. Вып. I. Л., 1972, С. 23-26.

3. Анкудинов Г.И. Об одном обтем подходе к синтезу структуры алгоритмов, устройств и систем // Кибернетика, Киев, 1962, » I, С. 55-68.

4. Анкудинов Г.И., Победнов В.А. Логика развивающихся систем // Проблемы управления 83: Тез.докл. и сообв. IX Всесоюзного совещания, Ереван, 1983, С. 422-423.

5. Анкудинов Г.И., Сафонов А.Е. Морфологическое прогнозирование развития объектов техники // Методы поискового конструирования в системах автоматизированного проектирования: Межвуз. сб. / Под ред. А.М.Дворянкина,- Йошкар-Ола: МарГУ, 1986,

С. 28-36.

6. Анкудинов f.M. Применение формальных грамматик для син-теха структура сложных объектов // Ш Всесоюзная ивжвуз. научно-техн.конф. "Достиаения и перспективы развития технической ко-бернетики" / Тез.докл. В'ып. 2. Киев, 1975, С. 30-32.

7. Анкудинов Г.И. Построение множества альтернативных вариантов структуры проектируемого объекта // Проблемы системотехники / Материалы 1У Всесоюзного симпозиума по проблемам системотехники. Д.: Судостроение, 1980, С. 138-140.

8. Анкудинов Г.И. Вопросы теории плекс-яэыков П Кибернетика, Киев, 1978, № 3, С. 44-49.

9. Николаев В.И., Анкудинов Г.И. Определение и возможные применения контекстно-свободных плекс-языков // Автоматизирован-кыа снстены управления. Вып. 3,- Д.: ЛГУ, 1976, С. 3-7.

10. Анкудинов /.И. Об одном подхода к свертыванию частных критериев эффективности // Автоматизированные системы управления. I.: ЛГУ, 1974, Вып. I, С. 39-41.

.II. Анкудинов Г.И. Взвешенное среднее как форма целевой функции U Проблемы системотехники ! Материалы 1У Всесоюзного симп. по проблемам системотехники. Л.: Судостроение, 1980, С. 136-138.

12. Анкудинов Г.И., Арефьев И.В., Победнов В.А. О разработке адаптивной структуры реляционной базы данных интерактивной системы /V Интерактивные системы/ Тез.докл. и сообш. четвертой школы-сеыинара. Тбилиси, 1982, С. 51-53.

13. Николаев В.И., Анкудинов Г.И., Победнов В.А. Об оптимизации логической структуры басы данных // Структура информационного и математического обеспечения. Вып. 5,- Л.: ЛГУ, 1980, С.. 20-24.

14. Альтах И.Н., Анкудинов Г.И., Крайзнер Л.П. и др. Схемы управления запоминающих устройств // Запоминающие устройства. Л.: Знергия, 1968, С. 74-109.

15. Анкуд'шое Г.И., Крайздар Л.П. К вопросу о повшении быстродействия усилителей считывания // Запоминающие устройства. Вып. 3. Л. 5 Энергия, 1968, С. 120-128.

16. Анкудинов Г.И., Крайзмер Л.Я. Применение теории обнаружения сигналов для исследования и проектирования усилителей считывания // Хранение информации в кибернетических устройствах. Ы.: Сов.радио, 1969, С. I0I-I22.

17. Явчуновская Г.Б., Анкудинов Г.И. Как усваивается телевизионная лекция? // Вестник высшей школы, 1972, * 10, С. 39-42.

18. Анкудинов Г.И, Символьно-численные методы в задачах дискретного программирования с логическими ограничениями // Кибернетика, Киев, 1989, № 3, С. 51-55.

19. Анкудинов Г.И., йобеднов В.А. Сетевая модель системы управления ГПС / Сев.-Зап. заоч. политехи, ин-т.- Л., 1988.-б е.- Деп. 23.03.68, » 2280-В88.

20. Анкудинов Г.И., Победнов В.А. Распределенная обработка данных в системах управления ГПС / Сев.-Зап. заоч. политехи, ин-т.- Д., 1988.- 6 е.- Деп. 23.03.88, # 2280-В88.

21. Анкудинов Г.И., Сгрижаченко А.И. Оценка эффективности автоматизации структурного синтеза / Сев.-Зап. заоч. политехи, ин-т,- Л., 1988,- 10 е.- Деп. 27.06.88, » 5108-Б88.

22. Анкудинов Г.И., Стрижаченко А.И. Символьно-численные методы решения оптимизационных задач на И-ИЛИ-графах с контурами / Сев.-Зал. заоч. политехи, ин-т.- Л., 1988,- 9 е.- Дэп. 07.07.88, № 5479-В88.

Подп. к печ. 26.I0.fc9. Ы-г718о. Формат 60x84 1/16. Офсетная печать. Печ.л. 2,0; уч.-изд.л. 2,0. Тираж 100 зкз. Зак.^527. Ьесплатн

Зак.*527.

Бесплатно.

Ротапринт ЛЭТИ 197022, Ленинград, ул. Проф. Попова, 5