Реферат за темою випускної роботи

Зміст

Вступ
1. Актуальність теми
2. Мета і задачі дослідження та заплановані результати
3. Огляд досліджень та розробок
3.1 Огляд національних джерел
3.2 Огляд локальних джерел
4. Підхід до уніфікації синтезу автоматів Мура в базисі FPGA
Висновки
Перелік посилань

Вступ

У науковій роботі студента розглядається тематика, пов'язана з автоматним аналізом геометричних середовищ, графів, та інших дискретних структур. Одним із завдань даної тематики, є завдання опису структури об'єкта на основі інформації отриманої при обході графа за його межі. Подібні задачі виникають у робототехніці, молекулярної фізики: побудова моделі карти середовища, моделі об'єкта. Відомий ряд робіт присвячених завданню розпізнавання структури об'єкта, в яких розглядався випадок вирішення подібних завдань з використанням одного автомата (далі агента). В даній роботі пропонується алгоритм вирішення задачі розпізнавання з використанням двох агентів. В якості моделі об'єкта використовується неорієнтований граф. Перший агент-дослідник (АІ) виконує переміщення по вихідному графу і передачу інформації другий агент-експериментатору (АЕ). Другий агент за отриманою інформацією описує структуру графа.

1. Актуальність теми

Тема стала актуальною ще в 50-х роках минулого століття, коли почали з'являтися перші статті Шеннона К., в якій фактично розглядалася задача пошуку автоматом-мишею певної мети в лабіринті, що значною мірою визначило тематику направлення на наступні роки. Через 60 років, тема залишається актуальною і дуже часто використовується в створенні ігор, програм та інших продуктів.

2. Мета і задачі дослідження та заплановані результати

Основні задачі дослідження:

Розробка нового алгоритму для графа, що складається з декількох сільносвязних подграфов, з'єднаних мостами. Потрібно розробити такі алгоритми пересування агента АІ по вихідному графу G з передачею інформації про це, і відновлення графа агентом АЕ за отриманими даними у вигляді формули, що АІ за кінцеве число кроків незалежно від початкового розміщення обійде частина внутрен-них вершин G і всі граничні вершини , покроково передаючи інформацію, за якою АЕ через кінцеве число кроків опише граф P, ізоморфний вихідного графу G.
Основні завдання дослідження:

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.2 Огляд локальних джерел

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

3.3 Огляд національних джерел

За тематикою теорії графів у національних джерелах практично ніякої інформації, зате наші співвітчизники дуже цікавляться цією темою, часто публікуючи нові статті, алгоритми, напрацювання і рішення.

Висновки

В ході виконання даної роботи, були проведені розрахунки, використовувалися матриці для перемножування і другі математичні операції. У роботі запропоновано алгоритм відновлення структури графа у вигляді формули, що відбиває склад вихідного графа як комбінацію базових структур.

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

Інститут інформатики та штучного інтелекту

Кафедра комп'ютерної інженерії

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

Розпізнавання колективом агентів графа мозаїчної структури, що складається з сильно-зв'язкових подграфов, з'єднаних мостами

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