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

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

ЛЯХОВ Олександр Логвинович

УДК 681.086

ІНТЕЛЕКТУАЛІЗАЦІЯ РОЗВ’ЯЗУВАННЯ

НАУКОВИХ І ПРИКЛАДНИХ ЗАДАЧ

НА ОСНОВІ МЕТОДІВ КОМП’ЮТЕРНОЇ АЛГЕБРИ

01.05.03 – Математичне та програмне забезпечення обчислювальних машин і систем

АВТОРЕФЕРАТ

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

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

Київ – 2004

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

Робота виконана в Інституті проблем математичних машин і систем Національної академії наук України

Науковий консультант:

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

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

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

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

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

доктор фіз.-мат.-наук, член-кор. НАН України, професор

Перевозчикова Ольга Леонідівна,

Інститут кібернетики імені В.М. Глушкова

НАН України, завідуюча відділом

доктор тех. наук, професор

Молчанов Олександр Артемович,

Національний технічний університет України „КПІ ”,

завідувач кафедри прикладної математики

доктор тех. наук, ст. наук. cпівробітник

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

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

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

Провідна установа:

Київський національний університет імені Тараса Шевченка,

факультет кібернетики, кафедра математичної інформатики,

Міністерство освіти і науки України, м. Київ

Захист відбудеться 14.05. року о 14 годині на засіданні спеціалізованої вченої ради Д26.204.01 в Інституті проблем математичних машин і систем НАН України

за адресою: пр-т Академіка В.М. Глушкова, 42, м. Київ-187, 03680, МСП.

З дисертацією можна ознайомитись у бібліотеці Інституту проблем математичних машин і систем НАН України за адресою:

пр-т Академіка В.М. Глушкова, 40, Київ-187, 03680, МСП.

Автореферат розісланий 16.03. р.

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

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

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

Актуальність теми. Необхідність досліджувати місткі науково-технічні проблеми у їх природному аналітичному вигляді привела до створення і широкого розповсюдження засобів автоматизації чисельно-аналітичних методів – систем комп`ютерної алгебри (СКА). Це дає змогу отримувати більш якісний розв’язок та зменшувати обсяг високовартісних експериментальних і натурних досліджень і значною мірою визначає ефективність наукових та інженерно-технічних розроблень.

Дисертація базується на доробку багатьох учених. Серед них – В.М.Глушков, Л.В. Канторович, А.Н. Колмогоров, а також С.О.Абрамов, А.В.Анісімов, Р. Бенерджі, М.М. Васильєв, В.П. Гердт, В.Ф. Єднерал, Г.Б. Єфімов, Є.В. Зима, Ю.В. Капітонова, В.П.Клименко, О.А.Летічевський, О.А.Молчанов, А.О. Морозов, О.Л. Перевозчикова, Б.О. Попов, В.О. Ростовцев, А.О. Стогній, Г.С. Теслер, Ю.С. Фішман, К. Фу, Д.В. Ширков, J.H.Davenport, R.J. Fateman, K.O. Geddes, K. M. Heal, A.C. Hearn, R.D. Jenks, G. Labahn, W.A. Martin, J. Moses, B.Monagan, R.S. Sutor, N.A.Trufyn, S. Wolfram, S.M.Vorkoetter та інші. Їх уявлення про програмне забезпечення (ПЗ) як про засоби, що забезпечують ефективну взаємодію суб’єктів розв’язування задач – “людини” та “комп’ютера” – втілене у десятки систем комп’ютерної алгебри (СКА) різноманітного призначення. Найбільш відомі серед них універсальні СКА MACSYMA, FORMAC, REDUCE, MATHEMATICA v2-4, AXIOM, MAPLE V R3-6, вітчизняні АНАЛІТИК, обчислювальні комплекси СМ 1410 і СКА АНАЛІТИК-93 з мовами сім’ї АНАЛІТИК тощо.

Стрімкий розвиток обчислювальної техніки, відповідне зростання комп’ютерної та математичної підготовленості користувачів містять потенціал подальшого розширення області застосування чисельно-аналітичних методів (ЧАМ) на нові класи задач із недосяжним раніше обсягом та складністю аналітичних об’єктів. Але, як показали дослідження, у даний час для такого розширення характерне непродуктивне використання високовартісної праці людини. Тому стало актуальним створення теоретичних і прикладних основ розроблення прикладного ПЗ, зорієнтованого на автоматичне розв’язування складних наукових та прикладних задач. Розв’язання кола цих питань якісно підвищить ефективність математичного моделювання у різноманітних галузях фундаментальної й прикладної науки і техніки – вагомих складників виробничого потенціалу сучасного рівня в Україні.

Зв’язок роботи з науковими програмами, планами та темами. Робота виконана згідно з планами науково-дослідних робіт НАН України, Міністерства освіти і науки України, планами науково-дослідних робіт Інституту проблем математичних машин і систем НАН України і Полтавського національного технічного університету імені Юрія Кондратюка на 1996-2003 роки у межах таких держбюджетних тем: “Математичне моделювання в радіолокації, дефектоскопії, акустиці та механіці з використанням методів комп`ютерної алгебри”, ГР № 0100U000811, 2000-2003 (відповідальний виконавець); “Розроблення і дослідження математичних моделей напружено-деформованого стану просторових тіл з ускладненими властивостями”, ГР № 0196U000996, 1996-1997 (відповідальний виконавець); “Розроблення розв’язків задач механіки деформування структурно-неоднорідних тіл і їх реалізація методами комп’ютерної алгебри”, ГР № 0198U002688, 1998-1999 (відповідальний виконавець); “Розроблення теорії та методів дослідження міцнісних властивостей елементів конструкцій у вигляді брусів кусково-однорідної структури”, ГР № 0100U001318, 2000-2002 (виконавець) та ряду інших тем, що підтверджено відповідними документами.

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

Для досягнення цієї мети необхідно розв’язати такі задачі:

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

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

3. Обґрунтувати і розробити структури даних та склад набору процедур вхідної мови універсальної СКА нового покоління для створення програмного забезпечення розв’язування складних задач.

4. Розробити аналітичні моделі реальних прикладних задач, складних за своїми характеристиками.

5. Розробити методи й програмне забезпечення розв’язування цих задач, отримати розв’язки.

Отже, у даній дисертації:

Об’єкт дослідження – сучасні проблеми застосування комп’ютерної алгебри, які ускладнюють створення ПЗ наукових та прикладних задач.

Предмет дослідження – складні задачі, що виникають у прикладному математичному моделюванні, процес їх розв’язування, інтелектуалізація цього процесу, властивості вхідних мов СКА, орієнтованих на створення автоматичного ПЗ для розв’язування складних наукових і прикладних задач.

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

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

· У загальній проблемі автоматизації ЧАМ виділена проблема інтелектуалізації. Уперше означений об`єкт інтелектуалізації – клас складних задач комп’ютерної алгебри. Розроблено новий підхід до аналізу і виведені критерії порівняльної продуктивності автоматичного та діалогового режимів СКА. Встановлено можливість якісного підвищення продуктивності розв`язування складних задач шляхом інтелектуалізації при сучасному співвідношенні між характеристиками складових системи „людина-комп`ютер”.

·

·

·

·

·

·

Практичне значення одержаних результатів. У дисертації розроблені теоретичні та прикладні основи створення вхідних мов СКА нового покоління та програмного забезпечення автоматичного розв’язування складних задач, що є ґрунтом для нового витка підвищення якості й продуктивності науково-дослідних робіт, а також процесу навчання.

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

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

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

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

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

Особистий внесок здобувача. Усі результати дисертаційної роботи одержані особисто автором. У працях, написаних у співавторстві, особисто автору дисертації належать: у публікаціях [8, 10, 13, 24] методи й алгоритми розв’язування задач, ПЗ та отримані розв`язки; у працях [11, 30] при розробленні мови і при визначенні семантики її процедур використані результати даної роботи, а також процедура СПИСОК; у публікаціях [9,12,31] теоретико-множинний підхід, принципи інтелектуалізації, теореми, наслідки, уявлення про процес розв`язування задачі як про перетворення множини виразів з відношенням залежності, “нерв” як структура даних мови СКА нового покоління; у публікаціях [20-22, 25-27, 29] формулювання в термінах узагальнених функцій математичних моделей, ПЗ, метод та реалізація визначення пружної лінії прогину брусу; у працях [14-19] загальна методика моделювання й розрахунків геометричних параметрів осередку деформації, її реалізація.

Апробація роботи. Основні положення та результати дисертації доповідалися на V-VII Міжнародних наукових конференціях імені академіка М. Кравчука (Київ, 1996-1998рр.); XVI Міжнародній конференції “Математическое моделирование в механике деформируемых твердых тел. Методы конечных и граничных элементов” (Росія, Санкт-Петербург, 1998 р.); Second International conference on Composite Science and Technology (ICCST/2, Durban, South Africa, 1998); Першій міжнародній науково-практичній конференції з програмування (УкрПРОГ-98, Київ, 1998); Міжнародній конференції “Численные и аналитические методы расчета конструкций” (Росія, Самара, 1998 р.); 4-th International IMACS Conference on Application of Computer Algebra (IMACS-ACA'98, Czech Republic, Praha, 1998); VI Міжнародному симпозіумі українських інженерів-механіків (Львів, 1999 р.); II Білоруському конгресі з теоретичної та прикладної механіки (Бєларусь, Мінськ, 1999 р.); III Міжнародній науково-технічній конференції “Математичне моделювання в електротехніці та електроенергетиці” (Львів, 1999 р.); International conference “Composite science and technology” (ICCST/3, Durban, South Africa, 2000); II Міжнародній науково-практичній конференції “Інтернет-Освіта-Наука-2000” (IOH-2000, Вінниця, 2000 р.); III Всеросійському семінарі “Проблемы оптимального проектирования сооружений” (Росія, Новосибірськ, 2000 р.); VI Сибірському Конгресі з прикладної та індустріальної математики, присвяченому пам’яті М.А.Лаврентьєва (ІНПРІМ-2000, Росія, Новосибірськ, 2000р.); VI-й Міжнародній науково-технічній конференції “Пластична деформація металів” (Україна, Дніпропетровськ, 2002); 8-9-й Міжнародних наукових конференціях “Современные проблемы информатизации в технике и технологиях” (Росія, Воронеж,2003-4рр.).

Публікації. Список основних опублікованих праць за темою дисертації у кількості 31, із них 9 без співавторів, наведений у кінці автореферату. Серед них 21 стаття у наукових журналах, 6 – у збірниках наукових праць та 4 – тези міжнародних конференцій та конгресів.

Структура та обсяг дисертації. Дисертація складається зі вступу, семи розділів, висновків, списку використаних джерел, що містить 376 найменувань, й 5 додатків. Загальний обсяг становить 320 сторінок, серед яких основної частини 291 сторінка, 63 рисунки й 8 таблиць.

ОСНОВНИЙ ЗМІСТ ДИСЕРТАЦІЇ

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

Перший розділ присвячений огляду літератури та ПЗ за темою дисертації й обґрунтуванню вибору напряму досліджень. В огляді окреслені основні етапи розвитку СКА як засобів автоматизації чисельно-аналітичного розв’язування складних наукових і прикладних задач. Увага сконцентрована на етапах якісної зміни властивостей СКА для розширення області застосування й спектра ЧАМ у відповідності з природним розвитком науки та інженерії.

Установлено, що на кожному з цих етапів продуктивному застосуванню СКА відповідає певний розподіл функцій між компонентами системи “людина-комп’ютер”, зумовлений рівнем розвитку можливостей обчислювальної техніки, властивостями вхідних мов і вартістю праці. Критерії оцінювання продуктивного застосування ЧАМ є відображенням такого розподілу.

У результаті огляду та аналізу визначено об’єкт і предмет дослідження. Розкритий зв’язок теми дисертації із загальною проблемою автоматизації ЧАМ.

Визначальною складовою процесу чисельно-аналітичного розв`язування є аналіз властивостей даних і вибір шляхів їх перетворень. Необхідні для цього якості суб`єкта підпадають під значення терміна “інтелект” у тому прагматичному розумінні, яке надавалося йому з самого початку у словосполученні “artificial intelligence”, а відповідні функції, що виконуються на всіх етапах розв’язування, можна назвати інтелектуальними. Розроблення засобів автоматизації такої діяльності природно назвати інтелектуалізацією ПЗ. Отже, інтелектуалізація ПЗ є складовою загальної проблеми автоматизації розв’язування складних для людини задач. Виділені два аспекти: теоретичний та прикладний. Теоретичний полягає у розробленні уявлень про задачу як про об`єкт СКА і про властивості мови для створення ПЗ складних задач. Прикладний – у виділенні класів задач, розв’язування яких потребує інтелектуалізації, у розробленні відповідної мови та у напрацюванні практичних методів програмування.

Установлено, що внаслідок швидкого розширення області застосування комп’ютерної алгебри на представницькі класи задач найрізноманітнішої тематики в даний час все більшої значущості набувають труднощі програмування розв’язування, які полягають в існуванні “відносної алгоритмічної проблеми”. Проблематичним є не існування алгоритму, а можливість продуктивного представлення розв’язування задачі чітко окресленими засобами, тобто вхідною мовою даної СКА. Ця проблема є наслідком неповноти вхідних мов сучасних СКА, незважаючи на неперервне збільшення об`єму їх бібліотек (рис.1), і причиною вимушеного переведення розв’язування у режим діалогу.

Спроможності сучасної комп’ютерної техніки дають змогу переходити до розв’язування задач із недосяжним раніше обсягом даних. На рис. 2 а, б, в показані приклади, взяті із різноманітних галузей фундаментальної та прикладної науки: ядерної і математичної фізики, а також теорії пружності композитних матеріалів. Лінійній зміні параметра т, що характеризує ускладнення задачі (кількість членів ряду, підстановок, ітерацій ЧАМ), відповідає майже експоненціальне зростання функції ємнісної складності (довжина виразу в символах: - експериментальні дані, о - згладжені дані, масштаб логарифмічний).

При зростанні обсягу виразів продуктивність візуального аналізу їх властивостей у режимі діалогу швидко знижується. На рис. 3а у логарифмічному масштабі показаний аналог сигнальної часової складності для однієї і тієї ж задачі теорії опору композитних матеріалів, розв’язаної автоматичною програмою та у діалозі. Криві 1а та 1b – загальний час розв’язування: а – в режимі діалогу; b – автоматичною програмою. Крива 2 – “чистий” час процесора, що витрачений на виконання автоматичних перетворень. Криві на рис. 3а ілюструють й іншу особливість застосування ЧАМ: час зростає переважно за рахунок витрат на виконання інтелектуальних функцій. Для варіанта m=4 “чистий час” перетворень (крива 2) складає ~ 3.4% від загального часу розв’язування в інтерактивному (крива 1b) і 33% - в автоматичному (крива 1a) режимах. Порівняння часових сигнальних показано на рис. 3б і свідчить про падіння продуктивності інтерактивного режиму при одному прогоні програми з ускладненням задач.

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

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

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

Установлено, що в усіх сучасних СКА розвиваються засоби, спроможні підтримувати такий розподіл функцій, але характерним є стихійність розвитку і відсутність єдиних уявлень про відповідні властивості вхідних мов. Виділено два альтернативних підходи до розв’язання цієї проблеми: конструктивний та аналітичний. Також установлено, що на даний час немає обґрунтування вибору між ними при загальному розв’язанні проблеми інтелектуалізації ПЗ.

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

У другому розділі обґрунтовані й розроблені шляхи та методи вирішення задач дослідження. Новий розподіл функцій потребує інших, ніж на попередніх етапах розвитку СКА, критеріїв оцінювання відносної продуктивності інтерактивного та автоматичного режимів праці. Доцільність інтелектуалізації випливає із сучасних спроможностей суб`єктів розв`язування до забезпечення більшої продуктивності автоматичного ПЗ порівняно з діалоговим.

При оцінках продуктивності враховані загальні витрати на всіх етапах розв`язування задачі і питома вартість одиниці праці кожного суб’єкта. Це відповідає суб’єктивній природі складності й доцільне з огляду на різнорідність природи та способів обробки інформації людиною і комп'ютером. Продуктивність П розглядається як

, (1)

де Р - загальна вартість розв’язування задачі. Її параметрами є швидкість обробки інформації , питома вартість праці суб’єкта, кількість прогонів програми за її “життя” та часові витрати T .

Для діалогової програми маємо

, (2)

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

За умови інтелектуалізації вартість автоматичної програми оцінюємо як

, (3)

де час, витрачений людиною на програмування та налагодження автоматичної програми. Для діалогової програми цим параметром нехтуємо, і для відносної продуктивності маємо

, та , (4)

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

Швидкість оброблення інформації людиною є сталою тільки при невеликій довжині коду:

, (5)

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

. (6).

Виходячи з об’єктивності природи задачі та розвитку комп’ютерної техніки, вважаємо, що у (4) і незалежні, а та . Доведено:

Твердження 1: Для підвищення продуктивності розв’язування шляхом інтелектуалізації ( у (4) ) необхідно і достатньо, щоб

. (7)

Критерій (7) представляє розв’язок задачі I. Основні результати його аналізу такі:

· При розв’язуванні складних задач автоматичні програми, за умови інтелектуалізації, продуктивніші, ніж діалогові. Більше того, їх відносна продуктивність зростає разом зі складністю задачі.

· Сучасні тенденції розвитку комп’ютерної техніки сприяють зменшенню значення та у (4) і таким чином сприяють виконанню нерівності (7) як достатньої умови. Значення та визначаються також властивостями вхідних мов сучасних СКА, рівень розвитку яких (розділ 1) недостатній для програмування автоматичного розв’язування складних задач.

Цим обґрунтовуються шляхи досягнення мети дисертації, викладені у вигляді задач 2-5.

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

·

·

·

, (8)

а кожний крок розв’язування також є алфавітним відображенням:

, (9)

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

·

При розв’язуванні невідомими є об’єкт, представлений виразами і послідовність функцій f (процедурне невідоме за термінологією G.Polya).

Із сформульованих положень та відомого феноменологічного означення поняття “задача” (В.М.Глушков, G.Polya) витікає:

Твердження 2: Для розв’язування масової складної задачі достатньо синтезувати процедурне невідоме f.

Це твердження у сукупності з означенням поняття “автоматичні обчислення” (Th. Cormen) обґрунтовує достатність вирішення задач II-III для досягнення мети дисертації, а поставлені задачі зведені до розроблення мови представлення даних та синтезу процедурного невідомого.

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

Твердження 3: У загальному випадку подання розв’язування складної задачі у вигляді (8)-(9) мовою, що породжується граматикою, містить відносну алгоритмічну проблему.

Для розв’язання проблеми інтелектуалізації програмного забезпечення автором розроблені принципи, які є обґрунтуванням, подальшим розвитком й узагальненням аналітичного підходу:

1. Задача об’єктивна. Вирази у (8)-(9) пов’язують між собою імена початкових, проміжних та невідомих даних і будуються за певними синтаксичними правилами, але їх вигляд, структура, а також вибір відображень fi зумовлені не тільки цими правилами, а є втіленням певних феноменологічних відношень на множині імен даних. Аналіз відношень між об’єктами складної задачі у процесі її розв’язування необхідно здійснювати на неконструктивній (канторівській) теоретико-множинній основі.

2. Мову представлення даних про складну задачу треба розробляти на основі аналітичної граматики, що відповідає теоретико-множинній моделі задачі:

Складна задача у процесі (8)-(9) розглядається як множина Ф виразів універсальної мови на словнику Г, що містить імена початкових, проміжних та невідомих даних. Інтелект наділяє множину Ф структурою мови шляхом аналізу відношень між виразами з Ф та їх складовими частинами.

3. Вхідна мова універсальної СКА, призначена для розв’язування складних задач, повинна бути відкритою для користувачів і містити підмножину засобів для надбудови гіпермови при розв’язуванні конкретної складної задачі.

4. Гіпермова має таку структурну четвірку:

, (10)

де Г – словник мови; Р – розбиття словника; Ф – множина виразів задачі на всіх етапах процесу розв’язування; – категорії вигляду (R(), F); R() – клас об’єктів; F – відповідний клас морфізмів; - феноменологічне відношення, що утворює категорію .

Методичну основу подальших досліджень становлять принципи:

5. Множини виразів у (8)-(9) розглядаються як вирази деякої мови (10) на аналітичній основі над вхідною мовою СКА.

6. Феноменологічні відношення абстрагуються суб’єктом при аналізі множини Ф. Кожне виражається деяким квантором узагальненості:

виконується - істина, (11)

є відношенням еквівалентності і задає властивість (клас) на множині Ф виразів вхідної мови.

7. Структура (10) мови динамічна і може збагачуватися за рахунок додавання нових категорій:

. (12)

8. Вхідна мова СКА є метамовою по відношенню до мови на аналітичній основі. Тому четвірка (10) визначає склад сукупності базисних процедур як компоненту сигнатури вхідної мови, над якою будується гіпермова для розв’язування складної задачі.

9. Базисними засобами для створення гіпермови є алфавіт вхідної мови СКА, словник Г та його розбиття Р, а також процедури для розширення або зміни Г і Р. Особливе значення мають базисні процедури для представлення категорій: для іменування класів об’єктів, перевірки належності деякого об’єкта заданому класу та здійснення алфавітних перетворень (9).

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

11. Базисні засоби вхідної мови СКА повинні бути орієнтовані на збереження компактності представлення даних у процесі розв’язування.

Отже, розв’язання задач дисертаційних досліджень зведене до доведення існування мови на аналітичній основі для представлення процесу (9) розв’язування задачі, розроблення структур для представлення даних, що забезпечують автоматичне виконання перетворень, до обгрунтування та розроблення відповідних процедур вхідної мови СКА, доведення відсутності відносної алгоритмічної проблеми при програмуванні розв’язування у термінах розроблених засобів, а також у апробації одержаних результатів і систематизації використаних стилів програмування. Цей перелік складає зміст подальших досліджень, а одержані результати – теоретичні й прикладні основи створення ПЗ, зорієнтованого на автоматичне розв’язування ЧАМ складних задач.

У третьому розділі розроблена теоретико-множинна модель задачі та процесу її розв’язування як об’єктів СКА. На цьому ґрунті доведене існування мови на аналітичній основі, розроблені узагальнені структури даних.

Загальні положення. Теоретико-множинна модель побудована як узагальнення відношень між даними у процесі розв’язування задач на знаходження:

1. Вирази з Ф у (8)-(9) утворені скінченними послідовностями на деякому словнику Г з розбиттям

, (13)

де – імена операцій; – імена даних (початкових , проміжних та невідомих), і є правилом запису обчислення його значення. У виразі існують головна І та одинична операції.

2. Кожній операції можна поставити в однозначну відповідність множину її операндів, кожному виразу систему таких множин, множині - систему, а відповідає система

, (14)

де - булеан множини Г``.

3. Розв’язок може бути представлений системою , у якій елементи мають вигляд

, (15)

де - ім’я невідомого або проміжного даних; .

4. Кожна система покриває . Система покриває .

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

Структуру сукупності з’ясовує

Лема 1: Схема відношень між виразами у множині Ф, зумовлена відношенням залежності між іменами даних, ізоморфна абстрактному комплексу K розмірності m, де m+1 – кількість різних імен даних у .

Системи , які відповідають виразам із у (9), ізоморфні симплексам комплексу .

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

Теорема: Якщо на кожному кроці у (9) існують множини виразів з відношенням залежності, то існує мова на основі аналітичної граматики (10) для представлення процесу (9) розв’язування задачі.

Отже, дослідження зведені до розроблення засобів опису категорій (12) у термінах класів на Ф та відображень f. Методика розроблення визначена принципами інтелектуалізації.

Із леми 1 та теореми випливає, що на множині Ф виразів задачі у процесі розв’язування існують просторові топологічні відношення. Також має місце

Твердження 4: Топологія, що породжена метрикою простору реалізації комплексу К, індукує на множині виразів універсальної мови на Г функціональну властивість.

Ці твердження є підставою для просторових уявлень про основний об’єкт СКА, парадигму вхідних мов АНАЛІТИК-93,-2000, але встановлюють його топологічну, а не метричну природу.

Програмування розв’язування складної задачі у термінах категорій (12) потребує структур даних відповідної узагальненості і процедур вхідної мови для роботи з такими даними.

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

Найменшою семантичною одиницею при запису розв’язування задачі є відокремлений вираз. Для усунення відношення залежності на і відокремлення виразів у (9) накладена

Умова 1: Вважаємо, що всі операнди всіх операцій у виразах , навіть якщо вони мають однакові імена, парами різні..

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

, (16)

де -імена операцій; - множини їх операндів. Загалом виразу відповідає

Лема 2: Система множин, зчеплена відношенням (16), ізоморфна орієнтованому дереву.

Схема (16) вільна від семантики операцій. Тому лема 2 при виконанні умови 1 природно поширюється на множину відокремлених виразів, упорядкованих черговістю виконання підстановок. Множині таких виразів також відповідає певне орієнтоване дерево, точніше, об’єднання дерев. Обернена відповідність у множину виразів універсальної мови не однозначна. Мають місце

Твердження 5: Схема відношень на множині операцій, зумовлена зчепленням (16), породжує клас еквівалентності на множині виразів універсальної мови на Г .

Означення 2: Цей клас еквівалентності назвемо структурною властивістю виразу мови на Г, а спільну схему відношень – просто схемою.

Важливим для програмування автоматичного розв’язування задач є:

Твердження 6: Схема, зумовлена зчепленням (16), є структурою даних.

Відокремлені вирази різноманітних типів є основними об’єктами вхідних мов провідних СКА, оброблення яких підтримує й АНАЛІТИК-93,-2000. Але при усуненні залежності між даними процедурне невідоме f у (8)-(9) може бути синтезоване тільки у вигляді послідовності перетворень, в якій обчисленню значення кожного відокремленого виразу передує підставлення замість імен даних їх поточних значень, що веде до стрімкого зростання обсягу даних. Отже при програмуванні автоматичного виконання процесу (8)-(9) у термінах відокремлених виразів не можна уникнути характерного (розділ 1) для складних задач явища – “вибуху даних”.

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

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

Скасуємо на Ф умову 1. Схема відношень на множині операцій, що виконуються при обчисленні значень виразів, пов’язаних відношенням залежності, на кожному кроці процесу розв’язування (9) може бути узагальнена у вигляді відношення

, (17)

де – також операція з О. При цьому має місце

Лема 3: Схема відношень на множині операцій у , обумовлена (17), ізоморфна абстрактному симпліціальному комплексові.

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

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

, (18)

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

Означення 3. Комплекс (18) будемо називати “нервом” множини виразів задачі.

Накладемо на “нерв” умову відокремлення, вважаючи кратні вершини різними. Відношення залежності можна продовжити до лінійної упорядкованості на . Тоді має місце

Твердження 7: ”Нерв” множини виразів задачі, упорядкованих продовженим відношенням залежності, є структурою даних.

Операнд може бути обчислений тільки раз і потім підставлений в усі вирази , що утворюють цю грань „нерва”. Оскільки нерв є повним комплексом, у такий спосіб можна здійснити перетворення усієї множини виразів , передаючи обчислені значення між суміжними вершинами граней без рекурсивного виконання підстановок. Отже, залежність (18) між виразами, представлена у термінах нової структури даних “нерв”, надає принципово нові можливості для організації автоматичних перетворень і вирішення аспекту проблеми складних задач, пов’язаного із зростанням обсягу проміжних даних. Загалом має місце

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

У важливому окремому випадку, коли множина виразів упорядкована черговістю виконання підстановок, нерв ізоморфний орієнтованому дереву. Це дозволяє проводити незалежні перетворення з передачею значень уздовж кожного відокремленого ланцюга нерва.

Сукупності виразів з однаковим нервом утворюють клас на множині виразів універсальної мови, і на цю сукупність природно поширюється поняття структурної властивості (означення 2). Ім’ям класу може бути вираз або із спеціального розбиття словника Г, або будь-який вираз даного класу. Отже, альтернативність природи конструктивного та аналітичного підходів у якісно різному способі іменування властивостей. Ураховуючи твердження 3, приймаємо:

Умова 2: Ім’ям класу виразів універсальної мови на Г може бути деякий вираз цього ж класу.

Умова 3: Ім’ям класу сукупностей виразів універсальної мови на Г, з відношенням залежності, може бути елемент цього класу.

Прийнятий спосіб іменування властивостей, відповідно до твердження 3, є основою для загального розв’язання другого аспекту складності задач – відносної алгоритмічної проблеми.

Структура даних “схема” (твердження 6) є узагальненням основних типів структур даних сучасних СКА, структура даних “нерв” є новою. Новими є принципи 1-11 та твердження 3-8. У розділі також доведено, що отримані у розділах 2-3 результати становлять достатню теоретичну основу для розроблення прикладних аспектів проблеми інтелектуалізації ПЗ.

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

Автоматичне ПЗ складних задач створюється мовою програмування, що складається з двох компонент. Перша використовується для програмування частини перетворень (9), яку можна представити у термінах стандартних проблемних типів даних і процедур використовуваної СКА, і тому далі вона не розглядається. Інтелектуалізація ПЗ полягає (принципи 5-11) у розробленні на аналітичній основі другої компоненти зі структурою (10), яка застосовується для усунення проблем, пов’язаних зі складністю задачі, що розв’язується.

Перетворення в (9) плануються людиною й описуються в термінах категорій (,) мови при розробленні ПЗ (принципи 5-7). Термінами є вирази, що іменують властивості (умови 2-3), процедури, що розв’язують множину виразів універсальної мови на Г відносно класу об'єктів , і процедури, що здійснюють алфавітні відображення .

Отже, категорія мови є „парою” процедур спільного застосування (перевірка належності класу об’єктів, морфізм). Їх доцільно реалізовувати однією процедурою. Перша компонента „пари” має і самостійне значення як елемент керування гілкуванням програми. Цей результат обґрунтовує та узагальнює результат, вперше отриманий у роботах В.П. Клименка й Ю.С. Фішмана у вигляді процедури ЗАСТОСУВАТИ. Тут поняття „пари” обгрунтовано й узагальнено як один з основних елементів інтелектуалізації ПЗ складних задач.

Спосіб реалізації компонент „пари” може бути різним, проте безпосередньо з теореми існування мови на аналітичній основі (розділ 3) випливає:

Наслідок: Представлення розв’язування складних задач мовою на аналітичній основі передбачає таку реалізацію базисних процедур вхідної мови СКА, яка здійснює відображення зі збереженням відношення залежності.

Умова 4: Вираз вхідної мови СКА, що описує заголовок базисної процедури, призначеної для розв’язування множини виразів універсальної мови відносно класу об’єктів, повинен містити список імен залежних даних.

Серед провідних СКА тільки у вхідній мові MAPLE V окремі