Магистерская диссертация на тему: Постановка задачи. Алгоритм Прима хождения оптимального каркаса

Введение

Функциональные и логические языки программирования опираются на т.н. декларативную парадигму программирования. В отличии от императивной, где основное внимание уделяется разработке и реализации конкретных алгоритмов для решения определенного класса задач, в декларативной парадигме на первый план выходит формальное описание задачи, опираясь на которое вычислительная машина может сама найти путь к ее решению. Декларативный подход к разработке программ имеет перед императивным ряд преимуществ, среди которых большая выразительность и меньшая трудоемкость разработки. Меньшая трудоемкость, в частности, достигается за счет того, что программист может не заботиться о физическом представлении программы, организации памяти, взаимодействии с аппаратными средствами и т.п., и может полностью сосредоточиться на поиске решения задачи как таковой, оставляя реализацию решения компьютеру. Разумеется, у такого подхода есть и существенные недостатки, по-видимому, основным из которых является уменьшение производительности и неэффективное использование памяти. Тем не менее, этот недостаток не является критичным, поскольку в большинстве случаев к программе не предъявляются настолько жесткие требования, что использование декларативных языков становится нецелесообразным. Более того, в определенных случаях реализация на декларативных языках может оказаться даже эффективнее, чем на императивных (например, существует вариант реализации алгоритма быстрой сортировки на языке Haskell, который работает быстрее, чем реализация на языке С). Выразительность же декларативных языков является очень существенным преимуществом. Здесь можно процитировать Дональда Кнутта: "Программы пишутся прежде всего для того, чтобы их читали люди". Программы на декларативных языках гораздо легче отлаживать, поскольку ошибки заведомо заложены только в решении, в то время как по статистике более 80% всех ошибок в программах на императивных языках составляют детали реализации, например, приведение типов.

В данной работе рассматривается применения языка логического программирования Пролог и языка функционального программирования Haskell для реализации алгоритма поиска оптимального каркаса графа.

Оглавление

- Введение

- Постановка задачи

- Алгоритм Прима нахождения оптимального каркаса

- Реализация алгоритма на языке Пролог

- Примеры работы программ Заключение

- Список литературы

- Приложение

Список литературы

1 Душкин Р.В. Функциональное программирование на языке Haskell. М.: ДМК Пресс, 2007. - 608 с., ил.

Стерлинг Л., Шапиро Э. Искусство программирования на языке Пролог: Пер. с англ.-М.: Мир, 1990. -235 с., ил.

Абельсон Х., Сассман Дж. Структура и интерпретация компьютерных программ - М.: Добросвет, КДУ, 2006. - 608 с.: ил.

Иван Братко. Алгоритмы искусственного интеллекта на языке PROLOG, 3-е издание. : Пер. с англ. - М.: Издательский дом "Вильямс", 2004. - 640 с.: ил. Парал. тит. Англ.

Касьянов В.Н., Евстигнеев В.А. Графы в программировании: обработка, визуализация и применение. - Спб.: БХВ-Петербург, 2003. - 1104 с.: ил.

Кристофидес Н. Теория графов. Алгоритмический подход. М. ДМК Пресс, 2003. - 356 с., ил.