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

Скорочена інформація про документ
dc.contributor.advisorСтаткевич, Віталій Михайлович
dc.contributor.authorБоднар, Максим Сергійович
dc.date.accessioned2023-09-12T08:31:51Z
dc.date.available2023-09-12T08:31:51Z
dc.date.issued2023
dc.description.abstractДипломна робота: 127 с., 52 рис., 6 табл., 2 дод., 22 джерела. Об’єктом роботи є задача пошуку максимального потоку в мережах. Предметом роботи є методи знаходження максимального потоку в мережах, їх асимптотична складність та порівняння за часом (швидкістю виконання). Мета роботи полягає в програмній реалізації алгоритма Форда- Фалкерсона, Едмондса-Карпа та просування передпотоку; вказати та обґрунтувати їх асимптотичну складність; виконати порівняльний аналіз вказаних алгоритмів. Результатом роботи є розроблене програмне забезпечення, яке реалізує алгоритми знаходження максимального потоку. Також було виконано аналіз та порівняння їх результатів. Вирішені наступні завдання: − досліджені та порівняні різні методи розв’язання задачі про максимальний потік, а саме алгоритм Форда-Фалкерсона, Едмондса- Карпа та просування передпотоку; − реалізовано програмний код на мові Python для кожного з алгоритмів та проведено експерименти на різних множинах тестових мереж; − зроблено порівняльний аналіз ефективності методів залежно від розміру мережі та її характеристик.uk
dc.description.abstractotherThesis: 127 p., 52 figures, 6 tables, 2 appendices, 22 sources. The objective of the research is the problem of finding the maximum flow in networks. The subject of the research is the set of methods of finding the maximum flow in networks, their asymptotic complexity and comparison by time (execution speed). The goal of the research is to implement the Ford-Fulkerson, Edmonds- Karp, and Push-Relabel algorithms in software; to indicate and justify their asymptotic complexity; to perform a comparative analysis of these algorithms. The result of the research is the developed software that implements the algorithms for finding the maximum flow. Additionally, a thorough analysis and comparison of their results have been conducted. The following tasks were solved: − investigated and compared different methods for solving the maximum flow problem, namely the Ford-Fulkerson algorithm, the Edmonds-Karp algorithm, and the Push-Relabel algorithm; − implemented the software code in Python for each of the algorithms and conducted experiments on various sets of test networks; − conducted a comparative analysis of the efficiency of the methods depending on the size of the network and its characteristics.uk
dc.format.extent127 с.uk
dc.identifier.citationБоднар, М. С. Порівняльний аналіз та програмна реалізація методів розв'язання задачі про максимальний потік у мережах : дипломна робота ... бакалавра : 124 Системний аналіз / Боднар Максим Сергійович. – Київ, 2023. – 127 с.uk
dc.identifier.urihttps://ela.kpi.ua/handle/123456789/60245
dc.language.isoukuk
dc.publisher.placeКиївuk
dc.subjectмаксимальний потікuk
dc.subjectзадача про максимальний потікuk
dc.subjectалгоритм форда-фалкерсонаuk
dc.subjectалгоритм едмондса-карпаuk
dc.subjectалгоритм просування передпотокуuk
dc.subjectmaximum flowuk
dc.subjectmaximum flow problemuk
dc.subjectford-fulkerson algorithmuk
dc.subjectedmonds-karp algorithmuk
dc.subjectpush-relabel algorithmuk
dc.titleПорівняльний аналіз та програмна реалізація методів розв'язання задачі про максимальний потік у мережахuk
dc.typeBachelor Thesisuk

Файли

Контейнер файлів
Зараз показуємо 1 - 1 з 1
Ескіз
Назва:
Bodnar_bakalavr.pdf
Розмір:
2.85 MB
Формат:
Adobe Portable Document Format
Опис:
Завантажити
Ліцензійна угода
Зараз показуємо 1 - 1 з 1
Ескіз недоступний
Назва:
license.txt
Розмір:
9.1 KB
Формат:
Item-specific license agreed upon to submission
Опис:
Завантажити

Зібрання

Бакалаврські роботи (ММСА)
Бакалаврські роботи