LibRar.Org.Ua — Бібліотека українських авторефератів

Загрузка...

Головна Електроніка. Обчислювальна техніка → Управління процесом символьних перетворень при розв'язанні задач комп'ютерної алгебри

налагодження й полегшує освоєння мови. Відзначимо, що управління обчисленнями в зарубіжних СКА (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 передбачає можливість формування таких