- •Організація проведення курсової роботи теми курсових робіт
- •Порядок виконання курсової роботи
- •Терміни виконання окремих етапів
- •Порядок захисту курсової роботи
- •Загальні положення
- •Структура роботи
- •Вимоги до титульного листа роботи
- •Вимоги до списку виконавців
- •Вимоги до реферату
- •Вимоги до змісту
- •Вимоги до переліку скорочень, умовних позначок, символів, одиниць вимірювань і спеціальних термінів
- •Вимоги до тексту роботи
- •1. Аналіз задачі, що вирішується
- •2 Вибір технології, мови і середовища розробки
- •3 Опис творчого процесу рішення задачі.
- •4. Вимоги до інформаційної та програмної сумісності
- •Правила оформлення роботи Загальні вимоги
- •Нумерація сторінок роботи
- •Нумерація розділів, підрозділів, пунктів, підпунктів і книг роботи
- •Ілюстрації
- •Перерахування і примітки
- •Формули і рівняння
- •Посилання
- •Додатки
- •Додатки
- •Зразок оформлення титульного листа
- •Зразок оформлення списку виконавців
- •Зразок оформлення реферату Реферат
- •Зразок оформлення змісту
- •Зразок оформлення вступу
- •Зразок оформлення розділу „Аналізу завдання”
- •Зразок оформлення розділу „Дослідження джерел існуючої інформації”
- •Зразок оформлення розділу „Вибір технології і мови програмування”
- •Зразки блок-схем програми і підпрограм
- •Зразок оформлення розділу „Опис програми”
- •Опис процедур і функцій
- •Зразок оформлення розділу „Структура файлів вхідних данних”
- •Зразок оформлення розділу „Структура файлів вихідних данних”
- •Зразок оформлення розділу „Опис роботи програми”
- •Зразок оформлення розділу „Вимоги до програмної та інформаційної сумісності”
- •Зразок оформлення висновку
- •Зразок оформлення списку використаних джерел
Зразок оформлення розділу „Аналізу завдання”
Данна задача є класичною задачею теорії графів і відома як задача пошуку найкоротших шляхів в мережі.
Подібні задачі виникають при виборі маршрутів в обчислювальних мережах і транспортних системах. У обчислювальних мережах рішення подібних задач визначає склад і структуру мережевих протоколів для обслуговування руху пакетів інформації. За даними про завантаження каналів обчислюється найбільш оптимальний маршрут проходження пакету інформації. При знаходженні такого шляху до пакету додається заголовок, в якому указують перелік вузлів для переходу від вершини хi до вершини хj або чергову вершину переходу. У транспортних системах рішення подібних задач визначає найекономніший по вартості або за часом маршрут руху транспортної одиниці.
Кожна вершина в такому графі використовується тільки один раз, а довжина найкоротшого шляху визначиться сумою вартостей ребер для переходу i,j=(хi;...хk;...хj):
Li,j=m,n lm,n, где im, nj, mn.
Для пошуку найкоротших шляхів є декілька алгоритмів. Алгоритми Форда-Беллмана і Дейкстри дозволяють знайти найкоротші шляхи від заданої вершини графа до будь-якої іншою. В результаті цих обчислень формується граф типу “дерево” з коренем в заданій вершині. Алгоритми Флойда і Данцига дозволяють шукати найкоротші шляхи між будь-якою парою вершин графа типу мережа.
У основі всіх алгоритмів лежить операція порівняння двох простих маршрутів. На мал. 30 показані два прості маршрути, що сполучають вершини хi і хj. Вибір найкоротшого шляху між вершинами хi і хj є результат порівняння довжин двох маршрутів, тобто Li,j=min{li,j; (li,p + lp,j)}. Якщо існує декілька вершин, суміжних з вершинами хi і хj слід виконувати процедуру послідовно, порівнюючи довжини двох (див.Мал.)
Алгоритм Флойда. Для того, щоб вибирати найкоротші шлях і переходи між вершинами xi і xj, необхідно використовувати дві матриці: матрицю найкоротших шляхів ||l(n;n)|| і матрицю найкоротших переходів ||(n;n)||, які дозволяють обчислювати і порівнювати різні маршрути через базову вершину графа.
lp |
x0 |
.. |
xi |
xp |
xj |
.. |
xn |
x0 |
0 |
.. |
l0i |
∞ |
l0j |
.. |
l0n |
.. |
.. |
0 |
.. |
.. |
.. |
.. |
.. |
xi |
li0 |
.. |
0 |
lip |
lij |
.. |
lin |
xp |
∞ |
.. |
lpi |
0 |
lpj |
.. |
lpn |
xj |
lj0 |
.. |
lji |
ljp |
0 |
.. |
ljn |
.. |
.. |
.. |
.. |
.. |
.. |
0 |
.. |
xn |
ln0 |
.. |
lni |
lnp |
lnj |
.. |
0nn |
p |
x0 |
.. |
xi |
xp |
xj |
.. |
xn |
x0 |
x0 |
.. |
xi |
xp |
xj |
.. |
xn |
.. |
x0 |
.. |
xi |
xp |
xj |
.. |
xn |
xi |
x0 |
.. |
xi |
xp |
xj |
.. |
xn |
xp |
x0 |
.. |
xi |
xp |
xj |
.. |
xn |
xj |
x0 |
.. |
xi |
xp |
xj |
.. |
xn |
.. |
x0 |
.. |
xi |
xp |
xj |
.. |
xn |
xn |
x0 |
.. |
xi |
xp |
xj |
.. |
xn |
а) якщо (li,p+ lp,j)pli,jp, то i,j (p+1)= i,j p=хj;
б) якщо (li,p+ lp,j)p<li,jp, то i,j (p+1)=хp.
Отже, для аналізу n-вершинного графа необхідно послідовно побудувати n матриць найкоротших шляхів і найкоротших переходів.
Додаток Є