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

• Еременко Дмитрий Александрович
• кандидат наук
• 2022

Оглавление диссертации кандидат наук Еременко Дмитрий Александрович

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ

ГЛАВА 1. ОБЩИЕ СВЕДЕНИЯ

1.1. Теоретические сведения об операциях и мультиоперациях

1.2. Обзор средств компьютерной математики

1.3. Описание основных понятий из теории автоматов

ГЛАВА 2. СТРУКТУРЫ И АЛГОРИТМЫ ДЛЯ ВЫЧИСЛЕНИЙ В ТЕОРИИ

МУЛЬТИОПЕРАЦИЙ

2.1. Представление операций и мультиопераций

2.2. Реализация суперпозиции для операций и мультиопераций

2.3. Алгебраические замыкания операций и мультиопераций

ГЛАВА 3. РАЗРАБОТКА БИБЛИОТЕКИ ДЛЯ ВЫЧИСЛЕНИЙ В ТЕОРИИ

МУЛЬТИОПЕРАЦИЙ

3.1. Реализация программного комплекса

3.2. Состав и назначение разработанного программного комплекса 87 ГЛАВА 4. ПОЛУЧЕННЫЕ РЕЗУЛЬТАТЫ В ТЕОРИИ МУЛЬТИОПЕРАЦИЙ

4.1. Представление алгебр операций через бинарные мультиоперации с помощью соответствия Галуа

4.2. Разработка алгоритма построения решеток мультиопераций на основе неразложимых алгебр

4.3. Минимальные алгебры бинарных операций ранга

4.4. Надминимальные алгебры бинарных операций ранга

4.5. Применение мультиопераций в теории автоматов 125 ЗАКЛЮЧЕНИЕ 134 СПИСОК ЛИТЕРАТУРЫ 135 Приложение А 143 Приложение Б 159 Приложение В 163 Приложение Г

ВВЕДЕНИЕ

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

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

Теория мультиопераций относится к теории функциональных систем, которая изучает множества функций с заданными на них операторами. Данный раздел математики развивается уже более ста лет. Так, в первой половине двадцатого века в работах Э. Поста [68, 69] была решена задача описания всех замкнутых классов функций, определенных на двухэлементном множестве. Во второй половине двадцатого века данная теория также активно развивалась. Например, в работе С.В. Яблонского [41] были найдены максимальные замкнутые классы функций ранга 3. В работе И.Г. Розенберга [74] была решена проблема полноты для замкнутого класса всех функций на конечном множестве. Он доказал, что каждый максимальный подкласс этого класса образован функциями, сохраняющими определенное отношение, и описал эти отношения. В работах А. И. Мальцева

[22,23] был предложен алгебраический подход к исследованию функций многозначной логики.

В 21 веке одним из направлений развития функциональных систем стала теория мультиопераций. Перечислим лишь некоторые исследования в теории мультиопераций: работа [48] посвящена изучению решетки замкнутых классов частичных мультиопераций (частичных гиперклонов), в работе [73] получен полный список максимальных замкнутых классов частичных мультиопераций, в работе [75] получено разбиение всех минимальных замкнутых классов функций на пять типов, а в работе [70] данная классификация была расширена на замкнутые классы мультиопераций.

В настоящий момент для развития теории мультиоперации применяются компьютерные вычисления. Так, например, в работе [15] были перечислены все алгебры унарных мультиопераций ранга 3, в работе [80] с помощью компьютерных вычислений были найдены все замкнутые классы трехзначной логики, содержащие функцию голосования. В работе [21] были вычислены все унарные Шефферовы мультиоперации ранга 4. В работе [38] были найдены все минимальные алгебры бинарных мультиопераций ранга

Однако, несмотря на ведущиеся исследования в теории мультиопераций, в современных средствах компьютерной математики недостаточно функционала для исследования алгебр операций и мультиопераций. Самой подходящей из существующих систем компьютерной алгебры (СКА) можно считать «Sage». Используя класс sage.sets.finite_set_maps [76], можно смоделировать алгебры унарных операций различного ранга в сигнатуре <*> (суперпозиция операций), представив их в виде моноида с операцией суперпозиции. Но для изучения унарных операций и мультиопераций данного инструментария недостаточно. В sage.sets.finite_set_maps поддерживается только одна сигнатура, в то время как в теории мультиопераций алгебры рассматриваются в различных сигнатурах (например, с операторами пересечения, объединения или более сложные сигнатуры, включающие в себя несколько операторов).

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

Актуальность темы

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

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

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

- разработать программный комплекс для вычисления алгебр с различными сигнатурами в теории мультиопераций;

- разработать и реализовать алгоритмы для решения трудоемких вычислительных задач в теории мультиопераций;

- получить классификацию бинарных операций ранга 3;

- разработать математическую модель обобщенных конечных автоматов, используя теорию мультиопераций.

Методы исследований

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

Основные положения, выносимые на защиту:

- Программный комплекс для компьютерных вычислений в теории мультиопераций.

- Алгоритмы и их реализация для решения вычислительных задач в теории мультиопераций.

- Классификация минимальных и надминимальных алгебр бинарных операций ранга 3.

- Математическая модель обобщенных конечных автоматов. Научная новизна

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

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

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

- Представлена математическая модель обобщенных автоматов с помощью мультиопераций.

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

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

Предложенная математическая модель применима для моделирования различных систем, которые могут быть описаны с помощью обобщенных конечных автоматов.

Апробация работы

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

- 71-я научно-техническая конференция профессорско-преподавательского состава ЛЭТИ, Санкт-Петербург, Россия, 29.01.2018 - 09.02.2018;

- 13th International Symposium. «Intelligent Systems - 2018» (INTELS'18), Санкт-Петербург, Россия, 22.10.2018 - 24.10.2018;

- Мальцевские чтения, Новосибирск, Россия, 19.11.2018 - 22.11.2018;

- 10th Mediterranean Conference on Embedded Computing (MECO'2021), Будва, Черногория, 07.06.2021-10.06.2021;

- XIV Международная школа-конференция «Пограничные вопросы теории моделей и универсальной алгебры», Новосибирск, Россия 23.06.2021 -28.06.2021.

Обоснованность и достоверность

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

Публикации

Полученные основные теоретические и практические результаты опубликованы в 8 трудах, из них 5 работ входят в перечень ВАК (3 статьи в журналах [83-85] и 2 свидетельства о регистрации программы ЭВМ [86,87]), а также 3 публикации в сборниках конференций [88,89] и в других журналах [82].

Структура и объем диссертации

Диссертационная работа состоит из введения, четырех глав, заключения, четырех приложений, списка литературы (89 наименований). Общий объем работы составляет 179 страниц машинописного текста, который включает 21 рисунок, 23 таблицы, 4 приложения.

В первой главе приводятся необходимые теоретические сведения для представления результатов, выносимых на защиту. В первом разделе приводится теоретические сведения из теории мультиопераций. Вводятся такие понятия как: операции, мультиоперации, алгебра операций/мультиопераций и прочие понятия необходимые для представления результатов работы. Во втором разделе приводится обзор средств компьютерной математики. Обзор был посвящен поиску инструментов для проведения исследований в теории мультиопераций. В результате не удалось найти подходящего инструмента для проведения вычислений в теории мультиопераций, однако необходимый функционал частично присутствует в системе компьютерной алгебры «Sage». В третьем разделе приводятся необходимые теоретические сведения из теории автоматов.

Вторая глава посвящена исследованию различных представлений операций и мультиопераций с помощью различных структур данных. В первом разделе на основании проведенных экспериментов делается вывод о том, какие коллекции Python 3, реализующие массивы, является оптимальным. Во втором разделе приводятся различные алгоритмы и их реализация для применения операторов к операциям и мультиоперациям. В третьем разделе приводятся алгоритмы и их реализация для вычисления алгебраического замыкания операций и мультиопераций.

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

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

Четвертая глава посвящена алгоритмам и новым полученным результатам в теории мультиопераций. В первом разделе представлен алгоритм для вычисления всех алгебр унарных операций ранга 3 через мультиоперации с помощью соответствия Галуа между решетками алгебр операций и мультиопераций. Во втором разделе приведено описание нахождения всех неразложимые алгебры унарных мультиопераций ранга 3, а также алгоритм построения решетки унарных мультиопераций ранга 3 на основе неразложимых алгебр. В третьем разделе представлен алгоритм нахождения всех минимальных алгебр бинарных операций ранга 3. В четвертом разделе приводится алгоритм для нахождения всех надминимальных алгебр над всеми минимальными алгебрами бинарных операций ранга 3, а также описание классов минимальных алгебр и описание классов надминимальных алгебр для каждого класса минимальных алгебр. В пятом разделе приводится разработанная математическая модель для обобщенных конечных автоматов и её применение для задачи выразимости из теории автоматов.

ГЛАВА 1. ОБЩИЕ СВЕДЕНИЯ

В разделе 1.1 приводятся необходимые теоретические сведения для представления результатов, выносимых на защиту.

В разделе 1.2 приводится обзор средств компьютерной математики как инструмента решения математических задач. Целью обзора был поиск инструмента для проведения исследований в теории мультиопераций. В результате исследования не удалось найти инструмент для проведения вычислений в теории мультиопераций. Тем не менее, необходимый функционал частично реализован в системе компьютерной алгебры «Sage».

В разделе 1.3 приведены необходимые теоретические сведения о теории автоматов.

1.1. Теоретические сведения об операциях и мультиоперациях

Введем следующие понятия и определения.

Операции

Воспользуемся теорией и определениями, использующимися в работах [25,26].

Пусть А - произвольное конечное множество, состоящее из к элементов. Элементы множества будем обозначать щ и записывать следующим образом:

А = {а0, ...ак-±}

Пусть п - натуральное число. Отображение f декартовой степени Ап в А называется n - местной операцией на А.

Под рангом к операции понимается мощность множества А. к = |Л|. Множество всех п - местных операций на А обозначим через Р1^. Выделим отдельно операцию проектирования по аргументу i:

е11(а1,...,ап) = аь

Введем следующий оператор - суперпозицию операций:

f£PnA и А.....fn^PT-

(f*fi,.~, fn)(x1, ...,хт) = f(fx (х1,...,хт), ...,fn (х1,...,хт)), где XiEA

Алгеброй п - местных операций над множеством А называют любое подмножество К с р™, замкнутое относительно суперпозиций и содержащее все п - местные операции проектирования.

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

Назовем наименьшей (тривиальной) алгеброй такую алгебру, которая содержит только операции проектирования.

Подалгеброй алгебры К будем называть алгебру содержащуюся в К и меньше К.

Минимальной алгеброй назовем алгебру, не содержащую в себе подалгебр, кроме наименьшей (тривиальной).

Пусть К - минимальная алгебра. Тогда надминимальной алгеброй и над К называется алгебра, не содержащая в себе подалгебр, которые содержат К.

Базисом для алгебры К будем называть минимальное порождающее множество, алгебраическое замыкание которого (вместе с операциями проектирования) порождает алгебру К. При этом в перечислении порождающего базиса будем опускать операции проектирования, т.к. они всегда присутствуют в алгебре по определению.

Алгебру К будем обозначать через порождающее множество следующим образом:

К = [Гг.....Гт]

Под объединением алгебр принято понимать алгебраическое замыкание объединения элементов, входящих в эти алгебры.

Неразложимой алгеброй К будем называть алгебру, которая не представима в виде объединения подалгебр К. Из определения очевидно, что любой базис такой алгебры содержит только одну операцию.

Разложимой алгеброй будем называть алгебру, которая представима в виде объединения собственных подалгебр.

Неразложимая надминимальная алгебра над минимальной К не может быть надминимальной над другой минимальной алгеброй.

Разложимая надминимальная алгебра над минимальной алгеброй К содержит еще хотя бы одну другую минимальную алгебру.

Клоном п - местных операций над множеством А называют любое подмножество К С Р1^, замкнутое относительно суперпозиций и содержащее все операции проектирования.

Мультиоперации

Воспользуемся теорией и определениями, использующимися в работах [27-30].

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

Пусть В (А) - множество всех подмножеств А. Отображение д декартовой степени Ап в В (А) называется п - местной мультиоперацией на А и обозначается как:

д:Ап ^ В (А)

Если все образы — одноэлементные множества, то д будет являться п -местной операцией.

Множество всех п - местных мультиопераций на А обозначим через М1^.

п - местной Шефферовой операцией/мультиоперацией на множестве А называется операция/мультиоперация, алгебраическое замыкание которой порождает всё множество Р1\/М1\.

Обобщим понятие суперпозиции для мультиопераций.

Суперпозиция мультиопераций определяется для д Е Мд и д±, ...,дп Е М™ следующей формулой:

(д * д1,^,дп)(Х1,^,хт) = У д(Ь1,^,Ьп),где Х1 Е А

Ь1Ед1(х1,^,хт)

Также для мультиопераций введём унарный оператор разрешимости:

(^д)(аг,..., ап) = {а \ а1 е д(аг ..., а1-1, а, аи1,..., ап)}

(п)

Алгеброй мультиопераций размерности п ранга к называется любое И Я Мк , содержащее все п - местные проекции, пустую мультиоперацию и замкнутое относительно операторов суперпозиции и разрешимости. Определение некоторых мультиопераций Определим некоторые мультиоперации.

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

0п(а1, ...,ап) = 0

п - местная полная мультиоперация - мультиоперация, возвращающая всё множество А, на котором она определена, независимо от входных аргументов.

пи(а1,..., ап) = А Бинарная мультиоперация пересечения:

дп(а,Ь) = {а] п {Ь} Векторная форма задания операций и мультиопераций Для обозначения конкретных операций и мультиопераций будем использовать векторную форму записи. Для этого введем кодировку элементов исходного множества А числами. Поскольку рассматриваются только конечные множества, то можно перечислить элементы и каждому из них сопоставить порядковый номер. Таким образом, операции f е Р™ на конечном множестве А = {а0,... ак-1} можно представить как отображения f: {0, ...,к — 1}п ^ х е {0,... ,к — 1}, получаемые при кодировке щ ^ /.

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

подмножествами этого множества. Поэтому для решения этой задачи используется кодировка, описанная ниже.

Мультиоперации д Е М™ на конечном множестве А = {а0, ...ак-1} можно представить как отображения д: {20,..., 2к-1}п ^ {0, 20,..., 2к-1}, получаемые при кодировке щ ^ 21,0 = 0, {а^,... а^) = 211 + —+ 213.

Тут и далее будем использовать кодировку для мультиопераций как обобщенную форму записи для операций и мультиопераций.

Векторная запись составляется таким образом, чтобы элементы вектора соответствовали значению функции для каждого набора аргументов из декартова произведения исходного набора. Например, для определения бинарной операции на трехэлементном множестве понадобится вектор, состоящий их 32 - элементов, который соответствует значениям определяемой операции.

Ниже приводится определение векторной формы.

Зададим / векторной формой:

С^ .■■,akn-l),

где аь Е {2°,..,2к-1}, аь = . ,2^п), Ц1,.,]п) есть представление I в

системе исчисления по основанию к, п - разрядным числом.

В качестве примера рассмотрим построение векторной формы для двухместной операции ранга 3 (п = 2, к = 3).

Зададим произвольное множество из трех элементов А = {а0, а1,а2].

Зададим операцию / с помощью таблицы Кэли:

Таблица 1.1 - Таблица Кэли для операций Г

Г а0 а1 0,2

а0 а1 а1 О2

а1 а0 а1 а1

0-2 0,2 а0 а0

В соответствии с кодировкой щ ^ 21 пронумеруем исходные элементы множества А и составим таблицу 1.2:

Таблица 1.2 - Таблица Кэли для f с кодировкой

Г 1 2 4

1 2 2 4

2 1 2 2

4 4 1 1

Составим векторную форму (а0,..., акп_1):

а0 = ¡{2^г, 0 = 003 таким образом }1 = 0, у2 = 0

ао = Г(20,20 , т. к. 0 = 00з ¡(1,1) = 2 или исходный элемент а1

а1 = Г(20,21 ,т.к.1 = 01з, ¡(1,2) = 2 или исходный элемент а1

а-2 = f(20, 22 , т. к. 2 = 02з ¡(1,4) = 4 или исходный элемент а2

а3 = f(21, 20 , т. к. 3 = 10з ¡(2,1) = 1 или исходный элемент а0

а4 = ¡(21, 21 ,т.к.4 = 11з ¡(2,2) = 2 или исходный элемент а1

а5 = Г(2\22 , т. к. 5 = 12з ¡(2,4) = 2 или исходный элемент а1

а6 = Г(22,20 , т. к. 6 = 20з 4, 1) = 4 или исходный элемент а2

а7 = Г(22,21 ,т.к.7 = 21з ¡(4,2) = 1 или исходный элемент а0

а8 = f(22, 22 , т. к. 8 = 22з ¡(4,4) = 1 или исходный элемент а0

В результате получим векторную форму заданной операции /:

! = (224122411)

Ниже приведем примеры векторной формы бинарных операций ранга 3:

- операции проектирования по первому аргументу е2, еКа^ а2) = а1 е2 = (111222444);

- операции проектирования по второму аргументу е|; е^(а1, а2) = а2 е2 = (124124124).

Также продемонстрируем применение кодировки для мультиопераций. Зададим мультиоперацию / таблицей Кэли:

Таблица 1.3 - Таблица Кэли для мультиопераций f

Г а-о а1 0,2

ао {ог02} (00,02) (ао,а1а2)

а1 М {а1) Ш

0-2 (а-о, %) (0)

В соответствии с кодировкой а^ ^ 21,0 = 0,{а^,...а= 21± + —+ 21б пронумеруем исходные элементы множества А и составим таблицу 1.4:

Таблица 1.4 - Таблица Кэли для мультиопераций f с кодировкой

Г 1 2 4

1 2г + 22 = 6 2о + 22 = 5 2о + 21 + 22 = 7

2 1 2 4

4 1 2о + 2г = 3 0

Составим векторную форму (ао,..., акп_1):

ао = ¡(2^1, 0 = 003 таким образом }1 = 0, у2 = 0

ао = Г(2о,2о , т. к. 0 = 00з ¡(1,1) = 6 или [а1а2)

а1 = Г(2о,21 ,т.к.1 = 01з, ¡(1,2) = 5 или (ао, а2)

а-2 = f(20, 22 ,т.к.2 = 02з ¡(1,4) = 7 или (ао, а1а2)

а3 = f(21, 2о , т. к. 3 = 10з ¡(2,1) = 1 или (ао)

а4 = ¡(21, 21 ,т.к.4 = 11з ¡(2,2) = 2 или (а1)

а5 = Г(2\22 , т. к. 5 = 12з ¡(2,4) = 4 или (а2)

а6 = Г(22,2о , т. к. 6 = 20з 4, 1) = 1 или (ао)

а7 = Г(22,21 ,т.к.7 = 21з ¡(4,2) = 3 или (ао, %)

а8 = f(22, 22 , т. к. 8 = 22з ¡(4,4) = 0 или (0)

В результате получим векторную форму заданной Г:

! = (657124130)

Применение суперпозиции к операциям

Рассмотрим суперпозицию бинарных операций ранга 3. Пусть даны три бинарные операции ранга 3, которые записываются в векторной форме следующим образом:

! = (224122411), ^ = (144241122), [2 = (412112424) Используя определение суперпозиции:

(! * к , /2)(Х1, Х2) = !(к (Х1, Х2), ¡2 (Х1, Х2)) Вычислим значение суперпозиции при заданных аргументах, например, при (Х1,Х2) = (а0,а0)\

(00,00) ^ (1,1), Г (к (1,1), Г2 (1,1)) = Г (1,4) = 4

Таким образом, вычислив значения суперпозиции для всех пар (х1, х2) Е А2, получим новую бинарную операцию ^ , которая представима в виде суперпозиции трех бинарных операций /3 = (/ * к ,/2). В векторной записи ^ будет иметь вид:

^ = (441142422) Применение суперпозиции к мультиоперациям

Пусть даны три бинарные мультиоперации ранга 3, которые записываются в векторной форме следующим образом:

д = (657124130), д1 = (215730461), д2 = (321145722) Используя определение суперпозиции:

(9* 91, д2)(*1, Х2) =^Ь1Ед1(х1,х2) 9(К Вычислим значение суперпозиции при заданных аргументах, например, при (Х1,Х2) = (а0,а0):

- (00,00(1,1), д(91 (1,1),д2(1,1))

- 91 (1,1) = {2}

- д2(1,1) = 3 = {1,2}

- (Ь1,Ь2) Е 91 (1,1) х 32(1,1) = {2} х {1,2}

- (д1 (1,1),д2(1,1)) = д(2,1) и д(2,2) = {а^} и {%} = {а0,%} = 3

а,ц =

Представление мультиопераций с помощью пространственных матриц

Представление унарных мультиопераций с помощью матриц было введено в работах [31, 67]. В работе [32] матричное представление было обобщено для всех мультиопераций.

Ниже приведём теоретические сведения из работы [32].

- Пусть В = ((0,1); +,.) - двухэлементное булево полукольцо. Для унарной мультиоперации / ранга к на А определим булеву квадратную матрицу над В к-го порядка М^ = ЦаиН где:

1, если щ Е ¡(а.}) 0, если щ £

- Операторы алгебр мультиопераций представляются матричными операциями: М(^д) = МГ Мд — матричное умножение;

гр

М(^) = М^ - транспонирование матрицы; Ме1 = Е - диагональная матрица; Мо = О - нулевая матрица.

Ниже приведём теоретические сведения из теории пространственных матриц

[36]:

- Двоичной п-мерной матрицей к-го порядка называется функция а : N¡1 ^ (0,1) , где Ык = (1.....к)

Обозначение: М = Н^.д ||, где ац.1п = а^,... ,Ьп).

- При фиксированном значении / (I Е Ык) индекса 5 получается (п - 1) - мерная матрица к-го порядка, которая называется ¿-сечением М по индексу 5, обозначается М1б .

Транспонированием матрицы М = матрицу Мт*р =

^11..Л8..Л-р..Лп

, по индексам 5 и р получаем

^11..Л8..Л-р..Лп

- В случае 5 = 1 и р = 2 используем обозначение Мт.

- Умножение п-мерной матрицей к-го порядка М на вектор V длины к по индексу 5 дает (п - 1) - мерную матрицу к-го порядка (М * =

\\Р11..л5-115+1...1п\1 при:

я. . = * V

где * является скалярным произведением векторов над булевым полукольцом

В.

Введем матричное представление мультиопераций размерности п ранга к.

Пусть В = ((0,1); +,.) - двухэлементное булево полукольцо. Для

мультиоперации / размерности п, ранга к на Л определим булеву

пространственную (п + 1) - мерную матрицу к-го порядка М^ = где:

_ (1, если а0 е /(а1,..., ап); 1°.~1п (0, если а0 £ [(а1, ...,ап).

Ниже приведем теорему, которая дает представление суперпозиции

мультиопераций пространственными булевыми матрицами [32].

Теорема А. Пусть /0 е М^ и /1.....^ е и .....Гп) =

а Я- ■ ■ = ( ((М10 * М11"'1™) * „ м11"-1™) м11"'1™

а Р1о11.1т ((^/о *п м/п ) *п-1 МГп-1 ) ... ) *1 Мг1

Замечание. Порядок умножения на вектора не меняет результат вычисления

матрицы суперпозиции.

Битовой сложностью алгоритма нахождения матрицы суперпозиции мультиопераций назовем максимальное число операций +, ■ необходимое для нахождения по матрицам любых мультиопераций матрицы суперпозиции этих мультиопераций. Ниже приведем теорему о битовой сложности алгоритма нахождения матрицы суперпозиции мультиопераций [32].

Теорема В. Алгоритм нахождения матрицы суперпозиции мультиоперации размерности п с мультиоперациями размерности т ранга к, представленный в теореме А, имеет битовую сложность 0(кп+т+1).

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

нахождении матрицы Бк скалярного умножения всех векторов длины к. Квадратная матрица Бк порядка 2к определяется так: = ||^у|| , где ^¿у = (/ — 1)2 * (] — 1)2 и /,; Е (1, ...,2к) .

Матрицу Бк можно построить следующей рекуррентной процедурой:

= ||0||; Бк =

1 1 $к_ 1 1

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

Скалярной сложностью алгоритма нахождения матрицы суперпозиции мультиопераций назовем максимальное число обращений к матрице скалярного умножения векторов, необходимое для нахождения по матрицам любых мультиопераций матрицы суперпозиции этих мультиопераций. Ниже приведем теорему о битовой сложности алгоритма нахождения матрицы суперпозиции мультиопераций с предварительной обработкой [32].

Теорема С. Скалярная сложность нахождения матрицы суперпозиции мультиоперации размерности п с мультиоперациями размерности т ранга к равна 0(кп+т) .

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

- ^(/о*Л,",/п )— (п + 1) - мерная матрица к-го порядка находится по теореме 1 при т = п;

гр

- ^(м/) = — транспонирование пространственной матрицы по двум первым индексам;

- Мвз = Е3 — (п + 1) - мерная матрица к-го порядка такая, что все сечения

_ ' являются диагональными квадратными матрицами к-го

порядка;

- Мо = О — нулевая (п + 1) - мерная матрица к-го порядка.

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

Если / мультиоперация ранга к, размерности п, то / = (at,..., акп) векторная форма, где at е {0,1, ...,2к-1} и at = f(2l1,...,2in), а (it,.,in) есть представление i - 1 в системе исчисления по основанию к п - разрядным числом.

Приведем пример представления суперпозиции мультиопераций размерности 3 ранга 2.

/о = (426537011) = (126543502),/2 = (247131225), 9 = (fo */i,/2) = (277415307) Эти мультиоперации представимы следующими пространственными булевыми матрицами:

М/0 = (000111011 011011000 101101000) Мп = (100101100 011001001 001110100) М/2 = (001111001 101010110 011000001)

Вычисление элементов матрицы суперпозиции можно находить с использованием матрицы скалярного умножения векторов.

00000000 01010101 00110011 01110111 0 0 0 0 1 1 1 1 01011111 00111111 01111111

Проделав вычисления:

ад(111)= (((000 111 011) *2 (010)) *! (100)) = ((011) *! (100)) = 0 ад(211) = (((011 011 000) *2 (010)) *! (100)) = ((110) (100)) = 1 ад(311)= (((101 101 000) *2 (010)) *! (100)) = ((000) (100)) = 0

S, =

и так далее, получим пространственную матрицу, представляющую суперпозицию:

Мд = (011011101 111000101 011101001) Связь Галуа для упорядоченных множеств

Воспользуемся теоретическими сведениями, которые приводятся в работах [24, 33].

Пусть С, О упорядоченные множества.

Пара соответствий р : С ^ Б и п : й ^ С определяет связь Галуа для С и если выполняются условия:

1. Для любых с1, с2 Е С и <11,<12 Е О если с1 < с2 и (11< <12, то р(с1) > р(с2) и п(й1) > я(^2);

2. Для любых с ЕС и й Е Б верно п(р(с)) > с и п(р((1)) > й.

Если при этом выполняется п(р(с)) = с, то связь Галуа совершенна в С, если р(п((£)) = (I, то совершенна в £ и просто совершенной, если является совершенной там и там. Часто используется следующий критерий [24]:

Теорема Б. 1. Связь Галуа совершенна в С тогда и только тогда, когда для любых различных элементов с1,с2 Е С следует, что р(с1) и р(с2) различны. 2. Связь Галуа совершенна в Б тогда и только тогда, когда для любых различных элемента й1, <12 Е Б следует, что п(<!1) и п(<12) различны.

Отметим, что совершенная связь Галуа была найдена для клонов и ко -клонов в работе [4], для клонов и суперклонов в работе [34]. Теория Галуа для У1^ и

Будем использовать обозначения М(п), для множества мультиопераций и

(п) (п)

операций размерности п, ранга к. Очевидно, выполняется с .

Для формулировки тождества полуперестановочности распространим определение суперпозиции на случай мультиопераций разной размерности

следующим образом: если f Е М(п) и Д,... ,/п Е М(т), то

(У* /1,...,/пЖ,-,ат) = У

Ь1 6 /¿(«1.....от)

Пусть / 6 М(п) и $6 М(т). Определим тождество полуперестановочности для / и д так:

(Г*(а* .....е™).....(я * <$-1)те+1.....«)) С

с (д*(Г* еГ, «1.....<$-1)те+1).....(Г* е™, .....е^)),

где верхний индекс у проекций указывает на их размерность.

В этом случае будем говорить, что / стабильна относительно д и д нормальна относительно f.

Пусть д 6 М(т) и f 6 о(п). Тогда

$п(д) = {Я/ 6 0(п) и f стабильна относительно д};

Ыт(/) = {д1д 6 М(т) и д нормальна относительно /}.

Множество 5п(д) называется п-стабилизатором д, а множество — т-

нормализатором

Пусть Я с м(т) и КС о(п\ Тогда: Бп(Ю = П а 6 я $п(д) - ^-стабилизатор множества мультиопераций Я Ыт(к) = Пf 6 к Мт(/) - т-нормализатор множества мультиопераций К [34].

Список литературы диссертационного исследования кандидат наук Еременко Дмитрий Александрович, 2022 год

СПИСОК ЛИТЕРАТУРЫ

1. Агибалов, Г.П., Оранов, А.М. Лекции по теории конечных автоматов. // Томск: Изд-во Том. Ун-та, 1985. — С. 120.

2. Аладьев, В. З., Ваганов В. А. Модульное программирование: Maple vs Mathematica, and vice versa //CA: Palo Alto, Fultus Corp. - 2011 — С. 417.

3. Аладьев В.З., Гринь Д.С. Расширение функциональной среды системы Mathematica: Монография / В.З. Аладьев, Д.С. Гринь.- Х.: Олди-Плюс, 2012. - С. 552.

4. Боднарчук, В. Г., Калужнин Л.А., Котов В.Н., Ромов Б.А. Теория Галуа для алгебр Поста I-II// Кибернетика - 1969 - №3 C.1-10, № 5 C. 1-9.

5. Буркатовская, Л. И. Логическое проектирование дискретных устройств: учебное пособие / Л. И. Буркатовская, Ю. Б. Буркатовская. // Томск: ТГУ, 2011. — С. 172.

6. Гамма, Э., Хелм Р., Джонсон Р. Дж. Влиссидес. Приемы объектно-ориентированного проектирования. Паттерны проектирования // СПб:Питер, 2001. — С. 368.

7. Гилл, А. Введение в теорию конечных автоматов. // М., Наука, 1966. - 272 с.

8. Гниденко В. М. Нахождение порядков предполных классов в трехзначной логике / / Проблемы кибернетики. Вып. 8. — М.: Физматгиз, 1962. — С. 341346.

9. Гржибовский, А.М., Иванов С.В., Горбатова М.А. Описательная статистика с использованием пакетов статистических программ Statistica и SPSS // Наука и здравоохранение. 2016. №1 — С. 7-36.

10. Дьяконов, В.П. Mathematica 5/6/7. Полное руководство. // М.: ДМК Пресс, 2009 — С.624.

11. Дьяконов, В. П. MATLAB. Полный самоучитель. // М.: ДМК Пресс, 2012— С. 768.

13. Дьяконов, В.П. Энциклопедия компьютерной алгебры. // М.: ДМК Пресс, 2009 — С. 1264.

14.Закревский, А. Д. Алгоритмы синтеза дискретных автоматов / А.Д. Закревский. // Москва: Наука, 1971. - С. 511.

15. Казимиров, А. С., Перязев, Н. А. Алгебры унарных мультиопераций //Тезисы докладов международной конференции Мальцевские чтения, Новосибирский государственный университет. - 2013. - С. 156.

16. Карпов, Ю. Г. Теория автоматов: Учебник для вузов / Юрий Глебович Карпов. // СПб.: Питер, 2002. - С. 208.

17. Кирьянов, Д. В. Mathcad 15/Mathcad Prime 1.0. // БХВ-Петербург, 2012 - С. 432.

18. Кравченко, А. В. О сложности решеток квазимногообразий для многообразий унарных алгебр. II// Сиб. электрон. матем. изв., 13, 2016. - С. 388-394.

19.Кудрявцев, В.Б, Алешин, С.В., Подколзин, А.С. Введение в теорию автоматов. // Москва: Издательство «Наука». 1985 - С. 320.

20. Кулаичев, А. П. Методы и средства комплексного анализа данных: учеб. пособие для вузов по дисциплинам "Прикладная статистика" и "Информатика" / А. П. Кулаичев ; А. П. Кулаичев. // Москва: Форум, 2006. -С. 511.

21. Малина, А. В. Шефферовы мультиоперации в полной алгебре унарных мультопераций ранга 4 / А. В. Малина, Н. А. Перязев // Известия Юго-Западного государственного университета. Серия: Управление, вычислительная техника, информатика. Медицинское приборостроение. -2016. - № 1(18). - С. 29-32.

22. Мальцев, А. И. Итеративные алгебры и многообразия Поста // Алгебра и логика. 1966. Т. 5. № 2. С. 5-24.

23. Мальцев, А. И. Итеративные алгебры Поста. // Новосибирск: Изд-во НГУ, 1976.

24. Оре, О. Теория графов. // М. : Наука, 1980 - С. 336.

25. Перязев, Н. А. Алгебры n-местных операций и мультиопераций. // Материалы XV международная конференция «Алгебра, теория чисел и дискретная геометрия: современные проблемы и приложения» (Тула, 28-31 мая 2018 г.) Тула: ТГПУ им. Л. Н. Толстого, 2018. - С. 113-116

26. Перязев, Н. А. Конечные алгебры операций и мультиопераций / Н. А. Перязев // Мальцевские чтения: Международная конференция. Тезисы докладов, Новосибирск, 19-22 ноября 2018 года. - Новосибирск: Федеральное государственное бюджетное учреждение науки Институт математики им. С. Л. Соболева, 2018. - С. 18.

27. Перязев, Н. А. Конечные алгебры мультиопераций //Алгебра, теория чисел и дискретная геометрия: современные проблемы, приложения и проблемы истории. - 2019. - С. 51-54.

28. Перязев, Н. А. Алгебры унарных мультиопераций конечного ранга / Н. А. Перязев // Синтаксис и семантика логических систем: материалы 6-й Междунар. школы-семинара / Под. ред. С. С. Гончарова [и др.]. - Иркутск: Изд-во ИГУ, 2019. - С. 76-79.

29. Перязев, Н. А., Тождества в алгебрах мультиопераций фиксированной размерности // Известия Иркутского государственного университета. Серия Математика, 2019, том 29, С. 86-97.

30. Перязев, Н. А., Шаранхаев И. К. Алгебры мультиопераций // Algebra and Model Theory 11. Collection of hahers. Novosibirsk : NSTU Publisher, 2017. P. 102-111.

31. Перязев, Н.А., Перязева Ю.В., Шаранхаев И.К. Минимальные алгебры унарных мультиопераций // Известия СПбГЭТУ «ЛЭТИ», №2/2016 С. 22-26

32. Перязев, Н. А. Представление алгебр мультиопераций пространственными матрицами //Алгебра, теория чисел и дискретная геометрия: современные проблемы, приложения и проблемы истории. Материалы XVIII Международной конференции, Тула. ТГПУ, 2020. С. 107-111.

33. Перязев, Н. А. Теория Галуа для конечных алгебр операций и мультиопераций ранга 2 // Известия Иркутского государственного университета. Серия Математика, 28 - 2019 - C. 113-122.

34. Перязев, Н. А., Шаранхаев И. К. Теория Галуа для клонов и суперклонов // Дискретная математика. Т. 27, вып. 4. -2015 - С. 79-93.

35. Перязев, Н.А. Клоны, ко-клоны, гиперклоны и суперклоны // Учён. зап. Казан. гос. ун-та. Сер. Физ.-матем. науки, T. 151, кн. 2, 2009 - С. 120-125.

36. Соколов, Н. П. Пространственные матрицы и их приложения. // М.: ГИФМЛ, 1960. - С. 300.

37. Таранчук, В. Б. Основные функции систем компьютерной алгебры : пособие для студентов фак. прикладной математики и информатики // Минск: БГУ, 2013 - С. 59.

38. Тодиков, С. И. Алгоритм поиска минимальных алгебр бинарных мультиопераций ранга 3 / С. И. Тодиков // Современные информационные технологии и ИТ-образование. - 2020. - Т. 16. - № 4. - С. 841-850.

39. Филиппова, Н. В. Применение систем компьютерной математики и компьютерных технологий при изучении дисциплин высшей математики как один из видов педагогических технологий // Молодой ученый.-2009. - №7. -С. 254-259

40. Черепашков, А. А. Компьютерные технологии, моделирование и автоматизированные системы в машиностроении: учебник / А. А. Черепашков, Н. В. Носов. // Волгоград: Ин-Фолио, 2009. - С. 591.

41. Яблонский, С. В. Функциональные построения в k-значной логике // Труды Математического института им. В. А. Стеклова АН СССР. — 1958. — Т. 51. — С. 5-142.

42. Badenhorst, W. Practical python design patterns. // Apress., 2017. Apress, Berkeley, CA — С. 350.

43.Basheyeva, A., Nurakunov, A., Schwidefsky, M., Zamojska-Dzienio, A. Lattices of subclasses. III // Сиб. электрон. матем. изв., 14, 2017. - С. 252-263.

44. Cronk, B. C. How to use PASW statistics: A step-by-step guide to analysis and interpretation. // Routledge, 2020.

45. Cronk, B. C. How to use SPSS: A step-by-step guide to analysis and interpretation. // Routledge, 2019.

46. Csakany, B. All minimal clones on three-element set / B. Csakany // Szeged : Acta Cybernetyca, 1983, Tom 6 - P. 227 - 237.

47. Demidova, L. et al. Software package statistica and educational process //SHS Web of Conferences. - EDP Sciences, 2016. - T. 29. - P. 2011.

48. Doroslovacki, R., Pantovic, J. and Vojvodic, G. One Interval in the Lattice of Partial Hyperclones. Czech Math J 55. - P. 719-724.

49.Everitt, B. S. Statistical Analvses using S-Plus. - Chapman and Hall/CRC, 2019. -P. 256.

50. Fitzpatrick, D. Analog design and simulation using OrCAD Capture and PSpice. -Newnes, 2017. - P. 433.

51. Fortin, C., Ignatiev, S. A., Voronina M. V. Wolfram Mathematica as applied to the interactive visualisation of descriptive geometry problems // Global Journal of Engineering Education. - 2021. - T. 23. - №. 1. - P. 37-42.

52. Giridhar, C. Learning Python Design Patterns. - Packt Publishing Ltd, 2016. - P. 138.

53. Gladstone, A. Building a Python Extension Module //C++ Software Interoperability for Windows Programmers. - Apress, Berkeley, CA, 2022. - P. 147-172.

54. Hilbe J. M. Review of sigmaplot 9.0 //The American Statistician. - 2005. - T. 59. - №. 1. - P. 111-112.

55. Hutz B. SAGE as a Source for Undergraduate Research Projects //PRIMUS. -2017. - T. 27. - №. 4-5. - P. 494-507.

56. Joachim von zur Gathen and Jürgen Gerhard, Modern Computer Algebra. Cambridge University Press, 2nd edition, 2003 - P. 768.

57. Kehtarnavaz, N., Gope C. DSP system design using LabVIEW and Simulink: a comparative evaluation //2006 IEEE International Conference on Acoustics Speech and Signal Processing Proceedings. - IEEE, 2006. - Т. 2. - С. II-II.

58. Lay, D. Function Algebras on Finite Sets. Berlin // Springer-Verlag, 2006. - P. 668.

59. Leander, J. et al. Nonlinear mixed effects modeling of deterministic and stochastic dynamical systems in Wolfram Mathematica //IFAC-PapersOnLine. - 2021. - Т. 54. - №. 7. - P. 409-414.

60. Lopez, C. MATLAB control systems engineering. - Apress, 2014.

61. Martin, N. M. The Sheffer functions of 3-valued logic //The Journal of Symbolic Logic. - 1954. - Т. 19. - №. 1. - P. 45-51.

62. Morrison M., Hastings C., Mischo K. Hands-on start to wolfram mathematica. // Wolfram Media, Inc. 2015.

63.Nau R. Statgraphics version 5: overview & tutorial guide // Fuqua School of Business. Duke University. - 2005. - P. 22.

64. NumPy documentation [Electronic resource]. - URL: https://numpy.org/doc/stable/reference/generated/numpy.array.html

65.Panteleyev, V. I., Haltanova, S. Yu. About some intervals in the lattic of clones of partial ultrafunctions// The Bulletin of Irkutsk State University. Series Mathematics, 2010, Volume 3, Issue 4. - P. 80-87

66. Pa§a, T., Ungureanu, V. Wolfram Mathematica as an environment for solving concave network transportation problems //Conference of Mathematical Society of the Republic of Moldova. - 2017. - Т. 4. - P. 429-432.

67. Peryazev, N. A., Peryazeva, Y. V., Sharankhaev, I. K. Minimal algebras of unary multioperations // Журнал СФУ. Математика и физика. 2016. №2 - P. 220-224.

68. Post, E. L. Determination of all closed systems of truth tables / E. L. Post // Bulletin American Mathematical Society, 1920, V. 26 - P. 427.

69. Post, E. L. Two-valued iterative systems of mathematical logic / E. L. Post // Annals of Mathematical Studies, 1941, V.5. - P. 122.

70.Pouzet, M., Rosenberg I. G. Small clones and the projection property //Algebra universalis. - 2010. - T. 63. - №. 1. - P. 37-44.

71.Python documentation: Abstract Base Classes [Electronic resource]. - URL: https://docs.python.org/3Zlibrary/abc.html

72. Rinker, D. G. Use of a TK Solver Performance Model in the Design and Testing of a Formula Hybrid Racecar. // University of Idaho, 2013.

73. Romov, B. A., "Partial hyperclones on a finite set," Proceedings 32nd IEEE International Symposium on Multiple-Valued Logic, 2002. - P. 17-22.

74. Rosenberg I. G. La structure des fonctions de plusieurs variables sur un ensemble fini // C. R. Acad. Sci. Paris. Ser. A, B. 1965. V. 260. - P. 3817-3819

75. Rosenberg I. G. Minimal clones I: the five types / I. G. Rosenberg // In Lectures in Universal Algebra 43, Colloq.Math. Soc. J. Bolyai. - 1983. - P. 405-427.

76. Sage 9.4 Reference Manual: Sets» Maps between finite sets [Electronic resource] .URL:https :// doc. sagemath.org/html/en/reference/sets/sage/sets/ finite_set_maps.html

77. Storey, B. D. Using the matlab data acquisition toolbox // URL: http://faculty. olin. edu/bstorey/Notes/Card. pdf (accessed January 2008). 2002. - P. 9.

78. Torrence, B. F., Torrence E. A. The Student's Introduction to Mathematica and the Wolfram Language. // Cambridge University Press, 2019. - P. 533.

79. Unpingco, J. Numpy // Python Programming for Data Analysis. - Springer, Cham, 2021. - P. 103-126.

80.Zhuk, D, Moiseev, S. On the clones containing a near-unanimity function. // In 43rd IEEE International Symposium on Multiple-Valued Logic (ISMVL 2013), May 2013. - P. 129-134.

81.Zimmermann, P. et al. Computational mathematics with SageMath. // Society for Industrial and Applied Mathematics, 2018. - P. 464.

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

82. Еременко, Д. А. Алгебры унарных операций ранга 3 / Д. А. Еременко // Известия СПбГЭТУ ЛЭТИ. - 2019. - № 7. - С. 14-18.

83. Еременко, Д. А. Минимальные алгебры бинарных операций ранга 3 / Д. А. Еременко // Компьютерные инструменты в образовании. - 2020. - № 1. - С. 38-48

84. Еременко, Д. А. Надминимальные алгебры бинарных операций ранга 3 / Д. А. Еременко // Компьютерные инструменты в образовании. - 2021. - № 4. -С. 72-87.

85. Еременко, Д. А. Разработка алгоритма построения решеток мультиопераций на основе неразложимых алгебр / Д. А. Еременко // Современные информационные технологии и ИТ-образование. - 2021. - Т. 17. - № 1. - С. 24-36

86.Еременко, Д.А. Программа для построения решетки алгебр унарных мультиопераций ранга 3 с помощью неразложимых алгебр. ПрЭВМ, Свидетельство № 2021615155 дата гос. рег. 05.04.21

87.Еременко, Д.А. Программа для проведения компьютерных вычислений в теории мультиопераций. ПрЭВМ, Свидетельство № 2022613916 дата гос. рег. 15.03.22

88. Еременко, Д. А. Классификация минимальных алгебр бинарных операций ранга 3 / Д. А. Еременко // Algebra and model theory: Collection of papers. -Novosibirsk: Новосибирский государственный технический университет, 2021. - С. 76-82.

89. Eremenko D. A. Minimal Algebras of Multioperations // 2021 10th Mediterranean Conference on Embedded Computing (MECO), 2021, P. 1-4

Приложение А

Исходный код пакета Algs

\Algs\_init_.py

from Algs.Algebras import AlgBase from Algs.Exceptions import AlgIter

from Algs.factories.args_generators import get_all_generators

from Algs.factories.closing_by_signature import get_closing_n

from Algs.factories.mappings import get_mapping_f_to_num, get_mapping_num_to_f

from Algs.factories.metaoperations import get_metaoperation_for_clc,

get_metaoperations_for_closing_by_signature

from Algs.helpers import parse_signature

def alg_factory(signature, parallel=True, bound=None, sheffer_list=(), chunk_size=10_000):

t, n, r, metaoperations_s = parse_signature(signature)

metaoperations_dict = get_metaoperation_for_clc(n, r, t) mapping_num_to_f = get_mapping_num_to_f(t, r, n) mapping_f_to_num = get_mapping_f_to_num(t, r) all_num = r ** (r ** n) if t == 'op' else (2 ** r) ** (r ** n)

metaoperations_for_closing = get_metaoperations_for_closing_by_signature(metaoperations_s, metaoperations_dict)

if '-1' in metaoperations_s:

basis_extend = metaoperations_dict['-1'] else:

basis_extend = None

closing = get_closing_n(metaoperations_for_closing,

n,

all_num, bound=bound,

sheffer_list=sheffer_list, chunk_size=chunk_size,

parallel=parallel, basis_extend=basis_extend)

class Alg(AlgBase):

metaoperations = metaoperations_dict

def _init_(self, basis):

AlgBase._init_(self, basis)

@staticmethod

def mapping_f_to_num(f):

return mapping_f_to_num(f)

@staticmethod

def mapping_num_to_f(num):

return mapping_num_to_f(num)

def _save_alg(self, closure): closure, msg = closure if msg == 'Sh':

self.alg = 'Sh"

return msg else:

self.alg = tuple((Alg.mapping_f_to_num(f) for f in closure)) return msg

@staticmethod

def make_close(base):

return closing(base)

def closing(self):

self.closed_state = self._save_alg(Alg.make_close(self.basis)) self.closed = True

def _iter_(self):

if self.closed:

if self.alg != 'Sh':

return (Alg.mapping_num_to_f(x) for x in self.alg) else:

return AlgIter("self.alg != 'Sh'", 'Alg is All fs')

else:

raise AlgIter('return (ternary(x, self.r) for x in self.alg)', 'Alg is not

closed')

return Alg

\Algs\Algebras.py

from abc import ABC, abstractmethod

class AlgBase(ABC):

def _init_(self, basis):

self.basis = basis self.alg = tuple() self.closed = False self.closed_state = None

@staticmethod @abstractmethod def mapping_f_to_num(f): pass

@staticmethod @abstractmethod def mapping_num_to_f(num): pass

@abstractmethod def closing(self): pass

@abstractmethod

def _iter_(self):

pass

Algs\Exceptions.py

class Error(Exception):

"""Base class for other exceptions

pass

class AlgIter(Error):

"""Raised when alg is not closed"""

def _init_(self, expression, message):

self.expression = expression self.message = message

class AlgSignature(Error):

"""Raised when alg is not closed"""

def _init_(self, expression, message):

self.expression = expression self.message = message

class AlgMetaoperation(Error):

"""Raised when alg is not closed"""

def _init_(self, expression, message):

self.expression = expression self.message = message

Algs\helpers.py

def parse_signature(signature):

prefix, *metaoperations_s = signature.split() t, n, r = prefix.split('_') n = int(n) r = int(r)

return t, n, r, metaoperations_s

Algs\factories\args_generators\__init_.py

from Algs.factories.args_generators.args_generators import *

def get_gen_superposition(n): if n == 2:

return binary_superposition_gen_args if n == 1:

return unary_superposition_gen_args

def gen_substitution_binary_cross_n(substitution_new, substitution_old): if substitution_old:

return filter(lambda x:

(not all(map(lambda y: y in substitution_new.copy(), x))) and

(not all(map(lambda y: y in substitution_old.copy(), x))), product(substitution_new.union(substitution_old), repeat=n + 1))

else:

return ()

def n_gen_args(substitution_new, substitution_old):

it = chain(gen_substitution_new(substitution_new.copy(), n + 1),

gen_substitution_binary_cross_n(substitution_new.copy(), substitution_old.copy()))

substitution_old.update(substitution_new) substitution_new.clear() return it

return n_gen_args

def get_gen_intersection_and_union(n): if n == 2:

return binary_intersection_and_union_gen_args

def gen_intersection_and_union_new_n(substitution_new): return combinations(substitution_new, n)

def gen_intersection_and_union_cross_1_n(substitution_new, substitution_old): if substitution_old:

return filter(lambda x:

(not all(map(lambda y: y in substitution_new.copy(), x))) and

(not all(map(lambda y: y in substitution_new.copy(), x))), combinations(substitution_new.union(substitution_old), n))

else:

return ()

def n_ary_intersection_and_union_gen_args(substitution_new, substitution_old): it = chain(gen_intersection_and_union_new_n(substitution_new.copy()),

gen_intersection_and_union_cross_1_n(substitution_new.copy(), substitution_old.copy()))

substitution_old.update(substitution_new) substitution_new.clear() return it

return n_ary_intersection_and_union_gen_args

def get_all_generators(n):

return get_gen_intersection_and_union(n), get_gen_superposition(n)

Algs\factories\args_generators\args_generators.py from itertools import product, chain, combinations

def gen_intersection_and_union_binary_new(substitution_new): return combinations(substitution_new, 2)

def gen_intersection_and_union_binary_cross_1(substitution_new, substitution_old): for x in substitution_new:

for y in substitution_old: yield (x, y)

def binary_intersection_and_union_gen_args(substitution_new, substitution_old): it = chain(gen_intersection_and_union_binary_new(substitution_new.copy()),

gen_intersection_and_union_binary_cross_1(substitution_new.copy(),

substitution_old.copy()))

substitution_old.update(substitution_new)

substitution_new.clear()

return it

def gen_substitution_new(substitution_new, rpt): return product(substitution_new, repeat=rpt)

def gen_substitution_binary_cross_1(substitution_new, substitution_old): for x in substitution_new:

for y in substitution_old:

for z in substitution_old: yield (x, y, z) yield (y, x, z) yield (y, z, x)

def gen_substitution_binary_cross_2(substitution_new, substitution_old): for x in substitution_new:

for y in substitution_new:

for z in substitution_old: yield (z, x, y) yield (x, z, y) yield (x, y, z)

def binary_superposition_gen_args(substitution_new, substitution_old): it = chain(gen_substitution_new(substitution_new.copy(), 3),

gen_substitution_binary_cross_1(substitution_new.copy(), substitution_old.copy()),

gen_substitution_binary_cross_2(substitution_new.copy(), substitution_old.copy()))

substitution_old.update(substitution_new)

substitution_new.clear()

return it

def gen_substitution_unary_cross_1(substitution_new, substitution_old): for x in substitution_new:

for y in substitution_old: yield (x, y) yield (y, x)

def unary_superposition_gen_args(substitution_new, substitution_old): it = chain(gen_substitution_new(substitution_new.copy(), 2),

gen_substitution_unary_cross_1(substitution_new.copy(), substitution_old.copy()))

substitution_old.update(substitution_new)

substitution_new.clear()

return it

Algs\factories\closing_by_signature\_init_.py

from Algs.factories.closing_by_signature.closing_by_signature import get_closing from Algs.factories.args_generators import get_all_generators

def get_closing_n(superposition_imap_list, n, all_num, sheffer_list=(), chunk_size=10_000, parallel=False,

bound=None, basis_extend=None): gen_args_list = get_all_generators(n)

closings_list = []

for superposition, gen in zip(superposition_imap_list, gen_args_list): if superposition:

closings_list.append(get_closing(superposition, gen, all_num, sheffer_list, chunk_size, parallel, bound))

def closing(basis): if basis_extend:

for mop in basis.copy():

basis.update(basis_extend(mop))

if any(map(lambda x: x in sheffer_list, basis)): return set(), 'Sh'

if len(closings_list) == 1:

alg_cloese = closings_list[0](basis) return alg_cloese else:

cnt = len(closings_list) while cnt > 0:

for closing_alg in closings_list: alg_close = closing_alg(basis)

if alg_close[1] == 'Sh' or alg_close[1] == 'Bond':

return alg_close if len(alg_close[0]) == len(basis):

cnt = cnt - 1 else:

if cnt <= 1:

cnt = cnt + 1 basis = alg_close[0] return alg_close

return closing

Algs\factories\closing_by_signature\closing_by_signature.py from multiprocessing import Pool

def make_s_close(superposition_imap, gen_args, all_num, sheffer_list=(), bound=None): if bound is None: bound = all_num msg = 'Sh' else:

msg = f'Bond_{bound}'

def closing_s(basis):

if any(map(lambda x: x in sheffer_list, basis)):

return set(), 'Sh' alg_close_substitution, new_mops_substitution = set(), basis.copy() while 1:

for fs in map(superposition_imap, gen_args(new_mops_substitution,

alg_close_substitution)):

for f in fs:

if f not in alg_close_substitution and f not in new_mops_substitution: if f in sheffer_list:

return set(), 'Sh' new_mops_substitution.add(f)

if len(alg_close_substitution) + len(new_mops_substitution) >=

bound:

return alg_close_substitution.union(new_mops_substitution),

msg

if not new_mops_substitution: break

return alg_close_substitution, 'Full' return closing_s

def make_p_close(superposition_imap, gen_args, all_num, sheffer_list=(), chunk_size=10_000, bound=None): if bound is None: bound = all_num msg = 'Sh' else:

msg = f'Bond_{bound}'

def closing_p(basis):

alg_close_substitution, new_mops_substitution = set(), basis.copy() with Pool() as pool: while 1:

for fs in pool.imap_unordered(superposition_imap, gen_args(new_mops_substitution,

alg_close_substitution), chunk_size):

for f in fs:

if f not in alg_close_substitution and f not in

new_mops_substitution:

if f in sheffer_list:

return set(), 'Sh' new_mops_substitution.add(f)

if len(alg_close_substitution) + len(new_mops_substitution) >=

bound:

return

alg_close_substitution.union(new_mops_substitution), msg if not new_mops_substitution: break

return alg_close_substitution, 'Full' return closing_p

def get_closing(superposition_imap, gen_args, all_num, sheffer_list=(), chunk_size=10_000, parallel=True,

bound=None):

selector = [make_s_close(superposition_imap, gen_args, all_num, sheffer_list, bound),

make_p_close(superposition_imap, gen_args, all_num, sheffer_list, chunk_size, bound)]

return selector[parallel]

Algs\factories\mappings\_init_.py

from functools import partial

from Algs.Exceptions import AlgSignature from Algs.factories.mappings.mappings import *

def get_mapping_f_to_num(t, r): if t == 'op':

return partial(mapping_f_num, base=r) if t == 'mop':

return partial(mapping_f_num, base=2 ** r)

def get_mapping_num_to_f(t, r, n): if t.startswith('op'):

base = r elif t.startswith('mop'):

base = 2 ** r else:

raise AlgSignature(expression='', message="signature not start with 'op' or

• ™~ _ i ii \ mop )

l = r ** n

return partial(mapping_num_f, base=base, l=l)

Algs\factories\mappings\mappings.py

def mapping_f_num(op, base):

return int(''.join(str(s) for s in op), base)

def mapping_num_f(num, l, base): if num == 0:

return tuple((0 for _ in range(l))) nums = [] while num:

num, m = divmod(num, base) nums.append(m) rez = list(reversed(nums)) while len(rez) < l:

rez.insert(0, 0) return tuple(rez)

Algs\factories\metaoperations\__init_.py

from Algs.Exceptions import AlgSignature, AlgMetaoperation from Algs.factories.metaoperations.metaoperations import *

def get_metaoperation_for_clc(n, r, t): if t == 'mop':

selector = {'*': get_superposition(t=t, r=r, n=n), '-1': get_invert(n, r), 'u': get_union(n), 'i': get_intersection(n)}

elif t == 'op':

selector = {'*': get_superposition(t=t, r=r, n=n)} else:

raise AlgSignature(expression=f't == {t}', message=f"No such type like {t}") return selector

def get_metaoperations_for_closing_by_signature(signature, metaoperations): rez = []

meataoperations_gen_1_list = []

if 'i' in signature:

meataoperations_gen_1_list.append(metaoperations['i'])

if 'u' in signature:

meataoperations_gen_1_list.append(metaoperations['u'])

if meataoperations_gen_1_list: if '-1' in signature:

invert = metaoperations['-1']

rez.append(partial(metaoperation_i, meataoperations_gen_1_list, invert)) else:

rez.append(partial(metaoperation, meataoperations_gen_1_list))

else:

rez.append([])

meataoperations_gen_2_list = []

if '*' in signature:

meataoperations_gen_2_list.append(metaoperations['*'])

if meataoperations_gen_2_list: if '-1' in signature:

invert = metaoperations['-1']

rez.append((partial(metaoperation_i, meataoperations_gen_2_list, invert))) else:

rez.append(partial(metaoperation, meataoperations_gen_2_list))

else:

rez.append([])

return rez

Algs\factories\metaoperations\metaoperations.py

from functools import partial, reduce

from itertools import product

from Algs.Exceptions import AlgMetaoperation

def num_to_set(x): powers = [] i = 1 cnt = 0 while i <= x: if i & x:

powers.append(cnt) cnt += 1 i <<= 1

return tuple(powers)

# Unary

def unary_superposition_op_r_3(ar_1, op):

return op[ar_1[0]], op[ar_1[1]], op[ar_1[2]]

def unary_substitution_op(r, ar_1, op): rez = [x for x in range(r)] for x in rez:

rez[x] = op[ar_1[x]] return tuple(rez)

def unary_superposition_op_r(r): if r == 3:

return unary_superposition_op_r_3 else:

return partial(unary_substitution_op, r)

def unary_superposition_mop_r_3(ar_1: tuple, mop: tuple): """substitution for unary muLtioperations. :param tuple f: multioperation which. :param tuple g: multioperation for :rtype: tuple

dic_mop = {

1: (0,),

2: (1,),

3: (0, 1),

4 (2,),

5 (0, 2),

6 (1, 2),

7 (0, 1, 2)

}

a, b, c = 0, 0, 0 if ar_1[0] != 0:

for x in dic_mop[ar_1[0]]: a = a | mop[x] if ar_1[1] != 0:

for x in dic_mop[ar_1[1]]: b = b | mop[x] if ar_1[2] != 0:

for x in dic_mop[ar_1[2]]: c = c | mop[x] return a, b, c

def unary_substitution_mop(r, dic_mop, ar_1, mop): # unary operations r 3 rez = [0 for _ in range(r)]

for index, num in enumerate(ar_1): if num == 0:

rez[index] = 0 else:

for x in dic_mop[num]:

rez[index] = rez[index] | mop[x] return tuple(rez)

def unary_superposition_mop_r(r): if r == 3:

return unary_superposition_mop_r_3 else:

dic_mop = {x: num_to_set(x) for x in range(1, 2 ** r)} return partial(unary_substitution_mop, r, dic_mop)

def unary_invert_r_3(mop):

I = list(map(lambda x: format(x, f'03b'), mop))

II = [x[::-1] for x in l]

rez = [int("".join(x[::-1]), 2) for x in zip(*ll)] return tuple(rez)

def unary_invert(r, mop):

I = list(map(lambda x: format(x, f'0{r}b'), mop))

II = [x[::-1] for x in l]

rez = [int("".join(x[::-1]), 2) for x in zip(*ll)] return tuple(rez)

def unary_invert_r(r):

return partial(unary_invert, r)

def unary_superposition_mop_r_i_3(ar1, mop):

superposition_rez = unary_superposition_mop_r_3(ar1, mop) invert_superposition_rez = unary_invert_r_3 return superposition_rez, invert_superposition_rez

def unary_superposition_mop_r_i(superposition_f, invert_f, arl, mop): superposition_rez = superposition_f(ar1, mop) invert_superposition_rez = invert_f(superposition_rez) return superposition_rez, invert_superposition_rez

def unary_superposition_mop_r_i_r(r):

superposition_mop = unary_superposition_mop_r(r) invert_mop = unary_invert_r(r)

return partial(unary_superposition_mop_r_i, superposition_mop, invert_mop)

# Binary

def binary_intersection(ar_1, ar_2): # ar_1, ar_2 = args_f

return tuple((a1 & a2 for a1, a2 in zip(ar_1, ar_2)))

def binary_union(ar_1, ar_2): # ar_1, ar_2 = args_f

return tuple((a1 | a2 for a1, a2 in zip(ar_1, ar_2)))

def binary_superposition_op_r_3(ar_1, ar_2, bop):

return bop[ar_2[0] * 3 + ar_1[0]], bop[ar_2[1] * 3 + ar_1[1]], bop[ar_2[2] * 3 + ar_1[2]], \