половин пръстен

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

Съдържание

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

Полупръстенът се наричакомутативен, ако операцията на умножение в него е комутативна: a ⋅ b = b ⋅ a ∀ a , b ∈ S .

Полупръстенът се наричаполупръстен с единица, ако съдържа неутрален елемент от умножението (нареченедно): a ⋅ 1 = 1 ⋅ a = a ∀ a ∈ S .

Полупринг ⟨ N 0 , + , ⋅ ⟩ _,+,\cdot \rangle > от естествени числа с нула.
Тривиално полупръстенце: ⟨ < 0 >, + , ⋅ ⟩
Двуелементни полупръстени: ⟨ Z 2 , + , ⋅ ⟩ _,+,\cdot \rangle > , ⟨ B , ⊕ , ∨ ⟩ ,\oplus ,\vee \rangle > , където ∨ означава дизюнкция, а ⊕ е логическата операция „изключително или“ върху множеството B = < 0, 1 >=\lскоба 0,1\rскоба >
Квадратни n × n матрици с елементи от полупръстен от естествени числа с нула N 0 _> и операции за събиране и умножение на матрици. Полупръстен също се формира от квадратни матрици с елементи от всяко полупръстен.
Ако A е комутативен моноид, тогава множеството End ⁡ ( A ) (A)> от ендоморфизми на A образува полупръстен, където събирането е дефинирано по точка, а умножението е дефинирано като композиция от функции.
N[x][x]> - полиноми с естествени коефициенти - образуват комутативен полупръстен; е свободен комутативен полупръстен с уникален генератор < x>> .
Вероятностен полупръстен - неотрицателенреални числа с обичайните операции събиране и умножение [2] .
( max , + ) и ( min , + ) са полукръгове от реални числа, в които събирането се определя като вземане на максимума (съответно минимума), а умножението като обичайното събиране на реални числа.

Алгоритъмът на Флойд-Уоршал за намиране на най-кратки пътища може да бъде преформулиран за изчисление върху (min, +) -алгебра. Също така, алгоритъмът на Витерби за намиране на най-вероятната последователност от състояния в скрит модел на Марков може да бъде преформулиран за изчисления върху (max, ×) -вероятностната алгебра. Тези алгоритми за динамично програмиране използват дистрибутивността на съответните полупръстени за изчисляване на свойства чрез използване на голям (вероятно експоненциално голям) брой променливи по-ефективно, отколкото чрез изброяване на всяка една.

По този начин, полукръг от множества съдържа празно множество, е затворен при пресичане и всяка разлика от набори от полукръг от множества може да бъде представена като краен съюз на несвързани (по двойки несвързани) множества, принадлежащи на този полукръг от множества. Такива полупръстени често се използват в теорията на мерките.