Search academic texts

Information × Registration Number 2123U003730, Article popup.category Бакалаврська робота Title popup.author Боднар Максим Сергійович popup.publication 01-01-2023 popup.source_user Національний технічний університет України «Київський політехнічний інститут імені Ігоря Сікорського» popup.source https://ela.kpi.ua/handle/123456789/60245 popup.publisher Київ Description Дипломна робота: 127 с., 52 рис., 6 табл., 2 дод., 22 джерела. Об’єктом роботи є задача пошуку максимального потоку в мережах. Предметом роботи є методи знаходження максимального потоку в мережах, їх асимптотична складність та порівняння за часом (швидкістю виконання). Мета роботи полягає в програмній реалізації алгоритма Форда- Фалкерсона, Едмондса-Карпа та просування передпотоку; вказати та обґрунтувати їх асимптотичну складність; виконати порівняльний аналіз вказаних алгоритмів. Результатом роботи є розроблене програмне забезпечення, яке реалізує алгоритми знаходження максимального потоку. Також було виконано аналіз та порівняння їх результатів. Вирішені наступні завдання: − досліджені та порівняні різні методи розв’язання задачі про максимальний потік, а саме алгоритм Форда-Фалкерсона, Едмондса- Карпа та просування передпотоку; − реалізовано програмний код на мові Python для кожного з алгоритмів та проведено експерименти на різних множинах тестових мереж; − зроблено порівняльний аналіз ефективності методів залежно від розміру мережі та її характеристик. popup.nrat_date 2025-01-29 Close