Размещено на http://www.allbest.ru/

ХЕРСОНСЬКИЙ НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ

УДК 681.32

ІНСТРУМЕНТАРІЙ ПРОЕКТУВАННЯ КОМП'ЮТЕРНИХ СИСТЕМ НА ОСНОВІ ДІАЛОГОВИХ АЛГЕБРО-ГРАМАТИЧНИХ МОДЕЛЕЙ ПРЕДСТАВЛЕННЯ ЗНАНЬ

05.13.06 - автоматизовані системи управління і прогресивні

інформаційні технології

АВТОРЕФЕРАТ

дисертації на здобуття наукового ступеня

кандидата технічних наук

ХОХЛОВ ВАДИМ АНАТОЛІЙОВИЧ

Херсон - 2006

Дисертацією є рукопис.

Робота виконана в Херсонському національному технічному університеті Міністерства освіти і науки України.

Науковий керівник: кандидат фізико-математичних наук, доцент Петрушенко Анатолій Миколайович, доцент кафедри інформаційних технологій Херсонського національного технічного університету.

Офіційні опоненти:

доктор технічних наук, професор Погорілий Сергій Дем'янович, заступник завідувача кафедри напівпровідникової електроніки Київського національного університету імені Тараса Шевченка;

кандидат технічних наук, доцент Булкін Віталій Іванович, завідувач секцією інформаційних технологій кафедри прикладної математики і інформаційних технологій Макіївського економіко-гуманітарного інституту, Міністерство освіти і науки України.

Провідна установа:

Міжнародний науково-навчальний центр інформаційних технологій та систем НАНУ, відділ автоматизованих систем обробки даних Міністерства освіти і науки України, м. Київ.

Захист відбудеться “3” липня 2006 р. о 10⁰⁰ годині на засіданні спеціалізованої вченої ради Д 67.052.01 Херсонського національного технічного університету за адресою: 73008, м. Херсон, Бериславське шосе 24, корп. 1, ауд. 223.

З дисертацією можна ознайомитися у бібліотеці Херсонського національного технічного університету за адресою: 73008, м. Херсон, Бериславське шосе 24, корп. 1.

Автореферат розісланий “2” червня 2006 р.

Вчений секретар

спеціалізованої вченої ради В.О. Костін

Загальна характеристика роботи

Актуальність теми. З часу виникнення автоматизованих систем управління (АСУ) теорія та практика керування зазнали ряд змін, які торкнулися, зокрема, моделей і методів керування, способів алгоритмізації задач, застосовуваного математичного апарату. Встановлено, що можливість автоматизації тих або інших процесів керування значною мірою визначається можливістю їх формалізації. При оцінці результату керуючого впливу треба, взагалі кажучи, враховувати випадкові збурення, які впливають на поводження об'єкта керування. Тому постає потреба в розробці підходів, що ґрунтуються на методах опису як недетермінованих, так і випадкових процесів функціонування систем керування. В той же час з ростом складності об'єктів управління вартість проектних робіт значно збільшується. Це обумовлено, зокрема, тим, що досить часто вимоги до АСУ та автоматизованих комп'ютерних систем (КС), що проектуються, формулюються замовником не достатньо формально, а також можуть змінюватися в процесі розробки та життєвого циклу цих систем. Існуючі інструментальні засоби майже не враховують зазначені особливості проектування. Як наслідок - значна кількість проектів для своєї розробки потребує набагато більше коштів і часу, ніж планувалося, або взагалі не реалізується. Єдиним виходом з цієї ситуації є використання теоретично обґрунтованих автоматизованих методів розробки АСУ, що призводять до зменшення термінів розробки й підвищення якості систем, що розробляються. Дана дисертаційна робота присвячена створенню інструментарію на основі діалогових алгебро-граматичних моделей представлення знань, що являються різновидом так званих трансформаційних методів синтезу КС і займають проміжне положення між класичними індуктивними і дедуктивними методами. Значний внесок у дану галузь досліджень внесли представники української кібернетичної школи, насамперед, Глушков В.М., Єршов А.П., Редько В.Н., Скуріхін В.І., Летічевський О.А., Перевозчикова О.Л., Ющенко К.Л., Анісімов А.В., Капітонова Ю.В., Цейтлін Г.О. та їх учні, праці яких створили необхідні теоретичні і практичні передумови для даного дисертаційного дослідження.

Зв'язок роботи з науковими програмами, планами, темами. Тематика дисертаційної роботи, її ціль і основні задачі відповідають державним науково-технічним програмам, що сформульовані в Законах України “Про вищу освіту”, “Про наукову і науково-технічну діяльність”, “Про національну програму інформатизації”, а також планам науково-технічних робіт Міністерства освіти і науки України:

6. - інформатика, автоматизація і приладобудування;

6.2.2 - перспективні інформаційні технології і системи.

Дисертаційна робота є складовою частиною тематичної програми досліджень кафедри інформаційних технологій Херсонського національного технічного університету (ХНТУ) за темою “Розробка теорії й інструментарію трансформаційних методів синтезу знань у різноманітних предметних областях”.

Автор брав участь у даній роботі як виконавець. Роль автора полягала в розробці та реалізації алгоритмів роботи інструментальних засобів, що розроблялись.

Мета і завдання дослідження. Метою дисертаційної роботи є розробка на основі діалогових алгебро-граматичних моделей представлення знань інструментарію проектування програмних і апаратних компонент АСУ.

Для досягнення поставленої мети в роботі необхідно вирішити наступні задачі:

- проаналізувати існуючі моделі представлення знань і побудовані на них, насамперед трансформаційні, методи формального синтезу автоматизованих КС;

- розробити відповідний обраній діалоговій алгебро-граматичній моделі представлення знань інструментарій - діалогову трансформаційну машину (ДТМ), зокрема, компоненти її архітектури: інтелектуальний редактор - компоненту машини виводу (МВ), а також базу знань (БЗ);

- розширити вхідну мову ДТМ, що наближена до природної і базується на апараті алгебри алгоритмів, засобами діалогової взаємодії користувача з автоматизованою КС;

- розробити методи представлення знань у БЗ ДТМ;

- розробити технологію підключення цільових мов програмування (МП) та проектування апаратури до вхідної мови ДТМ;

- розробити алгоритми синтезу апаратного і програмного забезпечення комп'ютерів;

- виконати наповнення БЗ для предметних областей (ПрО), пов'язаних із синтезом визначених класів програмного й апаратного забезпечення комп'ютерів.

Об'єктом дослідження є автоматизовані системи проектування універсальних і спеціалізованих комп'ютерних систем.

Предмет дослідження - інструментальні засоби проектування комп'ютерних систем на основі діалогових алгебро-граматичних моделей представлення знань.

Методи дослідження. Для розробки компонент архітектури ДТМ, методів представлення знань в БЗ були використані методи теорії алгоритмів, теорії алгебраїчних систем. Для розробки алгоритмів підключення цільових МП застосовувалась теорія формальних мов і граматик. Для розробки алгоритмів формування специфікацій операційних пристроїв використовувались методи абстрактної і структурної теорії автоматів.

Наукова новизна одержаних результатів полягає в наступному:

- дістала подальший розвиток близька до природної мова проектування КС САА/Д- вхідна мова ДТМ - шляхом розширення засобами діалогової взаємодії користувача та КС, що проектується;

- вперше запропоновано апарат параметризованих шаблонів, який використовується при підключенні до мови САА/Д цільових МП і дозволяє встановити однозначну відповідність між САА/Д-схемами й асоційованими з ними програмами в цільовій МП;

- дістала подальший розвиток МВ ДТМ шляхом розробки її компоненти - інтелектуального редактора (ІР), що дозволяє не лише динамічно (в діалозі) проектувати синтаксично правильні САА/Д-схеми, зокрема, змістовні ідентифікатори операторів та умов, але й асоційовані з цими схемами програми в цільових МП;

- отримала подальший розвиток структура БЗ ДТМ і механізми її супроводу та модифікації, що розроблені у відповідності з діалоговими алгебро-граматичними моделями представлення знань й методами підключення цільових МП;

- вперше реалізовані механізми роботи з історією створення проекту КС (САА/Д-схеми, САА/Д-формули, програми), що дозволяють підтримувати спіральну модель життєвого циклу (ЖЦ) КС;

- вперше алгоритми синтезу операційних пристроїв (ОП) за їх функціональними мікропрограмами, представленим у вигляді граф-схем, розповсюджені на САА/Д-схеми, що дозволяє автоматизувати як процеси проектування ОП, так і оптимізацію їх структури і затрат обладнання не лише методами структурної теорії автоматів, але й методами алгебри алгоритмів.

Практичне значення одержаних результатів:

- використання мови САА/Д, близької до природної, дозволяє підключати до процесу діалогового проектування КС замовника вже на ранніх стадіях їх розробки та, завдяки підтримці спіральної моделі ЖЦ КС, оперативно вносити необхідні зміни в розробку, що, разом з покладеним в основу ДТМ математичним апаратом, сприяє створенню КС необхідної якості в прийнятні терміни;

- можливість синтезу по одній і тій самій САА/Д-схемі як програми, так і специфікації операційного пристрою, що її реалізують, дозволяє відлагоджувати роботу пристрою на його програмній моделі, що суттєво скорочує термін розробки пристрою;

- виконане наповнення БЗ ДТМ для визначених класів КС.

Інструментарій, розроблений у ході виконання дисертаційної роботи, був упроваджений на виробництві в ТОВ “Сонар”. Зокрема, з його допомогою було розроблено АРМ для операторів кабельного телебачення, що у даний час експлуатується в ТРК “Берег”, АРМ для обробки результатів соціологічних опитувань, а також ряд модулів для АРМ бухгалтера на Херсонському головпоштамті. Розроблений інструментарій застосовується також в навчальному процесі ХНТУ при виконанні курсових робіт, дипломних проектів студентів і кваліфікаційних робіт магістрів за спеціальністю “Комп'ютерні системи і мережі”.

Особистий внесок здобувача. Автор брав безпосередню участь у створенні програмних модулів ДТМ від розробки алгоритмів і вибору структур даних до відлагодження і впровадження готового програмного продукту.

Апробація результатів дисертації. Основні положення дисертаційної роботи доповідалися й обговорювалися на Міжнародних конференціях: по математичному моделюванню (Херсон-Лазурне, 1998, 2000, 2002), Міжнародних науково-практичних конференціях по програмуванню УкрПРОГ-2000 (Київ, 2000) і УкрПРОГ-2004 (Київ, 2004), науково-практичній конференції “Інформаційні технології в освіті та управлінні” (Н. - Каховка, 2005, 2006), семінарах наукової ради НАН України з проблеми “Кібернетика” та семінарах кафедри інформаційних технологій ХНТУ.

Публікації. За темою дисертації опубліковано 10 друкованих праць у виданнях, що входять у перелік ВАК України.

Структура та обсяг роботи. Зміст дисертаційної роботи викладено на сторінках машинописного тексту, що складається зі вступу, чотирьох розділів, висновків і додатків. У роботі подано 4 таблиці, 25 рисунків, 5 додатків. Список використаних джерел включає 100 робіт, в тому числі 4 іноземних авторів.

Основний зміст роботи

У вступі обґрунтовано актуальність роботи, сформульовані мета та завдання досліджень, наведені одержані результати, характеризуються їх наукова новизна і практична цінність, а також наведено зв'язок роботи з науковими програмами, планами, темами.

У першому розділі розглянуті сучасні, що засновані на знаннях, методи синтезу КС, зокрема, індуктивний, дедуктивний та трансформаційний. Основна увага приділяється трансформаційним методам синтезу, що активно розвиваються у вітчизняній та світовій наукових школах. Підкреслюється плідність діалогових алгебро-граматичних формалізмів, в термінах яких може бути отримана одна із можливих реалізацій загальної ідеї трансформаційного синтезу. В результаті проведеного аналізу сформульовано об'єкт, предмет, мету, задачі та методи дослідження.

У другому розділі розглянуто апарат універсальних та багатоосновних алгебр, формальних мов та граматик, абстрактних автоматів та дискретних перетворювачів інформації. Основна увага приділяється абстрактно-автоматній моделі кібернетичної системи (АМКС), яка є композицією двох автоматів: керуючого (КА) та операційного (ОА). На АМКС базується також абстрактна модель керування (АМК), в якій втілене, зокрема, фундаментальне для кібернетики поняття зворотного зв'язку. При різних припущеннях стосовно КА та ОА така модель допускає різноманітні інтерпретації: машина Тьюрінга, алгоритм і інформація, яку він оброблює, пристрій керування комп'ютера та його арифметичний пристрій, технічний об'єкт управління та керуюча комп'ютерна система у випадку АСУ та ін.

Для формалізації процесів, що протікають в АМКС, зокрема в АМК, В.М. Глушков запропонував спеціальну мову, що отримала назву систем алгоритмічних алгебр (САА). САА - це двохосновна алгебраїчна система =A, B; , що складається з пари множин A (операторів) і B (умов) з заданою на них сигнатурою операцій . Над множиною A визначені операції композиція, -диз'юнкція, -ітерація, а над множиною B - узагальнені бульові операції, а також операція лівого множення оператора на умову. Оператори та умови визначені на множині M, що називається інформаційною. В подальшому сигнатура САА була розширена операціями недетермінованої, синхронної та асинхронної диз'юнкцій, а також засобами синхронізації паралельних гілок. Для регулярних схем (РС) - виразів в САА та їх модифікаціях (САА-М) - розроблений апарат формальних перетворень і канонічних форм представлень.

При відповідної переінтерпретації АМКС виникає абстрактна модель даних, з якою асоціюється двохосновна алгебра структур даних (САА-М/СД) <О, В; >, де О - множина об'єктів; В - множина тризначних логічних умов. В сигнатуру включаються відповідним чином проінтерпретовані операції сигнатури САА-М, а також деякі спеціальні операції над структурами даних. Апарат САА-М та САА-М/СД дозволяє формалізувати поняття абстрактного типу даних (АТД) та абстрактного типу пам'яті (АТП) і відкриває можливість автоматизації рішення задач аналізу і синтезу одночасно структур керування, пам'яті і даних.

У результаті поєднання САА-М і САА-М/СД були отримані трьохосновні САА <A, B, O; >. Базис =<А₀, В₀, О₀> САА <A, B, O; >, де А₀, В₀, О₀ - сукупність базисних операторів, предикатів і об'єктів (базових типів даних) відповідно, можна трактувати як багатоосновну алгебраїчну систему =<А₀, В₀, {O_0i: iI}>, де O_0i - основи (сорти), на яких визначені операції і предикати, що входять у сигнатуру А₀В₀ системи . З базисом асоціюється граматика структурного проектування (ГСП): ^п=(S^п, V_н^п, ^п, Р^п, U^п), де S^п - термінальний алфавіт, що складається із сукупності базисних умов, операторів, об'єктів, АТД, АТП, сукупності роздільників - символів операцій сигнатури САА-М, дужок, обмежників і інших; V_н^п - нетермінальний алфавіт, якому належать метазмінні: логічні, операторні, об'єктні, АТД, АТП; ^пV_н^п - аксіома, що ідентифікує клас, який проектується; Р^п={р_i: i} - схема граматики; U^п - механізм керування виводом, що прийнятий у ^п. Множина (^п)={RS: ^пRS} РС над базисом , що виводяться в ГСП, утворює мову (S^п), асоційовану із класом програм, що проектується. ГСП може розглядатись в якості математичної моделі актуальної ПрО.

Розглянутий математичний апарат при проектуванні компонент АСУ відкриває можливість опису дискретних процесів функціонування системи у вигляді деякої “програми”, що регламентує послідовність застосування до об'єкта тих чи інших базових керуючих впливів залежно від ситуації, в якій він перебуває. Такий опис, що включає інтерпретацію керуючих впливів і логічних умов їх застосування у вигляді операторів та предикатів на деякій (інформаційній) множині, можна задавати у вигляді РС. Стани інформаційної множини моделюють можливі стани керуючого об'єкта.

Однак, спроба автоматизації процесу “витягу” з ГСП (оптимального) алгоритму для розв'язання задач даного класу наштовхується на фундаментальні труднощі, пов'язанні з алгоритмічною нерозв'язністю. Один із шляхів подолання цієї проблеми дає концепція діалогових обчислень, що формулюється як процедура пошуку “рішення” модифікованої проблеми розпізнавання виводимості. Одну з можливих реалізацій концепції отримують шляхом збагачення апарату САА-М засобами діалогових обчислень: операцією діалогового вибору

ДВ(В₁  В₂ ... В_n)  D_(n+1) * В (₁В₁, ₂В₂, ..., _nВ_n) D_(n+1) * ,

а також її циклічним варіантом

ЦДВ(В₁ В₂ ... В_n) ДВ(В₁ В₂ ... В_n) D_(n+1)*В(₁В₁, ₂В₂, ..., _nВ_n),

де В₁, В₂, ..., В_n - оператори алгебри недетермінованих алгоритмів, яким поставлена у відповідність сукупність умов =(₁, ₂, ..., _n, _n+1); оператор D_(n+1) встановлює в діалоговому режимі значення “істина” одного і значення “помилка” інших умов із сукупності , при цьому mM D_(n+1)(m)=m.

Для моделювання алгоритмів, що допускають можливість повернень у попередні за часом елементи обробки обчислювального середовища M, вводиться оператор ПОВЕРНУТИСЯ, що визначається над історією h(t), t= 0, 1, 2, … обчислення, яке виконує АМКС:

ПОВЕРНУТИСЯ(h(t))ЦДВ(КРОК НАЗАД ПО h(t) КРОК УПЕРЕД ПО h(t)).

Представлення в САА-М =<А, В; > операторів з А через елементи базису за допомогою розглянутих операцій називають діалоговими регулярними схемами (ДРС), а саму алгебру - алгеброю діалогових алгоритмів (АДА).

Для синтаксично і діалогово керованого проектування, аналізу і трансформації операторних представлень в АДА побудована алгебра діалогових гіперсхем (АДГС), базовим поняттям якої служить узагальнення АМКС - модель генератора текстів. В якості КА у даній моделі використовується магазинний автомат , а в якості ОА - автомат , що постачається двома допоміжними стрічками L і D: на cтрічці L формується послідовність операторів і/чи операцій, а стрічці D - послідовність даних, до яких ці оператори і/чи операції застосовуються. Станами операційної структури даної моделі є елементи множини М'=SL₁L₂, де S - множина станів автомата , асоційована з параметрами, що керують генерацією текстів; L₁ - множина станів стрічки L, L₂ - множина станів стрічки D. Даній моделі ставиться у відповідність САА `=<A', B', O'; `>, де А' - множина операторів на операційній структурі М'; В' - множина умов чотиризначної логіки, що представляють собою відображення множини М' у множину {0, , , 1}, де 0 - помилка, - невизначеність, - не обчислена, 1 - істина; O' - множина об'єктів. Визначаються операції ` і задається F - спосіб формування тексту, що записується на L (праворуч від уже накопиченого тексту), для суперпозицій цих операцій над операторами, для яких F заданий; завдання F<sub>1</sub> - способу формування записуваного на D тексту - аналогічно формуванню історії обчислення АМКС. Представлення операторів з A' за допомогою введених операцій з ` через утворюючі елементи (оператори, об'єкти й умови) названі регулярними діалоговими гіперсхемами (РДГС), а алгебра ` - алгеброю діалогових гіперсхем (АДГС). Кожна РДГС PA', впливаючи на стан mM' такий, що m<sup>L</sup>= і m<sup>D</sup>= породжує РС F(P, m) у САА =<A, B, O; >, що асоціюється з розглянутою моделлю генератора текстів (без вихідних стрічок). Отже, зафіксувавши РДГС P, одержимо мову (клас РС у САА ), що породжена даною РДГС: L(P)={F(P, m): mS}. Для представлення багаторівневих алгоритмів генерації операторних представлень в АДА використовується поняття АДГС-схеми, під якою розуміється послідовність рівностей , де - вираз в АДГС ` над базисом (i=0, 1, 2, ..., k); позначає оператор, а - оператор, об'єкт чи умову в АДА .

Запропонований в АДА і АДГС апарат використовується для збагачення засобів керування виводом в ГСП. З цією метою у відповідність безконтекстній ГСП ^п=(^п, V_н^п, ^п, Р^п, U^п), де Р^п={v_jw: v_jV_н^п; w(V_н^пп)^*, j=1,2,…,m} - її схема, ставиться АДГС-схема наступним чином. Згрупуємо продукції з однаковими лівими частинами і запишемо Р^п у вигляді множини рівнянь: ={f_i: v_i=w₁ⁱw₂ⁱ…w_tiⁱ, i=1, 2,…, n}, де w₁ⁱ, w₂ⁱ, …, w_tiⁱ - праві частини цих продукцій. Не обмежуючи спільності, припустимо, що v₁, v₂ ,…,v_l - операторні (v₁=^п), v_l+1, v_l+2, …, v_k - логічні, v_k+1, v_k+2, …, v_n - об'єктні метазмінні. Задамо на множині М' АДГС `=<A', B', O'; `>, а граматиці ^п поставимо у відповідність АДГС-схему, що деталізує оператор v₁:

СХЕМА V1; ЦДВ( v₁=ЦДВ(, , …, );

v₂=ЦДВ( , , …, ); … v_l=ЦДВ(, , …,);

v_l+1=ЦДВ(, , …, );…v_k=ЦДВ(, , …,); v_k+1=ЦДВ(,,…,);...v_n=ЦДВ(,,…,)) ПОВЕРНУТИСЯ(h(t)); ДВ(Q₁ Q₂ ... Q_h)); КІНЕЦЬ СХЕМИ;,

де (i=1, 2, …, l, k+1, k+2, …, n) - відповідним чином модифіковані вирази , що входять у f_i; Q_i (i=1, 2, …, h) - оператори, дія яких складається в перевірці умов _iB' (i=1, 2, …, h) на стані mS, що виникає на і-му кроці роботи діалогово-параметричної моделі генератора текстів і видачі (на екран дисплея) відповідних значень.

Застосувавши САА/Д-схему V1 до деякого стану m=(m, , )М', одержимо на стрічці L РС F(V1, m) таку, що F(V1, m)A і F(V1, m)(^п). При цьому АДГС-схема V1 еквівалентна (в розумінні породження мови) граматиці ^п, тобто (V1)={F(V1, m): mМ'}=(^п).

АДГС-схеми, аналогічні побудованій вище АДГС-схемі v₁, називають АДГС-схемами, що відповідають заданим граматикам, чи, коротко, АДГС-схемами граматик. ГСП, збагачені апаратом виводу АДГС-схем граматик, називають діалоговими ГСП.

На основі введених вище понять формулюється поняття трансформаційного зведення. Кажуть, що схема F трансформаційно зводиться до схеми G, якщо існує вивід G із F, на кожному кроці якого застосовується одне із діалогових метаправил: конкретизація (згортка, розгортка або їх сполучення), переінтерпретація чи застосування співвідношення. В дисертаційній роботі в якості F розглядається аксіома ГСП, а в якості G - алгоритм, який необхідно спроектувати.

Автоматизація процесу трансформаційного зведення вимагає створення відповідного інструментарію, який отримав назву діалогової трансформаційної машини.

В третьому розділі розглянуті принципи побудови ДТМ. Підкреслюється, що в даній роботі прийняте представлення алгоритмічних знань за допомогою САА/Д-схем - описів алгоритмів у мові САА/Д, яка базується на зображувальних засобах АДА і є вхідною для ДТМ. У якості абстракцій операторів (перетворювачів даних) і умов (предикатів) у мові використовуються змістовні ідентифікатори - тексти українською чи будь-якою іншою ПМ. Абстрактні оператори й умови підрозділяються на елементарні і складові. Елементарні оператори й умови є первинними абстракціями. В мові САА/Д елементарні оператори й умови дозволяють подальше розбиття на складові частини, кожна з яких має визначену інтерпретацію: поняття ПрО, операція над поняттям, уточнення операції та ін., а також введення параметрів. Складовий оператор (умова) будується з елементарних за допомогою керуючих конструкцій мови САА/Д. Текст у мові САА/Д представляє собою послідовність рівностей. Кожна із рівностей засобами САА/Д конкретизує абстракцію деякого складеного оператора (умови), змістовний ідентифікатор якого (якої) присутній в одній з попередніх рівностей. Інтерпретація первинних абстракцій може бути різною. Тим самим відкривається можливість проектування схем (моделей) цілих класів алгоритмів, які ідентичні по способу запису і відрізняються лише інтерпретацією абстракцій, що входять в цей запис. Якщо в САА/Д-схемі замінити змістовні ідентифікатори їх кодами, то ми отримаємо компактний вираз - формулу САА/Д-схеми, до якої більш зручно застосовувати співвідношення.

Абстрактні оператори в САА/Д-схемі виконують деякі дії над об'єктами базових, структурованих або агрегатних типів. Структуровані та агрегатні типи будуються з базових типів за допомогою, можливо кількаразового, застосування способів конструювання.

В ДТМ для трансляції САА/Д-схем в програми на цільовій МП використовується розроблена в дисертації технологія шаблонів з параметрами, що дозволяє встановити динамічно, в процесі проектування САА/Д-схем, однозначну відповідність між САА/Д-схемами і асоційованими з ними програмами. Шаблони задаються для кожної синтаксичної одиниці цільової МП: програми в цілому, головної функції (процедури) програми, функцій користувача, керуючих конструкції, декларацій змінних та ін. В дисертаційній роботі в якості прикладу розглядаються шаблони для трансляції САА/Д-схем в програми на цільовій МП С++. Зокрема, відомо, виконання програми на C++ починається з функції main, тому шаблон для першого складеного оператора САА/Д-схеми має вигляд: int main() {%v %b; return 0;}, при цьому параметр %v буде замінено на декларації змінних, що використовуються в цьому операторі, %b - на відтрансльований текст оператору. Для об'єктів агрегатного типу “Масив” шаблон має вигляд:

%t %n[%a] 1 Число розмір масиву

%n[%a] 2 Число індекс елементу,

де перший рядок задає правила конструювання масиву, другий - елементу масиву, при цьому параметр %t буде замінено на тип елементів масиву, %n - на ім'я масиву, %a для першого рядка - на розмір масиву, для другого - на індекс елементу. Шаблон також визначає, що параметр масиву має назву “розмір масиву” і є константою типу “Число”, а параметр елемента масиву має назву “індекс елементу” і є змінною типу “Число”.

Шаблон оператору діалогового вибору має вигляд:

{ const char *menuDV[] = {%l}; choice = getChoice(menuDV, %c); %f },

де параметр %l - замінюється на список змістовних ідентифікаторів операторів, %c - кількість ідентифікаторів, %f - послідовність операторів if для обробки результату вибору користувача та виклику реалізації відповідного оператору. Діалогові оператори реалізовані таким чином, що під час виконання такого оператора у програмі на МП користувачу демонструється спеціальне меню, за допомогою якого він визначає, який з операторів має виконуватись. В якості пунктів меню використовуються змістовні ідентифікатори операторів. Кількість операторів, що утворюють діалогові оператори, а, відповідно й пунктів меню, завчасно не визначена й визначається проектувальником під час формування діалогового оператора в тексті САА/Д-схеми (див. розділ 4). Вигляд меню залежить від інтерфейсу користувача операційної системи, в якій виконується програма. Для побудови меню використовується спеціально розроблена функція, наприклад, для мови С++ - це функція getChoice. Ця функція в якості аргументів отримує список змістовних ідентифікаторів операторів, що входять в діалогові оператори. Результатом роботи функції є номер обраного користувачем оператору, який оброблюється фрагментом програми, що конкретизує параметр %f.

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

Запропонована технологія параметризованих шаблонів є досить гнучкою і дозволяє підключати до ДТМ довільні процедурні МП.

ДТМ може розглядатися як різновид систем знань. Структура ДТМ представлена на рис. 1. Ядро ДТМ складають БЗ і МВ. ДТМ підтримує наступне представлення про рішення задач у ПрО: користувач формулює розв'язувану задачу у вигляді мети - речення визначеної формалізованої моделі ПрО і намагається досягти цієї мети, застосовуючи знання, представлені в БЗ ДТМ. Представлення розглянутого вище процесу рішення задач зумовило необхідність реалізації символьного виводу, що реалізується компонентою МВ ДТМ - інтелектуальним редактором. В ІР входить, зокрема, блок формування змістовних ідентифікаторів елементарних та складених операторів й умов. ДТМ зберігає частини змістовних ідентифікаторів елементарних операторів і умов в БЗ у вигляді дерева відповідних словників понять (у вершині кожного з таких дерев знаходиться поняття ПрО - ім'я відповідного АТД), а блок надає техніку маніпулювання цими словниками (див. розділ 4); у результаті таких маніпуляцій різні розробники для одних і тих цілей сформують ті ж самі ідентифікатори. Наявність словників понять у ДТМ і відповідної техніки маніпулювання ними дозволяє вводити кожне поняття тільки один раз, а потім використовувати його в процесі проектування САА/Д-схем у різних контекстах, що значно збільшує продуктивність праці програміста. Інший блок ІР - блок керування змінними - використовується для діалогового формування синтаксично правильних описів об'єктів АТД. Результатом роботи редактору є синтаксично привільні САА/Д-схеми та асоційовані з ними програми.

Рис. 1. Структура ДТМ

Для підтримки спіральної моделі ЖЦ КС в ІР закладено можливість повернення на попередні етапи проектування САА/Д-схем з метою корегування прийнятих рішень й вибору іншого напрямку розв'язання задачі. Ця можливість реалізується за рахунок ведення протоколу (історії) проектування САА/Д-схеми, формули САА/Д-схеми й тексту програми на цільовій МП.

ДТМ також дозволяє виконувати трансформацію існуючої САА/Д-схеми з однієї ПрО в іншу. Для цих ПрО необхідно забезпечити однакові множини змістовних ідентифікаторів елементарних операторів і умов та їх кодів, але різні реалізації на цільових МП. Зазначена можливість дозволяє отримувати по одній і тій же САА/Д-схемі програми в різних МП, або, при проектуванні апаратних засобів комп'ютерів, розробляти їх моделі у вигляді САА/Д-схем та відповідних їм програм, а після отримання бажаних властивостей алгоритмів роботи операційних пристроїв автоматично отримувати їх специфікації, що сприяє економії часу і зменшує вартість розробки.

ДТМ використовує у своїй роботі чотири стрічки: для запису САА/Д-схеми, для запису САА/Д-формули, для запису тексту шаблону програми, для запам'ятовування історії проектування САА/Д-схеми. Кожна стрічка містить ланцюжок термінальних і нетермінальних символів, а також спеціальні маркери: початку (?) і кінця () ланцюжка. Уздовж стрічки переміщується спеціальний покажчик, який записує на стрічку символи, що залежать від дій користувача. Робота ДТМ описується наступною ДРС:

ДТМ = ДВ(НС | СС | ТР) * { ЦДВ(ЗК | ЗЕО | ЗСО | ВМ | ЗМ | ПІ)}_d() * ФП * ЗС*(ФС E),

де НС - оператор запису на стрічки шаблона нової САА/Д-схеми;

СС - оператор вибору і запису на стрічки існуючої САА/Д-схеми;

ТР - оператор трансформації існуючої САА/Д-схеми з однієї ПрО в іншу;

ЗК - оператор вибору і запису на стрічки конструкції САА/Д;

ЗЕО - оператор формування і запису на стрічки елементарного оператора;

ЗСО - оператор формування і запису на стрічки складеного оператора;

ЗМ - оператор уведення мітки і запису її на стрічки;

ПІ -оператор перегляду історії формуванні САА/Д-схеми;

d() - умова, що має значення “істина” в момент, коли маркер виявляється безпосередньо праворуч від покажчика;

ФП - оператор формування тексту програми на МП по її шаблону;

ЗС - оператор запису САА/Д-схеми, САА/Д-формули, шаблону тексту програми на МП, програми, протоколу формування схеми в відповідні файли;

- умова, що приймає значення “істина” при проектуванні операційних пристроїв (ОП);

ФС - оператор формування специфікацій ОП;

E - тотожний оператор.

Блоки генерації специфікацій та командного файлу для системи PCAD є допоміжними й використовуються при проектуванні апаратного забезпечення КС.

У четвертому розділ описується програмна реалізація розробленого інструментарію. Можливості ДТМ по синтезу програмного й апаратного забезпечення КС демонструються на ряді прикладів.

Розроблений інструментарій складається з додатків Windows - ДТМ (ІР та БЗ) та системного редактора для модифікації БЗ, а також допоміжних утиліт для генерації файлів специфікації пристрою по САА/Д-схемі роботи цього пристрою.

Головне вікно ДТМ складається з трьох областей: рядка головного меню, робочої області, яка містить текст САА/Д-схеми, що проектується, та діалогових вікон, за допомогою яких виконується формування схеми.

Головне меню ДТМ складається з наступних основних пунктів. Пункт “Проект” містить команди для відкриття нового або існуючого проекту САА/Д-схеми; роздрукування тексту схеми на принтері; виконання перетрансляції схеми в іншу ПрО, тобто генерації по тексту схеми нового тексту програми на цільовій МП в новій ПрО; завершення роботи з ДТМ. Пункт “Предметна область” містить команди для підключення до БЗ ДТМ знань з ПрО, для якої планується розробляти КС та настройки окремих параметрів БЗ, наприклад, каталогів, в яких знаходиться БЗ та ін. В пункті “Історія” знаходяться команди для роботи з історією формування САА/Д-схеми, зокрема, перегляду та повернення на попередні етапи. Пункт “Транслятор” містить команди для настройки зовнішнього транслятора для цільової МП та трансляції спроектованої програми.

Процес проектування САА/Д-схеми полягає у відповідях користувача на запитання ДТМ про тип поточного нетермінального символу. В процесі формування тексту схеми нетермінальні символи #P та #Q замінюються ідентифікаторами операторів (елементарних та складених), #R та #S - ідентифікаторами елементарних та складених умов. При створені нового проекту в робочій області розміщується початкова САА/Д-схема, що складається з одного складеного оператора, назва якого збігається з назвою схеми, і який має один нетермінальний символ.

Розглянемо в якості прикладу кілька кроків процесу проектування САА/Д-схеми для обчислення всіх параметрів трикутна (довжина сторін, значення кутів, периметр та площа) по частині відомих параметрів. Припустимо, що БЗ містить всі необхідні знання, зокрема, поняття “Рядок <ім'я>”, над яким визначена операція “вивести” з уточненнями “на екран” та “в файл”. Після створення нового проекту текст САА/Д-схеми буде мати вигляд:

СХЕМА Розв'язання трикутників:

"Розв'язання трикутників"===( #P )

КІНЕЦЬ СХЕМИ;

Для уточнення нетермінального символу (в даному випадку #P) використовується діалогове вікно з варіантами: “КОНСТРУКЦІЄЮ САА/Д”, “ЕЛЕМЕНТАРНИМ”, “СКЛАДЕНИМ”. При виборі “КОНСТРУКЦІЄЮ САА/Д” відкривається вікно, у якому перераховані основні конструкції мови САА/Д - операторні та логічні і, після вибору деякої конструкції, вона автоматично підставляється в текст САА/Д-схеми для наступного уточнення операторів і/чи умов, що містяться в ній. При виборі “ЕЛЕМЕНТАРНИМ” відкривається спеціальне діалогове вікно для вибору найменування АТД, вибору існуючої або створення нової змінної даного типу та формування змістовного ідентифікатора елементарного оператора чи умови з використанням відповідної змінної. Якщо проектувальник вибрав варіант “СКЛАДЕНИМ”, то ДМТ за допомогою відповідного діалогового вікна запропонує йому ввести ідентифікатор складеного оператора чи умови. Після введення названого ідентифікатора в кінець САА/Д-схеми додається нова рівність. Для нашого прикладу зробимо вибір “КОНСТРУКЦІЄЮ САА/Д”, а в підменю “P*Q”. Текст схеми прийме вигляд:

СХЕМА Розв'язання трикутників:

"Розв'язання трикутників"===( #P * #Q)

КІНЕЦЬ СХЕМИ;

Для уточнення метасимволу #P зробимо вибір “ЕЛЕМЕНТАРНИМ”, в діалоговому вікні для керування змінними виберемо “Рядок”, а в якості імені рядку сформуємо константу “Виберіть варіант рішення:”. Далі ІР відкриває вікно з змістовними ідентифікаторами операцій над АТД “Рядок”. Після вибору ідентифікатора “вивести” у вікні з'являються його уточнення. В результаті вибору уточнення “на екран” ІР сформує речення "Рядок "Виберіть варіант рішення:" вивести на екран". Для уточнення метасимволу #Q робимо вибір “КОНСТРУКЦІЄЮ САА/Д”, потім “Діалоговий Вибір”. Після цих дій ДТМ переходить в режим формування діалогових операторів (див. розділ 3). В цьому режимі за допомогою діалогового вікна проектувальник має можливість вводити необхідні змістовні ідентифікатори операторів, що утворюють діалоговий оператор. Після формування оператора діалогового вибору, що складається з трьох складених операторів, САА/Д-схема буде мати вигляд:

СХЕМА Розв'язання трикутників:

"Розв'язання трикутників"===(

"Рядок "Виберіть варіант рішення:" вивести на екран"*

Діалоговий Вибір( "Рішення по трьом сторонам" |

"Рішення по двом сторонам та куту між ними" |

"Рішення по стороні та прилеглим кутам" )

)

"Рішення по трьом сторонам"===( #P )

"Рішення по двом сторонам та куту між ними"=== ( #P )

"Рішення по стороні та прилеглим кутам"===( #P )

КІНЕЦЬ СХЕМИ;

Відповідний складеному оператору "Розв'язання трикутників" фрагмент програми буде мати вигляд:

int getChoice(char **menuDV, int count)

{int i; printf("Виберіть пункт:\n"); for(i = 0; i < count; i++) printf("d. s\n", i + 1, menuDV[i]); scanf("d", &i); return i;}

main()

{ puts("Виберіть варіант рішення:");

{ int choice;

const char *menuDV[] = {"Рішення по трьом сторонам", "Рішення по двом сторонам та куту між ними", "Рішення по стороні та прилеглим кутамам" };

choice = getChoice(menuDV, 3);

if( choice == 1 ) procB1(); else if( choice == 2 ) procB2(); else procB3(); } }

Далі послідовно уточнюємо складені оператори “Рішення по трьом сторонам”, “Рішення по двом сторонам та куту між ними”, “Рішення по стороні та прилеглим кутам”. Процес проектування САА/Д-схеми закінчується після того, як в тексті схеми не залишиться жодного метасимволу. В результаті проектування в ДТМ створюються файли: тексту САА/Д-схеми, формули САА/Д-схеми, тексту програми на цільовій МП, а також допоміжні файли історії формування проекту, списків відповідності змістовних ідентифікаторів складених операторів та умов та їх кодів, та інші.

ДТМ може функціонувати в режимі перегляду історії формування САА/Д-схеми. В цьому режимі за допомогою спеціального діалогового вікна користувач має змогу рухатися по історії формування назад і вперед і, при необхідності, зупинятися на одному з попередніх етапів. ДТМ переключається в режим перегляду історії при виборі відповідної команди головного меню.

Системний редактор використовується для наповнення БЗ новими знаннями про ПрО, а також для модифікації існуючих.

При проектуванні апаратного забезпечення комп'ютерів з САА/Д-схемою функціонування пристрою асоціюється спеціальна допоміжна програма на МП. Результати роботи цієї програми використовуються утилітою sintez, яка в залежності від заданого типу керуючого автомату (Мілі або Мура) та типу елементів пам'яті (RS-, JK-, D- або T-тригер) генерує специфікацію пристрою, зокрема бульові функції збудження елементів пам'яті та виходів керуючого автомату, що поступають на вхід операційного автомату. По отриманій специфікації утиліта gencmd створює для системи проектування схем радіоелектронної апаратури PCAD командний файл для створення схеми електричної принципової та ескізу печатної плати пристрою. Для відлагодження й аналізу отриманих в процесі проектування схем ОП використовується система схемотехнічного моделювання Electronics Workbench.

В додатках наведено: фрагменти розроблених БЗ “Програмування” та “Проектування операційних пристроїв”, приклади програмного забезпечення комп'ютерів, фрагмент програмної реалізації ДТМ, акти впровадження результатів дисертаційного дослідження.

Висновки

Дисертаційна робота присвячена розробці інструментальних засобів для побудови універсальних та спеціалізованих комп'ютерних систем. Метою дослідження була розробка на основі діалогових алгебро-граматичних моделей представлення знань інструментарію проектування програмних і апаратних компонент АСУ.

В результаті дисертаційного дослідження отримано наступні результати:

1. На основі проведеного аналізу обґрунтовано використання для синтезу КС діалогових алгебро-граматичних методів, які поєднують алгебраїчні, логічні та граматичні формалізми та орієнтовані на багаторівневе структурне проектування, трансформацію і синтез класів схем алгоритмів і програм (послідовних, паралельних, недетермінованих, діалогових), а також визначених класів апаратури.

2. Вхідна мова ДТМ була розширена засобами діалогової взаємодії користувача й комп'ютерної системи, що проектується. Використання мови проектування САА/Д, що є близькою до природної, дозволяє формувати легкі для розуміння тексти алгоритмів, а також залучати до процесу розробки компонент АСУ безпосередньо фахівців ПрО, для якої розробляється КС. Даний підхід сприяє отриманню необхідного кінцевого результату відповідної якості в прийнятні терміни.

3. Розроблено компоненти архітектури діалогової трансформаційної машини - ІР (компонента МВ) та БЗ. ІР підтримує діалоговий символічний вивід синтаксично правильних САА/Д-схем та асоційованих з ними програм і специфікацій відповідних класів апаратури, на мові, яка наближена до природної, що значно прискорює процес розробки КС.

4. Розроблені механізми підключення довільних процедурних мов, що забезпечує отримання для САА/Д-схем програм на цільових МП, а також відповідні алгоритми та програмні модулі ДТМ. Методика підключення цільових МП є універсальною, що дозволяє використовувати в кожному конкретному випадку найбільш доцільну мову.

5. Розроблено алгоритми та програмні модулі ДТМ для ведення історії формування САА/Д-схем, що забезпечують підтримку спіральної моделі ЖЦ КС. Таким чином, розробник має можливість повертатися на попередні етапи проектування й оперативно вносити необхідні зміни в проект, що розробляється.

6. Розроблено алгоритми й інструментальні засоби для одержання по САА/Д-схемі специфікацій пристрою, що реалізує даний алгоритм, зокрема, розроблено алгоритми та відповідні програмні модулі для трансформації САА/Д-схем з однієї ПрО в іншу. Такий підхід дозволяє при проектуванні апаратних засобів КС розробляти їх моделі у вигляді САА/Д-схем та відповідних їм програм, а після отримання бажаних властивостей алгоритмів роботи операційних пристроїв автоматично отримувати їх специфікації, що сприяє економії часу і вартості розробки.

7. Розроблено структуру БЗ для представлення і підключення знань для широкого класу КС, а також відповідне алгоритмічне і програмне забезпечення для супроводу і модифікації БЗ.

8. Здійснено наповнення БЗ знаннями для синтезу визначених класів програмного й апаратного забезпечення компонент АСУ.

Обґрунтованість висновків та рекомендацій, наведених у роботі, підтверджується практичним впровадженням результатів дисертаційних досліджень, зокрема, в ТОВ “Сонар”, а також у навчальному процесі кафедри інформаційних технологій ХНТУ.

СПИСОК ОПУБЛІКОВАНИХ ПРАЦЬ ЗА ТЕМОЮ ДИСЕРТАЦІЇ

1. Петрушенко А.Н., Хохлов В.А. Диалоговая трансформационная машина как инструментарий прототипирования программных изделий со спиральной моделью жизненного цикла // Вестник Херсонского государственного технического университета. - 1997. - № 2. - С. 144-148.

Здобувачем запропоновано реалізацію інтелектуального редактора - компоненти машини виводу діалогової трансформаційної машини, а також механізми підтримки спіральної моделі ЖЦ КС.

2. Петрушенко А.Н., Хохлов, В.А. Ткачев И.В. Автоматизация проектирования управляющих автоматов с жесткой логикой // Автоматика. Автоматизация. Электротехнические комплексы и системы. - 1999. - №1. - С. 80-86.

Здобувачем запропоновано реалізацію алгоритмів синтезу керуючого автомата по САА/Д-схемі алгоритму, а також розроблені відповідні програмні модулі.

3. Петрушенко А.Н., Хохлов В.А. Об использовании естественного языка для представления абстрактных типов данных и полиморфизма // Проблемы программирования. - 1999. - №1. - С. 136-143.

Здобувачем запропоновано алгоритм підключення до мови САА/Д цільових МП і виконана розробка відповідного інструментарію.

4. Петрушенко А.Н., Хохлов В.А. Пример синтеза в диалоговой трансформационной машине САА/Д-схемы и реализующих ее программы и управляющего автомата операционного устройства // Вестник Херсонского государственного технического университета. - 1999. - № 3. - С. 440-443.

Здобувачем запропоновано алгоритм одержання по однієї і тієї ж САА/Д-схемі алгоритму асоційованої зі схемою програми і керуючого автомата операційного пристрою, що реалізує даний алгоритм. Також розроблені необхідні програмні модулі.

5. Петрушенко А.Н., Хохлов В.А., Шепетухин Е.С. Об автоматизации проектирования некоторых классов операционных устройств // Вестник Херсонского государственного технического университета. - 2000. - №9. - С. 196-201.

Здобувачем запропоновано методику синтезу I-автоматів по САА/Д-схемі алгоритму роботи пристрою.

6. Хохлов В.А. Интеллектуальный редактор: об одной реализации диалогового проектирования схем обработки некоторых классов типов данных // Вестник Херсонского государственного технического университета. - 2000. - №9. - С. 202-205.

7. Петрушенко А.Н., Хохлов, В.А., Ткачев И.В., Шепетухин Е.С. Диалоговая трансформационная машина: некоторые функциональные возможности // Проблемы программирования. - 2000. - №1-2. - С. 323-334.

Внесок співавторів:

Петрушенко А.Н. - постановка проблеми, аналіз аспектів побудови ДТМ;

Хохлов В.А - запропоновані методи підтримки спіральної моделі ЖЦ КС, динамічного формування абстрактних типів даних;

Ткачев И.В., Шепетухин Е.С. - розроблені необхідні програмні модулі.

8. Петрушенко А.Н., Хохлов, В.А., Шепетухин Е.С. Основная задача программирования и синтез операционных устройств// Вестник Херсонского государственного технического университета. - 2001. - №1(10). - с.216-221.

Здобувачем розроблені модулі ДТМ для синтезу операційних пристроїв.

9. Петрушенко А.М., Хохлов В.А., Шепетухін Є.С. Про розширення вхідної мови діалогової трансформаційної машини засобами проектування діалогових алгоритмів і програм. // Вестник Херсонского государственного технического университета. - 2002. - № 3 (16). - С. 234-239.

Здобувачем запропоновані алгоритми реалізації діалогових операторів та алгоритми трансляції введених операторів в цільову МП.

10. Петрушенко А.М., Хохлов В.А., Петрушенко І.А. Про підключення до мови САА/Д - вхідної мови діалогової трансформаційної машини - засобів паралельного програмування пакету МРІСН // Автоматика. Автоматизация. Электротехнические комплексы и системы. - 2006. - № 1 (16). - С. 91-94.

Здобувачем запропоновані алгоритми реалізації та трансляції на цільову МП операцій синхронної та асинхронної диз'юнкції засобами бібліотеки MPICH.

анотація

Хохлов В.А. Інструментарій проектування комп'ютерних систем на основі діалогових алгебро-граматичних моделей представлення знань. - Рукопис.

Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 05.13.16 - автоматизовані системи управляння та прогресивні інформаційні технології. - Херсонський національний технічний університет, Херсон, 2006.

Дисертаційне дослідження присвячене проблематиці розробки на основі діалогових алгебро-граматичних моделей представлення знань інструментальних засобів для побудови універсальних та спеціалізованих автоматизованих комп'ютерних систем.

Розглянуті особливості проектування комп'ютерних систем, зокрема автоматизованих систем управління, та обґрунтоване використання діалогових алгебро-граматичних моделей представлення знань для їх синтезу. На основі наведених моделей розроблений інструментарій проектування комп'ютерних систем - діалогова трансформаційна машина.

Розроблені компоненти архітектури діалогової трансформаційної машини, зокрема, база знань, компонента машина виводу - інтелектуальний редактор, що реалізує символьний вивід синтаксично правильних САА/Д-схем. Вхідна мова діалогової трансформаційної машини САА/Д, що наближена до природної, розширена засобами діалогової взаємодії користувача й комп'ютерної системи, що проектується. Мова САА/Д є “відкритою знизу”, що дозволяє, зокрема, вже на ранніх стадіях проектування залучати до процесу розроби безпосередньо замовників, що сприяє отриманню компонент АСУ необхідної якості в прийнятні терміни. Розроблено алгоритми, що базуються на апараті параметризованих шаблонів, підключення до САА/Д довільних процедурних мов програмування. Запропонована технологія отримання по САА/Д-схемі роботи пристрою відповідних йому специфікацій. Розроблені методи підтримки спіральної моделі життєвого циклу комп'ютерних систем.

...