О представлении арифметических функций в системе обратимых преобразований абстрактного регистра
Рассматривается подход к построению доопределений частично определенных арифметических функций в системе обратимых преобразований и их классов на абстрактном регистре. Определяются условия замыкания классов и возможность их представления в системе квантовых вычислений. Розглядається підхід до побудо...
Saved in:
| Published in: | Математичні машини і системи |
|---|---|
| Date: | 2011 |
| Main Authors: | , |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут проблем математичних машин і систем НАН України
2011
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/83392 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | О представлении арифметических функций в системе обратимых преобразований абстрактного регистра / А.К. Беляев, В.П. Клименко // Мат. машини і системи. — 2011. — № 1. — С. 3-8. — Бібліогр.: 8 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859988766199906304 |
|---|---|
| author | Беляев, А.К. Клименко, В.П. |
| author_facet | Беляев, А.К. Клименко, В.П. |
| citation_txt | О представлении арифметических функций в системе обратимых преобразований абстрактного регистра / А.К. Беляев, В.П. Клименко // Мат. машини і системи. — 2011. — № 1. — С. 3-8. — Бібліогр.: 8 назв. — рос. |
| collection | DSpace DC |
| container_title | Математичні машини і системи |
| description | Рассматривается подход к построению доопределений частично определенных арифметических функций в системе обратимых преобразований и их классов на абстрактном регистре. Определяются условия замыкания классов и возможность их представления в системе квантовых вычислений.
Розглядається підхід до побудови довизначень частково визначених арифметичних функцій у системі обернених перетворень та їх класів на абстрактному регістрі. Визначаються умови замикання класів і можливість їх представлення в системі квантових обчислень
The article studies approach to building extensions of partially defined arithmetic functions within the system of reversible transformations and their classes on the abstract register. The conditions for class closures and possibilities of their representation in the system of quantum calculations are defined.
|
| first_indexed | 2025-12-07T16:30:21Z |
| format | Article |
| fulltext |
© Беляев А.К., Клименко В.П., 2011 3
ISSN 1028-9763. Математичні машини і системи, 2011, № 1
ОБЧИСЛЮВАЛЬНІ СИСТЕМИ
УДК 511.1, 512.542, 530.145
А.К. БЕЛЯЕВ, В.П. КЛИМЕНКО
О ПРЕДСТАВЛЕНИИ АРИФМЕТИЧЕСКИХ ФУНКЦИЙ В СИСТЕМЕ
ОБРАТИМЫХ ПРЕОБРАЗОВАНИЙ АБСТРАКТНОГО РЕГИСТРА
Анотація. Розглядається підхід до побудови довизначень частково визначених арифметичних
функцій у системі обернених перетворень та їх класів на абстрактному регістрі. Визначаються
умови замикання класів і можливість їх представлення в системі квантових обчислень.
Ключові слова: абстрактний реєстр, композиція арифметичних функцій, квантова модель обчис-
лень.
Аннотация. Рассматривается подход к построению доопределений частично определенных
арифметических функций в системе обратимых преобразований и их классов на абстрактном ре-
гистре. Определяются условия замыкания классов и возможность их представления в системе
квантовых вычислений.
Ключевые слова: абстрактный регистр, композиция арифметических функций, квантовая модель
вычислений.
Abstract. The article studies approach to building extensions of partially defined arithmetic functions
within the system of reversible transformations and their classes on the abstract register. The conditions
for class closures and possibilities of their representation in the system of quantum calculations are de-
fined.
Key words: abstract register, the composition of arithmetic functions, quantum computation model.
1. Введение
Развитие современных технологий в области создания вычислительных средств, например,
нанотехнологий, квантовых вычислений, приводит к появлению новых требований к орга-
низации вычислений, а также к представлению преобразований, описывающих возможно-
сти таких технологий.
Так, один из основных вопросов в описании и моделировании квантовых вычисле-
ний [1] проявляется в необходимости представления вычислений в системе обратимых
преобразований, в том числе представления арифметических функций, лежащих в основе
вычислений.
Для описания арифметических преобразований и функций в области дискретных
преобразований в [2] предложена система периодически определенных преобразований,
абстрактного бесконечного регистра.
Абстрактный регистр представляется некоторой универсальной моделью для опи-
сания вычислений [2, 3]. Представление арифметических функций в системе периодически
определенных преобразований дает возможность их структурного описания для реализа-
ции арифметических функций и служит основой постановки и решения задач оптимизации
вычислений [2].
Практическая реализация описанной системы преобразований связана с областью
приложений, а также с возможностью введения необходимых ограничений в представле-
ние преобразований на конечных множествах состояний ввиду ограничений разрядности
абстрактного регистра.
4 ISSN 1028-9763. Математичні машини і системи, 2011, № 1
Ограничение разрядности, как правило, ведет к нарушению регулярности в описа-
нии арифметических функций из-за их частичного определения на конечных множествах
состояний.
С задачей доопределения частично определенных арифметических функций связы-
вается построение системы обратимых арифметических вычислений на конечных множе-
ствах состояний и для описания квантовых вычислений.
Поэтому построение классов обратимых арифметических функций и их представ-
ление в системе преобразований n -разрядного абстрактного регистра представляется ак-
туальным.
В работе разрабатывается подход для построения таких доопределений.
2. Постановка задачи
Для обоснования подхода к построению описанных классов и проведения анализа доопре-
делений частично определенных арифметических функций на конечном множестве со-
стояний будем рассматривать некоторый набор известных элементарных арифметических
функций. Эти функции могут быть представлены в классе периодически определенных
преобразований бесконечного абстрактного двоичного регистра и иметь структурные опи-
сания на конечном абстрактном регистре. Обозначим функции набора через dcba ,,, ,
где a – перечисление состояний абстрактного регистра;
b – циклический сдвиг (влево) кодов состояний абстрактного регистра;
c – арифметическое умножение кодов состояний на число три;
d – вычисление суммы натурального ряда чисел ∑
=
x
i
i
1
, где x – текущее состояние аб-
страктного регистра.
Описание функций ba, в классе периодически определенных преобразований рас-
сматривается в [2].
Функции dc, описываются в составе технических устройств [4, 5]. В этих устрой-
ствах исходные состояния n -разрядных двоичных регистров преобразуются в значения
результатов вычисления заданных функций. Регулярность структурного описания арифме-
тических функций соответствует определению класса периодически определенных преоб-
разований и образуется в результате периодического повторения логических функций пе-
реключения состояний разрядов регистров. Логические функции определяются базовыми
уравнениями периодически определенных преобразований [2].
Структурные описания функций cba ,, непосредственно определяются базовыми
уравнениями абстрактного регистра, тогда как описание функции d представляется ком-
позицией преобразований и образует сложное структурное описание преобразований в
классе периодически определенных преобразований.
Ограничение разрядности бесконечного абстрактного регистра, а также выполнение
условий обратимости преобразований на конечном регистре, переводит рассмотрение опи-
санных выше преобразований из класса частично определенных в некоторый класс (час-
тично) доопределенных преобразований конечного n -разрядного абстрактного двоичного
регистра. Этот класс может быть описан в конечной симметрической группе G .
Действительно, пусть P – множество состояний конечного n-разрядного двоичного
абстрактного регистра, где }1,...,2,1,0{ −= mP , а nm 2= . В системе обратимых преобразо-
ваний на множестве P определим систему перестановок элементов симметрической груп-
пы G порядка !m . Перестановками состояний будем представлять предложенный набор
арифметических функций.
ISSN 1028-9763. Математичні машини і системи, 2011, № 1 5
Возможным способом частичного доопределения арифметических функций (опи-
санных выше) на конечных множествах состояний является представление функций в сис-
теме остаточных классов по n2mod . Тогда наборы функций в виде перестановок степени
m для случая 3=n представляются в виде
=
07654321
76543210
a ,
=
75316420
76543210
b ,
=
52741630
76543210
c ,
=
45726310
76543210
d .
Функция a – циклическая перестановка степени m .
Функция b может рассматриваться в виде некоторой частично доопределенной
функции, хотя эта функция не определяется в системе остаточных классов по nm 2= .
Функции c – инволютивное преобразование для 3=n .
Функция d – представляется циклической перестановкой степени )2( −m .
Функциональный анализ представленных функций и их композиций показывает,
что пара частично доопределенных функций },{ da является образующими симметриче-
ской группы G . Симметрическая группа G , однако, содержит множество произвольных
транспозиций.
Преобразования, реализующие множество произвольных транспозиций, не описы-
ваются в системе периодически определенных преобразований и не образуют регулярного
структурного описания на абстрактном бесконечном регистре в соответствии с определе-
ниями [2].
Поэтому система обратимых арифметических функций, определенная на конечных
множествах состояний n -разрядного двоичного абстрактного регистра и построенная на
основе непосредственного вычисления значений функций в системе остаточных классов,
не приводит к сужению класса частично доопределенных арифметических функций, а
также не позволяет определить условия логического замыкания классов этих функций.
Аналогичные построения могут быть проведены и для пары частично доопределен-
ных функций },{ ba , для которых нарушение структурной регулярности в результате ком-
позиции функций в этом случае непосредственно связывается с выбором исходной систе-
мы образующих функций, определенных на конечном абстрактном регистре. Функция b
не образует замыкание класса частично доопределенных арифметических функций.
Для построения класса частично доопределенных арифметических фунций и выяс-
нения условий логического замыкания класса определим ограничения в области частично-
го доопределения функций и проведем некоторые пребразования функций предложенного
набора.
3. Построение класса частично доопределенных арифметических функций
Представим символы состояний области определения частично доопределенных функций
в виде соответствия символов двух множеств: )}1
2
(,...,1,0{ −= m
A и
)}1(,...,)1
2
(,
2
{ −+= m
mm
B для четных m . Назовем множество B зеркальной частью об-
ласти определения частично доопределенных функций. Тогда разность соответствующих
пар символов, очевидно, равна
2
m
, где
2
m
ba ii =− , а Aai ∈ , а Bbi ∈ , и }
2
,...,1,0{
m
i = . Оп-
ределим условие соответствия пар символов для значений функций путем вычисления мо-
дуля разности соответствующих значений частично доопределенных функций в виде
6 ISSN 1028-9763. Математичні машини і системи, 2011, № 1
2
)()(
m
bfaf ii =− . (1)
Условие (1) выделяет некоторый замкнутый подкласс частично доопределенных
преобразований симметрической группе G . Обозначим этот класс функций через U . Рас-
смотрим примеры представления арифметических функций класса U на основе преобра-
зования функций набора dcba ,,, .
Определим функцию a для nm 2= и 3=n . Элементам значения функции a на
множестве }4,3,2,1{=A ставятся в соответствие значения функций на множестве
}0,7,6,5{=B . Модуль разности пар на множестве значений функции равен 4. То есть,
функция a – элемент класса U .
Аналогично для функции c при nm 2= и 3=n . Здесь множеству значений функции
на множестве }1,6,3,0{=A соответствуют значения на множестве }5,2,7,4{=B . Модуль
разности пар на множестве значений функции равен 4. Таким образом, c – элемент класса
U .
Рассмотрим функцию d . Анализ значений функции d в области определенияB
показывает, что функция d может быть представлена в классе U путем зеркального пре-
образования области значений функции, определенной на B . Это отличительное свойство
функции d , определенной в системе остаточных классов по модулю nm 2= .
Назовем эту операцию «погружением» функции d в класс U . Для nm 2= и 3=n
«погружение» может быть образовано путем умножения функции d слева на некоторый
элемент
=
45673210
76543210
r группы G . Обозначим преобразованную функцию через 'd .
Тогда для nm 2= и 3=n значение функции принимает вид
=
27546310
76543210
'd , соответст-
вующие разности }6,3,1,0{ и }2,7,5,4{ равны 4. Функция 'd – циклическая перестановка
степени )4( −m . Это функция класса U .
Функция b также «погружается» в класс U путем преобразования зеркальной час-
ти в области значений B . В этом случае операция «погружения» представляется транс-
формацией значений функции в области B элементом r группы G . Обозначим преобра-
зованную функцию через 'b . Тогда для случая nm 2= и 3=n функция принимает вид
=
13645720
76543210
'b , соответствующие разности }5,7,2,0{ и }1,3,6,4{ равны 4.
В системе образующих }',{ da преобразование 'b для случая nm 2= и 3=n пред-
ставляется разложением 322 )'()'(' adaadb = , а функция c , соответственно, разложением
adadc 32 )'('= . Результаты разложения могут быть получены в соответствии с методикой,
рассмотренной в [6].
Нужно отметить, что в системе образующих }',{ da также представляются функции
умножения на нечетные числа, представленные в системе остаточных классах по nm 2= .
Анализ условия (1) – образование элементов класса U показывает, что система об-
разующих класса U может также определяться элементами: функцией a и парой транспо-
зиций вида U
mm
mm ∈−−−− })2
2
,1
2
(),1,2({ , удовлетворяющих условию (1). В этом на-
боре образуется более широкий класс функций.
ISSN 1028-9763. Математичні машини і системи, 2011, № 1 7
В такой системе образующих порядок элементов класса U равен !
2
2 2 m
N
m
⋅= – т.е.,
произведению четных чисел натурального ряда mN ⋅⋅⋅⋅= ...642 , где m – четная степень
элемента группы G . Описанный набор функций образует замыкание класса U .
Назовем образованный таким образом класс функций центрально симметрическим
классом (ЦС классом) преобразований группы G .
Исходный набор преобразованных функций ',,', dcba представляется в классе ЦС.
Система образующих элементов }',{ da образует группу преобразований порядка
2' NN = , т.е. является подгруппой класса ЦС.
Особенностью элементов класса ЦС является наличие центральных элементов,
представленных множеством одиночных транспозиций вида ),1
2
,1({ −− m
m
})
2
,0(,...),2
2
,2(
mm
m −− . Центральные элементы коммутативны и образуют коммутатив-
ную подгруппу класса ЦС. Симметрия центральных элементов позволяет рассматривать
эти элементы в качестве элементов класса арифметических функций в системе частично
доопределенных функций.
Частично доопределенные функции умножения на числа два и три могут рассмат-
риваться в качестве системы образующих циклических подгрупп (порядков 2−m , 4−m )
произведений четных и нечетных чисел на элементы натурального ряда чисел. Так, для
случая 4=n образующие могут быть представлены в виде
=
BDFACE
ABCDEF
e
9024613578
0123456789
,
=
FDBECA
ABCDEF
f
4217803695
0123456789
,
где функции fe, – элементы класса U . Порядок подгруппы произведений чисел – 12.
В компактном виде образующие представляются таблицей разложений в циклах,
соответственно – длины 4 для умножения на три (по горизонтали) и длины 3 для умноже-
ния на два ( по вертикали ). Таблица разложений имеет вид
DC
EA
B
54
62
931
.
В таблице отмечена область доопределения функций умножения на числа два и три,
а также представлены результаты умножений.
Предлагаемый в работе подход представления частично доопределенных арифме-
тических функций в системе обратимых преобразований абстрактного регистра дает воз-
можность построения преобразований, локализованных в разрядах [6] абстрактного реги-
стра для определения базовых уравнений арифметических преобразований и дальнейшей
оптимизации вычислений [7].
В системе квантовых вычислений арифметические функции могут представляться
частично доопределенными обратимыми преобразованиями состояний p -позиционного
абстрактного регистра на основе микроопераций квантовой системы вычислений [3].
4. Выводы
1. Частично доопределенные обратимые арифметические функции представляются в клас-
се центрально симметрических преобразований симметрической группы G .
8 ISSN 1028-9763. Математичні машини і системи, 2011, № 1
2. Система центрально симметрических преобразований образует замыкание класса час-
тично доопределенных обратимых арифметических функций.
СПИСОК ЛИТЕРАТУРЫ
1. Нильсен М. Квантовые вычисления и квантовая информация / М. Нильсен. – М.: Мир, 2006. –
823 с.
2. Глушков В.М. Кибернетика, вычислительная техника, информатика: избр. труды в 3-х т. / Глуш-
ков В.М. – Киев: Наукова думка, 1990. – Т. 1. – С. 179 – 191.
3. Беляев А.К. Анализ модели квантовых вычислений / А.К. Беляев, В.П. Клименко // Математичні
машини і системи. – 2009. – № 2. – С. 45 – 52.
4. А. с. 744570 СССР, МКИ G06F7/52. Устройство умножения на три / А.К. Беляев, Г.И. Корниен-
ко, В.В. Ткаченко. – Опубл. 30.06.80, Бюл. № 4.
5. А.с. 947855 СССР, МКИ G06F7/552. Устройство для вычисления функции∑
=
x
i
i
1
/ А.К. Беляев,
Г.И. Корниенко, В.В. Ткаченко. – Опубл. 30.07.82, Бюл. № 28.
6. Беляев А.К. Базовая система микроопераций и ее применение / А.К. Беляев // Кибернетика. –
1972. – № 2. – С. 71 – 76.
7. Бєляєв А.К. Критерії оптимізації обчислень на абстрактному регістрі / А.К. Бєляєв, І.А. Климен-
ко // Вісник Національного технічного університету України «КПІ». Інформатика управління та
обчислювальна техніка. – 2004. – № 41. – С. 61 – 66.
8. Холл М. Теория групп / Холл М. – М.: Иностр. лит., 1962. – 468 с.
Стаття надійшла до редакції 19.01.2011
|
| id | nasplib_isofts_kiev_ua-123456789-83392 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1028-9763 |
| language | Russian |
| last_indexed | 2025-12-07T16:30:21Z |
| publishDate | 2011 |
| publisher | Інститут проблем математичних машин і систем НАН України |
| record_format | dspace |
| spelling | Беляев, А.К. Клименко, В.П. 2015-06-19T11:51:11Z 2015-06-19T11:51:11Z 2011 О представлении арифметических функций в системе обратимых преобразований абстрактного регистра / А.К. Беляев, В.П. Клименко // Мат. машини і системи. — 2011. — № 1. — С. 3-8. — Бібліогр.: 8 назв. — рос. 1028-9763 https://nasplib.isofts.kiev.ua/handle/123456789/83392 511.1, 512.542, 530.145 Рассматривается подход к построению доопределений частично определенных арифметических функций в системе обратимых преобразований и их классов на абстрактном регистре. Определяются условия замыкания классов и возможность их представления в системе квантовых вычислений. Розглядається підхід до побудови довизначень частково визначених арифметичних функцій у системі обернених перетворень та їх класів на абстрактному регістрі. Визначаються умови замикання класів і можливість їх представлення в системі квантових обчислень The article studies approach to building extensions of partially defined arithmetic functions within the system of reversible transformations and their classes on the abstract register. The conditions for class closures and possibilities of their representation in the system of quantum calculations are defined. ru Інститут проблем математичних машин і систем НАН України Математичні машини і системи Обчислювальні системи О представлении арифметических функций в системе обратимых преобразований абстрактного регистра Про представлення арифметичних функцій у системі обернених перетворень абстрактного регістру On presentation of arithmetic functions within the system of abstract register reversible transformations Article published earlier |
| spellingShingle | О представлении арифметических функций в системе обратимых преобразований абстрактного регистра Беляев, А.К. Клименко, В.П. Обчислювальні системи |
| title | О представлении арифметических функций в системе обратимых преобразований абстрактного регистра |
| title_alt | Про представлення арифметичних функцій у системі обернених перетворень абстрактного регістру On presentation of arithmetic functions within the system of abstract register reversible transformations |
| title_full | О представлении арифметических функций в системе обратимых преобразований абстрактного регистра |
| title_fullStr | О представлении арифметических функций в системе обратимых преобразований абстрактного регистра |
| title_full_unstemmed | О представлении арифметических функций в системе обратимых преобразований абстрактного регистра |
| title_short | О представлении арифметических функций в системе обратимых преобразований абстрактного регистра |
| title_sort | о представлении арифметических функций в системе обратимых преобразований абстрактного регистра |
| topic | Обчислювальні системи |
| topic_facet | Обчислювальні системи |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/83392 |
| work_keys_str_mv | AT belâevak opredstavleniiarifmetičeskihfunkciivsistemeobratimyhpreobrazovaniiabstraktnogoregistra AT klimenkovp opredstavleniiarifmetičeskihfunkciivsistemeobratimyhpreobrazovaniiabstraktnogoregistra AT belâevak propredstavlennâarifmetičnihfunkcíiusistemíobernenihperetvorenʹabstraktnogoregístru AT klimenkovp propredstavlennâarifmetičnihfunkcíiusistemíobernenihperetvorenʹabstraktnogoregístru AT belâevak onpresentationofarithmeticfunctionswithinthesystemofabstractregisterreversibletransformations AT klimenkovp onpresentationofarithmeticfunctionswithinthesystemofabstractregisterreversibletransformations |