Мощность Множеств. Равномощные множества. Конечные и бесконечные

Мощность Множеств. Равномощные множества. Конечные и бесконечные

Конечное множество состоит из конечного числа элементов, например, множество страниц в книге, множество учеников в школе и т.д.

Бесконечное множество состоит из бесконечного числа элементов, т.е. это множество, которое не является ни конечным, ни пустым. Примеры: множество действительных чисел, множество точек плоскости, множество атомов во Вселенной и т.д.

Мощность множества. Добавление и удаление элементов. Вычисление мощности. Булеан

Число подмножеств конечного множества, состоящего из элементов, равно .

Операции над множествами. Диаграммы Венна. Разбиения и покрытия множеств

 

Свойства операций над множествами (не меньше 8)

6.Представление множеств в программах. Генерация всех подмножеств (2 способа)

7.Представление множеств упорядоченными списками. Проверка включения. Операция объединения и пересечения.

Отношения. Упорядоченные пары. Прямое произведение множеств.

 

9.Бинарные отношения. Основные определения и виды отношений. Композиция отношений.

 

Свойства отношений(6 штук). Представление отношений в компьютере.

Замыкание отношений. Алгоритм построения транзитивного замыкания.

Пусть на множестве задано отношение . Видно, что отношение не симметрично, не рефлексивно и не транзитивно. Замыканием относительно свойства симметричности является . Замыканием относительно рефлексивности является . Замыканием относительно транзитивности является множество .

 

 

12.Функциональные отношения. Инъекция, сюрьекция и биекция.

13.Отношение эквивалентности. Классы эквивалентности.

 

Алгебра. Операции и носитель. Основные свойства операций(6 штук).

Алгебраическая система (или алгебраическая структура) в универсальной алгебре — множество (носитель) с заданным на нём набором операций и отношений (сигнатура), удовлетворяющим некоторой системе аксиом. Алгебраическая система с пустым множеством отношений называется универсальной алгеброй, а система с пустым множеством операций — моделью.

Морфизмы. Гомоморфизмы. Изоморфизмы.

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

Например, рассмотрим группы , . Отображение называется гомоморфизмом групп и , если оно одну групповую операцию переводит в другую: .

 

Пусть и — поля. Биекция называется изоморфизмом, если для любых выполняется

1. ,

2. .

17.Алгебры с одной операцией. Полугруппы. Моноиды

Примеры

§ Целые числа с операцией сложения. группа с нейтральным элементом 0. Она является абелевой.

§ Положительные рациональные числа с операцией умножения. Произведение рациональных чисел — снова рациональное число, обратный элемент к рациональному числу представляется обратной дробью, имеется ассоциативность и единица.

Простейшие свойства

§ Обратный к данному элемент всегда определяется однозначно.

§ (a ⁻¹)⁻¹ = a, a^maⁿ = a^{m + n} , (a^m) ⁿ = a^mn.

§ (ab)⁻¹ = b ⁻¹ a ⁻¹.

§ Верны законы сокращения:

,

.

§ Обратный элемент к нейтральному есть сам нейтральный элемент.

§ Группа содержит единственное решение x любого уравнения x · c = b или c · x = b; то есть в группе возможны однозначно определённые правое и левое «деление».

§ Пересечение двух подгрупп группы G есть подгруппа группы G.

§ Теорема Лагранжа: если G — группа конечного порядка g, то порядок g ₁ любой её подгруппы G ₁ является делителем порядка группы. Из этого следует, что и порядок любого элемента делит порядок группы.

§ Для определения числа подгрупп в группе используются теорема Лагранжа и теоремы Силова.

 

Симметрической группой множества X называется группа всех перестановок X (то есть биекций X → X) относительно операции композиции.

Симметрическая группа множества X обычно обозначается S (X). Если X = {1, 2,…, n }, то S (X) также обозначается через S_n.

Нейтральным элементом в симметрической группе является тождественная перестановка , определяемая как тождественное отображение:

для всех x из X.

Свойства

§ При симметрическая группа S_n некоммутативна.

§ При симметрическая группа S_n является неразрешимой (и напротив: при — разрешимой).

§ В случае, если X конечно, число элементов S (X) равно n! (факториал n), где n — число элементов X. В частности,

§ Каждая конечная группа G изоморфна некоторой подгруппе группы S (G) (теорема Кэли).

§ Симметрическая группа S_n допускает следующее задание:

(Можно считать, что переставляет i и i +1.)

 

Алгоритм построения СДНФ.

СДНФ (Совершенная Дизъюнктивная Нормальная Форма) — это такая ДНФ, которая удовлетворяет трём условиям:

§ в ней нет одинаковых элементарных конъюнкций

§ в каждой конъюнкции нет одинаковых пропозициональных букв

§ каждая элементарная конъюнкция содержит каждую пропозициональную букву из входящих в данную ДНФ пропозициональных букв, причем в одинаковом порядке.

Для любой функции алгебры логики существует своя СДНФ, причем единственная.

Пример нахождения СДНФ

Для того, чтобы получить СДНФ функции, требуется составить её таблицу истинности.

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

Первый столбец содержит 1 в указанном поле. Отмечаются значения всех четырёх переменных, это:

§ = 0

§ = 0

§ = 0

§ = 0

Нулевые значения — тут все переменные представлены нулями — записываются в конечном выражении инверсией этой переменной. Первый член СДНФ рассматриваемой функции выглядит так:
Переменные второго члена:

§ = 0

§ = 0

§ = 0

§ = 1

в этом случае будет представлен без инверсии:

Таким образом анализируются все ячейки . Совершенная ДНФ этой функции будет дизъюнкцией всех полученных членов (элементарных конъюнкций).

Совершенная ДНФ этой функции:

 

Полнота системы булевых функций. Примеры полных систем.

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

Теорема Поста. Замкнутые классы функций. Примеры.

Замкнутый класс в теории булевых функций — такое множество функций алгебры логики, замыкание которого относительно операции суперпозиции совпадает с ним самим: . Другими словами, любая функция, которую можно выразить формулой с использованием функций множества , снова входит в это же множество.

§ Класс конъюнкций K, являющийся замыканием множества . Он представляет собой множество функций вида .

§ Класс дизъюнкций D, являющийся замыканием множества . Он представляет собой множество функций вида .

По теореме Поста, чтобы система булевых функций была полной, надо, чтобы в ней существовали:

1. Хотя бы одна функция, не сохраняющая 0.

2. Хотя бы одна функция, не сохраняющая 1.

3. Хотя бы одна нелинейная функция.

4. Хотя бы одна немонотонная функция.

5. Хотя бы одна несамодвойственная функция.

Этому требованию отвечает система функций . На её основе и строятся полиномы Жегалкина.

 

29.Определения теории графов. Смежность. Связность. Виды графов(ор-, псевдо- и т.д.).

Изоморфизм графов. Примеры

Связность

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

Класс эквивалентности по отношению связности двух вершин называется компонентой связности графа.

Число компонентов связности K(G)

Если K == 1 => граф связный. Если K == 2 => граф не связный.

Длина маршрута равна количеству ребер.

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

Операции над графами

1. Дополнение графа

2. Объединение графов

3. Соединение графов

4. Добавление вершины

\

5. Удаление ребра

6. Удаление вершины

7. Стягивание подграфа A в G1(V1, E1)

8. Размножение вершины V

Поиск элемента (FIND)

Дано: дерево Т и ключ K.

Задача: проверить, есть ли узел с ключом K в дереве Т, и если да, то вернуть ссылку на этот узел.

Алгоритм:

• Если дерево пусто, сообщить, что узел не найден, и остановиться.
• Иначе сравнить K со значением ключа корневого узла X.
• Если K=X, выдать ссылку на этот узел и остановиться.
• Если K>X, рекурсивно искать ключ K в правом поддереве Т.
• Если K<X, рекурсивно искать ключ K в левом поддереве Т.

Удаление узла (REMOVE)

Дано: дерево Т с корнем n и ключом K.

Задача: удалить из дерева Т узел с ключом K (если такой есть).

Алгоритм:

• Если дерево T пусто, остановиться;
• Иначе сравнить K с ключом X корневого узла n.
• Если K>X, рекурсивно удалить K из правого поддерева Т;
• Если K<X, рекурсивно удалить K из левого поддерева Т;
• Если K=X, то необходимо рассмотреть три случая.
• Если обоих детей нет, то удаляем текущий узел и обнуляем ссылку на него у родительского узла;
• Если одного из детей нет, то значения полей ребёнка m ставим вместо соответствующих значений корневого узла, затирая его старые значения, и освобождаем память, занимаемую узлом m;
• Если оба ребёнка присутствуют, то
• найдём узел m, являющийся самым левым узлом правого поддерева с корневым узлом Right(n);
• скопируем данные (кроме ссылок на дочерние элементы) из m в n;
• рекурсивно удалим узел m.

Обход дерева (TRAVERSE)

Есть три операции обхода узлов дерева, отличающиеся порядком обхода узлов.

Первая операция — INFIX_TRAVERSE — позволяет обойти все узлы дерева в порядке возрастания ключей и применить к каждому узлу заданную пользователем функцию обратного вызова f. Эта функция обычно работает только с парой (K,V), хранящейся в узле. Операция INFIX_TRAVERSE реализуется рекурсивным образом: сначала она запускает себя для левого поддерева, потом запускает данную функцию для корня, потом запускает себя для правого поддерева.

• INFIX_TRAVERSE (f) — обойти всё дерево, следуя порядку (левое поддерево, вершина, правое поддерево).
• PREFIX_TRAVERSE (f) — обойти всё дерево, следуя порядку (вершина, левое поддерево, правое поддерево).
• POSTFIX_TRAVERSE (f) — обойти всё дерево, следуя порядку (левое поддерево, правое поддерево, вершина).

INFIX_TRAVERSE:

Дано: дерево Т и функция f

Задача: применить f ко всем узлам дерева Т в порядке возрастания ключей

Алгоритм:

• Если дерево пусто, остановиться.
• Иначе
• Рекурсивно обойти левое поддерево Т.
• Применить функцию f к корневому узлу.
• Рекурсивно обойти правое поддерево Т.

В простейшем случае, функция f может выводить значение пары (K,V). При использовании операции INFIX_TRAVERSE будут выведены все пары в порядке возрастания ключей. Если же использовать PREFIX_TRAVERSE, то пары будут выведены в порядке, соответствующим описанию дерева, приведённого в начале статьи.

АВЛдеревья.Балансировка

Так называемые AVL-деревья (названные в честь их двух изобретателей Г.М. Адельсона-Вельского и Е.М. Ландиса) хранят дополнительно в каждой вершине разность между высотами левого и правого поддеревьев, которая в сбалансированном дереве может принимать только три значения: -1, 0, 1.

Новая вершина добавляется как терминальная. После этого выполняется процедура восстановления балансировки. В ней используются следующие элементарные преобразования дерева, сохраняющие упорядоченность вершин:

1. вращение вершины x поддерева влево:

 

Здесь вершина x поддерева, которая является его корнем, опускается вниз и влево. Бывший правый сын d вершины x становится новым корнем поддерева, а x становится левым сыном d. (Вершины x и d, начальник и подчиненный, как бы меняются ролями: бывший начальник становится подчиненным.) Поддерево c, которое было левым сыном вершины d, переходит в подчинение от вершины d к вершине x и становится ее правым сыном. Отметим, что упорядоченность вершин сохраняется: a < b < c< d < e. Таким образом, для выполнения преобразования надо лишь заменить фиксированное количество указателей в вершинах x, d, c и, возможно, в родительской для x вершине;

1. вращение вершины x поддерева вправо:

 

Здесь вершина x опускается вниз и вправо, ее бывший левый сын b становится новым корнем поддерева, а x — его правым сыном. Поддерево c переходит в подчинение от b к x.

Операции вращения носят локальный характер и позволяют при необходимости исправить баланс поддерева с корнем x. Например, для восстановления баланса дерева, показанного на следующем рисунке, достаточно выполнить одно вращение вершины b влево:

 

В случае AVL-деревьев операции вращения повторяются в цикле при восстановлении баланса после добавления или удаления элемента, число вращений не превышает С x h, где h — высота дерева, C — константа.

 

Алгоритм Краскала

Идея алгоритма. Искомые ребра соединяют вершины. Поэтому возможны две стратегии построения. Можно идти от вершин и для каждой из них искать минимальное ребро (как это сделано в алгоритме Прима) а можно для каждого ребра выяснять можно ли его включить в строящееся дерево. Алгоритм Краскала предлагает делать это следующим образом. Во-первых, ребра графа пронумеровываем в порядке возрастания весов. Затем для каждого ребра начиная с первого проверяем соединяет или нет оно две несвязные вершины, если да, то его можно включить в остовное дерево. Ясно, что если мы имеем V вершин, то работа алгоритма начинается с V несвязных компонент графа (пока из графа все ребра исключаем). Для того, чтобы их связать необходимо найти V-1 ребро.

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

Пример

Изображение	Описание
	Ребра AD и CE имеют минимальный вес, равный 5. Произвольно выбирается ребро AD (выделено на рисунке).
	Теперь наименьший вес, равный 5, имеет ребро CE. Так добавление CE не образует цикла, то выбираем его в качестве второго ребра.
	Аналогично выбираем ребро DF, вес которого равен 6.
	Следующие ребра — AB и BE с весом 7. Произвольно выбирается ребро AB, выделенное на рисунке. Ребро BD выделено красным, так уже существует путь (зеленый) между B и D, поэтому, если бы это ребро было выбрано, то образовался бы цикл ABD.
	Аналогичным образом выбирается ребро BE, вес которого равен 7. На этом этапе красным выделено гораздо больше ребер: BC, потому что оно создаст цикл BCE, DE, потому что оно создаст цикл DEBA, и FE, потому что оно сформирует цикл FEBAD.
	Алгоритм завершается добавлением ребра EG с весом 9. Минимальное остовное дерево построено.

 

Алгоритм Прима

Сам алгоритм имеет очень простой вид. Искомый минимальный остов строится постепенно, добавлением в него рёбер по одному. Изначально остов полагается состоящим из единственной вершины (её можно выбрать произвольно). Затем выбирается ребро минимального веса, исходящее из этой вершины, и добавляется в минимальный остов. После этого остов содержит уже две вершины, и теперь ищется и добавляется ребро минимального веса, имеющее один конец в одной из двух выбранных вершин, а другой — наоборот, во всех остальных, кроме этих двух. И так далее, т.е. всякий раз ищется минимальное по весу ребро, один конец которого — уже взятая в остов вершина, а другой конец — ещё не взятая, и это ребро добавляется в остов (если таких рёбер несколько, можно взять любое). Этот процесс повторяется до тех пор, пока остов не станет содержать все вершины (или, что то же самое, ребро).

В итоге будет построен остов, являющийся минимальным. Если граф был изначально не связен, то остов найден не будет (количество выбранных рёбер останется меньше ).

 

Изображение	Множество выбранных вершин U	Ребро (u,v)	Множество невыбранных вершин V \ U	Описание
	{}		{A,B,C,D,E,F,G}	Исходный взвешенный граф. Числа возле ребер показывают их веса, которые можно рассматривать как расстояния между вершинами.
	{D}	(D,A) = 5 V (D,B) = 9 (D,E) = 15 (D,F) = 6	{A,B,C,E,F,G}	В качестве начальной произвольно выбирается вершина D. Каждая из вершин A, B, Eand F соединина с D единственным ребром. Вершина A — ближайшая к D, и выбирается как вторая вершина вместе с ребром AD.
	{A,D}	(D,B) = 9 (D,E) = 15 (D,F) = 6 V (A,B) = 7	{B,C,E,F,G}	Следующая вершина — ближайшая к любой из выбранных вершин D или A. B удалена от D на 9 и от A — на 7. Расстояние до E равно 15, а до F — 6. F является ближайшей вершиной, поэтому она включается в дерево F вместе с ребром DF.
	{A,D,F}	(D,B) = 9 (D,E) = 15 (A,B) = 7 V (F,E) = 8 (F,G) = 11	{B,C,E,G}	Аналогичным образом выбирается вершина B, удаленная от A на 7.
	{A,B,D,F}	(B,C) = 8 (B,E) = 7 V (D,B) = 9 cycle (D,E) = 15 (F,E) = 8 (F,G) = 11	{C,E,G}	В этом случае есть возможность выбрать либо C, либо E, либо G. C удалена от B на 8,E удалена от B на 7, а G удалена от F на 11. E — ближайшая вершина, поэтому выбирается E и ребро BE.
	{A,B,D,E,F}	(B,C) = 8 (D,B) = 9 цикл (D,E) = 15 цикл (E,C) = 5 V (E,G) = 9 (F,E) = 8 цикл (F,G) = 11	{C,G}	Здесь доступны только вершины C и G. Расстояние от E до C равно 5, а до G — 9. Выбирается вершина C и ребро EC.
	{A,B,C,D,E,F}	(B,C) = 8 цикл (D,B) = 9 цикл (D,E) = 15 цикл (E,G) = 9 V (F,E) = 8 цикл (F,G) = 11	{G}	Единственная оставшаяся вершина — G. Расстояние от F до нее равно 11, от E — 9. Eближе, поэтому выбирается вершина G и ребро EG.
	{A,B,C,D,E,F,G}	(B,C) = 8 цикл (D,B) = 9 цикл (D,E) = 15 цикл (F,E) = 8 цикл (F,G) = 11 цикл	{}	Выбраны все вершины, минимальное остовное дерево построено (выделено зеленым). В этом случае его вес равен 39.

 

Формальное определение

Дан взвешенный ориентированный^[1] граф без петель и дуг отрицательного веса^[2]. Найти кратчайшие пути от некоторой вершины графа до всех остальных вершин этого графа.

Неформальное объяснение

Каждой вершине из V сопоставим метку — минимальное известное расстояние от этой вершины до a. Алгоритм работает пошагово — на каждом шаге он «посещает» одну вершину и пытается уменьшать метки. Работа алгоритма завершается, когда все вершины посещены.

Инициализация. Метка самой вершины a полагается равной 0, метки остальных вершин — бесконечности. Это отражает то, что расстояния от a до других вершин пока неизвестны. Все вершины графа помечаются как непосещённые.

Шаг алгоритма. Если все вершины посещены, алгоритм завершается. В противном случае, из ещё не посещённых вершин выбирается вершина u, имеющая минимальную метку. Мы рассматриваем всевозможные маршруты, в которых u является предпоследним пунктом. Вершины, в которые ведут рёбра из u, назовем соседями этой вершины. Для каждого соседа вершины u, кроме отмеченных как посещённые, рассмотрим новую длину пути, равную сумме значений текущей метки u и длины ребра, соединяющего u с этим соседом. Если полученное значение длины меньше значения метки соседа, заменим значение метки полученным значением длины. Рассмотрев всех соседей, пометим вершину u как посещенную и повторимшаг алгоритма.

Пример

Рассмотрим выполнение алгоритма на примере графа, показанного на рисунке. Пусть требуется найти кратчайшие расстояния от 1-й вершины до всех остальных.

Кружками обозначены вершины, линиями — пути между ними (ребра графа). В кружках обозначены номера вершин, над ребрами обозначена их «цена» — длина пути. Рядом с каждой вершиной красным обозначена метка — длина кратчайшего пути в эту вершину из вершины 1.

Первый шаг. Рассмотрим шаг алгоритма Дейкстры для нашего примера. Минимальную метку имеет вершина 1. Её соседями являются вершины 2, 3 и 6.

Первый по очереди сосед вершины 1 — вершина 2, потому что длина пути до неё минимальна. Длина пути в неё через вершину 1 равна сумме кратчайшего расстояния до вершины 1, значению её метки, и длины ребра, идущего из 1-й в 2-ю, то есть 0 + 7 = 7. Это меньше текущей метки вершины 2, бесконечности, поэтому новая метка 2-й вершины равна 7.

Аналогичную операцию проделываем с двумя другими соседями 1-й вершины — 3-й и 6-й.

Все соседи вершины 1 проверены. Текущее минимальное расстояние до вершины 1 считается окончательным и пересмотру не подлежит (то, что это действительно так, впервые доказал Э. Дейкстра). Вычеркнем её из графа, чтобы отметить, что эта вершина посещена.

Второй шаг. Шаг алгоритма повторяется. Снова находим «ближайшую» из непосещенных вершин. Это вершина 2 с меткой 7.

Снова пытаемся уменьшить метки соседей выбранной вершины, пытаясь пройти в них через 2-ю вершину. Соседями вершины 2 являются вершины 1, 3 и 4.

Первый (по порядку) сосед вершины 2 — вершина 1. Но она уже посещена, поэтому с 1-й вершиной ничего не делаем.

Следующий сосед вершины 2 — вершина 3, так как имеет минимальную метку из вершин, отмеченных как не посещённые. Если идти в неё через 2, то длина такого пути будет равна 17 (7 + 10 = 17). Но текущая метка третьей вершины равна 9<17, поэтому метка не меняется.

Ещё один сосед вершины 2 — вершина 4. Если идти в неё через 2-ю, то длина такого пути будет равна сумме кратчайшего расстояния до 2-й вершины и расстояния между вершинами 2 и 4, то есть 22 (7 + 15 = 22). Поскольку 22< , устанавливаем метку вершины 4 равной 22.

Все соседи вершины 2 просмотрены, замораживаем расстояние до неё и помечаем её как посещенную.

Третий шаг. Повторяем шаг алгоритма, выбрав вершину 3. После её «обработки» получим такие результаты:

Дальнейшие шаги. Повторяем шаг алгоритма для оставшихся вершин. Это будут вершины 6, 4 и 5, соответственно порядку.

Завершение выполнения алгоритма. Алгоритм заканчивает работу, когда нельзя больше обработать ни одной вершины. В данном примере все вершины зачеркнуты, однако ошибочно полагать, что так будет в любом примере - некоторые вершины могут остаться незачеркнутыми, если до них нельзя добраться. Результат работы алгоритма виден на последнем рисунке: кратчайший путь от вершины 1 до 2-й составляет 7, до 3-й — 9, до 4-й — 20, до 5-й — 20, до 6-й — 11.

 

АлгоритмА-star