Реферат по теме выпускной работы

Содержание

Введение
1. Актуальность темы
2. Цель и задачи исследования, планируемые результаты
3. Обзор исследований и разработок
3.1 Обзор национальных источников
3.2 Обзор локальных источников
3.3 Обзор национальных источников
Выводы
Список источников

Введение

В научной работе студента рассматривается тематика, связанная с автоматным анализом геометрических сред, графов, и других дискретных структур. Одной из задач данной тематики, является задача описания структуры объекта на основе информации полученной при обходе графа по его границе. Подобные задачи возникают в робототехнике, молекулярной физике: построение модели карты среды, модели объекта. Известен ряд работ посвященных задаче распознавания структуры объекта, в которых рассматривался случай решения подобных задач с использованием одного автомата (далее агента). В настоящей работе предлагается алгоритм решения задачи распознавания с использованием двух агентов. В качестве модели объекта используется неориентированный граф. Первый агент-исследователь (АИ) выполняет перемещения по исходному графу и передачу информации второму агенту-экспериментатору (АЭ). Второй агент по полученной информации описывает структуру графа.

1. Актуальность темы

Тема стала актуальной ещё в 50-х годах прошлого века, когда начали появляться первые статьи Шеннона К., в которой фактически рассматривалась задача поиска автоматом-мышью определенной цели в лабиринте, что в значительной мере определило тематику направления на последующие годы. Спустя 60 лет, тема остаётся актуальной и очень часто используется в создании игр, программ и других продуктов.

2. Цель и задачи исследования, планируемые результаты

Разработка нового алгоритма для графа, состоящего из нескольких сильносвязных подграфов, соединенных мостами. Требуется разработать такие алгоритмы передвижения агента АИ по исходному графу G с передачей информации об этом, и восстановления графа агентом АЭ по полученным данным в виде формулы, что АИ за конечное число шагов независимо от начального размещения обойдет часть внутренних вершин G и все граничные вершины, пошагово передавая информацию, по которой АЭ через конечное число шагов опишет граф P, изоморфный исходному графу G.

Основные задачи исследования:

Разработка алгоритма для АИ и АЭ, для обхода и распознавания графа.
Создание программы для реализации этих алгоритмов.

Объект исследования: автоматный анализ графов

Предмет исследования: методы и алгоритмы восстановления структуры графа, которые состоят из сильно-связных подграфов, соединённых мостами

В рамках магистерской работы планируется получение новых научных результатов по следующим направлениям:

Разработка эффективного алгоритма для обхода графа мозаичной структуры состоящих сильно-связных подграфов, соединённых мостами.
Разработка эффективного алгоритма для восстановления графа.
Определение областей применения для данного алгоритма.
Создание кроссплатформенной программы для обхода графа.

Для экспериментальной оценки полученных теоретических результатов и формирования фундамента последующих исследований, в качестве практических результатов планируется разработка кроссплатформенной, настраиваемой и функциональной системы для работы с графом:

Использование кроссплатформенной библиотеки классов Qt.
Создание кода на С++.
Возможность управления процессом распознавания.
Возможность сохранять и восстанавливать из файла.

3. Обзор исследований и разработок

Мой научный руководитель Шатохина Н.К., опубликовала работу под названием "Распознавание графа мозаичной структуры колективом агентов", в которой описан принцип работы с графом мозаичной структуры специального вида сильно-связного графа.

Распознавание графа
Процесс распознавания состоит из двух алгоритмов. Первый алгоритм Обход описывает перемещение АИ по неизвестному графу G и генерацию информации для АЭ. Второй алгоритм Восстановление, представляет собой анализ полученной информации, на основании которой создается символьное описание графа Р, изоморфного исходному G.

Алгоритм Обход работы АИ.
Предполагается, что агент случайным образом может быть помещен в любую вершину графа, поэтому алгоритм состоит из двух этапов. На первом этапе, если необходимо АИ выходит на границу, а на втором этапе АИ обходит граф против часовой стрелки по граничным ребрам до тех пор, пока не возвратится в вершину выхода на границу. Алгоритм АИ выхода на границу. Агент, помещенный в произвольную вершину v, определяет ее степень, если это внутренняя вершина, т.е. deg(v)=6, то перемещается по диаметрально противоположному ребру относительно первого встреченного ребра до следующей вершины. Эту процедуру повторяет до тех пор, пока не найдет граничную вершину, выбирает первое граничное ребро путем поворота против часовой стрелки, которое помечает маркером. Алгоритм обхода графа по граничным вершинам. Дальнейшее перемещение агента происходит по границе графа в направлении против часовой стрелки, начиная из найденной вершины и ребра. Агент перемещается к следующей вершине по выбранному ребру, фиксируя букву-направление своего перемещения. Далее АИ проверяет, является ли помеченным маркером выбранное ребро. Если оно не помечено, он пересылает букву АЭ и продолжает движение, в противном случае АИ завершает свою работу. Алгоритм Обход состоит двух частей. Первая часть может отсутствовать. Лемма 1. Если в мозаичном графе n вершин, то максимальный путь по внутренним вершинам графа в выбранном направлении не превосходит величины l=(n-1)/3. Лемма 2. Любой маршрут по внутренним вершинам графа в выбранном направлении перемещения является незамкнутым. Исходный граф G может иметь более сложную структуру, чем базовая структура, для которой выполняется следующее. Лемма 3. Длина маршрута p по граничным вершинам G При подсчете временной сложности имеет место: для выхода на границу графа согласно лемме 1 уходит время (n-1)/3, т.е. О(n); согласно лемме 3 обход по границе не превосходит величины 2n, значит оценивается как О(n) шагов. Емкостная сложность Е(n) отсутствует, т.к. агенту ничего не требуется сохранять.

Рисунок 1. - Принцип работы АИ(выход на границу и дальнейший обход)

Алгоритм Восстановление работы АЭ.
В алгоритме анализируется строка направлений, сгенерированная и переданная АИ. Вначале производится поиск точек перегиба. Если точки имеются, то определяется идентификатор обратной базовой структуры, содержащий очередную точку перегиба, в качестве второй вершины маршрута. Производится преобразование строки, наращивание счетчиков внутренних Сч_вв и граничных Сч_гв вершин, присоединение данной структуры к графу, что фиксируется добавлением в формулу со знаком - соответствующего фрагмента. Если нет таких точек, то вновь просматривается сначала строка для поиска идентификаторов базовых структур. Каждый раз, когда находится такой идентификатор, производится удаление из строки соответствующей подстроки, уменьшение значения Сч_вв и Сч_гв, отделение данной структуры от графа, и добавление в формулу со знаком + соответствующего фрагмента. В алгоритме распознавания осуществляется два просмотра исходной строки. Если имеется хотя бы одна точка перегиба, то в граф добавляются соответствующее базовой структуре количество вершин и устанавливается неявная нумерация u: V(G∪G)→V(H∪G), где G' граф включенной части. Нумерация u(v)=Сч_вв или u(v)=Сч_гв, для всех v∈G'. Эта нумерация является биекцией, т.к. добавление базовых структур выполняется взаимно однозначно в соответствии с их идентификаторами. При выполнении операции отделения в графе Н создается неявная нумерация d: V(G')→V(H) вершин графа G в вершины графа Н, тех вершин, которые содержатся в отделяемой базовой структуре. При этом равенство d(v)= t, где t=Сч_вв или t=Сч_гв. Эта нумерация также является биекцией, т.к. удаление базовых структур выполняется взаимно однозначно в соответствии с их идентификаторами. Тем самым доказана следующая терема. Теорема 1. Выполняя алгоритмы распознавания, агенты распознают любой граф G с точностью до изоморфизма. При подсчете временной сложности алгоритма работы АЭ учитывается, что распознавание структуры графа выполняется за счет двукратного просмотра исходной строки, длина которой не может превосходить 2n букв, т.е. временная сложность оценивается следующим образом. Процесс присоединения базовых структур выполняется не более чем возможное количество точек перегиба, а это не более чем за n/2 шагов. Процесс отсечения базовых структур выполняется не более чем возможное количество углов в графе, т.е. не более, чем за n/2 шагов. Второй просмотр строки выполняется не более чем за 2n шагов. Следовательно, суммарная временная сложность оценивается как Т(n)=О(n). Таким образом, совместная работа АИ и АЭ оценивается как O(n). Емкостная сложность Е(n) определяется сложностью списков строки направлений S, множества граничных вершин V'⊂V, и строки формул F, сложность которых определяется величинами O(n), O(n), O(n). В связи с ограничениями на объем подробные описания алгоритмов опущены.

3.1 Обзор национальных источников

Капитонова Ю.В., Летичевский А.А. Математическая теория проектирования вычислительных систем

Излагаются основы математического аппарата и современных методов проектирования систем преобразования информации: аппаратуры вычислительных машин, программ и программных систем, систем управления и обработки данных, основанных на применении средств вычислительной техники.Первая часть посвящена обзору основных математических моделей вычислительных систем. Вторая часть содержит изложение практических методов проектирования различного типа систем — аппаратуры ЭВМ, последовательных и параллельных программ, компонент общесистемной математики.Для математиков и инженеров — разработчиков аппаратных и программных средств, а также для студентов и аспирантов в области информатики и вычислительной техники[1].

В.Б. Кудрявцев, Ш. Ушчумлич, Г. Килибарда. О поведении автоматов в лабиринтах
Дается обзор более 80-ти работ, выполненных за последние 20 лет, по поведению систем автоматов в лабиринтах. Выделяются основные понятия, проблематика, достижения, методы решения задач и открытые проблемы. Основные утверждения в ряде случаев приводятся в более сильном виде по сравнению с формулировками авторов. Статья содержит также новые результаты по проблеме обхода лабиринтов автоматами[2].

3.3 Обзор локальных источников

В Донецком национальном техническом университете есть публикация, на тему Распознавание графа мозаичной структуры коллективом агентов, авторы: Шатохина, Н.К. Шатохин, П.А.
Рассмотрена проблема анализа дискретных структур, представленных графом специального вида. В частности, рассмотрена задача описания структуры графа на основе информации, полученной при обходе его по границе. Описан алгоритм решения задачи, приведены оценки его временной и емкостной сложности[3].

3.2 Обзор национальных источников

По тематике теории графов в национальных источниках практически никакой информации, зато наши соотечественники очень интересуются этой темой, часто публикуя новые статьи, алгоритмы, наработки и решения.

Выводы

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

Кобернюк Сергей Александрович

Кафедра программного обеспечения интеллектуальных систем

Специальность Программное обеспечение систем

Специальность Компьютерные системы и сети

Распознавание коллективом агентов графа мозаичной структуры, состоящего из сильно-связных подграфов, соединённых мостами

Научный руководитель: кандидат технических наук, доц. Шатохина Наталья Константиновна