Интерпретационные методы в теории алгоритмических алгебр тема автореферата и диссертации по астрономии, 01.03.01 ВАК РФ
|
Суржко, Сергей Васильевич
АВТОР
|
||||
|
доктора физико-математических наук
УЧЕНАЯ СТЕПЕНЬ
|
||||
|
Киев
МЕСТО ЗАЩИТЫ
|
||||
|
1996
ГОД ЗАЩИТЫ
|
|
01.03.01
КОД ВАК РФ
|
||
|
|
||||
НАЦІОНАЛЬНА АКАДЕМІЯ НАУК УКРАЇНИ ІНСТИТУТ КІБЕРНЕТИКИ ІМ. В.М.ГЛУШКОВА
і ■ І Б 0 А . На правах рукопису
. : о :;ІВ .1396
СУРЖКО Сергій Васильович
ІНТЕРПРЕТАІДІЙНІ МЕТОДИ В ТЕОРІЇ АЛГОРИТМІЧНИХ
АЛІТ5БР
- '
Спсціапьність-<Н.05.01- - теоретичні основи інформатики га кібернетики (математична кібернетика)
. Автореферат
дисертації на здобуття наукового ступеня доктора фізико-математичних наук
Київ-1996
Робота виконана в Інституті кібернетики ім.В.М.Глушкова Н АН України . .
Науковий консультант: член-кореспондент НАН України, професор Ющенко Катерина Логвшіівна
Офіційні опоненти: '
1. Член-кореспондент НАН
України, професор Летічевський Олександр Адольфович
2. Доктор фізико-математичних
наук Вальковськпй Володимир Олександрович ,
3. Доктор фізико-математичних наук,
професор Лісовик Леонід Петрович
Провідна організація: Інститут прикладної інформатики Київської держадміністрації та НАН України (м.Київ)
Захист відбудеться 23 лютого 1996 р. об 11 год. на засіданні спеціалізованої ради Д 01.39.02 в Інституті кібернетики ім.В.М.Глушкова НАН України за адресою: 252207, Київ 207,
пр. академіка Глушкова, 40.
З дисертацією можна ознайомитись в бібліотеці інституту Автореферат розіслано 199* г.
Вчений секретар спеціалізованої ради СииявськийВ.Ф.
ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ
Актуальність теми. Теорія алгоритмічних алгебр займає важливе місце в математичній теорії обчислень та теоретичному програмуванні. Сфера застосувань цієї теорії охоплює паралельну обробку даних, проектування обчислювальних систем, проектування та синтез схем програм, аналіз та оптимізацію схем програм, структури даних, спеціалізовані системи автоматизованого проектування, форми представлення знань, моделювання технологічних процесів, а також ряд інших проблем як загального, так і спеціального змісту.
Основи даної теорії було закладено В.М.Глушковим і розвинено ного соратниками, учнями та послідовниками, якими були отримані такі важливі результати, як умови розв'язності проблеми еквівалентності автоматів відносно напівгрупп та вивчення зв'язку алгоритмічних алгебр з теорією схем програм (О.А.Летічевськнй); розв’язність алгоритмічної проблеми тотожності слів та існування повної системи аксіом для алгебр с замкненими умовами та дослідження алгебр структур даних (Г.Е.Цейтлін); розв'язність проблемі» тотожності слів та ісг аання повної снсіемн аксіом для 5(Н)-алгебр - спеціального класу алгебр недетермінованих алгоритмів (Ю.А.Ющенко), розв’язано цілий ряд інших задач. Серед робіт близького напрямку слід особливо відзначити результати Л.П.Лісовика з теорії перетворювачів (зокрема, Я- та ПЛ-перетворювачів), в рамках якої розв'язаний ряд важливих алгоритмічних проблем.
Однією з основних задач, з необхідністю розв'язку яких зв'язане виникнення алгоритмічних алгебр, є задача еквівалентних перетворень мікропрограм (регулярних схем), яка в багатьох випадках до цього часу не знайшла остаточного рішення. Тому актуальним є дослідження алгоритмічних проблем тотож-
пості для тих чи інших класів алгебр алгоритмів і особливо вільних алгебр.
Теорема В.М.Глушкова про представлення дискретних перетворювачів регулярними схемами вказує на можливість (і спосіб) формального опису обчислень, що задані обчислювальним пристроєм (дискретним перетворювачем), в алгебраїчних термінах. Разом з тим, зворотне твердження для даного класу перетворювачів не мас місця. Тому актуальними с задачі побудови та дослідження інших класів дискретних перегво-рювачів, особливо таких, для яких дана теорема допускає зворотнє твердження. З цією проблематикою зв'язана важлива проблема організації послідовних та паралельних обчислень, заданих регулярними схемами операторів з притаманними ним тими чи іншими корисними у практичному відношенні властивостями. Дослідження даної проблеми не може бути виконане без виходу за іраниці теорії алгоритмічних алгебр і потребує розробки та застосування спеціального апарату, ^
Рішення цих та багатьох інших актуальних задач вкрай ускладнене основним об’єктом - алгеброю алгоритмів, сигнатура якої включає до десяти специфічних операцій і яка далеко не .завжди дозволяє застосувати для свого дослідження добре розвинений апарат або безпосередньо використати результати загальнотеоретичного характеру. Тому проблема розробки як спеціальних методів дослідження алгоритмічних алгебр, так і таких методів, що дозволяють ефективно використати результати відомих математичних теорій, є вкрай актуальною. Саме до них відносяться интерпретаційні методи, тобто такі, в яких досліджуваний об'єкт замінюється (інтерпретується) в певному сенсі ізоморфним або еквівалентним «ому формальним об'єкТОМ ІНШОГО* КЛГіСу ІЗ ПЛиСТїшОСТЯМи, ЩО ДОГшОЛНЮіЬ ДОСІЙШЬО
ефективно виконати дослідження і перенести одержані результати на вихідний об'єкт.
Об'єктом дослідження в дисертації с алгебри (детермінованих та недетерміноианих) алгоритмів та пов'язані з ними об'єкти.
Метою дисертаційної роботи є розробка та застосування інтерпретаційних методів дослідження алгоритмічних алгебр.
, Для досягнення мети дослідження в дисертації поставлені и розв'язані наступні задачі:
- розроблено метод редукції алгебр детермінованих та недегермінованих алгоритмів до единого, простішого об'єкта -алгебри П-алгоритмів;
- введене и досліджене поняття П-мовн, узагальнююче формальну мову, розроблено метод дослідження функціонально еквівалентних П-мов шляхом їх зведення до так званих точних О-мов;
, - введені поняття та розроблено метод дослідження вільних алгебр П-алгоритмів, детермінованих та недетерміновашіх алгоритмів, що базується на точних П-мовзх;
- розроблено загальний метод дослідження спеціального класу Гі-мов - формальних мов над алфавітом, що інтерпретований в бульовій алгебрі;
- розроблено метод дослідження регулярних мов над алфавітом, інтерпретованим в бульовін алгебрі, в тому числі алгоритм перевірки еквівалентності таких мов;
- розроблено метод класифікації лов над алфавітом, інтерпретованим в бульовій алгебрі;
- розроблено апарат динамічних сітьових моделей спеціального вигляду (генераторів дискретних процесів, ГДГІ) і, на
його основі, - метод моделювання регулярних Схем операторів алгоритмічних алгебр у вигляді ГДІ1;
- розроблені методи формального опису дискретних перетворювачів в термінах регулярних схем (з настройкою) операторів алгоритмічних алгебр;
- розроблено метод дослідження випадкових обчислювальних процесів, заданих однорідними ланцюгами Маркова із скінченною кількістю станів, інтерпретованих як елементи марковської алгоритмічної алгебри - стохасгнчного аналога алгебри алгоритмів.
Методика досліджень. В роботі використовується загальна теорія універсальних алгебр, теорія напівтруп, решіток, бульоїшх алгебр, теорія формальних мов і грам абстрактних автоматів, а також теорія випадкових процесі і* (однорідні ланцюги Маркова із скінченною кількістю станів).
Наукова новизна одержаних результатів полягає в наступному. ■ .
1. Показано, що властивості будь-якої алгебри детермінованих або недетермінованих алгоритмів визначаються властивостями суїтсво простішого об'єкта - алгебри ії-алгоритмів, введеної в роботі, що однозначно задасться по вихідній алгоритмічній алгебрі. Будь-яку алгебру (детермінованих або неде-термінованих) алгоритмів можна побудувати по деякій алгебрі □-алгоритмів за допомогою стандартної та конструктивної процедури.
2. Введені і досліджені поняття £ї-мови та точної £ї-мовп, а па ціп основі - вільні алгебри Сї-алгоритмів, детермінованих та недетермінованих алгоритмів. Частковим випадком чільної
. алгебри П-алгоритмів є алгебра регулярних виразів (алгебра Кпіні). Встановлено властивості (точних) О-мов, заданих регу-
лярними схемами вільних алгебр детермінованих та недетермі-новатіх алгоритмів.
3. Введено і досліджено клас формальних мов, побудованих над алфавітом, частина символів якого інтерпретована в бульовій алгебрі. Виявлено можливість класифікації таких мов по аналогії із класифікацією за Хомським.
4. Виявлено зв'язок раціональних (регулярних) мов над , алфавітом, інтерпретованим в бульовій алгебрі, із скінченними
автоматами. Отримане узагальнення на даний випадок теореми Кліні про представлення раціональних мов автоматами. Доведено розв'язність алгоритмічної проблеми тотожності для регу-лярннх мов над алфавітом, інтерпретованим в бульовій алгебрі.
5. Доведено розв'язність алгоритмічної проблеми тотожно-сгі регулярних схем (операторів та умов) вільних алгебр недетер-мінованих алгоритмів.
6. Побудовано апарат динамічних сітьових моделей (ГДП), що охоплює сітки Петрі та їх модифікації, а також скінченні дискретні перетворювачі інформації. Досліджено напів-групові властивості вільної мови, породжуваної ГДП, встановлено зв'язок з частково комутативними моноїдами та мовами слідів.
7. Виявлено можливість представлення регулярної схеми оператора алг оритмічної алгебри у вигляді динамічної сітьової
. моделі (ГДП), яка обчислює тон же оператор. На основі даного представлення отримано можливість организації обчислень, стійких до "збоїв" гипотетичної машина.
8. Побудовано і досліджено стохастичний аналог алгоритмічної алгебри - марковська алгоритмічна алгебра.
Практична цінність та реалізація роботи. У роботі побудовано метод, що дозволяє реалізувати алгебри детермінованих
і недетермінованих алгоритмів', сигнатура яких містить відповідно сімь та вісім (не рахуючи нульариих) операцій, засобами суттєво простішої алгебри її-алгоритмів із чотирма операціями. Даний підхід спрощує розробку програмних засобів, орієнтованих на представлення алгоритмів і програм у вигляді регулярних схем алгоритмічних алгебр.
Розроблення в дисертації метод моделювання регулярних схем операторів алгоритмічних алгебр у вигляді ГДП дозволяє організувати обчислювальний процес, який є стійким до збоїв обчислювального пристрою. ' .
Апарат марковських алгоритмічних алгебр дозволяє ефективно розв'язувати ряд практичних задач ймовірнішого характера, що відносяться до програмних обчислень, зокрема ймовірнісний аналог задачі тестування пробам.
Апарат генераторів дискретних процесів дозволяє здійснити програмне моделювання і аналіз система управління промисловим підприємством. Розв'язано також практичну задачу декомпозиції інформаційного фонду промислового підприємства на бази даних. "
На. основі отриманих результатів при безпосередній участі автора було розроблено програмні засоби -моделювання і аналізу інтегрованої системи управління дискретним виробництвом ПАРИС та АВАНС, а також пакет прикладних програм "Декомпозиція інформаційної бази" (Галузевий фонд алгоритмів і програм АСУ Мінприладу СРСР, інв.№ 1030, Калінін, Ценгрпрограмсистем, 1983), що реалізує описаний в дисертації метод декомпозиції'інформаційного фонду на бази даних. „
Системи ПАРИС та АВАНС було апробовано па реальних даних, що відносяться до трьох підсистем інтегрованої АСУ
НВО "Еіекгрон" (системі! автоматизованого проектування виробів, системи оперативно-виробничого планування, автоматизованої системи оперативно-диспетчерського управління). Результат» • моделювання були оброблені, а на їх основі розроблено конкретні рекомендації для підвищення ефехтив-иосгі системи управління Львівського науково-виробничого 'об'єднання"Електрон". - ' ■
Розробка та апробація сказаних програмних засобів проводилась в рамках наступних дослідно-конструкторських та наукоио-дослідницьких робіт: ДКР "Розробка загальноснс-тємних іт! функціональних засобів, автоматизації управління виробничим об'єднанням" (шифр "Меркурій 2.2", номер державної реєстрації У45449 під 04.05.87 р.), проведеної на підставі наказів Міністерства промисловості засобів зв’язку СРСР 547 дек від І6.І2.85 р. та 96 дек бід 21.03.86 р.; НДР "Розробка принципів побудови типових інструментальних та функціональних засобів інтегрованих АСУ підприємством (об'єднанням)" (шифр “Старт", номер держапної реєстрації У48996 віл 06,05.88 р.), проведеної на підставі Постанови Державної Комісії Ради Міністрів СРСР-'Ф 47 від 11.02.88 р. та наказу Міністерства промисловості засобів зв'язку СРСР № <51 від 19.02.38 р.; НДР "Проведення наукових досліджень з напрямку розвнтху робіт в області АСУ підприємством, об'єднанням, створення науково-технічного доробку по розробці тсхніко-скономічних рішень для підвищення рівня інтеграції'та ефективності даних’ г 'стем у , ХШ-и п’ятирічці" (шифр "Розвиток”, номер державної реєстрації У56580 від 15.03.89 р.), проведеної у відповідності з рішенням Державної Комісії Ради Міністрів СРСР Л*? 47 під 11.02.58 р. та наказом Міністерстяа промисловості засобів зв'язку СРСР Лч 61 від 19.02.88 р.; при виконанні технічного завдання з науково-
їй
технічної програми ДКНТ СРСР 0.80.02, завдання 35.01.06Д "Розробити методологічні то інструментальні 'засоби для автоматизованого проектування складних багаторівневих та великомасштабних систем". Система ПАРНО (версія 1.1) відзначена срібного медаллю ВДНГ СРСР. -
На захист виносяться наступні наукові результати, то одержані особисто автором: 1) поняття і властивості алгебр !П-алгорнтмів та метод зведення алгебр детермінованих і не-деісрмінованих алгоритмів до алгебри П-алгоритмі»; 2) поняття і властивості П-мов і точних П-мов, а також введені та досліджені на їх основі поняття влышх алгебр ^-алгоритмів, детермінованих та недегерміноііаннх алгоритмів; 3) загальний метод дослідження спеціального класу П-.мои - формальних мов над алфавітом, інтерпретованим ^ бульовій алгебрі; *1) метод дослідження регулярних мов нал. алфавітом, інтерпретованим в бульовій алгебрі, в тому ч::сл! алгоритм її ревіркн на еквівалентність таких мов і розв’язок поставлених алгоритмічних проблем; 5).теорема лрі' розв'язність проблеми тотожності для вільних алгебр недстсрміїшванпх ішгорнгмі»: 6) ме-тод'ютс;тфіі;ації моь над алфавітом, інтерпретованим в бульо-бііі алгебрі; 7) апарат динамічних сітьових моделей спеціального вигляду (ГДП), властивості ГДП, метод дослідження регулярних схем операторів алгоритмічних алгебр за допомогою ГДП; 8) методи формального опису Дискретних перетворювачів в термінах регулярних схем (з настройкою) операторів алгоритмічних алгебр; 9) поняття марковськоі алгоритмічної алгебри і, на його основі, метод опису та дослідження випадкових обчислювальних процесів, заданих однорідними ланцюгами ’ '.аркова із скінченною кількістю станів. .
Апробація роботи. Основні результати роботи доповідались і обговорювались на Першому Всесвітньому конгресі Товариства математичної статистики та теорії ймовірностей ім.Бернулі (Ташкент, 1986), XIX Всесоюзній алгебраїчній конференції (Львів, 1987), ХШ Всесоюзному семішарі "Паралельне програмування і високопродуктивні структури" (Алушта, 1988), Всесоюзному семинарі "Методи та інструментальні засоби генерації програм" (Гілзнерське, 1989), X Всесоюзному семінарі "Паралельне програмування і високопродуктивні системи: методи представлення знань в інформаційних технологіях" (Уфа, 1990), Всесоюзній школі-семинарі "Багаторівневе структурне проектування програмних, систем" (Планерське, 1991), V, VI и VII Всесоюзній школі-семішарі "Розпаралелювання обробки інформації" (Львів, 1985, 1987, 3989), Міжнародній науково-технічній конференції Палацу радянської науки та культури/ (Болгарія, Софія, 1989), Всесоюзному семішарі "Синтез структур автоматизованого управління у великомасштабних системах (Херсон, 1989), V Всесоюзному семішарі "Методи синтезу і планування розвитку сіруктур великомасштабних систем" (Звенігород, 1990), II Українській конфереішії з автоматичного керування "Автоматика-95" (Львів, 1995), Всесоюзній науковій конференції "Комп'ютеризація інформаційних процесів в управлінні народним господарством" (Москва, 1988), Всесоюзній науковій конференції "Аналіз ефектишгосгі і якості проектування та функціонування АСУ в ('^родному господарстві" (Москва, 1983), І Всесоюзній науково-технічній конференції "Практичне застосування сучасних технологій програмування, пакетів прикладних програм а обчислювальних системах та мережах ЕОМ" (Дніпропетровськ, 1988). II Всесоюзній конференції "Автоматизовані системи обробки
зображень" (Львів, 1986), У Всесоюзній конференції "Розподілені інформації!но-керуючі системи1' (Саратов, 1988), ІУ Всесоюзному науковому семінарі "Методи синтезу та планування розвитку структур складних систем" (Ташкент, 1987), школах-снмпозіумах з системології та міждисциплінарних досліджень СМД-84, СМД-86, СМД-87, СМД-88 (Ворохта, 1984, 1986, 1987, 1988).
Публікації. За темою дисертації опубліковано понад 40 праць, в тому числі два учбових посібника, ряд статен в центральних виданнях за переліком ВДК, тези та доповіді на різних міжнародних та республіканських конференціях.
Структура і об'єм роботи. Дисертація складається зі вступу, чотирьох глав, які містять двадцять чотири розділи, висновків, списка літератури із 128 найменувань та додатку. Основний текст дисертації займає 192 сторінки. Робота містить 8 малюнків.
ОСНОВНИЙ"ЗМІСТ РОБОТИ
У вступі обгрунтовано актуальність теми, викладені питання, дослідженню яких присвячена дисертаційна-робота і які виносяться на захист, формулюється об'єкт та мета дослідження, розкривається зміст роботи.. •
Основний зміст першої глппн полягає у викладенні метода "... ' ' ' редукції алгебр (детермінованих і недетермінованих) алгорит-
діів до алгебри ft-алгоритмів. Наведені визначення основних об'єктів, що розглвдаються у роботі, вводиться та досліджується алгебра ft-алгоритмі в, встановлюється зв'язок цього поняття з алгебрами детермінованих і недетермінованих алгог ритмів. Вводяться та досліджуються поняття ft-мови і точної
О-мови, а на їх основі вводяться та досліджуються вільні алгебри £}-алгоритмів, детермінованих і недетермінованнх алгоритмів.
Нехай X - непуста (информаційиа) множина; Ио - скінченна множина попарно відмінних часткових точково-множинних (недетермінованнх) операторів, визначених в X; Хі, Хз, ..., Хь - неперетинаючися множини, що утворюють розбиття X; ді* цг, - такі оператори (диз'юнкти), які
утворюють множину Оо, що область визначення © співпадає з Хі, і оператор © тотожній у своїй області визначення. Алгеброю ІІ-алгоритмів називаємо універсальну алгебру Ф - (Р; Ро, во; X) сигнатури 12 ={, + ,*, с, 0, 1), породжену множиною РоиОо . Сигнатура С2 містить операції множення (композиції), суми (недетермінованої диз’юнкції) та ітерації, що природнім чином визначаються для точково-множинних операторів, а також / унарну операцію о (характеристику) і нульарні операції 0 та І. \ Операція характеристики визначається так: якщо (- частковий недетермінованкй оператор, визначений в X, то о(І) є звуженням тотожнього оператора на область визначення 1'. Основна мі. жнна Р алгебри Ф ‘'кладаеться з точково-множинних (недетермінованнх) операторів, які задачі термами відповідної алгебри термів сігнатури О, званих ^-схемами даних операторів.
. По алгебрі Ф.будуються алгебри Яеі,Ф і ЯеаФ, однотипні
відповідно алгебрам детермінованих і недегерміновичих алгоритмів і породжувані скінченною множиною вигляду РосТ, де сукупність Т с а(Р)ха(Р) с різною для ЯепФ та ІІ&іФ. Алгебри ЯеаФ і ІІе.іФ називаються відповідно недетермінованим та детермінованим редуктом алгебри Ф. Алгебра П-алгоритмів може бути побудована за допомогою представленої в роботі
процедури по алгебрі 91 (детермінованих або недетермінованих) алгоритмів. Отриману таким чином алгебру ^-алгоритмів позначаємо Ех Ф(Уї) і називаємо екстенсіоналом алгебри ЗІ.
Теорема 1.1. Будь-яка алгебра Н недетермінованих алгоритмів с ізоморфною деякому недетермінованому редукту екс-тенсіонала Ех ФОЛ!) цієї алгебри, 'Л * Ren Ех Ф(91). Навпаки, кожний недегермінованші редукт будь-якої алгебри Q-алгорит-мів Ф ізоморфний деякій • алгебрі 91 недетермінованих алгоритмів. _
Теорема 1.2. Будь-яка алгебра детермінованих алгоритмів є ізоморфною деякому детермінованому редукту її екстенсіонала Ех Ф(91), 91 * Rej Ех Ф('Л). Навпаки, Кожний детермінований редукт будь-якої алгебри (2-алгоритмів Ф ізоморфний деякій алгебрі 9ї детермінованих алгоритмів.
Значення цих теорем полягає в тому, що вивчення властивостей будь-якої алгебри алгоритмів (детермінованих чи неде-термінованих) зводиться додослідження алгебри ft-алгоритмів, сигнатура якої, значно простіша від сигнатури будь-якої з цих двох алгебр. Поняття алгебри ії-алгоритмів суттєво ширше від поняття алгоритмічної алгебри: існують оператори, які не можуть бути задані в алгебрах детермінованих або недетер-мінованих алгоритмів, але містяться в алгебрі fl-алгорнтмів, яка еїх екстенсіоналом.
Нехай А, В - скінченні непусті неперетинаючися алфавіти, W- сукупність термів сигнатури {, а, 0, 1}, побудованих над змінними з АиВ (ft-слів), WA - сукупність непустих підмножин з W, званих Ф-мовами над алфавітом АиВ. На W.' внзна-чаються операції сигнатури Q, що перетворюють цю множину в '-у;версальну алгебру.
Нехай 3 - таке відображення множшш АиВ на множину РоиСо елементарних операторів (Єо - диз'юнкті!), ЩО І(А) - 1то, НВ) = йо. Гомоморфізм і П-алгебри \УЛ на алгебру Ф П-алго-рнтмів, породжену множиною РоиОо , що продовжує відобра-жешіп Л, називається інтерпретацією \УЛ (в класі иедетермі-нованих операторів).
П-мови Ьі, Ьг є \УЛ називаються функціонально еквівалентними, якщо для любої інтерпретації І виконується рівність І(Ьі) = І(Ьг).
Нехай В = {Ьі, Ьг, ... , Ьп). На П-словах задаються тотожності наступного вигляду: а(ааф)у) = ст(ар)о(ау);
о(а)ст(Р) = аф)а(а); сг(Ь)а = а; ст(0) = 0, о(1) = 1; сг(Ьі) = Ьі, і = І,2,п; Ь,Ьі = 0 при і*у, у = І, 2,..., п; Ьіи Ьги... и Ьп = І; аі = Іа = ге, а0 = 0а = 0
11а основі даних тотожностей в визначається частковий порядок. Вводиться поняття точної П-мови, що складається з П-слів спеціального вигляду. Кожній П-мові Ь є \УА однозначним чином співставляється точна П-мова ?(Ь). Точні П-мови няц алфавітом АиВ утворюють П*алгебруЛ.
Теорема 1.3. П-мови Ц, Ьг є WЛ функціонально еквівалентні тоді і тільки тоді, коли точні П-мови в(Ьі) і і Іл) співпадають.
Нехай 3 - визначене вище відображення АиВ на РоиОо, Ф[А, В] - абсолютно вільна алгебра П-схем, що породжена множиною АиВ. Сюр'єктнвнші гомоморфізм І: Ф[А, В]-» Ф , що продовжує і, називаємо інтерпретацією Ф[А, В] (в класі недетермінованнх операторів).
На Ф[А, В] визначається конгруенція т : (Яі.Я:) є т , якщо І(Лі) = І(Яг) для будь-якої інтерпретації І алгебри Ф[А, В]. Кожній П-схемі Я є Ф{А, В] однозначним чином спів* ставляється деяка Гї-мова ЦЯ).
Теорема 1.4. Нехай Яі, Яг є Ф[А, В]. Включення (Яі, Яг) е і виконується тоді і тільки тоді, коли П-мови ЦЯ і), ЦЯз) функціонально еквівалентні.
Теорема 1.5. Існує гомоморфізм і алгебри Ф[А, В]/т в Й-алгебру Л точний П-мов, який є продовженням тотоаснього на множині АиВ відображення.
Існує гомоморфізм Ь: Ф[А, В}-> Л , який задасться формулою И(Я) = $(ЦЯ)), і фактор-алгебри Ф{А, В]/Кег її , Ф[А, В]/т ізоморфні. П-алгебра Ф[А, В]/Ке5 Ь = г(А, В) називається вільною алгеброю П-алгоритмів над алфавітом АиВ.
Теорема 1.6. Будь-яка алгебра П-алгоритмів г гомоморф-ним образом деякої П-алгебрн Ъ(А, В).
Нехай С - скінченний алфавіт, К(С) • алгебра термів сигнатури { , +, *, 0, 1) над алфавітом С (регулярні вирази), у -конгруенція на К(С): (Яі, Я:) є у, якщо ЦЯі) - ЦЯг). Під . алгеброю Кліні (алгеброю регулярних виразів) над алфавітом С, як правило, розуміють фактор-алгебру К.(С)/у. .
_ . _ _ Теорема 1.7. Нехай Яі, Яг є К (А). Включення (Яі, Яг) є у виконується тоді і тільки тоді, коли (Яі, Яг) є Кег Ь.
Теорема І.гі. Регулярні вирази Яі ,Яг є К(А) у-еквівалентні тоді і тільки тоді, коли для будь-якої інтерпретації І:Ф[А, В]-> Ф
— оператори І(Яі), І(Яг) співпадають. ■
На основі конструкцій детермінованого і недетермінова-ного редуктів по алгебрі Z(A, В) визначаються двохосновні алгебри 'J?zd = Red Z та 91zn = Ren Z, які називаються відповідно вільною алгеброю детермінованих та вільною алгеброю не-детермінованих алгоритмів. Поняття інтерпретації очевидним чином переноситься і на ці алгебри.
Теорема (1.9, 1.11). Будь-яка алгебра детермінованих (недетерміноваиих) алгоритмів є гомоморфним образом деякої вільної алгебри детермінованих (недетерміноваиих) алгоритмів.
Теорема (1.10, 1.12). Нехай 91 - вільна алгебра детермінованих (недетерміноваиих) алгоритмів, а, р є 91. Тотожність а = р справедлива тоді і тільки тоді, коли оператори (умови) 1(a), !(р) співпадають при будь-якій інтерпретації І алгебри 91.
Нехай р - звуження ядерної конгруенції Кег h на К(АиВ).
Лема 1.10. Основна множина вільної алгебри недетермі-новашіх алгоритмів, породженої множиною АиВ, міститься в К(АиВ)/р.
В другій главі досліджуються мови над алфавітом АиВ, де елементи з В відповідають елементам бульової алгебри, яка далі позначається тим же символом В. До таких мов відносяться точні П-мови, що задаються О-схемами вільної алгебри недетерміноваиих алгоритмів.
Нехай W=(Au(B\{0,i})*, P('W’) - сукупність мі і з W, побудованих над скінченними підалфавітами алфавіту -Аи(В\ {(),!}). Якщо L є P(W) і А’ (відповідно В) - такий скінченний піднлфавіт алфавіту А (відповідно В), що хоча б одне слово з L містить деякий символ з А’ (з В), а кожний символ з А1
(з BO має входження хоча б в одне слово з L, то пишемо A(L)=A\ B(L)=B'.
P(W) перетворюється в алгебраїчну систему сигнатури (ПцД), де fio = {+, *, 0, 1}, а ПР складається з єдиного
бінарного відношення - часткового порядку, індукованого з В та узгодженого з операціями. З В индукуються властивості операцій додавання і множення, що приводить до фактор-сйстеми U = P(S)/p , де р - деяка однозначно визначена по В конгруенція. Відносно операції додавання (порядку) U є верхньою напіврешіткою. Конгруенцію р можна розглядати як ядерну конгруенцію Ker h, де h: P(W) -> U - сильний сюр’єк-тившій гомоморфізм. :
Нехай S - множина слів вигляду '
w = аіаіа2а2...апапссп+ім> (*)
де аіаг...ап є А*, оіа2...апап+і є (В\{0))*, доповнена нулем. В S визначається множення (индуковане і В), іцо перетворює S в моноїд. Через P(S) позначасться сукупність непорожніх під-миожин з S, побудованих над скінченними нідалфавітами алфавіту Аи(В\{0}). P(S) перетворюється в алгебраїчну систему сигдатури (По А>). Існує сильний гомоморфізм z P(\V) на P(S).
Нехай Е - сукупність всіх скінченних розбиттів одиниці бульової алгебра В, D(e) - перетин S та (A u є)*, де е є Е, PD(e) -сукупність непорожніх підмножин з D(e).
Теореиа 2Д. Для будь-яких 'е є Е, Lj, L2 є PD(e) нерівність h(Li) £ h(L2> вшсонується тоді і тільки тоді, коли Li с L2.
, ’
Теорема 2.2. І. Для будь-яких*'е є Е, К. є U множина PD(e)nK містить не більше одного елемента.
2. Для будь-якого класу К є U існує таке розбиття одиниці е є Е І що PD(e)nK* 0.
Отже, визначено оператор 6: UxE -» P(S), який парі (К, е) співсгавяяє (можливо, порожню) мову 8(К., е) є PD(e)nK,
Теорема 2.3. І. Нехай Кі, Кі є U. Якщо 5(Кі,е) = 8(К:,е) = = L, L*0 хоча6 для одного е є Е ,то Кі = Кг = [LJ.
2. Для будь-якого К е U знайдеться таке розбиття одиниці е є Е, що 8(К.,е) = L * 0. При цьому К = [LJ і L • єдина мова з PD(e), для якої справедлива дана рівність.
Скажемо, що скінченна підмножина В' бульової алгебри В посідає властивість (А), якщо для будь-яких а, Р є В існують алгоритми обчислення а + р, ар, а . Дана властивість передбачає ефектівність опису елементів з В'.
Через 'Л = (С, Q, f, qo, Т) позначається автомат із вхідним клфавітом С, множиною станів Q, функцією переходів f, початковим станом qo та множиною заключних станів Т.
Якщо L є P(W) - регулярна мова, то вона может бути задана деяким регулярним виразом Rw. Тоді z(L) с S задасться в S регулярним виразом Rs. Якщо L с S і L регулярна в P(W), то ця мова задається регулярним виразом Rsw.
Теорема 2.5. 1. Мова L е P(S) регулярна в W тоді і тільки тоді, коли вона єрегулярною підмножиною моноїда S.
2. Нехай мова L є P(W) регулярна і задана виразом Rw (аГ;.; скінченним автоматом)! Тоді мова z(L) є P(S) теж регулярна в W. Якщо множина B(L) посідає властивість (А), то існує алгоритм побудови регулярного виразу Rsv>’ (відповідно скінченного автомату), який задас мову z(L), по виразу Rw (по відповідному автомату).
Розглядаються автомати спеціального вигляду - автомати з чергуванням ;шфавіту. Отримано таке узагальнення теореми Кліпі.
■ І
Теорема 2.6. Непорожня множина Ь с 5 е регулярною підмнбжнною моноїда Б тоді і тільки тоді, коли мова Ь розпізнається автоматом із чергуванням алфавіту.
Клас еквівалентності ІС є І) називається Іі-регулярним, якщо в ньому міститься хо^а б одна регулярна мова.
Теорема 2.7. Нехай клас К є и Ь-регулярннй. Тоді регулярна кожна з мов 8(К, е), де е є Е. Якщо 8(К, є) = Ь * 0, то Ь -
едина мова з РО(е), для котрої К = [І.].
Теорема 2.8. Нехай Ьі, Ьг • регулярні в № мови, задані регулярними виразами Кі, ІЬ відповідно і множина В(Ьі)иВ(Ьг) посідає властивість (А). Існує алгоритм перевірки справедливості рівності (Ьі] = (Ь:).
Сіверджуггься можливість класифікації елементів и по аналогії із класифікацією Хомського формальних мов. Підставою для цього є формульована нижче теорема.
Нехай Лі - клас мов, породжених граматиками типу і , і = 0, І, 2, 5 (Ло - клас рекурсивно перечислюаальних мов і тої.). Для мови Ь покладемо і(Ц - п\ах{і: Ь є Лі). -
Теорема 2.9. Нехай К е и, г(К) = {Ь: Ь = 6(К, е) * 0,
е є Е}. Тоді і(Ьі) = і(Ьі) для будь-яких Ьі, и є г(К).
Теорема 2.10, Існує алгоритм, що дозволяє для будь-яких схем Лі, 1*2 є К(АиВ) встановити справедливість рівності Ма.) = Ь(К2).
Теорема 2.11. Проблема тотожності для вільної алгебри недетерміноващіх алгоритмів є розв'язною.
У третій глапі будується та застосовується до дослідження алгоритмічних алгебр апарат динамічних сітьових моделей спеціального вигляду - генераторів дискретних процесів.
Генератор дискретних процесів (ГДП) визначається як деяка статична структура (схема ГДП), доповнена правилами функціонування. Схема ГДП описується двудольннм орієнто-ваинм графом і зв'язує скінченну сукупність змінних, що прий-
і
мають значення в заданих множинах, із сукупністю функціональних символів, ототожнювати з елементарними операторами (ЕО). ЕО визначається на деяких змінних, які називаються входами ЕО, і задає значення вихідних змінних (виходів). Процес обчислення виходів ЕО по заданих значеннях входів називається спрацьовуванням ЕО. Спрацьовування ЕО виконуються миттєво, недетерміновяннм чином і послідовно при обмеженнях: І) наступний в утворюваній послідовності спрацювавших операторів може спрацювати лише після завершення робот» попереднього; 2) повторне спрацьовування деякого ЕО можливе лише після "перерахування" хоча би одного його входа післе попереднього спрацьовування.
Серед змінних ГДП виділяються дві иідмножішн, одна з яких містить так звані інформаційні, а друга • керуючі зміні. Пара (Бо, 8і) непорожніх підмножин інформаційних змінних називається настройкою ГДП, Процес роботи ГДП ДБо, Зі) з даною настройкою полягає в послідовному спрацьовуванні ЕО, заданих на деякому початковому стані, що фіксує початкові значення змінних ГДП. Робота ГДП завершується, якщо ні один з ЕО не може спрацювати або ж досягаються стани із заданої множини заключних станів. '
Послідовності спрацьовувань ЕО ГДП Г можуть розглядатися як сліОіа деякої "Мови ЦГ) (вільної мови ГДП Г). побудованої над алфавітом функціональних символів. Слова з ЦГ) називаються допустимими процесами. Будь-який допустимий процес і визначає деякий частковий оператор (, що відносить
кожному початковому стану ГДП деякий заключний стан або опср;пор не визначений в цьому стані. В процесі роботи ГДП Г(&>, 8і) обчислює деякий частковий оператор, який являє собою вектор-функцію, то визначена на векторі змінних з Бо і задає значення вектора змінних з Бі. ,
Клас ГДП охо!ілюс сітки Петрі: по заданій сітці можна побудувати ГДП, функціонування якого точно відповідає функціонуванню даної сітки Петрі, біжучі розмітки якої співпадають з біжучимн станами ГДП, а вільна мова сітки співпадає з вільною мовою ГДГ1.
Головним обмеженням на функціонування ГДП є умова "перераховування" значені, вхідних змінних ЕО. Це обмеження можна зняти шляхом спеціального підбору керуючих змінних (теорема 3.1). .
Теорема 3,2. Нехай елементарні оператори ГДП Г визначені всюду на входах. Тоді мова ЦГ) с регулярною.
Розглянемо ГДГ1 Г із множиною А функціональних символів. Задамо бінарне відношення р , покладаючи (а, Ь) є р , якщо а * Ь і перегини входів а (входів Ь) з виходами Ь (виходами а) та виходів а з виходами Ь порожні. Відношення р с відношенням комутативності іій А і тому однозначно визначений пастково комутативний мопоїд М(Г). Через И позначимо канонічний гомоморфізм А* я М(0- V
Теорема 3.3.1) Мова ЦГ) є насиченою; 2) якшо і є М(Г), то всі слова, які містяться в Ь10) , с одночасно допустимими або одночасно недопустимими процесами; 3) якщо І е М(Г) і
XI, ТІ Є Ь'*(ї) . ТО ц = ц . • , і
Оскільки мова ЦГ) насичена, то на ній можна побудушнн деяку фактор-множину Л(Г), що складається із сліди* М(Г). Мова слідів Л(Г) характеризуй' Г як "паралельний” обчислю-’
вач, в якому допускається паралельна реалізація БО, що відповідають комутуючим функціональним символам.
Теорема 3.4. Якщо всі ЕО ГДП Г визначені всюду на входах,-то мова слідів Л(Г) є розпізнаваємою.
Показується, що на ЦГ) може бути введена така нетривіальна бінарна операція, яка перетворює ЦГ) в моноїд, що є гомоморфним образом вільного моноїда А*.
Розглядається багаторівневе представлення ГДП Г у вигляді скінченної впорядкованої послідовності більш простих і пов'язаних між собою ГДП. Подібне представлення, яке називається багаторівневою алгоритмічною системою, вводиться і для алгоритмічних алгебр. Доводиться, що будь-яка регулярна схема алгоритмічної алгебри допускає розклад -за деякою багаторівневою алгоритмічною системою (теорема 3.7). За допомогою введених представлень доводиться наступне твердження.
Теорема 3.8. Для будь-якої регулярної схеми Я, що задає оператор і", існує гакни ГДП Г(Я), що представляє тон же оператор. . .
Понад те, процес обчислення Г за схемою Я в деякому сенсі тотожній функціонуванню ГДП Г(Л).
На основі отриманих в даній главі результатів досліджуються і класифікуються механізми управління обчисленням зна-чен' оператора, заданого ГДП Г(Я). Показано, що обчислення можна організувати на основі "однорідного" способу управління. Наприклад, такий способ може полягати в циклічному виконанні ЕО, впорядкованих довільним чниои. Якщо цикл перервегы... (але біжучий стан змінних збережено), то обчислення можна відновіітн із будь-яким іншим порядком спрацьовувань ЕО.
24 •
і -
У четвертій главі розглянено спеціальні класи алгоритмічних алгебр та деякі застосування одержаних результатів.
Вводяться регулярні схеми операторів алгоритмічних алгебр над пам'яттю та регулярні схеми з настройкою. Обидва поняття аналогічні відповідним поняттям з теорії схем програм. Розглянено їх зв'язок із скінченними дискретними перетворювачами, що складаються з сумісно функціонуючій керуючого та операційного автоматів.
Теорема 4.1. Оператор, представлений скінченним дискрег* ним перетворювачем, може бути представлений регулярною схемою з настройкою в алгоритмічній алгебрі над структуро-ваною інформаційною множиною, сигнатура якої містить лише дві операції - о-ітерацію та композицію операторів.
Теорема 4.2. Оператор, заданий ГДП Г(8о, Зі), може бути заданий регулярною схемою (з настройкою) оператора такої алгебри (недстермінованих) алгоритмів, сигнатура якої містить лише три операції - композицію операторів, а-ітерацію та неде-терміновану диз'юнкцію.
Оскільки ГДП охоплюють сітки Пегрі, приходимо до висновку про те, що функціонування сіток Петрі теж може бути описане в термінах регулярних схем (з настройкою) операторів деякої алгебри алгоритмів.
Теорема 4.3. Для будь-якої регулярної схеми К оператора і" алгебри (детермінованих або недетермінованих) алгоритмів існує регулярна схема Я- (а){(і V ґі V ... V Гк) (з настройкою) алгебри алгоритмів, сигнатура якої містить лише три операції (композицію операторів, недетерміновану диз'юнкцію та а-ітерацію), елементарні оператори якої однозначним чином визначаються за схемою Я , і яка обчислює той же оператор Г
Оскільки регулярна схема, наведена в теоремі, може бути задана за допомогою ГДП, теорема Глушкова про представлення скінченних дискретних перетворювачів регулярними схемами допускає обернення в класі ГДП.
Побудований стохастичшш аналог алгебри алгоритмів -марковська алгоритмічна алгебра, в котрій однорідні ланцю» и Маркова із скінченною кількістю станів визначаються через "елементарні” випадкові процеси такого ж роду. По алгоритмічній алгебрі 31 можна побудувати деяку систему із скінченною кількістю станів, поведінка якої визначається регулярними схемами операторів алгебри 'Я. Якщо для даної системи задати початковий розподіл та матрицю ймовірностей переходів, то прийдемо до марковської алгоритмічної алгебри " М(!й).
Теорема 4.4. Марковська алгоритмічна алгебра М('Л)є гомоморфним образом алгоритмічної алгебри 'Д.
Дана відповідність да можливість рішення ряду таких задач ймовірнісного характеру стосовно до регулярних схем, які формулюються в термінах ланцюгів Маркова.
Розглянено застосування апарату ГДП до побудови і аналіза інформаційно-функціональної моделі системи управління підприємством. Розв’язуегься. задача декомпозиції інформаційного фонда АСУ на бази даних.
У висновках сформульовані винесені на захист результати дисертаційної робота. .
У додатку наводяться довідки про впровадження результатів дисертації. ;
к
ЗАГАЛЬНІ ВИСНОВКИ ТА РЕЗУЛЬТАТИ РОБОТИ
В дисертації пропонується для рішення актуальної наукової проблеми дослідження алгебр детермінованих і недетерміно-еаних алгоріттмів використовувати інтерпретаційні методи, основані на зведенні даних алгебр та пов'язаних з ними формальних об'єктів до інших об'єктів, дослідження яких може бути виконане достатньо ефективним чнном. До таких об’єктів, введених і розглянених в дисертації, відносяться унивсрсальні алгебри ІІ-алгоритмів, формальні мови над інтерпретованим в бульовШ алгебрі алфавітом, генератори дискретних процесів, марковські алт'оригмічмі алгебри.
Розробка та застосування для аналіза алгоритмічних алгебр інтерлрегацшнлх методів показали, що за їх допомогою може бути розв'язаний ряд теоретичних задач, які не допускали рішення традиційними методами і які виявили можливість застосування розробленого апарату для ефективного рішення практичних задач на промисловому рівні.
В роботі отримані наступні результати, що мають новизну та виносяться на захист: ,
. І. Розроблено інтерітрегаційний метод, який дозволяє звести алгебри детермінованих і недетермінованих алгоритмів до единого, суттєво простішого об'єкта - введенної і дослідженої в роботі алгебри £1-алгорнтмів. Показано, що властивості будь-якої алгебра детермінованих або недетермінованих алгоритмів визначаються в,чпетивостямн алгебри -алгоритм і в, яка однозначно задасться по вихідній алгоритмічній алгебрі, Будь-яка алгебра (детермінованих або недегерміновапнх) алгоритмів може-бути побудована по деякій алгебрі П-алгорнтмів за допомогою стандартної конструктивно! процедури. . ,
. і - ’ '
2. Введені і досліджені поняття £1-мови і точної П-моімі. а
на підставі цил понять • вільні алгебри ЇІ-алгорптмі», деіермшо-ванпх і недстермінооаїшх алгоритмів. Встановлено зв'язок вільної алгебри П-алгоріпміп і вільної алгебри недегермшо-ваних алгоритмів з алгеброю Кліпі. Розроблено меюд дослідження вільних алгебр П-алгорнімів, детермінованих і недеіер-мінованих алгоритмів, який базується на властивостях точних П-мов, заданих схемами відповідних алгебр. ■
3. Введене поняття ї розроблений загальний меюд дослідження спеціального класу П-нов • формальній мов над алфавітом, інтерпретованим » бульовій алгебрі. Встановлено можливість класифікації таких мов за аналоппо з класпфнкаїїіио за Хомськіїм.
4. Розроблено меюд дослідження регулярних мов над
алфавітом, інгериретоваїтм и бульиані алгебрі. Всгаиоичсно зв'язок раціональних (регулярних) мои над алфавітом, інтерпретованим в бульовій алгебрі, із скінченними аніомаїамн. Одержане узагальнення на данин випадок іеорсмп Кліпі про представлення раціональних мов автомліами. Описано ідпіль-шій алгоритм, який дозволяє перевірній еквівалентність таких мов. ' -
5. Доведена розв'язність алгоритмічної проблемі! тотожно .і для регулярних мов над алфавітом, інтерпретованим в бульовій алгебрі.
6. Встановлено розв'язність алгоритмічної проблеми ю-тохліості регулярних схем (операторів та умов) вільних аліебр педетермінопаних алгоритмів.
' 7. Побудовано апарат генераторів дкекреппіх процесів,
що охоплює автомати, сітки Петрі га їх модифікації, а пісок скінченні дискретні перетворювачі. Досліджено властивості мов,
пораліжумшіх ГДП, встановлено зв'язок* з частково комутативними моїюїдамн та мовами спілів. ' ; ‘
8. Розроблено метод дослідження регулярних схем опера-
торів алгоритмічних алгебр на основі їх представлення у вигляді генераторів дискретних процесів. На основі даного представ-лешія досліджені способи організації обчислень, описування регулярними схемами, в тому числі стійких до збоїв обчислю-пального пристрою. Показано, - що в класі ГДП с шриою і допускає обернення теорема В.М.Глушкова про представлення оператор;), заданого скінченним дискретним перетворювачем, регулярною схемою алгоритмічної алгебри. .. , -
9. Розроблено мстодн формального опису дискрстннх перетворювачів в термінах регулярних схем (з настройкою) операторів алгоритмічних алгебр.
10. Розроблено метод дослідження випадкових обчислю-
вальних процесів, які відповідають однорідним ланцюгам Маркова із скінченною кількістю станів і інтерпретуються як елементи введеної в' роботі млрковської алгоритмічної алгебри -стохасгнчіїого аналога алгебри алгоритмів. .
11. На основі розроблених теоретичних положень запропоноване використання введеного в роботі апарата для програмного моделювання та аналізу системи управління промисловим підприємством, а також для рішення задачі де-композинії інформаційного фонду підприсмсгаа на бази даних. *
- Підходи і методи, запропоновані в дисертації, мають загальний характер і можуть бути використані для рішення ряда інших тсоретнчнихі практичних задач. .
Основні результати дисертаційної роботи відображені в наступних публікаціях: г,-
1. Романов А.Н., Суржко С.В. Основы автоматизации проектирования и1|формацнонно-управляющих систем. - М.: МЭСИ, 1985.- 107 с.
2. Романов А.Н., Суржко С.В. Теоретические основы построения сложных экономических систем. - М.: МЭСИ, 1981, - 88 с.
3. Суржко С.В. О некоторых классах алгоритмических алгебр II Кибернетика. -1990. - N2. - С.108-112.
4. Суржко С.В. О вычислении значений операторов, заданных регулярными схемами // Кибернетика. - 1989. - N6. - С. 75-77,82.
5. Суржко С.В. О категорном подходе к изучению алгоритмических алгебр // Кибернетика и системный анализ. - 1993. - N2. -С. 50-62.
6. Суржко С.В. О сетевых моделях дискретных преобразователей информации // Кибернетика и системный анализ. - 1991. - N5. -С.83-90.
7. Суржко С.В., Ющенко Е.Л. О языках над алфавитом, интерпретированным в булевой алгебре // Кибернетика и системный анализ. - 1995. - №3. - С. 86-106.
8. Ющенко Е.Л., Цейтлин Г.Е., Суржко С.В. Алгоритмические алгебры Глущкова и проблемы моделирования систем // Кибернетика и системный анализ. - 1993. - N3. - С. 106-116.
9. Суржко С.В., Кример А.А. Моделирование и программные средства синтеза и анализа системы управления предприятием // Управляющие системы и машины. - 1990. - №5. - С. 107-112.
10. Суржко С.В. Фильтрация дискретных процессов // Проблемы бионики. Выпуск 41. - Харьков: Внща школа, 1988. - С. 109-113.
11. Сур "/а..) С.В. Некоторые свойства сопряженных нагруженных графов II Вестник Львовского университета. Серия экономическая. Выпуск 18. - Львов: Вища школа, 1986. - С. 79-80.
№
12. Суржко С.В. Структурирование и декомпозиция дискретных преобразователей // Декомпозиционные методы проектирования систем. - Киев: Ин-т кибернетики им. В.М.Глушкова АН УССР,
1988.-С.49-55.
13. Суржко С.В. Об управляемых динамических системах // Теоретико-системные методы ‘и их использование в автоматизированных системах. - Киев: Ин-т Кибернетики АН УССР, 1983. -С. 36-40.
14. Суржко С.В. О языках, порождаемых дискретными преобразователями II Цифровые устройства н микропроцессоры в системах передачи информации. Межвузовский сборник научных трудов ХИИТ. - Харьков: ХШ1Т, 1987. - С. 58-62.
15. Суржко С.В. О функциях от элементов упорядоченного пространства // Вестник Львовского университета. Серия экономическая. Выпуск 15. - Львов: Вища школа, 1983. - С. 73-75.
16. Суржко С.В. Совершенствование информационного обеспечения - основа повышения качества функционирования интегрированной системы управления /I Средства связи. Выпуск 1. -М.: ЦООНТИ "ЭКОС", 1989. - С. 10-12.
17. Романов А.Н., Одинцов Б.Е., Суржко С.В. О задаче струк-
туризации интегрированного информационного фонда для об-служивання пользователей различного типа // Применение методов вычислительной математики в экономике. Сборник науч-ныхтрудов. - М.: МЭСИ, 1981. - С. 31-44. ~
18. Романов А.Н., Одинцов Б.Е., Суржко С.В. Структуризация информационных фондов систем управления // Технология реализации многоуровневых систем управления базами данных. Сборник научных трудов. - М.: МЭСИ, 1982.-С. 28-41.
19. Романов А.Н., Суржко С.В., Одинцов Б.Е. Оптимизационная модель определения состава баз данных для запросных
задач И Исследование проблем проектирования информационного и программного обеспечения АСУ. Сборник научны ч трудов. - М.: МЭСИ, 1981. - С. 39-49.
20. Одинцов Б.Е., Романов А.Н., Суржко С.В. О некоторых подходах к организации информационных фондов АСУ на основе интеграции баз данных II Машинная обработка экономической информации на ЭВМ. Сборник научных трудов. - М.: МЭСИ, 1980.-С. 31-39.
21. Одинцов Б.Е., Романов' А.Н., Суржко С.В. О некоторых методах определения состава интегрированного фонда АСУ // Современные проблемы обработки экономической информации в АСУ. Сборник научных трудов. - М.: МЭСИ, 1981. - С. 39-49.
22. Одинцов Б.Е., Суржко |С.В. Метод определения уровня дублирования данных в информационном фонде АСУ II Теория и практика проектирования информационного обеспечения АСУ. Сборник научных трудов. - М.: МЭСИ, 1981. - С. 50-63.
23. Пакет прикладных программ ''Декомпозиция информационной базы”, нив. М> ЮЗОЮтраслевои фонд алгоритмов и иро-грамм (ОФАП АСУ Мштрибора). Каталог. - Калинин: Центрпрограммсистем, 1983. - 313 с.
24. Романов А.Н., Суржко С.В. Генераторы дискретных процессов: модели и приложения // Первый Всемирный Конгресс Общества математической статистики и теории вероятностей им. Бернулли: Тезисы докладов. - М.: Паука, 1986. - С. 993.
25. Суржко С.В. Алгебра П-регулярних елементі» та її властивості // Всеукраїнська наукова конференція "Застосування обппе-люпально, техніки, математичного моделювання та математичних методів у наукових дослідженнях. Тези доповідей. - Львів, 1995.-С. 85.
26. Суржко С.В. Алгебры 1С-регулярных схем и алгоритмические
алгебры II Друга українська конференція з автоматичного керу-ваннл "Лвтомагнка-95". Праці. Том 2. - Львів, 1995. - С. 137.
27. С'уржко С.В. Полугруппы и структурирование автоматов II XIX Всесоюзная алгебраическая конференция. Тезисы сообщений. Часть 1. - Львов, 1987. - С. 270.
28. Суржко С.В. Генераторы дискретных процессов /У Седьмая
Всесоюзная школа-семинар "Распараллеливание обработки информации". Тезисы докладов и сообщений. Часть 1. • Львов,
1989.-С, 224-225. . . . '
29. Суржко С.В. Моделирование, анализ и компьютеризация информационных процессов па основе математической модели системы управления 1! Компьютеризация информационных процессов в управлении народным хозяйством. Тезисы докладов Всесоюзной научной конференции. Часть 2. - М.: МЭСИ, 1988. -
с. 84-85. ■ , • • • - ". ■■ .
30- Суржко С.В. Об одном подходе к описанию многоуровневых схем алгоритмов И Пятая Всесоюзная школа-семинар "Распараллеливание обработки информации". Тезисы докладов и сообщений. Часть 2.-Львов, 1985.-С. 91.
31. Суржко С.В. Об 5-алгебрах и их обобщениях // Восьмой Всесоюзный семинар "Параллельное программирование и высокопроизводительные структуры". Тезисы докладов. - Киев: Ин-т кибернетики им. В.М.Глушкова АН УССР, 1988.. С. 7-8.
32. Суржко С.В. О двух подходах к формализованному описанию и исследованию систем управления 7/ Методы синтеза и планирования развития структур крупномасштабных систем. Тезисы докладов У Всесоюзного семинара; - М.: Ин-т проблем управления, 1990.-С. 15.
33. Суржко С.В. О динамических сетевых моделях информа-шюннэ-управляющпх систем // Распределенные информанчон-
• и '
но-улравляющне системы. Саратов: Изд-во Саратовского университета, 1988.- С. 21.
34. Суржко С.В. О моделировании действий и ситуаций в экспертных системах // Восьмой Всесоюзный семинар "Параллельное программирование и высокопроизводительные структуры". Тезисы докладов. - Киев: Ин-т кибернетики нм.
B.М.Глушкова АН УССР, 1988.-С, 199.
35. Суржко С.В, О полугрупповых свойствах параллельных
процессов //X Всесоюзный семинар "Параллельное программирование и высокопроизводительные системы: методы представления знаний в информационных технологиях". Тезисы докладов. - Киев: Ин-т кибернетики нм. В.М.Глушкова АН УССР,
1990.-С. 7. ,
36. Суржко С.В. Организация вычислении в соответствии с регулярными схемами операторов II Седьмая Всесоюзная школа-семинар "Распараллеливание обработки информации". Тезисы докладов и сообщений. Часть 1. - Львов, 1989. - С. 226.
37. Суржко С.В. Полугруппы дискретных процессов и минимизация бесконечных автоматов II Шестая Всесоюзная школа-семинар "Распараллеливание обработки информации". Тезисы докладов. Часть 3. - Львов, 1987. - С. 20-21.
38. Суржко С.В. Расширения системы алгоритмических алгебр // Ш^тая Всесоюзная школа-семинар "Распараллеливание обработки информации". Тезисы докладов. Часть I. - Львов, 1987. -
C. 77-78;
39. Сур;:ско С.В. Схемы функционирования дискретных систем управленьл И Синтез структур автоматизированного управления в крупномасштабных системах. Тезисы докладов Всесоюзного семинара. - Херсон, 1989. - С. 7-8.
40. Сурж ко С.В., Ющенко Е.Л. О языках над алфавитом, ннтер-прслфсшаиным в булевой алгебре II Друга українська конференція з автоматичного керування "Автома гика-95". Праці. Том 2. -Львів, (995.-С. 137-138.
41. Суржко С.В., Плаксші В.Ф., Сына И.М. Модельный подход к анализу, разработке к сопровождению интегрированной автоматизированной системы управления // Практическое при-менснне современных технологии программирования, пакетов прикладных программ в вычислительных системах н сетях ЭВМ. Тезисы докладов 1 Всесоюзной научно-технической конференции. - Днепропетровск, 1988. - С. 150-151.
Особистий внесок. Всі результата, що складають основний зміст роботи, отримані особисто автором. В публікаціях, написаних у співавторстві, дисертанту належать: в роботах (1,2,17231 • формальні моделі декомпозиції інформаційного фонду; в [7,40] - основні результати, крім теореми 4 та леми 8, отриманих сумісно із співавтором (теорема 2.4 і лема 2.8 дисертації); в [8] -недегерміиовані процеси, зв’язок з дискретними перетворювачами, поняття марковської САА, багаторівневі алгоритмічні системи; в [9,24,41]-апарат ГДП.
Surzhko S.V. Interpretation methods in the algorithmic algebras theory. .
Doctor of physics-mathematical science thesis, speciality 01.05.01 - theoretical basics of informatics and cybernetics
(mathematical cybernetics). . -.
National Academy of Sciences of Ukraine, Institute of Cybernetics named after V.M.Glushkov, Kiev, 1996.
The manuscript based on 41 articles is defended. It contains the results of algorithmic algebras investigations. The methods of the investigations based on conseptions of the algebra of £l-algorithms, the generator of discrete processes, Markov's algorithmic algebra, etc. are worked out, Properties of the algebras of determinated and non-determinated algorithms and connected objects are studied, the solvability of the problem of equivalence for the free algebra of non-determinated algorithms is proved on the basis of these method*.
Суржко C.B. Интерпретационные методы в теории алгоритмических алгебр.
Диссертация на соискание ученой степени доктора физикоматематических наук по специальности 01.05.01 - теоретические основы информатики и кибернетики (математическая кибернетика).
Национальная Академия наук Украины, Институт кибернетики им.В.М.Глушкова, Киев, 1996.
Защищается рукопись на основе 41 работы, содержащих результаты исследования алгоритмических алгебр. Разработаны •методы исследований, основанные на понятиях алгебры D-алгоритмов, генератора дискретных процессов* марковской алгоритмической алгебры и т.д. На базе этих методов изучены евг "їства алгебр детерминированных и недетерминированных алгоритмов и связанных с ними объектов, доказана разрешимость проблемы тождества для свободной алгебры недегер-мннированных алгоритмов.
Ключові слова: алгебра алгоритмів, алгебраїчне програмування, алгоритм, алгоритмічна алгебра, система алгоритмічних алгебр, схеми алгоритмів, схеми програм.
НАЦИОНАЛЬНАЯ АКАДЕМИЯ НАУК УКРАИНЫ
инс тит^гтшштактики им. в. м. рлушкова
' :• ';?" лГ •]■). '81 V?* *;г -г. л I' Л $ -У
-•-зидиум р
(решение ОТ" С£7"
присудил ученую степень & л
правах рукописи
Начальник уп
1-Ия В А.1\ Росс,
СУРЖКО Сергей Васильевич
ИНТЕРПРЕТАЦИОННЫЕ МЕТОДЕ! В ТЕОРИИ АЛГОРИТМИЧЕСКИХ АЛГЕБР
Специальность 01.05.01 - теоретические основы информатики и кибернетики (математическая кибернетика)
Диссертация на соискание ученой степени доктора физико-математических наук
Научный консультант - член-корреспондент НАН Украины Е.Л.ЮЩЕНКО
От
¡1еописС> . \ В С^рп-^ссо
О / . "
I ч
у/1'
ё -ер ¡£¿о
О К
о
Киев-1996
СОДЕРЖАНИЕ
Введение ...... . . .,................ . ,.......................... 4
Глава 1. Алгебры 0-алгоритмов и свободные алгоритмические алгебры
1. Основные определения ..................................20
1.1. Недетерминированные операторы.- Алгебра
П-алгоритмов . . .. ............... ,.. .......... 20
1.2. Алгебра недетерминированных алгоритмов ...........23
1.3. Алгебра детерминированных алгоритмов .............26
2. Редукты алгебры О-алгоритмов ..........................27
3. П-языки .................................32
4. Свободные алгебры П-алгоритмов. Связь
с алгеброй Клини ......................................43
5. Свободные алгебры детерминированных алгоритмов ........47
6. Свободные алгебры недетерминированных алгоритмов ......51
Глава 2. Формальные языки с интерпретацией алфавита в булевой алгебре
1. Вводные определения ...........................................56
2. Верхняя полурещетка и и ее свойства . . ................ .59
3. Связь с конечными автоматами ..................................66
4. Регулярные языки над интерпретированным алфавитом .....69
5. Алгоритмические проблемы ........................................87
6. Классификация языков над интерпретированным алфавитом ..92
7. Разрешимость проблемы тождества в свободных алгебрах недетерминированных алгоритмов ....................... .96
о
Глава 3. Сетевые динамические модели регулярных схем операторов
1. Генераторы дискретных процессов (ГДП). Основные определения ...........................................99
2. Связь с сетями Петри .................................106
3. Свободные ГДП ........................................107
4. Связь с частично коммутативными моноидами и
языками следов .......................................112
5. Полугрупповые свойства свободного языка ГДП ..........115
6. Многоуровневое представление ГДП .....................117
7. Многоуровневые алгоритмические системы. Представление регулярных схем операторов в виде ГДП ................119
8. Организация вычисления значений оператора алгоритмической алгебры, заданного ГДП ...............................136
Глава 4. Специальные классы алгоритмических алгебр. Некоторые приложения
1. Регулярные схемы над памятью. Связь с дискретными преобразователями ....................................142
2. Вероятностью оценки алгоритмических процессов. Марковские алгоритмические алгебры ..............................14 8
3. Некоторые приложения .................................155
3.1. Моделирование и анализ системы управления предприятием ....................................155
3.2, Декомпозиция информационного фонда
на базы данных ..................................165
Заключение ..................................................175
Список литературы ...........................................179
Приложение ..................................................193
ВВЕДЕНИЕ
Одной из определяющих тенденций развития науки является ее математизация, охватывающая, в частности, теорию компьютерных вычислений, в том числе теоретическое программирование. В этой связи особо следует отметить интенсивное проникновение в компьютерную науку идей и методов дискретной математики, алгебры и математической логики, успешное применение теории автоматов, формальных языков и грамматик как для сугубо теоретических, так и для практических целей, в частности, разработки систем программирования, основанных на языках высокого и сверхвысокого уровня, развитие средств логического программирования и т.д.
Особый вклад в развитие данной проблематики вносит алгебраический аппарат, на основе которого создан целый ряд теоретических и практических работ, среди которых особое место занимают работы, связанные с исследованием и применением идей теории алгоритмических алгебр. Основным объектом данной теории является универсальная алгебра алгоритмов той или иной сигнатуры, операции которой моделируют различные программистские конструкции, а целью -исследование математических свойств данной алгебры и связанных с ней объектов, в частности, установление взаимосвязей этих объектов с другими разделами математики и математической кибернетики.
Основы данной теории была заложены В.М.Глушковым в работах [17, 18], в которых впервые было введено и исследовано понятие алгоритмической алгебры (иначе - алгебры алгоритмов или системы алгоритмических алгебр), На основе этого понятия В.М.Глушковым и его учениками и последователями был получен целый ряд результатов
как теоретического, так и прикладного характера (см., в частности, работы [19-22, 27, 30- 33, 35, 43-46, 56, 105-110, 112-115]). Отметим лишь некоторые из результатов, которые имеют наиболее тесную связь с данной диссертационной работой.
Одним из основных результатов теории алгоритмических алгебр следует считать теорему В'.М.Глушкова о том, что функционирование конечного дискретного преобразователя (взаимодействующих автоматов, управляющего и операционного) может быть описано регулярной схемой оператора алгоритмической алгебры, однозначно определяемой по данному преобразователю [18]. Этот результат указывает, в частности, на тесную взаимосвязь алгоритмических проблем, формулируемых для алгоритмических алгебр, с проблемами эквивалентности дискретных преобразователей. A.A.Летичевским был получен ряд результатов по алгоритмической разрешимости проблемы эквивалентности автоматов относительно полугрупп [43-45]. Разрешимость алгоритмической проблемы тождества слов и существование полной системы аксиом для специального класса алгебр алгоритмов (алгебр с замкнутыми условиями или S-алгебр) была установлена Г.Е.Цейтлиным в работе [107]. Аналогичный результат для специального класса алгебр недетерминированных алгоритмов (S(Н)-алгебр) был получен Ю.А.Ющенко [115]. А.А.Летичевским была установлена связь алгоритмических алгебр с теорией схем программ [40], что позволило рассматривать проблематику алгебр алгоритмов в общем контексте теории дискретных систем [31] . В работах [12, 4 6, 105] рассмотрены алгебры структур данных и их связь с проблемами проектирования программ.
Важным этапом в развитии теории и приложений алгоритмических алгебр явилось издание монографии В.М. ГЛушкова, Г.Е. Цейтлина,
E.JI. Ющенко "Алгебра. Языки. Программирование" (Киев: Наук, думка, 1974. - 328 е.; 2-е изд., перераб., 1978. - 320 е.; 3-е изд., перераб. и доп., 1989. - 376 е.; Berlin: Acad.-Verl., 1980, -322 s,), посвященной фундаментальным исследованиям, связанным с применением аппарата общей алгебры в программировании.
Сфера приложений теории алгоритмических алгебр чрезвычайно обширна и охватывает параллельную обработку данных на многопроцессорных машинных комплексах [7, 20, 33], проектирование вычислительных систем [30], проектирование и синтез схем программ'[109-110, 112-113], анализ и оптимизацию схем программ [106], структуры данных [105], специализированные системы автоматизированного проектирования [111, 113], формы представления знаний [108], моделирование технологических процессов [3, 4, 111], а также'ряд других проблем специального характера. Эти приложения опираются и, в свою очередь, стимулируют такие теоретические исследования, которые призваны объяснить процессы, задаваемые регулярными схемами операторов и условий алгоритмических алгебр, а также сделать их исследование эффективным.
Следует заметить, что одной из основных задач, с необходимостью решения которых связано возникновение алгоритмических алгебр, являлась задача эквивалентных преобразований микропрограмм (регулярных схем)[17], которая удовлетворительным образом не решена до сих пор. Поэтому весьма актуальным является исследование алгоритмических проблем тождества для тех или иных классов алгебр алгоритмов.
Теорема В.М.Глушкова о представлении дискретных преобразователей регулярными схемами устанавливает возможность (и способ) формального описания вычислений, задаваемых вычислительным
устройством (дискретным преобразователем) в алгебраических терминах. Вместе с тем, обратное утверждение для рассмотренного класса преобразователей не имеет места. Поэтому актуальными являются задачи построения таких классов дискретных преобразователей, в котором указанная теорема не только верна, но и допускает обращение. Не менее важными являются задачи теоретического исследования способов организации последовательных и параллельных вычислений, задаваемых регулярными схемами операторов и обладающих теми или иными полезными в практическом отношении свойствами.
Решение этих и целого ряда других задач крайне затруднено сложностью основного объекта - алгоритмической алгебры, сигнатура которой включает в себя до десятка специфических операций и которая далеко не всегда позволяет применить для своего исследования хорошо разработанный аппарат или же непосредственно использовать результаты общетеоретического характера. Поэтому проблема разработки как специальных методов исследования алгоритмических алгебр, так и таких методов, которые позволяли бы эффективно использовать результаты известных математических теорий, представляется весьма актуальной. Именно к их числу относятся интерпретационные методы, т.е. такие, использование которых позволяет заменить (интерпретировать) исходный объект в некотором смысле изоморфным или же эквивалентным ему формальным объектом другого класса со свойствами, позволяющими достаточно эффективно выполнить исследование и перенести полученные результаты на исходный объект.
Объектом исследования в диссертации являются алгебры (детерминированных и недетерминированных) алгоритмов и связанные с ними объекты.
Целью диссертационной работы является разработка и применение интерпретационных методов исследования алгоритмических алгебр.
Для достижения цели исследования в диссертации решены следующие задачи:
- разработан метод редукции алгебр детерминированных и недетерминированных алгоритмов к единому, более простому объекту -
алгебре П-алгоритмов;
- введено и исследовано понятие О.-языка, обобщающее формальный язык, разработан метод изучения £2-языков путем их сведения к унифицированным объектам, так называемым точным П-языкам;
- введены понятия и разработан метод исследования свободных алгебр й-алгоритмов, детерминированных и недетерминированных алгоритмов, основанный на точных П-языках;
- разработан общий метод исследования специального класса П-языков - формальных языков над алфавитом, интерпретированным в булевой алгебре;
- разработан метод изучения регулярных языков над алфавитом, интерпретированным в булевой алгебре, в том числе алгоритм проверки таких языков на совпадение;
- разработан метод классификации языков над алфавитом, интерпретированным в булевой алгебре;
- разработан аппарат динамических сетевых моделей специального вида (генераторов дискретных процессов, ГДП) и, на его
основе, - метод моделирования регулярных схем операторов алгоритмических алгебр в виде ГДП;
- разработан метод многоуровневого представления алгоритмических алгебр;
- разработаны методы формального описания дискретных преобразователей в терминах регулярных схем (с настройкой) операторов алгоритмических алгебр;
- разработан метод исследования случайных вычислительных процессов, задаваемых однородными цепями Маркова с конечным числом состояний, интерпретируемых как элементы марковской алгоритмической алгебры - стохастического аналога алгебры алгоритмов.
Метода исследования основаны на применении общей теории универсальных алгебр, теории полугрупп, решеток, булевых алгебр, теории формальных языков и грамматик, абстрактных автоматов, а также теории случайных процессов.
Научная новизна полученных результатов состоит в следующем.
1. Показано, что свойства любой алгебры детерминированных или недетерминированных алгоритмов определяются свойствами существенно
более простого объекта - алгебры О-алгоритМов, введенной в работе и однозначно задаваемой по исходной алгоритмической алгебре. Любая алгебра (детерминированных или недетерминированных) алгоритмов может быть построена по некоторой алгебре П-алгоритмов с помощью стандартной конструктивной процедуры.
2. Введены и исследованы понятия П-языка и точного О-языка, обобщающие понятие формального языка и допускающие интерпретацию в классе частичных точечно-множественных (недетерминированных) операторов. На основе этих понятий введены и исследованы свободные
алгебры П-алгоритмов, детерминированных и недетерминированных .
алгоритмов. Частным случаем свободной алгебры О-алгоритмов является алгебра регулярных выражений (алгебра Клини). Установлены свойства (точных) П-языков, задаваемых регулярными схемами свободных алгебр детерминированных и недетерминированных алгоритмов.
3. Впервые введен и исследован класс формальных языков, построенных над алфавитом, часть символов которого интерпретирована в булевой алгебре. Обычные формальные языки являются частным случаем языков данного класса. Установлена возможность классификации таких языков по аналогии с классификацией Хомского.
4. Установлена связь рациональных (регулярных) языков над алфавитом, интерпретированным в булевой алгебре, с конечными автоматами. Получено обобщение на данный случай теоремы Клини о представлении рациональных языков автоматами. Доказана разрешимость алгоритмической проблемы тождества для регулярных языков над алфавитом, интерпретированным в булевой алгебре.
5. Установлена разрешимость алгоритмической проблемы тождества регулярных схем (операторов и условий) свободных алгебр недетерминированных алгоритмов.
6. Построен аппарат динамических сетевых моделей (ГДП), охватывающий сети Петри и их модификации, а также конечные дискретные преобразователи. Исследованы полугрупповые свойства свободного языка, порождаемого ГДП, установлена связь с частично коммутативными моноидами и теорией следов,
7. Установлена возможность представления регулярной схемы оператора алгоритмической алгебры в виде динамической сетевой модели (ГДП), вычисляющей тот же оператор. На основе данного
представления получена возможность организации вычислений, устойчивых к "сбоям" гипотетической машины.
8. Построен и исследован стохастический аналог алгоритмической алгебры - марковская алгоритмическая алгебра, позволяющая решать ряд задач вероятностного характера.
Практическая ценность и реализация работы. В работе построен метод, позволяющий реализовать алгебры детерминированных и недетерминированных алгоритмов, сигнатура которых включает соответственно семь и восемь операций {без учета нульарных операций) средствами существенно более простой алгебры О-алгоритмов с четырьмя операциями. Такой подход упрощает разработку программных средств, ориентированных на представление алгоритмов и программ в виде регулярных схем алгоритмических алгебр.
Разработанный в диссертации метод моделирования регулярных схем операторов алгоритмических алгебр в виде ГДП позволяет организовать вычислительный процесс, устойчивый к сбоям вычислительного устройства.
Аппарат марковских алгоритмических алгебр позволяет эффективно решать ряд практических задач вероятностного характера, относящихся к программным вычислениям, в частности, вероятностный аналог задачи тестирования программ.
Аппарат генераторов дискретных процессов позволяет осуществить программное моделирование и анализ системы управления промышленным предприятия. Решается также практическая задача декомпозиции информационного фонда промышленного предприятия на базы данных.
На основе полученных результатов при непосредственном участии автора были разработаны программные средства моделирования и
анализа интегрированной системы управления дискретным производством ПАРИС и АВАНС, а также пакет прикладных программ "Декомпозиция информационной базы" (Отраслевой фонд алгоритмов и программ АСУ Минприбора СССР, инв.№ 1030, Калинин, Центрпрограммсистем, 1983), реализующий описанный в диссертации метод декомпозиции информационного фонда на базы данных.
Системы ПАРИС и АВАНС были апробированы на реальных данных, относящихся к трем подсистемам интегрированной АСУ НПО "Электрон" (системы автоматизированного проектирования изделий, системы оперативно-производственного планирования, автоматизированной системы оперативно-диспетчерского управления). Результаты моделирования были обработаны, и на их основе разработаны конкретные рекомендации для повышения эффективности системы управления Львовского научно-производственного объедине
