Операційна модель комунікативних інформаційних систем

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

Full description

Saved in:

Bibliographic Details
Published in:	Проблеми програмування
Date:	2014
Main Author:	Зубенко, В.В.
Format:	Article
Language:	Ukrainian
Published:	Інститут програмних систем НАН України 2014
Subjects:	Експертні та інтелектуальні інформаційні системи
Online Access:	https://nasplib.isofts.kiev.ua/handle/123456789/86740
Tags:	Add Tag No Tags, Be the first to tag this record!
Journal Title:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Cite this:	Операційна модель комунікативних інформаційних систем / В.В. Зубенко // Проблеми програмування. — 2014. — № 1. — С. 55-61. — Бібліогр.: 5 назв. — укр.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

_version_	1859610433135050752
author	Зубенко, В.В.
author_facet	Зубенко, В.В.
citation_txt	Операційна модель комунікативних інформаційних систем / В.В. Зубенко // Проблеми програмування. — 2014. — № 1. — С. 55-61. — Бібліогр.: 5 назв. — укр.
collection	DSpace DC
container_title	Проблеми програмування
description	Розглядається операційна модель комунікативних інформаційних систем (КІС). Введено поняття абстактного алгоритму (А-алгоритму) як загальної моделі неавтоматних алгоритмічних систем. Показано, що А-алгоритмам притаманні усі властивості класичних алгоритмів, а для класу, так званих, табличних А-алгоритмів виконуються теореми про регулярний аналіз та синтез.
first_indexed	2025-11-28T11:55:09Z
format	Article
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
id	nasplib_isofts_kiev_ua-123456789-86740
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
issn	1727-4907
language	Ukrainian
last_indexed	2025-11-28T11:55:09Z
publishDate	2014
publisher	Інститут програмних систем НАН України
record_format	dspace
spelling	Зубенко, В.В. 2015-09-30T13:50:51Z 2015-09-30T13:50:51Z 2014 Операційна модель комунікативних інформаційних систем / В.В. Зубенко // Проблеми програмування. — 2014. — № 1. — С. 55-61. — Бібліогр.: 5 назв. — укр. 1727-4907 https://nasplib.isofts.kiev.ua/handle/123456789/86740 519.9 Розглядається операційна модель комунікативних інформаційних систем (КІС). Введено поняття абстактного алгоритму (А-алгоритму) як загальної моделі неавтоматних алгоритмічних систем. Показано, що А-алгоритмам притаманні усі властивості класичних алгоритмів, а для класу, так званих, табличних А-алгоритмів виконуються теореми про регулярний аналіз та синтез. uk Інститут програмних систем НАН України Проблеми програмування Експертні та інтелектуальні інформаційні системи Операційна модель комунікативних інформаційних систем The operating model of communicative informations systems Article published earlier
spellingShingle	Операційна модель комунікативних інформаційних систем Зубенко, В.В. Експертні та інтелектуальні інформаційні системи
title	Операційна модель комунікативних інформаційних систем
title_alt	The operating model of communicative informations systems
title_full	Операційна модель комунікативних інформаційних систем
title_fullStr	Операційна модель комунікативних інформаційних систем
title_full_unstemmed	Операційна модель комунікативних інформаційних систем
title_short	Операційна модель комунікативних інформаційних систем
title_sort	операційна модель комунікативних інформаційних систем
topic	Експертні та інтелектуальні інформаційні системи
topic_facet	Експертні та інтелектуальні інформаційні системи
url	https://nasplib.isofts.kiev.ua/handle/123456789/86740
work_keys_str_mv	AT zubenkovv operacíinamodelʹkomuníkativnihínformacíinihsistem AT zubenkovv theoperatingmodelofcommunicativeinformationssystems

Операційна модель комунікативних інформаційних систем

Institution

Similar Items