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

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

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

Виконала:

студентка групи Саіт-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