Аналіз графів з позначеними вершинами - Автореферат

НАЦІОНАЛЬНА АКАДЕМІЯ НАУК УКРАЇНИ ІНСТИТУТ КІБЕРНЕТИКИ ІМЕНІ В.М.ГЛУШКОВА АВТОРЕФЕРАТ дисертації на здобуття наукового ступеня кандидата фізико-математичних наук 01.05.01 - “Теоретичні основи інформатики та кібернетики” АНАЛІЗ ГРАФІВ З ПОЗНАЧЕНИМИ ВЕРШИНАМИ САПУНОВ СЕРГІЙ ВАЛЕРІЙОВИЧ Київ - 2007 ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ Актуальність теми. Взаємодія автомату та середовища найчастіше зображується як процес пересування автомата позначеним графом або лабіринтом середовища. Автомат, знаходячись у вершині графа, сприймає деяку інформацію про позначки локального околу цієї вершини, а також має можливість змінювати ці позначки і/або ставити додаткові. Однією з центральних та актуальних як у теоретичному, так і прикладному аспектах проблем, які виникають при дослідженні взаємодії автоматів та графів, є проблема аналізу або розпізнавання властивостей графа за різної апріорної інформації та при різних способах взаємодії автомата та графа. У рамках цього підходу у працях В.Б. Кудрявцева, Г.Ю. Кудрявцева, І.С. Грунського і Р.М. Олейника знайдено точні верхні оцінки найменшого часу, за який розрізняються два графи, запропоновано методи та алгоритми відрізнення графа-еталону від класу усіх таких графів, у яких кількість вершин не перевищує кількості вершин еталону. Її прикладна актуальність визначається тим, що проблеми самолокалізації та контролю для таких графів далекі від розв’язання, і їх дослідження знаходиться у початковому стані. Дослідження з проблеми дисертаційної роботи проводилися у відповідності з планами наукових досліджень відділу теорії керуючих систем ІПММ НАН України в рамках тем: №0104u000863 “Алгебраїчні, комбінаторні, логічні та еволюційні методи дослідження дискретних та безперервних систем та їх застосування до задач ідентифікації та керування”, №0204u000771 “Дослідження актуальних проблем моделювання, керування та ідентифікації дискретних систем”. Метою дисертаційної роботи є створення експериментів з графами шляхом аналізу та розрізнення пов’язаних з вершинами графа мов у алфавіті позначок для розпізнавання графів та їх вершин. У дисертаційній роботі отримано такі нові результати: - розроблено методи перевірки невідрізнимості вершин, індукованої рівністю їх мов, та методи побудови слів, які розрізнюють вершини; показано, що складність цих методів у загальному випадку експоненціальна від кількості вершин графа; - знайдено окремий вид графів, названі детермінованими, для яких визначено досяжну лінійну верхню оцінку довжини слова, яке розрізняє вершини; - введено скінченні множини слів, названі ідентифікаторами, які відрізняють одну вершину графа від усіх інших його вершин; знайдено умови існування, оцінки складності ідентифікаторів та розроблено методи їх побудови; - введено відношення невідрізнимості графів, які індуковані рівністю їх мов та сімей мов їх вершин; розроблено методи їх перевірки; досліджено структуру, потужність і екстремальні елементи класів невідрізнимості; - вперше введено поняття експерименту з позначеним графом, який ґрунтується на перевірці мобільним агентом, що пересувається графом, наявності/відсутності у мові графа заданих множин слів; розглянуто два види експериментів: діагностичні, тобто експерименти по розпізнаванню початкової вершини, у яку був встановлений мобільний агент, і контрольні, які перевіряють чи ізоморфний досліджуваний граф до заданого графа-еталона; - розроблено метод побудови і проведення діагностичних експериментів з позначеними графами, який ґрунтується на побудові ідентифікаторів усіх вершин досліджуваного графа; показано, що для детермінованого графа цей метод за складністю поліноміальний; - для ініціального сильно детермінованого графа, який є окремим випадком симетричного детермінованого графа, розроблено поліноміальний метод побудови та проведення контрольного експерименту відносно класу усіх таких графів з тією ж кількістю вершин; - розроблено поліноміальний метод побудови та проведення контрольного експерименту для ініціального сильно детермінованого графа-еталона відносно класу усіх таких графів; цей метод ґрунтується на введеному новому зображенні графа визначальною парою скінчених множин слів у алфавіті позначок, аналогічною системі визначальних співвідношень для скінченного автомату; знайдено критерії, за яких довільна пара скінченних множин слів є визначальною парою деякого позначеного графа. Основні результати роботи доповідалися та обговорювалися на: - XIII Міжнародній конференції “Проблемы теоретической кибернетики” (Казань, 2002); - Всеукраїнській конференції “Алгебраїчні методи дискретної математики (теорія та методологія)” (Луганськ, 2002); - V Міжнародному конгресі по математичному моделюванню (Дубна, Росія, 2002); - V Міжнародній конференції “Дискретные модели в теории управляющих систем” (Ратміно, Росія, 2003); - VIII Міжнародному семінарі “Дискретная математика и ее приложения” (Москва, 2004); - VI Міжнародній конференції “Дискретные модели в теории управляющих систем” (Москва, 2004); - XIV Міжнародній конференції “Проблемы теоре