Інтелектуальні методи синтезу семантичних моделей програм

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

Харківський національний університет радіоелектроніки

УДК 004.89:004.423.4

АВТОРЕФЕРАТ

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

Інтелектуальні методи синтезу семантичних моделей програм

05.13.23 - системи та засоби штучного інтелекту

Лещинська Олена Леонідівна

Харків - 2009

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

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

Науковий керівник: кандидат технічних наук, доцент Дюбко Геннадій Федорович, Харківський національний університет радіоелектроніки, професор кафедри програмного забезпечення ЕОМ.

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

доктор технічних наук, професор Кучеренко Євген Іванович, Харківський національний університет радіоелектроніки, професор кафедри штучного інтелекту;

доктор технічних наук, професор Серков Олександр Анатолійович, Національний технічний університет «Харківський політехнічний інститут», завідувач кафедри систем інформації.

Захист відбудеться « 27 » травня 2009 р. о 13 годині на засіданні спеціалізованої вченої ради Д 64.052.01 у Харківському національному університеті радіоелектроніки за адресою: 61166, м. Харків, пр. Леніна, 14.

З дисертацією можна ознайомитися у бібліотеці Харківського національного університету радіоелектроніки за адресою: 61166, м. Харків, пр. Леніна, 14.

Автореферат розісланий « 24 » квітня 2009 р.

Вчений секретар спеціалізованої вченої ради С.Ф. Чалий

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

Актуальність теми. Сучасний етап розвитку теоретичних та прикладних досліджень в галузі розробки програмного забезпечення (ПЗ) характеризується зростанням уваги до процесів синтезу моделей програм. Впровадження таких процесів у виробництво покликане поставити у відповідність промислові спроможності компаній-розробників ПЗ та постійно зростаючий попит на створення та супровід програм, який стає все важче задовольняти широко застосованою автоматизацією рутинних задач. Серед важливих результатів цього напрямку досліджень слід зазначити: створення консорціумом OMG методології «розробки ПЗ, що керується моделлю», створення стандартів високорівневого моделювання та документування програм, таких як UML, BPMN та ін.; розвиток дослідницьких концепцій «фабрик ПЗ» та «корпоративної пам'яті»; створення мов формальної специфікації програм, таких як Object-Z, Event-B, та заснованих на них методів верифікації формалізованих моделей програм на основі класичних та нестандартних (наприклад, темпоральних) логік, методів автоматичного доведення теорем, методів моделювання поведінки моделей програм на основі абстрактних машин, онтологічної моделі подання знань в інтелектуальних системах. Вагомий внесок у розвиток методів, що можуть бути використані для синтезу моделей програм, внесли такі вчені як: С.М. Авдошин, А.А. Шалито, В.В. Кулямін, Т.А. Гаврилова, Г.Ф. Дюбко, О.Ю. Шевченко, S. Russel, T. Nipkow, C. A. R. Hoare, J.-R. Abrial, W. Dijkstra, B. Meyer, F. Rossi, J. Cabot, C. Fischer, Charles L. Forgy.

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

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

Зв'язок теми дисертації з планами наукових робіт. Дисертаційна робота виконувалася у Харківському національному університеті радіоелектроніки на кафедрі програмного забезпечення ЕОМ відповідно до плану НДР університету в межах розділу № 200-5 «Розробка моделей та методів для забезпечення внутрішнього моніторингу якості підготовки фахівців у Харківському національному університеті радіоелектроніки» д/б теми №200 «Методи та технології створення інформаційно-освітнього середовища з метою інтеграції у загальноєвропейський простір вищої освіти» (№ ДР0106U003152, акт впровадження від 07.10.2008 р.), в якій здобувач О.Л. Лещинська взяла участь як виконавець, а також відповідно до індивідуальних планів роботи стажиста-дослідника та аспірантської підготовки. Дослідження, проведені у дисертаційній роботі, є природним продовженням робіт авторів Г.Ф. Дюбко, О.Ю. Шевченка, С.М. Авдошина, В.В. Куляміна, C. Fischer, J. Cabot та ін.

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

Поставлена мета роботи обґрунтувала такі задачі дослідження:

?розробка методу синтезу формальних моделей комп'ютерних програм на основі семантичних анотацій їх елементів;

?удосконалення формальних моделей подання комп'ютерних програм для забезпечення можливостей їх семантичного аналізу;

?удосконалення методу семантико-синтаксичного аналізу формальної мови для уніфікації розбору мов подання семантичних моделей програм;

?розробка методу перевірки здійсненності семантичних моделей програм;

?розробка методу навчання інтелектуальної системи синтезу семантичних моделей програм;

?розробка структури онтології для системи синтезу моделей програм;

?розробка модулів прототипу системи синтезу моделей програм.

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

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

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

Наукова новизна отриманих результатів. У процесі розв'язання поставлених задач отримано такі наукові результати:

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

2) набула подальшого розвитку модель, що формалізує семантику комп'ютерних програм, яка відрізняється від існуючих урахуванням семантичних анотацій, що задають призначення анотованих елементів моделі, вимоги до їх поведінки та рекомендації про використання анотованих елементів у різних контекстах, що дало можливість синтезувати запропоновані семантичні моделі програм на основі анотацій їх елементів та проводити верифікацію їх здійсненності;

3) набув подальшого розвитку метод семантико-синтаксичного аналізу формальної мови, який, на відміну від існуючих, об'єднує етапи синтаксичного та семантичного аналізу на основі багатокомпонентної моделі такої мови та уніфікує процес створення аналізаторів формальних мов як з текстовим, так і з графовим синтаксисом, що дозволило формалізувати та уніфікувати перевірку коректності структури запропонованих семантичних моделей програм;

4) набув подальшого розвитку метод перевірки здійсненності формальної моделі програми, який, на відміну від існуючих, містить у собі етапи побудови та розв'язання задачі задоволення обмежень у фіксованому домені на основі семантичних анотацій її поведінкових елементів, що дозволило проводити формальну верифікацію поведінкової складової запропонованих семантичних моделей програм;

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

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

Модулі прототипу впроваджено у виробничий процес на ТОВ «КОДА» (м. Харків, Україна), акт впровадження від 2.12.2008 р. У Харківському національному університеті радіоелектроніки результати дисертаційної роботи впроваджено у навчальний процес, акт впровадження від 5.11.2008 р. на кафедрі ПЗ ЕОМ у дисциплінах «Формальні методи програмної інженерії» та «Проектування трансляторів».

Особистий внесок здобувача. Усі результати дисертації отримано автором особисто. В [5] розроблено та в [9] описано практичну апробацію: інтелектуального методу синтезу семантичних моделей програм; удосконаленого методу перевірки здійсненності формальної моделі програми; удосконаленого методу машинного навчання з підкріпленням. В [3] удосконалено діаграми подання комп'ютерних програм та в [4] на їх основі розроблено модель, що формалізує семантику комп'ютерних програм з використанням семантичних анотацій її елементів, які задають призначення анотованих елементів моделі, вимоги до їх поведінки та рекомендації про використання анотованих елементів у різних контекстах. В [1] та тезах доповідей [10] розроблено багаторівневу граматику - фрагмент багатокомпонентної моделі формальної мови для опису текстового синтаксису та заснований на ній метод синтаксичного аналізу. В [8] розроблено типізовану плекс-граматику - фрагмент багатокомпонентної моделі формальної мови для опису графового синтаксису та заснований на ній метод синтаксичного аналізу. В [7] та тезах доповідей [11] розроблено спосіб внутрішнього подання моделі синтаксису формальної мови, що спрощує її повторне використання. В [2] та тезах доповідей [12] розроблено онтологічну модель подання семантики формальної мови, яка використовується на етапі пошуку семантичного еквівалента синтезованого нетерміналу в методі семантико-синтаксичного аналізу вхідної конструкції. В [6] та тезах доповідей [13] розроблено метод семантико-синтаксичного аналізу формальної мови на основі її багатокомпонентної моделі.

Апробація результатів дисертації. Основні результати дисертаційної роботи доповідалися та обговорювалися на конференціях: 1) 7-й, 8-й та 9-й Міжнародний молодіжний форум «Радіоелектроніка та молодь в XXI сторіччі» (м. Харків, квітень, 2003, 2004, 2005 р.); 2) Міжнародна наукова конференція «Горизонти прикладної лінгвістики та лінгвістичних технологій» (м. Партеніт, 22 - 28 вересня 2008 р.).

Публікації. За результатами досліджень опубліковано 13 робіт, з них 9 - статті у наукових спеціалізованих виданнях, згідно з «Перелік № 1,2,5,9,12,16 наукових фахових видань України…», 4 - матеріали конференцій.

Структура й обсяг дисертаційної роботи. Дисертаційна робота складається із вступу, п'яти розділів, висновків та додатків, обсяг основного тексту складає 135 сторінок, в тому числі 26 рисунків, 10 таблиць, список використаних літературних джерел, що складається зі 107 найменувань, на 11 сторінках. Робота також містить 11 додатків на 41 сторінці.

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

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

Перший розділ містить огляд предметної галузі і постановку задач дисертаційного дослідження. Серед досліджуваних парадигм програмування виділено як найбільш перспективну методологію «розробки програм, керовану моделлю» (MDD), яка розглядає розробку програми, як процес поетапного синтезу її моделей від високорівневої моделі до програмного коду. Проаналізовано існуючі формальні моделі специфікації програм (Object-Z, Event-B), методи їх синтезу (індуктивний, дедуктивний та трансформаційний, «фабрики ПЗ») та верифікації (синтаксичний аналіз на основі формальних граматик для мов з текстовим та графовим синтаксисом, доведення proof obligations і т. ін.). Зазначено особливості наведених підходів, що стримують їх розвиток. Проаналізовано можливості інтелектуалізації процесів синтезу моделей програм та обґрунтовано доцільність використання для цього ідеї семантичного анотування ресурсів (концепції SemanticWeb), онтологічної моделі подання знань та відповідних їй методів логічного виводу. Наведено загальну класифікацію методів машинного навчання та виділено метод машинного навчання з підкріпленням, як найбільш природного для навчання системи синтезу моделей програм. Сформульовано постановку задач дисертаційного дослідження.

У другому розділі набула подальшого розвитку модель, що формалізує семантику комп'ютерних програм. Розроблена модель (1) формалізує опис структурних та поведінкових елементів моделей програм за допомогою семантичних анотацій:

SPM={m | m={e | e=<D,SA> \/ e=<D,D,RP>}},(1)

де m - семантично анотоване подання розроблюваної програми у вигляді однієї із створених на основі стандарту UML діаграм взаємодії агентів предметної галузі (DAC), діаграм бізнес-об'єктів у межах кожного агента (BOD), діаграм класів (CD), що уточнюють BOD-діаграми, діаграм процесів (PD), що детально описують процеси, які призначена виконувати програма, та діаграм інтерфейсу користувача (UI); e - смисловий або єднальний елемент відповідної діаграми m. Смисловий елемент визначається як кортеж e=<D,SA>, де D - припустимий вузол відповідної діаграми m; SA - семантична анотація вузла e у вигляді (2). Єднальний елемент визначається як кортеж e=<D,D,RP>, що описує позначене на діаграмі m відношення між поєднуваними елементами D та множину атрибутів RP такого відношення. Для кожної з перелічених діаграм розроблено мету-модель, яка визначає допустимі типи елементів таких діаграм та можливі відношення між ними.

Семантична анотація елемента моделі програми - це трійка:

SA=<A,C,R>,(2)

де A - анотація призначення елемента, С - специфікація вимог до поведінки елемента, R - множина формалізованих рекомендацій щодо використання анотованого елемента у різних контекстах.

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

Специфікацію вимог до поведінки елемента e моделі програми формалізовано як множину залежностей Constraints(e) так, якщо:

X_e - контекст елемента e моделі (множина доступних змінних, атрибутів, типів, методів, констант),

M_e X_e - підмножина методів з контексту ,

T={always,before,after} - множина моментів часу відносно функціонального циклу елемента моделі,

C(X_e,T) - логічний вираз над X_e, що має бути виконаний у часовому інтервалі T,

R(M_e{ANY,STOP} ,T)- регулярний вираз над M_e{ANY,STOP}, що описує часовий інтервал T, тоді :

Constraints(e)=Inv(e) Pre(e) Post(e) Trace(e) (3)

де Inv(e) - множина інваріант inv(e) компонента: inv(e) : C(X_e,always),

Pre(e) - множина передумов pre(e) виконання елемента: inv(e) : C(X_e,before), синтез комп'ютерний інтелектуальний онтологія

Post(e) - множина постумов post(e) виконання компонента:

post(e) : C(X_e,before) >C(X_e,after),

Trace(e) - дозволена траса виклику методів компонента: R(M_e,always).

Constrainst(e) виражається на розробленій в дисертації мові OQLc (що є удосконаленням запропонованої консорціумом OMG для розширення можливостей UML мови OCL), яка дозволяє на вищому за специфікації Object-Z та Event-B рівні задавати вимоги до поведінки елементів моделей програм. Окрім стандартних можливостей OCL, OQLc дозволяє виражати постумови виконання методів як логічні правила виду «якщо-то» та задавати допустиму трасу виклику методів компонента за допомогою розширених регулярних виразів.

Будь-яка рекомендація формалізована як правило переваги та відповідний такому правилу коефіцієнт довіри. Правило переваги має форму:

ContextPattern>Recommendation;Degree_of_Belief (4)

де ContextPattern - кон'юнкція фактів про зв'язки анотованого елемента (далі dummy) в контексті поточної діаграми, наприклад, Version(c, N), ComponentTypeName(c), PropertyName(dummy, c), FollowsBy(dummy, c);

Recommendation- рекомендація щодо використання анотованого елемента у зазначеному контексті: RecommendToUse, RecommendToReplaceWith(Component TypeName), RecommendNotToUse;

Degree_of_Belief - ступінь довіри до правила.

Розроблено структуру онтології системи синтезу моделей програм (Software Engineering Ontology - SEOntology), яка включає концепти та відношення для опису елементів моделей програм та їх атрибутів, семантичної анотації, таксономію концептів загального призначення для заповнення атрибутів екземплярів семантичних анотації. Для оптимізації процесу пошуку уточнюючих елементів під час синтезу моделей програм запропоновано структуру організації індексу за анотаційною складовою онтології.

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

У третьому розділі розроблено метод семантико-синтаксичного аналізу формальної мови на основі її багатокомпонентної моделі.

Багатокомпонентна модель формальної мови, на відміну від існуючих форм опису формальних мов, дозволяє під час проектування мови та її аналізаторів задавати цілісну модель мови через декілька моделей синтаксису, одну первинну модель семантики, декілька вторинних моделей семантики:

(5)

де Synt(L) - модель синтаксису мови, Sem_prim (L) - первинна модель семантики мови, Sem(L) - вторинна модель семантики мови. Якщо SYNT_TEXT - допустима модель синтаксису текстової мови, SYNT_GRAPH - допустима модель синтаксису графової мови, то SYNT= SYNT_TEXT SYNT_GRAPH.

SEM=<U,R,F> (6)

де U - скінченна непуста множина типів,

U=SyntacticConcepts SemanticConcept;,

R - скінченна непуста множина відношень,

R=SyntacticRelations SemanticRelations SyntacticToSemanticMappingRelations;

F - скінченна непуста множина правил виду «якщо-то» обчислення властивостей семантичних концептів у процесі аналізу вхідної конструкції:

(7)

де SyntacticConcepts та SemanticConcepts - одномісні предикати, що задають множини концептів, які являють структурні елементи відповідно синтаксичної (термінал, нетермінал) та семантичної (елемент предметної галузі, що описується мовою) моделей мови.

SyntacticRelations, SemanticRelations, SyntacticToSemanticMappingRelations - бінарні предикати, що задають допустимі типи відношень між парами відповідно синтаксичних/семантичних концептів, парами, де перший елемент належить множині SyntacticConcepts, а другий - SemanticConcepts.

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

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

Автомат синтаксичного аналізу графових мов запропоновано будувати на основі типізованої плекс-граматики. Загальна форма продукції плекс-граматики:

(8)

де LeftNapeName - найменування нейпа в лівій частині продукції;

InterfaceList - список точок інтерфейсу нейпа, який деталізує продукція;

SubNapesList - список нейпів, які деталізують лівий нетермінал продукції;

SubNapesRelationsList - список сполучень між елементами SubNapesList;

InterfaceToSubNapesRelationsList - співвідношення між інтерфейсними точками нетерміналу лівої частини продукції та інтерфейсними точками нейпів з SubNapesList;

Загальна форма задання термінальних нейпів: NapeName(InterfaceList).

Побудований на основі такого класу граматик автомат названо DLALR(k) автоматом - це розширення класичного LALR(k)-автомата, в якому для забезпечення можливості аналізу багатовимірних структур запропоновано як критерії переходів - зв'язки виду <N_j.Pt_l,N_k.Pt_m>, що відповідають наявності у графі, який підлягає аналізу, зв'язку між точкою Pt_l нейпа N_j і точкою Pt_m нейпа N_k, а як стани використовувати множини просторових станів (DLR-ситуації) виду [N(…)>(…,SN_j.Pt_l/SN_k.Pt_m,…)(…)].

На етапі формування семантичного еквівалента синтезованого синтаксичного нетерміналу використовується метод прямого логічного виводу на множині фактів та правил, отриманих з початку процесу аналізу або з семантичної моделі мови. Семантичний еквівалент синтезованого в результаті згортання синтаксичного нетерміналу подається як підмножина екземплярів концептів первинної моделі семантики та відношень між ними.

На основі багатокомпонентної моделі формальної мови розроблено моделі мови OQLc, графових мов подання діаграм моделей програм та аналізатори для них.

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

У четвертому розділі розроблено інтелектуальний метод синтезу семантичних моделей програм, удосконалено метод перевірки здійсненності семантичних моделей програм та метод машинного навчання з підкріпленням.

Новий інтелектуальний метод синтезу семантичних моделей програм полягає у поетапному уточненні моделі з використанням збережених у онтології системи синтезу моделей програм елементів та складається з таких етапів: побудова та анотування семантичної моделі програми; семантико-синтаксичний аналіз побудованої моделі на приналежність розробленій формальній мові подання семантичних моделей програм; уточнення анотованих елементів моделі на основі онтології готових елементів та поточного контексту; перевірка здійсненності синтезованої моделі; корегування онтології системи синтезу шляхом машинного навчання з підкріпленням.

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

(9)

де - множина усіх можливих складових анотації сутності (дії, методу дії, об'єкта дії, підоб'єкта дії, мети дії, напрямку дії і т. ін.).

hasValue(A, AE) - функція, що задає відображення та дозволяє отримати концепт, відповідний зазначеному елементу анотації A.

Sim(С,С) - функція обчислення ступеня семантичної еквівалентності двох термінів, що знаходяться в єдиній таксономії. Термін С3 ближче за значенням до терміну С4, ніж до терміну С5, якщо Sim(C3,C4) < Sim(C3,C5).

Sim(C1,C2)=depth(C1)+depth(C2)-2*depth(C0) (10)

де depth(C) - глибина вузла ієрархії, С0 - найбільш близький спільний предок C1 та С2.

Підбір починається пошуком у множині S збережених у онтології елементів підмножини Analogs, анотації якої відповідають критерію:

e : AE Sim(hasValue(A,e),hasValue(A_i,e)) Threshold (11)

де Threshold - це порогове значення (ціле невід'ємне позитивне число), що задає допустиму межу області еквівалентності концептів. Таким чином тільки елементи, які містять у відповідних частинах анотації семантично близькі терміни приймаються до розглядання під час пошуку семантичних аналогів серед елементів множини S.

А - семантична анотація, що задає запит проектувальника.

Відібрані до Analogs елементи впорядковуються у послідовність AnalogsV відповідно до зростання i[1..|Analogs|](A,A_i), тобто за зменшенням ступеня семантичної близькості до заданої анотації А.

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

Введено відношення потенційної подібності між додатковими анотаціями двох елементів:

PSim(E1,E2)={ps | ps aA1 aA2 } (12)

де aA1 additionalAnnotation(E1), aA2 additionalAnnotation(E1), e:E Sim(hasValue(aA1,e),hasValue(aA2,e))Threshold.

PSim ін'єктивно обмежується запропонованим методом максимальної подібності до множини PSim'' та перетворюється на зважене ін'єктивне відношення WSim:

WSim(E1,E2)={ps | ps(PSim''(E1,E2)Z) } (13)

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

Модифікований метод обчислення ступеня семантичної еквівалентності двох елементів моделей на основі їх семантичних анотацій має вигляд:

(14)

де Z_i - ступінь семантичної еквівалентності і-ої пари анотацій з WSim(E1,E2).

Отримана за (9) або (14) послідовність AnalogsV корегується з урахуванням поточного контексту та приєднаних до вибраних елементів правил переваги. Для кожного з елементів c AnalogsV визначається R' R - підмножина його правил переваги, узгоджених із поточним контекстом. Для компонента с на основі R' обчислюється показник переваги , де ' - особистий, а '' - надбаний показники переваги:

(15)

Компонент с зміщується у AnalogsV на позицій вверх або вниз відповідно до знака .

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

Здійсненною, відповідно до теорії моделей, можна назвати таку модель програми, для якої можна створити хоча б один екземпляр програми, що повністю відповідає всім зазначеним у специфікації обмеженням. Для вирішення, чи є модель програми здійсненною, запропоновано будувати на її основі задачу задоволення обмежень у фіксованому домені (Finite Domain CSP). Якщо побудована задача має розв'язання, то модель програми вважається здійсненною. Стан моделі у задачі CSP визначається таким чином:

(16)

де Instances - множина екземплярів специфікованих у моделі класів;

Relations - множина відношень між елементами Instances;

Parameters_p - множина параметрів поведінкового елемента моделі, як

посилань на Instances.

Тоді задача CSP для верифікації застосовності поведінкового елемента p моделі M на основі його семантичної анотації (2) матиме вигляд:

(17)

А задача CSP для верифікації здійсненності поведінкового елемента p моделі M на основі його семантичної анотації (2) :

(18)

Запропоновано проводити навчання системи синтезу семантичних моделей програм на основі удосконаленого методу машинного навчання з підкріпленням. Навчання системи синтезу полягає у поповненні її онтології анотаціями нових розроблених елементів та формуванні для збережених раніше елементів «рекомендацій» щодо їх використання у вигляді (4).

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

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

Принципи формування правил переваги в робочій БЗ такі:

1. На місце елемента dummy з контекстом С застосований X: для компонента X буде сформоване правило C>RecommendToUse;1.

2. Х вилучений у контексті С: для елемента X буде сформоване правило C>RecommendNotToUse;1.

3. Х замінений на Y в контексті С: для компонента X буде сформоване правило C>RecommandToReplaceWith(Y);1, а для компонента Y - правило C>RecommendNotToUse;1.

4. X замінений на Y, Y замінений на Z у контексті С: для елемента X та Y будуть сформовані правила виду C>RecommandToReplaceWith(Z);1, для елемента Z буде сформоване правило: C>RecommendNotToUse;1.

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

- якщо підтверджує , то DofB_r ^j+1= DofB_r ^j+f ( DofB_r ^j);

- якщо уточнює , то ;

- якщо спростовує, то DofB_r ^j+1= DofB_r ^j-f ( DofB_r ^j);

- якщо не має аналогів у онтології системи синтезу, то додається до неї.

f (DofB_r) =kDofB_r, k - коефіцієнт швидкості зміни DofB_r, k (0..1) Якщо ступінь довіри стає від'ємним, то правило переваги вилучається з онтології.

Таким чином, у четвертому розділі розроблено сукупність інтелектуальних методів синтезу семантичних моделей програм, запропонованих у другому розділі.

У п'ятому розділі описано реалізацію та тестування модулів прототипу інтелектуальної системи синтезу семантичних моделей програм, впроваджених на ТОВ «КОДА» (акт впровадження від 02.12.2008 р.). Наведено розроблену логічну архітектуру прототипу, що включає онтологію системи синтезу, модуль підбору уточнюючих елементів моделей, модуль перевірки здійсненності формальних моделей програм, модуль навчання, модуль взаємодії з користувачем. Онтологію системи синтезу реалізовано запропонованою консорціумом W3C мовою OWL.

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

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

У висновках сформульовано теоретичні та практичні результати роботи.

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

Висновки

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

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

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

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

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

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

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

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

7. Проведено апробацію запропонованих методів та моделей: розроблено модулі прототипу інтелектуальної системи синтезу семантичних моделей програм, які впроваджені у виробничий процес на ТОВ «КОДА» (акт впровадження від 02.12.2008 р.). Використання прототипу показало практичну застосовність та ефективність моделі, що формалізує семантику комп'ютерних програм на основі анотації їх елементів, методів синтезу та верифікації таких моделей у порівнянні з існуючими методиками розробки програм. У Харківському національному університеті радіоелектроніки результати дисертаційної роботи впроваджено у навчальному процесі на кафедрі ПЗ ЕОМ у дисциплінах «Формальні методи програмної інженерії» та «Проектування трансляторів» (акт впровадження від 5.11.2008 р.).

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

Список опублікованих праць за темою дисертації

1. Лещинская Е.Л. Слоевая грамматика и её применение для синтаксического анализа / Е.Л. Лещинская // Радиоэлектроника и информатика. -2003. - № 4(25). - С. 104 - 108.

2. Дюбко Г.Ф. Современные теории представления формальных языков / Г.Ф. Дюбко, Е.Л. Лещинская // Вестник Международного Славянского Университета. - 2005. - Т.VIII, №1-2 - С.14 - 20. - (Серия: технические науки).

3. Дюбко Г.Ф. Современные парадигмы программирования, классификация и анализ / Г.Ф. Дюбко, В.М. Черепахин, Е.Л. Лещинская // Восточно-Eвропейский журнал передовых технологий. - 2007. - №5/2(29). - C. 26 - 30.

4. Дюбко Г.Ф. Семантические модели программ в интеллектуальных средах автоматизированного проектирования программного обеспечения / Г.Ф. Дюбко, Е.Л. Лещинская, В.М. Черепахин // Прикладная радиоэлектроника. - 2008. - Т. 7, №2. - С.145 - 150.

5. Дюбко Г.Ф. Прототип интеллектуальной системы автоматизи-рованного проектирования ПО на основе его семантических моделей / Г.Ф. Дюбко, Е.Л. Лещинская // Восточно-Eвропейский журнал передовых технологий. - 2008. - №5/2(35). - C. 45 - 50.

6. Лещинская Е.Л. Идентификация семантических ошибок при синтаксическом анализе / Е.Л. Лещинская // АСУ и приборы автоматики: сб. науч. трудов. - Х., 2003. - Вып.124. - С.8 - 17.

7. Дюбко Г.Ф. Разработка графового представления грамматики для создания CASE-средств построения трансляторов / Г.Ф. Дюбко, Е.Л. Лещинская // Проблемы бионики: сб. науч. трудов. - Х., 2004. - Вып. № 60. - C.32 - 38.

8. Дюбко Г.Ф. Теоретические основы вывода в типизированных плекс-грамматиках / Г.Ф. Дюбко, Е.Л. Лещинская // Вестник НТУ «ХПИ»: сб. науч. трудов. Тематический выпуск: Информатика и моделирование. - Х.,2006. - № 40. - С.70 - 83.

9. Дюбко Г.Ф. Интеллектуальные методы поддержки автоматизированной разработки ПО / Г.Ф. Дюбко, Е.Л. Лещинская // Системи обробки інформації: зб. наук. праць. - Х., 2008. - Вип. 6(73). - С. 44 - 49.

10. Лещинская Е.Л. Исследование возможностей применения грамматики в задачах анализа и трансляции информации / Е.Л. Лещинская // Радиоэлектроника и молодежь в 21 веке: 7-й Международный молодежный форум, 22 - 24 апреля 2003 г.: тезисы докл. - Х., 2003. - С. 634.

11. Лещинская Е.Л. О новом способе представления формальной грамматики и его возможностях / Е.Л. Лещинская // Радиоэлектроника и молодежь в 21 веке: 8-й Международный молодежный форум, 13 - 15 апреля 2004 г.:тезисы докл. - Х., 2004. - С. 75.

12. Лещинская Е.Л. О проблеме и перспективах семантического описания языков / Е.Л. Лещинская // Радиоэлектроника и молодежь в 21 веке: 9-й Международный молодежный форум, 19 - 21 апреля 2005 г.: тезисы докл. - Х., 2005. - С. 373.

13. Валенда Н.А. Семантико-синтаксический анализ естественного языка / Н.А. Валенда, Е.Л. Лещинская, А.В. Кобзарь //Горизонти прикладної лінгвістики та лінгвістичних технологій: Міжнародна наукова конференція, 22 - 28 вересня 2008 г.:тези доп. - П, 2008. - С. 150 - 151.

Анотація

Лещинська О.Л. «Інтелектуальні методи синтезу семантичних моделей програм» - Рукопис.

Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 05.13.23 - Системи та засоби штучного інтелекту. Харківський національний університет радіоелектроніки, Харків, 2009.

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

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

Ключові слова: семантична модель програми, здійсненність моделі, онтологія, правило переваги, ступінь довіри, навчання з підкріпленням, метод логічного виводу на основі прецедентів.

Аннотация

Лещинская Е.Л. «Интеллектуальные методы синтеза семантических моделей программ» - Рукопись.

Диссертация на соискание ученой степени кандидата технических наук по специальности 05.13.23 - системы и средства искусственного интеллекта. Харьковский национальный университет радиоэлектроники, Харьков, 2009.

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

...