Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Билет №1.Способы задания множеств. Подмножества. Отношения между множествами.
Множество – это вполне определенная совокупность различимых между собой предметов, понимаемая как единое целое. Предметы, составляющие множества, называется его элементами.
Множества обозначаются обычно большими латинскими буквами: A B C M N и тд.
Если предмет а является элементом множества А, то пишут а ϵ А.
Если множества А конечно и состоит из элементов а1 а2, … ,аn ,то пишут: А={ а1 а2, … ,аn}.
В случаях, когда число элементов какого либо множества А достаточно велико (или бесконечно), или эти элементы не известны, применяется запись вида: А={x|P(x)}, где символом P(x) обозначается характеристическое свойство элементов x множества А.
Ø- множество в котором нет элементов (пустое множество).
Множество А называется подмножеством множества В (А вложено В), если каждый элемент множества А является элементом множества В. А В
Пустое множество и само множество являются подмножествами для любого множества А(ØА, А). Они называются тривиальными подмножествами множествами. Подмножества, не совпадающие с тривиальными, называются собственными.
Множество всех подмножеств множества А называется булеаном множества А и обозначается 2А.
Если множество А состоит из n элементов, то множества 2А состоит из 2 n элементов.
Множества А и В называются равными (А=В), если они состоят из одних и тех же элементов.
А=В тогда и только тогда, когда АВ и ВА.
Операции над множествами.
Объединением (АВ) множества А и В называется множества всех предметов которые являются элементами множества А, или элементами множества В или их общими элементами. АВ = {с |c ϵ A или с ϵ В или с ϵ А, В}.
Пересечением (АВ) множества А и В называется множество предметов, являющихся элементами обоих множеств А и В. АВ={x |x ϵ A и x ϵ B}.
Дополнением Ᾱ множества А называется множества всех элементов универсального множества (U), не являющихся элементами множества А.
Разностью А\В множеств А и В называется множество, элементами которого являются элементы множества А но не являющиеся элементами множества В.
Декартовым произведением множеств А и В называется множества упорядоченных пар, первый элемент которых есть элемент множества А, второй элемент есть элемент множества В.
(А×В={(а, b)| a ϵ A, b ϵ B}.
Универсальным множеством (U) называется множества, для которого все рассматриваемые задачи или теории множества являются подмножествами.
Билет №2.Мощность множества. Представление множеств в ЭВМ.
1)
Множества А и В называются равномощными (эквивалентными), если между их элементами можно установить взаимно – однозначное соответствие.
Для конечных множеств их равномощность означает равное количество элементов в этих множествах.
Количество элементов в конечном множестве множестве А называется его мощностью и обозначается |a|.
Множество А называется счетным, если можно установить взаимно – однозначное соответствие (нумерацию) между элементами этого множества и множества N натуральных чисел.
Любое конечное множество не является счетным.
Теорема Кантора: Множества действительных чисел отрезка [0, 1] не является счетным.
Говорят, что множества равномощное отрезку [0, 1], имеет мощность континуума.
2)
Представление множеств в ЭВМ подразумевает описание способа хранения информации у принадлежности элементов множеству и описание алгоритмов вычисления объединения, пересечения и тд.
Все подмножества некоторого множества можно генерировать последовательностью кодов, которой каждый следующий код получается из предыдущего прибавления единицы в двоичной системе счисления, начиная с кода пустого множества.
Номер NA кода множества А в этой последовательности однозначно определяется самим кодом и является записью А2 в десятичной системе счисления.
Количество кодов в этой последовательности равно 2n и, следовательно, мощность множества 2U всех подмножеств множества U также равно 2n . (|2U|=2n)
Логической суммой (дизъюнкцией) и логическим произведением (конъюнкцией) булевых переменных x и y называется функции x ˄ y и x ˅ y, определяемые таблицей:
Билет №3.Отношения на множествах. График и граф бинарного отношения.
1.
n-арным отношением на множестве А называется любое подмножества упорядоченных n-ок элементов этого множества.
При n = 3 отношение называется тернарным, при n=2 бинарным, при n = 1 унарным.
Обозначение: ρ, σ, τ…
Таких образом, если ρ – n- арное отношение на множестве А, то ρ Аn.
Областью определения Dρ отношение ρ называется множеством всех первых элементов пар, входящих в ρ; областью значений Rρ отношение ρ называется множество всех вторых элементов пар, входящих в ρ.
Бинарным отношение от X к Y называется любое подмножество множества X×Y.
2.
Графиком бинарного отношения ρ, заданного на множестве А называется множество точек на плоскости с координатами (x, y): (x, y) ϵ ρ.
Графом отношения ρ называется геометрическая фигура на плоскости, состоящая из точек – вершин графа, и линии их соединяющих – ребер графа. Вершины графа обозначают элементы множества, на котором определено отношение, а ребро графа соединяющих вершины a и b графа, проводится в том случае, когда a, b ϵ ρ. В этом случае ребро изображается со стрелкой от вершины a к вершине b.
Билет №4.Свойства бинарных отношений.
Отношение ρ, заданное на множестве А, называется рефлексивным, если
Отношение ρ, заданное на множестве А, называется антирефлексивным, если
Отношение ρ, заданное на множестве А, называется симметричным, если
Отношение ρ, заданное на множестве А, называется антисимметричным, если
Отношение ρ, заданное на множестве А, называется транзитивным, если
График рефлексивного на А отношения включает все точки в (x, x) биссектрисы 1–го и 3–го координатных углов для x ϵ A. Граф рефлексивного отношения имеет в каждой его вершине петлю.
График антирефлексивного отношения не имеет ни одной точки (x, x) на биссектрисе 1-го и 3-го координатных углов для x ϵ A, а на его графе нет петель.
График симметричного отношения – эта фигура, симметричная относительно биссектрисы
График рефлексивного на А отношения включает все точки в (x, x) биссектрисы 1–го и 3–го координатных углов (прямой x=y). Граф симметричного отношения не имеет ориентированных ребер.
График антисимметричного отношения не имеет точек симметричных относительно биссектрисы 1-го и 3-го координатных углов, на самой же биссектрисе точки графика могут быть. Граф антисимметричного отношения не имеет неориентированных ребер, но может иметь петли.
На графике транзитивного отношения вместе с каждой парой точек (a, b) и (b, c) должна быть точка (a, c), это означает, что четвертая вершина прямоугольника так же должна быть на графике.
Билет №5.Отношение эквивалентности. Классы эквивалентности.
Рефлексивное, симметричное и транзитивное отношение называется отношением эквивалентности.
Классном эквивалентности [a]ρ с представителем а называется множество всех тех элементов множества А, которые говорят эквивалентны элементу а: [a]ρ = {x| x ϵ A, (x, a) ϵ ρ}.
Свойства классов эквивалентности:
Класс эквивалентности не зависит от его представителя. Если b ϵ [a]ρ , то [a]ρ = [b]ρ .
Различные классы эквивалентности не пересекаются. Если [a]ρ [b]ρ ≠ Ø, то [a]ρ = [b]ρ .
Множество всех классов эквивалентности отношения ρ на множестве А называется фактор – множеством множества А по отношению ρ и обозначается А/ρ .
Билет №6. Разбиения множеств и отношения эквивалентности.
Разбиения множества А называется семейство его непустых подмножеств, объединение которых совпадает с множеством А, а пересечение любых двух из них пусто.
Теорема:
1. Пусть ρ отношение эквивалентности на множестве А. Тогда фактор – множества А/ρ является разбиением множества А.
2. Любое разбиение множества порождает на нем некоторые отношения эквивалентности.
Отношение эквивалентности:
Рефлексивное, симметричное и транзитивное отношение называется отношением эквивалентности.
Классном эквивалентности [a]ρ с представителем а называется множество всех тех элементов множества А, которые говорят эквивалентны элементу а: [a]ρ = {x| x ϵ A, (x, a) ϵ ρ}.
Свойства классов эквивалентности:
Класс эквивалентности не зависит от его представителя. Если b ϵ [a]ρ , то [a]ρ = [b]ρ .
Различные классы эквивалентности не пересекаются. Если [a]ρ [b]ρ ≠ Ø, то [a]ρ = [b]ρ .
Множество всех классов эквивалентности отношения ρ на множестве А называется фактор – множеством множества А по отношению ρ и обозначается А/ρ .
Билет №7. Отношение порядка. Упорядоченные множества.
Бинарное отношение называется отношение порядка на множестве, если оно транзитивно и антисимметрично.
Отношения порядка делятся на строгие (в случае антирефлексивности)и не строгие (в случае рефлексивности) отношение порядка. Кроме того, отношение порядка делятся на линейные и не линейные (частичного порядка).
Отношение порядка ρ называется линейным на множестве А, если для любых x, y ϵ А либо
(x, y) ϵ ρ, либо (y, x) ϵ ρ, либо x=y.
Отношение порядка, не являющиеся линейным, называется отношением частичного порядка.
Множества, на котором введено отношение порядка (частичного порядка), называется упорядоченным (частично упорядоченным) множеством.
Элемент а ϵ А называется наименьшим (наибольшим) элементом
Элемент а ϵ А называется минимальным (максимальным) элементом
Билет №8. Композиция отношений. Инверсия отношения.
Композицией ρ ◦ τ отношений ρ и τ называется множество всех таких пар (x, z), что для некоторых y (x, y) ϵ τ и (y, z) ϵ ρ таким образом, ρ ◦ τ ={x, z|существует y, такое что y (x, y) ϵ τ и (y, z) ϵ ρ}.
Инверсия и отношение ρ называется отношение ρ ͝ = {(x, y)|(y, x) ϵ ρ}.
Операции и композиция и инверсия обладают свойствами:
1.ρ ◦ τ ≠ τ ◦ ρ
2. (ρ ◦ τ) ◦ σ = ρ ◦ (τ ◦ σ)
3.(ρ ◦ τ) ͝ = τ ͝ ◦ ρ ͝
Билет №9.Размешение, перестановки, сочетания и их количество.
Размещениями называются комбинации, составленные из n различных элементов по m элементов, которые отличаются либо составом, либо их порядком.
Определенное выше понятие размещений называют еще размещениями без повторений. Если при выборе размещений каждый выбранный элемент возвращать в множества А, то полученные комбинации называют размещениями с повторениями.
Перестановками из n элементов называются комбинации, состоящие из одних и тех же n элементов, отличающиеся друг от друга только порядком.
Перестановками с повторениями называются комбинации, в которых могут повторятся некоторые элементы и которые отличаются только порядком.
Сочетанием из n элементов по m элементов называется неупорядоченное подмножество n – элементного множества, состоящее из m элементов.
Билет №12.Разбиение множества. Числа Стирлинга 2-го рода и числа Белла.
Обозначим S (n,m) – число разбиений n – элементного множества на m блоков. Числа S(n,m) называются числами Стирлинга 2-го рода.
Теорема:
Для любых n,m справедливо равенство: S (n, m) = S (n-1, m-1) + m S (n-1, m)
Рекуррентная формула (которая выше) позволяет последовательно вычислять все числа Стирлинга 2-го рода при растущих m и n, учитывая, что S (n, n) = 1 и S (n, 1) = S (n-1, 0) + 1 * S (n-1, 1) = 0+S (n-1, 1) = S (n-2, 0)+1* S (n-2, 1) = … = S (1, 1) = 1.
Для вычисления чисел Стирлинга 2-го рода существует также явная формула:
Число всех разбиений n – элементного множества называется число Белла и обозначается В(n). B(0) полагают равным единицы.
Билет №13.Лексикографическое упорядочение постановок.
Перестановка (i1, i2,… ,in) лексикографически предшествует (<=) перестановки (j1, j2,… ,jn), если существует такое m, что ik = jk для 1<=k<m, и im<jm .
Алгоритм лексикографического упорядочения следящий:
1.Находим упорядоченный по убыванию «хвост» перестановки наибольшей длины. Если «хвост» совпадает со всей перестановкой, то конец алгоритма иначе шаг 2;
2.Элеемнты, предшествующий «хвосту», меняем с наименьшим элементом «хвоста», большим его; Элементы «хвоста» упорядочиваем в порядке возрастания и возвращаемся к пункту один.
При лексикографическом упорядочении номер перестановки (i1, i2,… ,in) вычисляется по формуле N=a1(n-1)!+a2(n-2)!+…+a n-1 1!, где aj – количество элементов, меньших ij ,и стоящих правее его (0 <= aj <= n-j).