46805 (Аналіз топологій)

Зміст

Вступ

Розділ 1. Способи задання топологій

1. Графічний спосіб

2. Матричний спосіб

3. Алгебраїчний спосіб

Розділ 2. Методи виявлення та перетворення топологічних структур

1. Виявлення послідовної топології

2. Виявлення паралельної топології

3. Виявлення топології «дерево»

Висновок

Додатки

Список використаної літератури

Вступ

Топологія – це така структура зв’язків між елементами системи, множина відображень яких є гомоморфною.

Для задання топологій можуть застосовуватись такі способи:

• вербально-дедуктивні;

• графічні;

• матричні;

• аналітичні.

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

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

Аналіз та синтез в класі станів зводиться до формалізованої моделі у вигляді графу станів, у якого вершини відповідають певним станам системи, а дуги – функціям і переходам між цими станами. Можна легко зауважити, що аналіз та синтез систем в класі станів проводиться тоді, коли між станами можливі альтернативні шляхи переходу, тобто ця задача зводиться д аналізу та синтезу структури зв’язків між станами – топології. Спочатку цей підхід використовували в процесі проектування цифрових актоматів, синтезу алгоритмів та програм роботи комп’ютерів, а згодом для розвитку задач синтезу електричних кіл, електричних схем, складих систем керування, а тепер ця задача стає актуальною для синтезу технологічних ліній.

Розділ 1. Способи задання топологій

1. Графічні способи

До графічних способів належать графи та мережі Петрі.

Граф G=(B,E) – це сукупність двох множин (об’єктів): В={b₁,b₂,…,b_n} – скінченна непуста множина вершин (вузлів); D={d₁,d₂,…,d_m} – скінчена множина пар вершин, що з’єднанні між собою і утворюють ребро (дугу) графа G.

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

Якщо топологія системи описується графом, то вершинам графа відповідають елементи системи, а дугам графа – з’єднання між елементами.

Наприклад, для задання топології поліграфічної системи оперативного викуску однокольорових брошур вказана така множина вершин В= {b₁ – комп’ютер, b₂ – дублікатор, b₃ – колатор, b₄ – степлер-фальцовщик, b₅ – одноножовий різак } і така множина пар вершин D={d₁=(b₁ b₂); d₂=(b₂ b₃); d₃=(b₃ b₃); d₄=(b₃ b₄); d₅; d₆=(b₅ b₅)}. В цій системі, орієнтований граф топології якої наведено на рис. 1.1., з’єднання, що відповідає парі вершин), забезпечує передачу інформації про поточну звертальну шпальту видання на дублікатор, який забезпечує друкування цієї шпальти заданим накладом. З’єднання (b₂ b₃) відповідає передачі накладу задрукованої шпальти на колатор. В колаторі проводиться накопичення всіх шпальт брошури. Як тільки буде прийнято від дублікатора наклад останньої шпальти даного видання, тоді він приступить до формування зошитів брошури, що будуть складатися із певної послідовності задрукованих шпальт. Власне цей процес відображений парою вершин (b₃ b₃). Зформований зошит брошури подається в степлер-фальцовщик за допомогою зв’язку, який описується парою вершин (b₃ b₄). Після скріплення та фальцування шпальт брошура через зв’язок, який описується парою вершин (b₄ b₅), подається на одноножовий різак. Парою вершин (b₅ b₅) відображається послідовна обрізка трьох боків брошури. Цілком очевидно, що пара вершин є впорядкованими, тобто (b₁ b₂)≠( b₂ b₁).

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

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

Топологія системи може мати деяку множину елементів, між якими встановлені певні відношення, та іншу множину елементів, між якими не встановлено відношень. Наприклад, для задання топології в комп’ютерно-видавничій системі (КВС) вказана така множина вершин В={b₁ – 1-й комп’ютер, b₂ – 2-й комп’ютер, b₃ – сканер, b₄ – модем, b₄ – лазерна друкарка} і така множина пар вершин D= {d₁ =(b₁,b₂); d₂ =(b₂,b₁); d₃ =(b₂,b₄); d₄ =(b₃,b₁); d₅ =(b₁,b₄); d₆ =(b₂,b₅); d₇ =(b₄,b₁); d₈ =(b₄,b₂)}, для якої (b₁,b₂)= (b₂,b₁), (b₁,b₄)= (b₄,b₁), (b₂,b₄)= (b₄,b₂), але (b₃,b₁)≠ (b₁,b₃) і (b₂,b₃) ≠ (b₅,b₂). Ця топологія буде описуватися змішаним графом, який наведено на рис.1.4.

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

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

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

1.2 Матричні способи

До матричних способів відносяться: матриці (суміжності, інциденції, цикломатичні), n-мірні таблиці (масиви), n-мірні куби.

Матриця суміжності А – це квадратна матриця, що задає топологію системи і має наступний вигляд:

Матрицями суміжності можна задавати топології, що описуються як орієнтованими графами, так і неорієнтованими графами.

Для систем, топологія яких задається орієнтованим графом, розрізняють два типи матриці суміжності з’єднань за виходами.

Матриця суміжності з’єднань за входами – це така матриця суміжності, в якій рядки позначені елементами (номерами елементів) системи, входи яких з’єднані з виходами тих елементів системи, якими позначені стовпці матриці.

Тобто, якщо в цій матриці А_ij=1, то це означає, що вхід і-го елеметна системи з’єднаний з виходом j-го елемента.

Так, наприклад, для топології, що на рис.1.1., матриця суміжності з’єднань за входами А_І буде такою:

Матриця суміжності з’єднань за виходами – це така матриця суміжності, в якій рядки позначені елементами системи, якими розначені стовпчі матриці.

Тобто, якщо в такій матриці a_ij =1, то це означає, що вихід i-го елемента системи з’єднаний з входом j-го елемента.

Для тієї ж топології, що на рис.1.1, матриця суміжності з’єднань за виходами А_о буде такою:

Для задання топології систем, що описується неорієнтованим графом, застосовують тільки одну матрицю суміжності А, яка є об’єднанням матриць А_І та А_о

А= А_І А_О.

Так, наприклад, для топології, що на рис. 1.3, матриця суміжності А буде такою:

Для задання топологій систем іноді застосовують матриці інциденцій

Якщо топологія задається орієнтованим графом G=(B,E), де B={b₁,b₂,…b_n}, D={d₁,d₂,…d_m}, то матриця інциденцій для дуг S матиме такий вигляд:

Наприклад, для топології, що на рис. 1.2., матриця інциденції для дуг S буде такою:

Якщо топологія задається неорієнтованим графом G=(B,E), де B={b₁,b₂,…b_n}, D={d₁,d₂,…d_m}, то матриця інциденцій для ребер R матиме такий вигляд:

Для топології, що на рис 1.3. матриця інциденції для ребер R буде такою:

Цикломатичні матриці, яких ще називають другі матриці інциденції, можуть застосовуватися для опису топологій, що містять v незалежних циклів (контурів). Вони мають такий вигляд: