XS
SM
MD
LG
Державний університет інформаційно-комунікаційних технологій

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


Адреса:
03110, Україна
м. Київ, вул. Солом'янська, 7
Контактна інформація:
Державний університет інформаційно-комунікаційних технологій

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

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

13:51, 12-04-2019

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

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

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

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

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

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

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

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

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

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

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

Фотографії

Бажаєте дізнаватись про особливості вступу у 2024 році?
Підписуйтесь на спільноти спеціальності "121-Інженерія програмного забезпечення" кафедри Інженерії програмного забезпечення та першим отримуйте новини, сповіщення про важливі події, підготовчі курси, дні відкритих дверей та багато цікавого.
Читайте також

Про кафедру

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

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

Ваш запит на зворотній дзвінок отримає завідуючий кафедрою
Надіслати запит

Абітурієнту

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

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

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

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

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

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

Переглядів: 4 127