Гомоморфизм и Изоморфизм

Предположим, у нас есть 2 алгебры.

Алгебра А = (K, ф1,….,ф_n)

Алгебра В = (L, ф1,….,ф_n)

(причем кол-во операций и их тип одинаковы в обоих множествах)

Тогда гомоморфизм – это такое отображение G

G: K à L (из K в L)

Для любого i от единицы до N

G (фi (x1,…,xm)) = Ψ_i (G(x1)….G(x_n))_, m<=m

(x,y) (x*y)

G G

(G(x),G(y)) G(x*y)

При гомоморфизме не имеет значения порядок выполнения действий. Либо в начале операция, а потом гомоморфное отображение, либо наоборот.

Изоморфизм - взаимно однозначный гомоморфизм.

Например – отрезок [0..1] изоморфен длине окружности, и всей оси вещественных чисел (мощность континуум)

На практике, для изучения сложного объекта можно изучать более простой, изоморфный ему.

Наличие изоморфного отображения сохраняет свойства алгебр, естественный их тип, сигнатуру.

Эндоморфизм.

Это гомоморфизм на себя (когда K и L тождественно равны)

Автоморфизм

Изоморфизм на себя (множества хоть и совпадают, но операции могут быть разными).

Основные свойства алгебраических операций.

1. Коммутативность (а+б == б+а)

2. Ассоциативность (а + (б + с) == (а + б) + с)

3. Дистрибутивность (а*(б+с) = а*б + а*с)

4. Единичный элемент

5. Обратный элемент

x/y, R- à R+ (обратный, единичный,

max(x,y) X,Y принадлежат N (коммутативность, ассоциативность)

A = (P(В), v ^) (объединение и пересечение. Какое само множество В и опред его.

Лекция 4

В зависимости от того, какие свойства операций выполняют ся, алгебру относят к тому или иному типу. Операции делятся на операции типа сложения (аддитивные) и умножения (мультипликативные)

Тип алгебры	Мультипликативные Операции	Аддитивные Операции	Дистриб.	Синоним	Примеры
	Асс	Ед	Обр	Комм	Асс	Ед	Обр	Комм
Одна операц.
Группоид
Полугруппа	+										(N, +)
Моноид	+	+								Полугруппа с единицей	Язык (А,.). – конкатенация Единичный элемент – пустой символ (лямбда)
Абелева полугруппа	+	+		+						Коммутативный моноид	(Z, *)
Группа	+	+	+							Моноид с обратным элементов
Абелева группа	+	+	+	+						Коммутативная группа	(Z, +)
2 операции
Кольцо	+				+	+	+	+
Поле	+	+	+	+	+	+	+	+	+		(R, +,-,*,/)

Графы

G – граф. G = (V, E), где V – множество вершин, а E – множество ребер.

Граф представляет собой отношения. Если вершины связаны ребром, то есть отношения, а если нет – то нет.

Обычный граф задает не рефлексивные и симметричные отношения, а ориентированный (заданы направления) наоборот.

Говорят, что ребро инцидентно вершинам.

Степень вершины – кол-во инцидентных ребер.

Висячие вершины – вершины со степенью 1.

Вершина со степенью 0 называется изолированной.

Способы задания.

1) Рисунок

2) Матрица смежности (связывает вершины ребрами)

3) Матрица инцидентности (связывает ребра вершинами)

Лекция 5

Звездный граф – лучи, исходящие из опр. Центра.

Двудольные. Все вершины разбиваются на 2 множества. Связи устанавливаются только между вершинами разных множеств

Полный граф. Связи устанавливаются между каждыми вершинами

Нагруженный граф. Вершинам и(или) ребрам сопоставлены числа

Однородный граф. Все вершины имеют одинаковую степень

Допустим есть некий граф G(V,E)

Рассмотрим такой G’(V’, E’)

Такой, что

V’ включается в V

E’ включается в E

Тогда этот граф будет Частью графа G

Подграф – часть графа, где вершины, связанные между собой ребром в исходном графе, также связаны между собой.

Покрывающий граф. Это часть графа, в котором каждой вершине инцидентно хотя бы одно ребро.

Суграф. Покрывающий граф, это такой граф, где V’ == V (тождественно)

Маршрут.

Маршрут есть последовательность ребер графа. Может быть бесконечная, в которой два соседних ребра имеют общую инцидентную вершину => на графе возможны циклы.

Цикл – это маршрут, в котором начальные и конечные вершины совпадают

Цепь – маршрут, в котором все ребра различны.
Простая цепь – все вершины различны.

d(x,y) – длина простой цепи из Х в У (минимальной, самой короткой)

1. d(x,y) = 0 ó x=y

2. d(x,y) >= 0

3. d(x,y) = d(y,x)

4. d(x,y) <= d(x,z) + d(y,z)

d(G) = max d(x,y)

x,y принадлежит V

две вершины связаны, если между ними есть маршрут.

Граф называется связным, если каждая пара вершин связана

Несвязный граф разбивается на компоненты связности

Эйлеров цикл – простой цикл, который обходит все ребра графа.

Гамильтонов цикл – простой цикл, который обходит все вершины графа.

С гамильтоновым циклом связаны многие задачи дискретной оптимизации (напр. Найти самый короткий).

Планарный граф – изображаемый на плоскости без пересечения ребер.

Графы, которые различаются только нумерацией вершин, ребер и их расположением, но имеют одинаковую структуру, изоморфны друг друга.

Соотношение |V| + |E| + |R| = 2 для планарных графов, где R – число областей Деревья.

Связанные ациклические графы - дерево.

Любые две вершины связаны единственной простой цепью

Корень – любая вершина

Концевая вершина (лист) – имеет степень 1

Вершины-братья имеют общую вершину.

Лекция 6

Среди деревьев выделяются 2 класса деревьев.

1) N-арные деревья. У каждой вершины не более, чем n потомков.
Бинарные. У каждой вершины – не более, чем 2 потомка.

Цикломатическое число графа

γ (G) = |E| - |V| + N
n – число связных компонентов. (кусков графа)

Цикломатическое число равно количеству элементарных циклов.

Для дерева оно равно 0.

Ориентированные графы

Ориентированный граф – отношение, но уже не симметричное.

Граф Орграф

Степень вершины Входящие/выходящие степени

Ребро Дуга

Маршрут Путь

Цикл Контур

В матрице инцидентности есть отличие

Для орграфов есть различия в связности

В вершину 3 мы не попадем никак.

Орграф СЛАБОсвязан, если связан его соотнесенный граф (без направлений)

Орграф односторонне связан, если для любой пары вершин Х,У существует путь из х в у, либо из у в х

Орграф сильно связан, если для любых Х,У существует путь из х в у И из у в х

Вершина У достижима из вершины Х, если существует ориентированный путь из Х в У

Множество достижимости – множество всех вершин, которые из нее достижимы.

G(x)

Граф называется К-раскрашенным, если G(x) = объединение V_i таких, что ребра в графе соединяют вершины из разных классов V_i (например, если вершины имеют цвет, то ребра соединяют 2 вершины разных цветов)

Min k(G) <= p+1, где p – точная верхняя грань степеней вершин

Разделяющие ребра – после их удаления граф становится несвязанным.

Дз

Докажите формулу для дерева E = V – 1

Определить цикломат число для графа на дом

На том графе сделать его орграфом и определить достижимость любой вершины.

Лекция 7

Алгоритмы и модели алгоритмов

Причины развития теории алгоритмов.

1) Появление вычислительной техники

2) Помимо чисел имеется мн-во других элементов

Теория алгоритмов родилась в 30-е годы 20 века.

Различные варианты теории:

1) Алгоритмы представлялись, как рекурсивные функции

2) Модели в виде некоторого устройства (напр. Машина Тьюринга, Схема Ляпунова)

3) Модели алгоритмов, как некие преобразования символьных строк (алгоритмы Маркова)

Эти модели алгоритмов оказались эквивалентны между собой.

В основе всех этих моделей лежит понятие вычислимой функции, для вычисления которой существует алгоритм.

Теория алгоритмов используется, чтобы понять, существует ли конкретный алгоритм, и чтобы оценить каждый алгоритм по времени выполнения, занимаемой памяти, и сравнивать разные алгоритмы между собой.

Алгоритм – это детерминированная последовательность однозначно определенных шагов, которые вырабатывают определенный результат.

Свойства алгоритма.

1. Алгоритм всегда имеет дело с обработкой данных, имеет входы и выходы.

2. Состоит из элементарных, четко определенных шагов. (Эффективность)

3. Всегда определен каждый следующий шаг, либо работа алгоритма кончается. (Детерминированность)

4. Останавливается после конечного числа шагов (результативность)

5. Массовость

Машина Тьюринга

(см лекцию из прошлого семестра)

M = (A,Q, d, q0)

А – мн-во символов на ленте

Q – конечное мн-во состояний машины

d- функция переходов

q0 – конечное состояние.

D: A * Q -> A * Q * {R, L, S}

(Обозревает символ из мн-ва А, головка в состоянии Q. Символ может остаться прежним или изменяется. Головка переходит или нет. (R- right, L – left, S – stay)

Конфигурация машины Тьюринга

K =a1 q a2 a2

a1

K1 à K2 à …. Kn

Вычисление на машине Тьюринга – это последовательность конфигураций

Функция вычислима по тьюрингу, если существует машина тьюринга, которая ее правильно вычисляет.

W = f(u), если q1u => q0w (u -> w)

Функция не определена, если машина Т будет бесконечно работать

Лента может быть как бесконечной, так и ограниченной в обе стороны (вз. одн. Соотв. Между лентами)

В отличие от компьютера она не универсальна.
у нее неограниченная память.
Команды выполняет человек.

Лекция 8

Опр: Машина Тьюринга U назыв. Универсальной машиной Тьюринга, если для любой машины тьюринга системы команд Et универсальная машина Тьюринга U(Et, a) тождественна исходной машине Тьюринга

исходные команды данные

Преимущество – на ленте хранятся не только данные, но и команды.

Доказано, что существует универсальная машины Тьюринга, в которой всего 2 состояния

Доказано, что сущ. Универсальная машина Тьюринга, где А = 2 (алфавит всего из 2 символов – бинарный код)

Но не существует у.м.т, где 2 состоянияи и 2 символа.

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

Тезис Тьюринга

Любой алгоритм может быть реализован на машине Тьюринга

Поиск по сайту: