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

Загрузка...

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

груп користувачем.

Найважливішою особливістю апарату іменування мови А-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


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