РЕФЕРАТ
Пояснительная записка к курсовой работе содержит 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, причем это одно и то же ребро.