- •Міністерство освіти та науки України в.В. Литвин, н.Б. Шаховська Проектування інформаційних систем
- •Передмова наукового редактора серії підручників «комп’ютинґ»
- •1.1. Складність програмного забезпечення
- •1.2. Структура складних систем
- •1.2.1. Приклади складних систем
- •1.2.2. П'ять ознак складної системи
- •1.2.3. Організована і неорганізована складність
- •1.3. Методи подолання складності
- •1.3.1. Роль декомпозиції
- •1.3.3. Роль абстракції
- •1.3.4. Роль ієрархії
- •1.4. Про проектування складних систем
- •1.4.1. Інженерна справа як наука і мистецтво
- •1.4.2. Сенс проектування
- •4. Методи подолання складності.
- •2.1. Базові означення
- •2.2. Методи проектування інформаційних систем
- •2.3. Види інформаційних систем
- •2.4. Рівні моделей даних
- •3. Види інформаційних систем.
- •3.1. Методологія процедурно-орієнтованого програмування
- •3.2. Методологія об'єктно-орієнтованого програмування
- •3.3. Методологія об'єктно-орієнтованого аналізу і проектування
- •3.4. Методологія системного аналізу і системного моделювання
- •4.1. Передісторія. Математичні основи
- •4.1.1. Теорія множин
- •4.1.2. Теорія графів
- •4.1.3. Семантичні мережі
- •4.2. Діаграми структурного системного аналізу
- •4.3. Основні етапи розвитку uml
- •3. Семантичні мережі.
- •5.1. Принципи структурного підходу до проектування
- •5.2. Структурний аналіз
- •5.3. Структурне проектування
- •5.4. Методологія структурного аналізу
- •5.5. Інструментальні засоби структурного аналізу та проектування
- •6.1. Основні елементи
- •6.2. Типи зв’язків
- •6.3. Техніка побудови
- •6.4. Діаграма бізнес – функцій
- •6.4.1. Призначення діаграми бізнес-функцій
- •6.4.2. Основні елементи
- •7.1. Призначення діаграм потоків даних та основні елементи
- •7.1.1. Зовнішні сутності
- •7.1.2. Процеси
- •7.1.3. Накопичувачі даних
- •7.1.4. Потоки даних
- •7.2. Методологія побудови dfd.
- •8.1. Діаграма «сутність-зв’язок»
- •8.2. Діаграма атрибутів
- •8.3. Діаграма категоризації
- •8.4. Обмеження діаграм сутність-зв’язок
- •8.5. Методологія idef1
- •9.1. Основні елементи
- •9.2. Типи керуючих потоків
- •9.3. Принципи побудови
- •10.1. Структурні карти Константайна
- •10.2. Структурні карти Джексона
- •11.1. Призначення case-технологій
- •11.2. Інструментальний засіб bPwin
- •11.2.4. Інші діаграми bpWin
- •11.2.5. Моделі as is і to be
- •11.3.1. Основні властивості
- •11.3.2. Стандарт idef1x
- •11.4. Програмний засіб Visio
- •12.1. Системний аналіз області наукових досліджень
- •12.1.1. Аналіз предметної області
- •12.2. Системний аналіз біржі праці
- •12.2.1. Дерево цілей
- •12.2.2. Опис об’єктів предметної області
- •12.2.3. Концептуальна модель
- •14.1. Еволюція об'єктної моделі
- •14.1.1. Основні положення об'єктної моделі
- •14.2. Складові частини об'єктного підходу
- •14.2.1. Парадигми програмування
- •14.2.2. Абстрагування
- •14.2.3. Інкапсуляція
- •14.2.4. Модульність
- •14.2.5. Ієрархія
- •14.2.7. Паралелізм
- •14.2.8. Збереженість
- •14.3. Застосування об'єктної моделі
- •14.3.1. Переваги об'єктної моделі
- •14.3.2. Використання об'єктного підходу
- •14.3.3. Відкриті питання
- •15.1. Природа об'єкта
- •15.1.1. Що є й що не є об'єктом?
- •15.1.2. Стан
- •15.1.3. Поведінка
- •15.1.4. Ідентичність
- •Void drag(DisplayItem I); // Небезпечно
- •15.2. Відношення між об'єктами
- •15.2.1. Типи відношень
- •15.2.2. Зв'язки
- •15.2.3. Агрегація
- •15.3. Природа класів
- •15.3.1. Що таке клас?
- •15.3.2. Інтерфейс і реалізація
- •15.3.3. Життєвий цикл класу
- •15.4. Відношення між класами
- •15.4.1. Типи відношень
- •15.4.2. Асоціація
- •15.4.3. Успадкування
- •15.4.4. Агрегація
- •15.4.5. Використання
- •15.4.6. Інсталювання (Параметризація)
- •15.4.6. Метакласи
- •15.5. Взаємозв'язок класів і об'єктів
- •15.5.1. Відношення між класами й об'єктами
- •15.5.2. Роль класів і об'єктів в аналізі й проектуванні
- •16.1. Важливість правильної класифікації
- •16.1.1. Класифікація й об’єктно-орієнтовне проектування
- •16.1.2. Труднощі класифікації
- •16.2. Ідентифікація класів і об'єктів
- •16.2.1. Класичний і сучасний підходи
- •16.2.2. Об’єктно-орієнтований аналіз
- •16.3. Ключові абстракції й механізми
- •16.3.1. Ключові абстракції
- •16.3.2. Ідентифікація механізмів
- •17.1. Призначення мови uml
- •17.2. Загальна структура мови uml
- •17.3. Пакети в мові uml
- •17.4. Основні пакети мета-моделі мови uml
- •17.5. Специфіка опису мета-моделі мови uml
- •17.6. Особливості зображення діаграм мови uml
- •18.1. Варіант використання
- •18.2. Актори
- •18.3. Інтерфейси
- •18.4. Примітки
- •18.5. Відношення на діаграмі варіантів використання
- •18.5.1. Відношення асоціації
- •13.5.2. Відношення розширення
- •18.5.3. Відношення узагальнення
- •18.5.4. Відношення включення
- •18.6. Приклад побудови діаграми варіантів використання
- •18.7. Рекомендації з розроблення діаграм варіантів використання
- •19.1. Клас
- •19.1.1. Ім'я класу
- •19.1.2. Атрибути класу
- •19.1.3. Операція
- •19.2. Відношення між класами
- •19.2.1. Відношення залежності
- •19.2.2. Відношення асоціації
- •19.2.3. Відношення агрегації
- •19.2.4. Відношення композиції
- •19.2.5. Відношення узагальнення
- •19.3. Інтерфейси
- •19.5. Шаблони або параметризовані класи
- •19.6. Рекомендації з побудови діаграми класів
- •20.1. Автомати
- •20.2. Стан
- •20.2.1. Ім'я стану
- •20.2.2. Список внутрішніх дій
- •20.2.3. Початковий стан
- •20.2.4. Кінцевий стан
- •20.3. Перехід
- •20.3.2. Сторожова умова
- •20.3.3.Вираз дії
- •15.4. Складений стан і підстан
- •20.4.1. Послідовні підстани
- •20.4.2. Паралельні підстани
- •15.5. Історичний стан
- •20.6. Складні переходи
- •15.6.1. Переходи між паралельними станами
- •20.6.2. Переходи між складеними станами
- •20.6.3. Синхронізуючі стани
- •20.7. Рекомендації з побудови діаграм станів
- •21.1. Стан дії
- •21.2. Переходи
- •21.5. Рекомендації до побудови діаграм діяльності
- •22.1.1. Лінія життя об'єкта
- •22.1.2. Фокус керування
- •22.2. Повідомлення
- •22.2.1. Розгалуження потоку керування
- •22.2.2. Стереотипи повідомлень
- •22.2.3. Тимчасові обмеження на діаграмах послідовності
- •22.2.4. Коментарі або примітки
- •22.3. Приклад побудови діаграми послідовності
- •22.4. Рекомендації з побудови діаграм послідовності
- •23.1. Кооперація
- •23.2.1. Мультиоб'єкт
- •23.2.2. Активний об'єкт
- •23.2.3. Складений об'єкт
- •23.3. Зв'язки
- •23.3.1. Стереотипи зв'язків
- •23.4. Повідомлення
- •23.4.1. Формат запису повідомлень
- •23.5. Приклад побудови діаграми кооперації
- •23.6. Рекомендації з побудови діаграм кооперації
- •24.1. Компоненти
- •24.1.1. Ім'я компоненту
- •24.1.2. Види компонент
- •24.2. Інтерфейси
- •24.3. Залежності
- •24.4. Рекомендації з побудови діаграми компонент
- •25.1. Вузол
- •25.2. З'єднання
- •25.3. Рекомендації з побудови діаграми розгортання
- •26.1. Загальна характеристика case-засобу Rational Rose
- •26.2. Особливості робочого інтерфейсу Rational Rose
- •26.1.1. Головне меню програми
- •26.1.2. Стандартна панель інструментів
- •26.1.3. Вікно браузера
- •26.1.4. Спеціальна панель інструментів
- •26.1.5. Вікно діаграми
- •26.1.6. Вікно документації
- •26.1.7. Вікно журналу
- •26.3. Початок роботи над проектом у середовищі Rational Rose
- •26.4. Розроблення діаграми варіантів використання в середовищі Rational Rose
- •26.5. Розроблення діаграми класів у середовищі Rational Rose
- •26.6. Розроблення діаграми станів у середовищі Rational Rose
- •26.7. Розроблення діаграми послідовності в середовищі Rational Rose
- •26.8. Розроблення діаграми кооперації в середовищі Rational Rose
- •26.9. Розроблення діаграми компонентів у середовищі Rational Rose
- •26.10. Розроблення діаграми розгортання в середовищі Rational Rose
4.1.2. Теорія графів
Граф можна розглядати як графічну нотацію для бінарного відношення двох множин. Бінарне відношення складається з таких кортежів або списків елементів, які містять тільки два елементи деякої множини. Хоча основні поняття теорії графів отримали свій розвиток задовго до появи теорії множин як самостійної наукової дисципліни, формальне визначення графа зручно подати в теоретико-множинних термінах.
Графом називається сукупність двох множин: множина крапок або вершин і множина ліній, що сполучають їх, або ребер. Формально граф задається у вигляді двох множин: G=(V, Е), де V={v1v2 ..., vn} – множина вершин графа, а Е={ е1, е2 ..., еm} – множина ребер графа. Натуральне число n визначає загальну кількість вершин конкретного графа, а натуральне число m – загальну кількість ребер графа. Слід відмітити, що у загальному випадку не всі вершини графа можуть з'єднуватися між собою, що ставить у відповідність кожному графові деяке бінарне відношення P, що складається зі всіх пар виду <vi, vj>, де vi, vj є V. При цьому пара <vi, vj> і, відповідно, пара <vj, vi> належать відношенню P в тому і лише в тому випадку, якщо вершини vi і vj з'єднуються в графові G деяким ребром ekєЕ. Вершини графа зображаються крапками, а ребра – відрізками прямих ліній. Поряд з вершинами і ребрами записуються відповідні номери або ідентифікатори, що дозволяють їх ідентифікувати однозначним чином.
Примітка
Взагалі кажучи, графи бувають двох різних типів. Розглянуте вище визначення відноситься до неорієнтованого графа, тобто до такого графа, у якому ребра не мають напряму або орієнтації. Окрім неорієнтованих графів існують орієнтовані графи, які визначаються таким чином.
Орієнтований граф також задається у вигляді двох множин G=(V, E), де V={v1, v2 ...,vn} – множина вершин графа, а E={ е1, е2...,еm] – множина дуг графа. Натуральне число n визначає загальну кількість вершин конкретного графа, а натуральне число m – загальну кількість дуг графа. При цьому кожна дуга еkєЕ орієнтованого графа G має свій початок – деяку єдину вершину viєV і кінець – деяку єдину вершину vjєV. На відміну від ребра, дуга завжди має позначення із стрілкою, яка направлена до кінцевої вершини дуги. Множина дуг ставить у відповідність кожному орієнтованому графові деяке бінарне відношення P, що складається зі всіх пар виду <vi, vj>, де vi, vj є V. При цьому пара <vi, vj> належить відношенню P в тому і лише в тому випадку, якщо вершини vi і vj з'єднуються в графові G деякою дугою еkєЕ з початком у вершині vi і кінцем у вершині vj.
Нижче представлено два приклади конкретних графів (рис. 4.4). При цьому перший з них (рис. 4.4, а) є неорієнтованим графом, а другий (рис. 4.4, б) – орієнтованим графом. Як неважко відмітити, для неорієнтованого графа ребро е1 з’єднює вершини v1 і v2, ребро е2 – вершини v1 і v3, а ребро e3 – вершини v2 і v3 і так далі Останнє ребро, e8, з’єднює вершини v4 і v5, тим самим задається опис графа в цілому. Інших ребер цей граф не містить, як не містить й інших вершин, що не зображаються на рисунку. Так, хоча ребра е6 і e7 візуально перетинаються, але точка їх перетину не є вершиною графа.
Для орієнтованого графа (рис. 4.4, б) ситуація інша. А саме, вершини v1 і v2 з’єднані дугою е1, для якої вершина v2 є початком дуги, а вершина v1 – кінцем цієї дуги. Далі дуга е2 з’єднює вершини v1 і v4, при цьому початком дуги e2 є вершина v1, а кінцем – вершина v4.
Рис. 4.4. Приклади неорієнтованого (а) і орієнтованого (б) графів
Графи широко застосовуються для подання різної інформації про структуру систем і процесів. Прикладами подібних графічних моделей можуть служити: схеми автомобільних доріг, з’єднюють окремі населені пункти; схеми телекомунікацій, використовуваних для передачі інформації між окремими вузлами; схеми програм, на яких вказуються варіанти розгалуження обчислювального процесу. Загальною для всіх конкретних подібних моделей є можливість подання інформації у графічному вигляді у формі відповідного графа. При цьому окремі моделі, як правило, володіють додатковою семантикою і спеціальними позначеннями, характерними для тієї або іншої предметної області.
Важливими поняттями теорії графів є поняття маршруту і шляху, які асоціюються з послідовним переміщенням від вершини до вершини ребрами, що з’єднюють їх, або дугами. Для неорієнтованого графа маршрут визначається як кінцева або нескінченна впорядкована послідовність ребер S=<esl, es2 ..., esk>, таких, що кожні два сусідні ребра мають спільну вершину. Нас цікавитимуть тільки кінцеві маршрути S=<es1, es2 ..., esk>, тобто такі маршрути, які складаються з кінцевого числа ребер. При цьому ребро esl прийнято вважати початком маршруту S, а ребро esk – кінцем маршруту S. Для орієнтованого графа відповідна послідовність дуг S=<es1, es2 ..., esk> називається орієнтованим маршрутом, якщо дві сусідні дуги мають спільну вершину, яка є кінцем попередньої і початком наступної дуги.
Прикладами маршрутів для неорієнтованого графа (рис. 2.4, а) є послідовності ребер: S1=<e1, e2 e5, e8>, S2=<e1, e2, е3, e1>, S3=<e3, e5, e8>. Якщо в маршруті не повторюються ні ребра, ні вершини, як у разі S1 і S3, то такий неорієнтований маршрут називається простим ланцюгом.
Прикладами орієнтованих маршрутів для графа (рис. 2.4, б) є такі послідовності дуг: S1=<e2, e8, e5>, S2=<e3, e7, e6>, S3=<e8, e3, e7, e4, e8>. Якщо в орієнтованому маршруті не повторюються ні ребра, ні вершини, як у випадку S1 і S2, то такий орієнтований маршрут називається шляхом. Останнє поняття також іноді застосовується для позначення простого ланцюга в неорієнтованих графах і для визначення спеціального класу графів, так званих дерев. У загальному випадку дерева служать для графічного подання ієрархічних структур або ієрархій, що займають важливе місце в ООАП.
Деревом в теорії графів називається такий граф D=<V, E>, між будь-якими двома вершинами якого існує єдиний простий ланцюг, тобто неорієнтований маршрут, у якого вершини і ребра не повторюються. Для орієнтованих графів відповідне означення є складнішим, оскільки ґрунтується на виділенні деякої спеціальної вершини v0, яка отримала спеціальну назву кореневої вершини або просто – кореня. У цьому випадку орієнтований граф D=<V, Е> називається орієнтованим деревом або скорочено – деревом, якщо між коренем дерева v0 і будь-якою іншою вершиною існує єдиний шлях, що бере початок в v0. Нижче представлено два приклади дерев: неорієнтованого дерева (рис. 4.5, а) і орієнтованого дерева (рис. 4.5, б).
Рис. 4.5. Приклади неорієнтованого (а) і орієнтованого (б) дерев
У випадку неорієнтованого дерева (рис. 4.5, а) будь-яка з вершин графа може бути вибрана як корінь. Подібний вибір визначається специфічними особливостями вирішуваного завдання. Так, вершина v1 може розглядатися як корінь неорієнтованого дерева, оскільки між v1 і будь-якою іншою вершиною дерева завжди існує єдиний простий ланцюг.
Для випадку орієнтованого дерева (рис. 4.5, б) вершина v2 є єдиним його коренем і має спеціальне позначення v0. Єдиність кореня в орієнтованому дереві отримується з того факту, що орієнтований шлях завжди має єдину вершину, яка є його початком. Оскільки в теорії графів має значення тільки наявність або відсутність зв'язків між окремими вершинами, дерева, як правило, зображаються спеціальним чином у вигляді ієрархічної структури. При цьому корінь дерева зображається самою верхньою вершиною в цій ієрархії. Далі слідують вершини 1-го рівня, які пов'язані з коренем одним ребром або однією дугою. Наступний рівень матиме номер 2, оскільки відповідні вершини повинні бути пов'язані з коренем двома послідовними ребрами або дугами. Процес побудови ієрархічного дерева продовжується до того моменту, поки не будуть розглянуті вершини, які не пов'язані з іншими вершинами, окрім розглянутих, або з яких не виходить жодна дуга. У цьому випадку самі нижні вершини іноді називають листям дерева. Важливо мати на увазі, що в теорії графів дерево "росте" вниз, а не вгору, як в реальному житті.
Зображені вище дерева (рис. 4.5) можна перетворити до виду ієрархій. Наприклад, неорієнтоване дерево (рис. 4.5, а) може бути представлене у вигляді ієрархічного дерева таким чином (рис. 4.6, а). У цьому випадку коренем ієрархії є вершина v1. Орієнтоване дерево (рис. 4.5, б) також може бути зображене у формі ієрархічного дерева (рис. 4.6, б), проте таке подання є єдиним.
Рис. 4.6. Ієрархічні схеми неорієнтованого дерева (а) і орієнтованого дерева (б)
У першому випадку (рис. 4.6, а) вершина v2 утворює перший рівень ієрархії, вершини v4 і v3 – другий рівень ієрархії, вершина v5 – третій і останній рівень ієрархії. При цьому листям даного неорієнтованого дерева є вершини v3 і v5. У другому випадку (рис. 4.6, б) вершини v1 і v5 утворюють перший рівень ієрархії, вершини v4 і v6 – другий рівень ієрархії, вершина v3 – третій і останній рівень ієрархії. Листям даного орієнтованого дерева є вершини v3 і v6.
На закінчення слід відмітити, що в теорії графів розроблені різні методи аналізу окремих класів графів і алгоритми побудови спеціальних графічних об'єктів, розгляд яких виходить за рамки цієї книги. Для отримання додаткової інформації з цієї теми можна рекомендувати звернутися до спеціальної літератури з теорії графів, де ці питання розглянуті детальніше. Надалі нас цікавитиме окремий напрям в теорії графів, який пов'язаний з явним включенням семантики в традиційні позначення і самостійний розвиток у формі семантичних мереж.