The operating model of communicative informations systems

Prombles in programming 2014; 1: 55-61

Saved in:

Bibliographic Details
Date:	2025
Main Author:	Zubenko, V.V.
Format:	Article
Language:	Ukrainian
Published:	Інститут програмних систем НАН України 2025
Subjects:	UDC 519.9
Online Access:	https://pp.isofts.kiev.ua/index.php/ojs1/article/view/731
Tags:	Add Tag No Tags, Be the first to tag this record!
Journal Title:	Problems in programming

Institution

Problems in programming

id	pp_isofts_kiev_ua-article-731
record_format	ojs
resource_txt_mv	ppisoftskievua/13/8ebeaef7c172f5baf5cc06208a9ac513.pdf
spelling	pp_isofts_kiev_ua-article-7312025-04-09T22:38:00Z The operating model of communicative informations systems Операційна модель комунікативних інформаційних систем Zubenko, V.V. UDC 519.9 УДК 519.9 Prombles in programming 2014; 1: 55-61 Розглядається операційна модель комунікативних інформаційних систем (КІС). Введено поняття абстактного алгоритму (А-алгоритму) як загальної моделі неавтоматних алгоритмічних систем. Показано, що А-алгоритмам притаманні усі властивості класичних алгоритмів, а для класу, так званих, табличних А-алгоритмів виконуються теореми про регулярний аналіз та синтез.Prombles in programming 2014; 1: 55-61 Інститут програмних систем НАН України 2025-04-09 Article Article application/pdf https://pp.isofts.kiev.ua/index.php/ojs1/article/view/731 PROBLEMS IN PROGRAMMING; No 1 (2014); 55-61 ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ; No 1 (2014); 55-61 ПРОБЛЕМИ ПРОГРАМУВАННЯ; No 1 (2014); 55-61 1727-4907 uk https://pp.isofts.kiev.ua/index.php/ojs1/article/view/731/783 Copyright (c) 2025 PROBLEMS IN PROGRAMMING
institution	Problems in programming
baseUrl_str	https://pp.isofts.kiev.ua/index.php/ojs1/oai
datestamp_date	2025-04-09T22:38:00Z
collection	OJS
language	Ukrainian
topic	UDC 519.9
spellingShingle	UDC 519.9 Zubenko, V.V. The operating model of communicative informations systems
topic_facet	UDC 519.9 УДК 519.9
format	Article
author	Zubenko, V.V.
author_facet	Zubenko, V.V.
author_sort	Zubenko, V.V.
title	The operating model of communicative informations systems
title_short	The operating model of communicative informations systems
title_full	The operating model of communicative informations systems
title_fullStr	The operating model of communicative informations systems
title_full_unstemmed	The operating model of communicative informations systems
title_sort	operating model of communicative informations systems
title_alt	Операційна модель комунікативних інформаційних систем
description	Prombles in programming 2014; 1: 55-61
publisher	Інститут програмних систем НАН України
publishDate	2025
url	https://pp.isofts.kiev.ua/index.php/ojs1/article/view/731
work_keys_str_mv	AT zubenkovv theoperatingmodelofcommunicativeinformationssystems AT zubenkovv operacíjnamodelʹkomuníkativnihínformacíjnihsistem AT zubenkovv operatingmodelofcommunicativeinformationssystems
first_indexed	2025-07-17T09:48:11Z
last_indexed	2025-07-17T09:48:11Z
_version_	1838409500567011328
fulltext	Експертні та інтелектуальні інформаційні системи © В.В. Зубенко, 2014 ISSN 1727-4907. Проблеми програмування. 2014. № 1 55 УДК 519.9 В.В. Зубенко ОПЕРАЦІЙНА МОДЕЛЬ КОМУНІКАТИВНИХ ІНФОРМАЦІЙНИХ СИСТЕМ Розглядається операційна модель комунікативних інформаційних систем (КІС). Введено поняття абста- ктного алгоритму (А-алгоритму) як загальної моделі неавтоматних алгоритмічних систем. Показано, що А-алгоритмам притаманні усі властивості класичних алгоритмів, а для класу, так званих, таблич- них А-алгоритмів виконуються теореми про регулярний аналіз та синтез. Вступ В роботах [1, 2] введено поняття комунікативної платформи інформатики. Проголосивши предметом комунікативної інформатики конструктивні моделі кому- нікативних процесів та систем (так звані, комунікативні інформаційні системи та процеси), в [3] побудовано композиційну модель таких систем. Ця модель сугубо алгебраїчна, що описує функціональну семантику останніх – структуру інформа- ційних об’єктів та інформаційних полів (даних), а також функцій і співвідношень, визначених на даних. Тепер будемо розг- лядати та уточнювати операційну (алгори- тмічну) семантику комунікативних інфор- маційних систем. 1. Комунікативні інформаційні системи та їхні моделі Нагадаємо деякі поняття, пов’язані з комунікативними інформаційними сис- темами та їхніми моделями. Необхідні де- талі можна знайти в [2]. Як зазначено ви- ще, КІС це конструктивна модель комуні- кативних систем (КС) – центрального по- няття комунікативної інформатики. Скла- довими КС є : 1) предметна область (ПрО) з пев- ною сукупністю інформаційних об’єктів та співвідношень між ними; 2) суб’єкт-ініціатор (далі ініціатор), який формує і передає суб’єкту-виконавцю певну вхідну та приймає від нього певну вихідну інформацію; 3) суб’єкт-виконавець (далі викона- вець), який приймає вхідну інформацію, аналізує її, обробляє та повертає як вихід- ну ініціатору. Головне призначення КС полягає у здійсненні комунікативних процесів, кож- ний з яких розгортається в певному часо- вому просторі та в результаті встановлює зв’язок між певними об’єктами предметної області системи. За своєю роллю у процесі ці об’єкти розподіляються на вхідні та вихі- дні. З перших розпочинається процес, останніми закінчується. Комунікативний процес складається з етапів, які разом ут- ворюють його життєвий цикл. Останній розпочинається ініціатором, який формує й передає виконавцю за допомогою засо- бів зв’язку повідомлення, що містить за- пит на обробку певних вхідних інформа- ційних об’єктів (не змішувати з запитами в інформаційно-пошуковими системах; тут термін “запит” трактується як загаль- не поняття з більш широким змістом). Запит окрім останніх містить інформацію про мету обробки, яка може бути сформу- льована неявно – як вимоги до очікуваних вихідних об’єктів або явно – як детальний опис їх отримання за вхідними об’єктами. В обох випадках мета декларує певне співвідношення між об’єктами і сама по- дається у вигляді спеціального інформа- ційного об’єкта – програми. Підкреслимо, що програма не обов’язково є імператив- ною. Вихідні об’єкти є результатом вико- нання обробником певної внутрішньої процедури, яка реалізує запит. Зазвичай виконавець має власні ін- формаційні об’єкти – внутрішні (сукупно- сті яких утворюють його стани), на відміну від зовнішніх – тих, що фігурують в пред- метній області. Тому сам запит містить не вхідні об’єкти виконавця, а тільки їхні Експертні та інтелектуальні інформаційні системи 56 прообрази, які після кодування утворюють початковий стан виконавця. Це стосується й вихідних внутрішніх об’єктів поданих у заключному стані процесу обробки. Вони потребують декодування. Комунікативна платформа накладає певні обмеження на інформаційні системи як модель КС, а саме: вони мають бути обов’язково дескриптивними і не просто дескриптивними – а конструктивними. Дескриптивність КІС означає, що до скла- ду її елементів входять дескриптивні сис- теми (ДС), в яких подаються (описуються) усі її інформаційні об’єкти: вхідні і вихідні дані, запити та внутрішні процедури. Мова йде не про одну, а, як правило, про декіль- ка ДС, тому що інформаційні об’єкти різ- них суб’єктів системи потребують різних дескриптологічних засобів. Як мінімум – мову специфікації запитів для ініціатора і внутрішню мову для виконавця. Остання описує внутрішні інформаційні об’єкти та внутрішні процедури, які задають правила для реалізації кожної з програм мови спе- цифікацій. Внутрішні мови на відміну від мов специфікацій обов’язково є імперати- вними. Конструктивність КІС означає, що її мова (мови) специфікацій та внутрішня мова є фінітними, тобто усі об’єкти в них – скінченно подані, а внутрішня мова ще і обов’язково інтенсіональною. Мови спе- цифікацій та внутрішня мова конструктив- них КС самі називаються конструктивни- ми, внутрішні мови – алгоритмічними, а внутрішні процедури – алгоритмами. На- голосимо, що для конструктивності дові- льної мови специфікацій недостатньо тіль- ки її фінітності – необхідна також наяв- ність алгоритмічної мови, яка задає реалі- зацію усіх її запитів. В композиційній моделі КІС ініціа- тор та виконавець подаються як спеціальні відповідно вхідна й вихідна формалізовані композиційні  системи, пов’язані між собою функціями кодування та декодуван- ня об’єктів. 2. Операційна модель КІС Мета операційної моделі КІС – кон- кретизувати семантику її алгоритмічної мови. Це вимагає уточнення таких за- гальних понять як обчислювальна проце- дура, обчислення та алгоритм. Ці поняття відносяться до фундаментальних понять математики (зокрема, обчислювальної її гілки) та математичної логіки. В процесі їхньої експлікації ми хочемо відійти від прийнятої у теорії алгоритмів практики визначати якийсь конкретний клас алгори- тмів (машин Тюрінга, алгоритмів Маркова тощо) і, посилаючись на його універсаль- ність та тезу Чорча, пов’язувати з ним за- гальне поняття алгоритму та обчислення. Такий підхід, оснований на моделюванні, достатній, можливо, для потреб математи- чної логіки та конструктивної математики, є занадто спеціалізованим і недостатнім для розбудови основ інформатики та про- грамування та й, на наш погляд, і для самої математики в цілому. Адже конкретні при- клади, які б вони цікаві не були, не можуть замінити загального поняття. Щоб уточнити загальне математи- чне поняття обчислювальної процедури, спробуємо з’ясувати його складові. Якщо звернутися до окремо взятого обчислення, то побачимо не одноразовий акт, а серію їх. Розпочавшись у певний фіксований момент часу з заданою початковою інфо- рмацією на вході, обчислення розгорта- ється у часі і супроводжується виконан- ням певних ціленаправлених елементар- них дій з визначенням результату. Тому будь-яке обчислення передбачає, насам- перед, наявність певного обчислювального простору  , який складається з лінійно- впорядкованого часового простору  і сукупності станів S . Часовий простір до- датково задовольняє умові градації: для будь-якого моменту часу  існують його безпосередньо попередній та наступний моменти – відповідно верхня границя йо- го нижнього конусу { : }sup x x    та нижня границя верхнього конусу { : }.inf x x    Вважається, що у часовому просторі не- має найменшого та найбільшого момен- тів часу. Стани представляють у просторі інформаційну складову обчислень. Упо- Експертні та інтелектуальні інформаційні системи 57 рядковані пари ( , )t s S називаються точками або конфігураціями обчислюва- льного простору  . Необхідні також су- купність { : \| 0}if S S i    елементар- них операцій на станах та функція керуван- ня або переходів простору, яка регулює порядок застосування операцій в обчис- леннях. Вона пов’язує з кожною конфігу- рацією обчислення одне або кілька можли- вих елементарних перетворень його пото- чного стану. Покладемо її як таку, що має вигляд : S   . У загальному випадку функція ке- рування може бути більш складною як, наприклад, у моделях з глобальним та ло- кальним часовими просторами [4], де вона може задавати й перетворення локального часового компонента простору. Якщо ло- кальний час збігається з основним, то це дає можливість повертати обчислення на- зад і продовжувати його іншим чином. Функція керування може також розпарале- лювати процеси обчислень. Функція керу- вання може бути багатозначною, але тоді мати скінченний індекс, тобто для кожної пари її аргументів має існувати тільки скі- нченна кількість варіантів значень. Обчислювальною процедурою у просторі  із сукупністю елементарних перетворень  і функцією керування  називається трійка , ,δP    . Кожна обчислювальна процедура породжує певну сукупність обчислюваль- них процесів у просторі  . Обчислення :p S  за процедурою P із початком у момент часу  і початковим станом 0s визначається рекурентно: 0p s  і для всіх   ( )p f p   , де ( , ).f p     Функція керування за поточним моментом часу  і станом p  у попередній момент часу визначає сукупність елементарних операцій, які можуть бути застосовані для отримання стану процесу в момент  . Бу- демо говорити, що обчислення p у мо- мент часу  переходить від попереднього стану до наступного стану p . Варіантів таких переходів може бути декілька, оскі- льки функція переходу багатозначна. На- справді їх може бути: а) два і більше (у випадку недетермінованих процедур); б) рівно один (у випадку детермінованих процедур); в) жодного (обчислення зупи- няється). Зазвичай інтерес становлять не всі можливі обчислення в процедурі, а насам- перед ті, що розпочинаються в певний фік- сований момент часу з певних виділених вхідних станів і закінчуються певними виділеними вихідними станами. Тому вве- демо поняття ініціальної обчислювальної процедури 0 fin 0( , , )P S S  над простором  як четвірки 0 fin 0( , , , )P S S  , де P – певна процедура над простором  , 0S S та finS S – виділені підмножини відповідно вхідних і вихідних станів, 0  – початко- вий момент часу. Далі під процедурою будемо розуміти саме ініціальний її варі- ант. Результативним назвемо обчислення p у процедурі P , що розпочинається в момент часу 0 із певного початкового стану 0p  0 0s S , закінчується у певний момент часу у вихідному стані, а всі його проміжні стани – не вихідні. Для результа- тивного обчислення p останній його стан p називається заключним і є результа- том. Результат позначається  * 0P s і є єдиним, якщо функція керування однозна- чна. У деяких випадках за результат обчи- слення береться не сам заключний стан, а значення на ньому певного результуючого часткового відображення fin:Val S B . В деяких випадках вважають заключними і ті скінченні обчислення, на останніх станах яких не визначена функція керування. Якщо в результативному обчислен- ні зняти умову, щоб усі проміжні стани були не вихідними, то таке обчислення називатимемо гіперрезультативним. Його вихідні стани можуть зустрічатися й серед проміжних, а результат позначається  ** 0P s . Коли для певного обчислення зна- чення результуючого відображення Val на заключному стані не визначене, то воно Експертні та інтелектуальні інформаційні системи 58 вважається безрезультатним. Безрезуль- татними є зазвичай і нескінченні обчис- лення. Але у деяких випадках можна і тут передбачити механізм для встановлення результату. Адже саме результат є квінте- сенцією будь-якого обчислення як проце- су. Одним із таких механізмів може бути, наприклад, встановлення на станах певно- го часткового порядку, і за результат не- скінченного обчислення – взяття наймен- шої верхньої границі його станів. Цей шлях може бути цікавим як доповнення апроксимаційної платформи Д. Скотта [5], яка сама по собі є чисто екстенсіональною і непроцедурною. Скажемо також про варіанти закін- чення обчислень з використанням часових критеріїв. Обчислення можуть закінчува- тись (примусово) за досягненням певного моменту часу або тільки після нього чи вичерпання його ліміту тощо. З кожною процедурою 0 0( , , )finP S S  пов’язані дві відповідності на вхідних станах * 0: finP S S та ** 0: finP S S , значення яких на початко- вому стані 0 0s S складають результати всіх результативних і гіперрезультативних обчислень із початком у момент 0 на 0s . Про відповідності P та P гово- рять, що їх обчислює процедура P . Функ- ції P та Q називаються еквівалентними ( P Q ), якщо відповідності P та Q , які вони обчислюють, збігаються. Стан функ- ції 0 0( , , )finP S S  назвемо припустимим, якщо він зустрічається серед станів деяко- го її результативного обчислення. Покла- демо accS S – підмножину всіх припус- тимих станів процедури P . Для відповід- ностей, які обчислює процедура стани за межами підмножини accS зайві. Нехай  0 0, ,finP S S    – ініціальна функція над простором  із множиною станів accS і обмеженими на  елементарними опера- ціями, функцією переходу та вхідними й вихідними станами процедури P . Очевид- но, що функції P та P еквівалентні. Фун- кція, усі стани якої припустимі, називаєть- ся зведеною. Багато прикладів процедур і саме процедур-неалгоритмів можна знайти вже на поверхні, в класичних задачах алгебри й геометрії (неалгоритмічність процедур тут пов’язана з неконструктивністю їхніх ста- нів, що складаються з актуально нескін- ченних дійсних чисел та фігур на площи- ні). Так, задачі з планіметрії на побудову за допомогою циркуля й лінійки є фактич- но задачами на пошук тих чи інших про- цедур. Станами в них є сукупності фігур на площині, які можуть бути побудовані за допомогою циркуля й лінійки та операцій виділення довільної точки площини, точок перетину фігур, операцій іменування точок і фігур, а також умовних варіантів подіб- них операцій. Часовий простір – дискрет- ний і збігається з натуральними числами. Приклади таких класичних задач є задача на побудову середини відрізка на площині (з відповідною процедурою розв’язку) або задача пошуку найбільшої спільної міри двох відрізків (алгоритм Евкліда) тощо. Підкреслимо, що ці приклади не штучні, а широко відомі. Цікава ситуація виникає у випадку, коли результат розв’язку обчислювальної задачі не один, а їх декілька. Якщо розв’язок такої задачі забезпечує недетер- мінована процедура, то його завжди можна детермінізувати, якщо перейти до гіпероб- числень. Наприклад, нехай для розв’язку задачі виконавець використовує дошку й крейду і необхідно побудувати два різні розв’язки якоїсь задачі на побудову. Тоді після побудови першого дошка витираєть- ся і процедура повертається в один із по- передніх станів, але не в попередню конфі- гурацію – момент часу інший. Завдяки цьому процес побудови другого розв’язку може бути просто зсунутим в часі і продо- вжений детерміновано. Процедури, керування діями в яких реально залежить від часової компоненти, будемо називати темпоральними на відмі- ну від автоматних, коли таке керування не залежить від часу. Класичними прикла- дами автоматних процедур є скінченні й магазинні автомати, машини Тьюрінга, деякі ігрові числення тощо. Але в останніх Експертні та інтелектуальні інформаційні системи 59 часові фактори можуть відігравати і важ- ливу роль. В таких випадках вони набува- ють ознак темпоральних процедур. Так, у багатьох іграх важливою є черговість ходу. У грі в шахи (шашки), наприклад, у всі непарні моменти часу ходять білі, а в парні – чорні. Однак тут є й інші більш принципові обставини, пов’язані з часом – рокіровка короля залежить від того, чи рухався він до цього моменту. У деяких моделях на стратегію вибору чергового ходу може впливати обмеженість часу від- веденого на гру (гра в цейтноті). З найбільш відомих алгоритмічних моделей темпоральними за природою є дискретні перетворювачі В.М. Глушкова, але вже в моделі з локальним часом, яку ми тут не розглядаємо. Щоб отримати загальне поняття ал- горитму, нам залишилося конструктуризу- вати обчислювальні процедури, тобто виб- рати для них алгоритмічну мову. Для цьо- го спочатку розглянемо абстрактну модель виконавців КС у вигляді, так званих, обчи- слювальних  систем. Сигнатурою називається шестірка 0 1 2 3 4 5( , , , , , )       , де 0 , 1 { : 0},it i   2 { : 0},is i   3 { : 0},if i   4 { : 0},jp j   5  { : 0}k k  – відповідно сукупності часо- вих констант та змінних, предметних змін- них, унарних функціональних символів, предикатних та керувальних символів. Для інтерпретації сигнатури  в певному обчислювальному просторі ( , )S   необхідно вибрати в ньому кон- кретні початкові моменти часу для часових констант, часовим та предметним змінним поставити у відповідність їхній типи – су- купності  та S , функціональним, преди- катним та керувальним символам – відпо- відно елементарні операції, предикати на станах та функції керування простору. При цьому предикатним символам 0p та 1p p відповідають сукупності вхідних та вихідних станів. Таке співставлення I сигнатурним символам їхніх значень нази- вається інтерпретацією сигнатури  в просторі  . Значення сигнатурного сим- вола c при інтерпретації I домовимося позначати Ic . Інтерпретація I може бути частковою. Наприклад, якщо часові конс- танти та предикатні символи 0p та p непроінтерпретовані, то сигнатура назива- ється неінеціалізованою. В інших випадках можуть залишатись непроінтерпретовани- ми деякі змінні, а також частина імен фун- кцій та предикатів. Проінтерпретовані сигнатури нази- ваються обчислювальними  системами і позначаються ( , , )C I   або I  . Кожному проінтерпретованому керуваль- ному символу I k такої системи C відпо- відає певна ініціальна обчислювальна про- цедура у просторі  . Як зазначалося вище, комунікатив- на платформа накладає певні обмеження на КС та їхні моделі, а саме – вони мають бути конструктивними. Це стосується і обчислювальних  систем як моделей виконавців. За означенням, має бути фіні- тна інтенсіональна ДС L для подання усіх елементів обчислювальних  сис- тем: моментів часу, станів, елементарних операції та функцій керування. Алфавіт мови L обов’язково включає сигнатуру  , а головними її об’єктами є схеми алго- ритмів, які подають функції керування процедур. Інтенсіонал конкретної схеми алгоритму фінітно описує значення функ- ції керування для кожної припустимої конфігурації її процедури. Двійка ( , )A C L називається фо- рмалізованою обчислювальною  систе- мою, а проінтерпретовані схеми алгорит- мів системи A – абстрактними алгори- тмами. Скорочено перші будемо називати також алгоритмічними  системами, другі – A -алгоритмами чи просто алго- ритмічними системами та відповідно ал- горитмами, якщо відомо яка система A мається на увазі. Як і процедури, абстрактні алгори- тми можуть бути детермінованими й неде- термінованими. Відповідності, що обчис- люються ними називаються алгоритмічно обчислювальними. Наведемо основні властивості Експертні та інтелектуальні інформаційні системи 60 A -алгоритмів, які безпосередньо випли- вають з їхнього означення. Масовість. A -алгоритм може бу- ти застосований до будь-якого вхідного стану. Темпоральність. Обчислення за A -алгоритмом відбуваються в глобально- му часовому просторі, елементи якого мо- жуть впливати на вибір перетворень пото- чного стану. Елементарність. У кожний момент часу в обчисленні виконується одна еле- ментарна операція з фіксованої сукупності таких операцій. Визначеність. Порядок застосу- вання елементарних операцій в обчислен- ні не довільний, а визначається функці- єю переходу за поточною конфігурацією обчислення. Результативність. У кожному A -алгоритмі є механізм завершення об- числень. Фінітність. Скінченність подання A -алгоритму. Релятивність. Відносність поняття A -алгоритму. Конструктивність A -алго- ритму прямо залежить від його алгоритмі- чної мови. Алгоритм в одній алгоритміч- ній системі не обов’язково буде алгорит- мом в іншій. Інший аспект релятивності A -алгоритмів пов’язаний з частковістю інтерпретацій в алгоритмічних системах, а саме, у деяких випадках символи елемен- тарних операції (усі чи їхня частина) мо- жуть бути не проінтерпретованими. Такі символи операцій називаються оракулами, а відповідні алгоритмічні системи – сис- темами з оракулами. Оракули можна тра- ктуватися по різному, але в основному – як операції, дія яких невідома в межах ал- горитмічної системи. Це може бути, на- приклад, тимчасово чи навпаки – дія відо- ма, але тільки поза межами системи або взагалі не відома. Як бачимо, A -алгоритмам прита- манні всі основні властивості класичних числових і словарних алгоритмів. Однак з’явилися й нові специфічні риси – темпо- ральність та релятивність. Алгоритмічні -системи можуть виступати моделями виконавців – вихід- ними системами в КІС. При цьому внут- рішніми процедурами виступають A - алгоритми, станами – інформаційні поля, а внутрішньою мовою – алгоритмічна мова. Алгоритмічні вихідні системи називають ще операційними, щоб підкреслити інтен- сіональний характер внутрішніх процедур як алгоритмів у противагу екстенсіональ- ній природі операторів оновлення в компо- зиційній моделі вихідних систем. Четвірка   , ,in out c,dS S S , де inS та outS – деякі вхідна та алгоритмічна ви- хідна системи, а c та d – відповідно фун- кції кодування та декодування, називаєть- ся алгоритмічною (операційною) моделлю комунікативних інформаційних систем. У зв’язку з релятивністю виникає задача порівняння різних класів A - алгоритмів за потужністю. Будемо казати, що A -алгоритм 1A з множиною станів 1S є моделлю A -алгоритму 2A з множиною станів 2S відносно функції кодування 2 1: S S  , якщо для кожного із вхідних станів s A -алгоритму 2A виконується 1 * 2 1( ) ( ( ))A s A s  . Нехай 1K та 2K – довільні класи A -алгоритмів над обчислюваними прос- торами 1 1 1,S   та 2 2 2,S   , від- повідно. Зафіксуємо певну функцію коду- вання 2 1: S S  . Кажуть, що клас A -алгоритмів 1K моделює клас A - алгоритмів 2K , якщо для кожного A - алгоритму з 2K у класі 1K існує його мо- дель. Якщо класи A -алгоритмів моделю- ють один одного відносно певних фіксова- них функцій кодування, то вони назива- ються еквівалентними відносно цих функ- цій. Фіксуючи конкретні обчислювальні простори  та відповідні алгоритмічні мови, можна отримати весь спектр класич- них алгоритмічних та ігрових систем (ма- шини Тьюрінга, алгоритми Маркова й Ко- лмогорова – Успенського, дискретні пере- творювачі, трансдюсери, різні класи схем програм, формальні граматики й числення Експертні та інтелектуальні інформаційні системи 61 Поста, ігрові числення – шахи тощо). Усі перелічені класи класичних ал- горитмів неігрових числень є автоматни- ми, еквівалентними відносно достатньо простих функцій кодування і за Чорчем – універсальними (не стосується ігрових чи- слень). Для ілюстрації деяких можливостей операційної моделі наведемо один важли- вий клас абстрактних алгоритмів – табли- чні алгоритми [4]. Нехай часовий простір  ізоморф- ний адитивній групі Z цілих чисел і P – довільна процедура у просторі ,Z S  . Насправді, табличні алгоритми мо- жуть бути визначені у будь-якому факто- ризованому часовому просторі. Фактори- зуємо функцію переходу  за часовим аргументом і станами. Зафіксуємо деяку часову константу 0k  і певне відношення еквівалентності  на станах із .S Будемо казати, що функція переходу  періодична за модулем відношення  із періодом k ( k -періодична за модулем  ), якщо для будь-яких еквівалентних станів p та s і довільного моменту часу t Z виконуєть- ся ( , ) ( , )t p t k s   . Функція переходу  просто періодична за модулем  , якщо вона k -періодична за модулем  для де- якого k . Якщо еквівалентність  має скі- нченний індекс \| \| і розв’язні класи, то процедура з періодичною функцією пере- ходу є абстрактним алгоритмом, який на- зивається табличним. Табличні алгоритми можна задава- ти двовимірними таблицями розміром \| \|k  : перший вимір відповідає числам від 0 до 1k  , другий – класам еквівален- тності  , а в клітинах таблиці розміщу- ються значення функції переходу. Традиційні алгоритмічні системи є табличними як абстрактні алгоритми, а оскільки вони автоматні, то й 1 періо- дичні (скінченні автомати, МП-автомати тощо). Наприклад, машина Тьюрінга є табличним 1 періодичним алгоритмом: два її стани еквівалентні, якщо їхні вну- трішні стани та стани робочих комірок збігаються. В роботі [4] показано, що для таб- личних алгоритмів мають місце теореми про регулярний аналіз та синтез. Висновки В роботі здійснена спроба уточнити загальне поняття обчислювальної проце- дури та абстрактного алгоритму. На їхній основі запропонована операційна модель КІС. Наведено поняття табличного алгори- тму як загальної моделі для усіх класичних алгоритмічних систем. 1. Зубенко В.В. Програмування: Навчальний посібник.– К.: ВПЦ Київський університет, 2011. – 625 с. 2. Зубенко В.В. Про комунікативну інформа- тику // Вісник КНУ ім. Тараса Шевченка, сер. фіз.-мат. наук, вип. 4. – 2012. 3. Зубенко В.В. Композиційна модель комунікативних інформаційних систем // Вісник КНУ ім. Тараса Шевченка, сер. Кібернетика, вип. 13. – 2013. 4. Зубенко В.В. Темпоральні процедури та алгоритми // Проблеми програмування. – 2006. – № 2-3. – C. 53–59. 5. Скотт Д. Набросок математической теории вычислений // Кибернетический сборник. – М.: Мир, 1977. – Вып. 24. – С. 107–121. Одержано 24.05.2013 Про автора: Зубенко Віталій Володимирович доцент, кандидат фізико-математичних наук, доцент. Місце роботи автора: Київський національний університет ім. Тараса Шевченка 01601, Київ, вул. Володимирська, 64/13. Тел.: (044) 259 0519. E-mail: vvz@unicyb.kiey.ua mailto:vvz@unicyb.kiey.ua

The operating model of communicative informations systems

Institution

Similar Items