Я Драґан, в Овсяк - Системний аналіз і методологія алгебри алгоритмів - страница 1

Страницы:
1 

УДК 004.4'232

1Я. Драґан, 2В. Овсяк

1Національний університет "Львівська політехніка",

кафедра ПЗ, 2Українська академія друкарства

СИСТЕМНИЙ АНАЛІЗ І МЕТОДОЛОГІЯ АЛГЕБРИ АЛГОРИТМІВ

© Драґан Я., Овсяк.В., 2012

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

Ключові слова: алгоритміка, алгебра алгоритмів, математична модель, аксіома­тичний метод, неповна аксіоматика.

There are exposed the results of system analysis of the problem for construction of algebra and metatheory of algorithms algebra in contemporary informatics with accent on necessity of elaboration of basic algebra that to be discovered by the process of concrete situation analysis even provided incomplet axiomatics.

Key words: algorithmics, algorithms algebra, mathematical model, axiomatic method, incomplet axiomatics.

 

Формулювання проблеми

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

Оскільки алгоритміка була задумана яко галузь перетворень шляхом дій над алгоритмами, то тут природно з'явився термін "алґебрична алгоритміка" [1-3], яка, за словами П. Нодена [4] «осідлала математику» й інформатику "і призначена для алгоритмічного подання (в авторів -описания) методів опрацювання математичних (алґебричних) об'єктів". І далі: "слід проте зазна­чити, що таке твердження виявилось би ще більш виправданим за умови розгляду самих алгоритмів як алґебричних об' єктів і, яко наслідку, інваріантного характеру подання щодо програмної реалізації алгоритмів в об'єктноорієнтованих обчислювальних середовищах" [2].

Автори [3], зазначаючи, що «об'єктом дослідження в алгоритміці служать високорівневі моделі алгоритмів та програм, подавані у вигляді схем, відразу переносять центр уваги від конкретної основи теорії алгоритмів, зазначаючи, що метод алгоритміки ґрунтується на апараті сучасної комп' ютерної алґебри і логіки (не пояснюючи при цьому, що ж це таке - авт.) та орієнтований на конструювання алгоритмів розв' язання різноманітних прикладних задач. Орієнтація на застосування визначає відмін­ність розроблюваних у межах алгоритміки формалізмів від алґебричних систем, покладених в основу класичної теорії алгоритмів: нормальних алгоритмів, обчислювальних функцій, машин Тюрінґа та ін.».

Цим показано, що цей метод досліджень залишає поза увагою питання вибору базових алгоритмів яко поля дії алґебри алгоритмів і, навіть більше того, засвідчує цей факт, підкреслюючи, що «математичним фундаментом алгоритміки слугує дворівнева алґебрична система. Верхній рівень цієї системи становить алґебра схематології (АС) - двоосновна алґебра основа якої - множина неінтер-претованих схем і множина бульових функцій (БФ). Сигнатура операцій АС є традиційною суперпо­зицією. Досліджена ґратка підалґебр (замкнутих клонів) АС» [3]. Це власне і визначає специфіку розглядуваної алгоритміки, коли акцентується «практичне значення для побудови інструментальних (програмних та апаратних засобів проектування і синтезу алгоритмів та програм, а також класів їх,

 

91асоційованих з актуальними предметними областями» (там само) і водночас алгоритміку вибрано за "стрижневий курс" інтеграції програмістських навчальних дисциплін.

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

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

Беручи до уваги історичний аспект як доконечну передумову системного аналізу проблеми алґебризації в теорії алгоритмів, розгляньмо, опираючись на матеріал відомих довідників [4, 5] принцип апріоризму в науці, а в даному разі так званого аксіоматичного методу в математиці.

Початок аксіоматичному методові, що зародився у древній Гелладі, як загально- математич­ному дедуктивному способові побудови математичної теорії, покладено в 19 столітті з виник­ненням неевклідової геометрії у працях М. Лобачевського та Я. Бойяї, коли дослідники усвідомили потребу обґрунтування математики як системи знань і коли постали проблеми установлення несуперечності, незалежності і повноти аксіом теорії. Перший результат в цьому напрямку приніс метод інтерпретації однієї теорії засобами іншої. Першу трактують, починаючи з праць Д. Гільберта, як формальну систему, а другу - як метатеорію таких систем.

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

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

Д. Гільберт сподівався, що метод формалізації дасть змогу будувати весь позитивний зміст математичних теорій на такій, здавалося б, надійній основі, як поняття вивідної формули (теореми формальної системи), а принципові питання типу несуперечливості математичних теорій розв' язувати у формі доведень відповідних тверджень про формальні системи, що формалізують ці теорії. Проте ці його надії зазнали краху після результатів К. Ґеделя початку 30-х років 20 століття, який показав неповноту формалізованої арифметики і непоповнимість її фінітними методами: будь-яке поповнення неминуче приводить до своїх нерозв' язних задач. І хоча формалізована арифметика несуперечлива, і це твердження виражене її мовою, але довести його не можна засобами, сформульованими у ній самій, тобто вже в арифметиці принципово не можливо вичерпати всі змістовно істинні судження класом її вивідних формул якої б то не було формальної системи, і нема ніякої надії знайти фінітне доведення несуперечливості арифметики й обійтись без інших, не фінітних засобів та ідей. Тому намагання згори нібито з загальних принципів математики чи її теорій розв' язати проблему обґрунтування - справа безнадійна і навіть не донкіхотство, а синдром барона Мюнхаузена - знаного героя літератури для дітей з його вичинами типу витягування себе з болота за волосся.

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

Цей аспект є повчальним і в наші дні. Бо після такого "блискучого провалу" надії Д. Гільберта, який навіть небезуспішно змагався з іншим не менш знаменитим фізиком-детерміністом - апріористом

 

92

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

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

Конструктивні науковці, як засвідчують головно стосовно математики відомі публікації [6-9] з акцентом на психологію дослідників, що наука - це творчість, а творчість - не формалізована, як переконують адепти матеріалістичної гносеології. Особливо показова у цьому напрямку анкета Ж. Адамара [8], яка підтверджує тезу, що й математики мислять спершу (при зародженні ідеї) невиразними образами. І тільки один - американський алгебрист Г. Біркгоф ствердив, що мислить формулами. Це щодо "зародження ідеї". А як після цього вона мала б опрацьовуватись?

Тут повчально повернутись до ідей Д. Гільберта. Хоча повна формалізація виявилась нереалізовною, то як показує історія, вона замінилась, як тепер прийнято казати, гільбертизацією -концепцією абстрактного гільбертового простору, що стала об'єднавчою для апарату багатьох математичних (і не тільки) дисциплін як засіб ефективного розв'язання лінійних задач. Навіть свого часу була спроба подати в такий спосіб аксіоматику апарату квантової теорії. Правда, Дж. фон Нойман - її автор - опирався на спектральну теорію лінійних операторів у гільбертовому просторі, що дуже незвично і незручно було для фізиків-теоретиків, які легко сприйняли так зване нормування на S -функцію за П. Діраком. Цей факт фон Нойман коментував словами, що Дірак "лицемірно допустив існування такої функції", тому діраків формалізм некоректний, і це змусило його (фон Ноймана) дати строге доведення. Цим він підтвердив, що навіть не підозрював, що її використовував ще О. Гевісайд як свого роду похідну від його ж "одиничної сходинки", що нею виражав увімкнення струму у працях з теорії телеграфу. Пізніше подібні функції знайшли повне коректне трактування у започаткованій S -функцією теорії дистрибуцій Л. Шварца чи інакше - узагальнених функцій, як їх називали у колишньому Союзі з претензією на оригінальність. Визнання математичної коректності (власне з боку математиків) таких функцій стимулювало запровадження сучасних варіантів гільбертових просторів -гільбертових просторів над гільбертовими просторами та оснащених гільбертових просторів, які, незважаючи на дещо незвичну термінологію, стали адекватним і ефективним апаратом багатьох теоретичних дисциплін сьогодні. Зокрема суттєва роль їх у створенні першим з авторів цієї статті енергетичної теорії стохастичних сигналів, розв'язавши заодно складні питання її математичного формалізму - теорії випадкових процесів, що є важливою сама по собі математичною дисципліною. Тобто ідеї Д. Гільберта відродились у зовсім іншій від початкової формі через поєднання їх з евклідовою метрикою, пов'язаною з енергетичними характеристиками явищ і процесів, так що доля ідей Д. Гільберта є повчальною і сьогодні.

Концепція МАПР - тріади: моделі, алгоритм, програмна реалізація

Розглянуті питання зародження ідей та напрямків математичних досліджень, а особливо так званої проблеми "застосування математики" в конкретних предметних областях, яке початково перегукується з неслушним трактуванням аксіоматичного методу: ніби досить придумати систему аксіом і вже справа залагоджена. Тут варто згадати фундатора модерної логіки Ґ. Фреґе, який у свій час виступав противником формалізму Д. Гільберта і запровадив конструктивні поняття: логічні функції, квантори, дедуктивну систему числення висловлень. І тут на сцену виступає інша лінія розвитку математики, що бере початок від І. Н' ютона і будує моделі, безпосередньо постулюючи властивості розглядуваних об' єктів, навіть не завжди підносячи їх до рангу аксіом, а несупереч-ливість їх має засвідчити факт існування самого об' єкта, властивостями якого ці постулати є. Зрозуміло, що живий об'єкт має багато більше інших властивостей, ніж потрібно для простої формалізованої схеми. Тоді таку формальну схему можна трактувати як модель реалізації навіть не сформульованих явно аксіом (та й вони фізиці, як показує історія, ні до чого, бо фізики, а тим

 

93більше техніки яко прагматики діють, але нічого не доводять). Цей логічний пасаж показує, що моделі фізики і техніки у певному сенсі "зворотні" до математичних pe rse, тобто внутрішньо-математичних. Тому говорити про застосування математичних засобів у фізико-технічних задачах слід дуже-дуже обережно, бо фізична, а більше того - технічна задача має бути завжди розв'язана, а математик може роками шукати доведення існування розв'язку його задачі, так що на відшукання власне самого розв' язку може й життя не вистачити.

Тому у фізико-технічних науках так суттєвою є концепція МАПР-тріади з визначальною роллю у ній власне моделі, як підкреслено в публікаціях [10, 11]. Модель при цьому - це математична структура в сенсі Бурбакі (див. [9]), яка у стислій конструктивній формі втілює у собі суттєві під оглядом потреб знаходження розвязку певного класу задач властивості досліджуваного (реального чи віртуального) об' єкта. При цьому самозрозуміло, що така структура є індикативною -вказує на інформативні ознаки об'єкта і принципи, способи та засоби визначення їхніх величин, що визначає (детермінує) конструкцію потрібних для цього алгоритмів як відповідних процедур.

А звідси випливає мораль (чи сила, як полюбляв казати Г. Сковорода): слід обережно користуватись терміном "алгебрична алгоритміка" стосовно різних предметних областей, бо неслушне використання його створює тільки ілюзію всемогутності (нібито він усе може) так званого наукового способу пізнання. А реальність вимагає як творчого трактування, так і кропіткої праці та поєднання їх для побудови фундаменту конкретної наукової теорії стосовно конкретної предметної області досліджень, зокрема при трактуванні алгоритмів як специфічних математичних об' єктів та розроблення відповідних алґебричних засобів. І тут доречними є слова відомого фізика-теоретика А. Свідзинського: "лише враховуючи, крім раціональних, інтуїтивні, етичні та інші потрібні аргументи, наукові спільноти зрештою виносять вердикт теорії, постійно зберігаючи готовність, у разі потреби, до її перегляду ... «аванс довіри» надається їй найпроникливішими дослідниками, які керуються радше інтуїцією і тонким відчуттям перспективности нових ідей, аніж суто раціональними арґументами" [12].

Цей висновок змушує від апріористичного трактування формальних теорій, зокрема алгорит­мів, повернутись до традиційного трактування їх у фізико-технічних науках з доповненням його логікою за Ґ. Фреґе, бо, як підкреслював ще популяризатор математики В. Сойєр [13], у цих науках нічого не доводять, а висувають постулати, якими послуговуються, доки вони дають слушні висновки. Це ще раз підтверджує, що намагання "згори" ніби з апріорних загальноматематичних принципів розв' язати проблему алгоритмів - справа безнадійна.

Тому, мабуть, і згадану вже алґебричну алгоритміку доцільно розбити на дві незалежні проблеми: 1) побудова базових алгоритмів і базової алґебри і 2) засоби керування потоками алгоритмів і даних у стилі ідей колишньої кібернетики (пор. [14]), бо інакше вона потрапляє в один псевдоклас з "алгоритмами довкола нас" (кулінарні приписи, лікарські рецепти, всілякі службові та технологічні інструкції) чи УРСЗ (універсальний розв'язувач системних задач, англ. Architecture of systems problem solving) [15]. А це, за словами авторів публікації [14], "приводить до певних поривів, результати яких породжують синдром «всезагального (всеобщего) алгоритму» -необґрунтовані надії на всезагальність і загальну значущість їх. Проте «інструментальний» імператив суспільства на певному етапі породжує скепсис". І, на їхню думку, замість розхваленої інформатики слід повернутися до старої доброї кібернетики.

Важливий крок у пошуку шляхів формалізації теорії алгоритмів, який привів до створення оригінальної алгебри алгоритмів, зробив другий співавтор цієї статті, який виокремив з усієї алгоритміки проблему алґебризації базової основи, запровадивши нові адекватні не комутативності операцій, що є розвитком ідей засновника сучасної логіки Ґ. Фреґе, зокрема про конечність виходу за лінійну впорядкованість [16].

Історію запровадження, формулювання ідеї та розроблення понять, термінів і засобів нового трактування подання алгоритмів та перетворень їх досить докладно висвітив сам автор (див. [17]), підкресливши, що ця нова теорія була названа як "Теорія впорядкувань" і зареєстрована в УкрФАП 1987 р. під номером АП0159 на 450 с., а також факт, що "проф. Я. Драґан настоював на створенні варіанта алгебри алгоритмів, який охопив би теорію впорядкувань, базовану на алгебрі логіки, як частковий випадок і став би подальшим якісно новим етапом розвою алгебри алгоритмів", а заодно "звернув увагу на недоліки означень теорії впорядкувань". Мова тут власне про потребу вироблення і відповідної термінології, і символіки цієї нової алґебри яко некомутативної і за неповної аксіоматики.

 

94

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

Підсумки

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

При цьому 1) постуляти в фізико-технічних галузях дають загалом неповну аксіоматику і доконче дослідник має працювати із нею як такою; 2) важливо зосередити зусилля на алґебрі базових алгоритмів предметної області; 3) комбінування базових алгоритмів керується правилами управління потоками даних; не може бути універсальних алгоритмів: пошуки їх - це прояв уже згадуваного синдрому; 4) реалізація ідеї Ґ. Фреґе - вихід за межі лінійності, а упорядкованість рівносильна врахуванню некомутативності; 5) концепція Бурбакі математичної структури для вираження моделей досліджуваного об'єкта є природною для предметних областей, але термін аксіома в ній немає нічого спільного з тлумаченням його як очевидної істини, а радше як постуляти фізиків і техніків, які можуть умовно грати роль аксіом, будучи на якийсь час "піднесеними до цього рангу", і то доти, доки дають слушні результати теорії (та й у певній конкретній предметній області), "зберігаючи готовність, у разі потреби, до її перегляду".

 

1. Глушков В.М., Цейтлин Г.Е., Ющенко Е.Л. Алгебра. Языки. Программирование. 3-у изд. _ Киев: Наук. Думка, 1989. - 376 с. 2. Цейтлин Г.Е., Мохница А.С. Что такое алгоритмика ? // Проблемы программирования. - 2004. - № 2, 3. - С.52-58. 3. Цейтлин Г.Е., Юсим Г.В. Развитие алгебраических основ алгоритмики и перспективные информационные технологии // Проблемы управления и информатики. - 1997. - № 38. - С.89-95. 4. Большой энциклопедический словарь. Математика /Гл. ред. Ю.В. Прохоров, 3-е изд. - М: Большая рос. энц. 1998. - 848 с. 5. Бородин А.И., Бугай А.С. Выдающиеся математики: Биогр. слов. - справ., 2-е изд. - К.: Рад. шк. 1987. - 686 с. 6. Пуанкаре А. Математические открытия //Математики о математике. - М. : Знание, 1967. - С.24 - 32. 7. Математика серед наук / В. Левицький, М. Зарицький, І. Свенціцький. - Львів: Сп. діло, 1927. - 58 с. 8. Адамар Ж. Исследование психологии процесса изобретения в области математики. -М. : Сов. радио, 1970. - 152 с. 9. Бурбаки Н. Архитектура математики. Математика или математики ? // Н. Бурбаки. Очерки по истории математики. - М.: ИИЛ, 1963. - С.245-259. 10. Драґан Я., Медиковський М., Овсяк В., Сікора Л., Яворський Б. Концепції математичної моделі і праксеології в теорії сиґналів і систем // Обчислювальні методи і системи перетворення інформації. Збірник праць конференції до 70-річчя Б. Попова. - Львів: Видання Фізико-механічного інституту НАНУ, 2010. - 250 с. - С.101-103. 11. Драґан Я., Медиковсь-кий М., Овсяк В., Сікора Л., Яворський Б. Системний аналіз концепції та принципів побудови математичної моделі досліджуваного обєкту в фізико-технічних науках та оцінювання її якості // Вісник Нац. ун-ту "Львівська політехніка", "Компютерні науки та інформаційні технології". - 2010. -№ 686. - С.170-179. 12. Свідзинський А. Математичні методи теоретичної фізики. - К. : Видавництво ім. Олени Теліги, 1998. - 442 с. 13. Sawyer W.W. Wposzukiwaniu modelu matematycznego. - Warszawa: Wiedzapowszechna, 1975. - 438 s. 14. Азаров С.С., Стогний А.А. Существует ли наука «информатика»? Новая апология кибернетики // Управляющие системы и машины, 1993, № 4. - С.3-20. 15. Клир Дж. Системология. Автоматизация решения системных задач. - М.: Радио и связь, 1990. - 544 с. 16. Ovsyak V.K. Computational models and algebra of algorithms // Вісник Нац. ун-ту "Львівська політехніка " " Інформаційні системи та мережі". - 2008. - № 621. - С.3-18. 17. Овсяк В.К. Основні етапи станов­лення і розвою секвенційних алгоритмів // Комп'ютерні технології друкарства. - 2005. - № 14. - С.137.

 

95

Страницы:
1 


Похожие статьи

Я Драґан, в Овсяк - Системний аналіз і методологія алгебри алгоритмів