Темпоральні процедури та алгоритми

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

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2006
Автор:	Зубенко, В.В.
Формат:	Стаття
Мова:	Ukrainian
Опубліковано:	Інститут програмних систем НАН України 2006
Теми:	Теоретичні та методологічні основи програмування
Онлайн доступ:	http://dspace.nbuv.gov.ua/handle/123456789/1636
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:	Темпоральні процедури та алгоритми / В.В. Зубенко // Проблеми програмування. — 2006. — N 2-3. — С. 53-59. — Бібліогр.: 4 назв. — укр.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-1636
record_format	dspace
spelling	irk-123456789-16362017-11-23T19:43:08Z Темпоральні процедури та алгоритми Зубенко, В.В. Теоретичні та методологічні основи програмування Уводиться поняття темпоральної процедури та алгоритму як засобів подання функціональних співвідношень в абстрактних динамічних системах. Розглядається проблема синтезу та аналізу таких процедур та алгоритмів. The notions of temporal procedure and algorithm are proposed and studied. The periodical temporal algorithms design and analyze are considered. 2006 Article Темпоральні процедури та алгоритми / В.В. Зубенко // Проблеми програмування. — 2006. — N 2-3. — С. 53-59. — Бібліогр.: 4 назв. — укр. 1727-4907 http://dspace.nbuv.gov.ua/handle/123456789/1636 510.6 uk Інститут програмних систем НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Ukrainian
topic	Теоретичні та методологічні основи програмування Теоретичні та методологічні основи програмування
spellingShingle	Теоретичні та методологічні основи програмування Теоретичні та методологічні основи програмування Зубенко, В.В. Темпоральні процедури та алгоритми
description	Уводиться поняття темпоральної процедури та алгоритму як засобів подання функціональних співвідношень в абстрактних динамічних системах. Розглядається проблема синтезу та аналізу таких процедур та алгоритмів.
format	Article
author	Зубенко, В.В.
author_facet	Зубенко, В.В.
author_sort	Зубенко, В.В.
title	Темпоральні процедури та алгоритми
title_short	Темпоральні процедури та алгоритми
title_full	Темпоральні процедури та алгоритми
title_fullStr	Темпоральні процедури та алгоритми
title_full_unstemmed	Темпоральні процедури та алгоритми
title_sort	темпоральні процедури та алгоритми
publisher	Інститут програмних систем НАН України
publishDate	2006
topic_facet	Теоретичні та методологічні основи програмування
url	http://dspace.nbuv.gov.ua/handle/123456789/1636
citation_txt	Темпоральні процедури та алгоритми / В.В. Зубенко // Проблеми програмування. — 2006. — N 2-3. — С. 53-59. — Бібліогр.: 4 назв. — укр.
work_keys_str_mv	AT zubenkovv temporalʹníproceduritaalgoritmi
first_indexed	2025-07-02T05:01:56Z
last_indexed	2025-07-02T05:01:56Z
_version_	1836510102263169024
fulltext	Теоретичні і методологічні основи програмування © И.В. Редько, 2006 ISSN 1727-4907. Проблеми програмування. 2006. № 2-3. Спеціальний випуск 53 УДК 510.6 ТЕМПОРАЛЬНІ ПРОЦЕДУРИ ТА АЛГОРИТМИ В. В.Зубенко Київський національний університет ім.Тараса Шевченка 01033, м.Київ, вул.Володимирська, 64 т/факс: (044) 259 0519, e-mail: vvz@unicyb.kiey.ua Уводиться поняття темпоральної процедури та алгоритму як засобів подання функціональних співвідношень в абстрактних динамічних системах. Розглядається проблема синтезу та аналізу таких процедур та алгоритмів. The notions of temporal procedure and algorithm are proposed and studied. The periodical temporal algorithms design and analyze are considered. Темпоральні процедури Темпоральні процедури та алгоритми, введені в [1], призначені для обчислення часових багатозначних функцій в абстрактних динамічних системах [2,3]. Класична теорія алгоритмів, теоретичне програмування з метою більшої прозорості та спрощення моделей, як правило, залишають поза увагою темпоральні елементи обчислень. Деяким виключенням є хіба що питання складності алгоритмів та програм. Але практика програму- вання, задачі інформаційного моделювання вимагають уточнення та вивчення саме не “оголених”, а реальних темпоральних моделей обчислень та обчислювальності. Особливістю підходу є те, що обчислення розгляда- ються не в просто часі, а в “подвійному” часовому просторі з урахуванням, так званих, локального і глобально- го часу. І цей простір не є “декоративним”, як наприклад в автоматних системах [3], а він може активно “впли- вати” на хід обчислень. Окрім цього обчислення локально можуть без обмежень повертатись “назад” або й про- сто “застигати” у просторі. Іншою особливістю є те, що темпоральні алгоритми вводяться не як традиційно пе- рвинне “наївне” поняття з певними “джентльменським” набором характеристичних ознак і властивостей, а як похідне від таких математичних понять, як множина, темпоральна процедура, конструктивний об’єкт. Наведемо основні поняття, пов’язані з темпоральними процедурами. Тлумачення деяких з них дещо від- різняється у порівнянні з [1]. Нехай −S довільна множина станів, >Γ< δ, – лінійно впорядкована сукупність, яку будемо трактувати як глобальний часовий простір, а T – локальний часовий простір. Він теж може бути лінійно впорядкованим, але це не є обов’язковою умовою. Позначимо ++t та t−− безпосередньо наступний та попередній моменти часу. Вважається, що в часових просторах немає найменшого та найбільшого елементів. На локальному часі T можуть бути визначені й інші структури. Наприклад, структура адитивної абелевої гру- пи або лінійного простору і т.п. Це дозволяє маніпулювати з часом і відстежувати локальну поведінку систем в тих чи інших часових розрізах. Як типові приклади локальних часових перетворень можна навести: облік сума- рного часу виконання всіх чи окремої групи операцій обчислення, часові зсуви “вперед” та “назад” 0tt ± (пе- реходи до іншого часового поясу), лінійні «стиснення» та «розширення» часу τk , обернення часу 1−τ , перехо- ди взагалі до іншого часового простору і т.д. Трійка =Π < ST ,,Γ > називається обчислювальним простором, елементи декартових добутків ST × та )( ST ××Γ –конфігураціями простору. Конфігурації STst ×∈),( та )()),(,( STst ××Γ∈τ будемо позначати відповідно t s та τ ts \| . Нехай Γ∈21,, τττ . Позначимо }\|{ ττττ ′≤Γ∈′=Γ , }{\ τττ Γ=Γ+ , ττ ΓΓ=Γ− \ , }:{],[ 2121 ττττττ ≤≤= . Аналогічні позначення будемо використовувати і для локального часового простору T . Процесами з початком в момент часу τ називаються відображення вигляду STa ×→Γτ: . Процесами на інтервалі ],[ 21 ττ називаються відображення вигляду STa ×→],[: 21 ττ . Багатозначні часткові функції надалі будемо називати співвідношеннями. Співвідношення вигляду STST ×××Γ a:δ називаються функціями переходу, а пари вигляду >Π=< δ,P – темпораль- ними процедурами над простором Π . У разі, коли обчислювальний простір Π зафіксовано, темпоральні про- цедури будемо ототожнювати з їх функціями переходу. Кожна процедура породжує певну сукупність процесів у глобальному часовому просторі, які називаються обчисленнями. А саме нехай Γ∈τ , Tt ∈ та Ss ∈ – дові- льні моменти локального часу та стан. Обчислення a за процедурою P з початком в момент τ та початковою Теоретичні і методологічні основи програмування 54 конфігурацією t s визначається рекурентно: =)(τa t s і ))(,()( ςςδς −−∈ aa для всіх +Γ∈ τς . Будемо го- ворити, що обчислення a в момент часу ς переходить від конфігурації )( ς−−a до конфігурації )(ςa і по- значати цей факт )()( ςς aa P→−− . Таких переходів в момент часу ς може бути кілька, оскільки функція переходу, взагалі кажучи, багатозначна. Обчислення a за процедурою P на інтервалі ],[ 21 ττ з початковою конфігурацією t s визначається як обмеженням відповідного обчислення a за процедурою P з початком в момент 1τ на інтервал ],[ 21 ττ . Будемо говорити, що обчислення a в цьому разі розпочинається конфігураці- єю )( 1τa і закінчується конфігурацією )( 2τa і позначати цей факт )()( 21 ττ aa P⇒ . Конфігурація )( 2τa на- зивається заключною, а її стан – результатом обчислення a на інтервалі ],[ 21 ττ . Якщо звернутись до загаль- них динамічних систем, то процедурні системи є різновидом 2-комнонентних неавтоматних динамічних систем [3], першій компоненті яких відведено спеціальну роль – локального часового простору. Нас цікавлять не стільки самі по собі процедури та обчислення, як засоби їх опису та конструювання, а також способи реалізації обчислень. У зв’язку з цим зауважимо, що з функцією переходу пов’язані дві сукупно- сті перетворень – локального часового простору та множини станів. А саме, якщо зафіксувати певний cтан Ss ∈0 та моменти часу Γ∈0τ , Tt ∈0 , то їм відповідають співвідношення TTp s a: 00 ,τ та SSf t a: 00 ,τ такі що, для довільних Tht ∈, , Sus ∈, : htp s =)( 00 ,τ , usf t =)( 00 ,τ , якщо існують такі Th ∈1 , Su ∈1 , що ),,(\| 001 stu h τδ∈ та ),,(\| 001 stu h τδ∈ . Вірно і обернене. Якщо кожній трійці ( st,,τ ) поставити у відповідність одну або кілька пар відображень ( TTp s →:,τ , SSf t →:,τ ), то цим самим буде визначена певна функція переходу, а саме така, що ),,())(),(( ,, stsftp ts τδττ ∈ . Щоб спростити опис функції переходу та наблизитись до засобів реалізації реальних обчислювальних процесів, здійснемо певну інтенсіона- лізацію підходу. А саме розділимо процес переходу від однієї конфігурації обчислення до наступної на дві окремі фази: з’ясування, яка саме дія має відбутися над конфігурацією, та саму дію. Для цього зафіксуємо }\|:{ Α∈→=Θ αα TTp та }\|:{ Β∈→=∆ ββ SSf - певні сукупності ста- ндартних (елементарних) перетворень моментів часу та станів. Будемо їх вважати однозначними і долучимо до обчислювального простору =Π >∆ΘΓ< ,,,, ST . Нову функцію переходу над простором Π визначимо у вигляді ∆×Θ→××Γ 2: STδ . Її дія тепер обмежується тільки першою фазою переходів конфігурацій. Друга ж фаза “відірвана” від першої і може подаватись та реалізовуватись незалежно від неї, у тому числі операційно, наприклад, у вигляді викликів відповідних алгоритмів, підпрограм і т.п. Обчислення a за процедурою P з початком в момент часу τ та початковою конфігурацією ),( 00 ts визначається рекурентно: =)(τa ),( 00 ts і для всіх τς > ))(),(()( sftpa ςςς = , де ))(,(),( ςςδςς −−∈ afp , а t та s – компоненти конфігурації на попередньому кроці, тобто tsa \|)( =−− ς . Обчислення a за процедурою P на інтервалі ],[ 21 ττ визначаєть- ся як обмеження відповідного обчислення a на інтервал ],[ 21 ττ . Зазначимо, варіантів пар ),( ςς fp на даному кроці обчислення може бути: а) кілька (у випадку недетермінованих процедур), б) рівно одна (у випадку детер- мінованих процедур) і в) жодної (обчислення зупиняється). Як правило, нас будуть цікавити не всі можливі обчислення в процедурі, а насамперед ті, що розпочинаються з певних виділених вхідних локальних конфігура- цій і закінчуються певними виділеними вихідними локальними конфігураціями. Тому введемо поняття ініціаль- ної процедури ),( 0 finCCP над простором Π як трійки >< finCCP ,, 0 , де −P певна процедура над просто- ром Π , STC ×⊆0 та STC fin ×⊆ – виділені підмножини відповідно вхідних та вихідних конфігурацій або як четвірки >Π=< δ,,, 0 finCCP . Обчислення, що розпочинається з певної початкової конфігурації )( 0τa = 0Cs t ∈ і закінчується певною вихідною конфігурацією )(τa = finr Cu ∈ і при цьому всі проміжні конфігурації якого не є вихідними, назвемо результативним. Конфігурація )(τa називається заключною, а її стан u – результатом обчислення на )( 0τa . Заключну конфігурацію позначатимо ( )0 * (τaP , а результат обчи- слення – ( ))( 0τaP . Про обчислення )()( 0 ττ aa P⇒ таке, що 00)( Ca ∈τ , finCa ∈)(τ , будемо говорити як про гіперрезультативне. В такому обчисленні вихідні конфігурації можуть зустрічатися і серед проміжних. За- ключна його конфігурація позначається ( ))( 0 ** τaP . Нескінченні обчислення називаються, як правило, безре- зультатними. Безрезультатними називатимемо і ті скінченні обчислення, які не мають жодного результативного продовження. В деяких випадках доречно вважати результативними і ті скінченні обчислення, на заключних Теоретичні і методологічні основи програмування 55 конфігураціях яких не визначена функція керування. Нехай 0S та finS – сукупності всіх станів, що належать відповідно вхідним та заключним конфігураціям процедури. Кожна ініціальна процедура ),( 0 finCCP визна- чає певні багатозначні часові оператори на вхідних конфігураціях finCCP a0 * : ×Γ , finCCP a0 ** : ×Γ , а саме такі, що їх значення в момент Γ∈0τ на аргументі ї 0Cs t ∈ складають заключні конфігурації всіх ре- зультативних та гіперрезультативних обчислень з початком в момент 0τ на 0Cs t ∈ . Позначимо finCCP →0 * :τ та finCCP →0 ** :τ результат підстановки в оператори P та P часової константи Γ∈τ замість першої компоненти і fint SSP →0, :τ – проекцію по другій компоненті результату підстановки в опера- тор τP константи Tt ∈ замість першої компоненти. Значеннями оператора tP ,τ на початковому стані s є стани заключних конфігурацій відповідних результативних обчислень за процедурою P , що розпочинаються в фіксований момент глобального (τ ) та локального ( t ) часу. Про оператори P , P , τP , ** τP та tP ,τ будемо говорити як про такі, що їх обчислює процедура P . Перші чотири з них є темпоральними, а останні – перетво- реннями множини станів. Окремо виділимо ініціальні процедури, що закінчують обчислення виключно за часо- вими (глобальними чи локальними) критеріями. У першому випадку можуть навіть не фіксуватись заключні конфігурації процедури, а замість них може вводитись, наприклад, певна топологія на сукупності всіх локаль- них конфігурацій і поняття границі процесу як результату обчислення. У другому випадку сукупність заключ- них конфігурацій має вигляд STC fin ×′= для деякого TT ⊆′ . Наприклад, процедури що закінчують роботу в певний момент часу h ( ShC fin ×= }{ ) або після деякого моменту часу h ( STC hfin ×= + ) і т.д. Процедури з однозначними функціями керування будемо називати детермінованими. Для таких процедур оператор P є також однозначним. Процедури P та Q називаються еквівалентними ( QP ≡ ), якщо оператори, які вони об- числюють, співпадають як функціональні відношення. Процедури P та Q називаються τ -еквівалентними ( QP τ ≅ ), якщо τP = * τQ . Процедури P та Q називаються ),( tτ -еквівалентними ( QP t,τ ≅ ), якщо tP ,τ = tQ ,τ . Процедури P та Q називаються −2 еквівалентними відносно моменту часу τ ( QP 2 ≅ ), якщо tP ,τ = tQ ,τ для всіх Tt ∈ . Стан ініціальної процедури ),( 0 finCCP назвемо допустимим, якщо він входить до конфігурації деякого результативного її обчислення. Позначимо SSacc ⊆ підмножину всіх допустимих станів процедури ),( 0 finCCP . Очевидно, з точку зору операторів, що обчислює ініціальна процедура, стани за межами підмно- жини accS є “зайвими”. Нехай ),( 0 finCCP ′′′ – ініціальна процедура над простором Π′ з множиною станів accS та з обмеженими на нього: елементарними операторами, функцією переходу та вхідними і вихідними конфігураціями процедури Ρ . Очевидно, процедури Ρ та Ρ′ еквівалентні. Процедура, всі стани якої допус- тимі, називається приведеною. Процедуру назвемо монотонно зростаючою (спадаючою), якщо всі стандартні часові перетворення є монотонно зростаючими (спадаючими) і монотонно не спадаючою (не зростаючою), якщо всі стандартні часові перетворення є монотонно не спадаючими (не зростаючими). Монотонно зростаючі (спадаючі) процедури будемо називати просто монотонними, а монотонно не спадаючі (не зростаючі) – слабко монотонними. Темпоральні алгоритми Як уже зазначалось, процедури цікавлять нас не самі по собі, а насамперед в контексті їх побудови (програмування) з метою реалізації або моделювання. Коли говориться про реалізацію процедур чи окремої процедури, то мають на увазі існування певного Виконавця обчислень, реального фізичного чи гіпотетичного, здатного фіксувати окремі конфігурації обчислення, знаходити значення функції переходу на кожній з конфігу- рацій та здійснювати відповідні елементарні перетворення компонентів. Вважається, що Виконавець володіє певною системою для подання (побудови) конфігурацій та правил для проведення елементарних перетворень і обчислення значень функції переходу. Існування та використання подібних правил є принциповим моментом, оскільки елементарні перетворення та функція переходу в більшості своїй є нескінченними, а от правила їх об- числення можуть бути подані в підходящій системі фінітно у вигляді спеціальних об’єктів, наприклад алгорит- мів чи програм і т.д. Дана обставина є принциповою з точки зору фізичної реалізації (моделювання) обчислень. Якщо всі об’єкти системи подання є скінченними, то про таку систему будемо говорити як про конструктивну, а її об’єкти називати конструктивними. Про конструктивність об’єктів (функцій, конфігурацій) можна говори- Теоретичні і методологічні основи програмування 56 ти, наприклад, у випадку алгебричних об’єктів. Для функцій це означає, що вони побудовані з певних базових функцій за допомогою конструкторів-композицій і відомі правила обчислень для найпростіших складових фун- кцій та результатів композицій. Наприклад, як це має місце у випадку арифметичних виразів. Алгебричні об’єкти мають і іншу важливу властивість – їх можна будувати (конструювати, програмувати) зокрема у вигля- ді слів-термів з базових сигнатурних елементів. Зазначимо, що наше тлумачення системи подання та конструк- тивності до певної міри інтуїтивне і ми свідомо на даному рівні уникаємо розгляду інших, не алгебричних (в тому числі і генетично обумовлених [4]) структур, пов’язаних з конструктивністю. Говорять, що ініціальна процедура A є конструктивною щодо певної системи подання, якщо її конфігурації та функція керування є конструктивними в цій системі. Конструктивні процедури будемо називати темпоральними алгоритмами (T - алгоритмами). Оператори A , A , τA , ** τA , tA ,τ , Γ∈τ , Tt ∈ , що обчислюються темпоральним алгорит- мом A , називаються алгоритмічно обчислювальними. Як і процедури, темпоральні алгоритми можуть бути детермінованими і недетермінованими. Наведемо основні властивості темпоральних алгоритмів, що безпосере- дньо випливають з їх означення. Масовість. T -алгоритм може бути застосовано до будь-якої вхідної конфігурації з певної їх сукупності. Темпоральність. Обчислення T -алгоритму відбуваються у глобальному та локальному часових просто- рах. Елементарність. На кожному кроці обчислень виконуються певні елементарні оператори з фіксованих сукупностей таких операторів ( Θ та ∆ ). Визначенність. Порядок застосування елементарних операторів в обчисленні не є довільним, а визнача- ється функцією переходу за поточними моментом часу та конфігурацією обчислення. Результативність. Є механізм завершення обчислень. Фінітність. Скінченність подання конфігурацій та функції переходу як конструктивних об’єктів. Релятивність. Відносність поняття T -алгоритму. Конструктивність процедури тісно пов’язана з систе- мою подання, і процедура, будучи T -алгоритмом відносно даної системи подання, не обов’язково буде T - алгоритмом відносно якоїсь іншої системи. Іншим аспектом релятивності алгоритмів є взаємовідносини елеме- нтарних операторів та системи подання. В деяких випадках елементарні оператори (всі чи їх частина) можуть бути неконструктивними відносно системи подання. Про такі оператори говорять як про оракули, що знахо- дяться за межами системи подання, а про самі алгоритми – як про алгоритми з оракулами. Як бачимо, основні властивості класичних числових та словарних алгоритмів притаманні й темпораль- ним алгоритмам. Але в останніх з’явились і нові специфічні риси – темпоральність та релятивність. Перша уза- гальнює дискретність класичних алгоритмів та “прив’язує” їх обчислення до локального часового простору, друга акцентує увагу на відносному характері поняття алгоритму, на його до певної міри «несамостійності» й залежності від тієї чи іншої системи подання. Оскільки темпоральні алгоритми обчислюють і позачасові опера- тори, то вони можуть слугувати платформою для уточнення і загального поняття обчислювального оператора в довільній області. Важливо, що цей шлях є прямим і не спирається на ті чи інші універсальні числові чи слова- рні моделі таких алгоритмів. Фіксуючи конкретні обчислювальні простори та вибираючи конкретні системи подання, можна отримати весь спектр класичних алгоритмічних систем ( машини Тьюрінга, алгорифми Марко- ва, алгоритми Колгоморова-Успенського, дискретні перетворювачі, різні класи схем програм, формальні грама- тики та числення і інші). Так, у випадку машин Тьюрінга станами їх процедурних еквівалентів виступають ста- ни робочої стрічки машини (=слова в робочому алфавіті з відміченою позицією робочої комірки), локальний часовий простір T – скінчений і його складають внутрішні стани машини, N=Γ , значення функції переходу на конфігурації визначається локальним часом та станом поточної комірки на стрічці. При цьому це значення ніяким чином не залежить від номера кроку (глобальної часової компоненти!) обчислення. Загальний варіант темпоральної машини Тюрінга можна отримати на основі 2-стрічкової її моделі, якщо одну зі стрічок викорис- товувати як звичайну робочу, а іншу – як лічильник натуральних чисел у якості локальної часової компоненти. Команди такої темпоральної квазімашини Тьюрінга враховують (та змінюють) стани поточної комірки, робочої голівки та лічильника. З відомих алгоритмічних систем найбільш природну процедурну інтерпретацію мають дискретні перетворювачі В.М.Глушкова. Як відомо, дискретний перетворювач є системою двох з’єднаних між собою автоматів: керуючого YX − -автомата Мілі та операційного XY − -автомата Мура. Операційний авто- мат здійснює перетворення своїх поточних станів (станів інформаційного середовища перетворювача) та поси- лає вхідні сигнали керуючому автомату про стан інформаційного середовища. Останній, виходячи з цієї інфор- мації та зі свого поточного стану, вибирає наступне елементарне перетворення для операційного автомата. Процедурний еквівалент дискретного перетворювача вхідні сигнали керуючого автомата інтерпретує як лока- льні часові константи ( тобто TX = ), глобальний часовий простір Γ є таким, як і у випадку машин Тюрінга, – N . Стани процедури – 2-компонентні і складаються зі станів керуючого та операційного автоматів. Функція переходу реалізує функцію керуючого автомата, за виключенням безпосереднього перетворення його внутріш- нього стану. Вона тільки передає інформацію про таке перетворення та про відповідні перетворення операцій- ного середовища та локального часу. Зазначимо, що функції переходу машини Тьюрінга чи дискретного пере- творювача є автоматними, тобто наступні їх дії не залежать від моменту часу (глобального) та попередньої іс- торії обчислення. Якщо звернутись до таких систем як, наприклад, ігрові числення, то в їх правилах та стратегі- Теоретичні і методологічні основи програмування 57 ях часові фактори відіграють дуже важливу роль. Це означає, що вони як динамічні системи є темпоральними. В багатьох іграх важливим локальним фактором є черговість ходу. Але є й інші принципові обставини, пов’язані з темпоральністю. Наприклад, в шахах рокіровка короля залежить від того, чи рухався він до цього. На стратегію вибору чергового ходу може впливати обмеженість часу, відведеного на шахову партію (гра в цейтноті), і т.д. Періодичні алгоритми Одним із шляхів до спеціалізації та вивчення тих чи інших підкласів темпоральних процедур та алгори- тмів є факторизація областей визначення функцій переходу. Розглянемо як приклад, так звані, періодичні алго- ритми. Нехай далі локальний часовий простір є ізоморфним адитивній групі Z цілих чисел і нехай P – довільна процедура над простором =Π < Θ∆Γ ,,,, SZ >, π – певне відношення еквівалентності на станах з S . Факто- ризуємо функцію переходу за часовими аргументами та станами. Зафіксуємо деяку локальну часову константу k . Будемо говорити, що функція переходу δ є періодичною по модулю π з періодом k ( або просто k - періодичною по модулю π ), якщо для будь-яких еквівалентних станів p та s та довільних моментів часу Γ∈′ττ , , Zt ∈ виконується ),,(),,( sktpt +′= τδτδ . З періодичності функції δ випливає, що вона факти- чно не залежить від глобального часу, тобто в будь-який момент часу вибір чергових перетворень визначається виключно поточною конфігурацією. З 1-періодичності δ випливає незалежність такого вибору і від локального часу. Темпоральні процедури та алгоритми з k -періодичними по модулю π функціями переходу називаються періодичними. Еквівалентність π назвемо розв’язною, якщо кожен з її класів еквівалентності є розв’язним. Ін- дексом багатозначної функції назвемо максимальну потужність сукупностей значень функції на окремих аргу- ментах. У разі, коли функція переходу періодичного алгоритму та еквівалентність π мають скінчений індекс і еквівалентність є розв’язною, алгоритм називається табличним . Табличні алгоритми задаються скінченими таблицями, стовпчики яких пронумеровані числами від 0 до 1−k , рядки відповідають класам еквівалентності π , а в клітинах таблиці розміщуються значення функції переходу. Традиційні алгоритмічні системи, як прави- ло, є табличним як темпоральні алгоритми. У випадку машин Тюрінга дві конфігурації є еквівалентними, якщо стани їх робочих головок та комірок співпадають. Ці два елементи повністю визначають чергове перетворення конфігурації машини. Нехай Π = >∆ΘΓ< ,,,, ST та Π′ >∆′Θ′′′Γ=< ,,,, ST - обчислювальні простори, такі, що, SSTT ′⊆′⊆ , , ),( 0 finCCA та ),( 0 finCCB - алгоритми відповідно над просторами Π та Π′ і нехай ці ал- горитми є еквівалентними. Тоді алгоритм ),( 0 finCCB називається розширенням алгоритму ),( 0 finCCA . Нехай ),( ATM сукупність всіх часткових багатозначних темпоральних операторів ( −T операторів) вигляду ATATf ×→×: . Для того чи іншого підкласу операторів ),( ATMM ⊆′ проблема його проце- дуризації (синтезу) полягає в побудові того чи іншого класу ініціальних темпоральних процедур, що обчислю- ють (моделюють) всі його функції. В [ ]1 показано, якщо дозволити процедурам переходити в процесі об- числень в додаткові ізоморфні простори, то сукупність операторів, які обчислюються такими розширеними −T процедурами, замкнена відносно композицій-зсувів (часових), дзеркального відображення, множення, прямого множення, об’єднання, прямої суми, розгалуження, вибору, −α ітерації, булевих композицій. Анало- гічний результат має місце і для періодичних та табличних алгоритмів. Але при умові, якщо у базовому обчис- лювальному просторі є тотожні елементарні оператори SSf →:0 , ZZp →:0 : ssf =)(0 , ttp =)(0 для будь-яких Ss ∈ , Zt ∈ . Такі обчислювальні простори назвемо невиродженими. Покладемо 0Ξ - сукупність наведених вище композицій. Позначимо ),( ~ AZM сукупність темпоральних операторів над AZ × та їх пря- мих добутків. Функціональну алгебру R = 0),,( ~ ΞAZM будемо називати регулярною алгеброю −T опера- торів. Елементи підалгебри )(FR алгебри R з множиною твірних F , де { },......,1 nffF = довільна сукуп- ність −T операторів та предикатів над AZ × , будемо називати регулярними −T операторами над базисом F . Теорема 1. Підклас темпоральних операторів, що обчислюються розширеними періодичними процеду- рами над невиродженим простором Π = >∆ΘΓ< ,,,, SZ , утворює підалгебру регулярної алгебри R = 0),,( ~ ΞSZM . Доведення. Проводиться аналогічно, як і у випадку загальних темпоральних алгоритмів [1]. € Теоретичні і методологічні основи програмування 58 Відзначимо також композицію збільшення періоду, яка, не змінюючи позачасові оператори обчислюва- ні −k періодичним алгоритмом A = >Π< δ,,, 0 finCC , збільшує його період на 1. Новий алгоритм познача- тимемо 1+A . Визначимо функцію переходу δ ′ на збільшеному основному періоді Sk ×],0[ наступним чином : ( ) =+′ sr ,1δ },0),,(),(:),1{ Sskrsrfpfp ∈<≤∈+ δ , ( ) ),(,0 00 fps =′δ для всіх Ss ∈ . За межами основного періоду функція переходу δ ′ продовжується як −+ )1(k періодична. Покладемо 1+A = >′′′Π< δ,,, 0 finCC , де початкові та заключні конфігурації алгоритму A зсунуті в часі вперед на 1. За побудо- вою, алгоритми A і 1+A обчислюють однакові позачасові оператори на станах. Композиція збільшення пері- оду дозволяє у разі необхідності вирівнювати періоди двох або більше алгоритмів. Проблема аналізу процедур, що належать певному класу K , полягає у пошуку тих чи інших алгебри- чних форм подання операторів, обчислювальних процедурами з K . При цьому таких форм, що існують для кожної процедури. Дану проблему можна також сформулювати як проблему конструктивізації операторів, об- числюваних процедурами класу K . Теорема 2 розв’язує проблему аналізу для монотонних табличних алгорит- мів. Конфігурації називаються сусідніми, якщо вони належать до одного часового періоду. Це означає, що їх часові компоненти 1t та 2t задовольнять умові: ktkt ÷=÷ 21 , де ÷ - операція цілочислового ділення. Нехай ∆×Θ∈),( fp - довільна пара елементарних перетворень. Позначимо fp ⊗ - темпоральний оператор, що здійснює покомпонентне перетворення конфігурацій: ))(),((),( sftpstfp =⊗ . Будемо називати його також елементарним. Покладемо }),(\|{ ∆×Θ∈⊗=Θ⊗∆ fpfp . Теорема 2 (про регуляризацію монотонних табличних алгоритмів). Нехай ),( 0 finCCA - k - періодичний по модулю π монотонний табличний алгоритм над певним обчислювальним простором =Π >∆ΘΓ< ,,,, SZ і Γ∈τ . Тоді оператор * τA є регулярним відносно базису, який складають елементарні оператори Θ⊗∆ , характеристичні предикати класів розбиття π , сукупностей початкових і заключних конфі- гурацій, а також предикат сусідства конфігурацій. Доведення. Нехай },...,,{][ 21 nRRRS =π - розбиття станів за еквівалентністю π , },...,{][ 1 nRZRZSZ ××=× π - розбиття конфігурацій за еквівалентністю π , { }∝=Ρ ,,..., ,01 finn pppp - сукупність характеристичних предикатів класів iRZ × , множин 0C та finC та відношення сусідства. Нехай ( )Ρ∪Θ∪∆,ZR - підалгебра регулярною алгебри R з множиною твірних Ρ∪Θ⊗∆ . Враховуючи наяв- ність композиції обходу в алгебрі R , для доведення теореми достатньо розглянути випадок, коли STC ×=0 і показати, що функція * τA належить підалгебрі ( )Ρ∪Θ∪∆,ZR . Виберемо nn RsRs ∈∈ ,...,11 - певну су- купність канонічних представників класів еквівалентності. Позначимо iB - обмеження функції * τA на клас еквівалентності iRZ × . Покажемо, що функції iB ___ ,1, ni = , задовольняють певній системі праволінійних рів- нянь в алгебрі ( )Ρ∪Θ∪∆,ZR . Покладемо TD оператор, що обчислює алгоритм A на кожному з періодів, не попадаючи в вихідний стан, тобто коли заключними оголошено конфігурації множини finCSZC \×= . Нехай ___ ,1, niQi = , - оператор, що обчислює алгоритм A на кожному з періодів своєї області визначення з початковими конфігураціями, що належать класу розбиття iRZ × . Враховуючи монотонність та “табличність” алгоритму A , можна перевірити, що всі оператори TD , ___ ,1, niQi = , є певними суперпозиціями обмежень відповідних елементарних операторів на області, що задаються тими чи іншими комбінаціями базових характе- ристичних предикатів підалгебри ( )Ρ∪Θ∪∆,ZR . А це означає, що вони належать підалгебрі ( )Ρ∪Θ∪∆,ZR . Покажемо, що функції iB ___ ,1, ni = , задовольняють наступній системі праволінійних рів- нянь: () in sjfp TC k j i QXXXDfpX i ∪∪∪∪⊗= ∈ − = )...(\|{ 2 ]),[,(),( 1 1 0 UU oo δ , ___ ,1 ni = , Теоретичні і методологічні основи програмування 59 Нехай ),(),( ststBi ′′= для деяких SZstst ×∈′′ ),(),,( , ni ≤≤1 . Тобто пара )\|,\|( tt ss ′′ належить лівій частині −i ї рівності () при підстановці функції iB замість змінної iX в () . Це означає, що існує таке обчислення λτ tP ss t ′′⇒ \|\| , що iRs ∈ і fint Cs ∈′ ′\| для деякого Γ∈λ . Покажемо, що дана пара належить і пра- вій частині рівняння. Зазначимо, що ___ ,1, niBQ ii =⊆ . Тому розглянемо тільки випадок, коли )(\| it QDoms ∉ . Враховуючи монотонність алгоритму A , це означає, що обчислення λτ tP ss t ′′⇒ \|\| виходить за межі одного періоду. Розглянемо його префікс ςτ lt tlP ss \|\| ⇒ , ltk ≤ , що закінчується “стрибком” за межі першого періоду та його хвіст ς ltls \| λ tP s ′′⇒ \| . За побудовою, ),(\| stfDs Ttl l = , =′ ts \| ),( llm stB для деяко- го nm ≤≤1 . Значить пара )\|,\|( tt ss ′′ належить правій частині −i ї рівності (). Вірно і обернене твердження, якщо пара )\|,\|( tt ss ′′ належить правій частині −i ї рівності при ii BX = , ___ ,1 ni = , то вона належить і її лівій частині. Доведення те саме, тільки проводиться у зворотному порядку. Таким чином, система функцій iB , ___ ,1 ni = , є розв’язком системи (). Більше того, вона є її найменшим розв’язком. Дійсно, розглянемо довільний розв’язок системи () iE ___ ,1, ni = . Ясно, ____ ,1, niEQ ii =⊆ . Визначимо сукупності станів 0,,1, ____ ≥= mniQm i , поклавши ii QQ =0 , )...(\| 1 ])[,(),( 1 0 1 m n m sjfp TC k j m i QQDfpQ i ∪∪⊗= ∈ − = + UU δ . За побудовою, i m i EQ ⊆ . Тоді i m i m i EQQ ⊆= ∞ = ∞ U 0 , ,,1 ____ ni = є розв’язком системи (), а значить, і найменшим її розв’язком. Але за побудо- вою, сукупності ∞ iQ співпадають з iB . Для закінчення доведення теореми 1 залишилось, зазначити, що: 1) найменший роз’язком праволінійної системи функціональних рівнянь вигляду () є кортеж регулярних функцій над базисом, що складається з її коефіцієнтів та вільних членів, та 2) U n i ii BpA 1 * )( = →=τ . Отже, функція * τA належить алгебрі ( )Ρ∪Θ∪∆,ZR . 1. Зубенко В.В. Про темпоральні процедури та алгоритми // Вісн. КНУ ім. Тараса Шевченка. Серія: Кібернетика. – 2005. –№6. – С. 20-26. 2. Месарович М., Такахара Я. Общая теория систем: математические основы // М.: Мир. –1978. – 308 с. 3. Капитонова Ю.В., Летичевский А.А. Математическая теория проектирования вычислительных систем // М.: Наука. –1988. – 295 с. 4. Редько В.Н. Экспликативное программирование: ретроспективы и перспективы // Тр. 1-й Межд. науч.-практ. конф. по программирова- нию УкрПРОГ”98. – Киев: Ин-т проблем программирования НАНУ, 1998 . – С. 3-24.

Темпоральні процедури та алгоритми

Репозитарії

Схожі ресурси