В В Різник, М Т Соломко - Синтез комбінаторних систем за допомогою багатовимірних в'язанок - страница 1

Страницы:
1  2  3  4 

інформаційних систем, 2006, http: // www. microsoft. Com / Ukraine / Government / Analytics / Integration Technologies/Overview, msp 5. Кузнецов С. Пространства данных: исследовательский полигон или путь к новому поколению систем управления данными? http: // synthesis. ipi. ac. Ru /sigmod/seminar/s20060420. 6 Donald Kossmann, Jens-Peter Dittrich. Personal Data Spaces. http://www.inf.ethz.ch/news/focus/res_focus/feb_2006/index_DE. 7. Garretts Summary of Principles of Dataspace Systems, http: // aravaipa. eas. asu. edu/ wiki/ index.php /Garretts _ Summary _ of _ Principles _of_Dataspace_Systems# Overview 8. ETH - Databases and Information Systems - iMeMex, www.dbis.ethz.ch/research/current_projects/iMeMex 9. Processing of natural language queries to a relational database. Samsonova M, Pisarev A, Blagov M, http: // www. cs.dartmouth. edu/ ~brd/ Teaching/ AI/Lectures/Summaries/natlang.html 10. Основные концепции и подходы при создании контекстно-поисковых систем на основе реляционных баз данных. http: // www. citforum. ru/ database/ articles/ search sys.shtml. 11. Особенности построения хранилищ данных. http: // citforum. uar.net/ seminars/ cis99/sch.shtml/ 12. Kacprzyk J., Ziolkowski A. Database Queries with Fuzzy Linguistic Quantifiers // IEEE Transactions on Systems, Man, and Cybernetics. SMC-16, 1996. - P. 512-529. 13. Fuzzy Grouping в Microsoft SQL Server 2005 http: // msdn. microsoft.com/ msdnmag/ issues/05/09/ SQLServer2005/ default.aspx. 14. Пелещишин А.М. Методи та алгоритми моделювання Web-систем //Вісник Держ. ун-ту "Львівська політехніка". 2000. - №406. - С.199-211. 15. Черняк Л. Машины для обработки событий. - Открытые системы #09/2006, http://www.osp.ru/os/2006/09/3776498/_p1.html 16. Гіпертекстові Технології, http://moodle.ukma.kiev.ua/mod/resource/view.php?id=1120

 

 

 

УДК 519.15:621.372

 

В.В. Різник, М.Т. Соломко*

Національний університет "Львівська політехніка", *Європейський університет (Рівненська філія), Технологічно-природничий університет, м. Бидгощ (Польща)

СИНТЕЗ КОМБІНАТОРНИХ СИСТЕМ ЗА ДОПОМОГОЮ БАГАТОВИМІРНИХ В'ЯЗАНОК

 

© Різник В.В., Соломко М.Т., 2008

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

Methods for synthesis of combinatorial configurations (BIB-designs) by means of multi­dimensional numerical constructions - so-called Ideal Ring Bundles (IRB)s has been considered. There are proposed algorithms of transition the multi-dimensional IRBs into classic combinatorial configurations. The methods discovers new possibilities for apply of the IRBs into modern combinatorial theory.

 

Вступ

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

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

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

 

Аналіз проблеми та постановка задачі

Найпростішою структурною організацією елементів, що утворює математичний об' єкт під назвою "в'язанка", є одновимірна упорядкована послідовність Kn чисел k1, k2,     ki, kn:

 

З погляду постановки задачі синтезу та дослідження оптимальних комбінаторних моделей особливий інтерес викликають в' язанки з кільцевою структурою, елементами яких є цілі додатні числа, а суми на кільцевій послідовності вичерпують значення чисел натурального ряду від 1 до суми Sn = k1 + k2 + ...+ ki + ...+ kn усіх чисел цієї послідовності. Така числова конструкція називається "ідеальною кільцевою в'язанкою", або скорочено ІКВ.

Наприклад, якщо обрати упорядкований ряд (1,4,2) як кільцеву послідовність чисел, то легко перевірити, що всі кільцеві суми цієї послідовності вичерпують натуральний ряд чисел від 1 до Sn=7:

1=1, 2=2, 3=2+1, 4=4, 5=1+4, 6=4+2, 7=1+4+2.

За допомогою в' язанок можна будувати блок-схеми. Під блок-схемою розуміють розміщення елементів множини {bi }, j=1,2, v в a підмножинах Bj , j =1,2, a, які називаються блоками, з однаковою кількістю елементів kj=k у кожному блоці, причому елемент bi належить до ri різних блоків, а кожна p-та пара різних елементів (bi, bj), p=1,2, v(v-1)/2 повторюється в 1p блоках [1].

До основного виду блок-схем належать зрівноважені неповні блок-схеми (balanced incomplete block design), або BIB-схеми [1]. BIB-схеми утворені на множині v різних елементів == bi^bj) з кількістю елементів k < v у кожному блоці, причому елементи у блоках розміщуються так:

а) всі елементи одного блоку різні;

б) кожний елемент розміщується точно в r різних блоках (ri=r), i=1, 2, ..., v;

в) кожна p-та пара різних елементів (bi, bj), p=1,2, v(v-1)/2 трапляється точно в l різних
блоках
   1p = l.

Між параметрами v, a, k, r, l BIB-схеми існують залежності

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

Числову в'язанку можна розглядати як структурований код, за допомогою якого зручно синтезувати відповідну комбінаторну систему. Методи побудови BIB-схем за допомогою одновимірних числових в' язанок розглядаються в [1,2].Перехід від одновимірних до багатовимірних числових конструкцій є логічним продовженням дослідження організації комбінаторних систем. У багатовимірних числових конструкціях-в'язанках відповідні ланцюжки операцій здійснюють над векторами багатовимірного простору. При перенесенні дій на послідовності векторів аналогами одновимірних послідовностей постають багатовимірні числові послідовності.

Багатовимірні в'язанки ще мало вивчені. На практиці особливий інтерес становлять методи побудови як самих двовимірних в'язанок, так і похідних конфігурацій за допомогою двовимірних в'язанок. Один з методів побудови двовимірних в'язанок ґрунтується на використанні одновимірних в'язанок [2].

Синтез зрівноважених блок-схем

Нехай задана одновимірна ідеальна кільцева в'язанка (кь k2, ki, kn) з параметрами Sn, n, де Sn=lyl2, /2)=1. Алгоритм побудови двовимірної ІКВ з такими самими параметрами на прямокутнику l1 x l2 містить виконання таких операцій:

  на послідовності Kn = (k1, k2, ki, kn) знайти елементи першого рядка таблиці кільцевих сум одновимірної ІКВ:

{Sj} j = 1, 2,    n; Sj =X k ; (2)

i=1

  на множині елементів {Sj} знайти пари чисел {(a bj)}, j =1, 2, n;

aj ° Sj (modl1),   bj ° Sj (mod l2); (3)

  упорядкувати пари чисел {(aj, bj)} у зростаючому порядку числових значень їх елементів, починаючи з bj, а потім - aj, причому (0,0) записати в кінці упорядкованої послідовності; утворена послідовність ((a;, b;), (a2, b2), (an, bn)) з відповідно перейменованими індексами j =1, 2, n становить перший рядок таблиці кільцевих вектор-сум на n-послідовності елементів шуканої ІКВ;

  визначити елементи двовимірної ІКВ за формулами:

k1 j ° aj - aj-1 (mod l1),  k2j ° bj - bj-1 (modl2) (4)

j = 2,3,...,n; ku = ax, k2l = \ Наприклад,   одновимірна   (21,5,1)-ІКВ   (2,5,1,3,10)   перетворюється   у   двовимірну на прямокутній матриці 3 х 7 після здійснення передбачених розглянутим алгоритмом операцій:

  на послідовності Kn = (2,5,1,3,10) знаходять елементи першого рядка таблиці кільцевих сум одновимірної ІКВ - {2,7,8,11,21};

     на множині елементів записаного рядка за допомогою співвідношень (3) знаходять послідовність ((2,2), (1,0), (2,1), (2,4), (0,0));

  після упорядкування отримують перший рядок таблиці кільцевих сум двовимірної ІКВ:

((1,0), (2,1), (2,2), (2,4), (0,0)); (5)

  за допомогою залежностей (4) визначають елементи двовимірної ІКВ:

((1,0), (1,1), (0,1), (0,2), (1,3)). (6) Побудована за цією послідовністю таблиця кільцевих вектор-сум має такий вигляд:

 

1, 0

2, 1

2, 2

2, 4

0, 0

0, 0

1, 1

1, 2

1, 4

2, 0

2, 6

0, 0

0, 1

0, 3

1, 6

2, 5

0, 6

0, 0

0, 2

1, 5

2, 3

0, 4

0, 5

0, 0

1, 3

Тут кожен із упорядкованих 2-наборів елементів, крім (0,0), трапляється точно по одному разу, де перший елемент набуває значення числового ряду {0, 1, 2}, другий - {0, 1, 2, 3, 4, 5, 6}. Отже, знайдена послідовність утворює двовимірну ІКВ п'ятого (n=5) порядку на прямокутнику 3 х 7. Синтез BIB-схем за допомогою двовимірної в'язанки здійснюють у два етапи.На першому етапі будується BIB-схема за алгоритмом, який викладено в [1].   Для цьогоS

n

двовимірним елементам ІКВ ((a;, b;), (a2, b2), n(n -1)

+1 послідовностей:

R


. •, (am,  bm X


• * * 5


(an, bn))  ставиться у відповідність

£(2)


 

 

a1 b(2)


(a21) Л ^0),

a2

b(2)

(a(1) >

m

b(1) (a(2) >

m

b(2)

(a(1) ЛЛ

n

 

 

(a(2)

n

b(2)VVb1 0


( a2j) Л

Vb2 0


an

Vbn

a

V bm 0

( a (j) Л     ( a (j) Л Лb(Sn )

b(Sn ) Vb2 0

((dSn) Л (a2Sn) Л     (aiSn) Л

Страницы:
1  2  3  4 


Похожие статьи

В В Різник, М Т Соломко - Синтез комбінаторних систем за допомогою багатовимірних в'язанок