РЕФЕРАТ
Пояснительная записка ккурсовой работе содержит 16 страниц, 9 рисунков, 3 источника литературы, 2приложения.
Темой работы являетсянаписание программы на XLisp, определяющей, является ли данныйнеориентированный граф связным.
Целью работы являетсяприобретение навыков и методов программирования достаточно сложных задач наязыках логического программирования, а также подготовка к выполнению дипломногопроекта.
Ключевые слова: программа,алгоритм, поиск, вершина, ребро, граф, связанность, путь, список, функция.
СОДЕРЖАНИЕ
Введение
1 Анализ задачи
2Обоснование выбора алгоритма и структур данных
3Описание алгоритма
4Обоснование набора тестов
Заключение
Списоклитературы
Приложение1. Текст программы
Приложение2. Результаты работы программы
ВВЕДЕНИЕ
Двоичные деревья играют весьмаважную роль в теории информации.
Предположим, чтоопределенное число сообщений требуется закодировать в виде конечных последовательностейразличной длины, состоящих из нулей и единиц. Если вероятности кодовых словзаданы, то наилучшим считается код, в котором средняя длина слов минимальна по сравнениюс прочими распределениями вероятности. Задачу о построении такого оптимальногокода позволяет решить алгоритм Хаффмана.
Двоичные кодовые деревья допускаютинтерпретацию в рамках теории поиска. Каждой вершине при этом сопоставляетсявопрос, ответить на который можно либо «да», либо «нет». Утвердительномуи отрицательному ответу соответствуют два ребра, выходящие из вершины. «Опрос»завершается, когда удается установить то, что требовалось. Таким образом, есликому-то понадобится взять интервью у различных людей, и ответ на очереднойвопрос будет зависеть от заранее неизвестного ответа на предыдущий вопрос, топлан такого интервью можно представить в виде двоичного дерева.
Еще недавно одной из наиболеесложных и утомительных задач для радиолюбителей было конструирование печатныхсхем.
Печатной схемой называют пластинкуиз какого-либо диэлектрика, на которой в виде металлических полосок вытравлены дорожки.Пересекаться дорожки могут только в определенных точках, куда устанавливаютсянеобходимые элементы (диоды, триоды, резисторы и другие), их пересечение вдругих местах вызовет замыкание электрической цепи.
В ходе решения этой задачинеобходимо вычертить плоский граф, с вершинами в указанных точках.
Можно привести множествопримеров, неопровержимо доказывающих практическую ценность теории графов.
Темой работы являетсянаписание программы на XLisp, определяющей, является ли данныйнеориентированный граф связным. Целью работы является приобретение навыков иметодов программирования достаточно сложных задач на языках логическогопрограммирования, а также подготовка к выполнению дипломного проекта.
1 Анализ задачи
В данной работенеобходимо написать программу на языке XLisp, определяющую, является ли данныйнеориентированный граф связным. Для этого необходимо запрограммироватьпредварительно предикат (path X Y), проверяющий, существует ли путь из вершиныX в вершину Y.
Говорят, что заданнеориентированный граф G, если заданы два множества:
— непустое множество V={v1,...,vn} — множество вершин графа;
— множество Qнеупорядоченных пар (vi, vj), где vi, vjÎ V. Это множество называетсямножеством рёбер графа. Очевидно, что (vi, vj) Î Q Û (vj, vi) Î Q, причем это одно и то же ребро.
Путем от vi до vj называется такая последовательностьребер графа, ведущая от vi к vj, в которой два соседних ребра имеют общую вершину и никакоеребро не встречается дважды.
Две вершины графаназываются связными, если в графе существует путь с концами в этих вершинах, инесвязными в противном случае.
Граф называется связным,если любые две его вершины связны, и несвязным в противном случае.
2Обоснование выбора алгоритма и структур данных
Дляопределения связности графа используется поиск пути от одной вершины к другой.Граф является связным, если все вершины связаны между собой. Можно утверждать,что граф является связным, если одну из вершин можно соединить со всеми другимипутем. Алгоритм определения связности графа заключается в поиске пути от первойвершины ко всем остальным. Если все пути можно найти – значит граф связный.
Поискпути от одной вершины к другой будет выполняться по алгоритму поиска в ширину.Схема алгоритма изображена на рисунке 2.1.
/>
Рис.2.1– Схема алгоритма поиска в ширину
Поисквершин, смежных с новыми вершинами выполняется так:
а)Если список ребер пустой – выход.
б)Берется первое ребро в списке ребер.
в)Если одна из вершин ребра находится в списке новых вершин, а вторая не входитни в список новых вершин, ни в список найденных вершин, то вершина добавляетсяв список смежных вершин.
г)Удалить из списка ребер первое ребро и перейти к пункту а.
Графпредставляется двумя множествами (списками): списком вершин и списком ребер.Каждое ребро – это список из двух вершин. Данный выбор обосновывается тем, чтосписки являются основным способом представления множеств данных.
3Описание алгоритма
Былиразработаны следующие функции (текст программы приведен в приложении 1).
Функцияsmezver (xy snaidsnov) – определяет, является ли вершинаy смежной с одной из новых вершин (x– входит в список новых вершин, y – не входит в списки новых и найденныхвершин).
Параметры:
— x — первая вершина ребра;
— y — вторая вершина ребра;
— snaid — список найденныхвершин;
— snov — список новых вершин.
Функцияsmez (snaidsnov sreb)- поиск смежных с новыми вершинами вершин.
Параметры:
— snaid — список найденных вершин;
— snov — список новых вершин;
— sreb — список ребер.
Функцияshir(snaid snov y sreb) — поиск в ширину пути.
Параметры:
— snaid — список найденных вершин;
— snov — список новых найденных вершин;
— y — вершина для поиска;
— sreb — список ребер.
Функцияpath(x y sreb) – поиск пути от вершины x к вершине y.
Параметры:
— x — первая вершина;
— y — вторая вершина;
— sreb — список ребер.
Функцияperebor(fver sver sreb) — перебор вершин и поиск пути от первой вершины ко всемостальным.
Параметры:
— fver — первая вершина;
— sver — список вершин:
— sreb — список ребер.
Функцияsvgraf(sver sreb) — определение связанности графа.
Параметры:
— sver — список вершин;
— sreb — список ребер.
4Обоснование набора тестов
Притестировании используются следующие тесты:
/>
Рис.4.1– Тест 1. Связанный граф
/>
Рис.4.2 – Тест 2.Связанный граф
/>
Рис.4.3 – Тест 3.Несвязанный граф
/>
Рис.4.4 – Тест 4.Связанный граф
/>
Рис.4.5 – Тест 5.Несвязанный граф
/>
Рис.4.6 –Тест 6. Связанный граф
/>
Рис.4.7 – Тест 7.Несвязанный граф
/>
Рис.4.8 – Тест 8. Несвязанный граф
Перечисленныетесты представляют собой различные входные данные, которые позволяют полностьюпроверить работу программы.
Притестировании все тесты были выполнены успешно. Результаты работы программыприведены в приложении 2.
ЗАКЛЮЧЕНИЕ
В данной работе написанапрограмма на XLisp, определяющей, является ли данный неориентированный графсвязным.
Все поставленные целивыполнены: приобретены навыки и методы программирования достаточно сложныхзадач на языках логического программирования, а также проведена подготовка квыполнению дипломного проекта.
Программа отлажена ипротестирована.
СПИСОКЛИТЕРАТУРЫ
1Лутай В.Н. Программирование на языках Лисп и Пролог. ТРТУ,1998.
2Филд А., Харрисон П. Функциональное программирование. — М.: Мир, 1993.
3Уилсон Р. Введение в теоpию гpафов. — М.: Миp, 1977.
ПРИЛОЖЕНИЕ1
Текстпрограммы
;смежная вершина (первая вершина ребра, вторая вершина ребра,
; список найденных вершин, список новых вершин)
(defun smezver(x y snaid snov)
(cond
((not(member x snov)) nil) ;x не является новой вершиной
((membery snov) nil) ;y является новой вершиной
((membery snaid) nil) ;y является ранее найденной вершиной
(t t))) ; вершинаявляется новой смежной вершиной
; поисксмежных вершин (список найденных вершин, список новых вершин, список ребер)
(defun smez(snaid snov sreb)
(cond
((null sreb) nil) ; конецпоиска
((smezver (caar sreb) (cadar sreb) snaidsnov) ; смежная вершина
(cons (cadar sreb) (smez snaid snov (cdrsreb)))) ; добавление всписок
((smezver (cadar sreb) (caar sreb) snaidsnov) ; смежная вершина
(cons (caar sreb) (smez snaid snov (cdrsreb)))) ; добавление всписок
(t (smez snaid snov (cdr sreb))))) ; пропускребра
; поискв ширину (список найденных вершин, список новых найденных вершин,
; вершина для поиска, список ребер)
(defun shir(snaid snov y sreb)
(cond
((nullsnov) nil) ; не найдено ни одной новой вершины
((membery snov) t) ; вершина найдена
(t (shir(append snaid snov) (smez snaid snov sreb) y sreb)))); добавление новых вершин
; поискпути (первая вершина, вторая вершина, список ребер)
(defun path(x y sreb)
(shir nil (list x) ysreb)); поиск в ширину
; переборвершин (первая вершина, список вершин, список ребер)
(defun perebor(fver sver sreb)
(cond
((nullsver) t) ; конец перебора
((pathfver (car sver) sreb) (perebor fver (cdr sver) sreb)); путьнайден
(t nil))) ; нет пути
; определениесвязанности графа(список вершин, список ребер)
(defunsvgraf(sver sreb)
(perebor(car sver) (cdr sver) sreb)) ; перебор вершин и поиск пути от первойвершины ко всем остальным
ПРИЛОЖЕНИЕ2
Результатыработы программы
Тест: 1
Выражение: (svgraf '(v1 v2 v3 v4) '((v1 v2) (v2 v3) (v3 v4)))
Результат: Т
Тест: 2
Выражение: (svgraf '(v1 v2 v3 v4) '((v1 v2) (v2 v4) (v2 v3) (v3 v4) (v1 v4) (v3 v4)))
Результат: T
Тест: 3
Выражение: (svgraf '(v1 v2 v3 v4 v5 v6 v7) '((v1 v2)(v2 v3)(v1 v3)(v4 v5)(v4 v7)(v5 v6)(v6 v7)))
Результат: NIL
Тест: 4
Выражение: (svgraf '(v1 v2 v3 v4 v5 v6) '((v1 v7)(v2 v7)(v3 v7)(v4 v7)(v5 v7)(v6 v7)(v1 v1)(v2 v2)(v3 v3)(v4 v4)(v5 v5)(v6 v6)))
Результат: T
Тест: 5
Выражение: (svgraf '(v1 v2 v3 v4) '((v1 v2)(v1 v2)(v3 v4)(v3 v4)))
Результат: NIL
Тест: 6
Выражение: (svgraf '(v1) nil)
Результат: T
Тест: 7
Выражение: (svgraf '(v1 v2 v3) nil)
Результат: NIL
Тест: 8
Выражение: (svgraf '(v1 v2 v3 v4) '((v1 v2) (v2 v3) (v3 v1)))
Результат: NIL