автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Функциональные системы полиномов и их применение в программировании для вычислительных систем и сетей

На правах рукописи

Мамонтов Андрей Игоревич

ФУНКЦИОНАЛЬНЫЕ СИСТЕМЫ ПОЛИНОМОВ И ИХ ПРИМЕНЕНИЕ В ПРОГРАММИРОВАНИИ ДЛЯ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ И СЕТЕЙ

Специальность 05 13 11 — Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

Автореферат диссертации на соискание ученой степени кандидата технических наук

ооз161129

Москва — 2007

003161129

Работа выполнена на кафедре Математического моделирования Московского энергетического института (технического университета)

Научный руководитель Официальные оппоненты

Ведущая организация

кандидат физико-математических наук, доцент

Мещанинов Дмитрий Германович

доктор технических наук, профессор

Кутепов Виталий Павлович

кандидат физико-математических наук, доцент

Алексиадис Никое Филиппович

факультет вычислительной математики и кибернетики МГУ им М В Ломоносова

Защита состоится" " 2007 в П ч 00 мин в ауд -ЪОЬ

на заседании Диссертационного совета Д 212 157 01 при Московском энергетическом институте (техническом университете) по адресу 111250, г Москва, ул Красноказарменная, д 17

С диссертацией можно ознакомиться в библиотеке МЭИ (ТУ)

Отзывы в двух экземплярах, заверенные печатью организации, просьба направлять по адресу 111250, г Москва, ул Красноказарменная, д 14, Ученый совет МЭИ (ТУ)

Автореферат разослан ' ш^д 2007

Ученый секретарь Диссертационного совета кандидат технических наук, профессор / / // (/ Ладыгин И И

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ Объект исследования и актуальность темы Задачи организации эффективных вычислений являются одними из ключевых задач информатики Успешное решение этих задач часто позволяет получить хорошие результаты в различных отраслях науки и техники

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

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

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

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

В соответствии с целью исследования были поставлены следующие конкретные задачи

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

2 Исследовать эффективность вычисления линейных полиномов при их представлении в различных базисах функциональных систем,

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

'Воеводин В В , Воеводин Вл В Параллельные вычисления — СПб БХВ-Петербург, 2004, Куте-чов В П Функциональные системы и параллельные вычисления Дисс докт техн наук — М , 1981, Малюгин В Д Параллельные логические вычисления посредством арифметических полиномов — М \ ФИЗМАТЛИТ, 1997 \ * ^

4 Провести экспериментальное исследование созданных методов и выполнить сравнительный анализ с другими применяемыми методами,

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

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

Практическая значимость работы

Полученные методы хорошо проявили себя в вычислительной практике Результаты исследований были внедрены в Московском энергетическом институте (техническом университете)

Обоснованность и достоверность результатов Реультаты диссертации обоснованы математически, и их достоверность подтверждена эксперимен-талоно

Апробация работы Результаты докладывались и обсуждались на

1 Научной сессии МИФИ, Москва, 2003, 2004, 2005,

2 Девятой, десятой, одиннадцатой, двенадцатой и тринадцатой международных научно-технических конференциях студентов и аспирантов „Радиоэлектроника, электротехника и энергетика", Москва, 2003, 2004, 2005, 2006, 2007,

3 Девятой международной конференции „Интеллектуальные системы и компьютерные науки", Москва, 2006,

4 Шестой и седьмой международных конференциях „Дискретные модели в теории управляющих систем", Москва, 2004, 2006,

5 Научном семинаре кафедры Математической кибернетики факультета ВМиК МГУ

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ Первая глава является вводной, в ней обоснована актуальность темы, сформулированы цели и основные задачи исследования, показана научная но-

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

Во второй главе приводятся необходимые определения из теории функциональных систем, проясняются задачи математической части диссертации В третьей главе исследуется функциональная система (¿(К), С) линейных полиномов с целыми неотрицательными коэффициентами и операцией суперпозиции (переименование переменных, отождествление переменных, подстановка функций на места переменных других функций)

В Ш Дарсалия2 исследовал функциональную систему (Р(К),С) полиномов с целыми неотрицательными коэффициентами и операцией суперпозиции и нашел все предполные классы в Р(Д) — это классы Уо — Р(Р5) \ \ {0}, класс всех функций со свободным членом отличным от 1, класс У+ всех неаддитивных функций (из них при замене переменных константами 0 и 1 иелйзя получить сумму двух переменных) и класс V"* всех немультипликативных функций (из них при замене переменных константами 0 и 1 нельзя получить произведение двух переменных) Рассмотрим замкнутые классы ¿о(Р|) = П = ОД П VI, Ь+(М) = ¿(К) П

Теорема 3.1 1. Система функций из ¿(К) полна в тогда и только тогда, когда она не содержится ни в одном из классов Ьо(К), Ь^К), £+(К) Следствие 3 13. Существует ровно три предполных в £(М) класса ¿о(Н), М^)

Для всех классов Х-оО^), и Ь+(К) построены критериальные си-

стемы

В четвертой главе исследуется функциональная система (Ь{Ъ),С) линейных полиномов с целыми коэффициентами и операцией суперпозиции Класс £(2) является конечно-порожденным, системы {1 ,х — у} и {1, -х,х + у} образуют базисы в ¿(2)

Определим следующие замкнутые классы

1 Пусть Ь+ — подкласс всех таких функций из Ь{Щ, у которых все коэффициенты при переменных неотрицательны

2 Пусть рх, ,ре — разные простые числа, т — р\ р5 Определим

2Дарсалия В Ш Условия полноты для починомов с натуральными, целыми и рациональными коэффициентами // Фундаментальная и прикладная математика — 1996 — т 2, № 2 — С 365-374

класс С(т) как класс, содержащий все функции каждого из двух типов 1) все коэффициенты при переменных кратны некоторому делителю рг числа т, 2) все коэффициенты при переменных кроме, возможно, одного кратны т

3 Для функции/(^1, ,хп) = ао+а,1Х2+ +апхп рассмотрим сумму коэффициентов ЯС^/) = + +а„ Для каждого к £ N определим (к) как класс всех функций / в Ь(Щ, удовлетворяющих условию ЗСД/) = 1 (тос! к)

4 Обозначим через V класс, содержащий все функции каждого из двух типов 1) константы и функции одной переменной, 2) функции, у которых все коэффициенты при переменьых кратьы некоторому натуральному числу к,

Г. ^ г> Л

5 Для 6 € N и а € {0,1, ,6 — 1} обозначим через II(а, Ь) класс всех функций из Ь{ 2), сохраняющих множество {с € Ъ с~ а (тос! &)}

Теорема 4.9.1. Система функций С Ь{Щ полна в Ь{Щ тогда и только тогда, когда при любых различных простых числах р\, р2, , рп> любом простом р 1л а = 0,1, , р — 1 система С? не содержится ни в одном из классов Ь+, Д 51(р), С(рг рп), и(а,р)

Найдены базисы в каждом из указанных классов, при этом класс О обладает бесконечным базисом

Опишем далее алгоритм, распознающий полноту в Ь{Ъ) любой конечной системы функций, для этого введем определения, обозначения и процедуры Далее буквами р, д (возможно с индексами) обозначаем простые числа

Расширим понятие наибольшего общего делителя нескольких целых чисел «1, ,ап полагая А(а% ,<0 = 0 при а\ — = ап = 0, в противном случае Д(оь ,ап) равен наибольшему общему делителю лишь ненулевых из чисел 01, ,а„ Наряду с приведенным будем применять обозначение

п

Д аг

г=1

Пусть Р = {/1, ,/т} — конечная система функций из Требу-

ется вычислить, полна ли система ^ в Ь{Ъ) (предполагается ответ „Да"или „Нет") Каждую из функций системы Р считаем зависящей от одного множества переменных и представляем в виде

/,(») = аг0 + алх 1 + + атхп, г = 1, , т,

при этом некоторые коэффициенты оу, j — 1, , п, могут быть нулевыми

Введем характеристику NV(f), принимающую значение 1, если функция / из jC(Z) существенно зависит от двух или более переменных, и 0 иначе

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

Процедура \Л/НАТС(г, с, /) имеет входной параметр г € {1, , то} — номер функции из системы F такой, что NV(f%) — 1 Процедура возвращает число с — Д(агх, , ает) и список I всех чисел d ф 1, таких, что

Зк е {1, , п) а1к Ф 0 и d| Д ач

Процедура INTERSECTÍcj, сг, h) получает на входе числа с\, ci и списки li, I2 В результате ее работы число ci заменяется на Д^сг), число сг не изменяется, список I2 заменяется на пустой, а измененный список 1\ образуется из чисел d, удовлетворяющих хотя бы одному из условий 1) d € € /1 П h, 2) d Е h и (d, сг) ф 1, 3) d € h и (d, cij ф 1

Алгоритм распознавания полноты представляет собой процедуру (назовем ее процедурой А), состоящую из следующих действий

1 Если ^ 0 при всех г — 1, ,т и j = 1, ,п, то выдать ответ „Нет"и завершить работу (в этом случае F С Ь+)

2 Для г = 1, ,т вычислить vt = NV(ft) А(агi, ,агп) Если все уг ф 1, то выдать ответ „Нет"и завершить работу (F С D)

3 Положить j — 1 и с\ = О

4 Для г = 1, ,ш, если NV(fl) = 1, то выполнить действия 4 1 применить \Л/НАТС(г, Cj, ¿j),

4 2 если j — 1, то положить j — 2, иначе применить

lNTERSECT(d,c2,Zi,J2)

5 Если с\ ф 1 или список 1\ не пуст, то выдать ответ „Нет"и завершить работу

6 Для г = 1, ,т положить А% — аго, Вг — oti + + ат — 1

7 Если А(ВЪ , Вт) ф 1, то выдать ответ „Нет"и завершать работу

8 Положить

«= Д (AtBj - А3Вг) (1)

9 Если и = 0, то выдать ответ „Нет"и завершить работу, иначе для 3 = 0,1, , и — 1 вычислять

Если d} ф 1 при некотором 3, то выдать ответ „Нет"и завершить работу 10 Выдать ответ „Да"и завершить работу

Теорема 4.10 2. Пусть все коэффициенты функций системы F ограничены по абсолютной величине константой t vt N = m + n + t Тогда процедура А представляет собой алгоритм с временной сложностью log2 N) Теорема 4.10 3. Пусть выполнены условия предыдущей теоремы Тогда емкостная сложность алгоритма А составляет 0(N2logN) бит

В пятой главе рассматривается функциональная система (L(Q), С), где £(<Q) - множество линейных полиномов с рациональными коэффициентами Определяется ряд замкнутых классов, в этих классах строятся бесконечные базисы, формулируется критерий относительной полноты, изучается алгоритмическая разрешимость некоторых вопросов, связанных с полнотой Результаты исследований сравниваются с работами В Ш Дарсалия и А Н Горбаня3, исследовавших произвольные полиномы с рационалными коэффициентами

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

Рассмотрим систему булевых функций {у3, j = 1, , m} от аргументов {хи г = 1, , п}

осуществляющую отображение щ {0,1}™ -» {0,1}т Будем интерпретировать значения функций как двоичные числа

т

,Хп), Хг,уг 6 {0, 1}

(1)

т

3ГЪрбань А Н Обобщенная агпрокскмадионная теорема* и точное представление многочленов от нескольких переменных суперпозициями многочленов от одного переменного // Известия вузов Математика — 1998 — № 5 — С 6-9

Будем также полагать, что функции системы (1) пространственно упорядочены в кортеж в соответствии с записью

fm(xi, ,Х„) * fm-l{xu ,Хп)* */l(®l, ,®п),

где * — разделительный знак Арифметическим полиномом назовем положительно определенную сумму вида

2"-1

Р(х 1, , Хп) - ZQ + ХгХЧ Хгк> г=0

в которой xiL хч — произвольный терм двоичных переменных из множества различающихся термов длины к (1 ^ к ^ п), zq,

Через Р' и L' в настоящей работе обозначаются множество арифметических полиномов и линейных арифметических полиномов соответственно Утверждение 6 2.1. Верно равенство [Р'] = P(Z) Рассмотрим далее множество ОР(Z) одночленов с целыми коэффициентами Коэффициентов таких многочленов на компьютере, как правило, представляются либо с помощью целочисленного типа данных, реализованного во всех современных языках программирования, либо с помощью специальных библиотек для работы с большими целыми числами Отметим, что даже если в одночлене Ахк коэффициент А представляет собой большое целое число, то вычислять значение этого одночлена на множестве {0,1} (область определения арифметических полиномов) можно достаточно быстро if (х==1) res=A, else res=0,

Поэтому при организации эффективных логических вычислений могут быть удобны представления арифметических полиномов с помощью суперпозиций над полными в Р{Ъ) системами, содержащими множество OP(Z)

Пример 1. При х, у £ {0,1} имеет место равенство х V у — х + у — ху Поскольку ху £ [{х + у — ху, -х, 0}] и х — у & [{ж т у, —ж}], то замыкание системы В = OP(Z) U {х 4- у — ху, х + у} содержит полную в Р{Z) систему {1, х ~ у, ху}, то есть система В полна в P(Z) Заменив в некотором арифметическом полиноме операции умножения по правилу ху = х-\-у—хУу, получим так называемую вторую арифметическую форму

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

Пример 2 (обобщение примера 1) Введем обозначение х $ у — а -г Ьх + Ьу + сху Рассмотрим систему (? — ОР{Щ и {х + у, х $у} При |с| > 1 или с= О, функция ху £ О и эта система не является полной в Ь{Щ

В диссертации показано, что система полная, а операция $ ассоциативна и коммутативна если выполнено одно из двух следующих условий 1 с = 1, а - Ь2 - 6, 2 с = -1, а = Ь - Ъ2

Условия полноты системы С и ассоциативности операции $ позволяют добиться следующих преимуществ систему С? можно использовать для представления любого арифметического полинома в памяти компьютера, при выводе полинома на экран операцию $ можно пропускать так же, как пропускают операцию умножения при привычной записи полиномов

При применении операции $ для хранения некоторых полиномов требуется меньше памяти, чем при использовании привычного способа представления полиномов Например, полином

1 + 2хз + Зжг + 4Ж2ЖЗ + + Ьх\хз + 7х\х^ + 8x1x2x3

при переходе к полной системе ОР(Щ и {х $у, %+у}, где х %у — х+у+ху, преобразуется к виду

1 - 4(х2 $ х3) - 2(хг $ х3) - 1(жх $ х2) + 8(2:1 $ ж2 $ х3)

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

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

4Власов А А , Мамаев Е И Расширенные арифметико-логические формы для реализации булевых функций // Труды науч конф по итогам научно-исследовательских работ Марийского государственного технического университета, Йошкар-Ола, 24-28 апр , 2000 Секи Информационные методы, технологии и системы - Йошкар-Ола 2С00- С 100-107 - Деп в ВИНИТИ 29 06 2000, № 3846-В2000

В Ш Дарсалия теорему не существует алгоритма, распознающего, образует ли произвольная конечная система функций из Р{Ж) вместе с множеством ОР(Z) полную в Р(Z) систему

Утверждение 6.3.1. Справедливо равенство [&} = L{Z) Рассмотрим далее множество OL{h) линейных одночленов с целыми коэффициентами Легко понять, что алгоритм, представляющий собой пункты 2-5,10 описанного во второй главе алгоритма, распознает, образует ли произвольная конечная система функций из L(Z) вместе с множеством ОЬ(Ъ) полную в L(Ъ) систему

Далее приведем интересный пример базиса в Ь(Щ Одним из препятствий практического использования арифметической логики в логическом проектировании и управлении является невозможность использования существующих методов для решения задач большой размерности Описание же арифметических полиномов и манипуляция с ними требует весовых коэффициентов астрономических величин даже для схем малой размерности Для представления линейных полиномов с такими коэффициентами можно предложить использовать специальные полные системы Например, если большая часть коэффициентов линейного арифметического полинома — числа кратные 4 (например, если функции Д, /2 из системы (1) равны нулю), то выгодно применять систему OL{Z) U {х + у, х + %}, используя для представления коэффициентов числа а^ Ъг такие, что коэффициент линейного полинома равен

{4аг, если Ьг = 1, а,, иначе

При этом для хранения каждого из коэффициентов не кратных четырем требуется на 1 бит больше (бит для хранения Ьг) чем при использовании традиционной схемы, напротив, для хранения каждого из коэффициентов кратных четырем требуется на 1 бит меньше Поэтому, если N - количество коэффициентов полинома, М — количество коэффициентов полинома не кратных 4, М « N, то при хранении полинома можно экономить N - 2 М бит

Рассмотренные выше теоретические построения были реализованы на языке программирования Ст+ в библиотеке для работы с логическими

функциями и арифметическими полиномами

Для улучшения качества и ускорения работ использовалась библиотека freelip для работы с большими целыми числами (разработчик А К Лен-стра, версия, найденная по адресу http //netsw org/system/libs/math/) и библиотека STL

Функции библиотеки для работы с логическими функциями и арифметическими полиномами размещаются в файле library срр, а их заголовки в файле library h Для использования библиотеки к проекту необходимо подключить эти файлы и файлы библиотеки А К Ленстра (hp срр, lip h, в папке с проектом также должен быть файл lippar h), в среде разработки должен также быть стандартный файл stdhb h Необходимо также чтобы в среде разработки были файлы библиотеки STL и ряд других довольно стандартных файлов, необходимых для подключения библиотеки А К Ленстра (например, windows h) Комментарии к описаниям функций библиотеки для работы с логическими функциями и арифметическими полиномами, в частности назначения параметров, как обычно, располагаются в файле library h

Разработан ряд приложений с пользовательским интерфейсом, использующих функции библиотеки, в частности приложение Liblll Его основная экранная форма показана на рис 1

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

Зададим систему булевых функций и преобразуем ее в соответствующий арифметический полином, используя клавишу „>>>> Преобразование булевых функций в арифметический полином >>>>" Затем, используя клавишу ,ДУ/ Представить АП, используя другую полную систему \\//", выбираем полную систему для представления арифметического полинома (например систему, состоящую из одночленов и функций х\ + Х2, x\Qx2 = —2 + 2х\ + 2х2 — xix%) и получаем искомый полином Подобным

; йя-^тм полином'' О лУогранне

Логические фучсции

Кйлниаствс функций в системе: [:* СГ6ВГ,ас тся Сйсимл еект ОрЯНМ ие ГИННОСТИ. оврв-

ивИНМК |5

Арифметический папиной

Функции грвд- . Галиной Ггредставпяетм вентерем сери=<кявффиций^г5д : Келиивс?вэ пере изнчьис пепннема. Коэффициента пол^моча

II" и 1« 1« ь

1 1С а 1! 0

¡б№ 1 р 0

? 1 0

1 0 С о

¡№Ю; I л ' ¡0 .Л... 1 ■А !! а

кйте а 1 ц ¡1 ¡0

¡ОШ V. . 1 ! 1 [1 1 1

[оКда I 1 0 ¡0

[о:.«! 1"- а .1 1 л

рГЩга \ 'а 0 1° И

отн 1 9 0

¡Ш1Х 5 ! 0 0 ;

Ш!» 1 1 л 5> ■в

ЛЯГ

<

М

I_I

И г! 1*1 анв1 [ладогащ»ни*к»<Г|-г7Е«).И>«-

|.'«. . ■ • ...

,..... .........................

С ¡57* •' ах2|*5225ГЛ|111Х!£|л(ЗД7Ьг1Э&ЭД 775и----

»<|Ьс51»«Я|>! (ЬаиЭ) 1 Б65И йЛОнЭалд-Т "Ю ИйОЛкМ^ИМ ГЬЯ «МО

Палиаадтт»« «1г«гоенЬ1 ■ ив -'.{.С- О

Рис. 1. Экранная форма приложения 1ЛЫИ.

образом выясняется, например, что полином

2 - х3 + 2х2 + 2x2^3 + хх + х\х3 + 4x1X2 + 421X2X3

можно представлять в более сжатом виде

2 - 2{х2их3) - 3(11^X3) + 4(х1{/а;2и'хз); где хчЬ'х^ - щ + х2 + Х1Х2.

Отметим, что если возможно считать Х1Е/Х2 с примерно той же скоростью, что и Х1.Г2, то второй способ представления этого полинома предпочтительнее. Заметим, что этот эксперимент требует совсем немного действий от пользователя приложения.

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

В седьмой главе диссертаций рассматриваются нейронные сети. Ка рис, 2, показана схема нейрона.

Я*ГЙЛ Аксон Выход нейрона м

•У

Рис 2 Искусственный нейрон

Состояние нейрона определяется по формуле

п

5 = ^ хгюи

г=1

где п — число входов нейрона, х, — значение г-го входа нейрона, — вес г-го синапса Затем определяется значение аксона нейрона по формуле У — /'(б'), где / - некоторая функция, которая называется активационной Тип коэффициентов 1иг зависит от реализации нейронной сети, и здесь возможны самые разные варианты, например, вещественные числа из отрезка [0,1], шестнадцатибитные целые числа Пусть и>г — целые числа, хг Е {0,1}, при нахождении значения первого и второго нейронов вычисляются соответственно суммы

п п

— Хгиг И £>2 = х%у% 1=1 2—1

Тогда можно эти суммы вычислять параллельно, используя способ организации вычислений, предложенный В Д Малюгиным

п

+ 51 = (24 + «,)

»=1

Если юг небольшие целые, то, используя вычисления со стандартными целочисленными типами данных (1оп§), можно параллельно вычислять

состояния нескольких нейронов. Если Щ - длинные целые, то параллельно вычислять состояния нескольких нейронов можно, используя библиотеки для работы с большими целыми числами. Случай, когда щ вещественные, Xi £ {0,1}. рассматривается аналогично.

Эти теоретические конструкции позволяют получить значительный выигрыш при решении ряда задач. Далее рассмотрим пример.

Есть конечное множество двуцветных изображений размером 5 х 5. На множестве этих изображений определена функция, принимающая значения из множества {00,01,10,11}. Требуется построить и обучить нейронную сеть, реализующую эту функцию.

Эту задачу можно решать, например, так. Будем реализовывать однослойную нейронную сеть, содержащую два нейрона с 25 входами и двумя выходами. Каждый из нейронов устроим следующим образом. Зададиы линейный полином с 25 коэффициентами а^ из множества {—16, —15, -14,... ,15,1б}:

5 г, 1-1

Б качестве нелинейности будем использовать пороговую функцию. Если линейный полином принимает положительное значение, то будем считать, что нейрон выдал значение 1. иначе 0. Работу иейросещ организуем следующим образом. Занумеруем два цвета цифрами 0 я 1. Если у ячейки {г,)} дает номер 0, то положим Хц = 0, иначе положим хц = 1. Далее произведём вычисления с помощью формальных нейронов.

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

Р И С □

Рис, 3. Латинские буквы-

Так, для распознавания значений 00, 01, 10, И, соответствующих изображениям букв А, В, С. Е (рис, 3), можно применять два полинома

Е Е а1 ХЧ = + 4ж12 - 12®13 - 12®14 - 8х15+ i=li=l

+3X21 - 5X22 - 11X23 + 6X24 + 16X25" -9Ж31 + 2х32 + 15жзз + 2х34 + 16х35-

—15®41 — 9^42 — 16^43 — 7^44 + 15X45+ +1х51 + 16^52 - 2х33 — 16х54 - 16х55, 5 5 .

е е агз хг} = -15жц + 1x12 — 15xi3 + lxu ~ 8X15-1=1,7=1

— 16X21 + 15х22 - 14X23 - 16X24 + 1^25+ +7x3i - 10X32 -1- Ожзз - 16х34 + 16x^5-

— 15X41 — 15X42 + 5X43 - 13X44 + 13x45+

+11х51 - 3x52 + 16X53 - 14X54 + 2x55

или один полином

Е Е a?ixv = -15368x11 + 1028xi2 - 15372x13 + Ю12х14 - 8200xi5-i=ii=i

-16381x21 + 15355X22 - 14347x23 - 16378х24 + Ю40х25+

+7159хз1 - 10238хз2 + 15х33 - 16382х34 + 16400х35--15375x41 - 15369x42 + 5104х43 - 13319x44 + 13327х45+ +11265x51 - 3056x52 + 16382х5з - 14352х54 + 2032х55,

где о® = a[f + 210а® при всех i,j е {1,2,3,4,5}

Отметим, что если у\%у2 и у% — результаты, подсчитанные с помощью первых двух и третьего полиномов, то знак числа у\ определяется девятью младшими разрядами числа t/3, а знак числа у2 определяется старшими разрядами числа j/з

В наших экспериментах мы использовали тип long (знаковое 32-х битное целое) и находили число у\ следующим образом у1=(уЗ«22)>>22

Согласно нашим экспериментам, на компьютере с процессором Intel(R) Pentium(R) 4 CPU 1 80GHz с помощью одного полинома результат получается за 250 не, а с помощью двух полиномов за 500 не

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

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

Например, если коэффициенты пороговой функции - целые числа и большинство коэффициентов кратно 4, то можно предложить вместо базиса {ж + у, 1} использовать базис {1, х + 4у} и т п

Если же коэффициенты полинома — рациональные числа, знаменатели которых не кратны некоторому простому числу р, то вместо базиса

со

{l.ar + j/.-sJuLk-},

i—i Рг

где pi, р2, Рг, , — простые числа, как обычно р\ = 2, рг — 3, рз — 5 и т д , можно использовать систему

оо

{l,x + y,-x}U (J {-}

Согласно нашим экспериментам, на компьютере с процессором Intel(R) Pentium(R) 4 CPU 1 80GHz выражение 400 X x считается за 8 не, а за 3 7 не считается выражение (25 X х) « 4, здесь << — операция сдвига вправо, то есть умножения числа на 23, соответственно верны равенства (25 х х) « 4 — (25 X х) х 23 = 400 х х Отметим, что эксперимент ставился следующим способом time_t sec, unsigned long f, x, sec=time(NULL),

for(x = 0, x < 3000000000, x = x + 1) { //f = 400 * x, f = (25 * x) « 4, > sec=time(NULL)-sec,

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

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

Вопрос, является ли набор линейных преобразований (линейных полиномов) достаточным для вычисления значений всех линейных полиномов, эквивалентен проблеме полноты в Ь(Ж)

ОСНОВНЫЕ РЕЗУЛЬТАТЫ

1 Исследованы функциональные системы линейных полиномов с целыми неотрицательными, целыми и рациональными коэффициентами и операцией суперпозиции и получены следующие теоретические результаты

1 1 Найдены критерии полноты в функциональных системах линейных полиномов с целыми и целыми неотрицательными коэффициентами

1 2 Построен алгоритм, распознающий полноту в функциональной системе линейных полиномов с целыми коэффициентами любой конечной системы функций

2 Исследована эффективность вычисления линейных полиномов при их представлении в различных базисах функциональных систем и получены следующие результаты

2 1 Найден базис, позволяющий эффективно вычислять значения полиномов, в которых большинство коэффициентов делятся на 4

2 2 Найдено семейство базисов с тремя параметрами, подбирая которые можно эффективно вычислять целочисленные полиномы

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

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

3 2 Предложен метод для представления линейных полиномов с большими коэффициентами, основанный на использовании полных систем

4 Созданные методы сравнивались с ранее известными результатами

в исследуемых областях

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

5 Разработана библиотека на языке программирования С++ для работы с логическими функциями и арифметическими полиномами, разработаны приложения Libiil и CompleteProj, использующие эту библиотеку Исходные тексты программ находятся в свободном доступе в сети Интернет Сайт http //www MamontovAI narod ru

основные Публикации

1 Мамонтов А.И Исследование структуры замкнутых классов в функциональной системе линейных полиномов с целыми неотрицательными коэффициентами / / Вестник МЭИ — 2006 —№6 — С 83-90.

2 Мамонтов А И Алгоритм распознавания полноты в алгебре линейных полиномов с целыми коэффициентами // Тез докл XII Между-нар науч -техн конф "Радиоэлектроника, электротехн и энергетика Т 1" - М Изд-во МЭИ - 2006 - С 371-372

3 Мамонтов А И Исследование структуры подалгебр в алгебрах полиномов с целыми коэффициентами // Научная сессия МИФН-2003 Сб научн трудов Т 13 - М МИФИ, Москва, 2003 - С 103-104

4 Мамонтов А И Исследование структуры подалгебр в алгебрах полиномов с целыми коэффициентами //' Тез докл IX Междунар науч -техн конф 'Радиоэлектроника, электротехн и энергетика Т 1" -М Изд-во МЭИ - 2003 - С 263-264

5 Мамонтов А И Критерий полноты в алгебре линейных полиномов с целыми коэффициентами // Тез докл X Междунар науч -техн конф "Радиоэлектроника, электротехн и энергетика Т 1" — М Изд-во МЭИ - 2004 - С 286-287

6 Мамонтов А И Некоторые возможные применения алгебр полиномов с целыми коэффициентами // Научная сессия МИФИ-2005 Сб научн трудов Т 14 - М МИФИ, Москва, 2005 - С 52-53

7 Мамонтов А И О возможном применении алгебр полиномов с целыми коэффициентами // Тез докл XI Междунар науч -техн конф. 'Радиоэлектроника, электротехн и энергетика Т 1" — М Изд-во МЭИ-2005-С 313-314

8 Мамонтов А И О максимальных подалгебрах алгебры линейных полиномов с рациональными коэффициентами // Тез докл XIII Междунар. науч -техн конф "Радиоэлектроника, электротехн и энергетика Т 1" - М Изд-во МЭИ - 2007 - С 343-345

9 Мамонтов А И О проблеме полноты в функциональной системе линейных полиномов с рациональными коэффициентами // Интеллектуальные системы и компьютерные науки Девятая Междунар конф Т 1 Часть 1 - М МехМат МГУ - 2005 - С 183

10 Мамонтов АИ, Мещанинов ДГ Проблема полноты в функциональной системе линейных полиномов с целыми коэффициентами // Труды VI Междунар конф "Дискретные модели в теории управляющих систем" (Москва, 7-11 декабря 2004 г) — М Изд отдел ф-та ВМиК МГУ, 2004, 50-52

Подписано в печать ^ >0> СЬ Зак. Тир. П.л.

Полиграфический центр МЭИ (ТУ)

Красноказарменная ул., д. 13

1 Введение

1.1 Предварительные замечания.

1.2 Линейные полиномы и параллельные вычисления.

1.3 О функциональных системах.

1.4 Некоторые прикладные вопросы.

1.5 Основные результаты

2 Необходимые определения

2.1 Проблема полноты в функциональных системах полиномов

3 Функциональная система линейных полиномов с целыми неотрицательными коэффициентами

3.1 Проблема полноты в классе Ь(Щ.

3.2 Класс L0(N).

3.3 Класс Li(N).

3.4 Класс L+(N)

3.5 Некоторые замечания о проблеме выразимости в классе L(N)

4 Функциональная система линейных полиномов с целыми коэффициентами

4.1 Классы F(k) и LF(k).

4.2 Классы L+ и F+(k)

4.3 Классы Lc+ и Ld~.

4.4 Классы С(т).

4.5 Классы S0(k) и Si(k).

4.6 Классы FS{k).

4.7 Класс D.

4.8 Классы U{a,b).

4.9 Критерий полноты.

4.10 Некоторые свойства базисов. Алгоритмическая разрешимость проблемы полноты.

5 Функциональная система линейных полиномов с рациональными коэффициентами

5.1 Класс O(Q).

5.2 Класс L+(Q)

5.3 Класс CP(Q).

5.4 Класс E(Q).

5.5 Классы Ua(Q).

5.6 Класс M(Q).

5.7 Критерий относительной полноты.

5.8 О глубине классов L(N) и Ь(Ъ) в L(Q).

5.9 О глубине класса L(Q) в P(Q).

5.10 Мощность некоторых множеств замкнутых классов в L(N), L(Z) и L(Q).

6 О реализации систем булевых функций арифметическими полиномами

6.1 Арифметические полиномы.

6.2 Связь и множества арифметических полиномов

6.3 Связь L(Z) и множества линейных арифметических полиномов

6.4 Библиотека для работы с логическими функциями и арифметическими полиномами.

7 Линейные полиномы и их применение в искусственных нейронных сетях.

7.1 Искусственный нейрон.

7.2 Предложения по распараллеливанию вычислений нейронной сети

7.3 Распараллеливание вычислений нейросети в задаче распознавания образов.

7.4 Дальнейшие результаты об особенностях распараллеливания вычислений нейронных сетей.

7.4.1 О хранении коэффициентов.

7.4.2 Об организации эффективных вычислений.

1.1. Предварительные замечания

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

В области организации эффективных вычислений и, в частности, в распараллеливании вычислений и программировании соответствующих алгоритмов сложился целый ряд научных школ. Отметим здесь школы Воеводиных, Кутепова, Малюгина [12, 52, 57]

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

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

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

В соответствии с целью исследования были поставлены следующие конкретные задачи:

1. Исследовать функциональные системы линейных полиномов.

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

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

4. Сравнить результаты применения составленных программ с существующими аналогами.

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

Практическая значимость работы.

Полученные методы хорошо проявили себя в вычислительной практике. Результаты исследований были внедрены в Московском энергетическом институте (техническом университете).

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

Апробация работы. Результаты работы докладывались и обсуждались на:

1. Научной сессии МИФИ, Москва, 2003, 2004, 2005;

2. Девятой, десятой, одиннадцатой, двенадцатой и тринадцатой международных научно-технических конференциях студентов и аспирантов „Радиоэлектроника, электротехника и энергетика", Москва, 2003, 2004, 2005, 2006, 2007;

3. Девятой международной конференции „Интеллектуальные системы и компьютерные науки", Москва, 2006;

4. Шестой и седьмой международных конференциях „Дискретные модели в теории управляющих систем", Москва, 2004, 2006;

5. Научном семинаре кафедры Математической кибернетики факультета ВМиК МГУ.

Заключение.

Итак, в работе получены следующие основные результаты.

1. Исследованы функциональные системы L(N), L{Z) и L(Q) линейных полиномов с целыми неотрицательными, целыми и рациональными коэффициентами и операцией суперпозиции и установлены следующие теоретические результаты.

1.1. Найдены полные системы в замкнутых классах L(N), L(Z), L(Q).

1.2. Установлены необходимые и достаточные условия полноты в каждой из систем L(N), L(Z), L(Q).

1.3. Построен алгоритм распознавания полноты в L(Z), оценена его сложность.

1.4. Найдены все возможные значения мощности базисов в этих функциональных ситемах.

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

2.1. Найден базис, позволяющий эффективно вычислять значения полиномов, в которых большинство коэффициентов делятся на 4.

2.2. Найдено семейство базисов с тремя параметрами, подбирая которые можно эффективно вычислять целочисленные полиномы.

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

2.4. Предложен метод для представления линейных полиномов с большими коэффициентами, основанный на использовании полных систем.

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

4. Создана программная библиотека для оперирования с арифметическими полиномами и решения названных технических задач.

5. Проведён вычислительный эксперимент, подтверждающий преимущества предложенных методов.

1. Алексеев В.Б., Вороненке А.А. О некоторых замкнутых классах в частичной двузначной логике // Дискретная математика.— 1994.— т. 6, №4,- С. 58-79.

2. Андреева О.В., Голунков Ю.В. Программно-замкнутые классы функций алгебры логики и предикатов // Кибернетика.— 1981.— №1.— С. 133.

3. Арутюнян Л.А. О мощности следов классов неоднородных функций // Дискретная математика.— 1993.— т. 5, №3.— С. 35-39.

4. Арутюнян J1.А. О решётке замкнутых классов неоднородных функций со следом типа С // Дискретная математика.— 1993.— т. 5, J№1.— С.130-145.

5. Бабин Д.Н. О разрешимости проблемы полноты для специальных систем автоматов // Дискретная математика.— 1996.— т. 8, №4.— С. 7991.

6. Бабин Д.Н. Разрешимый случай задачи о полноте автоматных функций // Дискретная математика.— 1992.— т. 4, №4.— С. 41-56.

7. Бабин Д.Н. Эффективная проверяемость полноты систем автоматных функций с полной булевой частью // Дискретная математика.— 2003.— т. 15, №1- С. 110-130.

8. Буевич В.А. О т-полноте в классе автоматных отображений // Доклады АН СССР.- 1980.- т. 252, № 5.- С. 708-712.

9. Буевич В.А. Условия Л-полноты для конечных автоматов.— М: Изд-во МГУ, Часть 1, 1986. Часть 2, 1987.

10. Ватолин Д., Ратушняк А., Смирнов М., Юкин В. Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео.— М: ДИАЛОГ-МИФИ, 2002.

11. Воеводин В.В., Воеводин Вл.В. Параллельные вычисления.— СПб: БХВ-Петербург, 2004.

12. Выхованец B.C., Малюгин В.Д. Мультипликативная алгебра и ее применение в логической обработке данных // Проблемы управления.— 2004.-№3.- С. 67-77.

13. Гаврилов Г. П. Вопросы выразимости и мощностной характеризации для дискретных функциональных систем с операцией суперпозиции: Дисс. докт. физ.-мат. наук.— М., 1997.

14. Гаврилов Г.П. Индуктивное представление булевых функций и конечная порождаемость классов Поста // Алгебра и логика.— 1984.— т. 23, №1- С. 3-26.

15. Гаврилов Г.П. О функциональной полноте в счётнозначной логике // Проблемы кибернетики.— 1965.— вып. 15.— С. 5-64.

16. Гаврилов Г.П. Функциональные системы дискретной математики,— М: Изд-во МГУ, 1985.

17. Глушков В.М., Цейтлин Г.Е., Ющенко E.JI. Алгебра. Языки. Программирование.— Киев: Наукова думка, 1978.

18. Голунков Ю.В. Аппроксимационная полнота в алгебрах частично рекурсивных функций и предикатов // Кибернетика.— 1987.— JVe. 6.— С.26-30.

19. Голунков Ю.В. К теории систем алгоритмических алгебр // Доклады АН СССР.- 1997.- т. 232, Ж 4.- С. 749-752.

20. Голунков Ю.В. О полноте операций в системах алгоритмических алгебр // В кн.: Алгоритмы и автоматы.— М: Изд-во Казанского ун-та, 1978.— С. 11-53.

21. Голунков Ю.В. Полнота по модулю идеала в функциональных системах программного типа // Дискретная математика.— 1990.— т. 2, Ж 2.— С. 112-120.

22. Голунков Ю.В. Полнота систем операций в операторных алгебрах, реализующих функции к-значной логики // Вероятностные методы и кибернетика 1980 - вып. 17 - С. 23-34.

23. Горбат А.Н. Обобщенная апрокеимационная теорема и точное представление многочленов от нескольких переменных суперпозициями многочленов от одного переменного // Известия вузов. Математика.— 1998 -№5 С. 6-9.

24. Дарсалия В.Ш. О базисах функциональных систем полиномов // Фундаментальная и прикладная математика.— 2001.— т. 7, №3.— С. 673682.

25. Дарсалия В.Ш. О мощностях множеств всех предполных классов в функциональных системах полиномов // Теоретические проблемы информатики и её приложения.— 1997.— № 1.— С. 35-44.

26. Дарсалия В.Ш. Об алгоритмической разрешимости свойства выразимости для полиномов // Фундаментальная и прикладная математика.— 1999.-т. 5, №3.- С. 931-935.

27. Дарсалия В.Ш. Относительная полнота для функциональных систем полиномов // Фундаментальная и прикладная математика — 2002.— т. 8, №4,- С. 967-977.

28. Дарсалия В.Ш. Проблема полноты для функциональных систем полиномов: Дисс. канд. физ.-мат. наук.— М., 1998.

29. Дарсалия В.Ш. Условия полноты для полиномов с натуральными, целыми и рациональными коэффициентами // Фундаментальная и прикладная математика.— 1996.— т. 2, №2.— С. 365-374.

30. Дзюжанъски П., Малюгин В., Шмерко В., Янушкевич С. Линейные модели схем на многозначных элементах // Автоматика и телемеханика 2002 - №6.- С.99-119.

31. Доу Ж. Вопросы полноты для конечно порождённых систем (P^fi) и {Pkj2,fi> // Дискретная математика — 1990 — т.2, №4 С. 116-124.

32. Доу Ж. Вопросы полноты для конечно порождённых ф.с. (Р^,^) и (Р№, 6) // Дискретная математика 1990 - т. 2, №3 - С. 128-136.

33. Дэвенпорт Г. Высшая арифметика. Введение в теорию чисел.— М: Наука, 1965.

34. Захарова Е.Ю., Кудрявцев В.В., Яблонский С.В. О предполных классах в Ахзначных логиках // Докл. АН СССР— 1969 — т. 186, №3 — С. 509-512.

35. Иорданский М.А. Структура и способы порождения замкнутых классов графов // Дискретная математика.— 2003.— т. 15, № 3.— С. 105-116.

36. Иорданский М.А. Функциональный подход к представлению графов // Доклады РАН.- 1997.- т. 353, №3.- С. 303-305.

37. Кнут Д.Э. Искусство программирования.— т. 2, Получисленные алгоритмы — М: Мир, 1976.

38. Коблиц Н. Курс теории чисел и криптографии.— 2001.— М.: Научное изд-во ТВП, 2001.

39. Коляда К.В. О полноте регулярных отображений // Проблемы кибернетики — 1984.— вып. 41 — С. 41-47.

40. Кратко М.И. Алгоритмическая неразрешимость проблемы распознавания полноты для конечных автоматов // Доклады АН СССР.— 1964.— т. 155, К0-1 — С. 35-37.

41. Крохин А.А., Сафин К.Л., Суханов Е.В. О строении решётки замкнутых классов полиномов // Дискретная математика.— 1997.— т. 9, № 2.— С. 24-39.

42. Кудрявцев В. Б. О мощностях множеств предполных классов некоторых функциональных систем, связанных с автоматами // Доклады АН СССР.- 1963.- т. 151, №3.- С. 493-496.

43. Кудрявцев В.Б. О функциональной системе // Доклады АН СССР.- 1973.- т. 210, №3.- С. 521-522.

44. Кудрявцев В.Б. О функциональной системе Ркд // Дискретная математика 1993 - т. 3, №3.- С. 124-134.

45. Кудрявцев В.Б. Относительно функциональной системы Ре // Журнал вычислительной математики и математической физики.— 1974.— т. 14, № 1.— С. 198-208.

46. Кудрявцев В.Б. Относительно функциональных систем // Проблемы кибернетики.— 1984.— вып. 41,— С. 5-40.

47. Кудрявцев В.Б. Функциональные системы.— М: Изд-во МГУ, 1982.

48. Кудрявцев В.В. О функциональной системе пучков логических функций // Фундаментальная и прикладная математика.— 1999.— т. 5, №1.- С. 149-192.

49. Кузнецов А. В. О проблемах тождества и функциональной полноты для алгебраических систем // Труды Третьего Всесоюзного матем. съезда.- М.: Изд-во АН СССР, 1956 т. 2, 145-146.

50. Кузнецов А.В. Структуры с замыканием и критерии функциональной полноты // Успехи математических наук.— 1961.— т. 16, вып. 2.— С. 201-202.

51. Кутепов В.П. Функциональные системы и параллельные вычисления: Дисс. докт. техн. наук.— М., 1981.

52. Летичевский А.А. Условия полноты для конечных автоматов // Журнал вычислительной математики и математической физики.— 1961.— №4.- С. 702-710.

53. Лисовик Л.П. Алгебры полилинейных преобразований над размеченными деревьями // Вычислительные системы.— 1988.— вып. 124.— С.114-143.

54. Ло Чжу Кай. Максимальные замкнутые классы в множестве частичных функций многозначной логики // Кибернетический сборник.— 1988.- вып. 25.- С. 131-141.

55. Ло Чжу Кай. Теория полноты для частичных функций многозначной логики // Кибернетический сборник.— 1988.— вып. 25.— С. 142-161.

56. Малюгин В.Д. Параллельные логические вычисления посредством арифметических полиномов.- М: ФИЗМАТЛИТ, 1997.

57. Мамонтов А.И. Алгоритм распознавания полноты в алгебре линейных полиномов с целыми коэффициентами // Тез. докл. XII Междунар.науч.-техн. конф. "Радиоэлектроника, электротехн. и энергетика. Т. 1." М: Изд-во МЭИ.- 2006.- С. 371-372.

58. Мамонтов А.И. Исследование структуры замкнутых классов в функциональной системе линейных полиномов с целыми неотрицательными коэффициентами // Вестник МЭИ 2006.—№6 — С. 83-90.

59. Мамонтов А.И. Исследование структуры подалгебр в алгебрах полиномов с целыми коэффициентами // Тез. докл. IX Междунар. науч.-техн. конф. "Радиоэлектроника, электротехн. и энергетика. Т. 1." — М: Изд-во МЭИ,- 2003.- С. 263-264.

60. Мамонтов А.И. Критерий полноты в алгебре линейных полиномов с целыми коэффициентами // Тез. докл. X Междунар. науч.-техн. конф. "Радиоэлектроника, электротехн. и энергетика. Т. 1." — М: Изд-во МЭИ.- 2004.- С. 286-287.

61. Мамонтов А.И. Некоторые возможные применения алгебр полиномов с целыми коэффициентами // Научная сессия МИФИ-2005. Сб. научн. трудов. Т. 14. М: МИФИ, Москва, 2005.- С. 52-53.

62. Мамонтов А.И. О проблеме полноты в функциональной системе линейных полиномов с рациональными коэффициентами // Интеллектуальные системы и компьютерные науки. Девятая Междунар. конф. Т. 1 Часть 1 М: МехМат МГУ.- 2005.- С. 183.

63. Марченков С.С. Замкнутые классы булевых функций.— М: ФИЗМАТ-ЛИТ, 2000.

64. Марченков С. С. К существованию конечных базисов в замкнутых классах булевых функций // Алгебра и логика.— 1984.— т. 23, № 1 — С. 8899.

65. Марченков С.С. 5-классификация функций многозначной логики // Дискретная математика,— 1997.— т. 9, №3.— С. 125-152.

66. Марченков С. С. 5-классификация функций трёхзначной логики.— М: ФИЗМАТЛИТ, 2001.

67. Марченков С. С. О предполных классах в декартовых произведениях Р2 и Р3 // Дискретная математика — 1994 — т. 6, №2 — С. 21-42.

68. Марченков С.С. О предполных классах Слупецкого в системах х х . х xPi // Дискретная математика 1992 — т. 4, № 3 — С. 135-148.

69. Марченков С. С. Предполнота замкнутых классов в Рк: предикатный подход // Математические вопросы кибернетики.— 1996.— вып.6.— С. 117-132.

70. Марченков С.С., Угольников А.Б. Замкнутые классы булевых функций.- М: Изд-во ИПМ АН СССР, 1990.

71. Мещанинов Д.Г. О первых с?-разностях функций &-значной логики // Математические вопросы кибернетики.— 1998 — вып. 6 — С. 265-280.

72. Мещанинов Д.Г. О замкнутых классах к-значных функций, сохраняющих первые d-разности // Математические вопросы кибернетики.— 1999,- вып. 8.- С. 219-230.

73. Перфильева И.Г. Построение гиперконтинуального семейства предполных классов счётнозначной логики // Проблемы кибернетики.— 1979.— т. 35.- С. 29-44.

74. Ромов Б.А. О максимальных подалгебрах алгебры частичных функций многозначной логики // Кибернетика.— 1980.— № 1.— С. 28-36.

75. Ромов Б.А. О полноте на квадрате функций алгебры логики и в системе Рк х Pi // Кибернетика 1987 - №4.- С. 9-14.

76. Ромов Б.А. Об одной серии максимальных подалгебр прямых произведений алгебр конечнозначных логик // Кибернетика.— 1987.— №3.—1. С. 11-16.

77. Семигродских А.П. Решётки замкнутых классов функций на бесконечном множестве: Дисс. канд. физ.-мат. наук.— Екатеринбург., 2003.

78. Тайманов В.А. О декартовых степенях Р2 // Доклады АН СССР.— 1983.- т. 270, № 6,- С. 1327-1330.

79. Тайманов В.А. О функциональных системах А;-значной логики с операциями программного типа // Доклады АН СССР.— 1983.— т. 268, №6.- С. 1307-1310.

80. Тарасова О. С. Классы fc-значной логики, замкнутые относительно расширенной операции суперпозиции // Вестник МГУ, Сер. 1: Математика. Механика 2001 - №6 - С. 54-57.

81. Угольников А.Б. О замкнутых классах Поста // Известия вузов. Математика,- 1998,- №7,- С. 79-88.

82. Финько О.А. Реализация систем булевых функций большой размерности методами модулярной арифметики // Автоматика и телемеханика,- 2004.- № 6 С. 37-60.

83. Фрейвалд Р.В. Критерий полноты для частичных функций алгебры логики и многозначной логики // Доклады АН СССР,— 1966,— т. 167, №6.- С. 1249-1250.

84. Фрейвалд Р.В. Функциональная полнота для не всюду определённых функций алгебры логики // Дискретный анализ,— 1966.— № 8.— С. 5568.

85. Хинчин А.Я. Три жемчужины теории чисел.— М: Наука, 1979.

86. Часовских А.А. Об алгоритмической разрешимости проблемы для линейных автоматов // Вестник МГУ, Сер. 1: Математика. Механика,— 1985 -№3- С.82-84.

87. Шмерко В.П. Теоремы Малюгина: новое понимание в логическом управлении, проектировании СБИС и структурах данных для новых технологий // Автоматика и телемеханика.— 2004.— № 6.— С. 61-83.

88. Яблонский С.В. Введение в дискретную математику.— М: Наука, 1979.

89. Яблонский С. В. Вопросы функциональной полноты в Ахзначном исчислении: Дисс. канд. физ.-мат. наук.— М., 1953.

90. Яблонский С. В. О функциональной полноте в трёхзначном исчислении // Доклады АН СССР.- 1954.- т. 92, Ж 6.- С. 1153-1156.

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

92. Яблонский С.В., Гаврилов Г.П., Кудрявцев В.Б. Функции алгебры логики и классы Поста.— М: Наука, 1966.

93. Яблонский С.В., Гаврилов Г.П., Набебин А. А. Анализ и синтез схем в многозначных логиках, ч. I,— М: Изд-во МЭИ, 1989.

94. Яблонский С.В., Гаврилов Г.П., Набебин А.А. Предполные классы в многозначных логиках,— М: Изд-во МЭИ, 1997.

95. Янов Ю.И., Мучник А.А. О существовании &-значных замкнутых классов, не имеющих конечного базиса // Доклады АН СССР.— 1959.— т. 127, №1.— С. 44-46.

96. Post E.L. Introduction to a general theory of elementary propositions // Amer. J. Math.- 1921.- т. 43, №3.- С. 163-185.

97. Post E.L. The two-valued iterative systems of mathematical logic // Annals of Math. Studies, v. 5.— Princeton-London: Princeton Univ. Press, 1941.

98. Rosenberg I.G. La structure des fonctions de plusieurs variables sur un ensembe fini // Computes Rendus de l'Acad. Sci. Paris.— 1965.— т. 260 — С. 3817-3819.

99. Rosenberg I.G. Uber die funktionale Vollstandigkeit in den mehrvertigen Logiken // Rospravy Ceskoslovenske Academie ved. Rada matematickych a prirodnich ved.- 1970 т. 80, №4,- С. 3-39.

100. Slupecki J. Kryterium pelnosci wielowar-tosciowych systemow logiki zdari // Comptes Rendus des Seances de la Societe des Sciences et de Lettres de Varsovie, cl. III.- 1939 т. 32.- С. 102-109.