Основы теории множеств

Август 21, 2022

Главная
Математика
Основы теории множеств

Содержание

2. Основные понятия Множество – совокупность определенных различаемых объектов, причем таких, что для каждого можно установить, принадлежит
3. Основные понятия Множества могут быть конечными, бесконечными и пустыми. Множество, содержащее конечное число элементов, называется конечным.
4. Основные понятия Множество ? называют подмножеством множества ? (обозначается ?⊆?), если всякий элемент множества ? является
5. Основные понятия Множества ? и ? равны (?=?) тогда и только тогда, когда ?⊆?, и ?⊆?,
6. Основные понятия
7. Способы задания множеств Задание множеств списком предполагает перечисление элементов. Пример: A={a, b , c , d}
8. Способы задания множеств Пример: B={b⏐b=π/2±kπ, k∈N0}, N0 – множество всех натуральных чисел; M2n=1, 2, 4, 8,
9. Способы задания множеств Так, «множество всех хороших песен 2013 года» каждый составит по-разному. Надежным способом однозначного
10. Способы задания множеств Графическое задание множеств (диаграммы Эйлера-Венна) Замкнутая линия-круг Эйлера ограничивает множество, а рамка -
11. Операции над множествами Объединением множеств ? и ? (?∪?) называется множество, состоящее из всех тех элементов,
12. Операции над множествами Пересечением множеств A и B (A∩B) называется множество, состоящее из элементов, входящих как
13. Операции над множествами Разностью множеств A и B (A\B) называется множество всех элементов множества A, которые
14. Операции над множествами Симметричная разность множеств A и B (AΔB) AΔB=(A∪B)\(A∩B) Дано: A={1, 2, 4, 6}
15. Операции над множествами Приоритет выполнения операций: дополнение, затем пересечение и только потом объединение и разность.
16. § 9. Основы теории графов
17. Основные понятия Теория графов - мощное средство исследования и решения многих задач, возникающих при изучении больших
18. Основные понятия Графы могут быть: ориентированными, неориентированными, смешанными. Если ребра у множества A ориентированы (показывается стрелкой),
19. Основные понятия Если ребра не имеют ориентации, то граф называется неориентированным. Граф, в котором присутствуют и
20. Способы задания графов Теоретико-множественное представление графов. Граф описывается перечислением множества вершин и дуг. G=(X, A), где
21. Способы задания графов Задание графов соответствием. Граф описывается заданием множества вершин Х и соответствия Г, которое
22. Способы задания графов
23. Способы задания графов 3.2. Матрица инциденций представляет собой прямоугольную матрицу размером n x m, где n
24. Пример
25. Структура графа Дан граф ?=(?, ?). Подграф - граф ?’=(?’, ?’), полученный из исходного удалением части
26. Структура графа Вершина ? называется достижимой из вершины ?, если существует маршрут из ? в ?.
27. Задача Березовое: 8:00 Полевое Б 16:00 07:30 11:50 14:00 14:40 16:10
28. Методы обхода графа Под обходом графа понимается перебор его вершин в определенном порядке, связанный с проходом
29. Пример Дан граф G=(V, E). Последовательность вершин поиска в глубину: 1-2-4-6-8-9-7-10-5-3 Поиск в глубину
30. Поиск начинается с некоторой фиксированной вершины v, просматриваются все вершины на расстоянии одного ребра от начальной
31. Граф G=(V, E) называется взвешенным, если каждому ребру v поставлено в соответствие некоторое число, называемое его
32. Рядом с каждой вершиной установим метку – длина кратчайшего пути в эту вершину из вершины 1
33. Определим кратчайшее расстояние от вершины 1 до соседних вершин 2, 3 и 6. Все соседи вершины
34. Определяем «ближайшую» из непосещенных вершин. Это вершина 2 с меткой 7. Соседи – вершины 1, 3
35. Определяем «ближайшую» из непосещенных вершин - вершина 3 с меткой 9. Меняем метки: вершина 4 и
36. Определяем «ближайшую» из непосещенных вершин - вершина 6 с меткой 11. Меняем метки: вершина 5. Вершину
38. Скачать презентацию

Слайд 2

Основные понятия
Множество – совокупность определенных различаемых объектов, причем таких, что для

каждого можно установить, принадлежит этот объект данному множеству или нет.
Элементы множества обозначаются маленькими буквами, сами множества - большими. Принадлежность элемента множеству ? обозначается так: m∈?, где знак является стилизацией первой буквы греческого слова ∈στι(есть, быть), знак непринадлежности - ∉.

Слайд 3

Основные понятия
Множества могут быть конечными, бесконечными и пустыми.
Множество, содержащее конечное

число элементов, называется конечным. Если множество не содержит ни одного элемента, то оно называется пустым и обозначается ∅.
Пример:
? - множество студентов потока - конечное множество;
? - множество звезд во Вселенной - бесконечное множество;
? - множество студентов потока, хорошо знающих три иностранных языка (японский, китайский и французский) – видимо, пустое множество.

Слайд 4

Основные понятия
Множество ? называют подмножеством множества ? (обозначается ?⊆?), если всякий

элемент множества ? является элементом множества ?:
?⊆?⟷?∈?⟶?∈?.
Множество ? содержит ?, или ? покрывает ?. Не включение подмножества ? в множество ? обозначается так: ?⊄?.

Слайд 5

Основные понятия
Множества ? и ? равны (?=?) тогда и только тогда,

когда ?⊆?, и ?⊆?, т. е. элементы множеств ? и ? совпадают.
Множество ? называется собственным подмножеством множества ?, если ?⊆?, а ?⊄?. Обозначается так: ?⊂?.
Пример
?={?,?,?,?,?,?}, ?={?,?,?}, ?⊂?.
Мощностью конечного множества ? называется число его элементов. Обозначается ⏐?⏐, например ⏐?⏐=6, ⏐?⏐=3.
Принято считать, что пустое множество ∅ является подмножеством любого множества.

Слайд 6

Основные понятия

Слайд 7

Способы задания множеств
Задание множеств списком предполагает перечисление элементов.
Пример:
A={a, b , c

, d}
{0, 2, 3, 4}= { 3, 4, 2, 0 } = { 4, 0, 2, 3 }=...
Задание множеств порождающей процедурой или арифметическими операциями означает описание характеристических свойств элементов множества:
X={x⏐H(x)},
т.е. множество X содержит такие элементы x, которые обладают свойством H(x).

Слайд 8

Способы задания множеств
Пример:
B={b⏐b=π/2±kπ, k∈N0},
N0 – множество всех натуральных чисел;
M2n=1, 2,

4, 8, 16, … или M2n= {m⏐m=2n, n∈N0}
C=A+B={x⏐x=a+b, a∈A, b∈B }
Задание множества описанием свойств элементов:
Пример:
? - это множество чисел, являющихся степенями двойки.
К описанию свойств естественно предъявить требования точности и недвусмысленности.

Слайд 9

Способы задания множеств
Так, «множество всех хороших песен 2013 года» каждый составит

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

Слайд 10

Способы задания множеств
Графическое задание множеств (диаграммы Эйлера-Венна)
Замкнутая линия-круг Эйлера ограничивает множество,

а рамка - универсальное пространство E. Заданы два множества: A={a, b, c} и B={b, d, e, f}. Если элементов множеств немного, то они могут на диаграмме указываться явно.

Слайд 11

Операции над множествами
Объединением множеств ? и ? (?∪?) называется множество, состоящее

из всех тех элементов, которые принадлежат хотя бы одному из множеств ? или ?.
?∪?={?|?∈? или ?∈?}.

Дано:
A={1, 2, 4, 6} и
B={0, 3, 4, 6}
Найти С=?∪?
Решение:
C={0, 1, 2, 3, 4, 6}

Слайд 12

Операции над множествами
Пересечением множеств A и B (A∩B) называется множество, состоящее

из элементов, входящих как в множество A, так и в множество B.
?∩?={?|?∈? и ?∈?}

Дано:
A={1, 2, 4, 6} и
B={0, 3, 4, 6}
Найти С=?∩?
Решение:
C={4, 6}

Слайд 13

$Операции над множествами Разностью множеств A и B (A\B) называется множество$

Операции над множествами
Разностью множеств A и B (A\B) называется множество всех

элементов множества A, которые не содержатся в B.
A\B={?|?∈A и ?∉B}
B\A={?|?∈B и ?∉A}

Дано:
A={1, 2, 4, 6} и
B={0, 3, 4, 6}
Найти С=?\?, D=B\A
Решение:
C={1, 2}, D={0, 3}
На рисунке B\A

Слайд 14

$Операции над множествами Симметричная разность множеств A и B (AΔB) AΔB=(A∪B)\(A∩B)$

Операции над множествами
Симметричная разность множеств A и B (AΔB)
AΔB=(A∪B)\(A∩B)
Дано:
A={1, 2, 4,

6} и
B={0, 3, 4, 6}
Найти С=?Δ?
Решение:
C={0, 1, 2, 3, 4, 6}\{4, 6}=
{0, 1, 2, 3}

Слайд 15

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

Приоритет выполнения операций: дополнение, затем пересечение и только потом

объединение и разность.

Слайд 16

§ 9. Основы теории графов

Слайд 17

Основные понятия
Теория графов - мощное средство исследования и решения многих задач,

возникающих при изучении больших и сложных систем. Графы встречаются во многих областях под разными названиями: «структуры» в гражданском строительстве, «сети» – в электронике, «социограммы» – в социологии и экономике, «молекулярные структуры» – в химии, «дорожные карты», электрические или газовые распределительные сети и т. д.
Графом G принято называть пару (X, A), где X={xi}- конечное непустое множество вершин, A={ai} – набор ребер (набор в отличие от множества может содержать несколько элементов по несколько раз).

Слайд 18

Основные понятия
Графы могут быть:
ориентированными,
неориентированными,
смешанными.
Если ребра у множества A ориентированы (показывается стрелкой),

то они называются дугами, и граф с такими ребрами называется ориентированным графом или орграфом.

Слайд 19

Основные понятия
Если ребра не имеют ориентации, то граф называется неориентированным.

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

Слайд 20

Способы задания графов
Теоретико-множественное представление графов. Граф описывается перечислением множества вершин и

дуг.

G=(X, A),
где
X={xi},
i=1, 2, 3, 4 – множество вершин;
А={ai},
i=1, 2, …, 6 – множество дуг, причем А={(x1, x2), (x4, x2), (x2, x4), (x2, x3), (x3, x3), (x4, x1)}.

Слайд 21

Способы задания графов
Задание графов соответствием. Граф описывается заданием множества вершин Х

и соответствия Г, которое показывает, как между собой связаны вершины.

G=(X, Г),
где
X={xi},
i=1, 2, 3, 4 – множество вершин;
Г(x1)={x2},
Г(x2)={x3, х4},
Г(x3)={x3},
Г(x4)={x1,х2}– отображения.
Отображение вершины xi – множество вершин, в которые существуют дуги из вершины xi.

Слайд 22

Способы задания графов

Слайд 23

Способы задания графов
3.2. Матрица инциденций представляет собой прямоугольную матрицу размером n

x m,
где n – количество вершин графа,
m – количество дуг графа.
Обозначается матрица инциденций
B = {bij}, i = 1, 2, ..., n, j = 1, 2, ..., m .
Каждый элемент матрицы определяется следующим образом:
bij = 1, если хi является начальной вершиной дуги aj,
bij = –1, если хi является конечной вершиной дуги aj,
bij = 0, если хi не является концевой вершиной дуги aj или если aj является петлей.
Таким образом, нулевой столбец j в матрице инциденций свидетельствует о том, что дуга aj яляется петлей.

Слайд 24

Пример

Слайд 25

Структура графа

Дан граф ?=(?, ?). Подграф - граф ?’=(?’, ?’), полученный

из исходного удалением части вершин вместе с инцидентными им ребрами. Надграф - исходный граф по отношению к подграфу. Всего из одного графа можно получить 2n подграфов.
Маршрут между вершинами ? и ? в графе ?=(?,?) - последовательность ребер вида (?, ?1), (?1, ?2), (?2, ?3),…, (??−1,??), (??, ?).
Маршрут, у которого начальная вершина совпадает с конечной, называется циклом.
(1,2), (2, 3) – маршрут из 1 в 3
(2, 3), (3, 4), (4, 2) - цикл

Слайд 26

Структура графа

Вершина ? называется достижимой из вершины ?, если существует маршрут

из ? в ?. Вершины ? и ? взаимнодостижимы, если существует маршрут из ? в ? и маршрут из ? в ?. Для неориентированных графов достижимость вершин влечет взаимодостижимость.
Вершина графа, для которой не существует достижимых вершин, и которая не достижима из других вершин называется изолированной. Очевидно, что вершина изолирована тогда и только тогда, когда у нее нет инцедентных ребер.

Слайд 27

Задача
Березовое: 8:00
Полевое
Б
16:00
07:30
11:50
14:00
14:40
16:10

Слайд 28

Методы обхода графа

Под обходом графа понимается перебор его вершин в определенном

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

Поиск в глубину

Поиск начинается с некоторой фиксированной вершины v0, затем выбирается произвольная вершина u, смежная с v0, и поиск повторяется от u. Если же не существует ни одной новой вершины, смежной с v, то необходимо вернуться в вершину, из которой попали в v и продолжить поиск.

Слайд 29

Пример
Дан граф G=(V, E).
Последовательность вершин поиска в глубину:
1-2-4-6-8-9-7-10-5-3
Поиск в глубину

Слайд 30

Поиск начинается с некоторой фиксированной вершины v, просматриваются все вершины на

расстоянии одного ребра от начальной вершины v. Затем на расстоянии двух ребер и т.д.

Поиск в ширину

1-2-3-4-5-6-7-8-9-10

Слайд 31

Граф G=(V, E) называется взвешенным, если каждому ребру v поставлено в

соответствие некоторое число, называемое его весом.

Поиск кратчайшего пути

В 1959г. нидерландский ученый Эдсгер Вибе Дейкстра изобрел алгоритм на графах, определяющий кратчайшее расстояние от одной из вершин графа до всех остальных. Алгоритм работает только для графов без ребер отрицательного веса.

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

Слайд 32

Рядом с каждой вершиной установим метку – длина кратчайшего пути в

эту вершину из вершины 1 или знак ∞, если длина пути не определена.

Поиск кратчайшего пути

∞

Слайд 33

Определим кратчайшее расстояние от вершины 1 до соседних вершин 2,

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

Поиск кратчайшего пути

∞

Слайд 34

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

Соседи – вершины 1, 3 и 4. Т.к. вершина 1 посещена, с ней ничего не делаем. Т.к. путь к вершине 3 это 7+10=17>9, то тоже ничего не делаем.
Вершина 4: 7+15=22<∞, меняем метку.
Вершину 2 замораживаем.

Поиск кратчайшего пути

∞

Слайд 35

Определяем «ближайшую» из непосещенных вершин - вершина 3 с меткой 9.

Меняем метки: вершина 4 и вершина 6.
Вершину 3 замораживаем.

Поиск кратчайшего пути

∞

Слайд 36

Определяем «ближайшую» из непосещенных вершин - вершина 6 с меткой 11.

Меняем метки: вершина 5.
Вершину 6 замораживаем.

Поиск кратчайшего пути

∞

Основы теории множеств

Содержание

Основные понятия Множество – совокупность определенных различаемых объектов, причем таких, что для

Основные понятия Множества могут быть конечными, бесконечными и пустыми. Множество, содержащее конечное

Основные понятия Множество ? называют подмножеством множества ? (обозначается ?⊆?), если всякий

Основные понятия Множества ? и ? равны (?=?) тогда и только тогда,

Основные понятия

Способы задания множествЗадание множеств списком предполагает перечисление элементов.Пример:A={a, b , c

Способы задания множествПример:B={b⏐b=π/2±kπ, k∈N0}, N0 – множество всех натуральных чисел;M2n=1, 2,

Способы задания множеств Так, «множество всех хороших песен 2013 года» каждый составит

Способы задания множеств Графическое задание множеств (диаграммы Эйлера-Венна) Замкнутая линия-круг Эйлера ограничивает множество,

Операции над множествами Объединением множеств ? и ? (?∪?) называется множество, состоящее

Операции над множествами Пересечением множеств A и B (A∩B) называется множество, состоящее

Операции над множествами Разностью множеств A и B (A\B) называется множество всех

Операции над множествами Симметричная разность множеств A и B (AΔB)AΔB=(A∪B)\(A∩B)Дано:A={1, 2, 4,

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

§ 9. Основы теории графов

Основные понятия Теория графов - мощное средство исследования и решения многих задач,

Основные понятия Графы могут быть:ориентированными,неориентированными,смешанными. Если ребра у множества A ориентированы (показывается стрелкой),

Основные понятия Если ребра не имеют ориентации, то граф называется неориентированным.

Способы задания графовТеоретико-множественное представление графов. Граф описывается перечислением множества вершин и

Способы задания графовЗадание графов соответствием. Граф описывается заданием множества вершин Х

Способы задания графов

Способы задания графов3.2. Матрица инциденций представляет собой прямоугольную матрицу размером n

Пример

Структура графа Дан граф ?=(?, ?). Подграф - граф ?’=(?’, ?’), полученный

Структура графа Вершина ? называется достижимой из вершины ?, если существует маршрут

ЗадачаБерезовое: 8:00ПолевоеБ16:0007:3011:5014:0014:4016:10

Методы обхода графа Под обходом графа понимается перебор его вершин в определенном

Пример Дан граф G=(V, E). Последовательность вершин поиска в глубину:1-2-4-6-8-9-7-10-5-3Поиск в глубину

Поиск начинается с некоторой фиксированной вершины v, просматриваются все вершины на

Граф G=(V, E) называется взвешенным, если каждому ребру v поставлено в

Рядом с каждой вершиной установим метку – длина кратчайшего пути в

Определим кратчайшее расстояние от вершины 1 до соседних вершин 2,

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

Определяем «ближайшую» из непосещенных вершин - вершина 3 с меткой 9.

Определяем «ближайшую» из непосещенных вершин - вершина 6 с меткой 11.

Похожие презентации

Основные понятия
Множество – совокупность определенных различаемых объектов, причем таких, что для

Основные понятия
Множества могут быть конечными, бесконечными и пустыми.
Множество, содержащее конечное

Основные понятия
Множество ? называют подмножеством множества ? (обозначается ?⊆?), если всякий

Основные понятия
Множества ? и ? равны (?=?) тогда и только тогда,

Способы задания множеств
Задание множеств списком предполагает перечисление элементов.
Пример:
A={a, b , c

Способы задания множеств
Пример:
B={b⏐b=π/2±kπ, k∈N0},
N0 – множество всех натуральных чисел;
M2n=1, 2,

Способы задания множеств
Так, «множество всех хороших песен 2013 года» каждый составит

Способы задания множеств
Графическое задание множеств (диаграммы Эйлера-Венна)
Замкнутая линия-круг Эйлера ограничивает множество,

Операции над множествами
Объединением множеств ? и ? (?∪?) называется множество, состоящее

Операции над множествами
Пересечением множеств A и B (A∩B) называется множество, состоящее

Операции над множествами
Разностью множеств A и B (A\B) называется множество всех

Операции над множествами
Симметричная разность множеств A и B (AΔB)
AΔB=(A∪B)\(A∩B)
Дано:
A={1, 2, 4,

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

Приоритет выполнения операций: дополнение, затем пересечение и только потом

Основные понятия
Теория графов - мощное средство исследования и решения многих задач,

Основные понятия
Графы могут быть:
ориентированными,
неориентированными,
смешанными.
Если ребра у множества A ориентированы (показывается стрелкой),

Основные понятия
Если ребра не имеют ориентации, то граф называется неориентированным.

Способы задания графов
Теоретико-множественное представление графов. Граф описывается перечислением множества вершин и

Способы задания графов
Задание графов соответствием. Граф описывается заданием множества вершин Х

Способы задания графов
3.2. Матрица инциденций представляет собой прямоугольную матрицу размером n

Структура графа

Дан граф ?=(?, ?). Подграф - граф ?’=(?’, ?’), полученный

Структура графа

Вершина ? называется достижимой из вершины ?, если существует маршрут

Задача
Березовое: 8:00
Полевое
Б
16:00
07:30
11:50
14:00
14:40
16:10

Методы обхода графа

Под обходом графа понимается перебор его вершин в определенном

Пример
Дан граф G=(V, E).
Последовательность вершин поиска в глубину:
1-2-4-6-8-9-7-10-5-3
Поиск в глубину