Реєстраційний номер
0407U003975, Кандидатська дисертація
На здобуття
к.ф.-м.н.
Дата захисту
12-10-2007
Статус
Захищена
Назва роботи
Аналіз графів з позначеними вершинами
Здобувач
Сапунов Сергій Валерійович,
Керівник Грунський Ігор Сергійович
Опонент Капітонова Юлія Володимирівна
Опонент Рисцов Ігор Костянтинович
Установа, організація, у вченій раді якої відбудеться/відбувся захист
Інститут кібернетики ім. В.М.Глушкова НАН України
Опис
Дисертацію присвячено створенню експериментів з графами з позначеними вершинами шляхом аналізу та розрізнення пов'язаних з вершинами графа мов у алфавіті позначок для розпізнавання графів та їх вершин. Розроблено дескриптивні і алгоритмічні методи аналізу мов, асоційованих з вершинами графів та самими графами. Знайдено окремий вид графів, названих детермінованими, для яких визначена досяжна лінійна верхня оцінка довжини слова, яке розрізняє вершини. Вперше введено поняття експерименту з позначеним графом, що ґрунтується на перевірці мобільним агентом, який пересувається графом, наявності/відсутності у мові графу заданих множин слів. Запропоновано методи побудови діагностичного і контрольного експериментів з графами, розроблено алгоритми проведення таких експериментів. Введено поняття визначальної пари множин слів; знайдено критерії, за яких ця пара є контрольним експериментом, та за яких довільна пара скінченних множин є визначальною парою деякого позначеного графа.
Дата реєстрації
2007-10-23
Додано/оновлено в НРАТ
2020-04-04 / 2026-06-30