РИСЦОВ ІГОР КОСТЯНТИНОВИЧ ЗАСТОСУВАННЯ МЕТОДІВ АЛГЕБРАЇЧНОЇ ТЕОРІЇ АВТОМАТІВ К ПРОБЛЕМАМ АНАЛІЗУ ДИСКРЕТНИХ ДИНАМІЧНИХ СИСТЕМ : Рысцова ИГОРЬ КОНСТАНТИНОВИЧ ПРИМЕНЕНИЕ МЕТОДОВ алгебраической теории АВТОМАТОВ К ПРОБЛЕМАМ АНАЛИЗА ДИСКРЕТНЫХ ДИНАМИЧЕСКИХ СИСТЕМ RYSTSOV IHOR KOSTIANTYNOVYCH APPLICATION OF METHODS OF ALGEBRAIC THEORY OF AUTOMATIC MACHINES TO PROBLEMS OF ANALYSIS OF DISCRETE DYNAMIC SYSTEMS

Короткий опис

Міністерство освіти і науки України Національний технічний університет України «Київський політехнічний інститут імені Ігоря Сікорського» Міністерство освіти і науки України Київський національний університет імені Тараса Шевченко» Кваліфікаційна наукова праця на правах рукопису РИСЦОВ ІГОР КОСТЯНТИНОВИЧ УДК 519.713.2 ДИСЕРТАЦІЯ ЗАСТОСУВАННЯ МЕТОДІВ АЛГЕБРАЇЧНОЇ ТЕОРІЇ АВТОМАТІВ К ПРОБЛЕМАМ АНАЛІЗУ ДИСКРЕТНИХ ДИНАМІЧНИХ СИСТЕМ 01.05.01 теоретичні основи інформатики та кібернетики фізико-математичні науки Подається на здобуття ступеня доктора фізико-математичних наук Дисертація містить результати власних досліджень автора. При використанні ідей, результатів і текстів інших авторів надаються посилання на відповідні джерела. _____________ І.К. Рисцов Київ 2020

ЗМІСТ Вступ.................................................................................................................15 Розділ 1. Історія проблеми й основні результати.........................................19 1.1. Постановка проблеми ..........................................................................19 1.2. Прикладне значення проблеми Черни ...............................................20 1.3. Прямий метод .......................................................................................22 1.4. Обернений метод..................................................................................23 1.4.1. Циклічні автомати.........................................................................25 1.4.2. Орієнтовані автомати....................................................................27 1.4.3. Регулярні автомати........................................................................28 1.4.4. Ейлерові автомати.........................................................................29 1.4.5. Автомати з простими ідемпотентами .........................................30 1.5. Лінійні оцінки.......................................................................................30 1.5.1. Комутативні автомати...................................................................30 1.5.2. Монотонні автомати .....................................................................31 1.6. Субквадратичні оцінки ........................................................................32 1.6.1. Автомати з нулем ..........................................................................33 1.6.2. Аперіодичні автомати...................................................................33 1.6.3. Частково монотонні автомати......................................................34 1.7. Лінійні методи ......................................................................................35 1.7.1. Трикутні автомати.........................................................................36 1.7.2. Функції мортальності....................................................................36 1.7.3. Одно-кластерні автомати..............................................................39 1.7.4. Радикальна гіпотеза ......................................................................41 1.8. Висновки за першім розділом.............................................................43 11 Розділ 2. Скінченні автомати й моноїди....................................................... 45 2.1. Моноїди морфізмів .............................................................................. 45 2.2. Скінченні автомати.............................................................................. 47 2.3. Теорія досяжності та інваріантності .................................................. 49 2.3.1. Інваріантні підмножини ............................................................... 50 2.3.2. Сильно зв'язані компоненти......................................................... 52 2.3.3. Ядро автомата................................................................................ 56 2.3.4. Автомати з нулем.......................................................................... 57 2.3.5. Регулярне зображення моноїда ................................................... 58 2.4. Гомоморфізми і конгруенції автоматів ............................................. 59 2.4.1. Моноїд ендоморфізмів автомата ................................................. 60 2.4.2. Фактор-автомати........................................................................... 62 2.4.3. Інваріантні відношення автомата................................................ 64 2.5. Орбіталі автоматів ............................................................................... 65 2.5.1. Примітивні автомати .................................................................... 68 2.5.2. Орбітальні орграфи....................................................................... 71 2.6. Синхронізовані автомати .................................................................... 77 2.6.1. Регулярні ідеали ............................................................................ 81 2.7. Синхронізовані групи перестановок.................................................. 86 2.7.1. Примітивні групи.......................................................................... 86 2.7.2. Двічі однорідні групи ................................................................... 90 2.7.3. Розбиття і трансверсалі ................................................................ 91 2.7.4. Спрямовані групи.......................................................................... 93 2.8. Висновки по другому розділу............................................................. 95 Розділ 3. Лінійні автомати та зображення.................................................... 97 12 3.1. Теорія лінійних зображень..................................................................97 3.1.1. Інваріантні підпростори................................................................99 3.1.2. Незвідні зображення та алгебри ................................................102 3.1.3. Повнота незвідних лінійних алгебр ..........................................105 3.1.4. Незвідні лінійні моноїди.............................................................107 3.1.5. Цілком звідні зображення ..........................................................110 3.2. Зображення скінченних груп ............................................................112 3.2.1. Мономіальне зображення групи................................................113 3.2.2. Підстановочний характер...........................................................117 3.2.3. Незвідні групи підстановок........................................................120 3.3. Узагальнені лінійні автомати............................................................123 3.3.1. Досяжність станів в лінійних автоматах...................................125 3.3.2. Підавтомати лінійних автоматів................................................128 3.3.3. Незвідні лінійні автомати...........................................................131 3.4. Лінійні зображення скінченних автоматів ......................................133 3.4.1. Лінійне розширення скінченного автомата..............................136 3.4.2. Лінійна алгебра скінченного автомата......................................140 3.5. Висновки по третьому розділу..........................................................154 Розділ 4. Проблема Черни ............................................................................156 4.1. Лінійні класи автоматів .....................................................................156 4.1.1. Впорядковані автомати...............................................................157 4.1.2. Комутативні автомати.................................................................158 4.1.3. Трикутні автомати.......................................................................159 4.1.4. Многовид автоматів DSA...........................................................163 4.2. Субквадратичні класи автоматів ......................................................167 13 4.2.2. Аперіодичні автомати................................................................. 169 4.2.3. Слабо монотонні автомати......................................................... 171 4.2.4. Многовид автоматів EDSA ........................................................ 173 4.3. Супер-квадратичні класи автоматів................................................. 179 4.3.1. Циклічні автомати....................................................................... 180 4.3.2. Орієнтовані автомати ................................................................. 183 4.3.3. Прості одно-кластерні автомати................................................ 187 4.4. Квазіквадратичні класи автоматів.................................................... 197 4.4.1. Загальні одно-кластерні автомати............................................. 197 4.4.2. Регулярні автомати ..................................................................... 201 4.4.3. Імовірнісні розподіли на словах................................................ 208 4.4.4. Автомати з простими ідемпотентами ....................................... 211 4.4.5. Півпрості автомати ..................................................................... 220 4.5. Висновки за четвертим розділом ..................................................... 230 Розділ 5. Афінні автомати ............................................................................ 233 5.1. Досяжність станів в афінних автоматах .......................................... 235 5.2. Проблема мортальності..................................................................... 237 5.2.1. Двовимірні автомати над скінченним полем........................... 244 5.2.2. Лінійні автомати над двійковим полем .................................... 247 5.3. Афінні автомати і фрактали.............................................................. 251 5.3.1. Класичні фрактали...................................................................... 254 5.4. Афінні автомати і різницеві рівняння.............................................. 257 5.4.1. Модель Кейнса ............................................................................ 258 5.4.2. Модель Самуельсона-Хікса ....................................................... 259 5.4.3. Автомат Фробеніуса ................................................................... 260 14 5.5. Висновки по п'ятому розділу ............................................................261 Розділ 6. Дискретні динамічні системи.......................................................264 6.1. Транспортна задача ............................................................................265 6.1.1. Транзитна задача .........................................................................267 6.2. Управління запасами .........................................................................268 6.2.1. Узагальнена задача управління запасами.................................270 6.3. Хаотична динаміка.............................................................................271 6.3.1. Автономні динамічні системи ...................................................271 6.3.2. Детермінований динамічний хаос .............................................274 6.3.3. Універсальна постійна і періодичність.....................................277 6.3.4. Ознаки детермінованого хаосу ..................................................279 6.4. Застосування теорії автоматів...........................................................283 6.4.1. Булеві автомати ...........................................................................283 6.4.2. Регулярні вирази..........................................................................286 6.4.3. Автомати Харела .........................................................................287 Список літератури .........................................................................................292 Додаток А. Список публікацій за темою дисертації .................................300

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

У зв'язку з черговою кризою в програмуванні подібні реалізації отримали суворий осуд з боку адептів структурного програмування, виразником яких був Дейкстра [107]. З тих пір, принаймні, на теоретичному рівні питання про програмну реалізацію автоматів більше не підіймався. І ось через десятиліття Шалито повертається до цієї ідеї і, щоб не порушувати принципів структурного програмування, пропонує замінити оператор «goto» оператором «switch», який є в багатьох мовах програмування в тому числі і в мові «С». В результаті реалізація автомата виходить простою і зрозумілою. Відповідна технологія отримала назву «SWITCH-технології» [108]. Шалито запропонував весь процес програмування контролерів базувати на кінцевому автоматі і назвав це «автоматним програмуванням». У цьому випадку кінцевий автомат виступає не тільки як вихідна модель для складання програми, але і як формальна специфікація для тестування і верифікації всього проекту [106]. У висновку відзначимо, що теорія автоматів продовжує розвиватися і коло її впроваджень постійно розширюється, що підтверджує пророчі слова Дугласа Росса.