ВВЕДЕНИЕ Тема данной работы – написание программы на XLisp

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

ОСНОВНАЯ ЧАСТЬ РАБОТЫ
1 Анализ задачи
В данной работе необходимо написать программу на языке XLisp, определяющую, является ли данный неориентированный граф связным. Для этого необходимо запрограммировать предварительно предикат (path X Y), проверяющий, существует ли путь из вершины X в вершину Y.
Граф, или неориентированный граф G – это упорядоченная пара G := (V, E), для которой выполнены следующие условия:
V – это непустое множество вершин или узлов;
E – это множество пар (в случае неориентированного графа – неупорядоченных) вершин, называемых рёбрами.
V (а значит и, E, иначе оно было бы мультимножеством) обычно считаются конечными множествами. Многие хорошие результаты, полученные для конечных графов, неверны (или каким-либо образом отличаются) для бесконечных графов. Это происходит потому, что ряд соображений становится ложным в случае бесконечных множеств [2].
Вершины и рёбра графа называются также элементами графа, число вершин в графе |V| – порядком, число рёбер |E| – размером графа.
Вершины u и v называются концевыми вершинами (или просто концами) ребра e={u,v}. Ребро, в свою очередь, соединяет эти вершины. Две концевые вершины одного и того же ребра называются соседними.
Ниже приведены некоторые критериальные (эквивалентные) определения связного графа. Граф называется односвязным (связным), если:
У него одна компонента связности
Существует путь из любой вершины в любую другую вершину
Существует путь из

saxwoman 4.9

Опыт написания студенческих работ более 10 лет. Большая база готовых работ Гуман.науки: - юриспруденция - экономика, финансы, налоги - менеджмент, маркетинг - физическая культура и спорт, БЖД - философия , психология и прочие

Нанять автора