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

Перейти к навигации Перейти к поиску
нет описания правки
Нет описания правки
Нет описания правки
 
Строка 1: Строка 1:
'''Замкнутое полукольцо''' (''[[Closed semiring]]'') - полукольцо <math>S</math> с двумя дополнительными свойствами: (а) если <math>a_{1}, a_{2}, \ldots, a_{n}, \ldots</math> есть счетная
'''Замкнутое полукольцо''' (''[[Closed semiring]]'') полукольцо <math>S</math> с двумя дополнительными свойствами: (а) если <math>a_{1}, a_{2}, \ldots, a_{n}, \ldots</math> есть счетная
последовательность элементов <math>S</math>, то существует и является единственной сумма  
последовательность элементов <math>S</math>, то существует и является единственной сумма  


<math>a_{1} + a_{2} + \ldots + a_{n} + \ldots,</math>  
:::::<math>a_{1} + a_{2} + \ldots + a_{n} + \ldots,</math>  


причем порядок, в котором производится сложение различных элементов, несуществен; (б) операция умножения "<math>\cdot</math>" дистрибутивна относительно конечных и счетно-бесконечных сумм. На замкнутых полукольцах может быть определена унарная операция, называемая замыканием. Пусть
причем порядок, в котором производится сложение различных элементов, несуществен; (б) операция умножения "<math>\cdot</math>" дистрибутивна относительно конечных и счетно-бесконечных сумм. На замкнутых полукольцах может быть определена унарная операция, называемая замыканием. Пусть
<math>a</math> --- некоторый элемент из <math>S</math>; тогда степени <math>a</math> могут
<math>a</math> некоторый элемент из <math>S</math>; тогда степени <math>a</math> могут
быть определены следующим образом:  
быть определены следующим образом:  


<math>a^{0} = 1;</math>  
:::::::<math>a^{0} = 1;</math>  


<math>a^{n} =
:::::<math>a^{n} =
a \cdot a^{n-1}\mbox{ для всех } n > 0.</math>  
a \cdot a^{n-1}\mbox{ для всех } n > 0.</math>  


Строка 16: Строка 16:
<math>a^{\ast}</math> можно определить как  
<math>a^{\ast}</math> можно определить как  


<math>a^{\ast} = 1 + a + a^{2} +
:::::<math>a^{\ast} = 1 + a + a^{2} +
\ldots + a^{n} + \ldots.</math>  
\ldots + a^{n} + \ldots.</math>  


Строка 22: Строка 22:
что  
что  


<math>a^{\ast} = 1 + a \cdot a^{\ast}.</math>
:::::<math>a^{\ast} = 1 + a \cdot a^{\ast}.</math>


Замкнутые полукольца находят применения в различных областях вычислительной техники: в теории автоматов, теории грамматик, теории рекурсии и неподвижных точек, последовательных машинах, матричной обработке, а также в решении различных задач теории графов, например при разработке алгоритмов нахождения [[кратчайший путь|кратчайших путей]], транзитивного замыкания и др.
Замкнутые полукольца находят применения в различных областях вычислительной техники: в теории автоматов, теории грамматик, теории рекурсии и неподвижных точек, последовательных машинах, матричной обработке, а также в решении различных задач теории графов, например при разработке [[алгоритм|алгоритмов]] нахождения [[кратчайший путь|кратчайших путей]], транзитивного замыкания и др.
==Литература==
==Литература==
[Словарь],  
* Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. —  М.: Мир, 1979.


[Ахо-Хопкрофт-Ульман]
* Толковый словарь по вычислительным системам. — М.: Машиностроение, 1991.

Навигация