автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.02, диссертация на тему:Методы повышения эффективности математического моделирования алгоритмов информационно-технологических систем

1 1 НОЯ 1993

ФІЗИКО-МЕХАНІЧНИИ ІНСТИТУТ НАЦІОНАЛЬНОЇ АКАДЕМІЇ НАУК УКРАЇНИ'

На правах рукопису

О В СЯ к

Володимир Казимирович

МЕТОДИ ПІДВИЩЕННЯ ЕФЕКТИВНОСТІ МАТЕМАТИЧНОГО МОДЕЛЮВАННЯ АЛГОРИТМІВ ІНФОРМАЦІЙНО-ТЕХНОЛОГІЧНИХ СИСТЕМ

Спеціальність: 05.13.02 — Математичне моделювання

наукових дослідженнях

Автореферат

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

Львів — 1996:

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

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

Науковий консультант — доктор фізико-математичних наук

Драган Ярослав Петрович

‘Офіційні опоненти: — доктор технічних наук •

Луцкий Георгій Михайлович

— доктор фізико-математичних наук Кунченко Юрій Петрович

;— доктор фізико-математичних наук Вальковський Володимир Олександрович

Провідна установа — Інститут кібернетики НАН України.

0»_ 1996 р. о « ?%“•/- °

Захист відбудеться « /а>> ----1996 р. о «>

'год. на засіданні спеціалізованої ради Д 04. 01. 02 при Фізико-механічному інституті НАН України (290601, Львів, вул. Наукова! 5). '

З дисертацією можна ознайомитись у бібліотеці інституту '(290601, Львів, вул. Наукова, 5).

Автореферат розісланий « •' ОІ-с----1996 р.

В. о. вченого секретаря ■спеціалізованої вченої ради докт. тех. наук., доцент

Л. П. Дікмарова.

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

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

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

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

Серед засобів аналізу алгоритмів виділяються гіпотетичні машини Поста, Тюрінґа, Колмогорова, Ахо-Хопкрофта-Ульмана, Шенгаґе, алгоритми Маркова, універсальний алгоритм Крініцького, рекурсивні функції. Цими засобами алгоритми інтерпретуються послідовностями відповідно: інструкцій, команд, колмогоровських локальних дій, команд машини Ахо-Хопкрофта-Ульмана, команд Шенгаге, підстановок, операцій алгоритмічної мови, частково рекурсивних функцій, які назвемо операторами опрацювання даних. Такі послідовності формуються із скінченого конструктивного і функціонально повного набору, характерного для кожного методу операторів. їхніх засобів цілком достатньо для трактування алгорітмів як послідовності операторів, але ними неможливо здійснити тотожні перетворення

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

л

ектування, практичної реалізації та апробації є актуальним, має теоретичний і практичний інтерес.

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

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

Задачі дослідження:

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

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

вірогідності математичних моделей алгоритмів інформаційно-технологічних систем опрацювання даних.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Основний зміст дисертації викладений у роботах [1, 4, 6, 8,

9, 11, 19, 20, 21, 24, 25, 21, 29, ЗО, 31, 36, 37], опублікованих без співавторів.

Окремі питання, які відносяться до застосувань отриманих наукових результатів, опубліковані у співавторстві з колегами в роботах [2, 3, 5,7, 10,12- 18,22,23,26,28, 32-35].

Структура і об'єм дисертації. Дисертація складається із вступу, семи розділів, основних результатів і висновків, описаних на 236 листках, списку літератури із 156 найменувань, додатків.

ОСНОВНИЙ ЗМІСТ РОБОТИ У вступі описані задачі дослідження, обгрунтована актуальність наукової проблеми, виконаний короткий аналіз відомих публікацій, сформульовані предмет і мета дослідження, наведені короткий зміст розділів, новизна, внесена автором у рішення наукової проблеми, і положення, винесені на захист, відомості про впровадження, публікації і виступи на семінарах, конференціях, симпозіумах.

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

Встановлено, що методами Поста, Тюрінга, Маркова, Колмогорова, Шенгаґе, Крініцького, Ахо-Хопкрофта-Ульмана, рекурсивних функцій алгоритми інформаціино-технологічних систем опрацювання даних моделюються скінченою послідовністю операторів. Загально відомо, що всі ці методи за своїми теоре-

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

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

вздовж стрічки на одну комірку вліво (<------)) і номер інструкції,

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

- то до інструкції з номером j. Формат інструкції третього типу містить номер інструкції і операцію зупинки функціонування машини Поста (Зуп.). У послідовності операторів обов'язково повинна бути інструкція з номером 1, з якої починається функціонування машини Поста, і номер відсилки, до кожної на-

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

1 2 3 4 5 6 7 8 9

- номери комірок

______ _/••■ -стрічка

^ - головка зап./зчит.

Рис. 1 .Стан машини Поста до виконання алоритму.

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

1. >. 2

2. > З

4

3.

4.

5.-

?

5

* 6 —> 6

(1)

6. Зуп.

Стан машини Поста після виконання алгориту наведений на рис.2, на якому крапкою позначена записана у комірку мітка

д

Рис.2. Стан машини Поста після виконання алгоритму (1).

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

1.-

2.-

3:-

-» 2

З

4

5

4. ?

6

5. х 7

6 .--->• 7

7. Зуп.

(2)

Стан машини наведений на рис.З.

1 23456789

7-

д

Рис.З. Стан машини Поста після виконання алгоритму (2).

Але перетворити в одну загальну програму, яка охоплюва би обидва алгоритми, описані формулами (1) і (2) виключно використовуючи формальні засоби, введені термінами машини По-

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

1. ► 2

3

2. ?

7

3. >4

5

4. ?

6

5. * 11

6. > 11

7. > 8

8. > 9

10

9. 7

6

10. X 11

II. Зуп.

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

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

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

Суть концепції: над парами символів, один із яких названий оператором (символом) опрацювання даних, а інший - символом-місцем (індексом), операції означені так, що ними вводяться відповідні дії не тільки над операторами, а й над індексами, котрі перетворюються у позиції (індекси порядку, ранги) операторів. Оператори опрацювання даних належать множині 5 = {*, х, у, ..., /(*)> !(у(2)’ — •и)> — } С* - порожній символ), а символи-місця (індекси) - множині М = {а, Р}. Пара охоплюється фігурними дужками. Знаком ^ ^ позначена операція строгого впо-

рядкування символів.

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

{х, а}< {х, а} - {х, а} {*, а}, {х, а} - {х, а}

{*, а}, {х, р} - {х, а} {х, а}, С, 0 - {х, а}

{х, а}, (У, а} - {У, а}, {х, а}

{{х, а}, а}, {{у, а}, а} - { {у, а}, {хТ~а£ сі

{{х, а}• р}> {{У> а}, р) ~ { {х, а}. {У, а}, р)

{{х, а}, Р), {{У. р}, Р) = { {х. а}, {У. 0, р)

^ ^----------^

{х, а}, {У, а), {2, а} = {х, а), {У, а}, {2, сі

{^х, г), а}, Р($ и), р} = РЮх, ..., г), ..., и), а}

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

Аналогічно означені операції, які названі операціями альтернативного і виключного (для означення якого ще введена множина ознак О = {п, т}) впорядкувань символів та операція

циклу. Позначені вони відповідно такими символами: І І -

квадратною дужкою і символом 1----------------1 (або символом

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

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

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

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

(3)

(4)

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

залишимо такими, якими вони були для машини Поста. У впорядкуваннях еквівалентною операції розпізнавання машини Поста є операція виключного впорядкування, оскільки нею теж виключається одночасний перехід до виконання двох наступних операцій еквівалентність тільки у цьому розумінні. Враховуючи сказане, алгоритми, які описані програмами (1) і (2) машини Поста, впорядкуваннями опишуться виразами (3) і (4).

Виключно впорядкувавши за ознакою О впорядкування (3)

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

за допомогою виключно засобів впорядкувань.

Отож те, що неможливо отримати відомими методами математичного моделювання алгоритмів (тотожні перетворення ал-

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

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

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

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

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

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

Дослідження впорядкувань предикатів за їхніми ранговани-ми значеннями базується на адаптованій під цю задачу математичній індукції. Особливість у тому, що враховуючи упорядкованість значень змінних, першим береться те із них, ранг г якого мінімальний, а для рангу к , будь-якого значення виконується співвідношення г <к.<к+], де у = /, якщо к не збігається з рангом наступного значення і / = 0 - у випадку їх збігу. Тому дослідження описується такою процедурою: якщо впорядкування У(х) вірогідне для х-2г (де 2Г - значення з найменшим рангом), а із справедливості У(2Г) для будь-якого значення 2Г, ранг к якого такий, що к >г випливає справедливість то У(х) вірогідне

для всіх рангованих значень х.

Встановлено, що у випадку збігу рангів рангованих суджень властивості операцій строгого впорядкування рангованих суд-

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

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

тертям, пружність з інерційністю в’язким та пружнім тертям), компоненти вхідних дій (задані закони зміни у часі швидкості

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

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

Синтаксис вхідної мови системи автоматизованого проектування електро-механічних схем описується впорядкуванням символів (5), деЛ - кількість вхідних дій електро-механічної сисеми; V - змінна номеру вхідної дії; Ух - ввід номеру вхідної дії; /у - тип вхідної дії; р? - параметри вхідної дії; В - кількість компонент електро-механічної схеми; к - номер елементарної компоненти електро-механічної схеми; Кь - вводимий у ПЕОМ номер елементарної компоненти схеми; /* - тип компоненти; рк - параметри компоненти; 2ь>- кількість входів елементарної к'-о'і компоненти; /*4 :г - вводимий номер компоненти схеми; 沈 - вводимий номер виходу компоненти; рк\г - інформація про некоректності електромеханічної схеми; Ск’, - умови перевірки некоректності схеми; т

- номер компоненти схеми, результати моделювання котрої виводяться на екран дисплею ПЕОМ або на друк; 2'т - виходи компонент, значення станів котрих виводяться в результаті моделювання; Стх~ номер компоненти; gm,г•- номер виходу компоненти; И - інтервал моделювання; у/ - кількість кроків моделювання.

Семантика, як і синтаксис вхідної мови, описана впорядкуванням символів, частково, у/ є І~Р;...; 1 000 тобто для всіх символів впорядкування (5) задані області їх можливих значень, впорядкованих означеними операціями над символами.

(6)

( А 7, РКРАСР ' Ад, PSEK

Впорядкування (5) досліджене за його семантичними значеннями. Цим апріорі до практичної реалізації і апробації встановлена вірогідність вхідної мови системи автоматизованого проективання електро-механічних схем.

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

Впорядкування символів, яким описана, оптимізована і досліджена математична модель алгоритму вологоміра, виражається формулою (6), де к - змінна часового ресурсу

функціонування к є 7~Т;ГМ() . Т,ш) - максимальне значення кількості годин функціонування); А0 - впорядкування символів, яким описано підготовку вологоміра до функціонування; рУІМ -ознака за якою ідентифікується функціонування системи у режимі вимірювання; А і - опрацювання переривання за сигналом "вимірювання" і маскування переривань за сигналами "вимірювання" і "зчитування"; сі - змінна кількості первинних

перетворювачів, сі є спочатку вимірювання вико-

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

26 ■

винні перетворювачі відключаються і система переходить у режим очікування зовнішніх переривань (сигнали "вимірювання" і "'зчитування"); А4 - підготовка етапів функціонування; <7 - змінна кількості етапів функціонування системи (<7 є де, на пер-

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

с є іТ~2^; •••; 80 ; А6 - запуск на функціонування аналогоцифрового перетворювача, яким здійснюється трансформація аналогового сигналу первинного перетворювача у цифровий код; ркраср • ознака, за якою встановлюється закінчення часового інтервалу перетворення; А1 - зчитування результату перетворення; А/о -аналіз зчитаного результату перетворення з метою встановлення діапазону вимірювальних значень сигналів первинного перетворювача; А// - нагромадження результатів вимірювань; Ан -очікування завершення функціонування АЦП; Ад - режим очікування внутрішнього сигналу переривань, яким фіксується завершення попереднього і початок наступного секундного інтервалу часу; рХ/х - ознака секундного сигналу внутрішніх переривань; А2 - функціонування мікропроцесорної системи у режимі зчитування, який починається з моменту надходження зовнішнього сигналу переривання - "зчитування", за ознакою Ргяпт і полягає у послідовній видачі на телеметричну систему результатів вимірювань від трьох первинних перетворювачів.

т

°А

« £

1А

X? W

■>

Встановлена вірогідність математичних моделей алгоритмів вологоміра.

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

Результатом оптимізації математичної моделі алгоритмів мікропроцесорної системи є зменшення у 1,6 рази кількості її символів.

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

Побудоване і оптимізоване впорядкування транслятора наведене формулою (7), де Т - позначення математичної моделі алгоритму транслятора ; °А - впорядкування, яким описана підготовка транслятора до функціонування; £ - кількість частин

вхідних даних, £ е ...; Сі < 140 ; 'А - ввід вхідних даних; Х°3 - предикат-ознака переходу до підготовки трансляції вхідних даних; Х2а - предикат підготовки вхідних даних; її - предикат вибору ознаки; - предикат-ознака переходу до відновлення типу трансльованих на попередньому введені вхідних даних; 30А -впорядкування відновлення типу даних, які були трансльованими до введеної порції вхідних даних; 2Л, Х!3, С/, Х3 , С;2.... Хн3,

С*], Х'з , Х'з - описують алгоритм розпізнавання типів введених вхідних даних; 3А - впорядкування підготовки циклу; V - змінна

циклу за кількістю V <= <5 000 багатозначних еле-

ментів; 4А - впорядкування діагностики опису багатозначних елементів схеми та зв'язків між ними; 5А - впорядкування їхньої трансляції;6А - впорядкування підготовки до опрацювання помилок; 32А - опрацювання помилок; Х3 - предикат-ознака переходу у випадку закінчення чергової порції вхідних даних; Х4І - предикат підготовки відновлення зафіксованого типу вхідних даних; 27А -впорядкування розпізнавання ознаки закінчення частини вхідних даних; 26А - впорядкування визначення завершення даного типу даних; Х300 - предикат-ознака того, що даного типу дані ще не закінчені; ‘Х3 - предикат переходу;1 А - впорядкування підготовки циклу за кількістю р часових параметрів багатозначних елементів, Р є Ср <50 ■ 8А - впорядкування діагностики

опису введеного у ЕОМ часових параметрів багатозначних елементів; 9А - впорядкування їхньої трансляції;10А - впорядкування опрацювання помилки в описі часових параметрів; "А - впорядкування підготовки циклу за змінною ц кількості вхідних дій,

т] є іТ?'; сг; < 6 000 ; 12А - впорядкування діагностики введених вхідних дій;13А - трансляція вхідних дій у структури даних програми моделювання; ,4А - впорядкування опрацювання помилок в описі вхідних дій;15А - впорядкування підготовлення циклу за змінною кількості у значень відхилень коефіцієнтів передачі

багатозначних елементів від їхніх номінальних значень,

у є :и~2 ; Сг <84 ; 16А - впорядкування діагностики введених значень відхилень; І7Л - трансляція значень відхилень; І8Л - впорядкування опрацювання помилок в описі відхилень коефіцієнтів передачі елементів від їхніх номінальних значень; І9А - впорядкування підготовки циклу за змінною кількості а неодинакових значень відхилень від заданих значностей елементів,

а є Т?! -І Са<50 ; 20А - впорядкування діагностики

відхилень значностей; 21А - трансляція відхилень значностей; 22А - впорядкування опрацювання помилок в описі відхилень значностей; Х93 - предикат ознаки кінця вхідних дашіх -26А; 2Г,Л‘

- впорядкування опрацювання помилок в описі типів вхідних даних; 23А - впорядкування діагностики і трансляції заданих режимів моделювання багатозначної схеми з врахуванням чи без врахування значень відхилень; 24А та 25А - впорядкування діагностики та трансляції описаних і введених режимів моделювання багатозначної схеми у часі та номерів елементів багатозначної схеми, значення станів котрих потрібно вивести після закінчення моделювання.

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

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

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

Математична модель алгоритму обмеження величини обертового моменту на валі електродвигуна, яка оптимізована за кількістю символів, описана впорядкуванням (8), де Ло - впорядкування символів, яким описаний алгоритм вводу заданого моменту ті та встановлення початкових значень; А і - впорядкування символів, котрим задана послідовність дій для запуску аналого-цифрового перетворювача на трансформацію аналогового сигналу від первинного перетворювача обертового моменту електродвигуна у цифровий код; А2 - впорядкування обчислення

різниці значень заданого і виміряного т2 моментів, якщо значення заданого більше від значення виміряного моменту, А3 - коли значення заданого менше від значення виміряного моменту; А4 -впорядкування виводу повідомлення про досягнення величини заданого обертового моменту; А5 - впорядкування збільшення цифрового коду, який видається на цифро-аналоговий перетворювач для трансформації в аналоговий сигнал - А6, який формується - А7 в керуючий сигнал, котрий подається на електродвигун.

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

ОСНОВНІ РЕЗУЛЬТАТИ РОБОТИ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1. Овсяк В. АЛГОРИТМИ: аналіз методів, алгебра впорядкувань, моделі, моделювання. - Львів: 1996.- 132 с.

2. Овсяк В. К., Бобало С. И., Раков М. А. Моделирование многозначных структур. //Машинное моделырование. - М.: МДНТП, 1979. -с. 13- 16.

3. Дунец Р. Б., Дмитриенко В. А., Овсяк В. К., Раков М. А. Математические модели задержек распространения сигналов на многозначных элементах и структурах с инжекционным питанием. //Многозначная информационно-вычислительная техника. -К.: ИК АН УССР, 1979. -с.34 - 40.

4. Овсяк В. К. Некоторые особенности и алгоритмы работы комплекса моделирования многозначных структур. //Моделирующие системы с многозначным и гибридным кодированием. - К.: Наук.думка, 1980. с.169- 175.

5. Дмитриенко В. А., Овсяк В. К. Вопросы построения комплекса моделирования многозначных структур. //Моделирующие системы с многозначным и гибридным кодированием. - К.: Наук.думка, 1980. -с.175-181.

6. Овсяк В. К. Математическая модель системы моделирования логических структур. //Информационные системы исследования природных ресурсов. - К.: ИК АН УССР, 1982. - с.65-76.

7. Овсяк В. К., Литвинюк А. А. Способ обнаружения генерирующих цепочек элементов в моделируемых логических структурах. //Многозначные элементы, структуры, системы. - К.: Наук.думка, 1983. - с.42-48.

8. Овсяк В. К. Концепція формалізації впорядкувань символів

і функцій. //Імовірнісні моделі та обробка випадкових сигналів і полів. - Харків: 1992. - с.126-130.

9. Овсяк В. К. Метод синтезу і аналізу алгоритмів обробки сигналів, //мовірнісні моделі та обробка випадкових сигналів і полів. - Львів: 1993. - с.98-106.

10. Драган Я. П., Овсяк .К. Спосіб аналітичного опису алгоритмів. //Імовірнісні моделі та обробка випадкових сигналів і полів.-Львів: 1993. - с.107-112

11. Овсяк В. К. Операції впорядкувань символів. //Обробка сигналів і зображень та розпізнавання образів. УкрОБРАЗ-94. -К.: ІК НАН України, 1994. с.48-51.

12. Драган Я. П., Овсяк В. К. Формалізований опис алгоритмів розпізнавання й опрацювання сигналів і зображень та розпізнавання образів. УкрОБРАЗ-94. - К.: ІК НАН України,

1994.-с.51-55.

13.ГутИ. И., ДунецР. Б., Колодчак И. Л., Овсяк В. К. Устройство для преобразования двоично-десятичных чисел в двоичные. А.С. № 550663 (СССР) Бюлл. изобр. №10. 1977.

14. Дунец Р. Б., Колодчак И. Л., Овсяк В. К. Микропрограммное устройство управления. А.С. № 564635 (СССР) Бюлл. изобр. № 25. 1977.

15. Гут И. И., Дунец Р. Б., Колодчак И. Л., Овсяк В. К. Устройство управления группой накопителей цифровой вычислительной машины. А.С. №601692 (СССР) Бюлл. изобр. № 13. 1978.

16. Ланцов А. Л., Овсяк В. К. Микропрограммное устройство управления. А.С. № (СССР) Бюлл. изобр. № 24. 1981.

17. Раков М. А., Кузнецова В. Л., Овсяк В. К. Устройство моделирования функций нейрона. А.С. № 1138813 (СССР) Бюлл. изобр. № 5. 1985.

18. Овсяк В. К., Карцев А. Д., ЛитвинюкА. А. Исследование и разработка системы моделирования многозначных логических структур. // - К.: ГФАП - УкрРФАП N 5929, 1981.-270 с.

19. Овсяк В. К. Элементы теории упорядочений. //- М.: ВИНИТИ, N4124, 1985.-6 с.

20. Овсяк В. К. Программа имитации функционирования многозначных логических структур (УПОРЯДОЧЕНИЯ). //- К.: ИК АН УССР. ГФАП - УкрРФАП N АП0159, 1986. - 450 с.

21. Овсяк В. К. Логика и исчисление упорядочений. //Высокопроизводительные системы обработки информации. -Львов: ФМИ, 1984. - с.73 - 74.

22. Драґан Я. П., Овсяк В. К. Структурний аналіз алгоритмів та ефективність обробки стохастичних сигналів. //Імовірнісні моделі та обробка випадкових сигналів і полів. - Харків: 1992. -с.131 -132.

23. Дунець Р. Б., Луцків М. М., Овсяк В. К. Розробка методів моделювання і аналізу електро-механічних систем з використанням ЕОМ. //Львів: УПІ, 1993. - с.9.

24. Овсяк В. К. Метод мінімізації впорядкувань суджень висіканням. //Тези доповіді звітної науково-технічної конференції УПІ. - Львів: УПІ, 1993. - с.39.

25. Овсяк В. К. Побудова та дослідження алгоритмів автоматичного управління мікропроцесорною системою вимірювання

вологості. //1-а Українська конференція з автоматичного керування "Автоматика - 94". - К.: КПІ, 1994. - с.243.

26. Волощак І.А., Козакевич Я. М., Овсяк В. К., Стреїіко І. Т. Мікропроцесорна система керування електроприводом рулонної друкарської машини. //Приборостроение - 94. -Винница-Симферополь: 1994. - с.140.

27. Овсяк В. К. Елементи алгебри впорядкувань символів. //Тези доповіді звітнної науково-технічної конференції УАД. -Львів: УАД, 1995.-С.53.

28. Дунець Р. Б., Овсяк В. К. Застосування розширених one-

\

рацій алгебри логіки для побудови підсистеми автоматизованого моделювання електро-механічних схем. //Тези доповіді звітної науково-технічної конференції УАД. - Львів: УАД, 1995. - с.55.

29. Овсяк В. К. Теорія впорядкувань і САПР. //Тези доповіді Міжнародної наукової конференції, присвяченої 150-річчю від дня народження видатного українського фізика і електротехніка Івана Пулюя. - Тернопіль: ТПІ ім.І.Пулюя, 1995. - с.85.

30. Овсяк В. К. Математична модель алгоритму мікропроцесорної системи керування електроприводом. //Контроль и управление в технических системах. Часть 2. - Винница: ВГТУ, 1995.-c.470.

31. Овсяк В. К. Математична модель алгоритму мікропроцесорної системи вимірювання вологості повітря. //Контроль и управление в технических системах. Часть 2. - Винница: ВГТУ, 1995.-c.391.

32. Луцків М. М., Овсяк В. К. Система керування електроприводом рулонної друкарської машини. //Контроль и управление в технических системах. Часть 2. - Винница: ВГТУ, 1995. - с.448.

33. ДраґанЯ. П., Овсяк В. К. Операції числення впорядкувань. //Друга Українська конференція з автоматичного керування "Автоматика - 95". Частина 4. - Львів: ЛДУ ім.Ів.Франка,

1995.-с.53.

34. Луцків М. М., Овсяк В. К. Математичне моделювання алгоритмів транслятора САПР ЕМС. //Розробка та застосування математичного моделювання в науково-технічних дослідженнях. Частина 2. - Львів: ДУ "Львівська політехніка", 1995. - с.118.

35. Драґан Я. П., Овсяк В. К. Аналіз методів математичного моделювання алгоритмів. //Розробка та застосування математичного моделювання в науково-технічних дослідженнях. Частина 3. -Львів: ДУ "Львівська політехніка", 1995. - с.ЗО.

36. Овсяк В. Метод формалізації, еквівалентних перетворень і дослідження синтаксису й семантики вхідних мов САПР. //Розробка та застосування математичного моделювання в науково-технічних дослідженнях. Частина 2. - Львів: ДУ "Львівська політехніка", 1995.-c.123.

37. Овсяк В. К. Впорядкування символів - математичні моделі алгоритмів комп'ютерних технологій. //УкрСОФТ - 95. - Львів: ДУ "Львівська політехніка", 1995. - с.68.

Овсяк В. К. Методы повышения еффектнвностн математического моделирования алгоритмов информационно-технологи-ческих систем.

Диссертация на соискание ученой степени доктора технических наук по специальности 05.13.02 - Математическое моделирование в научных исследованиях, Физико-механический институт им.Г.В.Карпенко НАН Украины, Львов, 1996.

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

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

печатной машины, транслятора САПР многозначных логических структур, синтаксис и семантика входного языка САПР электромеханических систем.

V.Ovsyak. Efficiency Improvement Methods of Mathematical Modelling of Algorithms of Information Technology Systems.

Thesis for scientific degree of doctor of the technical science. Speciality 05.13.02 "Mathematical modelling in scientific reseach's", Karpenko Physics and Mechanics Institute of Ukrainian National Academy of Sciences, Lviv, 1996.

The scientific problem of equvalent transformations for mathematical modelling of algorithms of data-processing information technology systems with a purpose of their optimization and truth ascertation is solved. The conception and the method for the construction of mathematical means to description, equvalent transformations and investigation of the mathematical models of algorithms are worked out. There are defined operations at the operators of data-processing and ranged predicate which make up the base of methametical modelling methods of algorithms by arran gement of the operators and the predicates. Worked out methods of minimization of algorithms which are descripted bu the arrangement of the statements. The techniques are built for modelling and truth ascertation of the mathematical models of the algorithms.

The mathematical modells of algorithms for the microprocessor's system of the air humidity measuring, of the

controlling of the rotation printing maghines, for the CAD translator of the multivalued logic structures, the syntax and semantics of the input language for the CAD of the electromechanical systems are elaborated and optimized by number of the data-processings operators and their truth is ascerted.

Ключові слова: математична модель алгоритму,

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

Підписано до друку 12.09.96. Зам. 728. Тираж 100.

Пустомитівська районна друкарня Львівська обл. м.Пустомити, вул.Грушевського,33