Дискретный анализ

и информатики.
Курс читается весь год по 1 разу в неделю.

Во втором семестре упражнения – 1 раз в две недели.
В первом семестре зачет, во втором экзамен.

она подходит нам в максимальной степени.
По отдельным вопросам есть

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

написать такую программу и получить отлично на экзамене. Но это

дело не простое.

ними
Сжатие и защита информации
Поиск и организация информации

множеств
Разность множеств
Симметрическая разность множеств
Пустое множество
Мощность множества – число элементов в

нем (для конечных множеств)

B
A=
|A|
$a\in A$
$a\notin A$
$A\subset B$
$A\cap B$
$A\cup B$
$A\setminus B$
$A\Delta B$
$A=\nothing$
$|A|$

условная запись соответствующих формул, применяемая в специальном языке для набора

научных текстов.
Этот язык и его программная поддержка были разработаны знаменитым американским математиком и программистом Дональдом Эрвином Кнутом (Donald E. Knuth).
Язык называется TeX. Вы обязательно должны будете им овладеть.

если $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$.

– Rene Descartes)
Разбиение множества

Прямым произведением этих множеств называется множество всевозможных пар {(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,c,d,e,f,g,h} и множества строк 1:8

является произведением множества мастей {,,,} на множество значений {A,K,D,J,T,9,8,7,6,5,4,3,2}.
При добавлении

джокеров это свойство теряется – расширенная колода в произведение двух множеств не раскладывается.

можно представить как произведение множества 0:5, задающего десятки секунд, и

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

и B заданы упорядочения, то на их произведении C=AB естественно

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

= 0:5 заданы нумерации, то на их произведении C=AB естественно

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

мощностей.

Доказательство прямо следует из определения произведения чисел.

конечных множеств A1, A2, … , Ak.
A1A2… Ak=
{(a1, a2, …

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

из нулей и единиц длины k.
Очевидно, что |Bk|=2k.
Вы, конечно, уже

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

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

дизъюнктны и объединение которых равно 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.

и B={Bj}j1:m.
Будем говорить, что разбиение B мельче разбиения A, и

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

A={Ai}i1:k и B={Bj}j1:m.
Разбиение C={Cr}r1:n называется произведением разбиений A и B,

если оно является самым крупным из разбиений, которые мельче и 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’.

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, и все доказано.
Осталось выкинуть из построенного набора пустые множества, и он станет искомым разбиением.

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}. Постройте произведение этих разбиений.