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

РЕФЕРАТ
Данная пояснительная записка к курсовой работе содержит 16 страниц, 9 рисунков, 3 источника литературы, 2 приложения.
Тема работы: написание программы, определяющей связность неориентированного графа на XLisp.
Целью работы является приобретение навыков и методов программирования достаточно сложных задач на языках логического программирования, а также подготовка к выполнению дипломного проекта.
Ключевые слова: логическое программирование, функциональное программирование, XLisp, поиск, вершина, алгоритм, функция, ребро, граф, связность, путь.
...

Оглавление
ВВЕДЕНИЕ 5
ОСНОВНАЯ ЧАСТЬ РАБОТЫ 7
1 Анализ задачи 7
2 Выбор алгоритма и структур данных 8
3 Составление алгоритма 9
4 Конструирование набора тестов 10
ЗАКЛЮЧЕНИЕ 13
СПИСОК ЛИТЕРАТУРЫ 14
ПРИЛОЖЕНИЕ 1 Текст программы 15
ПРИЛОЖЕНИЕ 2 Результаты работы программы 18

ВВЕДЕНИЕ
Тема данной работы – написание программы на XLisp, определяющей, является ли данный неориентированный граф связным. Целью её выполнения является приобретение навыков и овладение методами программирования комплексных задач на языках логического (функционального) программирования, а также подготовка к выполнению дипломного проекта.
Прежде всего кратко поясним, что такое Лисп. Лисп (LISP, от англ. LISt Processing language – «язык обработки списков»; современное написание: Lisp) – семейство языков программирования, программы и данные в которых представляются системами линейных списков символов. Создатель Лиспа Джон Маккарти занимался исследованиями в области искусственного интеллекта (в дальнейшем ИИ) и созданный им язык по сию пору является одним из основных средств моделирования раз личных аспектов ИИ [2].
Лисп является вторым в истории (после Фортрана) используемым по сей день высокоуровневым языком программирования, а также первым из сохранившихся в использовании языков, использующих автоматическое управление памятью и сборку мусора [1].
Традиционный Лисп имеет динамическую систему типов. Язык является функциональным, но начиная уже с ранних версий обладает также чертами императивности, к тому же, имея полноценные средства символьной обработки, позволяет реализовать объектно-ориентированность; примером такой реализации является платформа CLOS [4].
Связный граф – граф, содержащий ровно одну компоненту связности. Это означает, что между любой парой вершин этого графа существует как минимум один путь.
Прямым применением теории графов является теория сетей – и её приложение – теория электронных сетей. Например, все компьютеры, включенные в сеть Интернет, образуют связный граф, и хотя отдельная пара компьютеров может быть не соединена напрямую (в формулировке для графов – не быть соединены ребром), от каждого компьютера можно передать информацию к любому другому (есть путь из любой вершины графа в любую другую).
Видим, что актуальность выбранной темы обуславливается её фундаментальностью. Важно не только разобраться в сути проблемы и подхода «логического программирования», но и заложить основание для применения полученных знаний на практике.

V (а значит и, E, иначе оно было бы мультимножеством) обычно считаются конечными множествами. Многие хорошие результаты, полученные для конечных графов, неверны (или каким-либо образом отличаются) для бесконечных графов. Это происходит потому, что ряд соображений становится ложным в случае бесконечных множеств [2].Вершины и рёбра графа называются также элементами графа, число вершин в графе |V| – порядком, число рёбер |E| – размером графа.Вершины u и v называются концевыми вершинами (или просто концами) ребра e=\{u,v\}. Ребро, в свою очередь, соединяет эти вершины. Две концевые вершины одного и того же ребра называются соседними.Ниже приведены некоторые критериальные (эквивалентные) определения связного графа. Граф называется односвязным (связным), если:У него одна компонента связностиСуществует путь из любой вершины в любую другую вершинуСуществует путь из заданной вершины в любую другую вершинуСодержит связный подграф, включающий все вершины исходного графаСодержит в качестве подграфа дерево, включающее все вершины исходного графа (такое дерево называется остовным)При произвольном делении его вершин на 2 группы всегда существует хотя бы 1 ребро, соединяющее пару вершин из разных групп.2 Выбор алгоритма и структур данныхОпределение связности графа можно выполнять различными методами. Наиболее логичным выглядит использование поиска в ширину (пути от первой вершины ко всем остальным) [3]. Если все пути можно найти – значит граф связный. Блок-схема алгоритма показана на рисунке 1.Рис.1. Схема алгоритма поиска в ширинуПоиск вершин, смежных с новыми и не входящих в список найденных и список новых вершин, выполняется так:а) Если список ребер пустой – выход.б) Берется первое ребро в списке ребер.в) Если одна из вершин ребра находится в списке новых вершин, а вторая не входит ни в список новых вершин, ни в список найденных вершин, то вершина добавляется в список смежных вершин.г) Удалить из списка ребер первое ребро и перейти к пункту а.В программе граф задан двумя списками: списком вершин и списком ребер. Каждое ребро представляется списком из двух вершин. Данный выбор обосновывается тем, что списки являются основным способом представления множеств данных.3 Составление алгоритмаДля реализации вышеуказанного базового алгоритма на избранном множестве структур данных нами созданы следующие функции (полный текст программы приведен в приложении 1).Функция IsGraphConnective(Vertices Edges) – определение связанности графа.Параметры:- Vertices – список вершин;- Edges – список ребер.Функция FindPathsFromTheVertexToOthers(InitialVertex Vertices Edges) – перебор вершин и поиск пути от первой вершины ко всем остальным.Параметры:- InitialVertex – первая вершина;- Vertices – список вершин:- Edges – список ребер.Функция path(x y Edges) – поиск пути от вершины x к вершине y.Параметры:- x – первая вершина;- y – вторая вершина;- Edges – список ребер.Функция BFS(FoundVertices NewVertices y Edges) – поиск в ширину пути.Параметры:- FoundVertices – список найденных вершин;- NewVertices – список новых найденных вершин;- y – вершина для поиска;- Edges – список ребер.Функция AdjacentVertices (FoundVertices NewVertices Edges) – поиск смежных с новыми вершинами вершин.Параметры:- FoundVertices – список найденных вершин;- NewVertices – список новых вершин;- Edges – список ребер.Функция IsVertexConnected (x y FoundVertices NewVertices) – определяет, является ли вершина y смежной с одной из новых вершин (x – входит в список новых вершин, y – не входит в списки новых и найденных вершин).Параметры: - x – первая вершина ребра;- y – вторая вершина ребра;- FoundVertices – список найденных вершин;- NewVertices – список новых вершин.4 Конструирование набора тестовДля всеобъемлющего охвата возможных вариантов было принято решение использовать при тестировании такие тесты (рис.2 – рис.9):Рис. 2. Тест №1. Связанный графРис. 3. Тест №2. Связанный графРис. 4. Тест №3. Несвязанный графРис. 5. Тест №4. Несвязанный графРис. 6. Тест №5. Несвязанный графРис. 7. Тест №6. Связанный графРис. 8. Тест №7. Связанный графРис. 9. Тест №8. Несвязанный графВышеуказанные тесты представляют собой различные входные данные, которые позволяют полностью проверить работу программы.В каждом случае тестирование прошло успешно. Результаты работы приложения приведены в приложении 2.ЗАКЛЮЧЕНИЕНашу задачу по составлению работающей самодокументированной программы на XLisp, определяющей, является ли данный неориентированный граф связным, можно считать выполненной. В пояснительной записке дано описание всех этапов разработки, проиллюстрированных необходимыми рисунками и блок-схемами.Логическое программирование (в широком смысле слова) значительно отличается от традиционного императивного подхода. Вместе с тем программирование остаётся программированием – его базовые принципы остаются неизменными.