НАЦІОНАЛЬНА АКАДЕМІЯ НАУК УКРАЇНИ

ІНСТИТУТ ПРОБЛЕМ МАТЕМАТИЧНИХ МАШИН І СИСТЕМ

ШВАЛЮК Тетяна Миколаївна

УДК 681.086

УПРАВЛІННЯ ПРОЦЕСОМ СИМВОЛЬНИХ ПЕРЕТВОРЕНЬ

ПРИ РОЗВ’ЯЗАННІ ЗАДАЧ КОМП'ЮТЕРНОЇ АЛГЕБРИ

01.05.03 – Математичне та програмне забезпечення

обчислювальних машин і систем

АВТОРЕФЕРАТ

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

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

Київ - 2007

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

Робота виконана в Інституті проблем математичних машин і систем НАН України, м. Київ.

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

старший науковий співробітник

Клименко Віталій Петрович,

Інститут проблем математичних машин і систем НАН

України, заступник директора з наукової роботи

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

старший науковий співробітник

Теслер Геннадій Семенович,

Інститут проблем математичних машин і систем НАН

України, головний науковий співробітник

кандидат фізико-математичних наук,

старший науковий співробітник

Лялецький Олександр Вадимович,

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

імені Тараса Шевченка, факультет кібернетики,

завідуючий лабораторією

Захист відбудеться “ 23 ” січня 2008 року о 14 годині на засіданні спеціалізованої вченої ради Д26.204.01 в Інституті проблем математичних машин і систем НАН України за адресою: 03187, Київ-187, проспект Академіка Глушкова, 42.

З дисертацією можна ознайомитись у бібліотеці Інституту проблем математичних машин і систем НАН України за адресою: 03187, Київ-187, проспект Академіка Глушкова, 42.

Автореферат розісланий “ 19 ” грудня 2007 року.

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

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

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

Актуальність теми. Рівень сучасних наукових і технічних проблем різко підвищує роль математичного моделювання, яке часто звільняє від дорогих, довготривалих і менш точних натурних випробувань. Сучасні високі технології, звичайно, вимагають моделювання й вивчення нестаціонарних процесів і складних об'єктів, які характеризуються нелінійними, розривними й швидко коливними залежностями. Їхнє дослідження вимагає застосування розвиненого математичного апарату. Це приводить до необхідності розширення спектру застосовуваних методів їхнього рішення за рахунок використання аналітичних і чисельно-аналітичних перетворень. Тому актуальною є задача створення й удосконалення орієнтованих на такі методи систем програмування. З'являються все нові версії таких систем комп'ютерної алгебри (СКА), як АНАЛІТИК, AXІOM, MAPLE, MATHEMATІCA, REDUCE, які постійно вдосконалюються разом із ростом технічних характеристик ЕОМ.

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

Починаючи з 60-х років, під керівництвом академіка В.М. Глушкова в Інституті кібернетики НАН України розроблялися високоінтелектуальні СКА сімейства АНАЛІТИК, які апаратно реалізовувалися на ЕОМ серії МІР (АНАЛІТИК, АНАЛІТИК-74) та спеціалізованих машинах СМ-1410 та ЄС-2680 (АНАЛІТИК-79). У розвиток теорії та практики засобів СКА великий вклад внесли С.О. Абрамов, Ю.В. Благовєщенський, В.Г. Боднарчук, Т.О. Грінченко, Ю.В. Капітонова, В.П. Клименко, О.А. Летічевський, О.Л. Ляхов, Б.О. Попов, А.О. Стогній, Г.С. Теслер, Ю.С. Фішман та інш. З кінця 80-х років програмно реалізовувалися на сучасних ПЕОМ АНАЛІТИК-89, АНАЛІТИК-91, АНАЛІТИК-93, АНАЛІТИК-2000. Мови цього сімейства орієнтовані на застосування аналітичних і чисельно-аналітичних методів як в автоматичному, так і в інтерактивному режимах, а також обчислення з довільною розрядністю.

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

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

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

Зв'язок роботи з науковими програмами, планами, темами. Робота виконана в рамках науково-дослідних робіт, що виконувалися в Інституті проблем математичних машин і систем Національної академії наук України відповідно до координаційних планів “Створення наукових засад та розробка ефективних методів, алгоритмів і інструментальних засобів математичного моделювання складних об'єктів”, ДР №0198U000397, “Математичне моделювання в радіолокації, дефектоскопії, акустиці та механіці з використанням методів комп'ютерної алгебри”, ДР №0100U000811.

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

- визначити “вузькі місця” в організації обчислювального процесу СКА для автоматичного рішення задач;

- розробити методи й засоби підвищення ефективної продуктивності СКА;

- розробити розвинену систему розпізнавання функціональних та структурних властивостей об'єктів мови СКА;

- розробити апарат управління символьними перетвореннями;

- виконати перевірку запропонованих засобів і методів на практиці.

Об'єкт дослідження: процес символьних перетворень.

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

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

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

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

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

- вперше розроблене й обґрунтоване застосування нових ефективних функцій та операторів мови КА, пов'язаних із багаторівневою ієрархічною структурою;

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

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

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

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

- запропонований та реалізований універсальний апарат застосування формул з об'єктами більшої узагальненості.

Практичне значення одержаних результатів. На основі теоретичних і практичних досліджень була вирішена задача по створенню і програмній реалізації алгоритмічної мови нового покоління з високим рівнем інтелекту АНАЛІТИК-2000 (А-2000), яка забезпечує підвищення продуктивності праці користувача. Мова орієнтована на реалізацію аналітичних і чисельно-аналітичних методів рішення наукових і прикладних задач. Апарат роботи з раціональними дробами й числами з довільною довжиною мантиси збільшує ефективність застосування числових методів і точність отриманих результатів. Мова містить апарат адаптації до різних класів задач за рахунок включення нових операцій і функцій. Вона максимально наближена до загальноприйнятої мови математики.

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

СКА АНАЛІТИК-2000 впроваджена в Полтавському національному технічному університеті ім. Юрія Кондратюка, в Харківському національному університеті ім. В.Н. Каразіна, в Харківському національному університеті радіоелектроніки та інш.

Особистий внесок здобувача. Усі основні результати дисертаційної роботи отримані автором самостійно.

У публікаціях, які написані у співавторстві, автору належать:

у роботах [2, 4, 8] обґрунтування нового типу даних і базових функцій СКА А-2000, у роботах [1, 3, 6, 7, 9] - розробка та програмна реалізація алгоритмів.

Апробація результатів дисертації. Основні положення й результати дисертації доповідалися на 2-й Міжнародній науково-практичній конференції “Интернет-образование-наука-2000” (ІOH-2000, Вінниця, 2000), на 4-му Сибірському конгресі по прикладній та індустріальній математиці, присвяченому пам'яті М.А. Лаврентьєва (ІНПРІМ-2000, Росія, Новосибірськ, 2000). Матеріали дисертації обговорювалися на засіданнях наукового семінару “Аналітичні й символьні обчислення на ЕОМ” в Інституті проблем математичних машин і систем НАН України.

Публікації. Основні результати роботи викладено в 9 наукових працях, з яких 7 статей опубліковані у фахових виданнях, рекомендованих ВАК України для спеціальності 01.05.03. З них одна одноосібна.

Структура й обсяг дисертації. Дисертація складається із вступу, чотирьох розділів, висновків, списку використаної літератури з 103 найменувань і додатків. Обсяг дисертації становить 128 сторінок основного тексту, включаючи 6 таблиць та 13 рисунків.

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

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

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

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

Перші практично значимі роботи з автоматизації чисельно-аналітичних методів велися фізиками-теоретиками й фахівцями з небесної механіки. Вони ж були творцями перших спеціалізованих, а потім перших універсальних СКА. Одними з перших загальнодоступних мов того періоду можна вважати FORMAC, REDUCE. До того ж часу відноситься поява машин серії МІР. СКА цих ЕОМ включали універсальні мови сімейства АНАЛІТИК і були орієнтовані на реалізацію чисельно-аналітичних методів.

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

Принципова відмінність мов сімейства АНАЛІТИК від мов зарубіжних СКА полягає в тому, що управління процесом обчислень визначається не типом даних, а спеціальними режимними операторами й функціями, які діють на всю програму або її частину. Функції мов сімейства АНАЛІТИК визначаються досить узагальнено, й вибір потрібної гілки в реалізуючій функцію процедурі задається за допомогою певних режимних засобів. Хоча іноді це приводить до деякого падіння швидкодії, але такий підхід дозволяє обмежитися відносно невеликою кількістю функцій і приділити основну увагу підвищенню інтелекта мов СКА (зокрема, апарату розпізнавання функціональних та структурних властивостей даних). Все це забезпечує лаконізм та “прозорість” програм, спрощує їх налагодження й полегшує освоєння мови. Відзначимо, що управління обчисленнями в зарубіжних СКА (AXIOM, MAPLE, MATHEMATICA та інш.) в основному задається типами даних, що приводить до постійного збільшення числа функцій. Це число в ряді систем досягло багатьох тисяч і часто шокує користувача своєю неоглядністю.

Можливості сучасних комп'ютерів і застосовуваних методів вимагають нового усвідомлення властивостей СКА й тенденцій їхнього подальшого розвитку. Процедури КА визначаються на виразах мови, які вважаються основними об'єктами СКА. Такі вирази аналогічні виразам математичного аналізу і, звичайно, будуються зі змінних, чисел, дужок, укажчиків функцій та операцій. Тим часом, більш глибоке дослідження задач і алгоритмів, які реалізують чисельно-аналітичні методи, приводить до висновку, що фактично у процесі розв'язування, явно або неявно, відбувається маніпулювання з об'єктами більшої узагальненості. В А-2000 символ вектора “,” і символ тексту “'” також розглядаються як операції. При всій розмаїтості об'єктів СКА найбільш характерним для них є те, що вони містять змінні, які іменують подібні об'єкти. Така впорядкована система зчеплених значеннями змінних виразів утворює багаторівневу ієрархічну структуру. В А-2000 процедура підстановки значень змінних також розглядається як операція, символом якої є “[”. Така інтерпретація процедури підстановки дозволяє вважати багаторівневу ієрархічну структуру узагальненням поняття “вираз”. (При цьому вираз, у якому змінні не мають значень, розглядається як однорівнева ієрархічна структура).

Багатолітні дослідження на ЕОМ серії МІР і системах сімейства АНАЛІТИК показали, що головним об'єктом перетворень як при ручних, так і при машинних методах, по суті, є багаторівнева ієрархічна структура. СКА А-2000 відрізняється від інших систем комп'ютерної алгебри тим, що багаторівнева ієрархічна структура є її основним об'єктом. Кожен операнд функцій розглядається як вираз, що іменує деяку багаторівневу ієрархічну структуру. Система управління процесом обчислень в А-2000 дозволяє регулювати глибину підстановок значень змінних або виконувати перетворення на заданому рівні без попередньої підстановки.

Вхідні дані задачі, які вводить людина, рідко мають дуже великий обсяг. Громіздкі структури в СКА є результатом так званого “вибуху даних”, коли вони генеруються з малих багаторазово повторюваних об'єктів. Причому, чим складніша задача і більший обсяг об'єктів, тим більша імовірність повторення однакових структурних частин виразу. Тому в СКА А-2000 для обчислення значень використовується досить ефективна оптимізуюча процедура, яка іменує подібні підвирази (синтаксично правильні в А-2000 структурні частини виразу) спеціальними “робочими” змінними й обчислює один раз. Робота цієї процедури подібна до склеювання гілок деревоподібного графа. Ефективність такого обчислювального процесу тим вище, чим більше рівнів у структурі, що обчислюється.

Як приклад ефективності запропонованих методів приводяться результати обчислень із різними розрядностями для 10-ої похідної від виразу . Обсяг виразу (без попередніх спрощень) - 4 500 Кб.

Таблиця 1

Час виконання (у секундах) обчислень при

Розрядність

СКА | 25 | 50 | 100 | 250 | 500 | 1000 | 2500 | 5000 | 10000

АНАЛІТИК

без оптимізації | 98 | 200 | 434 | 2668 | - | - | - | - | -

АНАЛІТИК

з оптимізацією | 0,014 | 0,016 | 0,027 | 0,08 | 0,28 | 1,2 | 6,6 | 32,5 | 187,7

Matematica | 244 | 359 | 583 | 1436 | 4082 | - | - | - | -

Maple | 35 | 41 | 56 | 104 | 188 | 986 | - | - | -

Таблиця 2

Час виконання (у секундах) перетворень при відсутності числового значення x

СКА | АНАЛІТИК | Matematica | Maple

Час | 4 | 21 | 11

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

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

Описана у розділі сигнатура мови А-2000 була визначена на основі досліджень численних наукових і прикладних програм виконаних в Інституті проблем математичних машин і систем НАН України. Вона містить процедури, що реалізовані в попередніх версіях мови АНАЛІТИК та процедури які доводилося емулювати під час написання програм.

Програму на А-2000 можна розглядати як сукупність частин програми, які виконують роль управління, іменування, розпізнавання та перетворювання.

Основною рисою апарату управління перетвореннями мов сімейства АНАЛІТИК є система режимних процедур, які дозволяють або забороняють виконання певних перетворень. Ці режими задаються як глобально режимними операторами, дія їх поширюється на частини програми (групи операторів, що знаходяться між двома режимними операторами), так і локально режимними функціями, що визначають дію заданого режиму в межах виразу або підвиразу. Більш високий пріоритет мають локально задані режими.

В А-2000 перетворення визначаються такими режимами:

- раціональних чисел (РАЦ) або десяткових чисел (ДЕС) із заданою розрядністю (РОЗР);

- комутативності (КОМ) і некомутативності (НЕКОМ) алгебраїчних і логічних операцій +, *, &, \ ;

- підстановок на задане число кроків з обчисленням або без обчислень (ПІДСТ, ФОРМ);

-

До режимних засобів також відносяться:

-

-

Окрім того, до режимних належать функції, які дозволяють або забороняють виконання великих груп типових аналітичних перетворень (канонічні форми), таких як спрощення з урахуванням властивостей 0 та 1 для операцій “додавання”, “множення”, “ступінь”; блокування або дозвіл зведення подібних, законів дистрибутивності й асоціативності і т.п. Аналогічні режими використовуються й при виконанні логічних операцій. А-2000 передбачає можливість формування таких груп користувачем.

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

Один із найбільш складних і ефективних перетворювачів А-2000 реалізує апарат застосування формул виду , де Ф1 і Ф2 - іменні форми, тобто вирази, які містять вільні змінні. Цей алгоритм реалізує функцію ЗАСТОСУВАТИ з різними модифікаціями, вибір яких визначається значеннями параметрів.

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

Основна складність алгоритму, що реалізує ЗАСТОСУВАТИ, стосується етапу такого розпізнавання. Ця частина процедури має самостійне значення і є найважливішою функцією апарату розпізнавання мови А-2000.

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

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

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

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

Базовий розпізнавач - НАЛЕЖНІСТЬ - виконує розпізнавання структурних і функціональних властивостей. Ця функція перевіряє належність об'єкта до множини, що задається іменною формою. Функція є предикатом. Значення “істина” отримується, якщо при порівнянні об'єкта та форми визначаються значення вільних змінних, при підстановці яких форма перетворюється у вираз, еквівалентний об'єкту, що досліджується. При розпізнаванні структурних властивостей об'єкта його структура порівнюється зі структурою еталонного іменного виразу.

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

Нехай маємо форму і об'єкт . Ця форма задає сімейство парабол. Об'єкт належить сімейству за умови і . Для встановлення відповідності структура об'єкта добудовується, і він розглядається як вираз .

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

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

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

У третьому розділі наводяться система реалізації СКА і результати досліджень особливостей функціонування та структури реалізації мови КА. Наведені та досліджені основні алгоритми реалізації мови КА.

Система реалізації - це комплекс програм, написаних мовою Сі.

Об'єкти СКА А-2000 транслюються в об'єкти, що мають вид:

Х а р а к т е р и с т и к а

Довжина об'єкта

в байтах | Ознака

класу | Опис об'єкта

Рис. 1. Структура об'єктів

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

Наприклад, запис вектора має вигляд:

Довжина вектора | Ознака вектора | Опис вектора

Рис. 2. Структура вектора

Функціонування системи реалізації А-2000, в результаті якої організується процес символьних перетворень при розв'язанні задач, можна подати за допомогою схеми (рис. 3).

I блоку відповідає транслятор, який конвертує програми (блок VI) та дані (блок VIII) у коди, що прийняті в реалізації А-2000. Блок II задає порядок інтерпретації операторів програми. Інтерпретатор опирається на бібліотеку операторів (блок XII). Блок III містить спеціальну функцію, яка забезпечує виконання аналітичних обчислень символьної та числової інформації (бібліотека функцій та операцій блок X). У блоці IV відбуваються ретрансляція і вивід результату.

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

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

Рис. 3. Схема функціонування А-2000

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

У внутрішньому поданні програма мови АНАЛІТИК подана у вигляді дескрипторної таблиці “Програма”, яка містить послідовність фізичних адрес бездужкових записів операторів, що можуть розташовуватися в будь-яких місцях пам'яті.

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

Система реалізації містить бібліотеку функцій і операторів, доступ до яких здійснюється так само за допомогою дескрипторних таблиць. Написані користувачем процедури-функції за допомогою оператора ВКЛЮЧИТИ також включаються у відповідну дескрипторну таблицю.

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

На вхід АО подаються вирази, які іменують багаторівневу ієрархічну структуру. Значення змінних утворюють складні суперпозиції, де для виконання однієї функції необхідно викликати інші функції. Алгоритми таких обчислень виконуються по “гілках” багаторівневої ієрархічної структури без попередньої підстановки значень змінних. В АО послідовно виконуються функції і операції, які утворюють таку суперпозицію. Вони виконуються в міру готовності їх операндів. Фізична адреса отриманого значення по закінченні виконання АО заноситься в рядок дескрипторної таблиці “Каталог”, що відповідає імені результату.

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

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

,

де t1 - час обчислення f(uі);

t2 - середній час точного порівняння uі й uj ;

- число збігів ;

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

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

Подібним чином відбувається зведення подібних при виконанні таких багатомісних операцій, як “+”, “*”,“&”, “\”. При цьому як f(uі) в А-2000 використовується сума двійкових кодів запису uі .

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

;

;

,

де Dі - результат i-го кроку алгоритму Евкліда після видалення множників виду ,

u - чисельник,

v - знаменник,

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

Ознакою закінчення процедури є . Результат ділення .

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

Розглянемо як приклад диференціювання виразу

. (1)

Таблиця 3

Об'єм результатів диференціювання (без звичайних спрощень)

Порядок похідної (k) | 1 | 2 | 4 | 8 | 10

Об'єм (у Kб) | 36 | 80 | 666 | 170 732 | 4 570 000

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

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

Таблиця 4

Кількість фрагментів у результатах диференціювання

Порядок похідної

Фрагмент | 1 | 2 | 4 | 8 | 10

cos(x) | 1 | 3 | 25 | 6531 | 45 347

sin(x) | 1 | 2 | 19 | 5242 | 11 082

1 | 2 | 14 | 3238 | 20 574

Для оцінки ефективності описаної оптимізації позначимо через T час обчислень без оптимізації та через Toп - час з оптимізацією. Тоді

;

,

де m - число різних фрагментів об'єкта,

ti - час обчислень і-го фрагмента,

ni - число повторень цього фрагмента.

У такий спосіб оцінка ефективності описаної оптимізації

.

Для 10-ої похідної (1) при ефективність оптимізації швидко зростає з точністю обчислень. Фактично на результат експерименту дуже впливають особливості реалізації.

Таблиця 5

Ефективність оптимізації

Розрядність | 25 | 50 | 100 | 1000

5 | 11 | 23 | 2900

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

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

У четвертому розділі описані результати дослідження області застосування СКА й особливостей програмування засобами СКА.

Основні особливості та етапи програмування різноманітних задач КА пов'язані з:

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

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

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

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

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

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

Системні процедури, які входять до складу ядра мови описуються мовою реалізації. До них належать елементарні операції й функції. Інші процедури реалізуються мовою КА й приєднуються до ядра, тому їхня ефективність відповідно нижча. Мова А-2000 дозволяє включати в ядро довільний набір таких процедур; при цьому вони синтаксично не відрізняються від системних і утворюють проблемно орієнтоване розширення мови.

До них, зокрема, відноситься процедура розпізнавання еквівалентності двох виразів A й B, що містять деякі елементарні функції. В А-2000 вона реалізується поданням елементарних функцій в експоненціальному виді формулами Ейлера:

;

і т.д.

Ця процедура, зокрема, використовується, коли від еквівалентності виразів A і B залежить напрямок подальшої роботи програми.

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

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

ВИСНОВКИ

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

З таблиць 1, 2 видно, що швидкодія символьних перетворень приблизно у 3–5 разів вища у порівнянні з зарубіжними СКА. Швидкодія числових перетворень зросла у 7000–33000 разів у залежності від розрядності чисел. За усередненими даними користувачів час написання та налагодження програм скоротився у 3–6 разів.

При виконанні дисертаційної роботи були отримані такі результати:

1.

2.

3.

4.

5.

6.

7.

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

1.

2.

3.

4.

5.

6.

7.

8.

9.

АНОТАЦІЯ

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

Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 01.05.03 – Математичне та програмне забезпечення обчислювальних машин і систем. – Інститут проблем математичних машин і систем НАН України, Київ, 2007.

Дисертаційна робота присвячена засобам автоматичного управління обчислювальним процесом та засобам перетворення в системах комп'ютерної алгебри. Докладно розглядаються властивості й реалізація новітньої системи сімейства АНАЛІТИК (АНАЛІТИК-2000).

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

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

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

АННОТАЦИЯ

Швалюк Т.Н. Управление процессом символьных преобразований при решении задач компьютерной алгебры. – Рукопись.

Диссертация на соискание ученой степени кандидата технических наук по специальности 01.05.03 – Математическое и программное обеспечение вычислительных машин и систем. – Институт проблем математических машин и систем НАН Украины, Киев, 2007.

Диссертационная работа посвящена средствам автоматического управления вычислительным процессом и средствам преобразования в системах компьютерной алгебры. Подробно рассматриваются свойства и реализация новейшей версии алгоритмических языков семейства АНАЛИТИК (АНАЛИТИК-2000).

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

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

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

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