Несмотря на некоторые стилистические недостатки и мелкие недочеты по оформлению данную курсовую работу можно рассматривать как эталонную.
Министерство образования Российской Федерации
ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ СИСТЕМ УПРАВЛЕНИЯ И РАДИОЭЛЕКТРОНИКИ (ТУСУР)
Кафедра автоматизированных систем управления (АСУ)
Нахождение компонент связанности графа
Пояснительная записка к курсовой работе по дисциплине «Функциональное программирование»
Выполнил:
студент гр. з-430-45б
Проверил:
Доцент каф. КСУП
2003
Реферат
Ключевые слова: Lisp, теория графов, компоненты связности, алгоритм.
Работа содержит пояснительную записку к программе, реализующей поиск всех компонентов связанности неориентированного графа. В работе рассмотрены некоторые возможные алгоритмы реализации задачи, дана оценка сложности каждого алгоритма.
Стр. 16 (вместе с приложениями), рис. 3, библ. 5.
Министерство образования Российской Федерации
ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ СИСТЕМ УПРАВЛЕНИЯ И РАДИОЭЛЕКТРОНИКИ (ТУСУР)
Кафедра автоматизированных систем управления (АСУ)
УТВЕРЖДАЮ
зав. кафедрой АСУ
ЗАДАНИЕ
по курсовому проектированию по дисциплине
«Функциональное программирование»
студенту
группа з-430-45б факультет ФСУ
1. Тема проекта: Нахождение компонент связанности графа
2. Срок сдачи студентом законченной работы
3. Исходные данные к проекту: Напишите программу на языке Xlisp, определяющую компоненты связанности данного неориентированного графа. Каждая компонента графа — список вершин, следовательно, решением задачи должен быть список списков. Указание: запрограммируйте предварительно предикат (path X Y), проверяющий, существует ли путь из вершины X в вершину Y.
4. Дата выдачи задания:
Задание принял к исполнению
Олег Анатольевич.
СОДЕРЖАНИЕ
Введение....................................................................................................................... 5
Анализ и решение задачи........................................................................................... 5
Выбор алгоритма и структур данных........................................................................ 6
Описание программы.................................................................................................. 7
Операции над объектом «граф»............................................................................. 7
Операции над объектом «множество вершин».................................................... 9
Функция поиска компонент связанности графа.................................................. 9
Выбор набора тестов................................................................................................. 10
Заключение................................................................................................................. 11
Список литературы.................................................................................................... 12
Приложение 1. Листинг программы........................................................................ 13
Приложение 2. Распечатки тестов........................................................................... 16
Основной целью данного курсового проекта является приобретение навыков и изучение методов программирования достаточно сложных задач на языках логического и функционального программирования. Темой данной курсовой работы является программирование задач теории графов, имеющей самое широкое практическое применение в компьютерной технике. Среди основных применений теории графов можно назвать расчеты и проектирование электронных схем, печатных плат, маршрутизация в локальных и глобальных сетях, расчеты водопроводных и тепловых сетей и др. В частности, алгоритм определения компонент связанности имеет самое широкое применение во многих языках программирования (xlisp) для сборки мусора. В рамках данного курсового проекта разработана программа определения компонент связанности неориентированного графа, работающая за линейное время. В разработке применен язык функционального программирования Lisp, элегантность которого и богатые выразительные способности позволили создать программу, имеющую простую и ясную структуру, но вместе с тем оптимальную по своим характеристикам.
Граф G(X) определяется своим множество вершин X={x1,x2,…,xn} и множеством ребер Y={y1,y2,…,yn}, соединяющих между собой вершины графа. Две вершины xi,xj называются связанными, если существует цепь S с концами xi и xj. Отношение связанности вершин является транзитивным (xi~xj, xj~xk Þ xi~xk). Компонентой связанности неориентированного графа G(X) называется подграф H(A) графа G(X), с множеством вершин A Ì X и множеством ребер в G(X), инцидентным только вершинам из A, причем ни одна вершина xi Î A не смежна ни одной вершине из X \ A. Граф G(X) может иметь множество компонент связанности.
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.
