Розрахунок найкоротшого шляху графу за алгоритмом Дейкстри
РОЗРАХУНОК І ОПТИМІЗАЦІЯ МЕРЕЖ.
СИНТЕЗ АВТОМАТІВ.
Виконала:
студентка групи Саіт-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