56. Гомоморфизмы алгебры

def. Пусть А и В – однотипные алгебры, fa- главная операция алгебры A, а fb – соответствующая ей главная операция алгебры B, (т.е.f a и f b имеют одинаковые ранги).

, где n – ранг операции

(n1,n2,…,ns) – тип алгебры A

(n1,n2,…,ns ) – тип алгебры B

def. Отображение h основного множества А в основное множество В, сохраняет главную операцию f a алгебры A, если для ( )

, где n – ранг операции . ()

def. Гомоморфизмом алгебры A в (на) однотипную алгебру B называют такое отображение h множества A в (на) множество B, которое сохраняет все главные операции алгебры A, т.е. для любой операции fa алгебры A выполняется условие ().

def. Гомоморфизм алгебры A на алгебру B называется эпиморфизмом.

def. Гомоморфизм h алгебры A на алгебру B называют изоморфизмом, если h есть инъективное отображение множества A на множествo B. При этом пишут .

def. Гомоморфизм h алгебры A в алгебру B, называется мономорфизмом, если h является инъективным отображением множества A в множество B.

def. Гомоморфизм алгебры A в себя, называется эндоморфизмом.

def. Изоморфизм алгебры A на себя, называется автоморфизмом.

57. Алгебраические системы

def. Упорядоченная тройка называется алгебраической системой, где

– множество алгебр. операций на А,

- мн-во отношений на множестве А.

Таким образом, алгебры можно считать частным случаем алгебраических систем. Другим частным случаем алгебраических систем являются модели – множества, на которых заданы только отношения.

Решетки

def. Решёткой называется частичное упорядоченное множество , в котором каждая пара элементов имеет sup и inf. Для заданных элементов элемент inf{x,y}называется пересечением элементов х и у (обозначается ), а sup{x,y} называется объединением элементов х и у (обозначается), Решетка – это алгебраическая система

где - бинарные операции на множестве A, - бинарное отношение частичного порядка на A.

Заметим, что если в системе A введены операции , то отношение можно по этим операциям восстановить следующим образом:

, а также

Наименьший (наибольший) элемент решетки, если он существует, называют

нулем (единицей). Обозначаются эти элементы соответственно через 0 и 1.

Пример 1. Любое конечное линейно упорядоченное множество является решеткой. Пример 2. Рассмотрим , в котором , а элементы . Система A образует решётку, В этой решётке a=0, e=1

58. Матроиды. Жадн. Алгоритмы Матроид является классиф-ей подмножеств конечного мн-ва, предст. собой обобщение идеи независимости элементов. Матроид – упорядоченная пара <X,I> где X-конечное мн-во (носьтель матроида) Y-некоторое мн-во подмн-в X семейства независимых множеств (I включено в P(I)) При этом 1. 2. Есл. и , то 3.Если и мощность A больше мощности B, то существует такой, что Базами матроида называются максимальные по включению независимые множества Минимальные по включению зависимые множества называются циклами матроида Свободный матроид: <X,P(x)> Жадный алгоритм Опр: Жадный алгоритм— алгоритм, заключающийся в принятии локально оптимальных решений на каждом этапе, допуская, что конечное решение также окажется оптимальным. Общего критерия оценки применимости жадного алгоритма для решения конкретной задачи не существует, однако, для задач, решаемых жадными алгоритмами, характерны две особенности: во-первых, к ним применим Принцип жадного выбора, а во-вторых, они обладают свойством Оптимальности для подзадач