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