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

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

КОСЕНКО Віктор Васильович

УДК 658.012.011.56:681.3.062:519.71

моделі та методи алгоритмізації функціональних задач

управління і переробки інформації в бортових приладових комплексах

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

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

Автореферат

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

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

Харків – 2003

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

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

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

Чумаченко Ігор Володимирович,

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

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

завідувач кафедри менеджменту.

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

-

-

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

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

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

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

Автореферат розісланий “7” травня 2003 р.

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

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

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

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

Льотно-технічні та конструктивні характеристики сучасного літака визначаються не тільки технічним рівнем планера і двигуна, але й ступенем удосконалення його бортового приладового комплексу (БПК). Нові типи літаків розробляються з урахуванням зростаючих потреб підвищення безпеки і забезпечення регулярності польотів, будуються за новою структурно-функціональною архітектурою бортового пілотажно-навігаційного комплексу.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Особистий внесок здобувача. Здобувачеві особисто належать у спільних працях такі положення: методика оцінки інформаційних потоків [1], метод уніфікації та типізації алгоритмічних засобів [2], метод мінімізації алгоритмічних структур [3, 15], метод класифікації безповторних алгоритмічних структур [4, 14], метод синтезу універсальних алгоритмічних перетворювачів [5], апаратні засоби інструментальної підтримки автоматизованого проектування алгоритмів і програм [7], схема пристрою завдання програми навчання [8], схема пристрою керування тренажером операторів [9], схема пристрою аналізатора алгоритмічних перетворювачів [10], схема пристрою універсального алгоритмічного перетворювача [11], алгоритмічне та програмне забезпечення визначення ефективності алгоритмів [12, 18], алгоритмічне та програмне забезпечення аналізу алгоритмів [13, 19], застосування алгебричного підходу до аналізу і розробки діагностичних моделей [17, 22], програмні засоби інструментальної підтримки автоматизованого проектування алгоритмів і програм [20], модифікована алгебра регулярних схем алгоритмів з комутативними умовами [21].

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

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

Структура й обсяг роботи. Дисертація містить вступ, 6 розділів, висновки, викладена на 199 сторінках, що містять 71 рисунків на 15 сторінках, 20 таблиць на 11 сторінках, список з 186 використаних літературних джерел на 17 сторінках і 10 додатків на 16 сторінках.

ОСНОВНИЙ ЗМІСТ РОБОТИ

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

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

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

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

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

БПК належать до складних систем. Задача проектування складних систем різного призначення в цей час залишається актуальною і важливою науковою задачею. Значний вклад у створення і розвиток методів проектування складних систем внесли вчені М.П. Бусленко, В.М. Глушков, М.З. Згуровський, М. Коллінз, М. Месарович, В.С. Михалевич, Г.Є. Поспєлов та інші. Теоретичним фундаментом розробки технічного забезпечення систем стали праці відомих учених А.А.Амбарцумяна, С.І. Баранова, В.І. Варшавського, М.А. Гаврилова, А. Гілла, В.А. Горбатова, А.Д. Закревського, Г.Е. Цейтлін, А.А. Шалита та інших.

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

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

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

Відповідно до означень, прийнятих в алгебрі регулярних схем алгоритмів з комутативними умовами, диз'юнктивна нормальна форма алгоритму (ДНФА), який описується множиною операторів P = {P1, …, Pk} і множиною умов X = {X1,…,Xn}, у загальному випадку має вигляд:

A = П1U1 v … v ПiUi v … v ПhUh,

де ПiUi - добуток відповідних операторів, який реалізується при виконанні умови Ui = 1;

Ui - кон’юнкція відповідних умов;

h- кількість членів у ДНФА.

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

Алгоритми еквівалентні, якщо їм відповідають однакові ДДНФА .

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

Означення 2.1. Настройкою алгоритму називається підстановка як умовних змінних значень з множини {0, 1, X1,X1, … , Xn,Xn}. Настройки позначаються Н = {X1,…,Xn}, де Xi {0,1, Xi,Xn }.

Означення 2.2. Частинним алгоритмом називається алгоритм, еквівалентний вихідному алгоритму, що одержується з нього шляхом настройки. Розглянуто приклади настройок алгоритмів. Довільній настройці відповідає розгляд на АПД певної правильної конфігурації. Наведено приклади формування частинних алгоритмів. Визначено кількість настройок (n, s) алгоритму від n змінних при настройці s змінних.

Означення 2.3. Функціональною декомпозицією алгоритму А(X1,…,Xn) відносно функції (X1,…,Xn) називається наступне подання алгоритму

А(X1,…,Xn) = (А1(X1,…,Xn) v А2(X1,…,Xn))(X1,…,Xn),

де A1(X1,…,Xn) = П1.1U1.1 v … v П1.i1.i v … v П1.h1U1.h1; A2(X1,…,Xn)=П2.1U2.1 v … v v П2.i2.i v … v П2.h2U2.h2; A1(X1,…,Xn) v A2(X1,…,Xn)=А(X1,…,Xn); (X1,…,Xn)=U2.1 v v … v U2.i v … v U2.h2.

У результаті функціональної декомпозиції АПД алгоритму A(X1,…,Xn) розпадається на АПД алгоритму A1(X1,…,Xn) і АПД алгоритму A2(X1,…,Xn). Наведено алгоритм визначення виду цих АПД на підставі заданої функції (X1,…,Xn).

Означення 2.4. Не повністю визначеним алгоритмом (або - алгоритмом) називається алгоритм, що містить - оператори (невизначені оператори).

Розглянуті відношення між - алгоритмами та повністю визначеними алгоритмами.

Означення 2.5. Добуток П1 = P1.1…P1n1 належить добутку П2 = P2.1…P2n2, якщо n2 n1 і P1.i = P2.i, i=1..n2 (позначається П1 П2).

Означення 2.6. Алгоритм A1 (X1,…,Xn)=П1.1U1.1 v … v П1.i1.i v … v П1.h1.h належить - алгоритму A2 (X1,…,Xn)=П2.1U2.1 v…v П2.i2.i v…v П2.h2.h, якщо П1.i П2.i, i = 1…h (позначається A1 (X1,…,Xn)A2(X1,…,Xn)).

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

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

Нехай алгоритм А описується множиною операторів P = {P1,…,Pk} і множиною умов X = {X1,…,Xn}, а ДДНФА має вигляд:

A (X1,…,Xn) = П1U1 v…vПiUi v … v ПhUh,

де ПiUi - добуток відповідних операторів Пi, який реалізується при виконанні умови; Ui = 1; Ui - кон’юнкція відповідних умов; h - кількість членів у ДДНФА .

Розіб’ємо множину добутків операторів П на підмножини, що мають однакові значення елементів. Множину різних елементів множини П позначимо D={D1,…,Dq}, де q – кількість різних елементів. З наведених у попередньому розділі тотожностей випливає, що якщо Пi = Пj ,то Пi Ui v ПjUj = Пi Ui v Uj = Пj Ui v Uj.

Поставимо у відповідність множині D = {D1,…,Dq} множину логічних функцій T = {T1(X), … , Tq(X)}, що відповідають наборам умовних змінних, при яких виконується відповідний добуток операторів. Елементи множини Т мають такі властивості :

Ti (X) & Tj (X) = 0; i j ; i = 1, …, q; j = 1, … , q;

T1 (X) v … v Tq (X) = 1.

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

А = 1 v … v i v … v q,

де i = DiTi(X).

Процес формування АПД оптимального алгоритму полягає у визначенні функціональної декомпозиції алгоритму вигляду

А = (R1.2А1.2 v R1.1А1.1)F1(X) =

= ( (R2.2А2.2 v R2.1А2.1)F2.1(X) v (R2.4A2.4 v R2.3A2.3) F2.2(X) ) F1(X) =

= (( (R3.2А3.2 v R3.1А2.1)F3.1(X) v (R3.4A3.4 v R3.3A3.3) F3.2(X) ) F2.1(X) v …

У наведеному описі індекси складаються з двох значень, розділених крапкою. Перше число вказує на крок розбиття, а друге - на значення, отримані на цьому кроці. Ri,j – послідовність операторів, загальна для всіх членів ДДНФА алгоритму Аі,j.

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

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

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

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

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

Визначено такі безповторності алгоритмічних структур (БАС): умовна, операторна й умовно – операторна. Досліджено види еквівалентності БАС і група перетворень: ={Р, N, PN, }.

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

M = a1xr1 + a2xr2 + … + aixri + … + anxrn,

де аi – кількість різних маршрутів від початкової вершини алгоритму до кінцевої, які проходять через і (і =1,…,n) умовних вершин; х – умовна змінна; ri – ранг конфігурації маршруту алгоритму.

Поліном, що відповідає ПФБАС, називається D-поліномом.

Розроблено метод побудови ПФБАС, в основі якого лежить перетворення вихідної БАС в операторно-умовно безповторну та визначення кількості різних добутків операторів у СДНФА в залежності від рангу.

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

Звідний D-поліном, що відповідає безповторній схемі алгоритму від n змінних, може бути поданий у вигляді M = M1*…*Mk, де M1,…,Mk – D-поліноми, що відповідають безповторним схемам алгоритмів від n1,…,nk змінних, (n = n1 + … + nk).

Незвідний D-поліном P(X), що відповідає безповторній схемі алгоритму від n змінних, може бути поданий у вигляді P(X) = x*(Q(X) + R(X)), де - Q(X) і R(X) - D–поліноми, що відповідають безповторним схемам алгоритмів від n1 і n2 змінних ( n1 + n2 = n - 1).

Наступним етапом при дослідженні БАС є оцінка кількості типових варіантів і побудова каталогу типових варіантів. Розроблено методи побудови каталогів типових ПФБСА для кожного виду D-поліномів.

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

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

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

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

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

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

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

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

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

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

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

Задача побудови УАП може бути сформульована таким чином.

Для заданого функціонального базису УАП = {А1(Хч),…,Ак (Хч)}, де Хч - множина змінних частинних алгоритмів (Хч= m), потрібно знайти універсальний алгоритм A(Х), (Х=n), такий, що для будь-якого частинного алгоритму Аi(Хч), i = 1,.., n існує настройка Нj, така, що A(Hj) = Ai(Хч), (Хч Х).

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

1.

2.

3.

4.

5.

6.

7.

8.

9.

10.

11.

12.

13.

14.

15.

16.

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

Розроблений метод синтезу УАП дозволяє створювати патентоспроможні технічні рішення.

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

У п'ятому розділі розглянуто застосування алгебричного підходу до аналізу діагностичних моделей і розробки діагностичних алгоритмів. Цей клас алгоритмів будується на базі діагностичних моделей (ДМ). Найпоширенішою є таблична форма діагностичних моделей. Позначимо множину технічних станів об'єкта контролю символом С. Нехай с0 означає працездатний стан, а сi - його i-й непрацездатний стан, i=1...n, де n - загальне число відмов, визначених для розпізнавання в процесі діагностування. Кожному i-му непрацездатному стану ставиться у відповідність відмова сi з множини С і навпаки.

Показано, що ДМ А(Х,С) зображувані у вигляді

А(Х) = С0U0 v С1U1 v … v СiUi v … v СкUк,

де Сi - оператор ідентифікації i-го стану, що виконується при Ui = 1; Ui = Х1 … Хj …Хn; Хj = Xj при Rij = 1 і Хj = Xj при Rij = 0.

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

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

Нехай Х - множина умов, X = n, Т1 – множина умов, що ввійшли в тест, Т2 – множина умов, що не ввійшли в тест, Т2 = L.

Тоді А(Х1) = А(Н1) v … v Ai(Hi) v … v Aw(Hw), де w = 2L, Н1…Hw - усі можливі варіанти настройки несуттєвих умовних змінних.

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

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

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

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

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

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

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

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

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

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

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

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

Основні результати розділу опубліковано у працях [6, 7, 10, 12, 13, 16, 20].

ВИСНОВКИ

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

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

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

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

5. Розроблено метод синтезу узагальнених алгоритмічних перетворювачів і алгоритми розв’язання поетапних задач. Розглянуто особливості методу при реалізації УАП, що реалізують задану множину типових частинних алгоритмів.

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

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

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

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

9. Результати використання комплексу методів синтезу алгоритмічних перетворювачів дозволили: автоматизувати процес розробки і верифікації алгоритмічних і програмних засобів, скоротити час їхньої розробки і підвищити вірогідність одержуваних результатів за рахунок виключення суб'єктивних факторів у в/ч А-2374, м. Богодухів; скоротити терміни на розробку алгоритмічного забезпечення бортового приладового комплексу, підвищити швидкодія програмного забезпечення й удосконалити процес супроводу програмної документації у ВАТ “Авіаконтроль”, м. Харків; підвищити ефективність навчального процесу за фахом 8.091301 “Інформаційно-вимірювальні системи” у Національному аерокосмічного університету ім. Н.Е. Жуковського “Харківський авіаційний інститут” та у Харківському військовому університеті.

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

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

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

ДИСЕРТАЦІЇ

1. Пашнев А.А., Косенко В.В. Методика оценки информационных потоков // Информатика: Cб. науч. тр. Ин-т проблем моделирования в энергетике НАН Украины.- К.: Наукова думка.- 1998.- Вып. 5.- С. 179-182.

2. Чумаченко И.В., Косенко В.В. Унификация и типизация алгоритмических средств при проектировании автоматизированных систем обработки информации и управления // Авіаційно-коcмічна техніка і технологія: Зб. наук. праць.- Харків: Нац. аерокосміч. ун-т “Харк. авіац. ін-т”.- 2002.- Вип. 27.- С. 204-207.

3. Косенко В.В., Чумаченко И.В. Оптимизация алгоритмического обеспечения в задачах преобразования информации // Системи обробки інформаціi: Зб. наук. пр.- Харків: НАНУ, ПАНМ, ХВУ.- 2002.- Вип.1(17).- С. 248-252.

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

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

6. Косенко В.В. Исследование алгоритмических структур при помощи программного комплекс “Алгоритм-2.5” // Системи обробки інформаціi: Зб. наук. пр.- Харків: НАНУ, ПАНМ, ХВУ.- 2002.- Вип. 5 (21).- С. 243-245.

7. Чумаченко И.В., Косенко В.В. Средства инструментальной поддержки для автоматизированного проектирования алгоритмов и программ // Авіаційно-коcмічна техніка і технологія: Зб. наук. праць.- Харків: Нац. аерокосміч. ун-т “Харк. авіац. ін-т”.- 2002.- Вип. 29.- С. 105-108.

8. Устройство задания программы обучения: А.с. № 1681320 СССР, МКИ G09B9/00 / Балабай В.И., Севастьянов С.И., Косенко В.В., Гученко Н.А., (СССР).- № 1681320; Заявлено 02.10.89; Опубл. 30.09.91, Бюл. № 36.- 8 с.

9. Устройство управления тренажером операторов: А.с. № 1714645 СССР, МКИ G09B9/00 / Балабай В.И., Косенко В.В., Викторов И.П., Севастьянов С.И., Кривой Ю.Ф., (СССР).- № 1714645; Заявлено 09.11.89; Опубл. 23.02.92, Бюл. № 7.- 10 с.

10. Патент України № 52394 А, G06F17/00. Аналізатор алгоритмічних перетворювачів / Чумаченко I.В., Косенко В.В. - № 2002043568; Заявл. 29.04.2002; Опубл. 16.12.2002, Бюл. № 12.

11. Патент України № 53336 А, G06F17/00. Універсальний алгоритмічний перетворювач / Чумаченко I.В., Косенко В.В. - № 2002043569; Заявл. 29.04.2002; Опубл. 15.01.2003, Бюл. № 1.

12. Чумаченко I.В., Косенко В.В. Комп’ютерна програма “Програма визначення ефективності алгоритмів”: Свід. про реєстр. автор. права на твір № 5965.– Зареєстр. в Держ. департ. інтелектуальної власності Мін. освіти і науки України; Реєстр. 05.06.2002; Вид. 23.07.2002.

13. Чумаченко I.В., Косенко В.В. Комп’ютерна програма “Програма аналізу алгоритмів”: Свід. про реєстр. автор. права на твір № 5966.– Зареєстр. в Держ. департ. інтелектуальної власності Мін. освіти і науки України; Реєстр. 05.06.2002; Вид. 23.07.2002.

14. Губка С.А., Лещенко А.Б., Косенко В.В. Информационная система каталогизации, хранения и поиска подобных деталей // Труды Десятой международной конференции “Новые технологии в машиностроении”.- Харків: Нац. аерокосмічний ун-т “Харк. авіац. ін-т”, 2001.- С. 25.

15. Гіневський М.І., Пашнев А.А., Косенко В.В. Аналіз властивостей стратегій розподілення логічних фрагментів баз даних // Матеріали науково-технічної конференції. Харків. МОУ, ВПОУ, ХВУ,1999.- Вип. 3.- С. 15.

16. Косенко В.В. Программный комплекс “Алгоритм-2.5” // Проблеми інформатики і моделювання. Матеріали другої міжнародної науково-технічної конференції.- Харків: НТУ “ХПІ”, 2002.- С. 6.

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

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

19. Автоматизированная система выбора микроконтроллера для систем управления, сбора и переработки информации: Отчeт о НИР (заключит.) / Нац. аерокосміч. ун-т “Харк. авіац. ін-т”.- 303-11/2001; № ДР 0102U002307; Інв. № 0202U000938.- Харків, 2002.- 48 с.

20. Разработка системного обеспечения автоматизированной компьютерной информационно-управляющей системы воинской части Украины: Отчeт о НИР (заключит.) / Нац. аерокосміч. ун-т “Харк. авіац. ін-т”.- 303-11/2001; № ДР 0100U005402; Інв. № 0202U006605.- Харків, 2002.- 79 с.

21. Исследование и разработка методов проектирования и модернизации средств микроэлектронной техники: Отчeт о НИР (заключит.) / Нац. аерокосміч. ун-т “Харк. авіац. ін-т”.- 303-11/2001; № ДР 012U001772; Інв. № 0202U004383.- Харків, 2002.- 65 с.

22. Модели и методы алгоритмизации функциональных задач управления и переработки информации в бортовых приборных комплексах: Отчeт о НИР (промежут.) / Нац. аерокосміч. ун-т “Харк. авіац. ін-т”.- 602-8/2002; № ДР 0102U005986; Інв. № 0302U005487.- Харків, 2002.- 125 с.

АНОТАЦІЯ

Косенко В.В. Моделі і методи алгоритмізації функціональних задач управління і переробки інформації в бортових приладових комплексах. – Рукопис.

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

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

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

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

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

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

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

АННОТАЦИЯ

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