in English
Біографія
Огляд
магістерської
роботи
Бібліотека
Посилання
Результати
пошуку
Куркчі В'ячеслав Андрійович
kourktchi@ukrtop.com
магістрант групи ПЗ-99, ФОТІ
научний керівник:
Ладиженський Юрій Валентинович
тема магістерскої роботы:
Паралельні алгоритми для рішення задач на графах.
Повна версія [pdf - російською] (212 кб)
Введение
Графи є дуже поширеною структурою даних, і задачі, пов'язані з ними, знаходят своє застосування в різних галузях науки і техніки: ці задачі вирішуються при проектуванні ВІС, при розпаралелюванні обчислювальних та інших процесів, при організації асоціативної п'амяті, в теорії кінцевих автоматів, потоків в мережах і ін. Задачі на графах багато людей часто вирішують у повсякденному житті, навіть не думаючи про це.
Нажаль, більша частина задач на графах - NP-полні, що в значному ступені стає на перешкоді пошуку рішення. Однак задачі цього класу часто просто необхідно вирішити. Це зумовило появу напрямку, що вивчає наближені, чи еврістичні, алгоритми. Більша частина NP-повних задач зводяться до ЗЦЛП, що дозволяє використовувати в якості рішення будь-які локальні максімуми (мінімуми). Таке рішення не оптимальне, але допустиме.
Процес рішення задачі великого розміру, навіть наближеним алгоритмом може бути досить довгим, що справедливо для всіх задач та алгоритмів. Для прискорення пошуку рішень, використовують паралельні алгоритми. Часова складність паралельних алгоритмів зазвичай, як мінімум на порядок нижче, ніж у аналогічних послідовних, а иноді й відноситься до іншого класу.
Для розглядання було обрано задачу про найбільшу незалежну множину вершин. Цю задачу було обрано через дві причини. По-перше, вона є фундаментальною, і до неї зводяться задачі про найменьше покриття, про доконані паросполучення, про домінуючи множини та інші. Тобто більшість алгоритмів для рішення цієї задачі можно поширити на багато інших. А по-друге, у цієї задачі досить велика кількість практичних застосувань, що робить пошук ефективного алгоритму для рішення цієї задачі необхідним.
Підмножина вершин графа є незалежною, якщо ніякі дві вершины з цієї множини несуміжні.
Приклад незалежних множин на графі.
