Державний Університет Телекомунікацій

Чергове засідання гуртка «Дискретні структури для програмістів» кафедри Інженерії програмного забезпечення

На черговому засіданні гуртка «Дискретні структури для програмістів» кафедри Інженерії програмного забезпечення учасники розглядали різні алгоритми мінімізації шляху в графах, використовуючи мови програмування.

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

Існують різні постановки задачі про найкоротший шлях:

  1. Задача про найкоротший шлях в заданий пункт призначення. Потрібно знайти найкоротший шлях в задану вершину призначення t, який починається в кожній з вершин графа (крім t).
  2. Задача про найкоротший шлях між заданою парою вершин. Потрібно знайти найкоротший шлях із заданої вершини u в задану вершину v;
  3. Задача про найкоротший шлях між усіма парами вершин. Потрібно знайти найкоротший шлях з кожної вершини u в кожну вершину v.

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

До найбільш популярних алгоритмів пошуку маршруту в графі можна віднести: алгоритм Дейкстри, алгоритм Беллмана –Форда, алгоритм пошуку A*, який знаходить маршрут з найменшою вартістю від однієї вершини (початкової) до іншої (цільової, кінцевої), алгоритм Флойда-Уоршелла,  алгоритм Джонсона, алгоритм Лі (хвильовий алгоритм), Contraction hierarchies (алгоритм з переобробкою графу для знаходження коротших шляхів і «віртуального» видалення вершин які можна  пропустити при пошуку маршруту).

Студенти Пд-13, які є постійними учасниками гуртка, зосередили свою увагу на алгоритмі Флойда-Уоршела. Це динамічний алгоритм для знаходження найкоротших відстаней між усіма вершинами зваженого орієнтованого графа, який був розроблений в 1962 році Робертом Флойдом і Стівеном Уоршелом,  хоча в 1959  році Бернард Рой (Bernard Roy) опублікував практично такий самий алгоритм,  але це залишилося непоміченим.

Кирпичов Олександр на мові Javascript презентував наочне представлення алгоритму Флойда-Уоршела на прикладі потягів і станцій, як застосування алгоритму до знаходження мінімального шляху між станціями.

Успіх приходить до тих, хто займається улюбленою справою, а участь студентів 1 курсу в роботі гуртка підтверджує, що вибір зроблений вдало!

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

Розклад гуртків за посиланням.


Фотографії

Оцініть новину:
8

Читайте також

На кафедрі Інформаційних систем та технологій в межах навчального процесу викладається дисципліна Інтернет речей, практична частина якої передбачає ст..
Кафедра вищої математики кожного семестру проводяться двомісячні курси з обчислювальної математики з використанням персонального комп’ютера. Мет..
16 квітня 2019 р. завершилось навчання групи слухачів із вивчення мови програмування Java. Ця подія ознаменувалась урочистим врученням сертифікатів пр..

Ключові слова

Про кафедру

Кафедра Інженерії програмного забезпечення

Отримати консультацію

у завідувача кафедри
Надіслати запит

Абітурієнту

Спеціалізація: Програмна інженерія

Програмна інженерія пов'язана з усіма аспектами виробництва програмного забезпечення: від початкових стадій створення до підтримки системи після передачі замовнику.

Якщо Вам подобається захоплюючий процес розробки веб-сайтів, комп'ютерних ігор, створення та обробки баз даних, та багато іншого, то Вам слід обрати спеціалізацію «Програмна інженерія».

Ми зможемо надати Вам необхідну інформацію та рекомендації щодо вступу до ВНЗ під час вступної кампанії.
Спеціалізація: Програмна інженерія

Програмна інженерія пов'язана з усіма аспектами виробництва програмного забезпечення: від початкових стадій створення до підтримки системи після передачі замовнику.

Якщо Вам подобається захоплюючий процес розробки веб-сайтів, комп'ютерних ігор, створення та обробки баз даних, та багато іншого, то Вам слід обрати спеціалізацію «Програмна інженерія».

Ми у соціальних мережах


Переглядів: 177
^