Пошук академічних текстів

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