🗊 Дискретный анализ Лекция 1 Введение. Некоторые понятия теории множеств

Категория: Алгебра
Нажмите для полного просмотра!
Дискретный анализ Лекция 1 Введение. Некоторые понятия теории множеств , слайд №1 Дискретный анализ Лекция 1 Введение. Некоторые понятия теории множеств , слайд №2 Дискретный анализ Лекция 1 Введение. Некоторые понятия теории множеств , слайд №3 Дискретный анализ Лекция 1 Введение. Некоторые понятия теории множеств , слайд №4 Дискретный анализ Лекция 1 Введение. Некоторые понятия теории множеств , слайд №5 Дискретный анализ Лекция 1 Введение. Некоторые понятия теории множеств , слайд №6 Дискретный анализ Лекция 1 Введение. Некоторые понятия теории множеств , слайд №7 Дискретный анализ Лекция 1 Введение. Некоторые понятия теории множеств , слайд №8 Дискретный анализ Лекция 1 Введение. Некоторые понятия теории множеств , слайд №9 Дискретный анализ Лекция 1 Введение. Некоторые понятия теории множеств , слайд №10 Дискретный анализ Лекция 1 Введение. Некоторые понятия теории множеств , слайд №11 Дискретный анализ Лекция 1 Введение. Некоторые понятия теории множеств , слайд №12 Дискретный анализ Лекция 1 Введение. Некоторые понятия теории множеств , слайд №13 Дискретный анализ Лекция 1 Введение. Некоторые понятия теории множеств , слайд №14 Дискретный анализ Лекция 1 Введение. Некоторые понятия теории множеств , слайд №15 Дискретный анализ Лекция 1 Введение. Некоторые понятия теории множеств , слайд №16 Дискретный анализ Лекция 1 Введение. Некоторые понятия теории множеств , слайд №17 Дискретный анализ Лекция 1 Введение. Некоторые понятия теории множеств , слайд №18 Дискретный анализ Лекция 1 Введение. Некоторые понятия теории множеств , слайд №19 Дискретный анализ Лекция 1 Введение. Некоторые понятия теории множеств , слайд №20 Дискретный анализ Лекция 1 Введение. Некоторые понятия теории множеств , слайд №21 Дискретный анализ Лекция 1 Введение. Некоторые понятия теории множеств , слайд №22 Дискретный анализ Лекция 1 Введение. Некоторые понятия теории множеств , слайд №23 Дискретный анализ Лекция 1 Введение. Некоторые понятия теории множеств , слайд №24 Дискретный анализ Лекция 1 Введение. Некоторые понятия теории множеств , слайд №25 Дискретный анализ Лекция 1 Введение. Некоторые понятия теории множеств , слайд №26 Дискретный анализ Лекция 1 Введение. Некоторые понятия теории множеств , слайд №27
Скачать

Содержание ▲

Вы можете ознакомиться и скачать Дискретный анализ Лекция 1 Введение. Некоторые понятия теории множеств . Презентация содержит 27 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1


Дискретный анализ Лекция 1 Введение. Некоторые понятия теории множеств
Описание слайда:
Дискретный анализ Лекция 1 Введение. Некоторые понятия теории множеств

Слайд 2


Организационные вопросы Лектор – Романовский Иосиф Владимирович, профессор кафедр исследования операций и информатики. Курс читается весь год по 1 разу в неделю. Во втором семестре упражнения – 1 раз в две недели. В первом семестре зачет, во втором экзамен.
Описание слайда:
Организационные вопросы Лектор – Романовский Иосиф Владимирович, профессор кафедр исследования операций и информатики. Курс читается весь год по 1 разу в неделю. Во втором семестре упражнения – 1 раз в две недели. В первом семестре зачет, во втором экзамен.

Слайд 3


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

Слайд 4


Дополнительный материал Комплекс DA_Demo демонстрационных программ по отдельным темам курса. Можно написать такую программу и получить отлично на экзамене. Но это дело не простое.
Описание слайда:
Дополнительный материал Комплекс DA_Demo демонстрационных программ по отдельным темам курса. Можно написать такую программу и получить отлично на экзамене. Но это дело не простое.

Слайд 5


Программа 1-го семестра Немного теории множеств Комбинаторика Элементы теории вероятностей Строки и работа с ними Сжатие и защита информации Поиск и организация информации
Описание слайда:
Программа 1-го семестра Немного теории множеств Комбинаторика Элементы теории вероятностей Строки и работа с ними Сжатие и защита информации Поиск и организация информации

Слайд 6


Некоторые понятия теории множеств Вам должны быть знакомы понятия Множество Элемент множества Пересечение множеств Объединение множеств Разность множеств Симметрическая разность множеств Пустое множество Мощность множества – число элементов в нем (для конечных множеств)
Описание слайда:
Некоторые понятия теории множеств Вам должны быть знакомы понятия Множество Элемент множества Пересечение множеств Объединение множеств Разность множеств Симметрическая разность множеств Пустое множество Мощность множества – число элементов в нем (для конечных множеств)

Слайд 7


Запись введенных обозначений aA aA A  B A  B A  B A\B A  B A= |A|
Описание слайда:
Запись введенных обозначений aA aA A  B A  B A  B A\B A  B A= |A|

Слайд 8


Объяснение правого столбца Тексты, записанные в правом столбце таблицы, - это условная запись соответствующих формул, применяемая в специальном языке для набора научных текстов. Этот язык и его программная поддержка были разработаны знаменитым американским математиком и программистом Дональдом Эрвином Кнутом (Donald E. Knuth). Язык называется TeX. Вы обязательно должны будете им овладеть.
Описание слайда:
Объяснение правого столбца Тексты, записанные в правом столбце таблицы, - это условная запись соответствующих формул, применяемая в специальном языке для набора научных текстов. Этот язык и его программная поддержка были разработаны знаменитым американским математиком и программистом Дональдом Эрвином Кнутом (Donald E. Knuth). Язык называется TeX. Вы обязательно должны будете им овладеть.

Слайд 9


Прочтите и поймите тексты Говорят, что множества $A$ и $B$ дизъюнктны, если $A\cap B=\nothing$. Для любых $A$ и $B$ справедлива следующая формула $|A\cap B|+|A\cup B|=|A|+|B|$. Для любых $A$, $B$ и $C$ справедлива формула $(A\cap C)\cup(B\cap C)=(A\cup B)\cap C$. Множество целых чисел от $k$ до $l$, где $k\leq l$, мы будем обозначать через $k:l$. (Здесь введено новое обозначение: $\leq$ используется для символа  (less or equal).) Таким образом, $1:37 \cup 30:60 = 1:60$. Напишите, чему равны $1:37\cap 30:60$ и $1:37\Delta 30:60$.
Описание слайда:
Прочтите и поймите тексты Говорят, что множества $A$ и $B$ дизъюнктны, если $A\cap B=\nothing$. Для любых $A$ и $B$ справедлива следующая формула $|A\cap B|+|A\cup B|=|A|+|B|$. Для любых $A$, $B$ и $C$ справедлива формула $(A\cap C)\cup(B\cap C)=(A\cup B)\cap C$. Множество целых чисел от $k$ до $l$, где $k\leq l$, мы будем обозначать через $k:l$. (Здесь введено новое обозначение: $\leq$ используется для символа  (less or equal).) Таким образом, $1:37 \cup 30:60 = 1:60$. Напишите, чему равны $1:37\cap 30:60$ и $1:37\Delta 30:60$.

Слайд 10


Новые понятия Декартово или прямое произведение множеств (это портрет Рене Декарта – Rene Descartes) Разбиение множества
Описание слайда:
Новые понятия Декартово или прямое произведение множеств (это портрет Рене Декарта – Rene Descartes) Разбиение множества

Слайд 11


Прямое произведение множеств Пусть заданы два (конечных) множества A и B. Прямым произведением этих множеств называется множество всевозможных пар {(a,b)}, где a пробегает все множество A, а b пробегает все множество B. Можно это записать так AB= {(a,b) | aA, bB} Или в ТеХе $A\times B=\{(a,b)\,|\,a\in A,b\in B\}$ Очевидно, что равенство AB= BA верно не всегда.
Описание слайда:
Прямое произведение множеств Пусть заданы два (конечных) множества A и B. Прямым произведением этих множеств называется множество всевозможных пар {(a,b)}, где a пробегает все множество A, а b пробегает все множество B. Можно это записать так AB= {(a,b) | aA, bB} Или в ТеХе $A\times B=\{(a,b)\,|\,a\in A,b\in B\}$ Очевидно, что равенство AB= BA верно не всегда.

Слайд 12


Пример 1. Шахматная доска Множество клеток шахматной доски можно рассматривать как прямое произведение множества столбцов {a,b,c,d,e,f,g,h} и множества строк 1:8
Описание слайда:
Пример 1. Шахматная доска Множество клеток шахматной доски можно рассматривать как прямое произведение множества столбцов {a,b,c,d,e,f,g,h} и множества строк 1:8

Слайд 13


Пример 2. Колода игральных карт в 52 листа Колода игральных карт является произведением множества мастей {} на множество значений {A,K,D,J,T,9,8,7,6,5,4,3,2}. При добавлении джокеров это свойство теряется – расширенная колода в произведение двух множеств не раскладывается.
Описание слайда:
Пример 2. Колода игральных карт в 52 листа Колода игральных карт является произведением множества мастей {} на множество значений {A,K,D,J,T,9,8,7,6,5,4,3,2}. При добавлении джокеров это свойство теряется – расширенная колода в произведение двух множеств не раскладывается.

Слайд 14


Пример 3. Множество секунд в минуте Множество 60 секунд одной минуты можно представить как произведение множества 0:5, задающего десятки секунд, и множества 0:9, задающего единицы внутри десятки. Таким образом пара (3,7) определяет 37-ю секунду минуты, если считать от нулевой секунды. Аналогично можно описывать множество минут в часе, а множество часов в сутках так не описать. Можно только разбить сутки на две половины.
Описание слайда:
Пример 3. Множество секунд в минуте Множество 60 секунд одной минуты можно представить как произведение множества 0:5, задающего десятки секунд, и множества 0:9, задающего единицы внутри десятки. Таким образом пара (3,7) определяет 37-ю секунду минуты, если считать от нулевой секунды. Аналогично можно описывать множество минут в часе, а множество часов в сутках так не описать. Можно только разбить сутки на две половины.

Слайд 15


Еще о примере 3 Отметим еще, что если на множествах A и B заданы упорядочения, то на их произведении C=AB естественно возникает еще и упорядочение: предшествование пары (a,b) паре (a’,b’) означает, что либо a предшествует a’ в упорядочении множества A, либо a = a’, но b предшествует b’ в упорядочении множества B. Такое упорядочение называется лексикографическим. Дальше мы будем рассматривать более общее определение лексикографического упорядочения.
Описание слайда:
Еще о примере 3 Отметим еще, что если на множествах A и B заданы упорядочения, то на их произведении C=AB естественно возникает еще и упорядочение: предшествование пары (a,b) паре (a’,b’) означает, что либо a предшествует a’ в упорядочении множества A, либо a = a’, но b предшествует b’ в упорядочении множества B. Такое упорядочение называется лексикографическим. Дальше мы будем рассматривать более общее определение лексикографического упорядочения.

Слайд 16


Продолжение примера 3 Если на множествах A = 0:9 и B = 0:5 заданы нумерации, то на их произведении C=AB естественно возникает нумерация #C(a,b)=#B(b)|A|+#A(a). Можно считать, что у нас получилась позиционная система счисления с двухзначными числами: A – множество цифр младшего разряда, а B – старшего разряда.
Описание слайда:
Продолжение примера 3 Если на множествах A = 0:9 и B = 0:5 заданы нумерации, то на их произведении C=AB естественно возникает нумерация #C(a,b)=#B(b)|A|+#A(a). Можно считать, что у нас получилась позиционная система счисления с двухзначными числами: A – множество цифр младшего разряда, а B – старшего разряда.

Слайд 17


Мощность произведения множеств Теорема. Мощность произведения двух множеств равна произведению их мощностей. Доказательство прямо следует из определения произведения чисел.
Описание слайда:
Мощность произведения множеств Теорема. Мощность произведения двух множеств равна произведению их мощностей. Доказательство прямо следует из определения произведения чисел.

Слайд 18


Произведение нескольких множеств Аналогично предыдущему можно определить произведение любого нумерованного набора конечных множеств A1, A2, … , Ak. A1A2… Ak= {(a1, a2, … , ak)| ai Ai , i1:k} Сомножители в произведении могут быть одинаковыми. Как и раньше, |A1A2… Ak|=i1:k |Ai |. Как и раньше, если все множества упорядочены, на их произведении можно определить лексикографический порядок. Попробуйте его определить сами.
Описание слайда:
Произведение нескольких множеств Аналогично предыдущему можно определить произведение любого нумерованного набора конечных множеств A1, A2, … , Ak. A1A2… Ak= {(a1, a2, … , ak)| ai Ai , i1:k} Сомножители в произведении могут быть одинаковыми. Как и раньше, |A1A2… Ak|=i1:k |Ai |. Как и раньше, если все множества упорядочены, на их произведении можно определить лексикографический порядок. Попробуйте его определить сами.

Слайд 19


Особый случай произведения Пусть B=0:1. Множество Bk – это множество последовательностей из нулей и единиц длины k. Очевидно, что |Bk|=2k. Вы, конечно, уже знаете, что с помощью нулей и единиц представляются целые числа и что память компьютера состоит из элементов, каждый из которых хранит нуль или единицу. На следующей лекции мы будем заниматься всевозможными трактовками этого объекта.
Описание слайда:
Особый случай произведения Пусть B=0:1. Множество Bk – это множество последовательностей из нулей и единиц длины k. Очевидно, что |Bk|=2k. Вы, конечно, уже знаете, что с помощью нулей и единиц представляются целые числа и что память компьютера состоит из элементов, каждый из которых хранит нуль или единицу. На следующей лекции мы будем заниматься всевозможными трактовками этого объекта.

Слайд 20


Цилиндрические множества Пусть заданы два непустых множества A и B, и C=AB. Пусть PA. Множество R=PB называется цилиндрическим.
Описание слайда:
Цилиндрические множества Пусть заданы два непустых множества A и B, и C=AB. Пусть PA. Множество R=PB называется цилиндрическим.

Слайд 21


Разбиения Пусть задано множество A. Совокупность непустых множеств A={Ai}i1:k, которые попарно дизъюнктны и объединение которых равно A, называется разбиением A. Пример. Множество A={a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,s,t,u,v,w,x,y,z} разбито на три подмножества – красных, синих и черных букв. Эта система множеств составляет разбиение A.
Описание слайда:
Разбиения Пусть задано множество A. Совокупность непустых множеств A={Ai}i1:k, которые попарно дизъюнктны и объединение которых равно A, называется разбиением A. Пример. Множество A={a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,s,t,u,v,w,x,y,z} разбито на три подмножества – красных, синих и черных букв. Эта система множеств составляет разбиение A.

Слайд 22


Сравнение разбиений Пусть задано множество S и два его разбиения A={Ai}i1:k и B={Bj}j1:m. Будем говорить, что разбиение B мельче разбиения A, и писать B €A, если для любого Bj, j1:m, найдется такое Ai, которое содержит Bj полностью. (Мы можем сказать также, что A крупнее B ). Некоторые разбиения могут быть несравнимы, ни одно из двух не будет мельче другого. Каждое разбиение мельче и одновременно крупнее самого себя.
Описание слайда:
Сравнение разбиений Пусть задано множество S и два его разбиения A={Ai}i1:k и B={Bj}j1:m. Будем говорить, что разбиение B мельче разбиения A, и писать B €A, если для любого Bj, j1:m, найдется такое Ai, которое содержит Bj полностью. (Мы можем сказать также, что A крупнее B ). Некоторые разбиения могут быть несравнимы, ни одно из двух не будет мельче другого. Каждое разбиение мельче и одновременно крупнее самого себя.

Слайд 23


Произведение разбиений Пусть снова задано множество S и два его разбиения A={Ai}i1:k и B={Bj}j1:m. Разбиение C={Cr}r1:n называется произведением разбиений A и B, если оно является самым крупным из разбиений, которые мельче и A и B. Такого разбиения может и не существовать. Разбиения, о которых идет речь, не все сравнимы между собой. Но оказывается, что самое крупное из них, существует.
Описание слайда:
Произведение разбиений Пусть снова задано множество S и два его разбиения A={Ai}i1:k и B={Bj}j1:m. Разбиение C={Cr}r1:n называется произведением разбиений A и B, если оно является самым крупным из разбиений, которые мельче и A и B. Такого разбиения может и не существовать. Разбиения, о которых идет речь, не все сравнимы между собой. Но оказывается, что самое крупное из них, существует.

Слайд 24


Теорема о произведении разбиений Произведение C разбиений A и B существует. Доказательство. Мы просто предъявим разбиение C, а затем докажем, что это оно и есть. Образуем набор множеств C={Cij=AiBj} i1:k, j1:m Покажем, что множества Cij попарно дизъюнктны и их объединение равно S. Так что, если бы все эти множества были непусты, то C было бы разбиением. Дизъюнктность. Возьмем два различных множества Cij=AiBj и Ci’j’=Ai’Bj’ , так что либо i  i’, либо j  j’. Рассмотрим первый случай, второй аналогичен. Так как Ai  Ai’, то они не пересекаются (A - разбиение), значит не пересекаются и их подмножества Cij и Ci’j’.
Описание слайда:
Теорема о произведении разбиений Произведение C разбиений A и B существует. Доказательство. Мы просто предъявим разбиение C, а затем докажем, что это оно и есть. Образуем набор множеств C={Cij=AiBj} i1:k, j1:m Покажем, что множества Cij попарно дизъюнктны и их объединение равно S. Так что, если бы все эти множества были непусты, то C было бы разбиением. Дизъюнктность. Возьмем два различных множества Cij=AiBj и Ci’j’=Ai’Bj’ , так что либо i  i’, либо j  j’. Рассмотрим первый случай, второй аналогичен. Так как Ai  Ai’, то они не пересекаются (A - разбиение), значит не пересекаются и их подмножества Cij и Ci’j’.

Слайд 25


Продолжение доказательства Объединение равно S. Вычислим это объединение. i1:k, j1:m Cij = i1:k ( j1:m AiBj) = i1:k (Ai j1:m Bj) = i1:k (Ai S) = S Покажем теперь, что для любого разбиения D, D €A, D €B, выполняется D €C. Возьмем какой-либо элемент Ds разбиения D. Из того, что D €A, следует, что найдется Ai, Ds  Ai. Аналогично, найдется Bi, Ds  Bj. Значит, нашлось Cij, Ds  Cij, и все доказано. Осталось выкинуть из построенного набора пустые множества, и он станет искомым разбиением.
Описание слайда:
Продолжение доказательства Объединение равно S. Вычислим это объединение. i1:k, j1:m Cij = i1:k ( j1:m AiBj) = i1:k (Ai j1:m Bj) = i1:k (Ai S) = S Покажем теперь, что для любого разбиения D, D €A, D €B, выполняется D €C. Возьмем какой-либо элемент Ds разбиения D. Из того, что D €A, следует, что найдется Ai, Ds  Ai. Аналогично, найдется Bi, Ds  Bj. Значит, нашлось Cij, Ds  Cij, и все доказано. Осталось выкинуть из построенного набора пустые множества, и он станет искомым разбиением.

Слайд 26


Экзаменационные вопросы Прямое произведение множеств. Разбиения множеств. Произведение разбиений.
Описание слайда:
Экзаменационные вопросы Прямое произведение множеств. Разбиения множеств. Произведение разбиений.

Слайд 27


Упражнения 1. Пусть A={a,c,e,h,k}, B={b,c,d,e,h}. Найдите A  B, A  B, A\B, A  B. 2. Найдите A  B. 3. Сколько элементов содержит множество A  B  B  A  B  B ? 4. Пусть разбиения A и B заданы раскраской множества S: {a,b,c,d,e,f,g,h} и {a,b,c,d,e,f,g,h}. Постройте произведение этих разбиений.
Описание слайда:
Упражнения 1. Пусть A={a,c,e,h,k}, B={b,c,d,e,h}. Найдите A  B, A  B, A\B, A  B. 2. Найдите A  B. 3. Сколько элементов содержит множество A  B  B  A  B  B ? 4. Пусть разбиения A и B заданы раскраской множества S: {a,b,c,d,e,f,g,h} и {a,b,c,d,e,f,g,h}. Постройте произведение этих разбиений.

Скачать

Похожие презентации
Mypresentation.ru
Загрузить презентацию