Дослідження та створення інструментальних засобів автоматизованої трансформації схем алгоритмів
Запропоновано підхід до створення інструментальних засобів автоматизованої трансформації схем алгоритмів, який ґрунтується на
 застосуванні модифікованих систем алгоритмічних алгебр (САА-М). Розглянуто низку тотожніх перетворень під час трансформації та
 особливості інструментальної...
Збережено в:
| Дата: | 2004 |
|---|---|
| Автори: | , |
| Формат: | Стаття |
| Мова: | Українська |
| Опубліковано: |
Інститут програмних систем НАН України
2004
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/2294 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Дослідження та створення інструментальних засобів автоматизованої трансформації схем алгоритмів / С.Д. Погорілий, О.О. Камардіна // Проблеми програмування. — 2004. — N 2,3. — С. 417-421. — Бібліогр.: 8 назв. — укр. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860015349507817472 |
|---|---|
| author | Погорілий, С.Д. Камардіна, О.О. |
| author_facet | Погорілий, С.Д. Камардіна, О.О. |
| citation_txt | Дослідження та створення інструментальних засобів автоматизованої трансформації схем алгоритмів / С.Д. Погорілий, О.О. Камардіна // Проблеми програмування. — 2004. — N 2,3. — С. 417-421. — Бібліогр.: 8 назв. — укр. |
| collection | DSpace DC |
| description | Запропоновано підхід до створення інструментальних засобів автоматизованої трансформації схем алгоритмів, який ґрунтується на
застосуванні модифікованих систем алгоритмічних алгебр (САА-М). Розглянуто низку тотожніх перетворень під час трансформації та
особливості інструментальної системи. Наведено параметри програмної реалізації інструментальної системи мовою Perl та приклад її
роботи.
An approach to creation of instrumental means of automated algorithmic transformation, which is based on use of algorithmic algebras'
modified systems (SAA-M) is proposed. There were examined series of identical modifications during the transformation and peculiarities of
instrumental system as well. The parameters and examples of program realization were set for instrumental system using Perl programming language.
|
| first_indexed | 2025-12-07T16:44:38Z |
| format | Article |
| fulltext |
1
УДК 681.3
Дослідження та створення інструментальних засобів автоматизованої
трансформації схем алгоритмів
Погорілий С.Д., Камардіна О.О.
Київський національний університет імені Тараса Шевченка 01033, Київ, вулиця Володимирська, 64,
т. : (044)2660522, e-mail: sdp@rpd.univ.kiev.ua, olya@tviy.com.ua
Запропоновано підхід до створення інструментальних засобів автоматизованої трансформації схем алгоритмів, який ґрунтується на
застосуванні модифікованих систем алгоритмічних алгебр (САА-М). Розглянуто низку тотожніх перетворень під час трансформації та
особливості інструментальної системи. Наведено параметри програмної реалізації інструментальної системи мовою Perl та приклад її
роботи.
An approach to creation of instrumental means of automated algorithmic transformation, which is based on use of algorithmic algebras'
modified systems (SAA-M) is proposed. There were examined series of identical modifications during the transformation and peculiarities of
instrumental system as well. The parameters and examples of program realization were set for instrumental system using Perl programming language.
Етап алгоритмічного проектування програмного забезпечення [1] при проведенні кластерних обчислень є
вельми важливим та трудомістким. Створюваний алгоритм має передбачати ефективне використання ресурсів
кластера, забезпечувати хорошу масштабованість, тощо. Процес розробки паралельних алгоритмів можна
розбити на такі складові:
• декомпозиція (аналіз задачі, оцінка можливості її розпаралелювання, розбиття на підзадачі та
фрагменти структур даних);
• проектування обміну даними між задачами (визначення комунікацій необхідних для пересилання
вихідних даних та результатів виконання підзадач);
• об’єднання підзадач (згортка з метою виконування більш великих блоків, підвищення ефективності
алгоритму його трансформація та оптимізація);
• планування обчислень (розподіл задач між вузлами кластера з метою їх ефективного використання та
мінімізації накладних витрат часу на обмін даними).
Навіть поверхневий аналіз цих складових переконує у складності етапу алгоритмічного проектування, що
призводить до значної кількості трансформацій алгоритмів. З іншого боку дослідження тонкої інформаційної
структури програм передбачає формалізацію алгоритмів та подальше виконання низки їх тотожніх перетворень.
Для підвищення ефективності етапу алгоритмічного проектування доцільним є створення інструментальних
засобів для дослідження та автоматизованої трансформації схем алгоритмів [1].
Однією з першочергових задач, що постає при створенні інструментальних засобів автоматизованої
трансформації алгоритмів, є вибір математичного апарату, який би за своєю структурою був наближений до
об’єкту трансформації (програм, які написані алгоритмічними мовами).
Для формалізації пропонується застосування математичного апарату САА-М В.М. Глушкова, що є
різновидом систем алгоритмічних алгебр (САА). Цей математичний апарат було обрано з декількох причин:
• апарат САА-М у порівнянні з класичними алгоритмічними системами орієнтований на проектування
алгоритмів (та асоційованих з ними програм);
• будь-який алгоритм, записаний в САА-М, являє собою алгебраїчну формулу, що дозволяє
застосовувати до цього алгоритму систему достатньо розвинених в САА-М формальних трансформацій
з метою оптимізації і подальшого автоматизованого синтезу програмного забезпечення;
• САА-М знаходяться у відповідності з концепцією структурного програмування;
• наявність досвіду авторів трансформації послідовних схем алгоритмів протоколів маршрутизації [2].
Система оптимізації алгоритмів в САА-М
САА-М – це узагальнений апарат САА, орієнтований на формалізацію алгоритмів паралельної обробки
даних.
САА-М називають часткову алгебраїчну систему Z’=<A,B’> з фіксованою системою твірних, сигнатура
операцій якої містить узагальнені булеві операції, операцію лівого множення оператора на умову (призначена
для прогнозування обчислювального процесу), композицію, α-диз’юнкцію, α-ітерацію, α-фільтрації, синхронну
та асинхронну диз’юнкції. Крім того, до сигнатури входять спеціальні оператори та умови: невизначена умова,
невизначений оператор, що перериває обчислення, та оператор, який не виконує жодних дій. Слід зазначити,
2
що у САА-М можна визначити кілька похідних операцій, таких як обернена α-ітерація (цикл типу do-while) – її
можна отримати шляхом суперпозиції операцій композиції та циклу: {A}α = A * α{A}. Також як суперпозицію
композиції та циклу можна представити узагальнений цикл типу do-while-do: α{A [α] B} = A * α{B * A}. Такий
оператор реалізує вихід з циклу за умовою, що розміщена в середині циклу. Якщо А = Е, то отримаємо цикл
типу while-do: α{E [α] B} = α{B}, а якщо В = Е, то – цикл типу do-while: α{A [α] E} = {A}α,. що важливо при
конструюванні та трансформації алгоритмів. Саме можливість визначення похідних операцій та застосування
систем тотожних перетворень в САА-М є надзвичайно важливим засобом, оптимізації програм за певним
критерієм [3,4].
Метою процесу оптимізації є отримання на основі базового алгоритму одного або низки, оптимізованих
за певними критеріями.
Основними етапами процесу оптимізації алгоритму є:
• створення базового алгоритму. Основною вимогою до такого алгоритму є його безумовна
правильність, - оптимальність алгоритму на даному етапі не є обов’язковою;
• оптимізація алгоритму за обраними критеріями;
• тестування отриманих алгоритмів на певних вихідних даних з метою порівняння їх ефективності з
вихідним алгоритмом;
• оцінка ефективності отриманого алгоритму.
Створення базового алгоритму є необхідним у тому випадку, коли алгоритм для вирішення задачі ще не
створений. При створенні алгоритму виконуються наступні дії: по-перше, перераховуються та формалізуються
поняття, що використовуються при розв’язані задачі, по-друге, визначаються оператори та умови, які
застосовуються для побудови схеми, по-третє, створюється САА-М - схема розв’язання задачі з використанням
попередньо визначених умов та операторів для побудови базового алгоритму.
Оптимізація алгоритму здійснюється за допомогою розвинених засобів трансформації в САА-М. До
таких засобів належать комбінація згортки та розгортки, а також трансформації алгоритму.
Застосування цих засобів до алгоритму можливе завдяки тотожнім трансформаціям, які допомагають
спростити схему та надають можливість проводити поглиблену подальшу її трансформацію. Це особливо
важливо при створенні нових схем на базі вже існуючих. Поєднання цих засобів являє собою потужний
механізм для встановлення зв’язків між різноманітними алгоритмами, а також для конструювання нових
алгоритмів, більш ефективних за тими чи іншими критеріями.
Створення апарату тотожніх перетворень є необхідним для здійснення модифікації алгоритмів та
побудови інструментальних засобів автоматизованої трансформації схем алгоритмів.
Слід зазначити, що тотожні трансформації виконуються для будь-яких операторів чи умов, що входять до
них, тобто вони є незалежними від предметної області задачі. Характерним для тотожніх трансформацій є те,
що підвищення ефективності досягається шляхом уникнення повторних перевірок логічних умов (або зміни
порядку їх перевірки) які при виконанні алгоритму повинні виконуватися послідовно (тобто між такими
перевірками може виконуватися лише порожній оператор, що не змінює інформаційну множину).
Основні тотожності, щодо логічних операцій, які належать до сигнатури САА-М, стосуються
властивостей кон’юнкції, диз’юнкції, правил де Моргана, розподільчої властивості тощо. Рівності, що наведені
у таблиці 1, стосуються операторних конструкцій (А, В, С – оператори, символами "#...#" позначається частина
алгоритму, оператори якої повинні виконуватися паралельно, а символами "||" розділяються оператори, що
належать до паралельних гілок).
Таблиця 1
Властивості альтернативи
C * α(A, B) = C • α(C * A, C * B)
внесення оператора до альтернативи
(зліва)
α(A, B) * C = α (A * C, B * C)
внесення оператора до альтернативи
(справа)
α (A, B) = α * A || α * B розпаралелення альтернативи
Властивості циклу
α{A * B} = α{A} || α{B} розпаралелення
{A}α = A * α{A} перетворення циклів
α{A} = α{α * A} внесення фільтра в тіло циклу
α{A} = α || α * A * α{A}
розпаралелення з використанням
фільтра
α{A} = α{A} * α вставка фільтра
3
α{A} * α{B} = α{A}
перетворення двох циклів з
однаковими умовами
α ∨ β{A} = α{ β
* A} || β{α * A}
розпаралелення, якщо умова циклу –
диз’юнкція
α{ β * A} = α ∨ β{A} * α перетворення умови циклу
α ∨ β{B} * α{A} = α{# β * A || β * B#}
розпаралелення циклів зі схожими
умовами
α ∧ β{A} = α{A} * β || β{A} * α
розпаралелення, якщо умова циклу –
кон’юнкція
α ∧ β{A} = β{A} * α{A} розділення циклу
α * α{A} = α вилучення циклу
α * α{A * α } = α * A * α
вилучення циклу із вкладеним
фільтром
α{α * α ∧ β(A, B)} = α{α * β (A, B)} альтернатива, вкладена у цикл
α{A * β{B} * C} = α || α *A* β{B} *C* α{A * C} вкладені цикли
Загальні властивості
α * A * α = N фільтри з протилежними умовами
A * #B || C# = #A * B || A * C#
розподільча властивість паралельного
виконання
#A || B# * C = #A * C || B * C#
розподільча властивість паралельного
виконання
Процес застосування наведених тотожностей під час трансформації алгоритмів можливо автоматизувати
і тим самим виключити можливість припущення помилок, які можуть з’являються при ручній обробці великих
схем алгоритмів.
Створення інструментарію автоматизованої трансформації схем алгоритмів
Нижче розглянуто створений авторами інструментарій для автоматизованої трансформації
неінтерпретованих схем алгоритмів у САА-М. Інструментальна система, отримавши на вході деяку схему
алгоритму, має трансформувати її за деякою з вищенаведених тотожностей, та вивести як результат – нову
схему алгоритму. Для усіх наведених вище тотожностей було реалізоване їх автоматичне застосування.
Застосуванню будь-якої тотожності відносно деякої схеми алгоритму передує перевірка належності
символів, що знаходяться у лівій частині тотожності, цій схемі. Якщо таку відповідність встановлено, можна
проводити перетворення – замінити знайдений підрядок на символи, що знаходяться у правій частині
тотожності.
У даному випадку потрібно зробити зауваження: у лівій частині тотожності, як і у самій схемі,
знаходяться операторні та логічні змінні (схема алгоритму неінтерпретована). Оператори та предикати у схемі
можуть бути позначені будь-якими символами (не тільки х, у, А, В чи якимись іншими буквами або цифрами).
Тобто у схемі алгоритму потрібно знайти не просто таку, наприклад, послідовність символів: "{[α] А}".
Потрібно знайти вираз, який би задовольняв такому критерію: "{[...] …}", тобто мав певну структуру.
Таким чином, це означає, що ланцюжок символів "{[...] …}" повинен задавати кілька рядків, тобто деяку
мову. Іншими словами, перетворення схеми можливе лише тоді, коли у цій схемі можна буде виділити деякий
підрядок, який належатиме цій мові. В даному випадку алфавіт, на базі якого побудована вищезазначена мова,
складається з таких символів: символи англійського алфавіту у верхньому та нижньому регістрах, цифри,
дужки (круглі, квадратні, фігурні та кутові), символ "пробіл", символи "!", "+", ".", "*", ",", "@", "#" та "|". До
складу мови над таким алфавітом можуть належати ланцюжки будь-якої довжини, кожен з яких складається з
символів, що належать алфавіту. Над ланцюжками λ1 та λ2 символів визначено дві бінарні операції об’єднання
λ1Uλ2 та конкатенації λ1•λ2 та унарну операцію замикання Кліні λ1
* (ітерацію) [3].
Перед створенням інструментарію було розглянуто два методи пошуку зразків у тексті: метод пошуку з
використання автоматів та механізм регулярних виразів [4,5].
Регулярні вирази, як і автомати можуть застосовуватися для пошуку певних слів у тексті. Проте
перевагою регулярних виразів перед автоматами є те, що регулярні вирази можуть описувати нечітко визначені
шаблони для пошуку. Як приклад можна навести такий критерій відбору "{[...] …}", тобто кількість текстових
ланцюжків, що відповідають даному шаблону нескінчена. Таким чином, немає можливості чітко та однозначно
вказати послідовності символів, які потрібно шукати в тексті. Саме тому описати такі підрядки можна, тільки
описавши їхню структуру. А регулярні вирази – це простий та зручний механізм опису таких шаблонів.
4
Випливаючи зі сказаного видно, що регулярні вирази якнайкраще підходять для пошуку ланцюжка
символів, а саме для випадку пошуку тотожностей у схемі алгоритму, що записана в САА-М.
Реалізації інструментальної системи трансформації схем алгоритмів передує ретельний аналіз
алгоритмічної мови для її створення. Для вирішення задачі найкраще використати мову, яка б була
зорієнтована на обробку текстових даних та мала розвинений апарат опису регулярних виразів. Такою мовою є
Perl. Звичайно, існують мови, які мають широкий спектр функцій для роботи з рядками, наприклад, Java, C або
Pascal, але жодна з цих мов не має такого як у Perl розвиненого механізму роботи з регулярними виразами.
У таблиці 2 наведено приклад перетворення подвійного заперечення різними мовами С та Perl.
Таблиця 2
Мова C Мова Perl
for (int i=0; i<n-1; i++)
{ if ( str[i] == '!' &&
str[i+1] == '!')
{
str[i]=' ';
str[i+1]=' ';
}
}
$str =~ s%!!(\w+?)%$1%gx;
Навіть з наведеного простого прикладу видно, що код перетворення мовою С у кілька разів більший за
код перетворення мовою Perl. При програмуванні більш складних перетворень різниця у обсязі коду буде ще
помітніша. Така компактність Perl-програм досягається завдяки наявності у мові механізму регулярних виразів
та спеціальних операторів обробки текстової інформації.
Perl – мова, що інтерпретується (хоча компілятори Perl теж існують). Вона призначена для сканування
текстових файлів, отримання з них певної інформації та виводу текстових звітів на основі отриманих даних.
Незважаючи на те, що мова Perl зорієнтована на текстове введення-виведення інформації та запускається з
командного рядка, вона залишається мовою, що широко застосовується. Цьому є кілька причин. Мабуть
найголовнішим є те, що мова Perl являє собою мову, що не залежить від платформи, тому при перенесенні
інструментальної системи між різними операційними системами виправленню (якщо воно потрібне) підлягають
тільки деякі деталі [6,7,8].
Створена інструментальна система реалізована мовою Perl. Обсяг її складає біля 1000 рядків вихідного
тексту. Тестування інструментальної системи виконано на таких програмних платформах: операційні системи
UNIX (FreeBSD 5.1) та Windows XP.
Нижче наведено приклад роботи інструментальної системи, якій на вхід подається неінтерпретована
схема алгоритму лівого обходу бінарного дерева.
Вхідну інформацію інструментальна система отримує з файла на диску. При запуску програми не
потрібно вказувати ім’я цього файлу, користувач вибирає його вже під час виконання програми. Не обов’язково
навіть готувати такий файл заздалегідь: він може бути створений під час виконання програми.
Приклад
File list:
examp1 examp2
1 - Edit file
2 - Wieving file
3 - Choose file
q - Exit \n"
Choose something:
3
Enter the name of file:
exampl1
1 - Transformations of conditions
2 - Transformations of alternatives
3 - Transformations of cycles
4 - General transformations
q - Return in main menu
Choose something:
3
1 - Devide on the branches (rasparallelivanie)
2 - Do-while ==> while-do
3 - {[u] A} ==> {[u] <!u> * A}
5
4 - {[u] A} ==> <u> || <!u> * A * {[u] A}
5 - {[u] A} ==> {[u] A} * <u>
6 - {[u] A} * {[u] B} ==> {[u] A}
7 - {[u1+u2] A} ==> {[u1] <!u2> * A} || {[u2] <!u1> * A}
8 - {[u1] <!u2> * A} ==> {[u1+u2] A} * <u1>
9 - {[u1+u2] B}*{[u1] A} ==> {[u1] #<u2> * A||<!u2> * B#}
10 - {[u1.u2] A} ==> {[u1] A} * <u2> || {[u2] A} * <u1>
11 - {[u1.u2] A} ==> {[u2] A} * {[u1] A}
12 - <u> * {[u] A} == <u>
13 - <!u> * {[u] A * <u>} ==> <!u> * A * <u>
14 - {[u] <!u>*([!u.u1] A, B)} ==> {[u] <!u>*([u1] A, B)}
15 - {[u1] A * {[u2] B} * C} ==> <u1> || <!u1> * A * {[u2] B} * C * {[u1] A * C}
t - Rechoose kind of transformation
q - Return to main menu
Choose something:
1
The initial algoritm:
A * ([u1.u2] ([u3] B, {[u4.u1] ([u5] C * ([u6] D, ([!u5] F, G)))})
Transformed algoritm:
A * ([u1.u2] ([u3] B, #{[u4.u1] ([u5] C} || {[u4.u1] ([u6] D, ([!u5] F, G)))}#)
Press Enter to continue
Висновки
В результаті виконання роботи
• обгрунтовано доцільність створення інструментальних засобів автоматизованої трансформації схем
алгоритмів, які орієнтовані на застосування математичного апарату САА-М;
• визначено групу основних тотожностей щодо логічних операцій та групу рівностей для операторних
конструкцій як базис проведення трансформацій схем алгоритмів;
• виконано аналіз методів пошуку зразків у тексті та обгрунтовано ефективність застосування
регулярних виразів для знаходження тотожностей для подальших трансформацій;
• проведено порівняльний аналіз мовних засобів та обгрунтовано застосування мови програмування Perl
для реалізації інструментальної системи. Наведено параметри реалізації цієї системи для різних
програмних платформ та приклад її роботи.
Література
1. Погорелый С.Д. К формализации этапа алгоритмического проектирования микропроцесорних систем. -
К.: журнал УСиМ, № 6, 1995. стор. 3 – 8.
2. Погорілий С. Д. Автоматизація наукових досліджень. Основоположні математичні відомості. Програмне
забезпечення. За редакцією академіка АПН України Третяка О.В. – К.: Видавничо-поліграфічний центр
"Київський університет", 2002. – 288 с.
3. Хопкрофт Д., Мотвани Р., Ульман Д. Введение в теорию автоматов, языков и вычислений. – М.:
Издательский дом "Вильямс", 2002. – 528 с.
4. Ющенко К. Л., Суржко С. В., Цейтлін Г. О., Шевченко А. І. Алгоритмічні алгебри: Навчальний посібник.
– К.: ІЗМН, 1997. – 480 с.
5. Цейтлин Г. Е. Введение в алгортмику. – К.: Сфера, 1998. – 312 с.
6. Холзнер С. Perl: Специальный справочник. – СПб.: Питер, 2000. – 496 с.
7. citforum.univ.kiev.ua
8. www.perl.ru
|
| id | nasplib_isofts_kiev_ua-123456789-2294 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1727-4907 |
| language | Ukrainian |
| last_indexed | 2025-12-07T16:44:38Z |
| publishDate | 2004 |
| publisher | Інститут програмних систем НАН України |
| record_format | dspace |
| spelling | Погорілий, С.Д. Камардіна, О.О. 2008-09-17T12:18:31Z 2008-09-17T12:18:31Z 2004 Дослідження та створення інструментальних засобів автоматизованої трансформації схем алгоритмів / С.Д. Погорілий, О.О. Камардіна // Проблеми програмування. — 2004. — N 2,3. — С. 417-421. — Бібліогр.: 8 назв. — укр. 1727-4907 https://nasplib.isofts.kiev.ua/handle/123456789/2294 681.3 Запропоновано підхід до створення інструментальних засобів автоматизованої трансформації схем алгоритмів, який ґрунтується на
 застосуванні модифікованих систем алгоритмічних алгебр (САА-М). Розглянуто низку тотожніх перетворень під час трансформації та
 особливості інструментальної системи. Наведено параметри програмної реалізації інструментальної системи мовою Perl та приклад її
 роботи. An approach to creation of instrumental means of automated algorithmic transformation, which is based on use of algorithmic algebras'
 modified systems (SAA-M) is proposed. There were examined series of identical modifications during the transformation and peculiarities of
 instrumental system as well. The parameters and examples of program realization were set for instrumental system using Perl programming language. 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/2294 |
| work_keys_str_mv | AT pogoríliisd doslídžennâtastvorennâínstrumentalʹnihzasobívavtomatizovanoítransformacííshemalgoritmív AT kamardínaoo doslídžennâtastvorennâínstrumentalʹnihzasobívavtomatizovanoítransformacííshemalgoritmív |