Buchumschlag

Концепція діалогових обчислень та деякі проблеми автоматизації програмування

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

Ausführliche Beschreibung

Gespeichert in:
Bibliographische Detailangaben
Datum:2004
Hauptverfasser: Петрушенко, А.М., Хохлов, В.А.
Format: Artikel
Sprache:Ukrainisch
Veröffentlicht: Інститут програмних систем НАН України 2004
Schlagworte:
Теоретические и методологические основы программирования
Online Zugang:https://nasplib.isofts.kiev.ua/handle/123456789/2280
Tags: Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:Концепція діалогових обчислень та деякі проблеми автоматизації програмування/А.М. Петрушенко, В.А. Хохлов // Проблеми програмування. — 2004. — N 2,3. — С. 37-46. бiблiогр.: 26 назв. - укр.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine
_version_ 1859618546997264384
author Петрушенко, А.М.
Хохлов, В.А.
author_facet Петрушенко, А.М.
Хохлов, В.А.
citation_txt Концепція діалогових обчислень та деякі проблеми автоматизації програмування/А.М. Петрушенко, В.А. Хохлов // Проблеми програмування. — 2004. — N 2,3. — С. 37-46. бiблiогр.: 26 назв. - укр.
collection DSpace DC
description Розглядається концепція діалогових обчислень та наводяться деякі її раелізації в термінах алгебри алгоритміки, насамперед, уточнення основної задачі програмування. В термінах спеціального класу алгоритмів – діалогових адресних програм – дається уточнення поняття “методу програмування” та показується його зв’язок з концепцією змішаних обчислень і проблемою оптимізації програм. Пропонується одне із можливих визначень поняття “діалоговий процес”. Введені поняття демонструються на прикладах. Отримані в роботі результати знаходять реалізацію в діалоговій трансформаційній машині – інструментарії діалогових алгебро- граматичних методів представлення знань.
first_indexed 2025-11-28T22:40:11Z
format Article
fulltext КОНЦЕПЦІЯ ДІАЛОГОВИХ ОБЧИСЛЕНЬ ТА ДЕЯКІ ПРОБЛЕМИ АВТОМАТИЗАЦІЇ ПРОГРАМУВАННЯ Петрушенко А.М., Хохлов В.А. Херсонський державний технічний університет, Україна, 73008, м. Херсон, Бериславське шосе, 24, тел. 51-57-31, 55-17-31, E–mail: xvadim@newmail.ru Розглядається концепція діалогових обчислень та наводяться деякі її раелізації в термінах алгебри алгоритміки, насамперед, уточнення основної задачі програмування. В термінах спеціального класу алгоритмів – діалогових адресних програм – дається уточнення поняття “методу програмування” та показується його зв’язок з концепцією змішаних обчислень і проблемою оптимізації програм. Пропонується одне із можливих визначень поняття “діалоговий процес”. Введені поняття демонструються на прикладах. Отримані в роботі результати знаходять реалізацію в діалоговій трансформаційній машині – інструментарії діалогових алгебро- граматичних методів представлення знань. The conception of dialogue calculation is shown. The specification of idea “method of programming” is given. The definition of concept “dialogue process” is proposed. An introduced concepts are demonstreted by examples. Концепція діалогових обчислень та основна задача програмування Продемонструємо суть концепції діалогових обчислень наступним чином [1]. Нехай ми маємо деякий набір інструкцій Н, єдине правило виводу – підстановку, запис F „умов” задачі; необхідно з запису F вивести запис G „рішення” задачі. Процедура виводу розпадається на окремі кроки. На кожному кроці застосовується інструкція – правило виводу, що складається, як видно, з двох частин – правила, що задає властивості і правила безпосередньої переробки. З кожною властивістю ототожнюється, взагалі говорячи, декілька ділянок конструктивного об’єкту. Ділянка, що розглядається в даний момент, називається активною частиною цього перетворюваного об’єкту. Використовуючи правило безпосередньої переробки, що точно встановлює, як перетворювати (розчленовувати) активну частину, можливо, видаляючи при цьому деякі частини конструктивного об’єкту і вставляючи інші, необхідно отримати (вибираючи лише „головний” шлях і ігноруючи шляхи, що приводять до безперспективних слів) відповідні наслідки. Введемо важливе поняття концепції, що пропонується, – протоколу породження діалогових обчислень. У цьому протоколі фіксується інформація, необхідна для однозначного відтворення процесу рішення задачі. Зрозуміло, маючи протокол породження, можна повертатися на раніше пройдені етапи процесу пошуку рішення з метою корекції цього процесу. Процес пошуку рішення продовжується ітеративно доти, поки не буде досягнутий один із заключних станів – рішення (тобто ціль, у даному випадку G, досягнута) або неуспішне завершення (ціль не досягнута). Тут доречно нагадати, що поняття алгоритму Колмогорова [2] містить в собі фундаментальну ідею ітеративності алгоритмічного процесу, відповідно до якої всяке детерміноване перетворення одних об’єктів в інші представляє собою результат багаторазового застосування однієї і тієї ж, фіксованої для даного перетворення, операції – оператора безпосередньої переробки. Слід відзначити, що концепція дозволяє розглядати як детерміновані, так і недетерміновані моделі обчислень з пам’яттю. За рахунок умовного поділу інструкцій на дві частини: властивості задаються в метамові, а правила безпосередньої переробки – в предметній, концепція допускає явне керування перетвореннями, зокрема, дозволяє вибрати місце і послідовність інструкцій, що застосовуються. З цією взаємодією пов’язане уточнення такого фундаментального поняття комп’ютерної науки, яким є поняття алгоритму [21,26]. Твердження 1. Запропонована концепція діалогових обчислень завдяки поняттю протоколу не тільки реалізує фундаментальну ідею ітеративності алгоритмічного процесу, але, до того ж, фіксує всі проміжні стани обчислень і дозволяє у діалоговому режимі здійснити перехід до наступного стану в процесі пошуку рішення даної задачі. Зауважимо, при відповідній інтерпретації понять, що входять в концепцію, яка пропонується, – конструктивний об’єкт, правило безпосередньої переробки, активна зона, F, G, H та інших, можна отримати постановки та вирішення відомих програмістських задач (перетворення формул, проектування програм, мовне процесування та інших). В залежності від класу задач, що розв’язуються, виникають відповідні протоколи діалогових обчислень. В якості приклада розглянемо спочатку уточнення так званої основної задачі програмування [3-9]. У найбільш загальному вигляді основна задача програмування може бути сформульована в такий спосіб: по вхідній постановці задачі потрібно одержати програму в цільовій МП, що вирішує дану задачу. Приведене формулювання потребує уточнення, оскільки майже кожне слово в ньому не є точним математичним поняттям. До того ж у цьому формулюванні нічого не говориться про сам процес рішення задачі. Необхідне уточнення можна отримати в такий спосіб. Взагалі говорячи, вхідна постановка задачі формулюється в термінах предметної області (ПрО) цієї задачі. Вхідна постановка задачі повинна задаватися, як правило, у вигляді дано-отримати, а програма повинна обчислювати, обумовлену цими дано-отримати, деяку функцію f. Опис цієї функції в термінах математичної моделі актуальної ПрО називають головною функціональною моделлю програми (ГФМП). ГФМП дає опис зовнішніх властивостей програми – які в неї існують розпорядження, що вийде в результаті їхнього виконання і так далі. Як правило, розпорядження виконує деяку дію над об’єктом і полягає в зміні стану (чи значення) цього об’єкта. Під об’єктом при цьому розуміється деяка ділянка пам’яті комп’ютера, а під його станом – інформація, що у даний момент часу в цій ділянці зберігається. Зовнішній опис досить зручний для використання (поняття ГФМП близьке за змістом поняттю специфікації, але не тотожно йому), але в ньому нічого не говориться про його внутрішній устрій, оскільки остаточний результат проектування (текст програми) повинен бути виражений у термінах ПрО обчислювальної системи, за допомогою якої повинна виконуватися програма. У цілому процес переходу від вхідної постановки задачі до ГФМП не формалізований і істотно залежить від ПрО. Основою для побудови моделі ПрО є базова алгебра даних, компонентами якої є абстрактні типи даних (різні алгебри такого типу можна отримати в результаті використання стандартних теоретико-множинних конструкцій, деякі з яких будуть розглянуті нижче). В алгебраїчних термінах основну задачу програмування можна переформулювати в такий спосіб: по зовнішньому опису F програми G, яку треба створити, і зовнішньому опису базової алгебри A, що вважається існуючою, необхідно знайти реалізацію R(F,A)=G – текст на МП, що описує функціонування F у термінах A і що дозволяє синтезувати F при наявності A. При цьому програма G=R(F,A), як мінімум, повинна бути правильною, зрозумілою і легко виправною. Створення такого тексту являє собою важку задачу, для рішення якої в даний час розроблено декілька підходів [3-9]. Як правило, всі вони зводять процес проектування до послідовності етапів, що підтримують основний метод подолання складності при проектуванні великих систем – метод зведення вхідної задачі до більш простих підзадач (аналітичний метод). Процес зведення базується на операції “крок декомпозиції” Х⇒Y&R(X,Y), що дозволяє по зовнішньому опису Х знайти реалізацію Х на базі придуманого нами проміжного оператора Y і одночасно зовнішній опис цього Y. Технологічний ланцюжок програмування виглядає в цьому випадку наступним чином: F⇒B&R(F,B) → B⇒C&R(B,C) → ... → Z⇒A&R(Z,A), тобто складається в послідовному застосуванні кроку декомпозиції, починаючи з зовнішнього опису F шуканої програми G доти, поки не дійдемо до існуючої базової алгебри А. При цьому рішення основної задачі програмування – текст R(F,A)=G – ми отримуємо у вигляді композиції реалізацій: R(F,A)=R(F,B)*R(B,C)*...*R(Z,A), де В, ..., Z – проміжні оператори (їхні зовнішні описи), запропоновані в процесі рішення задачі. Відзначимо, при проведенні кроку декомпозиції Х, як правило, реалізується на базі не одного Y, а декількох. Тому у формулі для кроку декомпозиції Y варто розуміти як позначення вектора, тобто вірніше було б писати Х⇒(Y1, ..., Yn)&R(X,(Y1, ..., Yn)). Очевидно, у якості Yi можна використовувати оператори, зовнішні описи яких були отримані раніше, на попередніх кроках декомпозиції. Таким чином, за винятком, можливо, найпершого кроку, перед нами буде стояти не задача написання однієї окремо взятої програми, а задача реалізації одного оператора на базі якихось інших. У процесі проектування ми можемо побачити, що запропонована ієрархія проміжних операторів невдала, що якийсь оператор не реалізується чи реалізується занадто складно. У цьому випадку необхідно повертатися на декілька кроків декомпозиції назад і починати процес програмування з відповідного кроку. Приведений вище технологічний ланцюжок є ідеалізацією й описує процес програмування без таких повернень. Алгебро-граматична точка зору на процес проектування програм полягає в тому, що в якості математичної моделі ПрО задачі використовується граматика структурного проектування (ГСП), визначена над багатоосновною (багатосортною) алгеброю структур даних. У загальному випадку, як створення ГСП, так і “витяг” з неї алгоритму для рішення задач деякого конкретного типу – у тих випадках, коли це можливо, – вимагає, узагалі говорячи, високої кваліфікації і винахідливості, глибокого проникнення в семантику актуальної ПрО. У деяких випадках, при заданій ГСП, процес “витягу” з даної моделі алгоритму стає таким, що його може в точності виконати людина, що не має ні найменшого уявлення про сутність самої задачі. Потрібно лише, щоб ця гіпотетична людина була здатна виконувати ті елементарні операції, з яких складається процес, і, крім того, щоб вона сумлінно й акуратно керувався запропонованим розпорядженням (алгоритмом керування виводом), закладеним у ГСП. У таких випадках людину, що, керуючись визначеним алгоритмом, одержує алгоритм рішення конкретної задачі, можна дійсно замінити машиною, що виконує той же процес. Характерна риса цієї машини полягає в тому, що, починаючи з того моменту, як у неї введені початкові дані (умова задачі) і програма (алгоритм, що знаходить розв’язок задачі), вона може працювати без усякого втручання людини аж до видачі остаточного результату. При цьому, звичайно, не задовольняються констатацією того, що з відповідної ГСП можна “витягти” для даного кола задач алгоритм, що розв’язує їх , а прагнуть відшукати по можливості більш “оптимальний” алгоритм. Спроба автоматизувати ці процеси в загальних постановках задач, тобто спроба знайти їхнє повне і точне рішення, наштовхується на фундаментальні труднощі, що пов’язані з алгоритмічною нерозв’язністю. Щоб найбільш цікаві з них, насамперед у таких областях інтелектуальної діяльності людини як проектування алгоритмів і програм, їхня модифікація, зокрема, оптимізація і спеціалізація, доказ теорем і тому подібне, не були безповоротно закриті, необхідно виробити реалістичний підхід, заснований на відмовленні від повноти, абсолютної достовірності чи, можливо, чогось ще. Один з таких підходів дає концепція діалогових обчислень. Дійсно, якщо F – аксіома ГСП, Н – її схема (сукупність продукцій), а G – необхідний алгоритм, що формулюється в метамові неявно, у вигляді мети, і який необхідно одержати в предметній мові з використанням продукцій Н, то концепція дає “рішення” основної задачі програмування. Оскільки процес багаторівневого проектування алгоритмів і програм трактується у ГСП як вивід, на кожному кроці якого застосовується одне з правил граматики, то тим самим отримує уточнення операція „крок декомпозиції”. Твердження 2. Концепція діалогових обчислень в алгебро-граматичних термінах дає уточнення основної задачі програмування та шлях до автоматизації її рішення. Розглянемо алгоритмічний клон (теорія клонів покладена в основу метаалгебри алгоритміки – верхнього рівня дворівневої алгебри алгоритміки [4]) ALK = <{ОПЕР, L(2)}; СУПЕР>, де ОПЕР – множина неінтерпретованих операторних схем, L(2) – множина бульових функцій (БФ), СУПЕР – сигнатура, що включає лише операцію суперпозиції. Розглянемо деяку множину утворюючих Z⊂ОПЕР, в яку входять, зокрема, діалогові операції [10]. Замикання [Z] зазначеної множини по суперпозиції породжує алгоритмічний клон діалогових схем KDS⊂ALK: KDS = <{АДС, L(2)}; СУПЕР>, де АДС – множина діалогових неінтерпретованих схем. Нехай Z=Zо∪Zу, де Zо⊂ОПЕР, Zу⊂L(2). За допомогою приєднання операцій, які входять у Z, до сигнатури СУПЕР клону КDS може бути отримана алгебра діалогових алгоритмів (АДА) ADA=<{АДС, L(2)}; СУПЕР∪Z>, породжена сукупністю змінних V=V0∪Vу, де V0 і Vу – елементарні операторні і предикатні змінні. Розробка сукупностей інтерпретацій змінних із V сполучена з побудовою багатоосновних алгебраїчних систем (БАС) <{Di: i∈I}; СИГН>, де СИГН=Sо∪Sу. Якщо сорти Di інтерпретувати як множини оброблюваних даних, то БАС являє собою формалізацію концепції абстрактних типів даних (АТД). З АТД асоціюється гіпотетична машина, доступ до станів операційної структури якої і їхнє перетворення можливі лише в результаті застосування команд ГМ – елементарних операторів і предикатів, що входять до складу сигнатури АТД. Розміщення елементів АТД на носіях абстрактних типів пам’яті (АТП) забезпечує можливість виконання тієї чи іншої програми ГМ, оформленої у вигляді регулярних схем (РС) над сигнатурою АТД. Будемо говорити, що схема F трансформаційно зводиться в АДА до схеми G, якщо існує вивід G із F, на кожному кроці якого застосовується одне із діалогових метаправил: згортка, розгортка (та їх сполучення) і застосування співвідношення. Відзначимо, що, на відміну від метаправила трансформації алгебри алгоритміки [4], діалогова трансформація розуміється в широкому значенні – не тільки перетворення з використанням співвідношень, але і проектування алгоритмів і програм, що задовольняють визначеним властивостям. Під діалоговою трансформаційною машиною (ДТМ) розуміється гіпотетична машина, асоційована з концепцією АТД [11]. Список команд такої машини (видима частина АТД) базується на зображувальних засобах діалогових алгебро-граматичних формалізмів, що побудовані і досліджені у [10]. По аналогії з мовою САА\1, яка базується на апараті алгебри Глушкова, запропонована мова САА\Д проектування діалогових алгоритмів – вхідна для ДТМ, яка базується на зображувальних засобах діалогових ГСП. Побудовано апарат трансформації подібних проектів, який базується на метаправилах виводу, прийнятих в ГСП і збагачених засобами діалогу – діалогові згортка, розгортка, переінтерпретація і застосування співвідношень. Процес проектування діалогових алгоритмів і програм, оформлених засобами діалогових алгебро-граматичних формалізмів підтримуються в ДТМ спеціальною підструктурою – машиною виводу (МВ). Крім того, ДТМ представляє собою систему відкритого типу, яка, згідно з концепцією об’єктно-орієнтованого підходу, допускає підключення не тільки різноманітних цільових мов програмування (як це було в синтезаторі МУЛЬТИПРОЦЕСИСТ), але і різних ПрО (баз знань). Методи програмування діалогових адресно-обчислюваних функцій, змішані обчислення і оптимізація програм Як показав розвиток класичної і прикладної теорії алгоритмів, ні конкретний вибір обчислювальної моделі (ОМ), ні конкретний вибір способу програмування (при фіксованій моделі) майже (тут маються виключення, пов’язані з поняттям норми програми) не впливають на те, які теореми про обчислювальні функції і їхні програми виявляться справедливими. Іншими словами, у широких межах можлива єдина теорія методів програмування обчислюваних функцій. Точним математичним підтвердженням цієї тези є теорема Роджерса про ізоморфізм гьоделевих нумерацій [2]. Цей результат відкриває шляхи пошуку формального визначення поняття “метод програмування” (МеПр), яке, як відомо, в силу своєї загальності, є інтуїтивним поняттям. Зокрема, у відповідності зі сказаним, в класичній теорії алгоритмів в якості формального визначення МеПр обчислюваних функцій пропонується використовувати властивість гьоделевості так званої результатної функції ℜ(p,x)~R(A(p,x,µtП(A(p,x,t))) [2], де A(p,x,t) – тримісна функція (її можна називати адресною), значення якої дорівнює (повному) стану обчислювального процесу в момент часу t при роботі машини з програмою p∈P на вхідному даному х∈Х∞. Вхідна процедура є відображення x→A(p,x,0). Процедура закінчення являє собою предикат П, заданий на множині всіх можливих станів обчислювального процесу, а вихідна процедура – відображення R цієї множини в множину Y∞. Час роботи даної програми p∈P на даному аргументі х∈Х∞ визначається як найменше число t, при якому A(p,x,t) має властивість П. Значення R(A(p, x, t)) при цьому t природно вважати результатом роботи програми p∈P на вхідному даному х∈Х∞. Говорячи неформально, властивість гьоделевості й асоційовані з нею поняття (універсальна машина, s-m- n-теорема Кліні й інші) є абстракцією “доброго” МеПр, якщо на даному рівні абстракції “добрим” вважати такий МеПр, що за допомогою універсальної машини описує всі обчислення і дозволяє програми, складені іншим методом, ефективним образом переводити (транслювати) у програми, складені даним методом. Як показує практика, усі природно виникаючі МеПр мають властивість гьоделевості. Тому цю властивість можна розглядати як уточнюючу наші інтуїтивні уявлення про МеПр подібно тому, як теза Чьорча уточнює наші інтуїтивні уявлення про обчислюваність. При неформальному розумінні МеПр тезу гьоделевості для моделі, так само як і тезу Чьорча, не можна довести в звичайному математичному розумінні, але її можна підтверджувати, розглядаючи різні представницькі ОМ і різні точно описані МеПр. Однак, якщо теза Чьорча дає точний опис класу обчислювальних функцій, у той час як тут ми маємо лише “верхню” оцінку для класу всіх МеПр. Однак результатна функція лише частково відображає наші інтуїтивні уявлення про процес застосування даної програми до даного аргументу. Нам хотілося б, щоб весь процес обчислення, що веде від х∈Х∞ до y∈Y∞, усі проміжні викладки можна було запротоколювати так, щоб цей протокол містив вичерпну інформацію про всі послідовні етапи процесу. Ці уявлення мають витоки, насамперед, у реальному процесі виконання програм на реальних ЕОМ. У зв’язку з цим опишемо деякий клас алгоритмів спеціального вигляду – діалогові адресні програми (ДАП), що представляють собою послідовність пронумерованих команд, кожна з яких має один із видів(див. також [12]: 1) ‘a←b (присвоєння значення); 2) ‘a←‘b (пересилання чи переадресація); 3) ‘a←‘b+’c (додавання); 4) ЯКЩО ‘a=‘b ТО ЙТИ ДО m (умовний перехід); 5) СТОП (зупинка програми); 6) ПРИЗУПИНИТИ; (тимчасова зупинка програми); 7) ВИВЕСТИ(х); (виведення на екран ‘х); 8) ВВЕСТИ(х); (присвоєння ‘х деякого значення b); 9) ПРОДОВЖИТИ; (відмінює тимчасову зупинку програми). Тут a, b, c, m, n – деякі натуральні числа, ‘х – штрих-операція [13]. У [14] команди обнуління (окремий випадок присвоєння значення), додавання одиниці і переадресації названі арифметичними. Адресні програми можуть виконаються на ідеальних адресних обчислювальних машинах (ІАОМ), які мають нескінченне число пристроїв, призначених для збереження (запам’ятовування) натуральних чисел. Ці пристрої називають комірками пам’яті чи регістрами. Регістри забезпечуються номерами (адресами) 0, 1, 2,... у зв’язку з чим одержують наочний зміст символи команд, що були введені раніше. Переробка інформації в ІАОМ має форму встановлення і зміни деякого адресного відображення, відслідковувати зміни якого зручно мовою процесів (див. наступний підрозділ). Станом ІОАМ називається нескінченна послідовність натуральних чисел s=(s0, s1, ...), у якій майже всі (усі, крім кінцевого числа) дорівнюють 0. Якщо s0=0, стан називається заключним (станом зупинки); якщо s0≥1, стан називається робочим, а s0 – номером команди, що виконується. Число si+1 називається вмістом і-го регістра. Нехай p – деяка ДАП, s=(s0, s1 ,...) – робочий стан. Будемо говорити, що програма p може бути застосована до стану s, якщо s0 – номер однієї з команд програми p. Команди з номером s0 може і не бути, наприклад, якщо s0 занадто великий, – у цьому випадку говорять, що програма p не може бути застосована до стану s. Визначимо тепер деякий стан s’, що називають безпосереднім результатом застосування програми p до стану s. Стан s’=(s0’, s1’,...) визначається в такий спосіб: 1) якщо команда з номером s0 має вигляд ‘a←b, то s0’=s0+1, si+1’=si+1 при i≠a, sa+1’=b (уміст усіх регістрів, крім а-го, не міняється, в а-му регістрі міститься число b; машина переходить до виконання наступної по порядку команди); 2) якщо команда з номером s0 має вигляд ‘a←‘b, то s0’=s0+1, si+1’=si+1 при i≠a, sa+1’=sb+1; 3) якщо команда з номером s0 має вигляд ‘a←‘b+’c, то s0’=s0+1, si+1’=si+1 при i≠a, sa+1’=sb+1+sc+1; 4) якщо команда має вигляд ЯКЩО ‘a=‘b ТО ЙТИ ДО m, то si+1’=si+1 при всіх i; якщо sa+1=sb+1, то s0’=m; якщо ж sa+1’≠sb+1, то s0’=s0+1 (вміст регістрів не міняється; якщо вміст а-го регістра дорівнює вмісту b-го регістра, то машина переходить до виконання команди з номером m, в протилежному випадку – до виконання наступної команди); 5) якщо команда має вигляд СТОП, то si+1’=si+1 для всіх i і s0’=0 (машина переходить у заключний стан); 6) якщо команда має вигляд ПРИЗУПИНИТИ, то si’=si для всіх i≥0 (машина залишається у попередньому стані); 7) якщо команда має вигляд ВИВЕСТИ(х), то si+1’=si+1 для всіх i≥0, s0’=s0+1; 8) якщо команда має вигляд ВВЕСТИ(х), то ‘х←b (тут b – деяке введене значення), s0’=s0+1; 9) якщо команда має вигляд ПРОДОВЖИТИ, то si+1’=si+1 для всіх i≥0, s0’=s0+1. Протоколом застосування ДАП p називається послідовність станів s0, s1, ..., sk, у якій кожний наступний є результатом застосування програми p до попереднього, а останній стан є заключним. Стан s0 називають початковим станом протоколу. На відміну від детермінованого випадку, може існувати більше одного протоколу даної ДАП p з даним початковим станом; такого протоколу не існує, якщо p не може бути застосована до s0 чи якщо в послідовності, що виникає при багаторазовому застосуванні p до s0 , не зустрічається заключний стан. Нехай N – множина натуральних чисел, k – натуральне число. Розглянемо функцію f: Nk→N, що визначається в такий спосіб: значення f на наборі <a1 ,..., ak> дорівнює b, якщо існує протокол застосування ДАП p, початковим станом якого є (1, a1, a2, ... , ak, 0, 0, ...), а b є вміст 0-го регістра в заключному стані цього протоколу. Функцію f будемо називати функцією, dk-обчислюваною ДАП p (чи просто d-обчислюваною, якщо значення k ясне з контексту). Функції, dk-обчислювані ДАП, будемо називати адресно-обчислюваними функціями k аргументів. Очевидно, що всі адресно-обчислювані функції обчислювані; з іншого боку, усі обчислювані функції, відомі в даний час, виявляються адресно-обчислюваними (звичайно, тут необхідно враховувати розглянуте раніше зауваження про ідеалізацію). Таким чином, є підстави прийняти гіпотезу про збіг класів обчислюваних функцій з Nk у N і адресно-обчислюваних функцій. У цьому ж розумінні можна говорити про методи програмування діалогових адресно-обчислювальних функцій [12]. Властивість гьоделевості МеПр можна розглядати як теоретичне обґрунтування ідеї автоматизації програмування – існує автоматичний спосіб одержання з універсального алгоритму його спеціалізації. Процес переходу від універсального алгоритму до його спеціалізації було названо змішаним обчисленням [1,2,15-18]. Однак відповідні формулювання не дають конкретного алгоритму спеціалізації: у них враховується тільки семантична сторона – зв’язок програми з об’єктом, що обчислюється нею, – і майже не враховується синтаксична. Щоб знайти практичні основи для спеціалізації, уже недостатньо обмежуватися “якісною” теорією алгоритмів – необхідно визначитися з вхідною мовою змішаного обчислювача (ЗмО) – деякою мовою специфікацій алгоритмів, призначених для виконання на базовому обчислювачі (БО); зафіксувати (базову) МП; встановити необхідний інтерфейс між названими мовами (вони, взагалі говорячи, різні). З метою визначення вхідної мови ЗмО знову звернемося до визначення поняття МеПр, властивість гьоделевості якого “постулює”, зокрема, існування алгоритму, що дозволяє ефективно переходити від програм одного типу до програм іншого. Цей алгоритм не є конструктивним об’єктом, але оскільки всі природно виникаючі МеПр все-таки мають властивість гьоделевості, то це припускає існування визначення обчислюваності, що знаходиться в рівному положенні стосовно всіх конкретних теорій алгоритмів, що стають, таким чином, моделями цього абстрактного визначення. Перше коло досліджень показує, що початковий крок абстракції повинен складатися в пошуках визначення обчислювальності для довільних ПрО з фіксованими наборами елементарних операцій і предикатів, тобто для абстрактних алгебраїчних систем [15]. Відправною крапкою дослідження практичних основ спеціалізації може служити мета спеціалізації, що розуміється змістовно: одержання більш ефективного алгоритму, ніж початковий [1,2,15-18]. Основу способів спеціалізації у цьому випадку можуть скласти, наприклад, традиційні методи оптимізації програм, що базуються на результатах потокового аналізу [16], основною задачею якого є схематизація базової програми з метою одержання глобальної інформації про її семантичні властивості. Альтернативним підходом до оптимізації програм та спеціалізації служить використання формалізмів [4,17-19]. Рішення проблеми інтерфейсу між вхідною мовою ЗмО і мовою БО може бути досягнуте при використанні в якості мови ЗмО мови САА\Д-схем програм чи гіперсхем, а в якості самого ЗмО – ДТМ. На вхід ДТМ подається аксіома ГСП і множина її продукцій, на виході маємо деяку САА\Д-схему, у процесі проектування якої елементи її базису автоматично відображаються в обраній базовій мові. Інтерпретуючи частину елементів базису в цій мові і “заморожуючи” інші з них, можна побудувати залишкову схему і здійснити часткові обчислення на БО. Твердження 3. МеПр адресно-обчислювальних функцій завдяки введенню поняття протоколу обчислення адресних алгоритмів явно враховує не тільки результати обчислень, а й проміжні стани, які виникають в процесі виконання адресних алгоритмів. При цьому враховується можливість спеціалізації, що властива змішаним обчисленням, зокрема, конкретизуючому програмуванню. У зв’язку з отриманим результатом підкреслимо плідність поняття іменної множини [20], що становить важливий елемент композиційного програмування – складової частини програмології [5] – сучасної науки про алгоритми та програми. Поняття іменної множини узагальнює відомий принцип адресності, який був покладений в основу адресної мови програмування [13] – однієї з перших вітчизняних мов високого рівня. Діалогові системи та процеси Поняття системи, в силу своєї фундаментальності, відноситься до невизначуваних понять науки [21]. Повний опис потенційної поведінки (функціонування, роботи) системи називають процесом [5,6,22]. На відміну від поняття системи, яке є інтуїтивним поняттям, поняття процесу допускає точну математичну трактову. Центральне значення процесів для обчислювальних систем робить дуже бажаним точне математичне визначення поняття „(діалоговий) процес”, яке ґрунтувалося б на відповідних, що піддаються прямому чи непрямому спостереженню, властивостях (обчислювальних) систем і, зокрема, охоплювало б детерміновані та недетерміновані процеси. Під системою будемо розуміти сукупність взаємопов’язаних і взаємодіючих компонент, що відмежована від навколишнього середовища і взаємодіє з ним як єдине ціле [21,22]. Вважається, що система служить засобом досягнення деякої мети і саме цій меті підпорядкована організація всієї системи. Якщо система побудована із окремих, що віддалені одна від одної, компонент, то систему називають розподіленою. Систему називають послідовною, паралельною чи діалоговою у залежності від того, як виникають активності компонент - послідовно у часі, можуть мати місце одночасно (паралельно) чи у діалоговому режимі. Для кожного типу системи визначається відповідний тип процесу [22,23]. З кожною системою асоціюється множина (універсум) Е0 подій, що виникають у деякому, визначеному властивостями системи і впливом її зовнішнього оточення, порядку. Тому, перш за все, необхідно вирішити, якого роду події з поведінки системи нас цікавлять і вибрати для кожної з них відповідну назву, або ім’я. Множина Е⊂Е0 імен подій, що вибирається для конкретного опису системи, називається алфавітом системи. Алфавіт вважається постійною, заздалегідь визначеною властивістю системи. Приймати участь у події, що виходить за рамки алфавіту, для системи логічно неможливо. Система називається кінцевою (зокрема, пустою) або нескінченною в залежності від того, кінцевою або нескінченною є її множина подій Е. Послідовність імен подій, у яких процес приймав участь до деякого моменту часу, називається протоколом. Повний набір всіх можливих протоколів процесу Р будемо позначати через протоколи(Р). Виявляється, між кожним процесом Р і парою множин (Е, протоколи(Р)) існує (1-1)-відповідність. Останнє твердження служить достатньою основою для їх подальшого ототожнення і наступного визначення [6,22,23]. (Детермінований) процес - це пара (В,S), де В – довільна множина символів, а S – довільна підмножина В*, така що: 1. <>∈S; 2. ∀s, t s^t∈S ⇒ s∈S. Після визначення (детермінованого) процесу можна дати формальне визначення деяких операцій над процесами: префікс, рекурсія, вибір, паралельне виконання і інших. Однак, визначення (детермінованого) процесу не цілком достатнє визначення поняття процесу, оскільки в ньому, зокрема, ніяк не представлена можливість недетермінованого поводження. (Недетермінований) процес [22,23] – це трійка (Е, W, Q), де Е – довільна множина символів (для простоти – кінцева), W⊆Е*×2Е, Q⊆Е*, така що: 1. (<>, {})∈W; 2. (s^t, X)∈W ⇒ (s, {})∈W; 3. (s, Y)∈W & X⊆Y ⇒ (s, X)∈W; 4. (s, Y)∈W & x∈Е ⇒ (s, X∪{x})∈W ∨ (s^<x>, {})∈W; 5. Q⊆область(W); 6. s∈Q & t∈Е* ⇒ s^t∈Q; 7. s∈Q & X⊆Е ⇒ (s, X)∈W. Найпростіший процес, що задовольняє цьому визначенню, - це ХАОСЕ=(Е, Е*×2Е, Е*). Це найбільший процес з алфавітом Е, оскільки кожен елемент Е* є і його протоколом, і розходженням, а кожна підмножина Е* є відмовою після будь-якого протоколу [23]. Операції над (недетермінованими) процесами задаються описом того, як отримати три множини, що визначають їх результат, із відповідних множин їх операндів. Певна річ, необхідно показати, що результат операції задовольняє всім умовам у визначенні процесу. На щастя, це зробити не складно [23]. Дамо визначення процесу, що рекурсивно визначається за допомогою µ-оператора, а також доведемо основну теорему про нерухому точку [22]: µX: Е.F(X)=F(µX: Е.F(X)). Доведення того, що µX: Е.F(X) – рішення (фактично саме недетерміноване рішення) відповідного рівняння з точністю до визначення упорядкування і µ-оператора співпадає з доведенням для детермінованого випадку із [22]. В основу доведення покладено теорію нерухомої точки по Скотту [23]. Тому, перш за все, введемо на множині процесів відношення порядку: (С, W1, Q1) [⊆] (В, W2, Q2) ⇔ (С=В & W2⊆W1 & Q2⊆Q1). Запис (С, W1, Q1) [⊆] (В, W2, Q2) означає, що процес (В, W2, Q2) дорівнює (С, W1, Q1) або краще його у тому розумінні, що він з меншою імовірністю розходиться і з меншою імовірністю терпить невдачу. Очевидно, це відношення є частковим порядком в тому розумінні, що 1. (Е, W1, Q1) [⊆] (Е, W1, Q1); 2. (Е, W1, Q1) [⊆] (Е, W2, Q2) & (Е, W2, Q2) [⊆] (Е, W1, Q1) ⇒ (Е, W1, Q1)=(Е, W2, Q2); 3. (Е, W1, Q1) [⊆] (Е, W2, Q2) & (Е, W2, Q2) [⊆] (Е, W3, Q3) ⇒(Е, W1, Q1) [⊆] (Е, W3, Q3); Ланцюгом у наведеному упорядкуванні називається нескінченна послідовність елементів {(Е, W0, Q0), (Е, W1, Q1), (Е, W2, Q2), …}, така, що ∀n≥0 (Е, Wn, Qn) [⊆] (Е, Wn+1, Qn+1). Границя (найменша верхня грань) такого ланцюгу визначається в термінах перетинів ланцюгів, що убувають, невдач і розходжень: C 0≥n (Е, Wn, Qn)=(Е, I 0≥n Wn, I 0≥n Qn) при умові, що ∀n≥0 Wn+1⊆ Wn, Qn+1 ⊆ Qn. Говорять, що частковий порядок повний, якщо в ньому є найменший елемент, а всі ланцюги мають найменшу верхню грань. Множина всіх процесів над даним алфавітом Е утворює повний частковий порядок, так як вона задовольняє наступним законам: 1. ХАОСЕ [⊆] (Е, W, Q). 2. (Е, Wі, Qі) [⊆] C 0≥i (Е, Wі, Qі); 3. (∀і≥0 (Е, Wі, Qі) [⊆] (Е, W, Q)) ⇒ (C 0≥i (Е, Wі, Qі)) [⊆] (Е, W, Q). В термінах границі можна сформулювати і визначення µ-оператора: µX: Е.F(X) = C 0≥i Fi(ХАОСЕ). Функція F із одного повного часткового порядку в інший (або в той самий) безперервна, якщо вона дистрибутивна відносно границь всіх ланцюгів, тобто, якщо {(Е, Wі, Qі)| i≥0} утворює ланцюг, то F безперервна при умові, що F(C 0≥i (Е, Wі, Qі)) =C 0≥i F((Е, Wі, Qі)). Говорять, що функція із множини протоколів у множину протоколів монотонна, якщо вона зберігає відношення часткового порядку. Всі дистрибутивні функції монотонні, а, значить, монотонними будуть і всі безперервні функції у тому розумінні, що (Е, Wn, Qn) [⊆] (Е, Wn+1, Qn+1) ⇒ F(Е, Wn, Qn) [⊆] F(Е, Wn+1, Qn+1), і тому права частина попередньої рівності є границею ланцюга, що росте. По визначенню, функція F від декількох аргументів безперервна, якщо вона безперервна по кожному аргументу в окремості. Композиція безперервних функцій також безперервна. І, нарешті, будь-який вираз, що отриманий застосуванням будь-якого числа безперервних функцій до будь-якого числа і комбінації змінних, безперервний по кожній із цих змінних. Всі визначені операції над процесами (крім операції “після” / [23]) безперервні у вищезазначеному розумінні. Таким чином, якщо вираз F побудований в термінах тільки цих операцій, то він буде безперервним по Х. Тепер можна довести наступне твердження. Теорема 1 (основна теорема про нерухому точку) [22]: µX: Е.F(X)=F(µX: Е.F(X)). Дійсно, F(µX: Е.F(X)) = (по визначенню µ) = F(C 0≥i Fi(ХАОСЕ)) = (безперервність F) = C 0≥i F(Fi(ХАОСЕ)) = (по визначенню Fi+1) = C 0≥i Fi+1(ХАОСЕ) = (ХАОСЕ [⊆] F(ХАОСЕ)) =C 0≥i Fi(ХАОСЕ) = µХ: Е.F(X) (по визначенню µ). Таким чином, повний набір всіх можливих протоколів будь-якого процесу може бути відомим нам завчасно, але до початку процесу невідомо, який саме із можливих протоколів буде реалізований - його вибір залежить від зовнішніх по відношенню до процесу факторів. У загальному випадку перерахувати всі фактори, що впливають на функціонування систем, часто буває занадто складно (якщо взагалі можливо). Тому нам потрібне більш загальне визначення (діалогового) процесу, у формулювання якого повинні бути включені ще деякі додаткові вказівки, зокрема, про можливість динамічного (діалогового) керуванням процесом обчислень, про результати проміжних обчислень і так далі. До сих пір множину подій ми не інтерпретували далі. Однак, кожній події відповідає виконання деякої дії із множини А дій. Важливе значення для дій в процесах має змінювання станів. Множину S всіх станів будемо називати простором станів системи. Нехай надалі α: Е→А – позначення дії процесу. Тоді ∀e∈E α(e)=q∈A, q: S→S. Ввівши простір станів, можна розглядати в ньому послідовності станів (траєкторій), у яких знаходиться система в фіксовані моменти часу, а саму систему (предметну область) визначити як клас усіх дійсно можливих траєкторій системи (предметної області). Очевидно, елементи будь-якої траєкторії не можуть бути довільними, оскільки поточний стан, як правило, якось пов’язаний з попередніми станами. Тому у наведеному вище визначенні системи словосполучення “дійсно можливих” вимагає подальшого уточнення. У зв’язку з програмами і поставленими їм у відповідність процесами виникає питання про те, які зміни станів можуть бути безконфліктно вироблені паралельно в часі. Дати відповідь на це запитання, а також розкрити деякі інші важливі аспекти функціонування систем (наприклад, паралелізм, деталізація та інші), можна за допомогою поняття причинності [21-24]. Позначимо через p відношення причина-наслідок. Нехай відношення conflict⊆A×A для кожної пари дій q1, q2∈A задає, чи існує конфлікт. Процес р будемо називати безконфліктним, якщо ∀e, d∈E (α(e),α(d))∈conflict ⇒ep d∨dp e. Кінцеві процеси визначають зміни станів, якщо тільки діям зіставлені відображення змін станів ρ: А→(S→S) і процеси являються безконфліктними. Очевидно, процеси і їх значення є формальними описами історій протікання процесів. Система позначень для опису послідовних процесів [23], не менш потужна, ніж регулярні вирази. Використання рекурсії робить її потужність близькою до контекстно вільних граматик, але все ж не до кінця. Це відбувається тому, що при використанні оператору вибору (х: В→G(х)), який спочатку пропонує на вибір довільну подію х із деякої множини подій В (її називають початковим меню процесу), а потім веде себе як G(х), де G(х) – функція, що ставить у відповідність символу х∈В процес G(х) із деякої множини процесів Y, вимагається, щоб перша подія кожної альтернативи відрізнялась від інших можливих перших подій. Якщо перша подія можлива для декількох процесів, то вибір між ними залишається недетермінованим. Зауважимо, оператор вибору є дистрибутивним відносно операції недетермінованого вибору P|Q: (х: В→(P(х)|Q(х))=(х: В→P(х))|(х: В→Q(х)). Якщо у цьому випадку вибір буде зроблено невірно, то процес увійде в стан дедлоку. Реалізація може мінімізувати ризик дедлоку, відкладаючи вибір до тих пір, доки його не зробить оточення, і вибираючи той процес із P і Q, який не створює дедлоку. Однак ціна такої реалізації в термінах ефективності дуже висока: P і Q повинні виконуватися паралельно до тих пір, поки оточення не вибере подію, можливу для одного процесу і неможливу для іншого (у цьому розумінні операція недетермінованого вибору виявляється не самим кращим способом об’єднання процесів, оскільки оточення повинне бути готовим до того, щоб працювати з кожним із них, в той час як робота лише з одним із них була б, скоріше всього, більш простою). Дистрибутивним (зліва і справа) відносно недетермінованого вибору є також паралельний оператор: R||(P|Q)=(R||P)|(R||Q); (P|Q)||R=(P||R)|(Q||R). При цьому введення паралельного оператору || дозволяє задавати мови, що не є контекстно вільними. Рекурсивний оператор, однак, не є дистрибутивним [23]. Дійсно, легко бачити, що, наприклад, для Р=µХ.((а→X)(b→X)) і Q=(µX.(a→X))(µX.(b→X)) протоколи(Q)⊆протоколи(Р). У зв’язку з наведеними вище міркуваннями введемо новий різновид оператора вибору – оператор узагальненого (діалогового) вибору ([22], див. також [1,10]) – ДВ(х: В→G(х)), за допомогою якого оточення уже зможе керувати вибором між недетермінованими процесами на кожному кроці ітерації. У випадку, коли початкові події для всіх процесів, що входять в область значень Y функції G(х), різні, то ДВ(х: В→G(х))=(х: В→G(х)). Якщо деякі з процесів множини Y мають спільні початкові події, то початкове меню В розширюється додатковими пустими подіями (цим подіям не відповідає жодна дія) таким чином, щоб можна було встановити (1-1)-відповідність між подіями із множини В і процесами із множини Y, а функція G(х) модифікується згідно з визначенням діалогового вибору наступним чином. Якщо під час функціонування системи зустрічається спільна для деяких процесів подія, то функціонування системи призупиняється і система переходить в стан чекання вводу деякої (пустої) події. Після введення функціонування системи продовжується з процесу, відповідного введеній події. Різниця між операторами ДВ(Р|Q), (Р|Q) є досить тонкою. Їх не можна розрізнити по множинам протоколів, оскільки протокол одного із них можливий і для іншого. Однак, їх можна помістити в таке оточення, в якому (P|Q) увійде у дедлок, а ДВ(Р|Q) – ні. В той же час, µХ.ДВ(х: В→G(х,Х)) = µХ.(х: В→G(х,Х)), однак ДВ(х: В→G(х,Х)) дає можливість динамічного (діалогового) керуванням процесом породження будь- якого протоколу із множини протоколів рішення відповідного рекурсивного рівняння, а (х: В→G(х,Х)) – ні. Підсумовуючи наведені вище міркування ми приходимо до наступної (на даному рівні абстракції) математичної моделі для (діалогового) процесу. (Діалоговий) процес [22] - це вісімка (Е, W, Q, А, S, p , α, conflict), де W⊆Е*×2Е, Q⊆Е* і на них накладаються обмеження, властиві недетермінованим процесам. Твердження 4. Визначення діалогового процесу охоплює недетерміновані (зокрема, детерміновані) процеси і представляє інтерес як більш широка модель обчислень. Відзначається, що існує можливість тлумачення причинно-наслідкового відношення у визначенні системи, зокрема, як часткового порядку. Часткові порядки на кінцевих множинах однозначно характеризуються множиною елементів, безпосередньо наступних за кожним елементом. Однак для часткових порядків на нескінченних множинах це не справедливо. У випадку, коли процес починає вести себе хаотично, застосовується діалог. Виявляється, саме оточення процесу може бути описане як процес. Це дозволяє досліджувати поведінку цілої системи, що складається з процесу і його оточення, які взаємодіють по мірі їх паралельного виконання. Зокрема, потоки даних (вхідних і вихідних) і функції, що їх обробляють, можуть застосовуватися для моделювання взаємодії користувача і ДТМ [11]: користувач породжує потік завдань до ДТМ, а ДТМ виробляє потік системних виводів як „завдань” для користувача. Взаємодію користувача і ДТМ можна визначити через взаємо рекурсивні рівності. Найменша нерухома точка тоді представляє собою потік, який задовольняє рівнянню нерухомої точки. Тим самим адекватно моделюється зворотній зв’язок і взаємодія. Якщо виникає ситуація взаємного чекання (тупик), то потік обривається. Представлення алгоритмічних знань та керування процесом їх генерації, що прийняте в діалоговій трансформаційній машині Представлення алгоритмічних знань в ДТМ пов’язане з описом алгоритмів за допомогою схем. Оскільки САА\Д-схеми мають однаковий синтаксис з діалоговими гіперсхеми (що являють собою, по суті, різновид ГСП з розвинутими засобами керування виводом), то це дозволяє використовувати САА\Д-схеми і побудований в [10] апарат алгебр діалогових гіперсхем (АДГС) для компактного представлення класів алгоритмів і програм та гнучкого - за рахунок введення механізму параметрів, що задаються на рівні базисних операторів і умов - керування процесом їх генерації. В якості приклада розглядається алгоритм, що описує роботу автомату по розміну металевих монет. Припустимо, що автомат працює з п’ятьма типами монет і для кожного типу в автоматі мається декілька варіантів розміну, які він пропонує на вибір своїм клієнтам. Робота такого автомату може бути описана наступною діалоговою регулярною схемою (ДРС) в АДА σ=<A, B; Ω>: ДРМ1=ІН* ЕОР { ВВ* MINS< ( ДВ(ОП1ОП2)∨ MAXS > ( ДВ(ОП3ОП4)∨ДВ(ОП5ОП6) ))}, де ІН – оператор встановлення початкового стану даних алгоритму, ВВ – оператор введення чергової монети для розміну, ОП1, ..., ОП6 – оператори, що реалізують алгоритми розміну монети S визначеного кількісного еквіваленту; ЕОР – умова, що приймає значення “істина” при зупинці роботи автомату (можливо, тимчасовій, наприклад, для вилучення або поповнення запасу монет), ДВ – оператор діалогового вибору [10]. Інформаційна множина М, на якій задані оператори й умови, що входять у РС ДРМ1, асоціюються зі значеннями параметрів, з якими працює дана РС. Припустимо далі, що автомат буде застосовуватися в умовах, коли заздалегідь відомо, що будь-яка введена в автомат монета S задовольняє одній із попередніх умов: S<MIN, S≥MIN, S>MАХ, S≤MAX, MIN≤S≤MAX. При наведеному припущенні схема ДРМ1 стає надлишковою. Розглядаючи її як гіперсхему в алгебрі σ‘=<A’, B’; Ω‘> на інформаційній множині М’=S×L (S асоціюється з параметрами, що керують породженням РС), поставимо задачу генерації за ДРМ1 схем у САА σ‘=<A’, B’; Ω‘>, що відповідають вказаним умовам. Розглянемо підструктуру М1⊂М’: ∀р∈М1 ЕОР(р)=η. Припустимо також, що ∀р∈М1: F(ЕОР, р)=ЕОР, а оператори, що входять у РДГС ДРМ1, тотожні на підструктурі S: F(R, рψ)=R і ∀р∈М’: Rψ(р)=рψ. Нехай, для визначеності, попередньо задано таку умову: будь-яка введена в автомат для розміну монета S завжди менше MIN. Даній умові відповідає підмножина М2⊆М1, на якій для будь-якої монети S умова α1≡(A<MIN) є істинною, а умова α2≡(A>MAX) – не істинною. Застосувавши РДГС ДРМ1 до стану р∈М2 такого, що рL=∅, одержимо на стрічці ДРС ДРМ1 1=F(ДРМ1, р ψ)∈A: ДРМ1 1 = ІН* ЕОР { ВВ*ДВ(ОП1ОП2)} . Аналогічно, при попередній умові S≥MIN одержимо: ДРМ1 2 = ІН* ЕОР { ВВ* MAXS > ( ДВ(ОП3ОП4) ∨ ДВ(ОП5ОП6) )} і так далі. Нехай ∀р∈М3⊂М1 α1(р)=α2(р)=η; F(α1, р ψ)=α1, F(α2, р ψ)=α2. Застосувавши РДГС ДРМ1 до стану р∈М3, такого, що рL=∅, одержимо на стрічці ДРС ДРМ1 у САА σ=<A, B; Ω>. Отже, схеми ДРМ1 і, де і=1, ..., 5 і сама ДРМ1 належать до класу ДРС, що породжуються регулярною діалоговою гіперсхемою (РДГС) ДРМ1. Припустимо далі, що кожного типу монет в автоматі мається, відповідно, N1, …, N5 штук. Нехай відомо, що після видачі автоматом визначеної для даного типу кількості монет, автомат поновлює свої запаси монет даного типу із деякого запасника, після чого опрацювання вхідного потоку монет триває. Припускається, що поновлення може відбуватися не більше ніж N разів для кожного типу монет, після чого функціонування автомату (можливо тимчасово - для поновлення запасу монет із зовні) призупиняється. В нашому алгоритмі кожне поновлення моделюється шляхом деталізації операторів ОП1, …, ОП6: ДРМ1=ІН* ЕОР { ВВ* MINS< ( ДВ(ОП1ОП2)∨ MAXS > ( ДВ(ОП3ОП4)∨ДВ(ОП5ОП6) ))}; ОП1=ОПП1* MOZ ( E ∨ ОП7* RN ( ДРМ1 ∨ U )) ; ....; ОП6=ОПП6* MOZ ( E ∨ ОП7* RN ( ДРМ1 ∨ U )) . Тут ОПП1, ..., ОПП6 – оператори, що реалізують відповідний алгоритм розміну монет і віднімають кількість використаних при цьому монет визначеного типу від відповідного лічильника – S1, ..., S5 (названі лічильники, якщо їх вміст дорівнює нулю, поновлюються оператором ІН). Оператор ОП7, зокрема, підраховує кількість поновлень того чи іншого лічильника S1, ..., S5 шляхом додавання одиниці до одного з лічильників R1, ..., R5 (у початковому стані лічильники R1, ..., R5 дорівнюють нулю; їх вміст не змінюється оператором ІН); Е – тотожний оператор; U – оператор установки значення “істина” умови ЕОР; MOZ≡(S1>0)∧(S2>0)∧(S3>0)∧(S4>0)∧(S5>0); RN≡(R1<N)∧(R2<N)∧(R3<N)∧(R4<N)∧(R5<N). Звернувши в одну рівність, перетворимо отриману САА\Д-схему, застосувавши до неї тричі тотожність ДВ(А*СВ*С)=ДВ(АВ)*С і двічі – тотожність α ( А*С ∨ В*С ) = α ( А ∨ В ) *С. В результаті отримаємо: ДРМ1=ІН* ЕОР { ВВ* MINS< ( ДВ(ОПП1ОПП2)∨ MAXS > ( ДВ(ОПП3ОПП4)∨ ДВ(ОПП5ОПП6) )) * MOZ ( Е ∨ ОП7* RN ( ДРМ1 ∨ U ))}. Нехай тепер MIN≤S≤MAX для всіх монет, які вводяться в автомат для розміну, а N=2. Припустимо, що RN є змінною етапу генерації ДРС за АДГС-схемою ДРМ1. Описаній ситуації відповідає множина М4⊂М1 така, що ∀р∈М4 α1(р)=α2(р)=0, α3(р)=η, α4(p)≠η, де α3≡(MOZ), α4≡(RN). Покладемо ∀р∈М4 F(α3, p ϕ)=α3, ∀A∈{ІН, ВВ, ОПП1, …, ОПП6, ОП7, U, E}⊂A’ F(A, pϕ)=A, Aϕ(p)=pϕ. Тоді, застосувавши АДГС-схему ДРМ1 до деякого р=(рϕ, ∅)∈М’ отримаємо ДРС F(ДРМ1, p ϕ)= =ІН* ЕОР { ВВ*ДВ(ОПП5ОПП6)* MOZ ( Е∨ОП7*ІН* ЕОР { ВВ*ДВ(ОПП5ОПП6) * MOZ ( Е∨ОП7*U ))}. Перетворимо отриману ДРС, застосувавши до неї двічі співвідношення β { B* α ( E∨Uβ )} = α¬ { B}*Uβ, яке має місце при вхідних значеннях “не істинність” умови β та “істина” умови α, де В – оператор, який не змінює значення умови β і впливає на значення α; Uβ - оператор, що встановлює значення “істина” умови β. В результаті отримаємо F(ДРМ1, p ϕ) = =ІН * MOZ¬ { ВВ* ДВ(ОПП5ОПП6)}* ОП7 * ІН * MOZ¬ { ВВ * ДВ(ОПП5ОПП6)}* ОП7 * U. Оператор U при такому запису алгоритму можна опустити. Ввівши умову γ, що має у початковому стані значення “не істинність”, і оператор Uγ, який встановлює при його другій активізації значення “істина” умови γ, F(ДРМ1, p ϕ) можна записати у такому вигляді: F(ДРМ1, p ϕ)= γ { ІН* MOZ¬ { ВВ*ДВ(ОПП5ОПП6)}*ОП7*Uγ} . Алгоритм, що відповідає ДРС ДРМ1 у САА σ=<A, B; Ω>, можна записати у вигляді паралельної РС (ПРС), у якій α≡(S<MIN), β≡(S>MАХ), γ≡(MIN≤S≤MAX): ПРМ1=ІН* ЕОР { ВВ*(α ДВ(ОП1ОП2)∨ β ДВ(ОП3ОП4)∨γ ДВ(ОП5ОП6))} . Розглянемо ПРМ1 як РГС у модифікованій алгебрі гіперсхем (АГС), вважаючи визначення операторів і умов, що входять в неї, такими ж самими, як і у розглянутої раніше РДГС ДРМ1. У разі задавання попередньої умови: наперед відомо, що всі числа, що вводяться, менше від MIN, з якою пов’язана область М2⊆М1, така, що ∀р∈М2 α(р)=1, β(р)=γ(р)=0, застосувавши РГС ПРМ1 до стану р∈М2, в якому рL=∅, одержимо на стрічці РС: ПРМ1 1= ІН* ЕОР { ВВ*ДВ(ОП1ОП2)} . Аналогічно (розглянутим вище) виглядають РС, які отримують при задаванні на етапі генерації умов S>MАХ і MIN≤S≤MAX. Запишемо РГС, що містить операції асинхронного породження синхронної диз’юнкції: ПРМ2=ІН* ЕОР { ВВ*(α ДВ(ОП1ОП2) _ ∨ β ДВ(ОП3ОП4) _ ∨ γ ДВ(ОП5ОП6))} . Наведена РГС задає клас ПРС, що відповідають сформульованій задачі та генеруються при фіксації попередніх умов, варіанти завдання яких приведені раніше. У разі відсутності будь-яких попередніх умов РГС ПРМ2 породжує ПРС ПРМ1 у АГМ σ=<A, B; Ω>. Якщо припустити, що наш автомат не пропонує на вибір варіант розміну монет, то алгоритм його роботи описує РС НРМ1=ІН* ЕОР { ВВ* MINS< ( (ОП1ОП2)∨ MAXS > ( (ОП3ОП4) ∨ (ОП5ОП6) ))}, в якій вибір між операторами ОП1 і ОП2, ОП3 і ОП4, ОП5 і ОП6 відбувається недетерміновано. По аналогії з ДРМ1, НРМ1 можна розглядати як РГС, що породжує клас алгоритмів, обумовлений визначеними раніше параметрами. Твердження 5. Використовуючи заздалегідь відомі параметри, що визначають умови застосування представленого САА\Д-схемою алгоритму, можна одержати множину конкретизованих САА\Д-схем, орієнтованих на специфіку їх використання й оптимальних для заданих умов. Литература 1. Петрушенко А.Н. О диалоговых вычислениях в алгоритмических алгебрах // Кибернетика. – 1990. – № 1. – С. 13–20. 2. Успенский В.А., Семенов Л.Л. Теория алгоритмов: основные открытия и приложения. – М.: Наука, 1987.– 288 с. 3. Цейтлин Г.Е., Ющенко Е.Л. Формализованные спецификации и трансформационный синтез программ // Кибернетика и системный анализ. – 1993. – №1. – С. 127–138. 4. Цейтлин Г. Е. Введение в алгоритмику. – К.: Сфера, 1998. – 310 с. 5. Редько В.Н. Основания программологии // Кибернетика и системный анализ. – 2000. - №1. – С. 33-57. 6. Капитонова Ю.В., Летичевский А.А. Математическая теория проектирования вычислительных систем. – М.: Наука, 1988. – 296 с. 7. Кокорева Л.П., Перевозчикова О.Л., Ющенко Е.Л. Диалоговые системы и представление знаний Киев: Наук. думка, 1993. – 446 с. 8. Кушниренко А.Г., Лебедев Г.В. Программирование для математиков: Учеб. Пособие для вузов – М.: Наука. Гл. ред. физ.–мат. лит., 1988. – 384 с. 9. Петрушенко А.Н., Хохлов В.А., Шепетухин Е.С. Основная задача программирования и синтез операционных устройств // Вестник Херсонского государнственного технического университета. - 2001. - № 4 (10). - С. 216-221. 10. Петрушенко А.Н. Алгебры диалоговых алгоритмов и гиперсхем: некоторые их свойства и приложения // Вестник Международного Соломонова университета. – 2000. – №4. – С. 110-123. 11. Петрушенко А.Н., Хохлов В.А., Ткачев В.А., Шепетухин Е.С. Диалоговая трансформационная машина: некоторые функциональные возможности // Проблемы программирования. - 2000. - № 1-2 (Спец. выпуск) - С. 323-334. 12. Петрушенко А.Н. О машинно–независимых методах программирования адресно–вычислимых функций // Вестник Херсонского государственного технического университета.. – 1998. – №1 – С.134-139. 13. Ющенко Е.Л. Адресное программирование. – Киев: Гостехиздат, 1963 – 288 с. 14. Успенский В.А. Теорема Геделя о неполноте. - М.: Наука, 1982. - 111 с. 15. Ершов А.П. Смешанные вычисления // В мире науки. – 1984. – №6.– С. 28–42. 16. Касьянов А. П. Оптимизирующие преобразования программ. – М.: Наука, 1988. – 335 с. 13. 17. Летичевский А.А. Смешанные вычисления и оптимизация программ // Программирование. – 1990. – №1. – С.62–77. 18. Петрушенко А.Н. Диалоговая трансформационная машина и смешанные вычисления // Автоматика. Автоматизация. Электротехнические комплексы и системы. - 2000. - № 1 (6). - С. 91-97. 19. Петрушенко А.Н. Об одном подходе к проблеме автоматизации оптимизирующих преобразований алгоритмов и программ // Кибернетика и системный анализ. – 1991. – №5. – С. 127–137. 20. Басараб И.А., Никитченко Н.С., Редько В.Н. Композиционные базы данных. – Киев: Либiдь, 1992. – 191 с. 21. Петрушенко А.Н. Очерки по методологии научного познания: от математических к информационным моделям мира. – Киев: Наук. думка, 1998. – 128 с. 22. Петрушенко А.М. Діалогові системи та процеси: основні визначення та деякі властивості // Вестник Международного Соломонова университета. - 2004. – №1. – С. -. 23. Хоар Ч. Взаимодействующие последовательные процессы. – М.: Мир, 1989. – 264 с. 24. Скотт Д. Теория решеток, типы данных и семантика // Данные в языках программирования. - М.: Мир, 1982. – С. 25-73. 25. Брой М. Информатика. Основополагающее введение. В 4-х ч. / Пер. с нем. – М.: Диалог-МИФИ, 1996-1998. 26. Петрушенко А.Н. Понятие “алгоритм”: история возникновения и формирования // Вестник Херсонского государственного технического университета.. - 1998. - № 1 (3). - С.134-138.
id nasplib_isofts_kiev_ua-123456789-2280
institution Digital Library of Periodicals of National Academy of Sciences of Ukraine
issn 1727-4907
language Ukrainian
last_indexed 2025-11-28T22:40:11Z
publishDate 2004
publisher Інститут програмних систем НАН України
record_format dspace
spelling Петрушенко, А.М.
Хохлов, В.А.
2008-09-17T11:48:41Z
2008-09-17T11:48:41Z
2004
Концепція діалогових обчислень та деякі проблеми автоматизації програмування/А.М. Петрушенко, В.А. Хохлов // Проблеми програмування. — 2004. — N 2,3. — С. 37-46. бiблiогр.: 26 назв. - укр.
1727-4907
https://nasplib.isofts.kiev.ua/handle/123456789/2280
681.3
Розглядається концепція діалогових обчислень та наводяться деякі її раелізації в термінах алгебри алгоритміки, насамперед, уточнення основної задачі програмування. В термінах спеціального класу алгоритмів – діалогових адресних програм – дається уточнення поняття “методу програмування” та показується його зв’язок з концепцією змішаних обчислень і проблемою оптимізації програм. Пропонується одне із можливих визначень поняття “діалоговий процес”. Введені поняття демонструються на прикладах. Отримані в роботі результати знаходять реалізацію в діалоговій трансформаційній машині – інструментарії діалогових алгебро- граматичних методів представлення знань.
The conception of dialogue calculation is shown. The specification of idea “method of programming” is given. The definition of concept “dialogue process” is proposed. An introduced concepts are demonstreted by examples.
uk
Інститут програмних систем НАН України
Теоретические и методологические основы программирования
Концепція діалогових обчислень та деякі проблеми автоматизації програмування
Article
published earlier
spellingShingle Концепція діалогових обчислень та деякі проблеми автоматизації програмування
Петрушенко, А.М.
Хохлов, В.А.
Теоретические и методологические основы программирования
title Концепція діалогових обчислень та деякі проблеми автоматизації програмування
title_full Концепція діалогових обчислень та деякі проблеми автоматизації програмування
title_fullStr Концепція діалогових обчислень та деякі проблеми автоматизації програмування
title_full_unstemmed Концепція діалогових обчислень та деякі проблеми автоматизації програмування
title_short Концепція діалогових обчислень та деякі проблеми автоматизації програмування
title_sort концепція діалогових обчислень та деякі проблеми автоматизації програмування
topic Теоретические и методологические основы программирования
topic_facet Теоретические и методологические основы программирования
url https://nasplib.isofts.kiev.ua/handle/123456789/2280
work_keys_str_mv AT petrušenkoam koncepcíâdíalogovihobčislenʹtadeâkíproblemiavtomatizacííprogramuvannâ
AT hohlovva koncepcíâdíalogovihobčislenʹtadeâkíproblemiavtomatizacííprogramuvannâ

Ähnliche Einträge