Банк рефератов содержит более 364 тысяч рефератов, курсовых и дипломных работ, шпаргалок и докладов по различным дисциплинам: истории, психологии, экономике, менеджменту, философии, праву, экологии. А также изложения, сочинения по литературе, отчеты по практике, топики по английскому.
Полнотекстовый поиск
Всего работ:
364150
Теги названий
Разделы
Авиация и космонавтика (304)
Административное право (123)
Арбитражный процесс (23)
Архитектура (113)
Астрология (4)
Астрономия (4814)
Банковское дело (5227)
Безопасность жизнедеятельности (2616)
Биографии (3423)
Биология (4214)
Биология и химия (1518)
Биржевое дело (68)
Ботаника и сельское хоз-во (2836)
Бухгалтерский учет и аудит (8269)
Валютные отношения (50)
Ветеринария (50)
Военная кафедра (762)
ГДЗ (2)
География (5275)
Геодезия (30)
Геология (1222)
Геополитика (43)
Государство и право (20403)
Гражданское право и процесс (465)
Делопроизводство (19)
Деньги и кредит (108)
ЕГЭ (173)
Естествознание (96)
Журналистика (899)
ЗНО (54)
Зоология (34)
Издательское дело и полиграфия (476)
Инвестиции (106)
Иностранный язык (62792)
Информатика (3562)
Информатика, программирование (6444)
Исторические личности (2165)
История (21320)
История техники (766)
Кибернетика (64)
Коммуникации и связь (3145)
Компьютерные науки (60)
Косметология (17)
Краеведение и этнография (588)
Краткое содержание произведений (1000)
Криминалистика (106)
Криминология (48)
Криптология (3)
Кулинария (1167)
Культура и искусство (8485)
Культурология (537)
Литература : зарубежная (2044)
Литература и русский язык (11657)
Логика (532)
Логистика (21)
Маркетинг (7985)
Математика (3721)
Медицина, здоровье (10549)
Медицинские науки (88)
Международное публичное право (58)
Международное частное право (36)
Международные отношения (2257)
Менеджмент (12491)
Металлургия (91)
Москвоведение (797)
Музыка (1338)
Муниципальное право (24)
Налоги, налогообложение (214)
Наука и техника (1141)
Начертательная геометрия (3)
Оккультизм и уфология (8)
Остальные рефераты (21697)
Педагогика (7850)
Политология (3801)
Право (682)
Право, юриспруденция (2881)
Предпринимательство (475)
Прикладные науки (1)
Промышленность, производство (7100)
Психология (8694)
психология, педагогика (4121)
Радиоэлектроника (443)
Реклама (952)
Религия и мифология (2967)
Риторика (23)
Сексология (748)
Социология (4876)
Статистика (95)
Страхование (107)
Строительные науки (7)
Строительство (2004)
Схемотехника (15)
Таможенная система (663)
Теория государства и права (240)
Теория организации (39)
Теплотехника (25)
Технология (624)
Товароведение (16)
Транспорт (2652)
Трудовое право (136)
Туризм (90)
Уголовное право и процесс (406)
Управление (95)
Управленческие науки (24)
Физика (3463)
Физкультура и спорт (4482)
Философия (7216)
Финансовые науки (4592)
Финансы (5386)
Фотография (3)
Химия (2244)
Хозяйственное право (23)
Цифровые устройства (29)
Экологическое право (35)
Экология (4517)
Экономика (20645)
Экономико-математическое моделирование (666)
Экономическая география (119)
Экономическая теория (2573)
Этика (889)
Юриспруденция (288)
Языковедение (148)
Языкознание, филология (1140)

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

Название: Определение связности графа на Лиспе
Раздел: Рефераты по информатике, программированию
Тип: курсовая работа Добавлен 15:26:12 11 октября 2008 Похожие работы
Просмотров: 184 Комментариев: 2 Оценило: 0 человек Средний балл: 0 Оценка: неизвестно     Скачать

РЕФЕРАТ

Пояснительная записка к курсовой работе содержит 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(xysnaidsnov) – определяет, является ли вершина y смежной с одной из новых вершин (x – входит в список новых вершин, y – не входит в списки новых и найденных вершин).

Параметры:

- x - первая вершина ребра;

- y - вторая вершина ребра;

- snaid - список найденных вершин;

- snov - список новых вершин.

Функция smez(snaidsnovsreb) - поиск смежных с новыми вершинами вершин.

Параметры:

- 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 не является новой вершиной

((member y snov) nil) ;y является новой вершиной

((member y snaid) nil) ;y является ранее найденной вершиной

(t t))) ;вершина является новой смежной вершиной

;поиск смежных вершин (список найденных вершин, список новых вершин, список ребер)

(defun smez(snaid snov sreb)

(cond

((null sreb) nil) ;конецпоиска

((smezver (caar sreb) (cadar sreb) snaid snov) ;смежнаявершина

(cons (cadar sreb) (smez snaid snov (cdr sreb)))) ;добавлениевсписок

((smezver (cadar sreb) (caar sreb) snaid snov) ;смежнаявершина

(cons (caar sreb) (smez snaid snov (cdr sreb)))) ;добавлениевсписок

(t (smez snaid snov (cdr sreb))))) ;пропускребра

;поиск в ширину (список найденных вершин, список новых найденных вершин,

; вершина для поиска, список ребер)

(defun shir(snaid snov y sreb)

(cond

((null snov) nil) ;не найдено ни одной новой вершины

((member y snov) t) ;вершина найдена

(t (shir (append snaid snov) (smez snaid snov sreb) y sreb)))) ;добавление новых вершин

;поиск пути (первая вершина, вторая вершина, список ребер)

(defun path(x y sreb)

(shir nil (list x) y sreb)) ;поиск в ширину

;перебор вершин (первая вершина, список вершин, список ребер)

(defun perebor(fver sver sreb)

(cond

((null sver) t) ;конец перебора

((path fver (car sver) sreb) (perebor fver (cdr sver) sreb)) ;путьнайден

(t nil))) ;нет пути

;определение связанности графа(список вершин, список ребер)

(defun svgraf(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

Оценить/Добавить комментарий
Имя
Оценка
Комментарии:
Где скачать еще рефератов? Здесь: letsdoit777.blogspot.com
Евгений07:27:57 19 марта 2016
Кто еще хочет зарабатывать от 9000 рублей в день "Чистых Денег"? Узнайте как: business1777.blogspot.com ! Cпециально для студентов!
19:40:12 28 ноября 2015

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

Назад
Меню
Главная
Рефераты
Благодарности
Опрос
Станете ли вы заказывать работу за деньги, если не найдете ее в Интернете?

Да, в любом случае.
Да, но только в случае крайней необходимости.
Возможно, в зависимости от цены.
Нет, напишу его сам.
Нет, забью.



Результаты(150062)
Комментарии (1830)
Copyright © 2005-2016 BestReferat.ru bestreferat@mail.ru       реклама на сайте

Рейтинг@Mail.ru