імені Тараса Шевченка

Яценко Олена Анатоліївна

УДК 681.3.06

розробка інтегрованих алгебро-алгоритмічних моделей:

елементи теоріЇ, інструментарій, ЗАСТОСУВАННя

01.05.03 математичне та програмне забезпечення

обчислювальних машин і систем

Автореферат

дисертації на здобуття наукового ступеня

кандидата фізико-математичних наук

Київ – 2005

Дисертацією є рукопис

Робота виконана в Інституті програмних систем

Національної академії наук України, м. Київ.

Науковий керівник:

доктор технічних наук, професор

Цейтлін Георгій Овсійович

Міжнародний Соломонів університет, м. Київ,

завідувач кафедри

Офіційні опоненти:

доктор фізико-математичних наук, старший науковий

співробітник Буй Дмитро Борисович,

Київський національний університет

імені Тараса Шевченка, м. Київ, завідувач лабораторії

проблем програмування

кандидат фізико-математичних наук, старший науковий

співробітник Гороховський Семен Самуїлович,

Національний університет “Києво-Могилянська академія”,

м. Київ, доцент

Провідна установа: Інститут кібернетики НАН України, м. Київ,

відділ автоматизації програмування

Захист відбудеться 16 червня 2005 року о 14 годині на засіданні

спеціалізованої вченої ради Д .001.09 Київського національного

університету імені Тараса Шевченка за адресою:

03127, м. Київ-127, проспект Акад. Глушкова 2, корпус 6,

Київський національний університет імені Тараса Шевченка,

факультет кібернетики, ауд. 40. Тел. 259-04-24.

З дисертацією можна ознайомитися в бібліотеці Київського

національного університету імені Тараса Шевченка (вул. Володимирська 58).

Автореферат розісланий 11 травня 2005 року.

Вчений секретар

спеціалізованої вченої ради

кандидат фізико-математичних наук, доцент В.П. Шевченко

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

Актуальність теми. Важливою проблемою сучасного програмування є його математизація, розробка формалізованих мов проектування алгоритмів і програм, а також їх абстрактних моделей. Засоби проектування, аналізу і реалізації алгоритмів є особливо актуальними у зв’язку з важливими процесами комп’ютеризації й автоматизації діяльності суспільства. До таких засобів, зокрема, відносяться алгебри алгоритмів, орієнтовані на вирішення проблем формалізації, обґрунтування правильності, покращення алгоритмів (за обраними критеріями). Значний внесок у розробку алгебри алгоритмів був здійснений фундаментальними працями В.М. Глушкова з автоматизації програмування і проектування логічних структур ЕОМ, що були опубліковані в 60_х – х роках. У руслі вказаних праць Глушковим та його учнями була побудована теорія систем алгоритмічних алгебр (САА). Саме від концепції САА і бере свій початок алгебра алгоритміки – перспективний напрямок, що розвивається у рамках української алгебро-кібернетичної школи. Згадана алгебра займає власну нішу в області алгебраїчної алгоритміки, яка в останній час отримала поширення на Заході. Алгебра алгоритміки створює важливі теоретичні підвалини для розвитку суміжних досліджень, зокрема, що стосуються параметричних систем програмування та програмології, діалогових систем, повторного використання компонент, моделей предметних областей, баз даних та знань, паралельних обчислень. Використання теорії САА та алгебри алгоритміки в роботах К.Л. Ющенко, А.В. Анісімова, А.Ю. Дорошенка, Ю.В. Капітонової, О.А. Летичевського, К.М. Лавріщевої, О.Л. Перевозчикової, В.Н. Редька, Г.О. Цейтліна та інших вчених дозволило зробити суттєвий вклад у розвиток теорії і технології програмування.

Задачі побудови ефективних моделей і методів як послідовної, так і паралельної обробки займають одне із центральних місць у алгебрі алгоритміки. Так, важливою залишається проблема адаптивності формальних специфікацій алгоритмів та програм до конкретних умов їх використання. Зокрема вона може бути вирішена за рахунок параметризації згаданих специфікацій. Це робить надзвичайно актуальним подальший розвиток інтегрованих алгебро-алгоритмічних моделей програм, які сполучають алгебру алгоритміки з теорією формальних граматик. Таким чином побудовані моделі дозволяють створити інструментальні засоби проектування та синтезу послідовних і паралельних програм.

Розвиток об’єктно-орієнтованих (ОО) технологій вимагає нових підходів до інструментальних засобів програмування, з’явилися ефективні мови проектування і засоби генерації програм в ОО середовищах, зокрема, уніфікована мова моделювання UML (Unified Modeling Language) та її інструментарій. Тому актуальним при розробці програм є поєднання інструментарію, що ґрунтується на алгебрі алгоритміки, із засобами мови UML.

Розроблені в дисертації інструментальні засоби поєднують потужні можливості візуалізації алгоритмів, які застосовує UML, з притаманним алгебрі алгоритміки описом алгоритмів у аналітичній формі, яка дозволяє здійснювати формальні перетворення алгоритмів з метою їх покращення. Побудовані моделі, реалізовані у інструментарії, забезпечують адаптивність розроблюваних алгоритмів за рахунок їх параметрично керованої генерації. Важливість створення формальних моделей і практичних методик реалізації алгоритмів для розвитку сучасного теоретичного і прикладного програмування і визначає актуальність даної роботи.

Зв’язок з науковими програмами, планами, темами. Робота виконана у рамках державної бюджетної теми Інституту програмних систем НАН України “Розробка теорії та методів програмування високопродуктивної обробки в метакомп’ютерних системах на основі координаційних моделей обчислень” (2002–2006 рр., № ДР 0102U005995, шифр теми 3/02–02), а також у рамках досліджень, що проводяться на кафедрі програмного забезпечення автоматизованих систем Міжнародного Соломонова університету.

Мета і задачі дослідження. Мета даної роботи полягає в:

розробці інтегрованих алгебро-алгоритмічних моделей програм для розв’язання задач символьної мультиобробки (паралельні сортування, пошук, мовне процесування та ін.);

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

налагодженні запропонованого інструментарію на синтез програм у сучасних ОО середовищах із використанням засобів візуалізованого проектування ОО програм.

Об’єктом дослідження є алгебраїчні (схемні) моделі та засоби проектування алгоритмів і програм.

Предметом дослідження є алгебро-алгоритмічний підхід до побудови специфікацій та синтезу програм в ОО середовищах.

При розробці моделей алгоритмів та відповідного інструментарію використані методи сучасної загальної алгебри, теорії формальних граматик і мов, теорії автоматів (скінченних і нескінченних), алгоритмічної алгебри.

У відповідності до поставленої мети визначено такі основні задачі дослідження:

Побудувати високорівневі моделі послідовних та паралельних алгоритмів на основі поєднання засобів алгебри алгоритміки, формальних граматик і апарату параметричного керування виведенням.

Застосувати розроблені моделі для розв’язання задач символьної мультиобробки.

Розробити інструментарій синтезу програм, а також параметрично керованої генерації регулярних схем на основі зазначених моделей. Забезпечити генерацію програм у ОО середовищах із використанням інструментів візуалізованого проектування програм.

Апробувати інструментарій при створенні конкретних програмних продуктів символьної мультиобробки в ОО середовищах.

Наукова новизна одержаних результатів. При виконанні роботи отримані такі нові наукові результати:

Вперше побудовано розподілені інтегровані алгебро-алгоритмічні моделі, які призначені для проектування та синтезу класів як послідовних, так і паралельних алгоритмів та програм. Згадані моделі є подальшим розвитком теорії алгоритміки.

Отримані розподілені інтегровані моделі застосовано для розв’язання задач символьної мультиобробки. Побудовано моделі паралельних алгоритмів багатошарового човникового сортування, послідовних і паралельних адресного сортування і пошуку.

Запропоновано підхід до створення середовища конструювання алгоритмічних знань символьної мультиобробки, який ґрунтується на концепції алгебри алгоритміки.

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

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

Практичне значення одержаних результатів. Результати дисертації застосовуються в навчальному процесі на кафедрі програмного забезпечення автоматизованих систем Міжнародного Соломонова університету у курсі “Теорія алгоритмів і обчислювальних процесів”, а також при розробці інтегрованого інструментарію діалогового конструювання та синтезу синтаксично правильних послідовних і паралельних програм. Інструментарій забезпечує синтез програм у сучасних ОО середовищах програмування (Java, C++) із використанням засобів візуалізованого проектування програм (мови UML і системи Rational Rose). Інструментарій також призначено для потреб навчального процесу.

Особистий внесок здобувача. Усі результати, викладені в дисертації, отримані автором самостійно. У спільно виконаній роботі [1] науковому керівникові Г.О. Цейтліну належить постановка задач і пропозиції щодо методів їх розв’язання. У роботі [5] О.С. Мохниці належить розробка інструментарію діалогової трансформації та редагування граф-схем алгоритмів.

Апробація результатів дисертації. Результати роботи доповідалися на Міжнародних науково-практичних конференціях з програмування УкрПРОГ’2002 та УкрПРОГ’2004 (м. Київ), Міжнародній конференції “Теоретичні та прикладні аспекти побудови програмних систем” TAAPSD’2004 (м. Київ), на наукових семінарах Інституту програмних систем НАН України, Інституту кібернетики НАН України, Київського національного університету імені Тараса Шевченка.

Публікації. За темою дисертації опубліковано 6 робіт, з яких 3 є статтями у фахових періодичних виданнях, затверджених ВАК, 3 є доповідями на міжнародних наукових конференціях.

Структура і обсяг дисертації. Дисертація складається із вступу, 4 розділів, висновків, списку використаної літератури із 119 найменувань і одного додатку. Загальний обсяг дисертації становить 163 сторінки, з них 141 сторінка основного тексту. Текст дисертації містить 21 рисунок і 4 таблиці.

ОСНОВНИЙ ЗМІСТ РОБОТИ

У Вступі обґрунтовується актуальність теми дисертації, формулюються мета і задачі дослідження, вказані застосовані методи дослідження, визначаються наукова новизна і практична цінність отриманих результатів, наводяться дані стосовно апробації роботи і публікацій.

Перший розділ містить огляд літератури, що стосується сучасного стану досліджень у рамках алгебри алгоритміки. Особливу увагу приділено засобам побудови сімейств алгоритмічних алгебр – клонам, а також результатам, що стосуються абстрактно-автоматних моделей кібернетичних систем (дискретних перетворювачів). Розглядається проектування предметних областей, алгебро-алгоритмічні моделі та інструментальні засоби алгебри алгоритміки.

Об’єктом дослідження в алгебрі алгоритміки є високорівневі моделі алгоритмів, подані у вигляді схем. До таких моделей відносяться зокрема граф-схеми Калужніна і САА Глушкова. САА було покладено в основу структурної схематології – теорії структурованих схем і пов’язаних з нею інструментальних засобів генерації програм. Модифіковані САА (САА-М) призначені для формалізованого проектування структурованих алгоритмів, як послідовних, так і паралельних. Суперпозиції операцій, що входять у сигнатуру САА і САА-М, називаються регулярними схемами (РС). Подання алгоритмів в САА_М, які специфікують асинхронні операторні взаємодії, називаються паралельними регулярними схемами (ПРС).

Алгебра алгоритміки є дворівневою системою: в основу верхнього рівня покладено теорію клонів; на нижньому (інтерпретаційному) рівні здійснюється побудова прикладної алгебри, призначеної для подання алгоритмічних знань про обрану предметну область. Проектування схем алгоритмів ґрунтується на концепції граматик структурного проектування.

Граматика структурного проектування (ГСП) є формальною системою GT, N, , P, D), де T – термінальний алфавіт (базисні умови, оператори, об’єкти, роздільники); N – нетермінальний алфавіт (логічні, операторні, об’єктні метазмінні);   N – аксіома граматики; P {ui  vi| і , , …, k} – скінченна система продукцій логічного, операторного та об’єктного типів, що подані в САА-М і застосовуються при проектуванні алгоритмів; D – механізм керування виведенням у ГСП G.

Гіперсхеми є різновидом ГСП із розвинутими засобами керування виведенням.

Алгебра гіперсхем (АГС) є двоосновною алгеброю U, B; >, де U і B – множини операторів і умов, заданих на інформаційній множині (ІМ) P, асоційованій з параметрами, які керують генерацією (породженням) схем; – сигнатура, аналогічна сигнатурі САА. Застосування оператора A  U до стану p  P приводить до переходу ІМ у новий стан A(p)  P і генерації деякого фрагмента F(A, p) тексту РС. Операторні подання у АГС називаються гіперсхемами. Модифікована АГС із розширеною сигнатурою операцій призначена для генерації РС і ПРС у САА-М. Параметризація гіперсхем підвищує степінь адаптивності генерованих схем алгоритмів до умов їх використання.

ГСП і гіперсхеми будемо називати інтегрованими алгебро-алгоритмічними моделями. Згадані моделі інтегрують у собі апарат алгебр алгоритмів із теорією формальних граматик. Актуальним є застосування інтегрованих моделей для паралельних обчислень, зокрема для задач із області символьної мультиобробки.

На початку 80-х років апарат структурної схематології був покладений в основу реалізованого інструментарію Мультипроцесист, створеного у відділі автоматизації програмування Інституту кібернетики ім. В.М. Глушкова, що на протязі багатьох років очолювався член-кор. НАНУ, проф. К.Л. Ющенко. Згадана система ґрунтується на методі багаторівневого структурного проектування програм (БСПП) і є синтезатором програм за їх багаторівневими проектами – САА-схемами, оформленими у природно-лінгвістичному вигляді (наприклад, українською або російською мовами). У даний час усе більше значення набуває ОО проектування із використанням уніфікованої мови моделювання UML. Інструментарій UML, як і засоби алгебри алгоритміки, не залежить від конкретної мови програмування і може використовуватися для автоматизованої генерації текстів програм. Тому при проектуванні та реалізації програм актуальним є поєднання UML із засобами, що ґрунтуються на алгебрі алгоритміки.

Другий розділ присвячено результатам, отриманим у рамках створення інтегрованих алгебро-алгоритмічних моделей символьної мультиобробки. Запропоновано концепцію середовища конструювання алгоритмічних знань мультиобробки (СКЗ) [1]. Розглядаються розроблені паралельні алгоритми, що входять до складу згаданого СКЗ та отримано оригінальні оцінки їх обчислювальної складності.

У підрозділі 2.1 розроблено ГСП і розподілені гіперсхеми, призначені для проектування класів паралельних алгоритмів [2, 6].

Розглянемо клас асинхронних ПРС П(n) розподіленої кишенькової обробки, які складаються з n незалежних паралельних гілок (процесів) A(i) (i , , …, n). Згаданий клас складають схеми: П(1), П(2), …, П(n). ПРС П(n) здійснює обробку послідовності даних D, озділеної на n частин di: де Н і К – маркери, що відмічають початок і кінець послідовності D відповідно. Гілка A(i) реалізує обробку фрагмента di послідовності D, розміщеного у i-й кишені. Схеми П(n) визначаються таким чином: П(n) А(1)  А(2)  …   А(n). В [6] побудовано ГСП G0T0, N0, 0, P0, D0), призначену для проектування алгоритмів із цього класу. У наведених нижче продукціях граматики G0 використовується параметричний запис, який забезпечує нарощування гілок A(i) шляхом зміни параметра i від 1 до n – :

p0: 0 ПРС0;

p1: ПРС0 A(1);

p2: ПРС0 A(1) ПРС0;

p3: A(i) ПРС0 A(i) A(i + 1) ПРС0, i , 2, …, n – ;

p4: A(i) ПРС0 A(i) A(i + 1), i , 2, …, n – .

Тут 0  N0, ПРС0  N0 – аксіома і операторна метазмінна ГСП G0 відповідно; A(i)  T0 – оператор, який здійснює обробку даних у і-й гілці.

Породження регулярної схеми алгоритму за ГСП у рамках обраної стратегії виведення пов’язане із певним порядком застосування продукцій. Цей порядок визначається алгоритмом керування виведенням, поданим у алгебрі гіперсхем.

Визначення 2.1. Подання операторів в модифікованій АГС U, B; > за допомогою суперпозиції операцій з її сигнатури і твірних елементів (базисних операторів і умов) будемо називати розподіленими гіперсхемами (РГС). Кожна РГС A, впливаючи на поточний стан ІМ p  P, породжує ПРС F(A, p)].

Визначення 2.2. Багаторівневі структури в модифікованій АГС будемо називати багаторівневими РГС (БРГС).

Поняття РГС введено у даній роботі у зв’язку із розглядом асинхронних обчислень, на які орієнтована модифікована АГС. Згадана АГС пов’язана із абстрактно-автоматною моделлю параметрично керованого генератора схем. У випадку асинхронної обробки паралельні гілки РГС розподілені по мережі керуючих автоматів згаданої моделі.

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

За ГСП G0 побудовано БРГС R0, яка є алгоритмом керування виведенням у цій граматиці]:

R0i := 0) * (n := 5) * ПРС0,

ПРС0 ІНК(i) * ВИБІР([(i > 0) (i < n)] ()(А(i), ПРС0), [i n] А(i)).

де (i ) – оператор присвоювання параметру i значення 0; ІНК(i) – додавання одиниці до параметра . З побудови виводів ПРС за РГС R0 при конкретних значеннях параметра випливає

Лема 2.1. Розподілена гіперсхема R0 породжує ПРС алгоритмів, які належать до класу ПРС П(n) кишенькової обробки при n > 0[6].

У результаті відповідної інтерпретації гілок А(i) схеми П(n) можуть бути отримані алгоритми, призначені для розв’язання конкретних задач символьної мультиобробки (сортування, пошуку та ін.).

Для проектування ПРС алгоритмів використані також метаправила конструювання (згортка, розгортка, переорієнтація), які дозволяють укрупнити процес проектування і зробити його більш гнучким. Згортка є заміною операторних і предикатних інтерпретацій схеми на відповідні змінні. Розгортка є заміною змінних схеми на відповідні інтерпретації. Переорієнтація полягає в послідовному застосуванні метаправил згортки і розгортки. У роботі продемонстровано перехід від одних алгоритмів класу П(n) до інших із застосуванням побудованих систем рівностей I1, I2, I3, I4.

Лема 2.2. Для побудови ПРС П(n) нарівні з РГС R0 застосовні метаправила конструювання схем: згортка, розгортка, переорієнтація, які базуються на системах рівностей типу I1, I2, I3, I4.

Отримані результати використано у даному підрозділі, а також у підрозділі .2, для побудови ГСП G1, G2 і відповідних їм РГС R1 і R2, що призначені для породження класів паралельних алгоритмів сортування.

Розглянемо клас ПРС багатошарових алгоритмів човникового сортування ЧОВНИК_П(n) [2, ]. Суть багатошарової обробки полягає в поділі масиву вхідних даних М на n підмасивів для одночасної обробки паралельними гілками з наступним збиранням отриманих проміжних результатів . Згаданий клас складають схеми: ЧОВНИК_П(2), …,ЧОВНИК_П(n). Побудовано матричну ГСП G1T1, N1, 1, P1, D1), призначену для проектування алгоритмів із зазначеного класу. ГСП G1 складається з двох підграматик G11 і G12: . ГСП G11 призначена для проектування загальної схеми човникового сортування, а ГСП G12 – алгоритмів злиття упорядкованих підмасивів Li. За граматикою G1 отримано РГС R1. З побудови виводів ПРС за РГС R1 при конкретних значеннях параметра n, а також із леми 2.1 випливає

Теорема 2.1. Розподілена гіперсхема R1 породжує ПРС алгоритмів, які належать до класу ПРС багатошарового човникового сортування ЧОВНИК_П(n) при n > 1.

Із леми 2.2 випливає, що нарівні із РГС R1 для побудови алгоритмів ЧОВНИК_П(n) застосовні метаправила конструювання схем.

У підрозділі 2.2 застосовано апарат алгебри алгоритміки та розподілених гіперсхем для подання і розпаралелення відомого методу адресного сортування і пошуку [3, 6]. Розроблена РС алгоритму адресного сортування АДРСОРТ_П(М0, М, n) полягає в паралельному обчисленні для кожного з елементів вхідного масиву М0 його адреси у вихідному масиві М. Отриманий паралельний алгоритм має асимптотичну часову складність O(n), тоді як послідовний мав . Результатом адресного сортування, окрім вихідного масиву М, є масив Мі індексів елементів масиву М у вхідному масиві М0. Масив Мі використовується у побудованій РС алгоритму адресного пошуку заданого числа у масиві (РС ПОШУК-А).

Розглянемо клас паралельних алгоритмів адресного сортування, який складають такі ПРС: АДРСОРТ_П(М0, М, ), АДРСОРТ_П(М0, М, ), …, АДРСОРТ_П(М0, М, n). В [6] побудовано ГСП G2T2, N2, 2, P2, D2) і алгоритм керування виведенням – РГС R2, що призначені для проектування алгоритмів із зазначеного класу. При цьому використані результати, отримані у підрозділі 2.1 (леми 2.1, 2.2). З побудови виводу ПРС за РГС R2 при конкретних значеннях параметра n та леми 2.1 випливає

Теорема 2.2. Розподілена гіперсхема R2 породжує ПРС алгоритмів, які належать до класу ПРС адресного сортування АДРСОРТ_П(М0, М, n) при n > 0 [6].

Із леми 2.2 випливає, що нарівні з гіперсхемою для побудови алгоритмів АДРСОРТ_П(М0, М, n) застосовні метаправила конструювання схем.

У підрозділі 2.3 запропоновано концепцію середовища конструювання алгоритмічних знань, яке ґрунтується на понятті алгебри алгоритміки та призначене для розв’язання задач послідовної і паралельної символьної обробки [1]. СКЗ складається із компонентів, призначених для конструювання схем алгоритмів та синтезу програм. У ньому спільно використовуються три форми подання алгоритмів при їх проектуванні: аналітична (формула в алгебрі алгоритмів), природно-лінгвістична (САА-схема) і графова (граф-схеми Калужніна). Компонентами СКЗ є: 1) стратегії обробки (РС, які описують класи алгоритмів). До них відносяться: операції САА-М, опис яких у СКЗ включає їх подання у трьох зазначених вище формах, а також відображення у цільову мову програмування; частково інтерпретовані схеми (що містять змінні та базисні предикати і оператори) і неінтерпретовані схеми (не містять базисних елементів); 2) метаправила конструювання схем алгоритмів, які забезпечують породження нових знань (абстрагування, деталізацію і переорієнтацію схем); 3) базисні предикати і оператори, подані у трьох формах, а також їх програмні реалізації; 4) схеми алгоритмів символьної обробки; 5) розподілені гіперсхеми (див. підрозділ 2.1).

Далі у підрозділі розглянуто розроблені паралельні алгоритми сортування масивів і пошуку у файлах, які входять до складу СКЗ, розробленого за сформульованою концепцією. Для оцінки асимптотичної часової складності T(n) алгоритмів сортування обчислено C(n) – кількість необхідних операцій порівняння елементів масиву; а для пошуку – кількість C(n) операцій порівняння поточного запису файлу із запитом; де n – довжина масиву або файлу відповідно]. Для оцінки алгоритмів сортування у роботі обчислюється також кількість M(n) переміщень елементів масиву. Отримані результати відображено у теоремах 2.3–2.5.

Бульбашковий БС-М, альтернативний САВ/А, човниковий ЧОВНИК-2 алгоритми сортування (2 паралельні гілки) і узагальнене човникове ЧОВНИК_П(m) сортування (m гілок):

Теорема 2.3. Справедливі наступні твердження: 1) для алгоритму БС-М ; 2) для алгоритму САВ/А ; 3) для алгоритму ЧОВНИК-2 ; 4) для алгоритму ЧОВНИК_П(m)

Наслідок. Асимптотична часова складність T(n) алгоритмів БС-М, САВ/А, ЧОВНИК-2, ЧОВНИК_П становить .

Бульбашковий БП/П і БП_/П, човниковий ЧП/П, альтернативний АП/П, бінарний БінП/П алгоритми пошуку у файлі (s паралельних гілок):

Теорема 2.4. Справедливі наступні твердження: 1) для алгоритму БП/П C(n)  n; 2) для алгоритму БП_/П C(n) n; 3) для алгоритму ЧП/П C(n)  n ; 4) для алгоритму АП/П C(n)  n/2; 5) для алгоритму БінП/П C(n) .

Наслідок. Асимптотична часова складність T(n) алгоритмів БП/П, БП_/П, ЧП/П, АП/П становить O(n), а алгоритму БінП/П – .

Адресне сортування і пошук у масиві (n паралельних гілок):

Теорема 2.5. Асимптотична часова складність T(n) алгоритмів АДРСОРТ_П(М0, М, n) і ПОШУК-A становить O(n) і відповідно [6].

Здійснено порівняння розроблених у роботі паралельних алгоритмів із їх попередніми послідовними варіантами. Беручи до уваги коефіцієнти при , для паралельного алгоритму БС-М максимальна кількість операцій порівняння і максимальна кількість переміщень менші, ніж для послідовного алгоритму, у 1.6 і 2 рази відповідно; в алгоритмі ЧОВНИК-2 – в 1.33 рази; в алгоритмі АДРСОРТ_П(М0, М, n) – в n разів; у сортуванні САВ/А на n – менше, ніж у послідовному, а в 2 рази; для алгоритму ЧОВНИК_П менше в  разів, ніж для послідовного сортування (при ), а – в  разів (при m ). Алгоритми паралельного пошуку, згадані у теоремі 2.4, потребують у найкращому випадку приблизно в s разів менше операцій порівняння за послідовні, де s – кількість паралельно оброблюваних запитів.

У третьому розділі розроблено інтегрований інструментарій проектування та синтезу алгоритмів і програм на основі алгебро-алгоритмічних моделей, побудованих у розділі . Інструментарій використовує метод діалогового конструювання синтаксично правильних програм (ДСП-метод), який орієнтовано не на пошук і виправлення помилок (як у традиційних синтаксичних аналізаторах), а на виключення можливості їх появи в процесі побудови алгоритмів [4, ]. В інструментарії виконується побудова синтаксично правильних САА-схем алгоритмів і синтез відповідних програм у сучасних ОО середовищах програмування (Java, C++ та ін.). Особливість створеного інструментарію полягає в інтеграції згаданих у підрозділі 2.3 форм подання алгоритмів: аналітичного, природно-лінгвістичного і графового при їх проектуванні. У розділі розглянуто також одне із важливих прикладних застосувань алгебри алгоритміки – розробка інструментарію підтримки навчання в учбових структурах комп’ютерної орієнтації.

Підрозділ 3.1 присвячено огляду багатопоточних засобів мов програмування (threads), які використовуються для синтезу паралельних програм у інтегрованому інструментарії. Розглянуто також технологію MPІ, призначену для програмування паралельної обробки для обчислювальних систем із розподіленою пам’яттю.

У підрозділі 3.2 наведено пояснення доцільності інтегрованого використання інструментарію алгебри алгоритміки і засобів ОО проектування (діаграм мови UML) та описані стратегії подібної інтеграції [5]. Результатом моделювання в Rational Rose обраної предметної області із використанням діаграм класів є згенерований “каркас” програмного продукту мовою програмування (який не містить реалізацій методів). Далі для проектування і синтезу методів класів може бути використаний розроблений у даному розділі інтегрований інструментарій. Доповнювальним до викладеного підходу є використання інтегрованого інструментарію на початкових етапах проектування з подальшим використанням діаграм UML і переходом до ОО програм. Таким чином, мова йде про взаємодоповнюючі стратегії проектування ОО програм: “зверху-вниз” і “знизу-вверх”, а також про їх комбіноване застосування. Відмітимо також, що діаграми UML, доповнені граф-схемами алгоритмів, істотно збагачують засоби візуального проектування при реалізації програмних модулів.

У підрозділі 3.3 розглянуто архітектуру розробленого інтегрованого інструментарію (рис. ). ДСП-конструктор призначений для діалогового конструювання послідовних і паралельних САА-схем алгоритмів та синтезу відповідних програм. У блоці трансформатора виконується діалогове перетворення згаданих схем. Редактор граф-схем орієнтований на редагування зовнішнього вигляду графового подання алгоритмів, створених ДСП-конструктором. При цьому зміни, внесені в процесі редагування, відповідним чином відображаються на інших поданнях алгоритму (аналітичному і природно-лінгвістичному) у ДСП-конструкторі. ДСП-конструктор і редактор граф-схем мають зв’язок з інструментарієм візуалізованого проектування ОО програм (Rational Rose). Генератор САА-схем призначений для параметрично керованої генерації схем алгоритмів за РГС.

Рис. . Архітектура інтегрованого інструментарію

У підрозділі 3.4 розглядаються аналітична, природно-лінгвістична і графова форми подання проектованих алгоритмів в інструментарії.

Підрозділ 3.5 присвячено детальному розгляду проектування і синтезу програм у інструментарії за допомогою ДСП-конструктора, генератора САА-схем і редактора граф-схем.

В основу ДСП-конструктора покладено діалоговий режим із використанням меню підстановок і дерева конструювання алгоритму [4]. Меню складається з конструкцій САА-М, суперпозиція яких дозволяє створювати алгоритми в згаданих раніше формах. Обрані користувачем мовні конструкції відображаються в дереві з подальшою деталізацією їх змінних. У залежності від типу обраної змінної (операторного або предикатного) система пропонує відповідний список операцій САА-М або базисних понять із СКЗ. Процес побудови алгоритму є порівневим із можливістю переходів на різні рівні із продовженням процесу конструювання. За отриманими у процесі конструювання алгоритму деревом, реалізаціями елементарних операторів і умов цільовою ОО мовою програмування, а також іншими фрагментами, ДСП-конструктор виконує синтез програми. Підстановка синтезованого коду здійснюється у файл, згенерований у Rational Rose на основі діаграми класів. Даний файл містить каркасний опис основного класу програми.

Генератор САА-схем інструментарію забезпечує інтерпретацію РГС, результатом якої є текст САА-схем алгоритмів [2]. Конструювання гіперсхем, як і САА-схем, здійснюється у діалоговому режимі в ДСП-конструкторі. САА-схеми і гіперсхеми мають однаковий синтаксис, що дозволяє гнучко використовувати параметри керування генерацією схем, що задаються на рівні базисних операторів і умов. РГС виконується інтерпретатором у взаємодії із синтаксичним аналізатором, який розпізнає конструкції, що підлягають виконанню. У процесі цієї інтерпретації здійснюється обхід дерева конструювання гіперсхеми, отриманого на етапі її конструювання. У ході обробки вершин дерева формується породжувана ПРС.

Підрозділ 3.6 присвячено розробці засобів інструментальної підтримки навчання в учбових структурах комп’ютерної орієнтації. До таких засобів відноситься розроблений автоматизований лабораторний практикум, в основу якого покладено концепцію інтеграції навчальних курсів з імперативних мов програмування і алгоритміки [4]. Складовими частинами зазначеної програмної системи є модулі перевірки знань, алгоритмізації розв’язання задачі, розробки і виконання програм, довідкова система. Відмітимо доцільність використання в даному практикумі розглянутого ДСП-конструктора. Подібною до розглянутого автоматизованого практикуму є програмна система синтезу і діагностики логічних схем Baиa J., Koreиko Љ., Porubдn J., Vбclavik P. Didactic Version of Program System for Synthesis and Diagnostics of Logic Circuits // Programming Problems. – 2003. – ?3. – P. 53–58., яка відкриває можливості для використання отриманих у дисертації результатів у процесі проектування і синтезу схем апаратних засобів.

Четвертий розділ присвячено проектуванню і реалізації алгоритмічних знань із області символьної мультиобробки із використанням інтегрованого інструментарію, розробленого у розділі 3 [4, 5]. Наводяться результати тестування створених паралельних програм пошуку.

У підрозділі 4.1 розглянуто розроблені із використанням інтегрованого інструментарію і системи Rational Rose реалізації паралельних алгоритмів сортування у мові Java. У згаданій системі використано діаграми класів, діяльності, компонентів. У підрозділі 4.2 проілюстровано перехід від алгоритмів сортування до алгоритмів пошуку із використанням метаправил згортки і розгортки у розробленому ДСП-конструкторі.

У підрозділі 4.3 розглядається реалізація алгоритмів паралельного пошуку, моделі яких побудовано в підрозділі 2.3. Згадані алгоритми застосовуються у програмній системі паралельного пошуку Web-документів за ключовими словами]. Пошук виконується у файлі, який містить список слів із попередньо переглянутих документів. При цьому здійснюється паралельна обробка кількох запитів. Розглянуто також інший варіант системи пошуку документів, поданих за допомогою мови структурування даних XML. Пошук здійснюється за тегами у документах, які містять опис статей.

У таблиці 1 наведено середній час виконання паралельних програм пошуку мовою Cі із використанням технології MPІ у 3-процесорному обчислювальному кластері (процесори Іntel Celeron 1700 MГц, ОС Wіndows XP), розгорнутому на кафедрі програмного забезпечення автоматизованих систем МСУ під керівництвом проф. С.Д. Погорілого. Час виконання бульбашкового і човникового пошуку є приблизно однаковим, більш ефективними є альтернативний і бінарний алгоритми. Це відповідає отриманим у розділі 2 теоретичним оцінкам. Зазначені паралельні програми виконуються у середньому приблизно у 2 рази швидше послідовних.

Таблиця 1

Час виконання (у секундах) паралельних програм пошуку у файлах

Алгоритм пошуку | Кількість процесів | Кількість записів у файлі

15000 | 30000

Бульбашковий | 3 | 0.007 | 0.010

Човниковий | 3 | 0.006 | 0.010

Альтернативний | 3 | 0.004 | 0.006

Бінарний | 3 | 0.00079 | 0.00081

У Додатку до дисертації наведено тексти згенерованих за допомогою розробленого інтегрованого інструментарію паралельних програм сортування і пошуку мовою програмування Java.

ВИСНОВКИ

Головним результатом дисертації є розробка інтегрованих алгебро-алгоритмічних моделей, які розв’язують важливу задачу проектування і генерації програм і мають істотне значення для розробки послідовних та паралельних застосувань у сучасних ОО середовищах.

Конкретними науковими результатами проведеного дослідження є:

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

Створені моделі застосовано для проектування і генерації схем алгоритмів символьної мультиобробки: паралельних сортування, пошуку, мовного процесування та ін.

Розроблено концепцію середовища конструювання алгоритмічних знань символьної обробки, яка ґрунтується на апараті алгебри алгоритміки (стратегії обробки, метаправила конструювання схем). Отримано оригінальні оцінки обчислювальної складності розроблених паралельних алгоритмів мультиобробки, що входять до складу згаданого середовища.

Створено інтегрований інструментарій, в основу якого покладено систему діалогового конструювання та синтезу синтаксично правильних послідовних і паралельних алгоритмів та програм. Інструментарій забезпечує генерацію програм із використанням засобів візуалізованого проектування (мови UML і системи Rational Rose) у ОО середовищах програмування (Java, C++ та ін.). Інструментарій апробовано на розробці послідовних та паралельних програм сортування і пошуку.

Інструментарій впроваджено на кафедрі програмного забезпечення автоматизованих систем Міжнародного Соломонова університету.

ОСНОВНІ РЕЗУЛЬТАТИ ОПУБЛІКОВАНІ В РОБОТАХ

Цейтлин Г.Е., Яценко Е.А. Элементы алгебраической алгоритмики и объектно-ориентированный синтез параллельных программ // Математические машины и системы. – 2003. – №2. – С. 64–76.

Яценко Е.А. Алгебры гиперсхем и интегрированный инструментарий синтеза программ в современных объектно-ориентированных средах // Кибернетика и системный анализ. – 2004. – №1. – С. 47–52.

Яценко Е.А. Регулярные схемы алгоритмов адресной сортировки и поискаУСиМ. – 2004. – №5. – С. 61–66.

Яценко Е.А. Конструирование параллельных объектно-ориентированных программ // Проблемы программирования. Спец. выпуск по материалам 3-й Международной научно-практической конференции по программированию УкрПРОГ’2002. – К.: ИПС НАН Украины, 2002. – №1–2. – С. 188–197.

Яценко Е.А., Мохница А.С. Инструментальные средства конструирования синтаксически правильных параллельных алгоритмов и программ // Проблемы программирования. Спец. выпуск по материалам 4-й Международной научно-практической конференции по программированию УкрПРОГ’2004. – К.: ИПС НАН Украины, 2004. – №2–3. – С. 444–450.

Яценко О.А. Інтегровані алгебро-алгоритмічні моделі мультиобробки // Вісник Київського національного університету. Серія: фізико-математичні науки. Спец. випуск за матеріалами Міжнародної конференції “Теоретичні та прикладні аспекти побудови програмних систем” (TAAPSD’2004). – 2004. – С. 102–107.

АНОТАЦІЯ

Яценко О.А. Розробка інтегрованих алгебро-алгоритмічних моделей: елементи теорії, інструментарій, застосування. Рукопис.

Дисертація на здобуття наукового ступеня кандидата фізико-математичних наук за спеціальністю 01.05.03 – математичне та програмне забезпечення
обчислювальних машин і систем. Київський національний університет ім. Тараса Шевченка. – Київ, 2005.

Дисертація присвячена побудові інтегрованих алгебро-алгоритмічних моделей, що ґрунтуються на алгебрі алгоритміки, формальних граматиках і засобах параметрично керованої генерації регулярних схем. Згадані моделі призначено для проектування та синтезу паралельних алгоритмів і програм. Розроблені моделі застосовано для розв’язання задач символьної мультиобробки (паралельні сортування, пошук, мовне процесування та ін.). Розроблено концепцію середовища конструювання алгоритмічних знань мультиобробки, яка ґрунтується на апараті алгебри алгоритміки. Отримані теоретичні результати застосовано у розробленому інтегрованому інструментарії діалогового конструювання та синтезу синтаксично правильних послідовних і паралельних програм. Інструментарій забезпечує синтез програм у сучасних об’єктно-орієнтованих середовищах програмування із використанням засобів візуалізованого проектування програм.

Ключові слова: алгоритміка, регулярна схема, граматика структурного проектування, гіперсхема, діалогове конструювання синтаксично правильних програм, синтез програм, об’єктно-орієнтоване програмування.

ABSTRACT

Yatsenko O.A. The development of integrated algebra-algorithmic models: the elements of theory, instrumental means, applications. Manuscript.

Thesis for the degree of candidate of physical and mathematical sciences on the speciality 01.05.03 – mathematical and software support of computing machines and systems. – Kyiv National Taras Shevchenko university. – Kyiv, 2005.

The dissertation is devoted to development of integrated algebra-algorithmic models, which are based on algorithmics algebra, formal grammars and means of parametrically directed generation of regular schemes. The mentioned models are intended for designing and synthesis of consecutive and parallel algorithms and programs. The built models are applied for solving the problems of symbolical multiprocessing (parallel sorting, search, language processing etc.). Conception of the environment of constructing of algorithmic knowledge of multiprocessing was developed. It is based on algorithmics algebra. The instrumental means of dialogue designing and synthesis of syntactically correct consecutive and parallel programs were developed on the basis of the received theoretical results. The specified tools provide program synthesis in modern object-oriented environments with the use of means of visualized designing of programs.

Keywords: algorithmics, regular scheme, grammar of structural designing, hyperscheme, dialogue designing of syntactically correct programs, program synthesis, object-oriented programming.

AННОТАЦИЯ

Яценко Е.А. Разработка интегрированных алгебро-алгоритмических моделей: элементы теории, инструментарий, применения. Рукопись.

Диссертация на соискание научной степени кандидата физико-математических наук по специальности 01.05.03 – математическое и программное обеспечение вычислительных машин и систем. Киевский национальный университет им. Тараса Шевченко. – Киев, 2005.

Диссертация посвящена построению интегрированных алгебро-алгоритмических моделей, предназначенных для проектирования и синтеза классов последовательных и параллельных алгоритмов и программ.

Упомянутые интегрированные модели объединяют в себе аппарат алгебры алгоритмики с теорией формальных грамматик. Алгоритмика является перспективным направлением современной компьютерной науки, развивающимся в рамках украинской алгебро-кибернетической школы. В работе построены распределенные гиперсхемы – модели, предназначенные для представления алгоритмов управления выводом в грамматиках, ориентированных на порождение классов алгоритмов. В упомянутых грамматиках гиперсхемы задают порядок применения продукций. По распределенным гиперсхемам осуществляется параметрически управляемая генерация последовательных и параллельных регулярных схем, представленных в системах алгоритмических алгебр. Указанные интегрированные модели используются для описания некоторого класса алгоритмов. Результатом установки значений параметров гиперсхемы и ее интерпретации является схема алгоритма, адаптированного к конкретным условиям использования. Модели применены для решения задач символьной мультиобработки (параллельные сортировка, поиск, языковое процессирование и др.). Разработаны модели параллельных алгоритмов многослойной челночной сортировки, адресной сортировки и поиска. Для построения схем алгоритмов наравне с интегрированными моделями применяются метаправила конструирования, позволяющие укрупнить процесс проектирования и сделать его более гибким. С их использованием осуществляется абстрагирование и детализация алгоритмов, а также переход от одних алгоритмов к другим.

Предложена концепция среды конструирования алгоритмических знаний, основывающаяся на понятии алгебры алгоритмики. Основными элементами упомянутой среды в соответствии с данной концепцией являются: языковые конструкции систем алгоритмических алгебр и элементарные операторы и условия схем, а также их программные реализации, предназначенные для проектирования алгоритмов и синтеза программ в данной предметной области на выбранном целевом языке; метаправила конструирования (позволяющие порождать новые знания); стратегии обработки (схемы, описывающие классы алгоритмов и подлежащие дальнейшей детализации); алгоритмы сортировки и поиска; распределенные гиперсхемы. В среде конструирования знаний совместно используются три формы представления алгоритмов: аналитическая (формула в алгебре алгоритмов), естественно-лингвистическая и графовая (граф-схемы Калужнина). Разработаны модели параллельных алгоритмов сортировки и поиска, входящие в состав разработанного прототипа сформулированной концепции среды конструирования знаний, и получены оригинальные оценки их вычислительной сложности.

На основе полученных теоретических результатов разработан интегрированный инструментарий проектирования и синтеза последовательных и параллельных программ. В его основу положен метод диалогового конструирования синтаксически правильных программ, ориентированный не на поиск и исправление ошибок (как в традиционных синтаксических анализаторах), а на исключение возможности их появления в процессе построения схем алгоритмов. Особенностью программной системы является также интеграция всех трех упомянутых выше форм представления программ при их проектировании (аналитической, естественно-лингвистической и графовой). В интегрированном инструментарии осуществляется построение синтаксически правильных схем алгоритмов в системах алгоритмических алгебр, а также синтез программ в различных, в том числе объектно-ориентированных средах программирования (Java, C++ и др.). Кроме того, инструментарий предоставляет средства параметрически управляемой генерации схем алгоритмов по распределенным гиперсхемам и редактирования графового представления программ. Проектирование гиперсхем выполняется в диалоговом режиме, обеспечивающем их синтаксическую правильность. Инструментарий обеспечивает генерацию программ с использованием средств визуализированного проектирования объектно-ориентированных программ (языка UML и системы Rational Rose). Разработанный инструментарий апробирован на синтезе последовательных и параллельных программ сортировки и поиска. В частности, созданы программы сортировки числовых массивов, поиска Web-документов по ключевым словам, а также поиска, базирующегося на использовании XML-технологии.

Ключевые слова: алгоритмика, регулярная схема, грамматика структурного проектирования, гиперсхема, диалоговое конструирование синтаксически правильных программ, синтез программ, объектно-ориентированное программирование.