Замкнутое полукольцо: различия между версиями
KEV (обсуждение | вклад) Нет описания правки |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Замкнутое полукольцо''' (''[[Closed semiring]]'') | '''Замкнутое полукольцо''' (''[[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>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. | |||
Текущая версия от 15:26, 18 февраля 2011
Замкнутое полукольцо (Closed semiring) — полукольцо [math]\displaystyle{ S }[/math] с двумя дополнительными свойствами: (а) если [math]\displaystyle{ a_{1}, a_{2}, \ldots, a_{n}, \ldots }[/math] есть счетная последовательность элементов [math]\displaystyle{ S }[/math], то существует и является единственной сумма
- [math]\displaystyle{ a_{1} + a_{2} + \ldots + a_{n} + \ldots, }[/math]
причем порядок, в котором производится сложение различных элементов, несуществен; (б) операция умножения "[math]\displaystyle{ \cdot }[/math]" дистрибутивна относительно конечных и счетно-бесконечных сумм. На замкнутых полукольцах может быть определена унарная операция, называемая замыканием. Пусть [math]\displaystyle{ a }[/math] — некоторый элемент из [math]\displaystyle{ S }[/math]; тогда степени [math]\displaystyle{ a }[/math] могут быть определены следующим образом:
- [math]\displaystyle{ a^{0} = 1; }[/math]
- [math]\displaystyle{ a^{n} = a \cdot a^{n-1}\mbox{ для всех } n \gt 0. }[/math]
Тогда замыкание [math]\displaystyle{ a^{\ast} }[/math] можно определить как
- [math]\displaystyle{ a^{\ast} = 1 + a + a^{2} + \ldots + a^{n} + \ldots. }[/math]
Из свойств полуколец вытекает, что
- [math]\displaystyle{ a^{\ast} = 1 + a \cdot a^{\ast}. }[/math]
Замкнутые полукольца находят применения в различных областях вычислительной техники: в теории автоматов, теории грамматик, теории рекурсии и неподвижных точек, последовательных машинах, матричной обработке, а также в решении различных задач теории графов, например при разработке алгоритмов нахождения кратчайших путей, транзитивного замыкания и др.
Литература
- Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. — М.: Мир, 1979.
- Толковый словарь по вычислительным системам. — М.: Машиностроение, 1991.