1. Множество. Способы описания множеств. Примеры. Пустое множество. Универсальное множество. Подмножество. Собственное подмножество. Равенство множеств.

2. Операции над множествами: объединение, пересечение, разность, симметрическая разность. Дополнение множества. Примеры.

3. Свойства операций над множествами.

4. Диаграммы Эйлера – Венна. Примеры.

5. Булеан множества. Примеры. Мощность булеана конечного множества.

6. Прямое (декартово) произведение. Примеры. Число элементов в декартовом произведении п множеств.

7. Бинарное отношение на множестве. Примеры.

8. Свойства бинарных отношений: рефлексивность, антирефлексивность, симметричность, антисимметричность, транзитивность. Примеры

9. Отношение эквивалентности. Классы эквивалентности. Примеры.

10. Отношение порядка: строгого и нестрогого. Примеры. Полное отношение.

11. Отображение (функция). Примеры. Постоянная функция. Тождественная функция. Образ и прообраз множества.

12. Инъективное отображение. Сюръективное отображение. Биективное отображение.

13. Операции над отображениями. Суперпозиция отображений, ее свойства. Примеры. Обратное отображение. Примеры. Критерий обратимости отображения. Свойства операции.

14. Мощность множества. Равномощные множества. Мощность конечного множества. Первая теорема Кантора. Счетное множество. Свойства счетных множеств. Доказательство того, что множество рациональных чисел счетно. Вторая теорема Кантора. Множество мощности континуум. Примеры.

15. Граф. Неориентированный граф. Ориентированный граф. Мультиграф. Псевдограф. Примеры.

Смежность. Инцидентность. Примеры.

Степень вершины неориентированного графа. Полустепени входа и выхода вершины ориентированного графа. Примеры.

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

17. Представление графа. Матрицы смежности и инцидентности ориентированного и неориентированного графов. Примеры. Смысл элемента п-й степени матрицы смежности.

18. Полный граф. Пустой граф. Дополнение графа. Двудольный граф. Полный двудольный граф. Планарный граф. Однородный граф. Подграф. Частичный граф. Примеры.

19. Маршрут в графе. Цепь. Простая цепь. Циклический маршрут. Цикл. Простой цикл. Путь и контур в орграфе. Примеры.

20. Достижимость в неориентированном графе. Матрица достижимости, ее нахождение. Компоненты связности графа, их нахождение.

21. Достижимость и взаимная достижимость в ориентированном графе. Матрицы достижимости и сильной связности, их нахождение. Компоненты сильной связности, их нахождение.

22. Нахождение кратчайшего пути между двумя вершинами в невзвешенном ориентированном графе. Волновой алгоритм.

23. Взвешенный граф. Нахождение кратчайшего пути между двумя заданными вершинами во взвешенном ориентированном графе. Алгоритм Дейкстры.

24. Нахождение кратчайшего пути между всеми парами вершин во взвешенном ориентированном графе. Алгоритм Флойда.

25. Центр и медиана взвешенного ориентированного графа. Их нахождение.

26. Лес. Дерево. Остовное дерево. Цикломатическое число графа. Нахождение минимального остовного дерева. Алгоритм Прима.

27. Основной принцип комбинаторики. Перестановки. Размещения с повторениями. Размещения без повторений. Сочетания без повторений. Биномиальные коэффициенты и их свойства. Сочетания с повторениями. Примеры.

1.Множество. Способы описания множеств. Примеры. Пустое множество. Универсальное множество. Подмножество. Собственное подмножество. Равенство множеств.

Множество совокупность объектов (элементов).

Важно отметить, что множество ПОЛНОСТЬЮ

характеризуется набором своих элементов. Множество считается заданным, если определены все его элементы. Обозначаются: А, В.

Элементы обозначаются: a,b.

Например: a ∈A, a ∉A.

Способы описания:

1)Перечислением всех элементов множества в фигурных скобках.

ПРИМЕР

A = {Оля, Маша, Саша}

M = {1, 2, 3, 4, 5, 6, 7}

2)С помощью указания свойства всех элементов, входящих в множество. Характеристический предикат записывается после двоеточия или символа « | ».

ПРИМЕР

Р(x) = x N  x < 8 - характеристический предикат.

M = {x : Р(x)}  или  M = {x : x N   x < 8}.

Множество не содержащее ни одного элемента называется пустым (обозначается: Ø).

Множества из элементов которого составляем конкретное множество называется универсальным (обозначается: U).

Если всякий элемент множества A

является элементом множества B, то A называется подмножеством B, обозначение: A ∈ B.

Если каждый элемент множества A входит в B, но множество B содержит хотя бы один элемент, не входящий в A, т. е. если   и  , то A называется собственным подмножеством B, а B -собственным надмножеством A. В этом случае пишут  . Например, запись   и  означают одно и то же, а именно, что множество A не пусто.

Два множества назовем равными, если все элементы множества А будут содержаться во множестве В, и все элементы множества В будут содержаться во множестве А.

2.Операции над множествами: объединение, пересечение, разность, симметрическая разность. Дополнение множества. Примеры.

Операции над множествами:

1.Объединением множеств A и B называется множество A U B,,

состоящее из элементов, каждый из которых принадлежит хотя бы

одному из множеств A,B. Иначе говоря, A U B={a: a ∈A или a ∈B}.

2.Пересечением множеств A и B называется множество A ⋂ B,

состоящее из элементов, каждый из которых принадлежит обоим

множествам A,B, т.е. A ⋂B={a: a∈A и a∈B}.

Объединение множеств также называется суммой множеств, а

пересечение – произведением.

3.Разностью множеств A и B называется множество A\B,

образованное элементами, каждый из которых входит в A и не

входит в B, т.е. A\B={a: a∈A, a∉B}.

4.Еще одна операция, которая достаточно широко используется

- симметрическая разность A∆B=(A\B) U (B\A)=(A U B)\(A ⋂ B).

Полезное свойство симметрической разности состоит в том, что A ∆ B= ∅ тогда и только тогда, когда A=B.

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

Пусть  . Тогда 

3.Свойства операций над множествами.

1. (Коммутативность) AUB=BUA, A⋂B=B⋂A.

2. (Ассоциативность) (AUB)UС=AU(BUС). Эти свойства

также очевидны. Они позволяют опускать скобки, не опасаясь

разночтений.

3. (Дистрибутивность объединения относительно

пересечения) (AUB)⋂С=(AUС)⋂(BUС).

Закон Де моргана:

а или не а, третьего не дано.

1. ~(a & b) == ~a v ~b - закон Де Моргана

2. ~(a v b) == ~a & ~b - закон Де Моргана

3. a & b == ~(~a v ~b) - закон Де Моргана

4. a v b == ~(~a & ~b) - закон Де Моргана