- •1)Понятие множества и его элементов. Способы задания множеств. Подмножества.
- •6)Свойства операций над множествами (коммутативность, ассоциативность, дистрибутивность, свойство разности, операции с и универсумом, …).
- •7) Отношения на множествах. Способы задания отношений
- •8) Специальные отношения (обратное, универсальное, тождественное). Композиция отношений.
- •9) Свойства отношений (рефлексивность, симметричность, антисимметричность, транзитивность, эквивалентность), теорема о свойствах композиции отношений.
- •1. R рефлексивно I r;
- •12) Отношение порядка и его свойства. Частично упорядоченные множества, наибольший и наименьший, максимальный и минимальный элементы, точная верхняя и нижняя грани. Понятие замкнутости множеств.
- •14) Понятие перестановки.
- •15) Понятие выборки. Способы классификации выборок
- •16) Размещения и сочетания без повторений – определение, формулы для расчета числа вариантов.
- •17) Размещения и сочетания с повторениями – определение, формулы для расчета числа вариантов.
- •20) Перестановки с повторениями.
- •25) Виды графов (орграф, псевдограф, мультиграф, простой граф) и их связь с бинарными отношениями.
- •27) Степени вершин. Лемма о рукопожатиях.
- •28) Маршруты, цепи, циклы. Расстояние между вершинами, диаметр графа.
- •29) Связность, компоненты связности. Сильная и слабая связность. Выделение компонент сильной связности в орграфе.
- •30) Подграфы. Минимальный остов и алгоритм его построения.
- •38) Эйлеровы и гамильтоновы графы, понятия эйлеровой цепи, цикла, гамильтонова цикла. Алгоритм поиска эйлеровой цепи.
- •42) Булевы функции и булева алгебра. Аксиомы булевой алгебры. Их применение.
- •49) Минимизация
14) Понятие перестановки.
Перестановки различаются только порядком входящих в них элементов.
Перестановка элементов множества M может быть задана посредством функции подстановки. Будем определять подстановку как биекцию : M M и задавать ее с помощью матрицы, состоящей из двух строк.
Если заданы две подстановки и своими матрицами [] и [], то их произведение определяется следующим образом. В матрице [] столбцы переставляются так, чтобы ее первая строка совпала со второй строкой матрицы []: . В итоге получится:
[][] = =.
Тождественная подстановка – это такая подстановка e, что e(x)=x x.
[e] = .
Обратная подстановка – это обратная функция, которая всегда существует (подстановка является биекцией). Для получения таблицы обратной подстановки нужно поменять местами строки таблицы исходной подстановки.
Для подстановки [] = [–1] = .
Подстановка называется циклом длины r, если матрицу [] перестановкой столбцов можно привести к виду:
, т.е. первые r элементов сменяют друг друга, а остальные неподвижны: (si) = si+1, для 1 i r –1 и (sr) = s1.
Подстановка с матрицей [] = =является циклом (2 5 3 6), а подстановка с матрицей [] = циклом не является, т.к. из нее можно выделить два цикла (1 4) и (2 5 6 3).
Утверждение 2.2 Каждую подстановку можно однозначно (с точностью до порядка сомножителей) представить в виде произведения независимых циклов.
В примере 2.7 [] = (2 5 3 6), [] = = (1 4)(2 5 6 3).
Двухэлементный цикл (i j) называется транспозицией. При транспозиции меняются местами только i-й и j-й элементы, а остальные сохраняют свое положение.
Подстановку удобно изображать графически, соединяя стрелками элементы x и (x): .
Используя только транспозиции, можно выполнить сортировку множества в определенном порядке (например, в лексикографическом). Известный алгоритм сортировки, основанный на этом принципе, на каждом шаге осуществляет перестановку только двух соседних элементов и носит название «пузырьковой сортировки».
Число перестановок объема n принято обозначать как Pn.
15) Понятие выборки. Способы классификации выборок
Пусть дано множество M = {a1, a2, a3, ..., an}, m n. Набор, состоящий из m элементов множества М, называется выборкой объема m из n элементов.
Выборки классифицируются следующим образом:
По критерию повторяемости элементов: С возвращением объема (с повторениями) и без возвращения объема (без повторений).
По критерию упорядоченности:
Упорядоченные (размещения) и неупорядоченные (сочетания).
В ящике n≤10 нумерованных шаров, один достают, записывают номер и бросают обратно. Так делают три раза. Сколько разных трехзначных чисел может получиться? Для подсчета нужны размещения с повторениями
16) Размещения и сочетания без повторений – определение, формулы для расчета числа вариантов.
Размещениями из n элементов по m называются упорядоченные выборки без повторений элементов множества, которые отличаются одна от другой либо составом элементов, либо порядком их расположения. Размещение можно рассматривать как разнозначную функцию f:{1,2,…,m}M, для которой f(j)=aij.
Тогда числу размещений из n элементов по m соответствует число инъективных функций или число всех возможных способов разместить n предметов по m позициям («ящикам»), не более чем по одному в «ящик». Это число будем обозначать =A(n,m) (иногда обозначают P(n,m)).
Пусть дано множество M={1,2,3,4,5}. Тогда размещениями из 5 элементов по 2 будут, в частности, выборки (1,2), (2,1), (2,4), (4,2) и т.п.
Сочетаниями без повторений из n элементов по m называются неупорядоченные выборки без повторений элементов множества, которые отличаются одна от другой только составом элементов. Иными словами, это любые подмножества исходного множества, состоящие из m элементов.
Пусть дано множество M={1,2,3,4,5}. Тогда сочетаниями из 5 элементов по 2 будут выборки (1,2), (2,4), (5,2) и т.п. (Здесь (2,4)~(4,2)…)
Число сочетаний без повторений будем обозначать илиC(n,m).
.
Формула для числа размещений из n элементов по m была получена ранее. Если объединить размещения, отличающиеся только порядком элементов и совпадающие по составу, в классы эквивалентности, то получим, что мощность каждого из таких классов m! Тогда число сочетаний будет определяться как C(n,m)= .