Головна Головна -> Реферати українською -> Дисертації та автореферати -> АНАЛІЗ ГРАФІВ З ПОЗНАЧЕНИМИ ВЕРШИНАМИ

АНАЛІЗ ГРАФІВ З ПОЗНАЧЕНИМИ ВЕРШИНАМИ

Назва:
АНАЛІЗ ГРАФІВ З ПОЗНАЧЕНИМИ ВЕРШИНАМИ
Тип:
Реферат
Мова:
Українська
Розмiр:
18,57 KB
Завантажень:
326
Оцінка:
 
поточна оцінка 5.0


Скачати цю роботу безкоштовно
Пролистати роботу: 1  2  3  4  5  6  7  8  9  10  11  12  13 
НАЦІОНАЛЬНА АКАДЕМІЯ НАУК УКРАЇНИ
ІНСТИТУТ КІБЕРНЕТИКИ ІМЕНІ В.М.ГЛУШКОВА
САПУНОВ СЕРГІЙ ВАЛЕРІЙОВИЧ
УДК 519.7
АНАЛІЗ ГРАФІВ З ПОЗНАЧЕНИМИ ВЕРШИНАМИ
01.05.01 – “Теоретичні основи інформатики та кібернетики”
АВТОРЕФЕРАТ
дисертації на здобуття наукового ступеня
кандидата фізико-математичних наук
Київ – 2007
Дисертацією є рукопис
Робота виконана в Інституті прикладної математики і механіки НАН України
Науковий керівник: кандидат фізико-математичних наук, с.н.с
Грунський Ігор Сергійович,
Слов’янський державний педагогічний університет,
доцент кафедри алгебри
Офіційні опоненти: доктор фізико-математичних наук, професор
Капітонова Юлія Володимирівна,
Інститут кібернетики імені В.М.Глушкова НАН України,
завідуюча відділом теорії цифрових автоматів
кандидат фізико-математичних наук
Рисцов Ігор Костянтинович,
Національний технічний університет України (КПІ),
доцент кафедри математичного моделювання
економічних систем
Провідна установа: Київський національний університет імені Тараса Шевченка,
факультет кібернетики,
кафедра теорії і технології програмування
Захист відбудеться “ 12 ” жовтня 2007 р. о 122 годині на засіданні спеціалізованої вченої ради Д.26.194.02 в Інституті кібернетики ім. В.М.Глушкова НАН України
за адресою: 03680 МСП Київ–187, проспект Академіка Глушкова, 40.
З дисертацією можна ознайомитися в науково-технічному архіві Інституту кібернетики ім. В.М.Глушкова НАН України за адресою:
03680 МСП Київ–187, проспект Академіка Глушкова, 40.
Автореферат розісланий “ 11 ” вересня 2007 р.
Вчений секретар
спеціалізованої вченої ради |
В.Ф. Синявський


ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ
Актуальність теми. Основною проблемою теоретичної кібернетики є проблема взаємодії керуючої та керованої систем (керуючого автомата та його операційного середовища). Біля витоків цієї проблематики стояли В.М. Глушков та К. Шеннон. Взаємодія автомату та середовища найчастіше зображується як процес пересування автомата позначеним графом або лабіринтом середовища. Таке зображення інтенсивно розвивається у працях В.Б. Кудрявцева та керованої ним школи. Автомат, знаходячись у вершині графа, сприймає деяку інформацію про позначки локального околу цієї вершини, а також має можливість змінювати ці позначки і/або ставити додаткові. На підставі сприйнятої інформації автомат пересувається у деяку суміжну вершину.
Однією з центральних та актуальних як у теоретичному, так і прикладному аспектах проблем, які виникають при дослідженні взаємодії автоматів та графів, є проблема аналізу або розпізнавання властивостей графа за різної апріорної інформації та при різних способах взаємодії автомата та графа.
При вирішенні проблеми аналізу графа операційного середовища виділилося кілька підходів. Один з них ґрунтується на тому, що досліджувані графи розглядаються як скінченні ініціальні автомати без виходу, тобто як скінченні орієнтовані графи з позначеними дугами. Такий підхід дозволяє використовувати методи та результати теорії автоматів, що є найстаршою та найбільш розвиненою галуззю теоретичної кібернетики. У рамках цього підходу у працях В.Б. Кудрявцева, Г.Ю. Кудрявцева, І.С. Грунського і Р.М. Олейника знайдено точні верхні оцінки найменшого часу, за який розрізняються два графи, запропоновано методи та алгоритми відрізнення графа-еталону від класу усіх таких графів, у яких кількість вершин не перевищує кількості вершин еталону. Другий підхід виник у межах вивчення проблеми навігації мобільних роботів та ґрунтується на тому, що операційне середовище розглядається як скінченний неорієнтований граф з позначеними кінцями ребер. У працях Г. Дудека, М. Дженкіна, Е. Міліоса та Д. Вілкеса запропоновано методи і алгоритми вирішення таких задач: задачі самолокалізації, тобто відрізнення деякої вершини відомого графа від усіх інших його вершин, і задачі контролю карти, тобто відрізнення графа-еталону від заданого класу графів. Третій підхід ґрунтується на тому, що операційне середовище розглядається як неорієнтований граф з позначеними вершинами.

Завантажити цю роботу безкоштовно
Пролистати роботу: 1  2  3  4  5  6  7  8  9  10  11  12  13 



Реферат на тему: АНАЛІЗ ГРАФІВ З ПОЗНАЧЕНИМИ ВЕРШИНАМИ

BR.com.ua © 1999-2017 | Реклама на сайті | Умови використання | Зворотній зв'язок