Алгебраическая теория графовых квазибесконтурных автоматов тема диссертации и автореферата по ВАК РФ 00.00.00, кандидат наук Фарахутдинов Ренат Абуханович

• Фарахутдинов Ренат Абуханович
• кандидат наук
• 2025

Оглавление диссертации кандидат наук Фарахутдинов Ренат Абуханович

Введение

Глава 1. Основные понятия и определения

1.1 Элементы алгебры бинарных отношений и теории полугрупп

1.2 Элементы теории графов

1.3 Элементы теории графовых автоматов

Глава 2. Универсальные графовые автоматы

2.1 Определяемость универсальных графовых автоматов своими полугруппами входных сигналов

2.2 Конкретная характеризация универсальных графовых автоматов

2.3 Об элементарной аксиоматизации классов универсальных графовых автоматов

2.4 Строение изоморфизмов универсальных графовых автоматов

2.5 Группы автоморфизмов универсальных графовых автоматов

Глава 3. Универсальные графовые полуавтоматы

3.1 Конкретная характеризация универсальных графовых полуавтоматов

3.2 Абстрактная характеризация универсальных графовых полуавтоматов

3.3 Относительно элементарная определимость класса универсальных графовых полуавтоматов в классе полугрупп

3.4 Приложения относительно элементарной определимости класса универсальных графовых полуавтоматов в классе полугрупп

Глава 4. Линейное упорядочивание автоматов

4.1 Алгоритм перебора с возвратами и отсечениями

4.1.1 Алгоритм перебора с возвратами и отсечениями для полуавтоматов

4.1.2 Алгоритм перебора с возвратами и отсечениями для автоматов

4.2 Метод имитации отжига

Стр.

4.3 Алгоритм пчелиной колонии

4.4 Программная реализация методов линейного упорядочивания полуавтоматов

Заключение

Список литературы

Список рисунков

Список таблиц

Список алгоритмов

Приложение А. Свидетельства о государственной регистрации

программ для ЭВМ

Введение диссертации (часть автореферата) на тему «Алгебраическая теория графовых квазибесконтурных автоматов»

Введение

Данная работа посвящена алгебраической теории графовых автоматов. Предметом изучения теории автоматов являются различные устройства преобразования дискретной информации. В общем случае такое устройство может находиться в различных состояниях, переходя из одного состояния в другое под действием определённых внешних воздействий и, при этом, также воздействуя на внешнюю среду. Математической моделью устройства преобразования информации является трёхосновная алгебра Л = (Х1,3,Х2,*, о), которая называется автоматом и состоит из трёх базисных множеств Х2 и двух бинарных операций * : Хх х Б ^ и о : Хх х Б ^ Х2. Мпожество Хх называется множеством состояний автомата, множество Б — множеством входных сигналов автомата, множество Х2 — множеством выходных сигналов автомата. Бинарная операция * называется функцией переходов автомата, которая определяется для пары переменных х € Х17 в € Б значениями х * в в множестве состояний Х\ и показывает переход автомата из состояния х в состояние Х\ = х * в под воздействием входного сигнала в. В свою очередь, операция о называется функцией выходов автомата, которая определяется для пары переменных х € в € Б значениями х о в в множестве выходных сигналов Х2 и показывает выходной сигнал у = х о в автомата в состоянии х иод воздействием входного сигнала в.

Особое внимание в алгебраической теории автоматов [1] уделяется так называемым полугрупповым автоматам Л = (Хх, Б, Х2,*, о), у которых на множестве входных сигналов Б задана ассоциативная бинарная операция •, согласованная с функцией переходов и функцией выходов автомата по формулам

X* • в2) = (х * * в2, X о (й! • в2) = (х* вХ) о в2

для всех х € € Б. При этом, в зависимости от исследуемых за-

дач рассматриваются структурированные автоматы в категориях [2], то есть автоматы, множества состояний и выходных сигналов которых наделены дополнительными математическими структурами, а функции переходов и выходов являются морфизмами этих категорий. Такие автоматы изучались в работах Б.И. Плоткина [2]. Исследование конкретных задач привело к появлению топологических, вероятностных, упорядоченных, графовых и гиперграфических

автоматов. Им посвящены работы Л.А. Скорнякова, Б.И. Плоткина, В.А. Молчанова, С.А. Акимовой, Е.В. Хворостухиной и других. Обзор основных идей алгебраической теории автоматов и её связи с алгебраической теорией полугрупп приведён в монографии М.А. Арбиба [1] и в работе И.Б. Кожухова и A.B. Михалёва [3].

Настоящая работа продолжает исследование полугрупповых автоматов в категории графов — графовых автоматов, то есть автоматов, у которых множества состояний и выходных сигналов наделены структурами графов, сохраняющимися функциями переходов и выходов автомата. Особое внимание уделяется универсальным графовым автоматам. Универсальный графовый автомат — это универсально притягивающий объект в категории графовых автоматов, который представляет собой алгебраическую систему Atm(Gi, G2) = (Gi, S(G1, G2), G2,*, о) с графом состояний Gi = (X1,p1), графом выходных сигналов G2 = (Х2,р2)7 полугруппой входных сигналов S (Gi ,G2) = End Gi x Hom(G1, G2), функцией переходов * и функцией выходов о которые для элементов х £ Xi5 s = (р,ф) £ S(G1,G2) определяются по формулам х * s = f(x) и х о s = ф(х). Помимо описанных выше автоматов в работах по комбинаторной теории полугрупп М.А. Арбиба [1], Ж. Лаллема-на [4], Р. Лидла [5] и других авторов рассматриваются автоматы без выходов, которые называются полуавтоматами. Среди графовых полуавтоматов особо выделяются универсальные графовые полуавтоматы, представляющие собой алгебраическую систему Atm(G) = (G, End G,*) с графом состояний G = (X, р), полугруппой входных сигналов End G и функцией переходов *, которая для состояния х £ X и входного сигнала if £ End G определяется по формуле X * if = if(x).

Полугруппы входных сигналов универсальных графовых автоматов могут рассматриваться как их производные алгебраические системы, которые взаимосвязаны со свойствами алгебраической структуры автоматов. Таким образом, изучение универсальных графовых автоматов имеет непосредственное отношение к задаче исследования математических объектов с помощью некоторых производных алгебр отображений, которые специальным образом связаны с исходными математическими объектами. Такого рода задачи соотносятся с известной проблемой, обозначенной С. Уламом [6], которая заключается в исследовании определяемости математических объектов с помощью алгебр их эндоморфизмов и автоморфизмов.

В настоящей работе рассматривается типичный спектр вопросов, возникающих при исследовании математических объектов с помощью их производных алгебраических систем:

— насколько хорошо производная алгебра отображений определяет исходный математический объект?

— какими абстрактными свойствами характеризуется производная алгебра отображений?

— как взаимосвязаны логико-алгебраические свойства исходного объекта и его производной алгебры отображений?

Такие вопросы для групп автоморфизмов алгебраических систем, полугрупп эндоморфизмов графов, колец эндоморфизмов линейных пространств, модулей и других производных алгебраических систем исследовались в работах Б.И. Плоткина [7], А.Г. Пинуса [8], Ю.М. Важенина [9], Л.М. Глускина [10],

A.B. Михалёва [11], И.Б. Кожухова [12] и других. В этом направлении особое внимание уделялось исследованию групп автоморфизмов и полугрупп эндоморфизмов графов. В.Г. Визингом [13] сформулирована следующая задача: найти все графы, группа автоморфизмов которых совпадает с данной группой подстановок. Эта проблема является частным случаем проблемы конкретной характеризации производных алгебр отображений [14], заключающейся в поиске условий, при которых алгебра отображений будет равна производной алгебре отображений некоторого изучаемого математического объекта. Важные результаты в этом направлении получены Б. Ионсоном [14], Д.А. Бредихиным [15],

B.А. Молчановым [16].

В данной работе соответствующие исследования проводятся для универсальных графовых автоматов над широким классом квазибесконтурных рефлексивных графов. Отметим, что граф называется квазибесконтурным, если никакая его собственная дуга (то есть дуга, не имеющая встречной) не содержится ни в каком контуре графа. В этом направлении первоначально решается задача определяемое™ универсальных графовых автоматов своими полугруппами входных сигналов, которая формулируется следующим образом: при каких условиях полугруппы, входных сигналов S(G1,G2) и S(G^GQ) двух универсальных графовых автоматов Atm(Gi,G2) и Atm(G'1,G'2) будут изоморфны? На следующем этапе рассматривается задача конкретной характеризации универсальных графовых автоматов: при каких условиях автомат А с множеством состояний X1l полугруппой входных сигналов S и

множеством выходных сигналов Х2 является универсальным графовым автоматом, то есть на множестве состояний Х\ и множестве выходных сигналов Х2 можно задать такие бинарные отношения р\ и р2, что для графов С\ = (Х\,р\), С2 = (Х2, р2) выполняется равенство Л = АЬт(С1,С2)? Для решения данной задачи используется разработанная В.А. Молчановым техника канонических отношений полугрупп преобразований [16], которые определяются в исходных полугруппах формулами языка узкого исчисления предикатов. Такой подход позволяет последовательно и эффективно изучать логико-алгебраические свойства универсальных графовых автоматов и их взаимосвязь со своими полугруппами входных сигналов. В частности, проведено исследование строения изоморфизмов и групп автоморфизмов таких автоматов. Аналогично для универсальных графовых полуавтоматов решается задача конкретной характеризации. На её основе получено решение проблемы абстрактной характеризации универсальных графовых полуавтоматов и доказана относительно элементарная определимость [17] класса универсальных графовых полуавтоматов над квазибесконтурными рефлексивными графами в классе

В свете вышеизложенных теоретических вопросов рассматривается проблема линейного упорядочивания автоматов, заключающаяся в построении на множествах состояний и выходных сигналов линейных порядков, стабильных относительно действия входных и выходных сигналов автомата. Актуальность этой задачи обосновывается тем, что, с одной стороны, линейно упорядоченные автоматы (называемые также монотонными автоматами) играют важную роль в компьютерной науке и комбинаторной теории полугрупп [18; 19] и, с другой стороны, как следует из работы М. Шикулы [20], задача распознавания таких автоматов является ХР-полнои и, значит, не имеет эффективных алгоритмов решения. В настоящей работе для решения задачи линейного упорядочивания автоматов рассматривается алгоритм перебора с возвратами и отсечениями, а также эвристические алгоритмы: метод имитации отжига и алгоритм пчелиной колонии.

Цели и задачи исследования. Целью данной диссертации является разработка алгебраических методов исследования универсальных графовых

автоматов. Для достижения поставленной цели необходимо было решить следующие задачи:

1. Исследовать определяемость универсальных графовых автоматов и полуавтоматов над квазибесконтурными рефлексивными графами своими полугруппами входных сигналов.

2. Решить задачу конкретной характеризации универсальных графовых автоматов и полуавтоматов над квазибесконтурными рефлексивными графами.

3. Решить задачу абстрактной характеризации универсальных графовых полуавтоматов над квазибесконтурными рефлексивными графами.

4. Доказать относительно элементарную определимость класса универсальных графовых полуавтоматов над квазибесконтурными рефлексивными графами в классе полугрупп.

5. Исследовать вопрос о возможности элементарной аксиоматизации классов универсальных графовых автоматов и полуавтоматов над некоторыми важными классами рефлексивных графов.

6. Исследовать вопрос линейного упорядочивания автоматов и разработать практические методы линейного упорядочивания автоматов.

Теоретическая и практическая значимость. Работа носит в основном теоретический характер. Полученные результаты могут быть использованы для дальнейших исследований в алгебраической теории автоматов, теории графов, теории полугрупп и универсальной алгебре. Разработанные алгоритмы и программы для ЭВМ могут найти применение при решении задач комбинаторной теории полугрупп и задач анализа больших данных.

Методология и методы исследования. В работе использовались классические методы алгебраической теории автоматов, универсальной алгебры, теории моделей, математической логики, теории полугрупп и теории графов.

Основные положения, выносимые на защиту. Основные результаты диссертации состоят в следующем:

1. Исследована определяемость универсальных графовых автоматов над квазибесконтурными рефлексивными графами их полугруппами входных сигналов.

2. Решена задача конкретной характеризации универсальных графовых автоматов над квазибесконтурными рефлексивными графами.

3. Описано строение изоморфизмов и групп автоморфизмов универсальных графовых автоматов над квазибесконтурными рефлексивными графами.

4. Решена задача конкретной характеризации универсальных графовых полуавтоматов над квазибесконтурными рефлексивными графами.

5. Решена задача абстрактной характеризации универсальных графовых полуавтоматов над квазибесконтурными рефлексивными графами.

6. Доказана относительно элементарная определимость класса универсальных графовых полуавтоматов над квазибесконтурными рефлексивными графами в классе полугрупп.

7. Изучена взаимосвязь логико-алгебраических свойств универсальных графовых полуавтоматов над квазибесконтурными рефлексивными графами и полугрупп их входных сигналов.

8. Доказана невозможность элементарной аксиоматизации универсальных графовых автоматов и полуавтоматов над некоторыми важными классами рефлексивных графов.

9. Разработаны и программно реализованы алгоритмы линейного упорядочивания автоматов: алгоритм перебора с возвратами и отсечениями, алгоритм имитации отжига и алгоритм пчелиной колонии.

Научная новизна. Все перечисленные выше результаты являются новыми.

Достоверность основных результатов проведённых исследований подтверждается строгостью математических утверждений и их доказательств, а также их публикацией в открытой печати в рецензируемых изданиях и апробацией результатов диссертации на научных конференциях и семинарах.

Апробация работы. Основные результаты работы докладывались на следующих международных и всероссийских научных конференциях:

1. Международная конференция «Мальцевские чтения» (Новосибирск, 2020, 2022, 2023);

2. Международная летняя школ а-конференция «Пограничные вопросы теории моделей и универсальной алгебры» (Новосибирск, 2023, 2024);

3. Международная конференция по алгебре, анализу и геометрии (Казань, 2021);

4. Международная конференция «Алгебра и математическая логика: теория и приложения» (Казань, 2024);

5. Международная молодёжная школа-конференция «Современные проблемы математики и её приложений» (Екатеринбург, 2024);

6. Международная алгебраическая конференция, посвящённая 90-летию со дня рождения А.И. Старостина (Екатеринбург, 2021);

7. Международный научный семинар «Дискретная математика и её приложения» имени академика О.Б. Лупанова (Москва, 2022);

8. Международная научная конференция студентов, аспирантов и молодых учёных «Ломоносов» (Москва, 2020, 2021, 2024);

9. Международная научная конференция «Компьютерные науки и информационные технологии» (Саратов, 2018, 2021);

10. Научная конференция механико-математического факультета СГУ им. Н.Г. Чернышевского «Актуальные проблемы математики и механики» (Саратов, 2018-2019, 2021-2024);

11. Международная научно-практическая конференция «Presenting Academic Achievements to the World» (Саратов, 2021);

12. Всероссийский съезд учителей и преподавателей математики в МГУ им. Ломоносова (Москва, 2023);

13. Семинар «Workshop on Computer Modelling and Data Analysis in Decision Making» в рамках Международной научно-практической конференции «Математическое и компьютерное моделирование в экономике, страховании и управлении рисками» (Саратов, 2023);

14. Всероссийская (с международным участием) научно-практическая конференция «Информационные технологии в образовании» (Саратов, 2023).

Личный вклад. Постановки задач и методов исследования принадлежат научному руководителю. Основные результаты работы получены автором самостоятельно и опубликованы в работах |47 511. В работах [47; 50], выполненных в нераздельном соавторстве с В.А. Молчановым, идея доказательств предложена научным руководителем, а реализация выполнена соискателем. В работе [52], выполненной в соавторстве с научным руководителем, идея алгоритма предложена научным руководителем, диссертанту принадлежит программная реализация. В тезисах докладов [54] анонсированы результаты статьи [47], в [56; 57; 61] — результаты статьи [48], в [58; 69] — результат статьи [49], в [60] — результаты статьи [50], в [64] — результаты статьи [51].

и

Объём и структура работы. Диссертация состоит из введения, 4 глав и заключения.

Полный объём диссертации составляет 130 страниц, включая 8 рисунков, 1 таблицу, 5 алгоритмов и 1 приложение. Список литературы содержит 72 наименования.

Глава 1. Основные понятия и определения

В данной главе представлены основные понятия и определения, которые необходимы для последовательного изложения алгебраической теории графовых автоматов. В работе используется общепринятая терминология теории полугрупп из [21], теории графов из [22], теории автоматов из [2] и теории алгебраических систем из [23].

1.1 Элементы алгебры бинарных отношений и теории полугрупп

Пусть Х,У — некоторые непустые множества. Декартовым произведением множеств X и У называется множество X х У, состоящее из всевозможных пар (х, у)7 таких что первая компонента х принадлежит множеству X, вторая компонента у принадлежит множеству У, то есть

X х У = {(х,у) | ж е X Л у е У}.

Бинарным от,ношением, р между элементами множеств X и У называется всякое подмножество декартова произведения X х У. Очевидно, что для любого бинарного отношения р между элементами множеств X и У выполняется условие 0 С р С X х У. При этом 0 называется пустым бинарным отношением, а X х У универсальным бинарным отношением.

Пусть р С X х У — некоторое бинарное отношение, х е X. Срезом бинарного от,ношения р через элемент х называется множество

р(х) = {у е У 1 (х,у) е р}.

Пусть X 'С X. Тогда срезом, бинарного от,ношения, р через X' называется множество

р(х') = и р(х).

хеХ'

Областью определения бинарного отношения р называется множество

йотр = {х е X | (Зу е У)(х,у) е р},

а областью значений — множество

Imp = {у е Y | (Эх е X)(х,у) е р}.

Бинарное отношение р С X х Y называется

— всюду определённымесли dom р = X;

— однозначным, если для всех х е Х,у\ ,у2 е Y выполняется условие

(х, yi) е р Л (х, у2) е Р ^ У1 = У2.

Пусть р С X х Y7 а С Y х Z. Ком/позицией бинарных отношений р и а называется бинарное отношение р • а С X х Z7 где

р • а = {(x,z) е X х Z I (Эу е Y)((x,y) е Р Л (y,z) е а}.

Обратным для р называется бинарное отношение р-1 С Y х X, где

р-1 = {(у,х) е Y х X I (х,у) е р}.

Отношение Ах = {(х1 ,х2) е X х X | х1 = х2} называется тождественным на множестве X.

Выделим основные классы бинарных отношений на множестве X. Бинарное отношение р С X х X называется

— рефлексивным, если для любого элементам е X выполняется (х, х) е р, что равносильно условию Ах С р;

— симметричным, если для любых элементов х,у е X выполняется (х,у) е р ^ (у,х) е р, что равносильно условию р-1 С р;

— антисимметричным, если для любых элементов х,у е X выполняется

(х,у) е р Л (у,х) е Р ^ X = у,

что равносильно условию р П р-1 С Ах]

— транзитивным, если для любых элементов x,y,z е X выполняется

(х, у) е р Л (y,z) е р ^ (х, z) е p,

что равносильно условию р • р С р. Бинарное отношение р С X х X называется

— эквивалентностью, если оно рефлексивно, симметрично и транзитив-но;

— порядком, если оно рефлексивно, антисимметрично и транзитивно;

— квазипорядком, если оно рефлексивно и транзитивно.

Множество X с заданным на нём отношением порядкам называется упорядоченным, множеством (Х,ш). Порядок ш на множестве X называется линейным, если для любых двух элементов х,у е X выполняется следующее условие:

(х, у) е и V (у, х) е и.

В этом случае упорядоченное множество (Х,ш) называется линейно упорядоченным.

Бинарное отношение / С X х У называется отображением множества X в множество У, если оно всюду определённое и однозначное. Символически отображения обозначаются / : X ^ У, при этом для (х, у) е / говорят, что элемент х е X отображается в элемент у е У и пишут у = /(х). Множество всех отображений X в У обозначается Р(Х,У). Отображение множества X в себя называется преобразованием, множества X. Множество всех преобразований множества X обозначается Р(X). Отображение сх : X ^ {х} называется постоянным отображением множества X в элемент х.

Отображение / : X ^ У называется

— инзект,ивны,м,, если для любых х1,х2 е X выполняется условие

/(хг) = /(х2) х1 = х2;

— сюрзективным, если 1т / = У;

— биективны,месли оно инъективное и сюръективное.

Суперпозицией отображений / : X ^ У,д : У ^ % называется отображение / • д : X ^ которое элемент х е X отображает в элемент ^ = д(/(х)).

Для биекции / : X ^ У каждый элемент у е У однозначно определяется как у = /(х). В связи с этим, можно определить отображение /-1 : У ^ X по формуле /-1(у) = х, которое называется отображением, обратным к /. Ясно, что отображение /-1 также является биекцией, и, помимо этого, выполняется равенство (/-1)-1 = ^ Биективное отображение множества X в себя называется подстановкой на X. Множество всех подстановок на множестве X обозначается Бх-

Полугруппой называется алгебра Б = (Б, •) с одной ассоциативной бинарной операцией •, то есть выполняется тождество ассоциативности:

х • (У • г) = (х • у) • х.

Пусть Б = (Б, •) — некоторая полугруппа. Элемент в € Б называется:

— идемпотентом, если й • й = й;

— левой единицейесли для любых х € Б выполняется в • х = х;

— правой единицейесли для любых х € Б выполняется х • в = х;

— единицей (двусторонней), если он является и левой, и правой единицей;

— левым нулём,., если для любых х € £ выполняется в • х = в;

— правым нулём,., если для любых х € £ выполняется х • в = в;

— нулём (двусторонним), если он является и левым, и правым нулём.

Пусть Б = (51, •) — некоторая полугруппа, Т С Т = 0. Множество Т

называется подполугруппой, полугруппы Б, если оно замкнуто относительно операции • полугруппы, то есть для всех € Т выполняется в • £ € Т.

Пусть Б = (Б, •), Т = (Т, о) — полугруппы. Отображепие р : Б ^ Т называется гомоморфизмом полугруппы Б в полугруппу Т, если оно согласовано с операциями полугрупп ^Тв том смысле, что

(У в, г € Б) (р(в • г) = (р(в) о

Биективный гомоморфизм р : Б ^ Т называется полугруппы Б

па полугруппу Т, а сами полугруппы называют изоморфными, что символически записывается как Б = Т.

Рассмотрим совокупность ^(X) всех преобразований множества X. Поскольку множество Г(X) замкнуто относительно умножения и умножение в Г(X) ассоциативно, то (Г(X), •) является полугруппой, которая называется симметрической полугруппой, преобразований множества X.

1.2 Элементы теории графов

Ориентированным графом (далее просто графом) называется пара С = (X, р)7 где X — непустое множество, р С X х X — бинарное отношение на нём. При этом, множество X называется множеством вершин графа С, а его элементы — вершинами; отношение р называется отношением смежности, а его элементы — дугами графа.

Пусть С = (X, р) — некоторый граф. Для дуги (х,у) € р вершина х называется её началом, вершина у её концом, и символически дуга обозначается

х ^ у. Если х = у, то дуга (х, х) Е р называется петлёй. Если (х, у) Е р или (у, х) Е р, то говорят, что вершина х смежна с вершиной у, а сама дуга инцидентна вершинам х и у. Дуга (у, х) Е р называется встречной для дуги (х, у) Е р. Дуга, не имеющая встречной, называется собственной.

Маршрутом в графе G = (X, р) называется последовательность дуг (х1,х2), (х2,х3), ..., (xk-i,Xk), где (xi-\,Xi) Е р для всех г = 2,к. При этом, вершина ^ называется иа^алсш маршрута, a Xk — его концом. Маршрут, в котором начало и конец совпадают, называется циклом. Маршрут, в котором каждая дуга встречается только один раз, называется путём. Путь, каждая вершина которого принадлежит не более чем двум дугам, называется простым. Простой циклический путь в графе называется контуром. Граф, не содержащий контуров длины больше 1, называется бесконтурным. Граф, у которого никакая его собственная дуга не содержится ни в каком контуре, называется квазибесконтурным. В частности, бесконтурные графы, графы квазипорядка и симметричные графы являются квазибесконтурными графами. Квазибескон-турный граф называется тривиальным, если у него нет собственных дуг, и нетривиальным в противном случае. На рисунке 1.1 приведены примеры ква-зибесконтурных графов.

Граф G = (X, р-1) называется двойственным для графа G = (Х,р).

Классификация бинарных отношений естественным образом распространяется па графы. В частности, граф G = (X, р) называется

— тождественным, если его отношение смежности р есть тождественное бинарное отношение, то есть р = Ах]

— полным, если его отношение смежности р есть универсальное бинарное отношение, то есть р = X х X.

Гомоморфизмом графа G = (X, р) в граф Н = (Y, а) называется отображение f : X ^ У, такое что для любых вершин х1,х2 Е X выполняется условие

(xi,x2) Е р (f(xi),f(x2)) Е а.

Множество всех гомоморфизмов графа G в граф Н обозначавтся Hom(G, Н). Гомоморфизм графа в себя называется эндоморфизмом. Множество всех эндоморфизмов графа G обозначав тся End G. Множест во End G с композицией образует полугруппу, которая называется полугруппой эндоморфизмов графа G.

Гассмотрнм множество S = End G х Hom(G, Н) для графов G = (X, р) и Н = (Y, а). Определим умножение • пар отображений (f1,'ф1), (^2,ф2) из мно-

В г

Рисунок 1.1 Примеры квазибесконтурных графов: А бесконтурный граф; Б нетривиальный квазибесконтурный; В граф квазипорядка; Г симметричный граф.

жества Б по формуле:

(Р1,фг) • (<Р2,ф2) = (<Р1ф2, <Р1ф2).

Полученное множество Б с операцией умножения является полугруппой [2].

Графы С = (X, р) и Н = (У, а) называются изоморфными, если существует биекция р : X ^ У, которая сохраняет отношение смежности, то есть для любых двух вершин х1,х2 € X выполняется условие

(Х1,Х2) € р ^^ (р(хх), р(х2)) € а.

Изоморфизм графа на себя называется автоморфизмом. Множество всех автоморфизмов графа С с композицией образует группу А^ С.

Антиизоморфизмом графа С на граф Н называется изоморфизм графа С на двойственный графу Н граф Н. Антиавтоморфизмом графа С называется изоморфизм графа С па двойственный граф С.

Полумаршрутом в графе С = (X, р) называется последовательность дуг (х1,х2), (х2, х3), ..., (хк-1,Хк), в которой (х!—1,х^ € р ил и (х,ь,х—1) € р для всех г = 2, к. Полумаршрут, в котором каждая дуга встречается только один раз, называется полупутём. Граф называется слабо связным, если любые его две вершины соединены полупутём. Классы такого отношения связности называются его компонентами связности.

1.3 Элементы теории графовых автоматов

Под автоматом будем понимать трёхосновную алгебраическую систему Л = (X, Б, У, к, о) с тремя основными множествами Х,Б,У и двумя бинарными операциями к : X х Б ^ Хи о : X х Б ^ У. Множество X называется множеством состояний автомата, Б — множеством входных сигналов, У —

к

ей переходов автомата, которая определяется для элементов х € X, з € Б значениями х к в в множестве состояний X и показывает переход автомата из состояния х в состояние х1 = х к в иод воздействием входного сигнала в. Бинарная операция о называется функцией выходов автомата, которая определяется для элементов х € X, в € Б значениями х о и множестве выходных сигналов У и показывает выходной сигнал у = х о в автомата в состоянии х иод воздействием входного сигнала в.

Список литературы диссертационного исследования кандидат наук Фарахутдинов Ренат Абуханович, 2025 год

Список литературы

1. Алгебраическая теория автоматов, языков и полугрупп / под ред. М. А. Ар-биба. — М. : Статистика, 1975. — 335 с.

2. Плоткищ Б. И. Элементы алгебраической теории автоматов / Б. И. Плот-кип, Л. Я. Гринглаз, А. А. Гварамия. — М. : Высш. шк., 1994. — 191 с.

3. Кожухов, И. Б. Об алгебраической теории автоматов / И. Б. Кожухов, А. В. Михалёв // Интеллектуальные системы. Теория и приложения. — 2021. - Т. 25, № 4. - С. 45—51.

4. Лаллемащ Ж. Полугруппы и комбинаторные приложения / Ж. Лалле-мин. — М. : Мир, 1985. — 440 с.

5. Лид л, Р. Прикладная абстрактная алгебра: учеб. пособие / Р. Лидл, Г. Пильц. — Екатеринбург : Изд-во Урал. Ун-та, 1996. — 744 с. — 1)01: 10.1007/978-1-4757-2941-2.

6. Улам. С. Нерешенные математические задачи / С. Улам. — М. : Наука, 1964. - 168 с. - Б01: 10.1126/8аепсе.132.3428.665.

7. Плоткищ Б. И. Группы автоморфизмов алгебраических систем / Б. И. Плоткин. — М. : Наука, 1966. — 604 с.

8. Пину с, А. Г. Об элементарной эквивалентности производных структур свободных полугрупп, у пиров и групп / А. Г. Пинус / / Алгебра и логика. — 2004. - Т. 43, № 6. - С. 730 748.

9. Важенин, Ю. М. Элементарные свойства полугрупп преобразований упорядоченных множеств / Ю. М. Важенин // Алгебра и логика. — 1970. — Т. 9, № 3. - С. 281—301.

10. Глускищ Л. М. Полугруппы изотопных преобразований / Л. М. Глускин // УМН. - 1961. - Т. 16, № 5. - С. 157—162.

11. Михалёв, А. В. Кольца эндоморфизмов модулей и структуры подмодулей / А. В. Михалёв // Итоги науки и техн. Сер. Алгебра. Топол. Геом. — 1974. — Т. 12. - С. 51—76.

12. Кожухов, И. Б. Полигоны над полугруппами / И. Б. Кожухов, А. В. Михалёв // Фундаментальная и прикладная математика. — 2020. — Т. 23, Л" 3. - С. 141—199.

13. Визит, В. Г. Некоторые нерешённые задачи в теории графов / В. Г. Ви-зинг // УМН. - 1968. - Т. 23, № 6. - С. 117 134.

14. Jonsson, В. Topics in Universal Algebra / B. Jonsson. — Berlin : Springer Berlin, Heidelberg, 1972. — 224 p. — DOI: 10.1007/BFb0058648.

15. Бредихин, Д. А. Инверсные полугруппы локальных автоморфизмов универсальных алгебр / Д. А. Бредихин // Сибирск. матем. журнал. — 1975. — Т. 17, № 3. - С. 490 507.

16. Molchanov, V. A. Semigroups of mappings on graphs / V. A. Molchanov // Semigroup Forum. — 1983. — Vol. 27. — P. 155—199. — DOI: 10.1007/ BF02572738.

17. Ершов, Ю. Л. Проблемы разрешимости и конструктивные модели / Ю. Л. Ершов. — М. : Наука. Физматлит, 1980. — 416 с.

18. Eppstein, D. Reset sequences for monotonic automata / D. Eppstein // SIAM Journal on Computing. — 1990. — Vol. 19, no. 3. — P. 500^510. — DOI: 10.1137/0219033.

19. Ananichev, D. S. Synchronizing monotonic automata / D. S. Ananichev, M. V. Volkov // Theoretical Computer Science. — 2004. — Vol. 327, no. 3. — p 225—239. — DOI: 10.1016/j.tcs.2004.03.068.

20. Szykuta, M. Checking whether an automaton is monotonic is NP-com-plete / M. Szykula // Implementation and application of automata / ed. by F. Drewes. — Cham : Springer, 2015. — P. 279—291. — DOI: 10.1007/978-3-319-22360-5_23.

21. Клиффорд, А. Алгебраическая теория полугрупп, т. 1 / А. Клиффорд, Г. Престон. - М. : Мир, 1972. - 285 с.

22. Харарщ Ф. Теория графов / Ф. Харари. — М. : Мир, 1973. — 300 с.

23. Мальцев, А. И. Алгебраические системы / А. И. Мальцев. — М. : Наука. Физматлит, 1970. — 392 с.

24. Важенин, Ю. М. Об элементарной определяемости и элементарной характеризуемое™ классов рефлексивных графов / Ю. М. Важенин // Изв. вузов. Матем. - 1972. - № 7. - С. 3-11.

25. Акимова, С. А. Об определяемости упорядоченных автоматов полугруппами их входных сигналов / С. А. Акимова // Известия ВГПУ. — 2005. — Л" 4. - С. 24^27.

26. Кейслер, Г. Теория моделей / Г. Кейслер, Ч. Ч. Чэн. — М. : Мир, 1977. — 616 с.

27. Куратовский, К. Теория множеств / К. Куратовский, А. Мостовский. — М. : Мир, 1970. - 416 с.

28. Курош, А. Г. Теория групп / А. Г. Курош. — М. : Наука, 1967. — 648 с.

29. Глускин, Л. М. Идеалы полугрупп / Л. М. Глускин // Матем. сб. — 1961. — Т. 55, № 4. - С. 421 448.

30. Л я,пин, Е. С. Абстрактная характеристика некоторых полугрупп преобразований / Е. С. Ляпин // Учёные записки ЛГПИ. — 1955. — Т. 103. — С. 5^29.

31. Мальцев, А. И. Симметрические группоиды / А. И. Мальцев // Матем. сб_ _ 1952. - Т. 31. - С. 136—151.

32. Важенин, Ю. М. Элементарная классификация и разрешимость теорий производных структур / Ю. М. Важенин, А. Г. Пинус // УМН. — 2005. — Т. 60, № 3. - С. 3 40.

33. Робинсон, А. Введение в теорию моделей и метаматематику алгебры / А. Робинсон. — М. : Наука. Физматлит, 1967. — 376 с. — DOI: 10.2307/ 2269789.

34. Акимова, С. А. Относительно элементарная определимость класса универсальных упорядоченных полуавтоматов в классе полугрупп / С. А. Акимова // Математика. Механика. — 2007. — № 9. — С. 3 5.

35. McNaughton, R. Counter-Free automata (M.I.Т. research monograph no. 65) / R. McNaughton, S. A. Papert. — Cambridge : The MIT Press, 1971.

36. Brzozowski, J. Syntactic complexities of some classes of star-free languages / J. Brzozowski, B. Li // Descriptional complexity of formal systems / ed. by M. Kutrib, N. Moreira, R. Reis. — Berlin, Heidelberg : Springer, 2012. — P. 117—129. — DOI: 10.1007 978-3-642-31623-4J).

37. Габович, E. Я. Линейно упорядоченные полугруппы и их приложения / Е. Я. Габович // УМН. - 1976. - Т. 31, № 1. - С. 137 201.

38. Volkov, М. V. Synchronizing automata preserving a chain of partial orders / M. V. Volkov // Theoretical Computer Science. — 2009. — Vol. 410, no. 37. — p 35i3—3519. — DOI: 10.1016/j.tcs.2009.03.021.

39. Ryzhikov, A. Subset synchronization in monotonic automata / A. Ryzhikov, A. Shemyakov // Fundamenta Informaticae. — 2017. — Vol. 162, no. 2/3. — P. 205—221. — DOI: 10.3233 FI-2018-1721.

40. Богомолов, А. М. Алгебраические основы теории дискретных систем / А. М. Богомолов, В. Н. Салий. — М. : Наука, 1997. — 368 с.

41. Binder, К. Monte Carlo simulation in statistical physics / K. Binder. — Springer, 2019. — 258 p. — DOI: 10.1007/978-3-030-10758-1.

42. Equation of State Calculations by Fast Computer Machines / N. Metropolis [et al.] //J. Chem. Phys. — 1953. — Vol. 21, no. 1087. — P. 1087 1092. — DOI: 10.1063/1.1699114.

43. Kirkpatrick, S. Optimization by Simulated Annealing / S. Kirkpatrick, J. C. D. Gelatt, M. P. Vecchi // Science. — 1983. — Vol. 220, no. 4598. — P 671^680_ — DOI: 10.1126/science.220.4598.671.

44. Лопатин, А. С. Метод отжига / А. С. Лопатин // Стохастическая оптимизация в информатике. — 2005. Л'° 1. С. 133 149.

45. Karaboga, D. An Idea Based on Honey Bee Swarm for Numerical Optimization. Technical Report / D. Karaboga // Technical Report-TR06. — 2005. — P. 1—10.

46. Айзенштат, А. Я. Определяющие соотношения полугруппы эндомофриз-мов конечного линейно упорядоченного множества / А. Я. Айзенштат // Сиб. матем. журн. — 1962. — Т. 3, № 2. — С. 161 169.

Публикации автора по теме диссертации

В изданиях из списка ВАК РФ

47. Farakhutdinov, R. A. On Definability of Universal Graphic Automata by Their Input Symbol Semigroups / R. A. Farakhutdinov, V. A. Molchanov // Известия Саратовского университета. Новая серия. Серия: Математика. Механика. Информатика. — 2020. — Т. 20, № 1. — С. 42 50. — DOI: 10. 18500/1816-9791-2020-20-1-42-50.

48. Фарахутдинов, Р. А. О конкретной характеризации универсальных графовых полуавтоматов / Р. А. Фарахутдинов // Известия Саратовского университета. Новая серия. Серия: Математика. Механика. Информатика. - 2022. - Т. 22, № 4. - С. 458-467. - DOI: 10.18500 1816-9791-202222-4-458-467.

49. Фарахутдинов, Р. А. Относительно элементарная определимость класса универсальных графовых полуавтоматов в классе полугрупп / Р. А. Фарахутдинов // Известия высших учебных заведений. Математика. — 2022. - № 1. - С. 74-84. - DOI: 10.26907/0021-3446-2022-1-74-84. Переводная версия: Farakhutdinov, R. A. Relatively Elementary Definability of the Class of Universal Graphic Semiautomata in the Class of Semigroups / R. A. Farakhutdinov // Russian Mathematics. — 2022. — Vol. 66, no. 1. — P. 62-70. - DOI: 10.3103/S1066369X22010029.

50. Farakhutdinov, R. A. On Concrete Characterization of Universal Graphic Automata / R. A. Farakhutdinov, V. A. Molchanov // Lobachevskii Journal of Mathematics. — 2022. — Vol. 43, no. 3. — P. 664 671. — DOI: 10.1134/ S1995080222060233.

51. Фарахутдинов, P. А. О проблеме абстрактной характеризации универсальных графовых автоматов / Р. А. Фарахутдинов // Чебышевский сборник. - 2024. - Т. 25, 1 (92). - С. 116-126. - DOI: 10.22405 22268383-2024-25-1-116-126.

Зарегистрированные программы для ЭВМ

52. Свидетельство о гос. регистрации программы для ЭВМ. Программа линейного упорядочивания множества состояний конечного автомата / В. А. Молчанов, Р. А. Фарахутдинов ; Ф. государственное бюджетное образовательное учреждение высшего образования «Саратовский национальный исследовательский государственный университет имени Н.Г. Чернышевского» (RU). — № 2018664580 ; заявл. 20.12.2018 ; опубл. 09.01.2019, 2019610057 (Рос. Федерация).

53. Свидетельство о гос. регистрации программы для ЭВМ. Программа линейного упорядочивания конечных автоматов эвристическими методами / Р. А. Фарахутдинов ; Ф. государственное бюджетное образовательное учреждение высшего образования «Саратовский национальный исследовательский государственный университет имени Н.Г. Чернышевского» (RU). — № 2024619132 ; заявл. 26.04.2024 ; опубл. 26.04.2024, 2024619828 (Рос. Федерация).

В сборниках трудов конференций

54. Фарахутдинов, Р. А. Об универсальных графических автоматах / Р. А. Фа-рахутдинов, В. А. Молчанов // Компьютерные науки и информационные технологии. Материалы Международной научной конференции. — 2018. — С. 276^278.

55. Фарахутдинов, Р. А. Линейное упорядочивание конечных автоматов / Р. А. Фарахутдинов, В. А. Молчанов // Информационные технологии и математическое моделирование (ИТММ-2019): Материалы XVIII Международной конференции имени А.Ф. Терпугова. - 2019. - С. 31^36.

56. Farakhutdinov, R. A. On Concrete Characterization Problem of Universal Graphic Automata / R. A. Farakhutdinov // Материалы Международного молодежного научного форума «ЛОМОНОСОВ-2020». — 2020.

57. Farakhutdinov, R. A. On Concrete Characterization Problem of Universal Graphic Automata / R. A. Farakhutdinov // Мальцевские чтения: Тезисы докладов Международной конференции. — 2020. — С. 245.

58. Farakhutdinov, R. A. Relatively Elementary Definability of the Class of Universal Graphic Automata in the class of Semigroups / R. A. Farakhutdinov // Материалы Международного молодежного научного форума «ЛОМОНОСОВ-2021». - 2021.

59. Фарахутдинов, Р. А. Абстрактная характеризация универсальных графовых полуавтоматов / Р. А. Фарахутдинов // Материалы Международной алгебраической конференции, посвягцённой 90-летию со дня рождения А.И. Старостина: Тезисы докладов. — 2021. — С. 89—91.

60. Фарахутдинов, Р. А. Конкретная характеризация универсальных графовых автоматов / Р. А. Фарахутдинов, В. А. Молчанов // Труды Математического центра имени И.И. Лобачевского. Материалы Международной конференции по алгебре, анализу и геометрии 2021. — 2021. — С. 101—102.

61. Фарахутдинов, Р. А. Конкретная характеризация универсальных графовых полуавтоматов / Р. А. Фарахутдинов // Компьютерные науки и информационные технологии. Материалы Международной научной конференции. — 2021. — С. 186—188.

62. Фарахутдинов, Р. А. Строение изоморфизмов и групп автоморфизмов универсальных графовых автоматов / Р. А. Фарахутдинов, В. А. Молчанов // Материалы XIV Международного семинара «Дискретная математика и её приложения» имени академика О.Б. Лупанова. — 2022. — С. 203^206.

63. Farakhutdinov, R. A. On Structure of Isomorphisms of Input Signal Semigroups of Universal Graphic Automata / R. A. Farakhutdinov, V. A. Molchanov // Тезисы докладов Международной конференции «Мальцевские чтения». — 2022. - С. 171.

64. Farakhutdinov, R. A. On Abstract Characterization of Universal Graphic Automata / R. A. Farakhutdinov, V. A. Molchanov // Тезисы докладов Международной конференции «Мальцевские чтения». — 2023. — С. 113.

65. Фарахутдинов, Р. А. Применение эвристических алгоритмов глобальной оптимизации для задач, не имеющих эффективных методов решения / Р. А. Фарахутдинов // Информационные технологии в образовании: сборник научных статей. Материалы XV Всероссийской (с международным участием) научно-практической конференции «Информационные технологии в образовании» (ИТО-Саратов-2023). — 2023. — С. 332—337.

66. Фарахутдинов, Р. А. Относительно элементарная определимость класса частичных графовых полуавтоматов в классе полугрупп / Р. А. Фарахутдинов, В. А. Молчанов // Материалы международной конференции «Алгебра и математическая логика: теория и приложения», посвященной 130-летию со дня рождения основателя кафедры алгебры Казанского университета члена-корреспондента АН СССР Николая Григорьевича Чеботарева и 80-летию со дня рождения заведующего кафедрой академика АН РТ Марата Мирзаевича Арсланова. — 2024. — С. 172.

В прочих изданиях

67. Фарахутдинов, Р. А. Линейное упорядочивание полуавтоматов / Р. А. Фарахутдинов, В. А. Молчанов // Математика. Механика. — 2019. — № 21. — С. 45-48.

68. Фарахутдинов, Р. А. Об аксиоматизации графовых полуавтоматов / Р. А. Фарахутдинов, В. А. Молчанов // Математика. Механика. — 2021. — Л" 23. - С. 41-43.

69. Farakhutdinov, R. A. Relatively Elementary Definability of the Class of Universal Graphic Semiautomata in the Class of Semigroups / R. A. Farakhutdinov // Представляем научные достижения миру. Естественные науки: материалы XII научной конференции молодых ученых «Presenting Academic Achievements to the World». — 2022. — № 11. — C. 33-39.

70. Фарахутдинов, Р. А. О строении изоморфизмов универсальных графовых автоматов / Р. А. Фарахутдинов, В. А. Молчанов // Математика. Механика. - 2022. - № 24. - С. 37-40.

71. Farakhutdinov, R. A. On the Problem of Axiomatization of Some Classes of Universal Graphic Semiautomata / R. A. Farakhutdinov, V. A. Molchanov // Algebra and model theory. — 2023. — No. 14. — P. 75—82.

72. Фарахутдинов, Р. А. Линейное упорядочивание полуавтоматов методом имитации отжига / Р. А. Фарахутдинов, В. А. Молчанов // Математика. Механика. - 2023. - № 25. - С. 69-73.

Список рисунков

1.1 Примеры квазибескоитуриых графов: А — бесконтурный граф; Б — нетривиальный квазибесконтурный; В — граф квазипорядка; Г — симметричный граф............................. 17

2.1 Схематическое изображение отображения / : Х\ ^ Х^......... 30

2.2 Контрпример определяемости универсальных графовых автоматов своими полугруппами входных сигналов в случае, когда каждая собственная дуга принадлежит некоторому контуру графа......36

2.3 Пример графа из класса Кге1....................... 52

2.4 Схематическое изображение отображения р : X ^ X для бесконечного подмножества У С Z.................... 54

2.5 Графы С и Н................................ 56

2.6 Равенство изоморфизмов да и дь антисимметричного графа С2

на граф С2) когда вершины а и Ь смежные................ 58

4.1 Диаграмма переходов/выходов автомата Л = (X, 3,У,*, о)......103

Список таблиц

1 Результаты тестирования алгоритмов линейного упорядочивания

конечных полуавтоматов.........................114

Список алгоритмов

4.1 Линейное упорядочивание конечных полуавтоматов алгоритмом перебора с возвратами и отсечениями................ 97

4.2 Линейное упорядочивание конечных автоматов алгоритмом перебора с возвратами и отсечениями................100

4.3 Линейное упорядочивание конечных полуавтоматов методом имитации отжига............................108

4.4 Вычисление целевой функции метода имитации отжига для линейного упорядочивания конечных полуавтоматов .......109

4.5 Линейное упорядочивание конечных полуавтоматов алгоритмом пчелиной колонии ...........................111

Приложение А

Свидетельства о государственной регистрации программ для ЭВМ