Search academic texts

Registration Number

0825U004163, PhD dissertation

Status

Доктор філософії

Date

popup.evolution

o

Title

The linguistic presentation of deterministic graphs

Author

Mykola I. Prytula,

popup.head Oleksii S. Senchenko
popup.opponent Oleksandr O. Marchenko
popup.opponent Larysa S. Koriashkina
popup.review Yuriy N. Kononov
popup.review Serhii V. Sapunov

Description

Дисертаційна робота присвячена удосконаленню, систематизації та програмному моделюванню лінгвістичного представлення детермінованих графів двома множинами слів у алфавіті їх міток та розв’язанню задачі характеризації такого представлення. Лінгвістичне представлення графа з використанням множин рядкового типу має особливу цінність у контексті моделювання мобільних агентів-роботів, що переміщуються цим графом. Представлення графа множинами слів дозволяє агенту здійснювати обробку даних у символьній формі, що може спростити алгоритмічні процедури. Зокрема, символьне кодування вершин і ребер полегшує пошук, зіставлення та верифікацію маршрутів, оскільки переходи агента можуть бути описані у вигляді простих операцій над рядками. Це створює інтуїтивний і компактний механізм опису поведінки агента, який не потребує складних структур на зразок матриць суміжності чи словників. У результаті мобільний агент може ефективніше використовувати текстові інструкції як стандартний інтерфейс для взаємодії з графом, що робить підхід універсальним та придатним для широкого кола задач інформатики. У роботі уточнено, узагальнено та формалізовано алгоритм побудови графа за парою; доведено визначальну роль канонічної визначальної пари детермінованого графа у його лінгвістичному представленні; знайдено об'єм компонент канонічної визначальної пари детермінованого графа та доведено мінімальність метричних властивостей канонічної визначальної пари серед усіх визначальних пар заданого детермінованого графа; знайдено еквівалентні перетворення заданої коректної пари та розроблено алгоритм її перетворення у канонічну визначальну пару; розроблено алгоритм знаходження найкоротших шляхів від ініціальної до всіх інших вершин детермінованого графа; розроблено інформаційну модель - програмний прототип бібліотеки лінгвістичного представлення детермінованих графів. Теоретичне значення отриманих результатів полягає у розробці формалізованого підходу до лінгвістичного представлення детермінованих графів; закладенні основ для подальших досліджень у галузі символьної обробки графових даних; поглибленні зв’язку між теорією графів і теорією автоматів та формальних мов, що може дозволити застосовувати апарат граматик та автоматів для дослідження властивостей графових структур. Одержані результати можуть бути основою для розв’язання інших прикладних задач, зокрема, задачі побудови найкоротших шляхів між усіма вершинами детермінованого графа. Практичне значення отриманих результатів полягає у можливості використання запропонованого методу для компактного подання графових структур у програмних системах; лінгвістичний підхід полегшує реалізацію алгоритмів обробки графів у середовищах, орієнтованих на роботу з текстовими або символьними даними та відкриває нові можливості для застосування у задачах мобільних роботів, оптимізації, систем штучного інтелекту, лінгвістичного моделювання даних, теорії керування та систем; розроблені алгоритми можуть бути використані у навчальних та дослідницьких програмних засобах.

Registration Date

2025-11-26

popup.nrat_date

2025-11-26