Національний аерокосмічний університет ім. М.Є. Жуковського

“Харківський авіаційний інститут”

ДОЦЕНКО Наталія Володимирівна

УДК 658.012.011.56:681.3.062:519.71

Методи СИНТЕЗУ алгоритмічних перетворювачів для автоматизованих систем діагностування авіаційного призначення

05.13.06 – автоматизовані системи управління та прогресивні інформаційні технології

Автореферат

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

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

Харків – 2004

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

Робота виконана в Національному аерокосмічному університеті імені М.Є. Жуковського “Харківський авіаційний інститут”, Міністерство освіти і науки України.

Науковий керівник - кандидат технічних наук, старший науковий

співробітник Кучмієв Володимир Гавриїлович,

Національний аерокосмічний університет

імені М.Є. Жуковського “ХАІ”, доцент

кафедри менеджменту.

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

- доктор технічних наук, професор Лисенко Едуард Вікторович, Національний аерокосмічний університет імені М.Є. Жуковського “ХАІ”, професор кафедри інформаційних систем;

- кандидат технічних наук, доцент Безкоровайний Володимир Валентинович, Харківський національний університет радіоелектроніки, доцент кафедри системотехніки.

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

Національний технічний університет “Харківський політехнічний інститут”, кафедра системного аналізу і управління, Міністерство освіти і науки України, м. Харків.

Захист відбудеться “21” травня 2004 р. о 1200 годині на засіданні спеціалізованої вченої ради Д 64.062.01 у Національному аерокосмічному університеті імені М.Є. Жуковського “Харківський авіаційний інститут” за адресою: 61070, м. Харків, вул. Чкалова 17, радіотехнічний корпус, ауд. 232.

З дисертацією можна ознайомитися у бібліотеці Національного аерокосмічного університету імені М.Є. Жуковського за адресою: 61070, м. Харків, вул. Чкалова, 17.

Автореферат розісланий “14” квітня 2004 р.

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

спеціалізованої вченої ради Чумаченко І.В.

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

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

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

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

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

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

Зв'язок роботи з науковими програмами, планами, темами. Дисертаційна робота виконувалася в рамках науково-дослідних робіт, що проводилися на кафедрах авіаційних приладів і вимірювань, менеджменту Національного аерокосмічного університету ім. М.Є. Жуковського “ХАІ”, відповідно до планів Міністерства освіти і науки України, Міністерства оборони України, постанов директивних органів, з держбюджетних і госпдоговірних тем: “Автоматизована система вибору мікроконтролера для систем управління, збирання і переробки інформації” (№ ДР 0102U002307); “Розробка системного забезпечення автоматизованої комп'ютерної інформаційно-керуючої системи військової частини України” (№ ДР 0100U005402); “Дослідження і розробка методів проектування та модернізації засобів мікроелектронної техніки” (№ ДР 012U001772); “Моделі та методи алгоритмізації функціональних задач управління та переробки інформації в бортових приладових комплексах” (№ ДР 0102U005986). Доценко Н.В. є виконавцем перелічених робіт.

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

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

Задачі, що вирішуються в дисертаційній роботі:

1) провести аналіз методів створення автоматизованих комплексів авіаційного призначення;

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

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

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

5) створити програмно-апаратні засоби автоматизованого аналізу та розробки алгоритмічних структур;

6) впровадити результати досліджень у практику створення апаратно-програмних засобів.

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

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

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

Наукова новизна одержаних результатів.

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

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

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

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

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

Наукові результати одержані автором особисто і є основою для розв’язання науково-прикладної задачі.

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

У практику підприємств та організацій впроваджені такі результати виконаних досліджень: алгебричний метод перетворення безповторних алгоритмічних структур із комутативними умовами, метод конструктивного перерахування діагностичних моделей, метод синтезу настроювальних алгоритмічних перетворювачів, програмно-апаратні засоби автоматизації аналізу та розробки алгоритмічних структур впроваджені у ВАТ “Авіаконтроль”, м. Харків; метод перетворення безповторних алгоритмічних структур із комутативними умовами, метод синтезу настроювальних алгоритмічних перетворювачів, алгоритмічне та програмне забезпечення впроваджені у Науково-дослідному інституті “ХЕМЗ”, м. Харків; комп'ютерні програми “Програма побудови контрольних та діагностичних тестів”, “Програма побудови мінімальних діагностичних тестів” впроваджені у ВАТ “Теплові мережі”, м. Харків; метод перетворення алгоритмічних структур, метод класифікації та конструктивного перерахування діагностичних моделей, алгоритми та програми побудови оптимальних контрольних і діагностичних тестів, метод синтезу настроювальних алгоритмічних перетворювачів, принципи побудови програмно-апаратних засобів автоматизації аналізу та синтезу алгоритмічних структур впроваджені у навчальному процесі Національного аерокосмічного університету ім. М.Є. Жуковського “ХАІ”, м. Харків; визнані винаходами з видачею патентів України у Державному департаменті інтелектуальної власності, Українському інституті промислової власності синтаксичний аналізатор контекстно-вільних граматик, пристрій для розв’язання комбінаторно-логічних задач, пристрій для визначення характеристик двійкових послідовностей, аналізатор, автоматизована система для проведення багатофакторного експерименту, аналізатор алгоритмічних перетворювачів, формувач контрольних тестів, діагностичний процесор, адаптивна резервована система, пристрій для оптимізації діагностичних тестів, комбінаторно-логічний процесор, адаптивний діагностичний процесор, м. Київ; свідоцтва про Державну реєстрацію прав автора на твори комп'ютерні програми “Програма визначення еквівалентності діагностичних моделей”, “Програма генерації типових комбінаторних конфігурацій”, “Програма побудови адаптивних діагностичних алгоритмів”, “Програма побудови контрольних та діагностичних тестів”, “Програма побудови мінімальних діагностичних тестів” отримані у Державному департаменті інтелектуальної власності, м. Київ.

Особистий внесок здобувача. Здобувачеві особисто належать у спільних працях такі положення: структура настроювальних алгоритмічних перетворювачів [1], метод побудови графових моделей об’єктів діагностування [2], оцінка кількості біхроматичних графів [3], види перетворень і метод класифікації діагностичних моделей [4, 32], алгебричний метод аналізу та розробки діагностичних алгоритмів [5, 29], види класифікації безповторних алгоритмічних структур [6], оцінка кількості змінних у настроювальних алгоритмічних перетворювачах [7], оцінка реберних характеристик М-графів [8], структура синтаксичного аналізатора контекстно-вільних граматик [9], схема пристрою для розв’язання комбінаторно-логічних задач [10], схема пристрою для визначення характеристик двійкових послідовностей [11], схема аналізатора [12], схема аналізатора алгоритмічних перетворювачів [13], схема автоматизованої системи для проведення багатофакторного експерименту [14], схема пристрою формувача контрольних тестів [15], схема діагностичного процесора [16], структура адаптивної резервованої системи [17], схема пристрою для оптимізації діагностичних тестів [18], структура адаптивного діагностичного процесора [20], алгоритм визначення еквівалентності діагностичних моделей [21], алгоритм генерації типових комбінаторних конфігурацій [22], процедури побудови адаптивних діагностичних алгоритмів [23], процедури побудови діагностичних тестів [24], процедури побудови мінімальних діагностичних тестів [25], структура програмного забезпечення [26], метод класифікації типових структур схем алгоритмів [27], аналіз поліноміальних форм алгоритмів і виявлення властивості поліноміальної форми діагностичних алгоритмів [30], аналіз принципів побудови адаптивних діагностичних алгоритмів [33].

Апробація результатів дисертації. Основні результати дисертації доповідалися й обговорювалися на Міжнародній науково-технічній конференції “Приладобудування - 2000” (с. Симеіз, 2000 р.); Міжнародній науково-технічній конференції “Інтегровані комп’ютерні технології в машинобудуванні ІКТМ’2001” (м. Харків, 2001 р.); Міжнародній науково-практичній конференції “Інформаційні технології управління екологічною безпекою, ресурсами та заходами у надзвичайних ситуаціях” (м. Харків, 2002 р.); 3-й Міжнародній міждисциплінарній науково-практичній конференції “Сучасні проблеми гуманізації та гармонізації управління” (м. Харків, 2002 р.); Міжнародній науково-технічній конференції “Інтегровані комп’ютерні технології в машинобудуванні ІКТМ’2002” (м. Харків, 2002 р.); 4-й Міжнародній міждисциплінарній науково-практичній конференції “Сучасні проблеми науки та освіти” (м. Ялта, 2003 р.); Міжнародній науково-практичній конференції “Україна наукова 2003” (м. Дніпропетровськ, 2003 р.); науково-технічній конференції “Системи управління - 2001” (м. Харків, 2001 р.).

Публікації. Основні результати дисертації опубліковані в 33 працях, з яких 3 статті у наукових журналах, 5 статей у збірках наукових праць, 12 патентів України, 5 свідоцтв Державної реєстрації прав автора на твір, 8 матеріалів і тез конференцій.

Структура й обсяг роботи. Дисертація містить вступ, 6 розділів, висновки, викладена на 205 сторінках, що містять 50 рисунків на 4 сторінках, 33 таблиці на 6 сторінках, список з 205 використаних літературних джерел на 20 сторінках і 3 додатку на 24 сторінках.

ОСНОВНИЙ ЗМІСТ роботи

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

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

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

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

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

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

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

При проектуванні систем управління, контролю та переробки інформації у переважній більшості випадків використовується вузький клас формул, для яких безповторність і комутативність є характерними властивостями. Проведено аналіз різних видів безповторності залежно від форми подання алгоритмів, наведено інваріанти для визначення класів еквівалентності. Розглянуто види перетворень, які легко здійсненні для розглянутого виду об’єктів: перестановка елементів (Р – перетворення), інверсія значень змінних на протилежні (N – перетворення), підстановка замість змінної деякої логічної функції (F - перетворення).

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

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

На множині операторів введено операцію об'єднання операторів “”, що визначається таким чином: Р1vР2=(Р1Р2). Виявлено основні властивості операції об'єднання операторів. Наведено графічну інтерпретацію операції об'єднання.

Настройкою алгоритму A(Y) називається підстановка як умовних змінних значень із множини {0, 1, xi,xi, (X)}, де (X) - логічна функція від змінних X={x1, …, xk}. У результаті настройки алгоритм перетворюється на похідний алгоритм від k змінних.

Декомпозицією алгоритму A=(Y1, …, Yn) за змінною Yi (позначається (A(Y), Yi)) називається розбиття алгоритму A=(Y1, …, Yn) на два похідних алгоритми, які отримають у результаті настройок: A1(Y1, …, Yi-1, 0, Yi+1, …, Yn) та A2(Y1, …, Yi-1, 1, Yi+1, …, Yn).

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

Показано, що у результаті тотожних перетворень отримуємо множину еквівалентних алгоритмів, які у загальному випадку мають різні характеристики (глибина схеми алгоритму, кількість операторів). Це дає можливість вибирати оптимальний варіант побудови алгоритму. Наведено приклади перетворень.

Розглянуто застосування алгебричного методу перетворення безповторних алгоритмічних структур із комутативними умовами для алгоритмів, що мають деревоподібну структуру. Показано, що при n > ]log2d[ (d – кількість кінцевих гілок дерева, n – кількість умовних змінних вихідного алгоритму) ці перетворення приводять до мінімізації глибини структури, що особливо актуально при використанні багатоконвеєрних процесорів.

Суть перетворень полягає у введенні нових умовних змінних, які є логічними функціями від початкових умовних змінних. При цьому відповідно до вибраного кодування визначається вид логічних функцій і вид АПД перетвореного алгоритму. Застосування цих перетворень дозволяє зменшити глибину алгоритму у середньому на 10…35% залежно від виду алгоритму.

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

Основні результати розділу опубліковано у працях [4, 5, 6, 27, 29, 30, 32].

У третьому розділі розглянуто питання аналізу та синтезу настроювальних алгоритмічних перетворювачів (НАП).

Запропоновано структуру НАП. НАП складається з формувача настройок і реалізатора базового алгоритму (РБА). Розглянуто види і особливості настройок НАП. Для запису варіанта настройки використовується запис a1Ca2D2а3D3…аvDv, де коефіцієнт а1 вказує на кількість константних сигналів, коефіцієнти ai (і>1) вказують, скільки разів у варіанті настройки використовується дублювання Di. Виявлено властивості коефіцієнтів, що входять у запис настройки:

де n - кількість входів реалізатора базового алгоритму; r - кількість входів, що настроюються; k - кількість інформаційних входів НАП.

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

Сформульовано задачі аналізу та синтезу НАП.

Нехай А - базовий алгоритм, Н - {h1, h2, …, hq} - множина настройок, П - задана множина перетворень.

Задача аналізу НАП.

Знайти множину В={В1, …, Вv} похідних алгоритмів, таких що Вi=A(Hj); i=1,…,v; j=1,…,q;

П

BiBd; d=1…v,

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

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

Задача синтезу НАП.

Визначити базовий алгоритм A(Y) з множиною настройок H={h1, h2, …,hq}, такий, що A(hj)=Bi, де hiH, i=1,…,q та |Y|min.

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

Метод синтезу НАП складається з таких етапів.

Етап 1. Визначаємо довжину початкової конфігурації d=2n-r-1 і відповідну їй настройку h(n, r, d).

Етап 2. Записуємо значення АПД похідного алгоритму В1 у відповідні комірки АПД базового алгоритму В1A(h(n, r, d)).

Етап 3. Видаляємо реалізований похідний алгоритм В1 із множини В.

Етап 4. d=d+1.

Етап 5. Якщо значення d не відповідає номеру кінцевої комірки (n, r) конфігурації, то переходимо до п. 4.

Етап 6. Визначаємо множину настройок з довжиною конфігурації d.

Етап 7. Для кожної настройки визначаємо похідний алгоритм, що реалізується, С=А(hi(n, r, d)).

Етап 8. Перевіряємо відношення заданих похідних алгоритмів та алгоритму С(А(hi(n, r, d))). Алгоритм Bj реалізується, якщо BjС(А(hi(n, r, d))) або Bj=С(А(hi(n, r, d))). У першому випадку записуємо значення АПД алгоритму Bj у відповідні комірки АПД базового алгоритму BjА(hi(n, r, d)).

Етап 9. Реалізований алгоритм Bj виключаємо з множини В.

Етап 10. Виконуємо пп. 4-9 до реалізації всіх заданих похідних алгоритмів.

Етап 11. Визначаємо кількість змінних НАП n=]log2d[, де ]а[ - найближче ціле, не менше, ніж а.

Етап 12. Довизначаємо у випадку необхідності значення комірок АПД базового алгоритму.

Етап 13. Кінець.

Розроблений метод синтезу відрізняється тим, що використовується розширена множина настройок, яка формується безпосередньо під час роботи. Отримані за допомогою запропонованого методу синтезу НАП мають складність, що на 12…27% менше в порівнянні з використанням інших методів синтезу.

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

Показано, що до визначення виду настройок зводиться і задача побудови мінімального діагностичного тесту. Нехай Р - множина перевірок, А(Р) – алгоритм, що відповідає діагностичній моделі (матриці несправностей), R – множина настроювальних перевірок (R P), тоді мінімальному діагностичному тесту відповідає -декомпозиція виду (A(Р), R), для якої |R|max і всі стани ідентифікуються.

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

Основні результати розділу наведено у працях [1, 7, 13, 31, 33].

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

Для конструктивного перерахування діагностичних моделей запропоновано використовувати М-графи.

М (V1,V2,R) – граф – біхроматичний граф, у якого множина вершин розбита на дві підмножини V1 = {v11,…,v1n} та V2 = {v21,…,v2k} з околами вершин відповідно O(v11), … , O(v1n) для підмножини вершин V1 та O(v21), …,O(v2k) для підмножини вершин V2, що відповідає таким властивостям:

1) O(v1i) O(v1j) (i,j = 1…n; ij); 2) O(v2i) O(v2j), (i,j = 1…k; ij);

3) k >O(v1i) 1 (i = 1…n); 4) n O(v2j) 1 (j = 1…k).

Для визначення кількості типових варіантів діагностичних моделей необхідно знати мінімальну та максимальну кількість ребер у М–графі. Існуючі оцінки максимальної кількості ребер: оцінки Турана, Моцкіна та Штрауса, є верхніми оцінками. Тому були визначені мінімальна та максимальна кількість ребер М-графа:

- мінімальна кількість ребер

- максимальна кількість ребер

де (n,k) - функція, що відповідає найбільшому ступеню вершини S, для якої виконується співвідношення

Отримано оцінку кількості М(V1,V2,R)-графів для заданих n,k, R:

де R - коефіцієнт в багаточлені, що перераховує bn,k при доданку xR,

[r, t] – найменше кратне чисел r і t; (r, t) – найбільший спільний дільник чисел r і t; , - підстановки; jr() - число циклів довжини r для підстановки; jt() - число циклів довжини t для підстановки; (Z(G), 1+x) – функція, що дорівнює підстановці 1+xm замість sm в Z(G); =1 при n=k та 0 у протилежному випадку; LRn,k - кількість графів, у яких порушені властивості 1-4, та які при цьому не мають ізольованих вершин.

Приведено оцінки кількості типових варіантів M(V1,V2,R)-графів для деяких n, k. Наведено метод генерації типових варіантів M(V1,V2,R)-графів. Побудовано каталог діагностичних моделей.

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

Основні результати розділу опубліковано у працях [2, 3, 8].

У п'ятому розділі розглянуто апаратні засоби автоматизації розробки алгоритмічних структур.

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

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

Основні результати розділу опубліковані у працях [9, 11, 15-20].

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

Програмний комплекс автоматизації проектування алгоритмічних структур призначений для розвязання таких задач:

-

-

-

-

-

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

Основні результати розділу опубліковані у працях [21-25].

ВИСНОВКИ

1. Вирішено науково-прикладну задачу розробки ефективних алгоритмічних

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

2. Розроблено алгебричний метод перетворення безповторних алгоритмічних структур із комутативними умовами, що дозволяє проводити формалізовані перетворення при аналізі та синтезі керуючих, обчислювальних і діагностичних алгоритмів. Показано, що в результаті тотожних перетворень формуються алгоритми з різними характеристиками. Застосування цих перетворень дозволяє скоротити глибину алгоритму у середньому на 10…35% для різних алгоритмів.

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

4. Запропоновано принципи побудови настроювальних алгоритмічних перетворювачів. Розширено множину настройок. Розглянуто способи настроювання алгоритмічних перетворювачів. Запропоновано метод аналізу НАП, що дозволяє визначити множину похідних алгоритмів, одержуваних з базового шляхом настройки. Для автоматизації процесу аналізу алгоритмічних перетворювачів, а також для апаратної реалізації відповідної макрокоманди розроблено аналізатор алгоритмічних перетворювачів. Запропоновано метод синтезу настроювальних алгоритмічних перетворювачів при застосуванні розширеної множини настройок для вирішення функціональних задач керування, контролю та переробки інформації, що дозволяє реалізувати задану множину керуючих, обчислювальних і діагностичних алгоритмів з більшою ефективністю. Отримані за допомогою запропонованого методу синтезу НАП мають складність, на 12…27% меншу в порівнянні із застосуванням інших методів синтезу. Показано використання методу для вирішення задачі організації оптимального діагностування у директивний термін часу.

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

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

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

8. У практику підприємств та організацій впроваджено такі результати виконаних досліджень:

- алгебричний метод перетворення безповторних алгоритмічних структур із комутативними умовами, метод конструктивного перерахування діагностичних моделей, метод синтезу настроювальних алгоритмічних перетворювачів, програмно-апаратні засоби автоматизації аналізу та розробки алгоритмічних структур впроваджені у ВАТ “Авіаконтроль”, м. Харків;

- метод перетворення безповторних алгоритмічних структур із комутативними умовами, метод синтезу настроювальних алгоритмічних перетворювачів, алгоритмічне та програмне забезпечення впроваджені у Науково-дослідному інституті “ХЕМЗ”, м. Харків;

- комп'ютерні програми “Програма побудови контрольних та діагностичних тестів”, “Програма побудови мінімальних діагностичних тестів” впроваджені у ВАТ “Теплові мережі”, м. Харків;

- метод перетворення алгоритмічних структур, метод класифікації та конструктивного перерахування діагностичних моделей, алгоритми та програми побудови оптимальних контрольних і діагностичних тестів, метод синтезу настроювальних алгоритмічних перетворювачів, принципи побудови програмно-апаратних засобів автоматизації аналізу та синтезу алгоритмічних структур впроваджені у навчальному процесі Національного аерокосмічного університету ім. М.Є. Жуковського “ХАІ”, м. Харків;

- апаратні засоби автоматизації розробки алгоритмічних структур впроваджені в Державному департаменті інтелектуальної власності, Українському інституті промислової власності;

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

СПИСОК ОПУБЛІКОВАНИХ ПРАЦЬ за темою дисертації

1. Настройка алгоритмических преобразователей / И.В. Чумаченко, В.Г. Кучмиев, Н.В. Доценко, Е.Е. Малафеев, В.В. Косенко // Інформаційно-керуючі системи на залізничному транспорті. - 2003. - №2 (41). - С. 16-18.

2. Графовые модели объектов диагностирования / В.Г. Кучмиев, Н.В. Доценко, Е.Е. Малафеев, И.В. Чумаченко // Авиационно-космическая техника и технология. - 2003. - №8 (43). - С. 97-99.

3. Чумаченко И.В., Кучмиев В.Г., Доценко н.в. Перечисление бихроматических графов // Радіоелектронні і комп'ютерні системи. - 2003. - №4 (4). - С. .

4. Жихарев В.Я., Шилова Т.В., Доценко Н.В. Эквивалентность диагностических моделей // Открытые информационные и компьютерные интегрированные технологии: Сб. науч. тр. – Харьков: ХАИ, 2002. – Вып. 11. – С. .

5. Алгебраический подход к анализу и разработке диагностических алгоритмов / В.Я. Жихарев, Н.В. Доценко, В.Н. Торчило, А.В. Чечуй // Открытые информационные и компьютерные интегрированные технологии: Сб. науч. тр. – Харьков: ХАИ, 2002. – Вып. 13. – С. .

6. Чумаченко И.В., Косенко В.В., Доценко Н.В. Бесповторные алгоритмические структуры // Системи обробки інформаціi: Зб. наук. пр. - Харків: НАНУ, ПАНМ, ХВУ, 2002. - Вип. 3 (19). - С. .

7. Чумаченко И.В., Косенко В.В., Доценко Н.В. Универсальные алгоритмические преобразователи // Системи обробки інформаціi: Зб. наук. пр. - Харків: НАНУ, ПАНМ, ХВУ, 2002. - Вип. 4 (20). - С. 243-246.

8. Кучмиев В.Г., Доценко Н.В., Чумаченко И.В. Оценка реберных характеристик М-графов // Системи обробки інформаціi: Зб. наук. пр. - Харків: НАНУ, ПАНМ, ХВУ, 2003. - Вип. 5 (21). - С. .

9. Патент України № 37162, G06F17/27. Синтаксичний аналiзатор контекстно-вiльних граматик / Чумаченко I.В., Жихарев В.Я., Дергачова Н.В. - № ; Заявл. 28.03.2000; Опубл. 15.09.2003, Бюл. № 9.- 11 с.

10. Патент України № 38565 А, G06F15/20. Пристрій для розв’язання комбінаторно-логічних задач / Чумаченко I.В., Жихарев В.Я., Дергачова Н.В.- № ; Заявл. 26.07.2000; Опубл. 15.05.2001, Бюл. № 4.- 7 с.

11. Патент України № 43182 А, G06F15/00. Пристрій для визначення характеристик двійкових послідовностей / М.Д. Кошовий, С.Г. Бестань, Н.В. Доценко, О.М. Кошовий. – № ; Заявл. 23.03.2001; Опубл. 15.11.2001, Бюл. № 10. - 4 с.

12. Патент України № 43709 А, G06F19/00. Аналізатор / С.О. Губка,  В.А. Дергачов, Н.В. Доценко, О.С. Губка. – № 2001053368; Заявл. 18.05.2001; Опубл. 17.12.2001, Бюл. № 11. - 5 с.

13. Патент України № 44172, G06F17/00. Аналізатор алгоритмічних перетворювачів / І.В. Чумаченко, Н.В. Доценко, Д.М. Бугас, О.В. Кас'ян, С.Ю. Мелешенко, А.Є. Горобець. - № ; Заявл. 14.06.2001; Опубл. 15.10.2003, Бюл. № 10. – 4 с.

14. Патент України № 45845 А, G06F17/00. Автоматизована система для проведення багатофакторного експерименту / М.Д. Кошовий, С.Г. Бестань, Н.В. Доценко, О.М. Кошовий. - № ; Заявл. 23.07.2001; Опубл. 15.04.2002, Бюл. №4. – 5 с.

15. Патент України № 45737 А, G06F15/00. Формувач контрольних тестів / О.Є. Федорович, С.О. Губка, В.А.  Дергачов, Н.В. Доценко, О.С. Губка. – № ; Заявл. 19.06.2001; Опубл. 15.04.2002, Бюл. № 4. - 4 с.

16. Патент України № 49639 А, G06F11/25. Діагностичний процесор /  В.Я. Жихарев, О.В. Касьян, О.В. Чечуй, С.Ю. Мелешенко, М.В. Вангельєв, Н.В. Доценко. - № 2002010352; Заявл. 14.01.2002; Опубл. 16.09.2002, Бюл. №9. - 5 с.

17. Патент України № 51152 А, G06F11/18. Адаптивна резервована система / Кулік А.С., Дергачов В.А., Доценко Н.В. - № 2002010470; Заявл. 18.01.2002; Опубл. 15.11.2002, Бюл. №11. - 5 с.

18. Патент України № 49638 А, G06F11/25. Пристрій для оптимізації діагностичних тестів / В.Я. Жихарев, О.В. Касьян, О.В. Чечуй, Т.В. Шилова, Н.В. Доценко. - № 2002010351; Заявл. 14.01.2002; Опубл. 16.09.2002, Бюл. №9. - 6 с.

19. Патент України № 54065 А, G06F15/20. Комбінаторно-логічний процесор / Доценко Н.В. - № 2002043571; Заявл. 29.04.2002; Опубл. 17.02.2003, Бюл. №2. - 5 с.

20. Патент України № 53459 А, G06F15/00. Адаптивний діагностичний процесор / Кулік А.С., Дергачов В.А., Доценко Н.В. - № 2002064542; Заявл. 04.06.2002; Опубл. 15.01.2003, Бюл. №1. - 4 с.

21. Комп’ютерна програма “Програма визначення еквівалентності діагностичних моделей” / В.Я. Жихарев, О.В. Касьян, О.В. Чечуй, Н.В. Доценко, Т.В. Шилова, С.Ю. Мелешенко: Свід. Держ. реєстр. прав автора на твір № 5470. – Зареєстр. в Держ. департ. інтелектуальної власності Мін. освіти і науки України 28.05.2002 р.

22. Комп’ютерна програма “Програма генерації типових комбінаторних конфігурацій” / В.Я. Жихарев, О.В. Касьян, О.В. Чечуй, Н.В. Доценко, Т.В. Шилова, С.Ю. Мелешенко: Свід. Держ. реєстр. прав автора на твір № 5719. – Зареєстр. в Держ. департ. інтелектуальної власності Мін. освіти і науки України 4.06.2002 р.

23. Комп’ютерна програма “Програма побудови адаптивних діагностичних алгоритмів” / Чумаченко І.В., Кучмієв В.Г., Доценко Н.В.: Свід. Держ. реєстр. прав автора на твір № 8213. – Зареєстр. в Держ. департ. інтелектуальної власності Мін. освіти і науки України 28.08.2003 р.

24. Комп’ютерна програма “Програма побудови контрольних та діагностичних тестів” / І.В. Чумаченко, В.Г. Кучмієв, Є.Є. Малафєєв, Н.В. Доценко: Свід. Держ. реєстр. прав автора на твір № 8443. – Зареєстр. в Держ. департ. інтелектуальної власності Мін. освіти і науки України 25.09.2003 р.

25. Комп’ютерна програма “Програма побудови мінімальних діагностичних тестів” / І.В. Чумаченко, В.Г. Кучмієв, Є.Є. Малафєєв, Н.В. Доценко: Свід. Держ. реєстр. прав автора на твір № 8445. – Зареєстр. в Держ. департ. інтелектуальної власності Мін. освіти і науки України 26.09.2003 р.

26. “FACTOR–M” - программное обеспечение для решения оптимизационных задач / Н.Д. Кошевой, С.Г. Бестань, О.Н. Кошевой, Н.В. Дергачёва // Тр. филиала МГТУ им. Н.Э. Баумана в г. Калуге. Спец. выпуск: Материалы междунар. науч.-техн. конф. “Приборостроение – 2000”. – Калуга, 2000. – С. .

27. Чумаченко И.В., Доценко Н.В. Перечисление типовых вариантов структур схем алгоритмов // Міжнар. наук.-техн. конф. “Інтегровані комп’ютерні технології в машинобудуванні ІКТМ – 2001”: Тези доповідей. - Харків: Нац. аерокосм. ун-т “ХАІ”, 2001. – С. .

28. Доценко Н.В. Построение оптимальных контрольных тестов // Тезисы докладов науч.-техн. конф. “Системы управления – 2001”. – Харьков: Нац. аэрокосм. ун-т “ХАИ”, 2001. – С. 6.

29. Доценко Н.В., Чечуй А.В. Алгебраический подход к анализу и разработке диагностических алгоритмов // Тези доповідей Міжнар. наук.-практ. конф. “Інформаційні технології управління екологічною безпекою, ресурсами та заходами у надзвичайних ситуаціях”. – Харків: “ХАІ”, 2002. – С. 123.

30. Косенко В.В., Доценко Н.В., Чумаченко И.В. Анализ диагностических моделей и разработка диагностических алгоритмов с помощью алгебраического подхода // “Сучасні проблеми гуманізації та гармонізації управління”: Матеріали 3-ї міжнар. міждисциплінарної наук.-практ. конф. – Харків: ХНУ, 2002. – С. .

31. Доценко Н.В. Синтез настраиваемых алгоритмических преобразователей // Міжнар. наук.-техн. конф. “Інформаційні комп’ютерні технології в машинобудуванні” – ІКТМ’2002”: Тези доповідей. – Харків: “ХАІ”, 2002. – С. 114.

32. Чумаченко И.В., Кучмиев В.Г., Доценко Н.В. Классификация диагностических моделей // “Сучасні проблеми науки та освіти”. Матеріали 4-ї Міжнар. міждисциплінарної наук.-практ. конф. – Харків: ХНУ, 2003. – С. 49.

33. Чумаченко И.В., Кучмиев В.Г., Доценко Н.В. Адаптивные диагностические алгоритмы // Матеріали міжнар. наук.-практ. конф. “Україна наукова 2003”. - Дніпропетровськ: Наука і освіта, 2003. - Т. 30. – С. 13-14.

анотація

Доценко Н.В. Методи синтезу алгоритмічних перетворювачів для автоматизованих систем діагностування авіаційного призначення. - Рукопис.

Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 05.13.06 - автоматизовані системи управління і прогресивні інформаційні технології. - Національний аерокосмічний університет ім. М.Є. Жуковського “Харківський авіаційний інститут”, Харків, 2004.

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

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

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

Аннотация

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

Диссертация на соискание ученой степени кандидата технических наук по специальности 05.13.06 - автоматизированные системы управления и прогрессивные информационные технологии. - Национальный аэрокосмический университет им. Н.Е. Жуковского “Харьковский авиационный институт”, Харьков, 2004.

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

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

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

Описаны преобразования алгоритмов, имеющих древовидную структуру. Суть преобразований состоит во введении новых условных переменных, которые являются логическими функциями от начальных условных переменных. При этом в соответствии с выбранным кодированием определяются виды логических функций и алгоритмической позиционной диаграммы преобразованного алгоритма. Применение этих преобразований позволяет сократить глубину алгоритма в среднем на 10…35% в зависимости от его структуры для различных алгоритмов.

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

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

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

Описанные методы анализа и синтеза настраиваемых алгоритмических преобразователей