Розрахунок найкоротшого шляху графу за алгоритмом Дейкстри

РОЗРАХУНОК І ОПТИМІЗАЦІЯ МЕРЕЖ.

СИНТЕЗ АВТОМАТІВ.

 

Виконала:

студентка групи Саіт-09

Безродня Анна

Перевірив:

доцент кафедри СаіУ

Одновол Н.Н.

 

Дніпропетровськ. 2010

Зміст

 

1. Вступ.

3

2. Розділ 1

1.1 Розрахунок найкоротшого шляху графу за алгоритмом Дейкстри.

4

 

1.2 Розрахунок максимального потоку в мережі за алгоритмом Форда-Фалкерсона.

9

 

1.3 Розрахунок мережевого графу.

12

 

3. Розділ 2

2.1 Мінімізація логічної функціїї аналітичним методом та за допомогою карт Карно.

17

 

4. Розділ 3

3.1 Синтез кінцевого автомату.

19

 

5. Розділ 4

4.1 Представлення оператора Паскаля While за допомогою КС-граматики.

4.2 Представлення оператора Паскаля While у формі Бекуса.

6. Розділ 5

5.1 Зіставлення програми: алгоритм Форда Фалкерсона.

29

 

7. Висновок

31

 

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

32

 

 

 

Вступ

 

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

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

Для кількісного аналізу та обчислювальних перетворень неперерних процесів доводиться їх «дискретизувати». Зрозуміло, що математичні методи обробки, аналізу та перетворення дискретної інформації необхідні у всії галузях. Часто для аналізу реальних систем з неперерними конструктивними елементами будуються моделі скінченної або дискретної математики

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

 

 

Розділ 1.

Розрахунок найкоротшого шляху графу за алгоритмом Дейкстри.

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

Розгляно даний алгоритм для даного графу.

 

 

Рис.1.1.1

Вершина 1 – джерело. Вершина 9 –стік.

 

1)Пофарбуємо вершину 1. Покладемо, що d(1)=0,

d(2)=d(3)=d(4)=d(5)=d(6)=d(7)=d(8)=d(9)=∞

 

 

Рис.1.1.2

 

2) Поточна змінна y=1.

d(2)=min{d(2);d(1) + d(1,2)}= min{∞;0+5}=5

d(3)=min{d(3);d(1) + d(1,3)}= min{∞;0+4}=4

d(4)=min{d(4);d(1) + d(1,4)}= min{∞;0+5}=5

d(5)=d(6)=d(7)=d(8)=d(9)= ∞

min{d(2);d(3);d(4);d(5);d(6);d(7);d(8);d(9)}=min{5,4,5, ∞;∞;∞;∞;∞}=4

Мінімум в вершині 3. Фарбуємо її.

 

 

Рис.1.1.3

3) Поточна змінна y=3.

d(2)=min{d(2);d(1) + d(1,2)}= min{∞;0+5}=5

d(4)=min{d(4);d(1) + d(1,)}= min{∞;0+5}=5

d(6)=min{d(6);d(3) + d(3,6)}= min{∞;4+7}=11

d(5)=d(7)=d(8)=d(9)= ∞

min{d(2);d(4);d(5);d(6);d(7);d(8);d(9)}=min{5;5;11;∞;∞;∞;∞}=5

Мінімум в вершинах 2 і 4. Фарбуємо їх.

 

Рис.1.1.4

 

4) Поточні змінні y=2 і y=4.

d(5)=min{d(5);d(2) + d(2,5)}= min{∞;5+7}=12

d(6)=min{d(6);d(3) + d(3,6)}= min{∞;4+7}=11

d(7)=min{d(7);d(4) + d(4,7)}= min{∞;5+5}=10

d(8)=d(9)= ∞

min{d(5);d(6);d(7);d(8);d(9)}=min{12;11;10;∞;∞}=10

Мінімум в вершині 7. Фарбуємо її.

 

 

Рис.1.1.5

 

5) Поточна змінна y=7.

d(5)=min{d(5);d(2) + d(2,5)}= min{∞;5+7}=12

d(6)=min{d(6);d(3) + d(3,6)}= min{∞;4+7}=11

d(8)=d(9)= ∞

min{d(5);d(6);d(8);d(9)}=min{12;11;∞;∞}=11

Мінімум в вершині 6. Фарбуємо її.

 

Рис.1.1.6

 

6) Поточна змінна y=6.

d(5)=min{d(5);d(2) + d(2,5)}= min{∞;5+7}=12

d(8)=min{d(8);d(6) + d(6,8)}= min{∞;11+2}=13

d(9)= min{d(9);d(6)+d(6,9)}=min{∞;11+4}=15

min{d(5);d(8);d(9)}=min{12;13;15}=12

Мінімум в вершині 5. Фарбуємо її.

 

 

Рис.1.1.7

 

 

7) Поточна змінна y=5.

d(8)=min{d(8);d(5)+d(5,8);d(6) + d(6,8)}= min{∞;12+3;11+2}=13

d(9)= min{d(9);d(6)+d(6,9);d(7)+d(7,9)}=min{∞;11+4;10+4}=14

min{d(8);d(9)}=min{13;14}=14

Мінімум в вершині 8. Фарбуємо її.

 

Рис.1.1.8

 

 

8) Поточна змінна y=8.

d(9)= min{d(9);d(6)+d(6,9);d(7)+d(7,9);d(8);d(8)+d(8,9)}=min{∞;11+4;10+4;13+6}=14

Мінімум в вершині 9. Фарбуємо її.

 

 

Рис.1.1.9

 

Вершина 9 пофарбована – алгоритм закінчує свою дію.

 

Найкоротший шлях із джерела до стоку лише один і він складається з таких дуг (1,4);(4,7);(7,9) і довжина шляху дорівнює 16 одиниць.

 

Рис.1.1.10