Курсовая работа: Аналіз топологій

Вступ

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

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

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

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

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

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

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

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

Висновок

Додатки

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

Вступ

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

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

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

- графічні;

- матричні;

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

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

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

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

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

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. Дуга в неорієнтованому графі не має стрілок або має відразу дві стрілки на кінцях.

--> ЧИТАТЬ ПОЛНОСТЬЮ <--