Вступ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ
«ЛЬВІВСЬКА ПОЛІТЕХНІКА»
Василюк Андрій Степанович
УДК 004.4’232
підвищення ефективності математичного і програмного забезпечення редактора формул алгоритмів
01.05.03 – математичне та програмне забезпечення обчислювальних машин і систем
Автореферат
дисертації на здобуття наукового ступеня
кандидата технічних наук
Львів – 2008
Дисертацією є рукопис
Робота виконана в Українській академії друкарства Міністерства освіти і науки України
Науковий керівник доктор технічних наук, професор
Овсяк Володимир Казимирович,
професор кафедри автоматизації
та комп’ютерних технологій,
Українська академія друкарства, м. Львів
Офіційні опоненти:
Драґан Ярослав Петрович, д.ф.-м.н., проф., Національний університет “Львівська політехніка” Міністерства освіти і науки України, професор кафедри програмного забезпечення.
Опир Наталія Василівна, к.т.н., ст.н.сп., Фізико-механічний інститут ім. Г.В. Карпенка Національної академії наук України, старший науковий співробітник.
Захист відбудеться «26» травня 2008р. о 16 год. на засіданні спеціалізованої вченої ради Д.35.052.05 в Національному університеті «Львівська політехніка» (79013, Львів, вул. С. Бандери, 12).
З дисертацією можна ознайомитися в науково-технічній бібліотеці Національного університету «Львівська політехніка» (79013, Львів, вул. Професорська, 1).
Автореферат розісланий «24» квітня 2008р.
Вчений секретар
спеціалізованої вченої ради,
доктор технічних наук, професор Р.А Бунь
Загальна ХАРАКТЕРИСТИКА роботи
Актуальність теми. Будь-якою обчислювальною системою програмно, апаратно, чи програмно-апаратно реалізуються алгоритми. Як правило, опис алгоритмів у вигляді програм виконується мовами високого або асемблерного рівня. Існують інші методи опису алгоритмів, наприклад, такі як, вербальний, блок-схемний, алгебричний. Результатом алгебричного опису алгоритмів є математичне забезпечення обчислювальної системи, якою реалізуються формули алгоритмів. На відміну від відомих засобів опису математичного забезпечення комп’ютерних систем, використання відомої алгебри алгоритмів забезпечує точний опис, мінімізацію за кількістю дій (унітермів) та дослідження алгоритмів.
Операції алгебри алгоритмів викону-ються над унітермами, якими є окремі знаки та їхні послідовності. Унітерми, в залежності від конкретних чи абстрактних залежностей поділяються на предметні, наприклад (y = x, z = t2,..) і абстрактні (F(x,y) - абстрактна функція від двох змінних). Формули-алгоритми утворюються операціями над унітермами. Абстрактні алгоритми – формули з абстрактними унітермами. Заміною в абстрактних алгоритмах всіх абстрактних унітермів предметними утворюються моделі абстрактних алгоритмів.
Операціями алгебри алгоритмів є: секвентування, елімінування, паралелення, інвертування, циклічне секвентування, циклічне еліміну-вання, та циклічне паралелення. Операція секвентування використовується для опису послідовностей дій, елімінування – розгалужень в алгоритмах, паралелення – процесів, які виконуються одночасно, інвертування – зміни черговості виконання унітермів, циклічними операціями описуються цикли в алгоритмах.
Знаки операцій є специфічними і, як правило, їхні геометричні розміри є змінними і залежать від розмірів уніте-рмів над якими вони виконуються. Наприклад, у формулах:
довжина і висота знаку операції секвентування () є різними.
Крім того, при формуванні формул алгоритмів необхідно враховувати кеглі задаваних шрифтів унітермів, наявність/відсутність нижніх і (або) верхніх, розміщених з правої й лівої сторони, індексів унітермів, нелінійні співвідношення розмірів знаків операцій і взаємне розташування формул та знаків операцій.
Найбільш розповсюдженими універсальними системами комп’ютер-ного на-бору і редагування є такі як Microsoft Word 2003, Microsoft Visio 2003, Adobe InDesign CS2, CorelDraw X3, LaTex, MathCAD. Процес набору засобами моделей найбільш розповсюджених універсальних комп’ютерних систем виконується, але його практична реалізація супроводжується значною кількістю операцій, що робить їх застосування малоефективним.
Набір формул алгоритмів засобами моделі спеціалізованої системи МОДАЛ передбачає ручне задання початкових та кінцевих точок знаків операцій, що є не зручним та зменшує ефективність використання системи.
Редагування формул алгоритмів як засобами моделей універсальних, так і спеціалізованої комп’ютерної системи МОДАЛ реалізується, але не передбачає процесів автоматизованого формування формул алгоритмів на підставі вибраних кеглів унітермів, їхніх індексів та знаків операцій, немає згортання і розгортання формул алгоритмів. Тому створення і дослідження математичного та програмного забезпечення редактора формул алгоритмів з такими можливостями, реалізація яких підвищує рівень автоматизації набору і редагування формул алгоритмів, є актуальною науковою задачею.
Зв’язок роботи з науковими програмами, планами і темами. Дисертаційна робота пов’язана з виконанням держбюджетної науково-дослідної роботи “Моделювання редактора формул абстрактних алгоритмів” з номером державної реєстрації 0106U000967 в Українській академії друкарства. Участь автора полягала у створенні ієрархічно-модульної моделі редактора, синтезі, мінімізації і досліджені математичних моделей процесів автоматизованого формування і редагування формул абстрактних алгоритмів.
Мета і завдання дослідження. Метою роботи є створення математичного і програмного забезпечення редактора з підвищеним рівнем автоматизації набору і редагування формул алгоритмів.
Завдання дослідження. Для досягнення мети дослідження необхідно розв’язати такі задачі:
ь виконати аналіз математичного і програмного забезпечення процесів набору та редагування формул алгоритмів засобами універсальних і спеціалізованої комп’ютерних систем;
ь створити ієрархічно-модульну модель редактора формул алгоритмів;
ь виконати синтез та мінімізацію математичного забезпечення редактора;
ь побудувати і дослідити математичні моделі абстрактних алгоритмів редактора;
ь виконати програмну реалізацію та апробацію розробленого математичного забезпечення редактора.
Об’єкт дослідження – математичне і програмне забезпечення редактора формул алгоритмів.
Предмет дисертаційної роботи – ієрархічно-модульна модель редактора формул абстрактних алгоритмів, синтез, мінімізація і дослідження математичного забезпечення процесів автоматизованого адаптивного формування/редагу-вання, згортання/розгортання і вирізання/вставляння формул алгоритмів або їх фрагментів та структура даних редактора.
Методи дослідження. Алгебра алгоритмів використана для синтезу і мінімізації математичного забезпечення редактора, метод трансфінітної математичної індукції – для дослідження математичної моделі, комп’ютерні технології і алгоритмічні мови – для реалізації та апробації математичної моделі.
Наукова новизна одержаних результатів. В роботі на основі виконаних досліджень розв’язано наукову задачу синтезу і дослідження математичного та програмного забезпечення редактора формул алгоритмів. При цьому отримано такі нові наукові результати:
ь вперше створено ієрархічно-модульну модель редактора формул абстрактних алгоритмів, яка відрізняється наявністю модулів автоматизованого адаптивного формування/редагування, згортання/розгортання, вирі-зання/встав-лян-ня, заміни знаків операцій і орієнтації формул алгоритмів;
ь вперше синтезовано, мінімізовано і досліджено математичне забезпечення процесів набору і редагування формул алгоритмів, яке відрізняється автоматизованою генерацією формул алгоритмів з врахуванням заданих кеглів шрифтів, введених унітермів, розміщених з правої і лівої сторони верхніх та нижніх індексів унітермів, нелінійних співвідношень розмірів знаків операцій і позицій унітермів та знаків операцій;
ь вперше побудовано, мінімізовано і досліджено математичне забезпечення процесів згортання виділеного фрагмента або цілої формули алгоритму у згорнутий унітерм і розгортання згорнутих унітермів у формули, яке відрізняються автоматичною адаптацією знаків операцій до унітермів і знаків операцій не згорнутої частини формули до згорнутого унітерму;
ь вперше створено, мінімізовано і досліджено математичне забезпечення процесів копіювання, вирізання та вставляння формул алгоритмів, яке відрізняються автоматичною адаптацією знаків операцій до унітермів і знаків операцій формул, що утворюються після вирізання та вставляння;
ь вперше розроблено модель структури даних редактора, яка відрізняється наявністю унітермів верхніх і нижніх індексів, секвентних областей значень, ознак циклів з перед- та післяумовами, системних назв та вхідних і вихідних параметрів.
Практичне значення одержаних результатів. Програмно реалізований редактор формул абстрактних алгоритмів, у порівнянні з відомими системами, забезпечує підвищення рівня автоматизації процесів формування, згортання, розгортання, копіювання, вирізання і вставляння формул абстрактних алгоритмів. Тим самим зменшуються трудомісткість, затрати робочого і комп’ютерного часу на творення і редагування формул абстрактних алгоритмів і їхніх моделей.
Отримані у дисертаційній роботі результати використані у навчальному процесі Української академії друкарства. Зокрема при викладанні таких навчальних дисциплін, як “Основи систем автоматизації проектувальних робіт” і “Проектування комп’ютерно-інтегрованих технологічних процесів і виробництв”, а також в дипломних проектах й магістерських роботах. Створений ієрархічно-модульний принцип побудови, синтезовані, мінімізовані за кількістю унітермів абстрактні алгоритми редактора та їхні математичні моделі використані при виконанні держбюджетної теми Б 400 – 2006 з номером державної реєстрації 0106U000967. Редактор формул алгоритмів «АбстрактАл» впроваджений на ТзОВ «Бескид Біт», де використовувався для набору та редагування формул алгоритмів.
Особистий внесок здобувача. Всі теоретичні і практичні результати, висновки і рекомендації отримано автором особисто.
З опублікованих 10 наукових праць 7 праць написано без співавторів.
У публікаціях, написаних у співавторстві, здобувачу належать: [5] – ієрархічно-модульний принцип побудови редактора абстрактних алгоритмів та їхніх моделей; [6,10] – модель середовища АбстрактАлу для функціонування комп’ютерної бібліотеки абстрактних алгоритмів та їхніх моделей.
Апробація результатів дисертації. Основні наукові результати дисертаційної роботи доповідались та отримали схвалення на: Міжнародних наукових конференціях “Комп’ютерні технології друкарства” (Львів, УАД, 2004-2006); The VIII-th international conference “The experience of designing and application of CAD systems in microelectronics (CADSM’2005)” (Lviv-Polyana, 2005); The international conference “Modern problems of radio engineering, telecommunications and computer science (TCSET’2006)” (Lviv-Slavske, 2006).
Публікації. За результатами наукових досліджень опубліковано 10 робіт із них 6 у фахових наукових виданнях і 4 – тези доповідей у матеріалах міжнародних конференцій.
Структура і обсяг дисертації. Дисертаційна робота складається з вступу, чотирьох розділів, висновків, списку використаних джерел із 110 найменувань та 2 додатків. Загальний обсяг роботи – 131 сторінки. Основний зміст роботи викладено на 117 сторінках. Робота містить 28 рисунків і 3 таблиці.
Основний зміст
У вступі обґрунтовано актуальність роботи, сформульовано мету та визначено основні задачі та методи дослідження, наведено наукову новизну та практичну цінність наукових результатів. Висвітлено питання реалізації, апробації та впровадження наукових результатів.
У першому розділі проведено аналіз математичного і програмного забезпечення процесів набору і редагування формул алгоритмів засобами найбільш розповсюджених універсальних та спеціалізованої комп’ютерних систем.
В результаті проведеного аналізу математичного і програмного забезпечення процесів набору та редагування формул алгоритмів встановлено, що виконання цих процесів засобами відомих універсальних і спеціалізованої комп’ютерних систем є складним, трудомістким і малоефективним. Сформульовано наукову задачу дослідження. Обґрунтовано вибір математичних засобів для побудови математичної моделі редактора.
У другому розділі синтезовано абстрактні алгоритми процесів адаптації, згортання і розгортання, копіювання, вирізання та вставляння формул.
Одним з найважливіших процесів системи автоматизованого редагування формул абстрактних алгоритмів є процес адаптації.
А-д--ап-та--цією -на--зи-ва-ти--м-емо п-роц-ес зміни розмірів знаків операцій в залежності від розмірів, розташування (зверху/знизу), орієнтації (вертикальна/горизонтальна), кегля, верхніх та нижніх індексів унітермів, а також знаків операцій алгебри алгоритмів.
Задачі адаптації:
а) в залежності від розмірів шрифта
де l0 – довжина формули до адаптації, la – довжина вложеної формули, l1 – довжина формули після адаптації, la’ – довжина вложеної формули після зміни кегля, 10, 20, 30, 40 – точки побудови знаку операції до зміни розмірів знаку, 11, 21, 31, 41 – точки побудови знаку операції після зміни розмірів знаку;
б) з врахуванням індексів
де l – діапазон зміни розміру знаку операції по горизонталі, b – діапазон зміни розташування знаку операції по вертикалі, d1 – діапазон зміни координат розташування формули по горизонталі, d2 – діапазон зміни розмірів формули по горизонталі, d3 – діапазон зміни координат розташування формули по вертикалі;
в) з врахуванням наявності вертикальної або горизонтальної орієнтації знаків операцій;
де L1 – довжина формули, L2 – довжина вложеної формули, L1’ - довжина формули після адаптації, L2’ – довжина формули після зміни орієнтації;
г) в залежності від розташування унітермів;
де Y – відстань по висоті від знаку операції до унітерму при розташуванні зверху, Y’ – відстань по висоті від знаку операції до унітерму при розташуванні знизу.
На рис.1(а) наведено три складові формули алгоритму: 1 – базовий знак операції секвентування, 2 – перший вложений унітерм А, 3 – другий вложений унітерм F(x, y). Процес адаптації складається з таких етапів: а) набір трьох складових формули алгоритму (базового знаку операції та вложених формул); б) переміщення першого вложеного унітерму (2) під базовий знак операції (1); в) ввід розділювача (« , » або « ; »); г) переміщення другого вложеного унітерму (3) під базовий знак операції (1); д) зміна розмірів базового знаку операції (1) в залежності від геометричних параметрів вложених уніткрмів (2) і (3).
Зміна розмірів знаку операції в залежності від геометричних параметрів унітермів в свою чергу складається з таких процесів (див. рис. 2):
1) ідентифікація базової формули; 2) зчитування поточних початкових і кінцевих точок знаку операції; 3) адаптація базового знаку операції в залежності від типу ідентифікованого знаку операції (секвентування, елімінування, паралелення та циклічних операцій).
Процес адаптації базового знаку операції секвентування враховує нелінійне співвідношення його довжини і ширини та залежить від розмірів шрифта унітермів, наявності чи відсутності індексів, типу орієнтації знаків операцій та від розташування вложених формул.
На рис. 3 зображено адап-тацію базового знаку операції секвентування з врахуванням гео-мет-----рич--них параметрів вложених унітермів, де x1, y1, x2, y2, x3, y3, x4, y4 – абсциси і ординати першої, другої, третьої та четвертої точок побудови знаку операції секвентування до адаптації, x1, y1, x2, y2, x3, y3, x4, y4 – абсциси і ординати першої, другої, третьої та четвертої точок побудови знаку операції секвентування після адаптації, l – довжина знаку операції секвентування до адаптації, la – довжина знаку операції секвентування після адаптації.
Синтез абстрактного алгоритму процесу адаптації базового знаку операції секвентування виконано секвентним методом, який передбачає два етапи – синтез секвенцій і синтез елімінувань.-
Синтез секвенцій. Абстрактний -алгоритм а-д-ап--тації -ба--зо--вого з--наку о-пе--рації --пер--ед-бачає:
а) секвенції S1 і S2 обчислення координат першої та другої точок:
,
де -f – унітерм, який описує взаємозв’язок між висотою і довжиною знаку операції секвентування, P1(x1, x1), P1(y1, y1), P1(x2, x1+la), P1(y2, y1+f(la, c1)) - унітерми присвоєння абсцис і ординат першої та другої точок знаку операції секвентування;
б) секвенції S3 і S4 обчислення координат третьої та четвертої точок:
де P1(x3, x3), P1(y3, y1+f(la, c1)), P1(x4, x1+la), P1(y4, y4) - унітерми присвоєння абсцис і ординат третьої і четвертої точок знаку операції секвентування.
Процес обчислення геометричних параметрів знаку операції секвентування для його горизонтальної орієнтації описується так:
Процес обчислення геометричних параметрів знаку операції при його вертикальній орієнтації описується аналогічно:
Синтез елімінувань. Процес перевірки типу орієнтації знаку операції секвентування описується таким елімінуванням:
де u1 – умова типу орієнтації знаку операції секвентування.
Підставивши у K3 замість S5 і S6 їхні секвенції та виконавши на підставі властивостей операцій алгебри алгоритмів мінімізацію за кількістю унітермів, отримаємо такий абстрактний алгоритм процесу адаптації базового знаку операції секвентування:
Абстрактний алгоритм адаптації будь-якої базової формули до вложеної має такий вигляд:
де P1(i,i0) – унітерм присвоєння змінній i значення порядкового номера i0 будь-якого базового знаку операції; К1, К2, К3, К4, К5, К6 – алгоритми адаптації базових знаків паралелення, елімінування, секвентування, циклічного секвентування, циклічного елімінування і циклічного паралелення; u1, u2, u3, u4, u5, u6 – умови типу операції базових знаків (паралелення, елімінування, секвентування, циклічного секвентування, циклічного елімінування і циклічного паралелення).
Загальний абстрактний алгоритм процесів адаптації будь-яких базових формул до вложених і вложених до базових має такий вигляд:
де ha – довжина знаку операції секвентування після адаптації, Z1 , Z2 , Z3 , Z4 – змінні адаптованих геометричних параметрів формул, F1 – алгоритм адаптації будь-якої базової формули до вложеної, F2 – алгоритм адаптації вложених формул до базової, u1 – умова типу орієнтації знаків операцій, u2 – умова першої та другої вложених формул.
Результатом синтезу і мінімізації абстрактного алгоритму редактора є формула (2).
У третьому розділі побудовано та досліджено математичне забезпечення процесів набору, адаптації, згортання та розгортання, обчислення геометричних розмірів унітермів та формул, знищення, копіювання та вставляння формул абстрактних алгоритмів. Математичні моделі побудовані заміною абстрактних унітермів предметними та заданням секвентних областей значень змінних і унітермів. Дослідження моделі процесів набору і редагування здійснено методом математичної індукції.
Замінивши у формулі (1) абстрактний унітерм предметним унітермом присвоєння (P1(X1, x1) на X1=x1, P1(Y1, y1) на Y1=y1 і т.д.) і унітерм f(la , c1) предметним унітермом @vla + 3, де @vla – ціла частина кореня квадратного від la, унітерм f(ha , c1) предметним унітермом @vha + 3, де @vha – ціла частина кореня квадратного від ha, а абстрактний умовний унітерм u1 предметним унітермом порівняння (v=0)-?, де v – змінна орієнтації знаку операції (при горизонтальній орієнтації v = 0 і при вертикальній v = 1) і задавши (при v=0) секвентні області значень Q1,..,Q5 змінним x1 , y1 , x2 , y2 , x3 , y3 , x4 , y4 , x1 , y1 , x2 , y2 , x3 , y3 , x4 , y4 отримаємо модель абстрактного алгоритму адаптації базового знаку операції секвентування, наведену формулою (3).
де N1max = N – la – 5 - верхня межа області значень Q1, N2max = N –(@vla+3)– 5 – верхня межа області значень Q2, N3max = N4max =N – 5 - верхні межі областей значень Q3, Q4, Q5, N = 2147483648 – максимальне можливе значення для всіх змінних без врахування особливостей будови знаку операції секвентування, x11 , x12 , y11 , y12 – перше і друге значення координат x1 , y1.
Дослідження опису моделлю обчислення координат для адаптації знаку операції горизонтального секвентування в залежності від координат неадаптованого знаку і довжини вложених формул виконано з використанням методу трансфінітної математичної індукції.
Модель, яка подана формулою (3) має такі змінні: x1 , y1 , x2 , y2 , x3 , y3 , x4 , y4 , x1 , y1 , x2 , y2 , x3 , y3 , x4 , y4 , la , ha , v. Як видно з формули x1 = x1 = x3 = x3, y1 = y1 = y4 = y4, а значення x2 , x4 , y2 , y3 обчислюються із значень змінних x1 , y1 , la. Отже, формула (3) має 3 незалежні змінні, а всі решта є рівні їм або є функціонально залежні від них. Тому дослідження має бути виконане за цими трьома змінними.
Нехай x1 = i < p О Q1 , y1 = j < q О Q2 , la = k < r О Q3 , а формула (3) описує обчислення координат для адаптації знаку операції секвентування.
Встановимо чи моделлю (3) описується адаптація знаку операції секвентування при горизонтальній орієнтації знаку (v = 0) і значенні змінних la = k+1 = r. Для цього у формулу (3) підставляємо такі значення x1 = i , y1 = j, la = k+1. Отримаємо вираз:
Як видно з отриманої формули, при зміні довжини унітермів на 1 координати для знаку операції горизонтального секвентування X2 і X4 також змінюються на 1.
Нехай для @vk = e = 2q. При k + 1 можливі 2 випадки:
ь результатом обчислення квадратного кореня не є ціле число і координати Y2 і Y3 залишаються не змінними;
ь результатом обчислення квадратного кореня е ціле число і координати Y2 і Y3 збільшуються на величину, яка враховує нелінійну залежність висоти формули від довжини вложених формул.
На підставі трансфінітної математичної індукції стверджуємо, що формула (3) описує адаптацію знаку операції секвентування для всіх можливих значень змінної la. Аналогічним чином досліджується для решти змінних.
Дослідження процедури обчислення координати знаку секвентування при вертикальній орієнтації виконується аналогічно.
На основі синтезованої моделі редактора формул абстрактних алгоритмів розроблено ієрархічно-модульну модель редактора, яку представлено нижче у вигляді схеми. Ця модель редактора формул абстрактних алгоритмів полягає у введені з клавіатури унітермів, виборі знаків операцій з панелі інструментів та автоматичному генеруванні формул алгоритмів. Система поділяється на три рівні. Ієрархічно-модульна модель редактора зображена на рис.4.
Перший рівень включає в себе ядро редактора «АбстрактАл».
На другому рівні структурної схеми редактора знаходяться такі модулі: функціональний модуль, модуль організаційних даних, модуль додаткових операцій, системний модуль, модуль генерування унітерму.
Третій рівень поділяється на наступні модулі:
ь модуль даних редактора – розділ редактора, в якому зберігається структура даних та інші параметри редактора;
ь інструментальний модуль редактора, який в свою чергу поділяється на модулі генерування знаків операцій, ідентифікації та переміщення;
ь модуль редагування знаків операцій, який поділяється на модулі зміни орієнтації формул алгоритмів, заміни знаків операцій, згортання і розгортання формул алгоритмів та адаптації формул алгоритмів;
ь модуль ініціалізації редактора;
ь інформаційний модуль – методики щодо користування редактором;
ь модуль ресурсних операцій – зберігання і зчитування параметрів знаків операцій;
ь модуль налаштування робочого поля – задання параметрів редактора (колір канви робочого поля, параметри шрифту системи та ін.);
ь модуль конвертування – представлення абстрактного алгоритму у вигляді відомих графічних форматів;
ь функціональний модуль – виконання процесів адаптації, згортання, розгортання, копіювання, вирізання та вставляння формул алгоритмів;
ь модуль генерування унітермів –засоби для набору та редагування унітермів.
ь модуль редагування знаків операцій включає в себе операції переміщення, зміну орієнтації формул алгоритмів, заміну знаків операцій, згортання і розгортання та модуль адаптації формул алгоритмів.
Ці модулі включають в себе такі операції, як відображення інформації про вибраний знак операції чи унітерм. Модуль вводу нових параметрів знаку операцій чи унітермів. Модуль генерування унітермів включає в себе такі модулі: модуль генерації унітермів та модуль редагування унітермів.
У четвертому розділі описано програмну реалізацію інструментальними засобами алгоритмічної мови Borland Delphi 2006 розроблених та досліджених математичних моделей процесів набору і редагування формул абстрактних алгоритмів. Перед реалізацією редактора проаналізовано велику кількість середовищ розробки, серед яких: Borland Builder C++ 7.0, Microsoft Visual C#. Проаналізувавши поставлені задачі, встановлено, що для її реалізації необхідно використовувати середовище розробки Borland Developer Studio 2006 (Borland Delphi 2006).Програма редактора названа АбстрактАл, і забезпечує автоматизовану генерацію та адаптацію формул абстрактних алгоритмів із збереженням специфіки будови знаків операцій. Інтерфейс користувача редактора АбстрактАл зображено на рис. 5. Інтерфейс складається з:
1 – панель інструментів; 2, 3 – робоча зона;
4 – вікно редагування формул абстрактних алгоритмів;
5 – деревоподібна структура формули абстрактного алгоритму;
6 – статистика формули.
Комп’ю-терні системи
Кількість
операцій
при наборі: | АбстрактАл |
Microsoft
Word 2003 | CorelDRAW 12 | МОДАЛ
Кількість операцій | Змен-шено (раз) | Кількість операцій | Змен-шено (раз) | Кількість операцій | Змен-шено (раз)
Унітермів | 75 | 110 | 1,4 | 117 | 1,6 | 99 | 1,32
Знаків операцій секвентуван-ня | 45 | 96 | 2,1 | 85 | 1,9 | 60 | 1,33
Знаків операцій елімінування | 36 | 30 | 0,8 | 36 | 1 | 40 | 1,1
Всього алгоритму | 156 | 236 | 1,5 | 238 | 1,5 | 199 | 1,3
Таблиця .Оцінка кількості операцій, виконаних при наборі абстрактного алгоритму розв’язку квадратного рівняння
висновки
У дисертаційній роботі розв’язано актуальну наукову задачу синтезу і дослідження математичного і програмного забезпечення редактора формул алгоритмів з підвищеним рівнем автоматизації процесів набору і редагування формул алгоритмів та при цьому отримано такі результати:
1. Аналізом математичного і програмного забезпечення відомих універсальних і спеціалізованої комп’ютерних систем встановлено, що їхніми засобами процеси набору виконуються, але значною кількістю операцій, а процеси редагування відбуваються без автоматичної адаптації знаків операцій до унітермів та знаків операцій формул алгоритмів при виконанні згортання/розгортання та вирізання/вставляння частин чи цілих формул алгоритмів.
2. Мінімізацією алгоритмів процесів адаптації, згортання, розгортання зменшено кількість унітермів в середньому у 2 рази.
3. Математичне забезпечення процесів згортання виділеного фрагмента або цілої формули алгоритму в унітерм і розгортання згорнутих унітермів у формули програмно реалізовані і забезпечили більшу наочність і компактність формул алгоритмів.
4. Реалізовані моделі алгоритмів процесів комп’ютерного копіювання, вирізання та вставляння формул алгоритмів зменшили затрати робочого і комп’ютерного часу на редагування формул алгоритмів.
5. Програмна реалізація розробленої ієрархічно-модульної моделі редактора підвищила рівень автоматизації процесів набору і редагування формул алгоритмів, кількість виконуваних операцій для реалізації цих процесів зменшена в 1,5-2 рази.
6. Реалізація створеної математичної моделі структури даних редактора стала основою створення комп’ютерної бібліотеки формул алгоритмів і підсистеми автоматичної генерації кодів програм з моделей абстрактних алгоритмів.
7. Редактор формул абстрактних алгоритмів (АбстрактАл) програмно реалізований і впроваджений у навчальний процес Української академії друкарства та використаний для проведення занять і виконанні дипломних й магістерських робіт. Створений ієрархічно-модульний принцип побудови, синтезовані, мінімізовані за кількістю унітермів абстрактні алгоритми редактора та їхні математичні моделі використані при виконанні держбюджетної теми Б 400 – 2006 з номером державної реєстрації 0106U000967. Редактор формул алгоритмів «АбстрактАл» впроваджений на ТзОВ «Бескид Біт», де використовувався для набору та редагування формул алгоритмів.
Публікації за темою дисертаційної роботи
1. Василюк А. Моделювання процесу генерації формул абстрактних алгоритмів / А. Василюк // Комп’ютерні технології друкарства : Збірник наукових праць. – Львів: УАД, 2005. - №13. – С. 136-144.
2. Василюк А. Абстрактний алгоритм редактора формул абстрактних алгоритмів «АбстрактАл» / А. Василюк // Комп’ютерні технології
друкарства : Збірник наукових праць. – Львів: УАД, 2006. - №16. – С. 99 –108 .
3. Василюк А. Моделювання процесу перетворення формул абстрактних алгоритмів / А. Василюк // Квалілогія книги. –Львів: УАД, 2005. – № 8. – С. 58-63.
4. Василюк А. Моделювання процесів синтезу математичних моделей формул абстрактних алгоритмів / А. Василюк // Комп’ютерні технології друкарства : Збірник наукових праць. – Львів: УАД, 2006. – №15. – С.133 – 143.
5. Овсяк В. Принцип побудови підсистеми редагування формул абстрактних алгоритмів / В. Овсяк, А. Василюк // Комп’ютерні технології друкарства : Збірник наукових праць.– Львів: УАД, 2004. – №12. – С. 137-145.
6. Овсяк В. Принципи побудови комп’ютерної бібліотеки абстрактних алгоритмів Коба / В. Овсяк, А. Василюк, О. Яремчишин // Комп’ютерні технології друкарства : Збірник наукових праць.- Львів: УАД, 2006. – №15. – С.85 – 95.
7. Vasyluk A. Design of abstract algorithms of calculation of height and width of inserted formulas / A. Vasyluk // Proc. of the VIII-th intern. Conference “The experience of designing and application of CAD systems in microelectronics (CADSM’2005)”. –Lviv-Polyana: Lviv Polytechnic National University, 2005. – P. 416-417.
8. Vasyluk A. Modified generalized data structure of the system of set and editing of formulas of abstract algorithms / A. Vasyluk // Proc. of the intern. conference “Modern problems of radio engineering, telecommunications and computer science (TCSET’2006)”. – Lviv-Slavske: Lviv Polytechnic National University, 2006. – P. 101-102.
9. Vasyluk A. Structure of algorithm of calculation of height and width of the unitherm A. Vasyluk // Proc. of the IX-th intern. conference “The experience of designing and application of CAD systems in microelectronics (CADSM’2007)”. –Lviv-Polyana: Lviv Polytechnic National University, 2007. – P. 315-316.
10. Ovsyak V. Automation of the Process of Search of the Algorithms’ Formulae in the Library “КоБА” / V. Ovsyak, A. Vasyluk, O. Yaremchyshyn // Proc. of the IX-th intern. Conference “The experience of designing and application of CAD systems in microelectronics (CADSM’2007)”. –Lviv-Polyana: Lviv Polytechnic National University, 2007. – P. 418-420.
АНОТАЦІЇ
Василюк А. С. Підвищення ефективності математичного і програмного забезпечення редактора формул алгоритмів. – Рукопис.
Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 01.05.03 – математичне та програмне забезпечення обчислювальних машин і систем. – Національний університет “Львівська політехніка”, Львів, 2008.
Дисертаційна робота присвячена створенню ієрархічно-модульної моделі редактора формул, яка описує процеси адаптації, згортання, розгортання, вирізання, копіювання та вставляння формул алгоритмів, реалізація якого забезпечила підвищення рівня автоматизації, зменшення кількості дій для набору та редагування формул алгоритмів. Синтезовано і досліджено математичне забезпечення процесів адаптації вложених формул до базової формули, згортання та розгортання формул, копіювання, вирізання і вставляння формул алгоритмів. Розроблено модель структури даних, яка містить верхні і нижні індекси унітермів, секвентні області значень унітермів, ознаки циклів з перед- та післяумовами, системні назви унітермів та вхідні і вихідні параметри унітермів та використовується для введення, виведення, збереження і обміну даними з іншими прикладними системами. Математичне забезпечення програмно реалізовано і апробовано.
Ключові слова: математична модель, математичне забезпечення, дослідження моделі, унітерм, абстрактні алгоритми, моделі алгоритмів, програмне забезпечення, редактор формул алгоритмів.
Василюк А. С. Повышение эффективности математического и программного обеспечения редактора формул алгоритмов. – Рукопись.
Диссертация на соискание учёней степени кандидата технических наук по специальности 01.05.03 – математическое и программное обеспечение вычислительных машин и систем. – Национальный университет “Львовская политехника”, Львов, 2008.
Диссертационная работа посвящена созданию иерархически модульной модели редактора формул, которая описывает процессы адаптации, свертывания, развертывания, вырезания, копирования и вставки формул алгоритмов, реализация которого обеспечила повышение уровня автоматизации, уменьшения количества действий для набора и редактирования формул алгоритмов. Синтезировано и исследовано математическое обеспечение процессов адаптации вложеных формул к базовой формуле, свертывания и развертывания формул, копирования, вырезания и вставки формул алгоритмов. Разработана модель структуры данных, которая содержит верхние и нижние индексы унитермов, секвентные области значений унитермов, признаки циклов с пред- и послеусловиями, системные названия унитермов, входные и исходные параметры унитермов и используется для ввода, вывода, сохранения и обмена данными с другими прикладными системами. Математическое обеспечение программно реализовано и апробировано.
Ключевые слова: математическая модель, математическое обеспечение, исследование модели, унитерм, абстрактные алгоритмы, модели алгоритмов, программное обеспечение, редактор формул алгоритмов.
Vasyluk A. S. Increase of efficiency of the mathematical and programmatic providing of editor of formulas of algorithms. Manuscript.
Thesis for a candidate’s degree on technical science by specialty 01.05.03 – mathematical and programmatic providing of calculable machines and systems.–Polytechnic National University, Lviv, 2008.
Dissertation work is devoted to the creation of hierarchical module model of formula editor, which difference is that the mathematical providing describes the processes of adaptation, collapsing, expanding, cutting, copying and pasting of algorithm formulas, realization of which provided the increase of automation level, diminishing of action amount for typing and editing the algorithm formulas. The mathematical providing of data structures is developed, which contains the variables of over and below indexes of unitherms, sequence areas of unitherms values, signs of loop with before- and after condition, system names of unitherms and input and output parameters of unitherms and is used for inputting and outputting, saving and data exchange with other applications. The mathematical providing of adaptation processes of inserted formulas is synthesized and researched to the base formula, collapsing and expanding of formulas, copying, cutting and pasting of algorithm formulas. The mathematical providing is programmatically realized.
Construction principle of formula editor of algorithms, which consists in a two-level hierarchical modular construction, realization of which would provide implementation of adaptation processes, collapsing and expanding, copying, cutting and pasting of abstract formula algorithms, is first developed.
The mathematical providing of typing processes and editing the algorithm formulas, which is adaptation described by, collapsing and expanding of abstract algorithm formulas, copying, cutting, pasting and deleting of algorithm formulas, is synthesized and minimized after the amount of unitherm algorithms.
The mathematical providing of data structure is developed, which includes types, orientation, colour, thickness of line, geometrical parameters of operation signs and is used for inputting and outputting, saving and data exchange with other application
The mathematical providing of typing processes, adaptation, collapsing, expanding, deleting of abstract algorithm formulas, synthesis of mathematical models, calculation of unitherms and abstract algorithm formulas geometrical sizes is built.
By research of the higher described mathematical providing the method of mathematical induction yet before practical realization and approbation of models discovered and the corrected are allowed on the stage of synthesis of their error structure, that is why expenses on planning of editor are diminished.
Main window, mathematical providing of typing processes and editing of abstract algorithm formulas, adaptation, collapsing, expanding are practically realized by the tools of Borland Delphi 2006 and approved at a typing and layout of algorithm formulas.
The authenticity of the realized models are confirmed by experimental researches.
The analysis of editor using efficiency of the АбстрактАл is conducted, which proved that amount of operations for realization of typing processes and editing in this system in 1,5-2 times less ,than in the universal systems and in the specialized system МОДАЛ,
Keywords: mathematical model, mathematical providing, research of model, unitherm, abstract algorithms, models of algorithms, software, editor of formulas of algorithms.
