Курсовая работа: Определение связности графа на Лиспе

РЕФЕРАТ

Пояснительная записка к курсовой работе содержит 16 страниц, 9 рисунков, 3 источника литературы, 2 приложения.

Темой работы является написание программы на XLisp, определяющей, является ли данный неориентированный граф связным.

Целью работы является приобретение навыков и методов программирования достаточно сложных задач на языках логического программирования, а также подготовка к выполнению дипломного проекта.

Ключевые слова: программа, алгоритм, поиск, вершина, ребро, граф, связанность, путь, список, функция.

СОДЕРЖАНИЕ

Введение

1 Анализ задачи

2 Обоснование выбора алгоритма и структур данных

3 Описание алгоритма

4 Обоснование набора тестов

Заключение

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

Приложение 1. Текст программы

Приложение 2. Результаты работы программы

ВВЕДЕНИЕ

Двоичные деревья играют весьма важную роль в теории информации.

Предположим, что определенное число сообщений требуется закодировать в виде конечных последовательностей различной длины, состоящих из нулей и единиц. Если вероятности кодовых слов заданы, то наилучшим считается код, в котором средняя длина слов минимальна по сравнению с прочими распределениями вероятности. Задачу о построении такого оптимального кода позволяет решить алгоритм Хаффмана.

Двоичные кодовые деревья допускают интерпретацию в рамках теории поиска. Каждой вершине при этом сопоставляется вопрос, ответить на который можно либо "да", либо "нет". Утвердительному и отрицательному ответу соответствуют два ребра, выходящие из вершины. "Опрос" завершается, когда удается установить то, что требовалось. Таким образом, если кому-то понадобится взять интервью у различных людей, и ответ на очередной вопрос будет зависеть от заранее неизвестного ответа на предыдущий вопрос, то план такого интервью можно представить в виде двоичного дерева.

Еще недавно одной из наиболее сложных и утомительных задач для радиолюбителей было конструирование печатных схем.

Печатной схемой называют пластинку из какого-либо диэлектрика, на которой в виде металлических полосок вытравлены дорожки. Пересекаться дорожки могут только в определенных точках, куда устанавливаются необходимые элементы (диоды, триоды, резисторы и другие), их пересечение в других местах вызовет замыкание электрической цепи.

В ходе решения этой задачи необходимо вычертить плоский граф, с вершинами в указанных точках.

Можно привести множество примеров, неопровержимо доказывающих практическую ценность теории графов.

Темой работы является написание программы на XLisp, определяющей, является ли данный неориентированный граф связным. Целью работы является приобретение навыков и методов программирования достаточно сложных задач на языках логического программирования, а также подготовка к выполнению дипломного проекта.

1 Анализ задачи

В данной работе необходимо написать программу на языке XLisp, определяющую, является ли данный неориентированный граф связным. Для этого необходимо запрограммировать предварительно предикат (path X Y), проверяющий, существует ли путь из вершины X в вершину Y.

Говорят, что задан неориентированный граф G, если заданы два множества:

- непустое множество V={v₁ ,..., v_n } - множество вершин графа;

- множество Q неупорядоченных пар (v_i , v_j ), где v_i , v_j Î V. Это множество называется множеством рёбер графа. Очевидно, что (v_i , v_j ) Î Q Û (v_j , v_i ) Î Q, причем это одно и то же ребро.

--> ЧИТАТЬ ПОЛНОСТЬЮ <--