Тривіальні і повні графи.

Означення. Граф, що складається з однієї вершини, називається тривіальним.

Означення. Граф, що має максимально можливе число ребер називається повним.

2) Дерево і ліс.

Означення.Деревом називається зв'язний ациклічний неорієнтований граф, Дерево не містить петель і кратних ребер.

Приклад.

 

 

Властивості дерев.

1. Щоб простий зв'язний граф був деревом, необхідно й достатньо, щоб число вершин було більше числа ребер на одиницю.

2. Щоб граф був деревом, необхідно й достатньо, щоб будь-які дві його вершини з'єднувалися єдиним маршрутом.

3. Граф буде деревом тоді й тільки тоді, коли додавання будь-якого нового ребра приводить до появи рівно одного циклу.

Означення. Остовним деревом для графа  називається остовний підграф, який є деревом.

Означення. Лісом називається незв'язний неорієнтований граф без циклів, в якому кожна зв'язна компонента є деревом.

Будь-яка частина дерева або ліса також є деревом або лісом. Будь-який ланцюг у такому графі простий (інакше він містив би цикл).

 

Дерево з коренем.

Виділимо в дереві  вершину . Цю вершину називають коренем дерева , а саме дерево називають деревом з коренем. У дереві з коренем можна природним чином орієнтувати ребра. Вершину  ребра  можна з'єднати єдиним ланцюгом з коренем . Якщо цей ланцюг не містить ребра , то вводиться орієнтація від  к , в противному випадку – від  до . Орієнтоване в такий спосіб дерево з коренем називається орієнтованим деревом. У ньому всі ребра мають напрямок від кореня:

 

 

                                

 

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

Будь-яке дерево можна орієнтувати, вибравши як корінь будь-яку його вершину.

 

Тема 5. Елементи теорії алгоритмів

Інтуїтивне означення алгоритму. Приклади алгоритмів.

Блок-схеми алгоритмів.

Простими прикладами алгоритмів є відомі ще з початкової школи методи додавання і множення цілих невід’ємних чисел “стовпчиком” і ділення “куточком”. Інші алгоритми: алгоритм Евкліда знаходження НСД двох чисел, алгоритм розкладання числа на прості множники; спосіб побудови трикутника за трьома заданими сторонами; метод послідовного виключення невідомих при розв’язуванні систем лінійних алгебраїчних рівнянь; правило диференціювання складеної функції, та інші.

Означення.Алгоритмом називається процес, якому притаманні наступні властивості:

1. Наявність даних: вихідних (входів), проміжних і результатів (виходів).

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

3. Елементарність кроку: операції, які виконуються на кожнім кроці, повинні бути відносно простими і локальними.

4. Детермінованість: множина даних, одержуваних у якийсь (не початковий) момент часу, однозначно визначається множиною даних, отриманих у попередній момент часу.

5. Результативність: зупинка після скінченого числа кроків ( що залежить від даних) із указівкою того, що вважати результатом.

6. Масовість: множина вихідних даних повинна вибиратися з деякої потенціально нескінченної множини. Іншими словами, алгоритм повинний вирішувати масову проблему, тобто клас однотипних задач.

Варто розрізняти:

1) опис алгоритму (інструкцію чи програму)

2) механізм реалізації алгоритму (наприклад, ЕОМ), що включає засоби пуску, зупинки, реалізації елементарних кроків, видачі результатів і забезпечення детермінованості, тобто керування ходом обчислення.

3) процес реалізації алгоритму, тобто послідовність кроків, що буде породжена при застосуванні алгоритму до конкретних даних.

Будемо припускати, що опис алгоритму і механізм його реалізації скінченні. Вимога скінченності процесу реалізації збігається з вимогою результативності.

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

Вершини блок-схеми можуть бути двох видів:

1) оператори, з них виходить одне ребро

2) логічні умови, з яких виходить 2 ребра.

Крім того, існує єдиний оператор кінця, з якого не виходить жодне ребро і єдиний оператор початку.

Важлива особливість блок-схеми полягає в тому, що зв’язки, які вона описує, не залежать від того, чи є кроки елементарними чи являють собою самостійні алгоритми, так звані блоки. Можливість розбивати великий алгоритм на блоки широко використовується в програмуванні. І навпаки, за допомогою блок-схем можна декілька алгоритмів, розглянутих як блоки, зв'язати в один великий алгоритм.

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

 

 

⇐ Предыдущая1234567Следующая ⇒

Поделиться: