Дисертацію присвячено вивченню зображень вільних груп та напівгруп автоматними перетвореннями над скінченними алфавітами. Розвинуто техніку обчислень у вінцевих добутках за нескінченними послідовностями напівгруп перетворень. Доведено, що у сенсі Бера "більшість" скінченно породжених піднапівгруп напівгрупи автоматних перетворень над скінченним алфавітом є вільними. Побудовано континуальну серію прикладів вільних напівгруп автоматних підстановок. Знайдено зображення вільних неабелевих груп рангу 2 як скінченними, так і нескінченними автоматами над двоелементним алфавітом. Описано відношення Гріна в напівгрупі автоматних перетворень над скінченним алфавітом.

  Скачати повний текст

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

  Скачати повний текст

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

  Скачати повний текст

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

  Скачати повний текст

За результатами теоретичних і експериментальних досліджень запропоновано нові структури та формальні методи синтезу керувальних автоматів з "жорсткою" логікою (АЖЛ). Показано, що оптимізація апаратурних витрат у схемах формування змінних може бути одержана у разі використання методу кодування наборів фрагмента змінних. Запропоновано застосовувати метод кодування наборів фрагмента змінних у структурах керуючого автомату Мілі з кодуванням наборів мікрооперацій та кодуванням рядків прямої структурної таблиці, а також у структурах керуючого автомата Мура з кодуванням наборів мікрооперацій та з кодуванням класів псевдоеквівалентних станів. Розроблено нові структури та методи синтезу для структур автоматів Мілі та Мура з кодуванням наборів фрагмента змінних. Використання запропонованих методів дозволяє зменшити апаратурні витрати у схемах автомата Мілі до 20 % та у схемах автомата Мура до 10 % у порівнянні з відомими структурами. Одержано результати аналітичного оцінювання ефективності запропонованих структур АЖЛ у аспекті апаратурних витрат як функції від параметрів граф-схеми алгоритму. За результатами дослідження визначено область ефективного використання запропонованих структур мікропрограмних автоматів.

  Скачати повний текст

Розроблено нові ефективні моделі та методи, призначені для використання в САПР цифрових керуючих пристроїв (ЦКП). На основі відомої ознаки жорсткості моделі та новоутворених ознак її ширини та загальності розроблено класифікацію моделей керування та цифрових обчислювальних систем (ЦОС). Визначено місце традиційних моделей керування ЦОС у даній класифікації, виявлено їх недоліки. Показано недосконалість методів проектування, розроблених з використанням традиційних моделей керування ЦОС. Запропоновано нові моделі низького та високого рівнів для ЦКП, в яких усунуто виявлені недоліки традиційних моделей. Розроблено ефективні методи синтезу ЦКП за його описом на основі нових моделей керування ЦОС. Удосконалено методи оптимального кодування станів цифрового автомата, впровадження яких сприяє зменшенню апаратних витрат на реалізацію функції переходів ЦКП. Розроблено інформаційну технологію автоматизованого проектування ЦКП, в якій об'єднано традиційні й нові моделі та методи в єдиний формалізований процес, спрямований на підвищення ефективності кінцевого результату. Здійснено практичну апробацію розробленої інформаційної технології в САПР ЦКП.

  Скачати повний текст

Виконано модифікацію методів зменшення витрат апаратури у схемі автомата Мура. Застосування даних модифікацій забезпечує зменшення апаратурних витрат у логічній схемі автомата до 62 %. Розроблено структури, застосування яких разом з модифікованими методами забезпечує зменшення апаратурних витрат в логічній схемі автомата до 44 %. Наведено алгоритм вибору моделі автомата Мура з найменшими витратами апаратури для заданої граф-схеми алгоритму (ГСА), за результатами аналізу характеристик ГСА та базису реалізації схеми.

  Скачати повний текст

Висвітлено питання проектування моделей цифрових керуючих автоматів, поведінку яких представлено на мові VHDL. Для дотримання стандарту VHDL розроблено моделі змістовних графів переходів цифрових автоматів, орієнтованих на технологічне рішення задач генерації тестів, перевірки справності та верифікаційного моделювання. Запропоновано стратегію тестування керуючого автомата, яка містить чотири алгоритми обходу верхівок та дуг графа; модифікований П-алгоритм для знаходження рішень у вигляді вхідних наборів, які приводять автомат у необхідний стан. Моделі опису, генерації тестів реалізовано у вигляді програмного продукту ASFTEST, який сумісний з системою Active - HDL і підтримує стандарти мов Active, Verilog.

  Скачати повний текст

Досліджено властивості самоподібних груп, їх зв'язок з теорією автоматів, ітераціями віртуальних ендоморфізмів, операторними алгебрами та динамічними системами. Побудовано теорію стикуючих груп та їх граничних просторів. Знайдено алгоритми для розв'язання проблеми рівності у групах та напівгрупах асинхронних автоматів. Доведено, що стискуючі групи мають поліноміальну складність проблеми рівності. Розроблено нові методи доведення неізоморфності груп, що дозволило дати відповідь на питання Р.Григорчука про класифікацію груп G_omega з точністю до ізоморфізму. Введено групи ітерованих монодромій. Показано, що граничні простори груп ітерованих монодромій розширюючих відображень збігаються з їх множинами Жюліа. Обгрунтовано можливості застосування теорії груп, породжених скінченими автоматами, до голоморфної динаміки. Знайдено формулу для обчислення дії груп ітерованих монодромій на кореневому дереві, що розв'язує проблему Р.Пінка про обчислення груп Галуа ітерованих розширень поля функцій. Доведено, що алгебри Кунца - Пімзнера, природньо пов'язані з самоподібними групами, є простими. Знайдено новий зв'язок між групами Хігмана - Томпсона та алгебрами Кунца. Доведено, що всі власні фактор-групи групи, породженої групою Хігмана - Томпсона та самоподібною групою, абелеві. Запропоновано метод знаходження максимального абелевого фактора такої групи та знайдено новий клас простих нескінчених груп.

  Скачати повний текст

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

  Скачати повний текст

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

  Скачати повний текст