Зміст
Введення
. Постановка завдання
. Алгоритм Прима знаходження оптимального каркаса
. Реалізація алгоритму мовою Пролог
. Приклади роботи програм
Висновок
Список літератури
Додаток
Введення
Функціональні і логічні мови програмування спираються на т.зв. декларативну парадигму програмування. У відмінності від імперативної, де основна увага приділяється розробці та реалізації конкретних алгоритмів для вирішення певного класу задач, в декларативної парадигмі на перший план виходить формальний опис задачі, спираючись на яке обчислювальна машина може сама знайти шлях до її вирішення. Декларативний підхід до розробки програм має перед імперативним ряд переваг, серед яких більша виразність і менша трудомісткість розробки. Менша трудомісткість, зокрема, досягається за рахунок того, що програміст може не дбати про фізичне поданні програми, організації пам'яті, взаємодії з апаратними засобами і т.п., і може повністю зосередитися на пошуку рішення задачі як такої, залишаючи реалізацію рішення комп'ютера. Зрозуміло, у такого підходу є і суттєві недоліки, мабуть, основним з яких є зменшення продуктивності та неефективне використання пам'яті. Тим не менш, цей недолік не є критичним, оскільки в більшості випадків до програми не пред'являються настільки жорсткі вимоги, що використання декларативних мов стає недоцільним. Більше того, у певних випадках реалізація на декларативних мовах може виявитися навіть ефективніше, ніж на імперативних (наприклад, існує варіант реалізації алгоритму швидкого сортування на мові Haskell, який працює швидше, ніж реалізація мовою C). Виразність ж декларативних мов є дуже суттєвою перевагою. Тут можна процитувати Дональда Кнутта: В«Програми пишуться насамперед для того, щоб їх читали людиВ». Програми на декларативних мовах набагато легше налагоджувати, оскільки помилки свідомо закладені тільки в рішенні, в той час як за статистикою більше 80% всіх помилок в програмах на імперативних мовах становлять деталі реалізації, наприклад, приведення типів. p align="justify"> У даній роботі розглядається застосування мови логічного програмування Пролог та мови функціонального програмування Haskell для реалізації алгоритму пошуку оптимального каркаса графа.
1. Постановка завдання
Каркасом графа називають подграф без циклів, що містить всі вершини вихідного графа і безліч ребер якого є підмножиною ребер початкового графа. Оптимальним каркасом зваженого графа називають G називають каркас, здатний мінімізувати деяку функцію від ваг входять до нього ребер. Найчастіше в якості такої функції виступає сума ваг ребер, рідше - твір, ще рідше - довільна сепарабельного ...
