Анотація до роботи:

Сапунов С.В. Аналіз графів з позначеними вершинами. – Рукопис.

Дисертація на здобуття наукового ступеня кандидата фізико-математичних наук за спеціальністю 01.05.01 – теоретичні основи інформатики та кібернетики. – Інститут кібернетики імені В.М.Глушкова НАН України, Київ, 2007.

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

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

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

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

У роботі отримано такі результати:

повністю вирішено задачу характеризації відношення невідрізнимості вершин позначеного графа за породжуваними ними мовами;

введено клас графів, названих детермінованими, для яких знайдено досяжну лінійну від кількості вершин графа верхню оцінку довжини слова, що розрізняє дві вершини такого графа;

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

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

вперше введено поняття експерименту з позначеним графом, що ґрунтується на перевірці мобільним агентом, який пересувається графом, наявності/відсутності у мові графа заданих множин слів; розглянуто два види експериментів: діагностичні, тобто експерименти по розпізнаванню початкової вершини, у яку був встановлений мобільний агент, і контрольні, які перевіряють чи є ізоморфним досліджуваний граф до графа-еталону;

запропоновано методи побудови діагностичного і контрольного експериментів з позначеними графами; розроблено алгоритми проведення таких експериментів;

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

Ці результати є новими і завершеними. Таким чином вперше повністю вирішена задача контролю вершин граф і самого графа з позначеними вершинами шляхом експерименту з ним.

Публікації автора:

1. Сапунов С.В. Эквивалентность отмеченных графов // Труды института прикладной математики и механики. – 2002. – Т. 7. – С. 162-167.

2. Сапунов С.В. Контроль детерминированных графов // Труды института прикладной математики и механики. – 2003. – Т. 8. – С. 106-110.

3. Сапунов С.В. Построение контрольных экспериментов для неориентированных графов // Вісник ДонНУ, серія А: Природничі науки. – 2003. – В. 1. – С. 351-354.

4. Сапунов С.В. Структура класса неотличимости неориентированных помеченных графов // Труды института прикладной математики и механики. – 2005. – Т. 10. – С. 166-172.

5. Сапунов С.В. Проверка соответствия карты при навигации мобильных роботов // Искусственный интеллект. – 2006. – № 3 – С. 677-685.

6. Грунский И.С, Сапунов С.В. О контроле графов с отмеченными вершинами // Тезисы докладов XIII международной конференции «Проблемы теоретической кибернетики» (Казань, 27-31 мая 2002 г.). – М.: Изд-во центра приклад. исслед. при мех.-мат. ф-те МГУ им. М.В. Ломоносова, 2002. – С. 52.

7. Сапунов С.В. Отличимость вершин графа моделирующего информационную среду // Всеукраїнська конференція «Алгебраїчні методи дискретної математики (теорія та методологія)» в ЛДПУ iм. Т.Г. Шевченка (Луганськ, 23-27 вересня 2002 р.). – Луганськ: Alma Mater, 2002. – С. 81-82.

8. Grunsky I.S., Sapunov S.V. Map validation of robot environments // V international congress on mathematical modeling: Book of abstracts (September 30 – October 6, 2002). – M.: Изд-во мех.-мат. ф-та МГУ им. М.В. Ломоносова, 2002. – С. 93.

9. Грунский И.С, Сапунов С.В. О контроле детерминированных графов // Труды V международной конференции «Дискретные модели в теории управляющих систем» (Ратмино, 26-29 мая 2003 г.). – М.: Изд. отдел ф-та ВМиК МГУ им. М.В. Ломоносова, 2003. – С. 27-29.

10. Сапунов С.В. О неотличимости неориентированных графов с помеченными вершинами // Труды VI международной конференции «Дискретные модели в теории управляющих систем» (Москва, 7-11 декабря 2004 г.). – М.: Изд. отдел ф-та ВМиК МГУ им. М.В. Ломоносова, 2004. – С. 209-211.

11. Сапунов С.В. Структура класса неотличимости неориентированных помеченных графов // Материалы VIII международного семинара «Дискретная математика и ее приложения» (2-6 февраля 2004 г.). – М.: Изд-во мех.-мат. ф-та МГУ им. М.В. Ломоносова, 2004. – С. 304-307.

12. Сапунов С.В. О контроле помеченных графов при неизвестной верхней оценке числа вершин // Тезисы докладов XIV международной конференции «Проблемы теоретической кибернетики» (Пенза, 23-28 мая 2005 г.). – М.: Изд-во мех.-мат. ф-та МГУ им. М.В. Ломоносова, 2005. – С. 138.

13. Сапунов С.В. Контрольные эксперименты с помеченными графами при неизвестной верхней оценке числа вершин // Труды VII международной конференции «Дискретные модели в теории управляющих систем» (Покровское, 4-6 марта 2006 г.). – М.: МАКС Пресс, 2006. – С. 325-331.

14. Сапунов С.В. Анализ графов с помеченными вершинами // Материалы IX международной конференции «Интеллектуальные системы и компьютерные науки» (Москва, 23-27 октября 2006 г.). – М.: Изд-во мех.-мат. ф-та МГУ им. М.В. Ломоносова, 2006. – С. 233-234.