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

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

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

Анотації

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

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

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

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

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

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

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

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

Эти объекты принадлежат различным типам данных и для их автоматического преобразования необходимо очень общо определять функции преобразования или увеличивать число функций соответственно множеству различных типов данных (AXІOM, MAPLE, MATHEMATІCA, REDUCE).

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

Уровень интеллекта системы АНАЛИТИК-2000 в основном определяется богатством функций распознавания функциональных и структурных свойств объектов языка и режимных операторов и функций.

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

Работа содержит описание аппарата автоматического применения формул, который аналогичен соответствующему аппарату математического анализа. Уровень интеллекта языков семейства АНАЛИТИК в сильной мере определяется общностью аппарата, связанного с применением формул. С его помощью выполняется распознавание структурных и функциональных свойств данных, их преобразование и именование.

Описана система работы с рациональными числами и числами с произвольной длиной мантиссы, которая расширяет область применения численных методов и увеличивает точность полученных результатов.

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

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

Shvaluk Т.N. Management of process of symbolical transformations at the decision of problems of computer algebra. - Manuscript.

Основний зміст роботи

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

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

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

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

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

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

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

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

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

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

Таблиця 1

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

Таблиця 2

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

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

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

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

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

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

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

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

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

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

оптимізації обчислень (ОПТ).

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

перевизначення семантики символів математичних операцій і функцій, а також введення нових операцій (ОПЕР);

відміна результатів виконаних перетворень, якщо вони не відповідають заданому виду (КЛАС).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Рис. 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 - знаменник,

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

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