Зміст
Вступ
Розділ 1. Способи задання топологій
1.1. Графічнийспосіб
1.2. Матричнийспосіб
1.3. Алгебраїчнийспосіб
Розділ 2. Методи виявлення таперетворення топологічних структур
2.1. Виявленняпослідовної топології
2.2. Виявленняпаралельної топології
2.3. Виявленнятопології «дерево»
Висновок
Додатки
Список використаної літератури
Вступ
Топологія – це така структура зв’язківміж елементами системи, множина відображень яких є гомоморфною.
Для заданнятопологій можуть застосовуватись такі способи:
- вербально-дедуктивні;
- графічні;
- матричні;
- аналітичні.
Вербально-дедуктивнийабо словесно-логічний спосіб застосовується, як правило, на початкупроектування систем, найчастіше на етапі формування технічного завдання. Цейнайбільш простий і доступний спосіб для різних спеціалістів, які можуть бутизалучені до створення систем, не маючи спеціальних знань. Однак, цей спосібпрактично не має наочності і зовсім не придатний для проведення певнихформальних перетворень топологій як ручним, так і автоматичним (машинним)способом. Якщо цим способом вдається описати топологію системи лаконічно, тоопис, як правило, є неповним і вимагає від спеціалістів попередньогоуточненняосновних понять та положень.
Як відомо, задачіаналізу топологій зводяться до виявлення в графах різних шляхів між початковимита кінцевими станами, контурів чи циклів, остові дерева, множини станів(вершин) чи дуг, що задовільняють певні умови тощо. Проте, ці методи аналізутопологій, що базуються на графах, є фактично ручними методами і не зовсімпідходять до машинних методів, які використовуються длоя побудови програмнихпродуктів, оскільки графи в комп’ютерах не можуть безпосередньо вводитися,опрацьовуватися чи зберігатися в пам’яті. Найбільш придатними для цього єматричні методи аналізу та синтезу топологій. Однак, ці матричні методи в основномуорієнтовані на зв’язок тільки деяких класичних задач (пошук контурів, украдкиграфів, перетворення матриць до певного виду, тощо) територій графів. Окреміспособи були зроблені в розвитку матричних методів для синтезу систем керуваннята мінімізації логічних функцій, але цілісного підходу до створення матричнихметодів для аналізу та синтезу систем, зокрема комп’ютернихвидавничо-поліграфічних не було.
Аналіз та синтезв класі станів зводиться до формалізованої моделі у вигляді графу станів, уякого вершини відповідають певним станам системи, а дуги – функціям і переходамміж цими станами. Можна легко зауважити, що аналіз та синтез систем в класістанів проводиться тоді, коли між станами можливі альтернативні шляхи переходу,тобто ця задача зводиться д аналізу та синтезу структури зв’язків між станами –топології. Спочатку цей підхід використовували в процесі проектування цифровихактоматів, синтезу алгоритмів та програм роботи комп’ютерів, а згодом длярозвитку задач синтезу електричних кіл, електричних схем, складих системкерування, а тепер ця задача стає актуальною для синтезу технологічних ліній.
Розділ1. Способи задання топологій
1.1. Графічніспособи
До графічнихспособів належать графи та мережі Петрі.
Граф G=(B,E) – це сукупність двох множин(об’єктів): В={b1,b2,…,bn} – скінченна непуста множина вершин(вузлів); D={d1,d2,…,dm} – скінчена множина пар вершин, щоз’єднанні між собою і утворюють ребро (дугу) графа G.
Якщо пара вершинупорядковані, то граф називається орієнтованим (орграфом), в іншому випадку –неорієнтованим. Ребра (дуги) із множини D в орієнтованому графі зазвичай маютьстрілку.
Якщо топологіясистеми описується графом, то вершинам графа відповідають елементи системи, адугам графа – з’єднання між елементами.
Наприклад, для заданнятопології поліграфічної системи оперативного викуску однокольорових брошурвказана така множина вершин В= {b1 – комп’ютер, b2 – дублікатор, b3 – колатор, b4 – степлер-фальцовщик, b5 – одноножовий різак } і така множинапар вершин D={d1=(b1 b2); d2=(b2 b3); d3=(b3 b3); d4=(b3 b4); d5; d6=(b5 b5)}. В цій системі, орієнтований графтопології якої наведено на рис. 1.1., з’єднання, що відповідає парі вершин),забезпечує передачу інформації про поточну звертальну шпальту видання надублікатор, який забезпечує друкування цієї шпальти заданим накладом. З’єднання(b2 b3) відповідає передачі накладузадрукованої шпальти на колатор. В колаторі проводиться накопичення всіх шпальтброшури. Як тільки буде прийнято від дублікатора наклад останньої шпальтиданого видання, тоді він приступить до формування зошитів брошури, що будутьскладатися із певної послідовності задрукованих шпальт. Власне цей процесвідображений парою вершин (b3 b3). Зформований зошит брошуриподається в степлер-фальцовщик за допомогою зв’язку, який описується пароювершин (b3 b4). Після скріплення та фальцуванняшпальт брошура через зв’язок, який описується парою вершин (b4 b5), подається на одноножовий різак.Парою вершин (b5 b5) відображається послідовна обрізкатрьох боків брошури. Цілком очевидно, що пара вершин є впорядкованими, тобто (b1 b2)≠( b2 b1).
/>
Прикладорієнтованого графа більш складної топології системи показаний на рис.1.2., вякому вершини позначені просто числами.
Якщо в топологіїсистеми пари елементів, що з’єднані між собою, не впорядковані, тобто міжпарами встановлений зв’язок від одного елемента до іншого і навпаки (наприклад,з’єднання в комп’ютерно-видавничій системі комп’ютер-модем, модем-комп’ютертощо), то така топологія задається неорієнтованим графом. Приклад такого графає на рис.1.3. Дуга в неорієнтованому графі не має стрілок або має відразу двістрілки на кінцях.
Топологія системиможе мати деяку множину елементів, між якими встановлені певні відношення, таіншу множину елементів, між якими не встановлено відношень. Наприклад, длязадання топології в комп’ютерно-видавничій системі (КВС) вказана така множинавершин В={b1 –1-й комп’ютер, b2 – 2-й комп’ютер, b3 – сканер, b4 – модем, b4 – лазерна друкарка} і така множинапар вершин D= {d1 =(b1,b2); d2 =(b2,b1); d3 =(b2,b4); d4 =(b3,b1); d5 =(b1,b4); d6 =(b2,b5); d7 =(b4,b1); d8 =(b4,b2)}, для якої (b1,b2)= (b2,b1), (b1,b4)= (b4,b1), (b2,b4)= (b4,b2), але (b3,b1)≠ (b1,b3) і (b2,b3) ≠ (b5,b2). Ця топологія буде описуватисязмішаним графом, який наведено на рис.1.4.
/>
/>
/>
/>
Основноюперевагою графічного способу завдання топологій систем з одного боку це високанаочність безпосереднього відображення структури зв’язків між елементамисистеми, а з другого – достатньо розроблені в теорії графів методи їхопрацювання. Проте, графічний спосіб має й певні недоліки. По-перше, цетруднощі автоматичного опрацювання графів в комп’ютерах, що пов’язані зпопереднім розпізнаванням графічних образів та потреба великих обсягів пам’ятідля зберігання графів. По-друге, це труднощі відображення топологій систем звеликою кількістю (понад 30) елементів і як наслідок – втрата наочності.По-третє, одна і та ж топологія системи може бути задана великою кількістюеквівалентних графів із різним геометричним зображенням. Так, наприклад,топологія системи, що відображена на рис.1.1., може мати інше еквівалентне(гомоморфне) зображення, що наведене на рис.1.5., і таке не відразу може бутисприйняте як відображення однакової топології.
Власне томуграфічний спосіб задання, як правило, використовується для первинного описутопологій з невеликою кількістю елементів перед введенням топологій систем вкомп’ютер, а також для перевірки (верифікації) розроблених методів опрацюванняпри інших способах задання.
Щодо мереж Петрі,то вони застосовуються переважно для опису та моделювання систем знедетермінованою поведінкою, елемиенти яких функціонують незалежно івзаємодіють час від часу. За допомогою мереж Петрі описують як стани системи,так і дії її складових елементів. З цих міркувань застосовувати мережі Петрідля задання топологій систем недоцільно.
1.2Матричні способи
До матричнихспособів відносяться: матриці (суміжності, інциденції, цикломатичні), n-мірні таблиці (масиви), n-мірні куби.
Матрицясуміжності А– це квадратна матриця, що задає топологію системи і має наступний вигляд:
/>
Матрицямисуміжності можна задавати топології, що описуються як орієнтованими графами,так і неорієнтованими графами.
Для систем,топологія яких задається орієнтованим графом, розрізняють два типи матрицісуміжності з’єднань за виходами.
Матрицясуміжності з’єднань за входами – це така матриця суміжності, в якій рядки позначеніелементами (номерами елементів) системи, входи яких з’єднані з виходами тихелементів системи, якими позначені стовпці матриці.
Тобто, якщо в ційматриці Аij=1, то це означає, що вхіді-го елеметна системи з’єднаний з виходом j-го елемента.
Так, наприклад,для топології, що на рис.1.1., матриця суміжності з’єднань за входами АІбуде такою:
/>
Матриця суміжності з’єднаньза виходами– це така матриця суміжності, в якій рядки позначені елементами системи, якимирозначені стовпчі матриці.
Тобто, якщо втакій матриці aij=1, то це означає, що вихід i-го елемента системи з’єднаний звходом j-го елемента.
Для тієї жтопології, що на рис.1.1, матриця суміжності з’єднань за виходами Ао будетакою:
/>
Для заданнятопології систем, що описується неорієнтованим графом, застосовують тільки однуматрицю суміжності А, яка є об’єднанням матриць АІ та Ао
А= АІ/>АО.
Так, наприклад,для топології, що на рис. 1.3, матриця суміжності А буде такою:
/>
Для заданнятопологій систем іноді застосовують матриці інциденцій
Якщо топологіязадається орієнтованим графом G=(B,E), де B={b1,b2,…bn}, D={d1,d2,…dm}, то матриця інциденцій для дуг S матиме такий вигляд:
/>
Наприклад, длятопології, що на рис. 1.2., матриця інциденції для дуг S буде такою:
/>
Якщо топологіязадається неорієнтованим графом G=(B,E), де B={b1,b2,…bn}, D={d1,d2,…dm}, то матриця інциденцій для ребер R матиме такий вигляд:
/>
Для топології, щона рис 1.3. матриця інциденції для ребер R буде такою:
/>
Цикломатичніматриці, яких ще називають другі матриці інциденції, можуть застосовуватися дляопису топологій, що містять v незалежних циклів (контурів). Вони мають такий вигляд:
/>
Так, наприклад,для топології, що на рис. 1.3., цикломатична матриця С, що має один незалежнийконтур, буде такою:
/>
Можна легкозауважити, що для задання топології цикломатичні матриці є непридатними, бо увипадку відсутності в топології контурів, що часто буває в топологічнихсистемах, такі матриці містять лише нулі, а тому топології не описують.
Матриціінциденції можуть застосовуватися для задання топологій систем, але вони неможуть задавати топології, що містять петлі – контури, що складаються лише зодного елемента. Наприклад, скласти матрицю інциденції для топології (рис.1.1.)є проблематичним. Крім того, елементи таких матриць можуть приймати одне із трьохзначень +1,1,0, а тому для перетворення матриць інциденції з метою аналізузаданих топологій потрібно застосовувати або звичайні алгебраїчні операції, якіє більш трудомісткі, ніж логічні операції двійкової алгебри логіки, абооперації трійкової алгебри логіки, які хоч менш трудомісткі від звичайнихоперацій, але складніші від операційбулевої алгебри. З цих міркувань монографіїдля задання топологой систем застосовуються лише матриці суміжності.
Перевагазастосування матриці суміжностей полягає у зручності представлення, опрацюваннята зберігання в комп’ютерах топологій з довільною кількістю елементів. Такіматриці в комп’ютерах записуються як масиви або списки зв’язності, що очевидноє для них найбільш природним представленням. Враховуючи також і те, що елементиматриць суміжностей приймають тільки два значення, то над ними зручнозастосовувати менш трудомісткі операції алгебри логіки та інші спеціальні дляаналізу топології систем.
Єдиним, алесуттєвим, недоліком матричних способів задання топологій є низька наочність.Тому, для виведення на екран монітора результатів аналізу топологій увідповідних програмах необхіджно передбачити перетворення матриць у графи.
1.3 Аналітичний спосіб
До аналітичнихспособів задання топологій систем можна віднести логічні схеми алгоритмів(ЛСА). ЛСА спочатку були розролені для компактного опису процесу функціонуванняцифрових пристроїв у вигляді формул, що можуть складатися з двох об’єктів –операторів та логічних умов. Оператори, як правило, позначаються великимилатинськими літерами з індексами чи без них, а логічні умови – малимилатинськими буквами (з індексами чи без них) та пронумерованими стрілками, щорозміщуються праворуч від логічних умов. Ці стрілки вказують альтернативнімаршрутипереходів при різних значеннях логічних умов. ЛСА формується як деякасистема послідовностей запису з цих об’єктів, в кожній з яких виконанняоператорів проводиться послідовно, починаючи зліва.
Якщо операторамЛСА поставити у відповідність елементи топології системи, то можна отримати її аналітичнийопис. Так, наприклад, для топологій (рис.1.2.) аналітичний опис матиме такийвигляд:
/>
Логічні умови р1-р3виконують функції комутування з’єднань між елементами системи у тому випадку,коли деякий елемент системи з’єднаний одночасно з декількома іншими.
Цілком очевидно,що основна перевага аналітичного способу – це компактність запису топологіїсистеми у вигляді системи формул. У зв’язку з цим, його інколи зручновикористовувати в теоретичних дослідженнях. Однак, є ряд суттєвих недоліків, асаме: труднощі введення, опрацювання та зберігання в комп’ютерах топологійсистем, а також низька наочість представлення топологій. Крім того, виникаютьдодаткові проблеми при заданні аналітичним способом топологій систем, щоописуються неорієнтованими графами.
Якщо дляпорівняння описаних способів задання топологій взяти такі два параметри, яккількість елементів N, з якихскладається система, та кількість систем S, топології яких повинні бути задані,то отримаємо співвідношення, наведені на рис.1.6.
/>
Таким чином, длязадання топологій систем доцільно використовувати одночасно два способи –графічний для побудови інтерфейсу користувача з метою спрощення процесівстворення, введення, коригування топології систем та виведення синтезованоїтопології та матричний (матриці суміжності) для проведення аналізу,перетворення, зберігання топології в комп’ютері. Аналітичний спосіб не доцільнозастосовувати, бо він об’єднує недоліки графічного та матричного.
Розділ2. Методи виявлення та перетворення топологічних структур
Відомі методианалізу топологій є або евристичними, особливо для представлення топологійграфами, або такими, що базуються на комбінаториці, а відтак передбачаютьзначні затрати часу на виконання великої кількостіпорівнянь.
2.1Виявлення послідовної топології
Послідовноютопологієюназивається така топологія систем, яка містить n- елементів, серед яких є одинвхідний елемент, один вихідний елемент, а решта елементів з’єднані з ними такимчином, що від вхідного елемента до вихідного є лише один маршрут з’єднань(рис.2.1.).
/>
Нехай графічнозадана така послідовна топологія (рис.2.2.).
/>
Матрицясуміжності з’єднань за входами АІ цієї топології буде такою:
/>
А матрицясуміжності з’єднань за виходами А0буде такою:
/>
На рис.2.3.наведено алгоритм виявлення послідовних топологій, в основу якого покладеноаналіз матриці суміжності. В ньому, крім попередніх та загальновідомихпозначень, прийнято, що і – номер рядка матриці суміжності, j – номер стовпця матриці суміжності,р – кількість нульових рядків матриці суміжності.
/>
2.2Виявлення паралельної топології
Паралельноютопологієюназивається така топологія системи, яка містить n елементів, кожен з яких не маєжодних зв’язків з іншими (рис.2.4.)
Нехай графічнозадана топологія, що наведена на рис.2.5.
Для цієїтопології матриця суміжності з’єднань за входами АІ і матрицясуміжностей за виходами Ао буде нульовою:
/>
/>
/>
На рис.2.6.наведено алгоритм виявлення паралельних топологій, в основу якого покладеноаналіз матриці суміжності.
/>
2.3Виявлення топології «дерево»
Топологією«дерево»називається така топологія системи, яка містить n елементів (n≥3), серед яких є один вхіднийелемент, та m вихідних ((n-1)≥m>1), причому від вхідного докожного з вихідних елементів є лише один маршрут з’єднання (рис.2.7.).
Топологією«дзеркальне дерево» називається така топологія системи, яка містить n елементів (n≥3), серед яких є m вхідних елементів ((n-1)≥m>1) та один вхідний елемент, а відкожного вхідного елемента до вихідного є лише один маршрут з’єднань (рис.2.8.).
/>
/>
Нехай графічнозадана така топологія «дерево» (рис.2.9)
/>
Матрицясуміжності АІ цієї топології буде такою:
/>
а матрицясуміжності Ао буде такою:
/>
На рис.2.10. yаведено алгоритм виявлення топології«дерево», в осноку якого покладено аналіз матриці суміжності.
Алгоритмвиявлення топології «дзеркальне дерево» аналогічний алгоритму виявленнятопології «дерева» лише з однією відміністю, а саме в першій вершині графазамість операції А: — AI повинна бути операція А: = AO.
/>
Висновок
Отже, топологія –це така структура зв’язків між елементами системи, множина відображень яких єгомоморфною.
Топологію можназадавати за допомогою вербально-дедуктивного, графічного, матричного тааналітичного способу.
До графічнихспособів належать графи та мережі Петрі.
Основноюперевагою графічного способу завдання топологій систем з одного боку це високанаочність безпосереднього відображення структури зв’язків між елементамисистеми, а з другого – достатньо розроблені в теорії графів методи їхопрацювання. Проте, графічний спосіб має й певні недоліки. По-перше, цетруднощі автоматичного опрацювання графів в комп’ютерах, що пов’язані зпопереднім розпізнаванням графічних образів та потреба великих обсягів пам’ятідля зберігання графів. По-друге, це труднощі відображення топологій систем звеликою кількістю (понад 30) елементів і як наслідок – втрата наочності.По-третє, одна і та ж топологія системи може бути задана великою кількістюеквівалентних графів із різним геометричним зображенням.
До матричнихспособів відносяться: матриці (суміжності, інциденції, цикломатичні), n-мірні таблиці (масиви), n-мірні куби.
Перевагазастосування матриці суміжностей полягає у зручності представлення, опрацюваннята зберігання в комп’ютерах топологій з довільною кількістю елементів. Такіматриці в комп’ютерах записуються як масиви або списки зв’язності, що очевидноє для них найбільш природним представленням. Враховуючи також і те, що елементиматриць суміжностей приймають тільки два значення, то над ними зручнозастосовувати менш трудомісткі операції алгебри логіки та інші спеціальні дляаналізу топології систем.
Єдиним, алесуттєвим, недоліком матричних способів задання топологій є низька наочність.Тому, для виведення на екран монітора результатів аналізу топологій увідповідних програмах необхіджно передбачити перетворення матриць у графи.
До аналітичнихспособів задання топологій систем можна віднести логічні схеми алгоритмів(ЛСА).
Цілком очевидно,що основна перевага аналітичного способу – це компактність запису топологіїсистеми у вигляді системи формул. У зв’язку з цим, його інколи зручновикористовувати в теоретичних дослідженнях. Однак, є ряд суттєвих недоліків, асаме: труднощі введення, опрацювання та зберігання в комп’ютерах топологійсистем, а також низька наочість представлення топологій. Крім того, виникаютьдодаткові проблеми при заданні аналітичним способом топологій систем, щоописуються неорієнтованими графами.
Додаток1
Текст програмивиявлення послідовної топології
tic
n=15;
A(1:n,1:n)=0;
A(1:n,1:n)=0;
A(1,7)=1;
A(1,13)=1;
A(3,13)=1;
A(3,14)=1;
A(4,15)=1;
A(5,1)=1;
A(6,9)=1;
A(7,3)=1;
A(8,12)=1;
A(9,8)=1;
A(10,11)=1;
A(11,2)=1;
A(12,10)=1;
A(13,4)=1;
A(14,7)=1;
A(15,13)=1;
d=A
p=0;
for i=1:n;
c=d(i,:);
if sum(c)==0;
p=p+1;
if p>1
z=0;
break
end
else
if ~(sum(c)==1)
z=0;
break
end
j=i;
if d(i,j)==1
z=1;
break
end
end
if p==0
z=1;
else
p=0;
for j=1:n
c=d(:,j);
if sum(c)==0
p=p+1;
if p>1
z=0;
else
if j==n
if p==0
z=0;
break
else
z=1;
end
end
end
else
if ~(sum(c)==1)
if j==n
if p==0
z=0;
end
end
end
end
end
end
end
z
toc
Додаток2
Текст програмивиявлення паралельної топології
tic
n=5;
A(1:n,1:n)=0;
A(1,1)=1;
A
c=0;
for i=1:n
for j=1:n
c=c+A(i,j);
end
end
end
if c>0
input(' topologia ne paralelna')
toc
break
end
input('topologia paralelna')
toc
Додаток3
Текст програмивиявлення топології «дерево»
tic
n=7
A (1:n,1:n)=0;
A(1,4)=1;
A(2,4)=1;
A(4,3)=1;
A(5,3)=1
A(6,5)=1;
A(7,5)=1;
d=A
p=0;
z=0;
for i=1:n;
c=d(i,:);
if sum (c)==0;
p=p+1;
if p>1
z=0;
break
end
else
if~(sum(c)==1)
z=0;
break
end
j=i;
if d(i,j)==1
z=0;
break
end
end
if p==0
z=0;
else
p=0
for j=1:n
c=d(:j);
if sum (c)==0
p=p+1;
end
if j==n
if p>1
z=1
else
z=0
end
end
end
end
end
top
if z==1
disp(‘topologia derevo’)
else
disp(‘topologia ne derevo’)
end
Списоквикоhистаної літератури
1. ДунецьР.Б. Аналіз та синтез топологій комп’ютерних видавничо-поліграфічних систем: монографія.– Львів: НВФ “Українські технології”, 2003.
2. ЦилькерБ.Я., Орлов С.А. Организация ЭВМ и систем. – Спб Питер, 2004.
3. Берж К.Теория графов и ее применение. – М.: Иностранная литература, 1962.- 320 с.
4. Оре О.Теория графов. – М.: Наука, 1980.-336 с.
5. ДунецьР., Басюк Т. Структура програми перетворення графів в ярусно- паралельнуформу//Комп’ютерні технології друкарства. – 2002. — №7. – С.97-102.
6. КапитоноваЮ.В., Летичевский А.А. Математическая теория вычислительных систем. – М.: Наука,1988. – 295 с.
7. ШатихинЛ.Г. Структурные матрицы и их применение для исследования систем. – М.:Машиностроение, 1991. – 253 с.