Синтез комбінаторних конфігурацій на рівні блок-схем за допомогою числових в’язанок

Размещено на http://www.allbest.ru/

Міністерство освіти та науки України

Державний університет “Львівська політехніка”

УДК 621.382:519.6

СИНТЕЗ КОМБІНАТОРНИХ КОНФІГУРАЦІЙ НА РІВНІ БЛОК-СХЕМ ЗА ДОПОМОГОЮ ЧИСЛОВИХ В'ЯЗАНОК

01.05.02 - математичне моделювання та обчислювальні методи

Автореферат

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

кандидата технічних наук

Соломко Михайло Тимофійович

Львів 2000

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

Робота виконана в Державному університеті “Львівська політехніка” Міністерства освіти та науки України.

Науковий керівник: доктор технічних наук, професор кафедри “Автоматизовані системи управління” Державного університету “Львівська політехніка” Міністерства освіти та науки України, м. Львів Різник Володимир Васильович

Офіційні опоненти: доктор фізико-математичних наук, професор, завідувач кафедри “Теоретичної і загальної електротехніки” Державного університету “Львівська політехніка”, м. Львів Стахів Петро Григорович;

доктор технічних наук, професор, завідувач кафедри “Прикладна математика” Рівненського Державного технічного університету, м. Рівне Власюк Анатолій Павлович.

Провідна установа: Державний науково-дослідний інститут інформаційної інфраструктури Державного комітету звязку та інформатизації України і Національної академії наук України, відділ інформаційних технологій і систем (м. Львів).

Захист відбудеться “_23_”____грудня____ 2000 року о _13_ годині на засіданні спеціалізованої вченої ради Д 35.052.05 у Державному університеті “Львівська політехніка” за адресою: 79013, м. Львів, вул. С. Бандери, 12, ауд. 226 головного корпусу.

З дисертацією можна ознайомитися в бібліотеці Державного університету “Львівська політехніка” (79013, м. Львів, вул. Професорська, 1).

Автореферат розісланий “_22_“___листопада____2000 року.

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

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

кандидат технічних наук Ткаченко С.П.

Загальна характеристика роботи

блок схема лінійка математичний

Актуальність проблеми. Комбінаторні конфігурації вперше з'явилися в задачах математичної статистики під час планування експерименту і обробки експериментальних даних. Вони стали самостійним обєктом досліджень та засобом для вирішення ряду практично важливих задач і набули різних видів інтерпретацій, таких як блок-схеми, ортогональні таблиці та інші. Блок схеми виявилися ефективним апаратом теорії кодування, теорії ігор, графів, тестових оцінок, пов'язаних з дослідженнями в різних галузях народного господарства. Інтерес до неповних блоків пов'язаний із зменшенням трудомісткості експерименту у порівнянні з класичною схемою дисперсійного аналізу, завдяки скороченню обсягу спостережень за умови збереження рівня об'єктивності результатів дослідження. Питання існування і побудови неповних блок-схем належить до найскладніших задач сучасного комбінаторного аналізу. На даний час відомі методи побудови блок-схем вимагають різних математичних підходів, пов'язаних з використанням розрізнених знань з математики. Однак, існуючі критерії визначення умов існування блок-схем не завжди гарантують ефективну їх побудову, а синтез таких моделей здебільшого базується на складних математичних рішеннях. Тому важливим і актуальним постає проблема створення достатньо простих алгоритмів та автоматизованих методів побудови комбінаторних конфігурацій, зокрема неповних блок-схем.

До відомих методів синтезу блок-схем належать табличні методи побудови матриць інцидентності різного виду, методи апарату скінченних груп перестановок, схеми відношень як базові структури по Дельсарту, методами, які пов'язані з використанням апарату теорії полів Галуа та ін.

Запропоновані в 1979 р. В.В. Різником комбінаторні конструкції або, так звані “ідеальні кільцеві в'язанки” виявилися зручним інструментом для синтезу та дослідження комбінаторних конфігурацій, оскільки відношення інцидентності, що існують в більшості класичних комбінаторних конфігураціях, не піддаються відносно простому математичному описові, в той час як у в'язанках ці відношення постають у вигляді звичайної числової послідовності. Тому останні дають змогу спростити дослідження і синтез комбінаторних конфігурацій, а відтак побудову оптимальних планів експерименту і розширити теоретичні дослідження в області комбінаторики.

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

Для досягнення поставленої мети необхідно вирішити наступні задачі:

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

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

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

дослідити параметри другого роду частково зрівноважених блок-схем, побудованих за допомогою компактних лінійок з метою упорядкування класифікації частково зрівноважених блок-схем;

дослідити особливості синтезу частково зрівноважених блок-схем з >2 за допомогою в'язанок з розгалуженою структурою, де - число траплянь пар елементів у блоках блок-схеми;

дослідити можливості системного методу побудови блок-схем з метою автоматизації їх синтезу;

розробити алгоритмічно-програмні засоби генерації блок-схем на базі створеного математичного забезпечення.

Методи досліджень. Дослідження, які спрямовані на вирішення поставлених задач, базуються на обчислювальних методах комбінаторного аналізу і математичного моделювання, з використанням елементів теорії полів Галуа, групи діедра, теорії графів та алгебричної теорії в'язанок.

Наукова новизна роботи:

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

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

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

вперше розроблено метод синтезу блок-схем за допомогою в'язанок з розгалуженою структурою, що дало змогу розширити діапазон значень параметрів синтезованих блок-схем;

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

Практичне значення одержаних результатів:

запропоновано підхід для синтезу та дослідження класичних блок-схем за числовими в'язанками, що дає змогу спростити метод побудови широкого класу блок-схем;

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

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

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

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

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

Впровадження результатів роботи.

Розроблені в дисертаційній роботі методи і рекомендації впроваджені:

на Сарненській дослідній станції Інституту гідротехніки і меліорації УААН для побудови планів експерименту при дослідженні агрохімічних, агрофізичних та радіологічних характеристик стану грунтового покриву меліорованих грунтів гумідної зони Західного Полісся;

у Рівненському Інституті епізоотології УААН для побудови планів експерименту при дослідженні біохімічних показників сироватки крові ВРХ;

у Рівненському інноваційному центрі “Темп” в маркетингових дослідженнях при визначенні ефективності різних видів реклами;

у Львівобленерго (ЛЕМ) для побудови неповноблочних планів проведення випробовування елементів та вузлів електромереж;

у навчальний процес в Державному університеті “Львівська політехніка” при проведенні лабораторного практикуму з курсів “Проектування автоматизованих систем наукових досліджень та комплексних випробувань” та “Математичні моделі синтезу та оптимізації систем”.

Апробація роботи

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

Міжнародна наукова конференція, присвячена 150-річчю від дня народження Івана Пулюя (м. Львів, 23-26 травня 1995 р.);

Міжнародна конференція “Сучасні проблеми автоматизованої розробки і виробництва радіоелектронних засобів, застосування засобів зв'язку та підготовки інженерних кадрів” (м. Славсько, 27 лютого - 3 березня 1996р.);

Міжнародний симпозіум “Сучасні проблеми в компютерних науках в Україні” (м. Славсько, 21-25 лютого, 2000 р.).

У повному обсязі дисертаційна робота доповідалась на кафедрі “Автоматизовані системи управління” Державного університету “Львівська політехніка”.

Особистий внесок автора. Автором самостійно виконана основна частина теоретичних та експериментальних досліджень:

розроблено спрощений метод побудови неповних зрівноважених блок-схем і тактичних конфігурацій за допомогою числових в'язанок [4,5];

досліджені параметри частково зрівноважених блок-схем та розроблено спрощений метод їх синтезу числовими в'язанками [5];

розроблено метод синтезу лінійок Голомба за допомогою генератора сполучень [2];

розроблено спрощений метод генерації сполучень [1];

розроблений системний метод побудови блок-схем з використанням критерію керування ситуацією [1,3].

Публікації. Основні положення і результати дисертаційної роботи відображені у восьми друкованих працях, з яких 5 статей у фахових виданнях.

Зв'язок роботи з науковими програмами, планами, темами. Тема дисертації пов'язана з такими науково-технічними темами (виконувались в Державному університеті “Львівська політехніка”):

“Оптимізація побудови нееквідистантних структур”. Тема виконувалась в 1989-1991 рр. згідно з програмою АН УРСР по АСНД (№31/1 від 06.04.1989р. по замовленню СНТБ Інституту прикладних проблем механіки і математики АН УРСР).

“Інформаційно-пошукова система по технічних умовах у Львівських міських електромережах”. Тема виконувалася в 1996-1997 рр. згідно з угодою № 1096Д.

Структура та обсяг роботи. Дисертаційна робота обіймає 136 сторінок машинописного тексту і складається із вступу, чотирьох розділів, висновків, а також списку літератури та додатків. Робота містить 26 рисунків, 7 таблиць. Бібліографічний список складається із 100 назв.

Основний зміст роботи

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

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

Зрівноваженою блок-схемою називається таке розміщення v різних елементів по b блоках, коли кожен блок містить рівно k різних елементів, кожен елемент трапляється рівно в r різних блоках і кожна пара різних елементів a_i, a_j трапляється точно в блоках. Подані співвідношення, яким задовольняють параметри блок-схеми. Якщо в зрівноваженій неповній блок-схемі число b блоків дорівнює числу v елементів (b=v), число траплянь кожного елемента в блоках схеми дорівнює розміру блока, тобто r=k і навпаки, то блок-схеми з такими властивостями належать до симетричних схем.

Розглянуто циклічний автоморфізм блок-схем і проблеми побудови симетричних блок-схем, причому симетрична блок-схема на множині елементів {b_j}={j}, j=1,2,...,S_n відповідає числовій послідовності (k₁, k₂,..., k_j,..., k_n), яка утворює ідеальну кільцеву в'язанку (ІКВ) з параметрами n та R, де n -- число елементів, а R - число кільцевих сум з однаковими числовими значеннями. Кільцеві суми утворюються на ІКВ як довільна кількість будь-яких поруч розміщених елементів числової вязанки.

Аналіз схемно-конструктивного зв'язку між блок-схемами та ІКВ дозволив розробити спрощений метод дослідження блок-схем без їх побудови, на підставі таблиць сум на на n-послідовності чисел. За таблицею сум можна не лише досліджувати блок-схеми, але й передбачати існування відповідної блок-схеми. Така можливість особливо корисна під час пошуку в'язанок, властивості яких відповідають моделям для одержання блок-схем зі заданими параметрами.

В'язанки в своїй сукупності можуть утворювати широку структуру внутрішніх зв'язків комбінаторних моделей. Для неідеальних в'язанок, таких як компактні кільцеві в'язанки, лінійки без розгалуження більше третього порядку, лінійки з розгалуженням відповідають частково зрівноважені блок-схеми (ЧЗ блок-схеми). На відміну від неповних збалансованих блоків, у частково зрівноваженій блок-схемі пари елементів можуть з'являтися неоднакове число разів.

У другому розділі дисертації досліджуються частково зрівноважені блок-схеми за допомогою неідеальних в'язанок.

Блок-схеми називаються зрівноваженими тому, що в них пари різних елементів трапляються з однаковою частотою і параметри блок-схеми задовольняють співвідношенням

bk=vr (1)

r(k-1)=(v-1) (2)

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

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

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

Неідеальні в'язанки можна розділити на дві групи. До першої належать компактні в'язанки, до другої - некомпактні. Компактні в'язанки за своїми комбінаторними властивостями близькі до ідеальних і є наближеною моделлю останніх. Такі моделі зручно розглядати тоді, коли ідеальних в'язанок при заданих параметрах не вдається побудувати, або якщо їх зовсім не існує.

Найпростіші серед компактних в'язанок - компактні лінійки-вязанки, тобто одновимірні розімкнені в'язанки без розгалужень. Лінійка-вязанка характеризується числом n елементів k₁,k₂,...,k_i,...,k_n, довжиною L=, а також діапазоном реалізації значень 1,2,...,N<L, утворених на цій числовій послідовності.

Для побудови частково зрівноваженої блок-схеми використовується циклічний автоморфізм , який полягає в тому, що зміна індексів jj+1(mod v) при всіх k елементах j-го блоку блок-схеми приводить до утворення множини елементів (j+1(mod v))-го блоку цієї ж блок-схеми, так що множина елементів окремого блоку повністю визначає всю блок-схему.

Показано, що компактній лінійці з параметрами n та L відповідає частково зрівноважена блок-схема на множині елементів

{b_j}={j}, j=1,2,...,L

З цією метою послідовності чисел (k₁,k₂,...,k_i,...,k_n), яка утворює КЛ, можна поставити у відповідність L= послідовностей:

елементи яких визначаються за формулою

(3)

Розглядаючи кожну послідовність B^(j) як окремий блок блок-схеми, легко знайти b=L і k=n. Інші параметри блок-схеми знаходяться за допомогою відомих теорем комбінаторного аналізу. Серед інших питань розглянуто умови існування частково зрівноваженої блок-схеми з параметрами t-(v,k, ), де =p/q - відношення цілих чисел, а також досліджені параметри другого роду для частково зрівноважених блок-схем, які побудовані за допомогою неідеальних лінійок.

Досліджені особливості побудови частково зрівноважених блок-схем з > 2. За кількістю повторів кожного з реалізованих на в'язанці числових значень ідеальні в'язанки ділять на прості (реалізовані значення не повторюються) та багатократні - (повторюються значення). У неідеальних в'язанках реалізовані значення можуть траплятися не більше одного (R<1) разу, більше одного (R>1), або повторюються згідно з установленими обмеженнями в заданому діапазоні змін кратності (R=var). Кратність повторів реалізованих числових значень R в'язанки відповідає параметру відповідної блок-схеми. Відомо, що для неідеальних в'язанок багатократність повторів реалізується на в'язанках з розгалуженою структурою, приклад якої наводиться нижче (Рис.1).

Размещено на http://www.allbest.ru/

Перед тим, як застосувати циклічний автоморфізм необхідно знайти перший блок, за яким буде синтезована решта блоків. Для вязанки з розгалуженою структурою елементи першого блоку визначаються наступним чином:

b⁽¹⁾₁= k₁=1 b⁽¹⁾₃= k₁+ k₂+ k₃=7

b⁽¹⁾₂= k₁+ k₂=3 b⁽¹⁾₄= k₁+ k₄=2

b⁽¹⁾₅= k₁+ k₅=5

Отже, перший блок має вигляд

B⁽¹⁾=(1,3,7,2,5)

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

У третьому розділі проаналізовані питання побудови неповних зрівноважених блоків, тактичних блок-схем за допомогою ІКВ, а також досліджені інші методи синтезу частково зрівноважених блок-схем. З цією метою проведено аналіз побудови додаткового, похідного і залишкового блоків. Моделі додаткового, похідного і залишкового блоків задовольняють умовам (1) і (2) для неповних збалансованих блоків. Показано, як із симетричної блок-схеми можна отримати дві нові блок-схеми, які називаються залишковою та похідною.

На ряді прикладів реалізовано побудову неповних зрівноважених блоків за допомогою ІКВ. Для того, щоб виконати таку побудову достатньо обрати необхідну ідеальну кільцеву в'язанку і на основі залежності (3) побудувати симетричну блок-схему. Для одержаної симетричної блок-схеми можна побудувати похідну і залишкову блок-схеми.

Аналогічні дії можна виконувати стосовно будь-яких інших послідовностей чисел, що утворюють ІКВ з відповідними параметрами, кожного разу отримуючи неповну зрівноважену блок-схему з параметрами 2-(v,k,).

Параметри повних зрівноважених блоків, одержаних за допомогою послідовності чисел, що утворюють ІКВ, можна записати в термінах ІКВ:

- для залишкової блок схеми

b=S_n-1, k=n-R,

v=S_n-n, =R (4)

її параметри в термінах ІКВ

2-(S_n-1, n-R, R)

- для похідної блок-схеми

b=S_n-1, k=R,

v=n, =R-1 5)

її параметри в термінах ІКВ

2-(S_n-1, n, R-1)

- для додаткової блок-схеми

b=S_n, k=n-1

v=n, =R-1 (6)

її параметри в термінах ІКВ

2-(S_n, n-1, R-1)

Блок-схеми виділяються серед комбінаторних конфігурацій вимогою зрівноваженності відносно пар, тобто однакової частоти траплянь пар елементів в підмножинах (блоках). Питання існування тактичних конфігурацій (t>2) з параметрами t-(v,k,), які можна побудувати за допомогою ІКВ, вирішується на основі відомих теорем комбінаторного аналізу та співвідношень (4), (5).

Показано, що ІКВ з параметрами n, R та n+1, R+1 відповідають симетричні блок-схеми з однаковими значеннями S_n. Якщо для симетричної блок-схеми, яка утворена за допомогою ІКВ з параметрами n, R, побудувати залишкову блок-схему2-(S_n-1, n-R, R), а для симетричної блок-схеми, яка утворена за допомогою ІКВ з параметрами n+1, R+1, похідну блок-схему2-(S_n-1, n, R-1), тоді отримаємо залишкову і похідну схеми з однаковою кількістю блоків, які також мають однакову кількість елементів і відтак розмір блока. Це означає, що блоки першої блок-схеми можна об'єднати з блоками другої, після об'єднання яких одержимо нову блок-схему з параметрами:

t-(v,k,l)

де: t - підмножина чисел, яка покривається k-підмножиною тих же чисел,

Існування t-конфігурацій при t>2 вимагає, щоб усі числа l_t=l, l_t-1,..., l₁=r, l₀=b були цілі. В термінах ІКВ, для об'єднаної блок-схеми це означає, що за умови, коли

не виключена можливість існування t-конфігурації при t>2.

Показано, що для побудови t-конфігурації через об'єднання залишкової та похідної блок-схем необхідно вибрати взаємно-доповнюючі блоки. Для того, щоб одержати блок-схему із взаємно доповнюючими блоками, необхідно виконати нову побудову симетричної блок-схеми, попередньо зробивши перестановку числової послідовності, яка утворює ІКВ. Причому перестановка не повинна порушувати властивості симетричної блок-схеми, тобто будь-які два блоки повинні мати однакову кількість загальних елементів. Однак, пошук потрібної перестановки серед великого числа перестановок на послідовності чисел є громіздкою задачею. Пошуки ефективного способу знаходження потрібної перестановки показали, що вся необхідна інформація міститься в групі діедра випуклого n-кутника, який співставлється послідовності чисел, що утворює ІКВ порядка n (Рис.2).

Для прикладу розглянемо числову послідовність (1, 1, 1, 2, 2, 5, 1, 2, 1, 3), що утворює ІКВ з параметрами n=10, R=5, S_n=19 та числову послідовність (1, 1, 1, 2, 2, 5, 1, 3, 3), що утворює ІКВ з параметрами n=9, R=4, S_n=19.

Зaмінивши в залежності (3) величину L на значення кільцевої суми S_n, для ІКВ з параметрами n=10, R=5, S_n=19, знаходимо:

B₁=(2,3,4,6,8,13,14,16,17,1), B₁₀=(11,12,13,15,17,3,4,6,7,10),

B₂=(3,4,5,7,9,14,15,17,18,2), B₁₁=(12,13,14,16,18,4,5,7,8,11),

B₃=(4,5,6,8,10,15,16,18,19,3), B₁₂=(13,14,15,17,19,5,6,8,9,12),

B₄=(5,6,7,9,11,16,17,19,1,4), B₁₃=(14,15,16,18,1,6,7,9,10,13),

B₅=(6,7,8,10,12,17,18,1,2,5), B₁₄=(15,16,17,19,2,7,8,10,11,14), (7)

B₆=(7,8,9,11,13,18,19,2,3,6), B₁₅=(16,17,18,1,3,8,9,11,12,15),

B₇=(8,9,10,12,14,19,1,3,4,7), B₁₆=(17,18,19,2,4,9,10,12,13,16),

B₈=(9,10,11,13,15,1,2,4,5,8), B₁₇=(18,19,1,3,5,10,11,13,14,17),

B₉=(10,11,12,14,16,2,3,5,6,9), B₁₈=(19,1,2,4,6,11,12,14,15,18),

B₁₉=(1,2,3,5,7,12,13,15,16,19).

Размещено на http://www.allbest.ru/

Відмітимо, що симетрична схема, яку можна отримати за допомогою послідовності (1, 1, 1, 2, 2, 5, 1, 3, 3), що утворює ІКВ з параметрами n=9, R=4, Sn=19, не буде мати взаємно доповнюючих блоків з блок-схемою (7). Тому слід зробити перестановку чисел послідовності за допомогою групи діедра випуклого 9-кутника. Відповідний 9-кутник показаний на рис.2. Вісь симетрії вказує на пари елементів, які переставляються: (1,3), (1,3), (2,1), (2,5).

Зробивши відповідні симетричні перетворення відносно осі одержимо перстановку, яка відповідає переходу послідовності (1, 1, 1, 2, 2, 5, 1, 3, 3) у послідовність (1, 3, 3, 1, 5, 2, 2, 1, 1). Для нової послідовності чисел симетрична блок-схема складається з блоків:

B₁=(2,5,8,9,14,16,18,19,1), B₁₀=(11,14,17,18,4,6,8,9,10),

B₂=(3,6,9,10,15,17,19,1,2), B₁₁=(12,15,18,19,5,7,9,10,11),

B₃=(4,7,10,11,16,18,1,2,3), B₁₂=(13,16,19,1,6,8,10,11,12),

B₄=(5,8,11,12,17,19,2,3,4), B₁₃=(14,17,1,2,7,9,11,12,13),

B₅=(6,9,12,13,18,1,3,4,5), B₁₄=(15,18,2,3,8,10,12,13,14), (8)

B₆=(7,10,13,14,19,2,4,5,6), B₁₅=(16,19,3,4,9,11,13,14,15),

B₇=(8,11,14,15,1,3,5,6,7), B₁₆=(17,1,4,5,10,12,14,15,16),

B₈=(9,12,15,16,2,4,6,7,8), B₁₇=(18,2,5,6,11,13,15,16,17),

B₉=(10,13,16,17,3,5,7,8,9), B₁₈=(19,2,6,7,12,14,16,17,18),

B₁₉=(1,4,7,8,13,15,17,18,19).

Блок B19=(1,2,3,5,7,12,13,15,16,19) з схеми (7) є доповнюючим блоком до блоку B10=(11,14,17,18,4,6,8,9,10) з схеми (8).

Похідна блок-схема (а) до симетричної схеми (7), побудована за допомогою B19, та залишкова блок-схема (б) до симетричної схеми (8) - за допомогою B10, набувають наступного вигляду:

а) похідна блок-схема б) залишкова блок-схема

B₁=(1,2,3,13,16), B₁₀=(3,7,12,13,15), B^*₁=(1,2,5,16,19),

B^*₁₀=(5,7,12,15,19), B₂=(2,3,5,7,15), B₁₁=(5,7,12,13,16),

B^*₂=(1,2,3,15,19), B^*₁₁=(1,12,13,16,19), B₃=(3,5,15,16,19),

B₁₂=(5,12,13,15,19), B^*₃=(1,2,3,7,16), B^*₁₂=(1,2,7,12,13),

B₄=(1,5,7,16,19), B₁₃=(1,7,13,15,16), B^*₄=(2,3,5,12,19),

B^*₁₃=(2,3,12,13,15), B₅=(1,2,5,7,12), B₁₄=(2,7,15,16,19),

B^*₅=(1,3,5,12,13), B^*₁₄=(3,13,15,16,19), B₆=(2,3,7,13,19),

B₁₅=(1,3,12,15,16), B^*₆=(2,5,7,13,19), B^*₁₅=(1,5,12,15,16),

B₇=(1,3,7,12,19), B₁₆=(2,12,13,16,19), B^*₇=(1,3,5,7,15),

B^*₁₆=(2,5,13,15,16), B₈=(1,2,5,13,15), B₁₇=(1,3,5,13,19),

B^*₈=(2,7,12,15,16), B^*₁₇=(3,7,12,16,19), B₉=(2,3,5,12,16),

B₁₈=(1,2,12,15,19). B^*₉=(3,5,7,13,16), B^*₁₈=(1,7,13,15,19).

Об'єднавши похідну (а) та залишкову (б) блок-схеми, одержимо t-конфігурацію з параметрами 3-(10,5,3).

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

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

Размещено на http://www.allbest.ru/

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

В додатках подані акти впроваджень результатів роботи, програмні засоби генерації блок-схем, приклади синтезованих блок-схем.

Основні результати роботи та висновки

У дисертаційній роботі на базі теоретичних досліджень розроблено алгоритмічне та програмне забезпечення для синтезу комбінаторних конфігурацій на рівні блок-схем за допомогою в'язанок і одержано такі основні результати:

1. Застосування ідеальних в'язанок як числових моделей (прості і багатократні ідеальні кільця) дало змогу спростити методику побудови та дослідження неповних зрівноважених блок-схем й тактичних конфігурацій і розширити можливості їх практичного застосування.

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

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

4. Вперше за допомогою в'язанок розроблено регулярний метод побудови тактичних конфігурацій (t-конфігурацій) з використанням двох блок-схем, одержаних з відповідних ІКВ, та показано, що достатніми умовами побудови таких конфігурацій є наявність доповнюючих блоків з похідної та залишкової блок-схем, і зі збільшенням порядку ІКВ принцип побудови t-конфігурацій не порушується.

5. Вперше виявлено тісний взаємозв'язок числових в'язанок з групою діедра випуклого n-кутника, що дозволяє підвищити швидкість побудови тактичних конфігурацій, і тим самим розширити можливості синтезу конфігурацій високих порядків.

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

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

8. Вперше розроблено пакет алгоритмічних засобів для побудови блок-схем за допомогою числових в'язанок та побудовані блок-схеми t _ (v, k, ) для t=25.

Публікації за темою дисертаційної роботи

Соломко М.Т. Спрощений метод генерації сполучень // Контрольно-вимірювальна техніка. Львів: “Світ”, 1993. Вип. 50. С. 86-91.

Рибіцький Т.О. Соломко М.Т. Методи синтезу лінійок Голомба // Технічні засоби автоматизації вимірів та керування науковими дослідженнями: Вісник ЛПІ. Львів, 1992. №267. С. 79-80.

Соломко М.Т. Побудова систем трійок Штейнера // “Комп'ютерна інженерія та інформаційні технології”: Вісник ДУ “Львівська політехніка”. №294. 1995. С. 93-97.

Велика О.Т., Парамуд Н.Я., Різник В.В., Соломко М.Т. Синтез циклічних блок-схем за допомогою ідеальних кільцевих в'язанок // Прикладна математика: Вісник ДУ “Львівська політехніка”. №364. 1999. С. 187-189.

Різник В.В., Різник О.Я., Соломко М.Т. Моделювання та дослідження комбінаторних конфігурацій за допомогою числових в'язанок // Комп'ютерна інженерія та інформаційні технології: Вісник Державного університету “Львівська політехніка”. №370. 1999. С. 78-81.

Різник В.В., Кісь Я.П., Соломко М.Т. Комбінаторні конфігурації в радіофізичних методах досліджень // Тези доповідей Міжнародної наукової конференції, присвяченої 150-річчю від дня народження Івана Пулюя. Львів, 1995. С. 218.

Різник В.В., Різник О.Я, Кісь Я.П., Соломко М.Т. Комбінаторні моделі для синтезу оптимальних планів експерименту в задачах радіоелектроніки // Матеріали Міжнародної НТК “Сучасні проблеми автоматизованої розробки і виробництва радіоелектронних засобів, застосування засобів зв'язку та підготовки інженерних кадрів”. Львів, 1996. Ч.2. С. 215.

Різник В.В., Купчак М.В., Соломко М.Т. Комбінаторні конфігурації в задачах моделювання телекомутаційних систем // Матеріали міжнародної НТК “Сучасні проблеми автоматизованої розробки і виробництва радіоелектронних засобів, застосування засобів зв'язку та підготовки інженерних кадрів”. Львів, 1996. Ч.2. С. 214.

Анотація

Соломко М.Т. Синтез комбінаторних конфігурацій на рівні блок-схем за допомогою числових вязанок. Дисертація у вигляді рукопису на здобуття наукового ступеня кандидата технічних наук за спеціальністю 01.05.02 - “Математичне моделювання та обчислювальні методи”, Державний університет “Львівська політехніка”. м. Львів, 2000р.

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

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

Аннотация

Соломко М.Т. Синтез комбинаторных конфигураций на уровне блок-схем с помощью числовых вязанок. Диссертация на соискание ученой степени кандидата технических наук по специальности 01.05.02 - “Математическое моделирование и вычислительные методы” Госсударственный университет “Львивська политехника”. г.Львов, 2000г.

В диссертационной работе защищаются методы построения классических комбинаторных конфигураций с помощью прикладной теории вязанок: метод построения неполных уравновешенных блок-схем с помощью идеальных кольцевых вязанок; метод построения тактических конфигураций с помощью идеальных кольцевых вязанок; метод построения частично уравновешенных блок-схем с помощью компактных линеек-вязанок и компактных кольцевых вязанок; метод построения частично уравновешеных блоков с помощью двукратных компактных вязанок с разветвленной структурой.

В качестве базовых моделей предложено использовать числовые последовательности в виде вязанок с кольцевой, цепочной и разветвленной структурами. Это позволило упростить построение и расширить исследование неполных блок-схем и тактических конфигураций, благодаря использованию обнаруженных взаимосвязей между вязанками и комбинаторными конфигурациями различных типов. Вязанки оказались очень удобными моделями для быстрого построения комбинаторных конфигураций высоких порядков с разнообразными наборами параметров.

Разработан метод построения широкого класса производных, остаточных и дополнительных блок-схем, которые принадлежат к неполным уравновешеным блокам.

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

Впервые выявлена тесная взаимосвязь вязанок с группой диедра выпуклого n-угольника, что позволяет ускорить построение тактической конфигурации.

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

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

Впервые разработан эффективный синтез блок-схем системным методом с использованием критерия управления ситуацией, который уменьшает объем вычислений в два и больше раз. Показан метод построения блок-схем с помощью объединения аппарата теории вязанок с системным методом, что дало возможность строить блок-схемы с расширенным диапазоном значений параметров синтезированных блок-схем. Предложенный системный метод впервые позволяет эффективно строить все неизоморфные блок-схемы для заданых значений параметров.

Приведены результаты построения блок-схем с параметрами t-(v, k, ) для t=25.

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

Annotation

Solomko M.T. Syntethis of combinatorial configurations on the block-design's level by numerical bundles.

The thesis is represented as a manuscript to acquire for degree of candidate of technical sciences in speciality 01.05.02 - Mathematical simulation and computing techniques, State University “Lvivs'ka Politechnika”, Lviv, 2000.

This thesis contains techniques and algorithms of synthesis of classical combinatorial configurations using applied theory of bundles, namely: technique of synthesis of balanced incomplete block designs by ideal ring bundles; technique of synthesis of tactical configurations by ideal ring bundles; algorithm of construction of partial balanced block-designs by compact ruler-bundles and compact ring bundles; technique of construction of partial balanced blocks by two-times compact bundles with tree-like structure.

Effectiveness of developed technique and algorithms has been researched and their advantages and possibilities for application have been grounded.

Key words: combinatorial configuration, simulation, block-design, numerical bundle, synthesis.

Размещено на Allbest.ru

...