Введение в концепции программирования. Series 2. Episode 3

• Множества. Основные понятия. Операции, Свойства
• Дискретная вероятность
• Математическая логика

• Определение
• Свойства
• Операции
• Ассоциативные правила

Множество: Набор объектов (элементов множества).

Примеры множеств:

• Целые числа: \( \{1, 2, 3, 4, 5, ...\} \)
• Предметы мебели: \( \{Стол, Стул, Шкаф, Кровать\} \)
• Студенты: \( \{?\} \)

Базовое понятие, не выводится из других.

Q: Какие ещё множества мы знаем?

Для любого множества \( A \) и произвольного элемента \( b \) верно ровно одно из двух высказываний:

• \( b \) входит в \( A \) (\( b \in A \))
• \( b \) НЕ входит в \( A \) (\( b \notin A \))

Пример:

• Входит ли 0 в множество {1, 2, 3}? Нет (\( 0 \notin \{1, 2, 3\} \))
• Входит ли 0 в множество {0, 1, 77, 245}? Да (\( 0 \in \{0, 1, 77, 245\} \))

• Входит ли 789 в множество целых чисел?
• Входит ли Нью-Йорк в множество городов?
• Входит ли Калининград в множество субъектов федерации?
• Входит ли Санкт-Петербург в множество субъектов федерации?
• Входит ли “Женя” в число имён мальчиков?

1. Перечислением:
   • \( \{1, 3, 5\} \);
   • \( \{1, 3, 5, ...\} \)
2. Заданием свойства (Set builder notation):
   • \( \{x: x целое \land x > 2 \land x < 10\} \)
3. Заданием надмножества и свойства:
   • \( \{x \in \mathbb{Z} : x > 2 \land x < 10\} \)

Корректно заданное множество предполагает, что определено универсальное множество \( U \) (генеральная совокупность).

• Способы описания множества присутствующих в аудитории (включая задание \( U \))

\( A \) – множество

\( n(A) \) – количество элементов (мощность) множества

Пустое множество: \( \varnothing \); \( {} \) не содержит никаких элементов

Пустое множество является подмножеством любого множества.

Универсальное множество (генеральная совокупность): \( U \) (разное для разных рассматриваемых ситуаций)

• \( n(\varnothing)=? \)
• \( \{0\} = \varnothing? \)

• \( 0 \in \varnothing ? \)

• \( U \) для переписи населения (одинаково ли в разных странах?)

• \( C \subseteq B \) ?
• \( C \subseteq A \) ?
• Какое неравенство выполняется для \( n(C), n(B), n(A) \)?
• \( C \subset B \) содержательно значит …
• \( B = A \) содержательно значит …

• Перечислить все подмножества {a}, {a, b}, {a, b, c}, {a, b, c, d}
• Перечислить все собственные подмножества {a}, {a, b}, {a, b, c}, {a, b, c, d}

• A: Студенты
  • B: Студенты 1 курса
    • C: Студенты 1 курса, посещающие факультатив
  • D: Студенты других курсов
    • E: Студенты других курсов, посещающие факультатив

• F студенты, посещающие факультатив

• \( n(B\cap D)= \)?

• \( B\cap D= \)?

• \( B\cup D= \)?

• \( F\cap D= \)?

\( S \setminus T = \left\{{x \in S: x \notin T}\right\} \)

Q Диаграмма Эйлера-Венна?

\( A^c = U ∖ A \)

Q Диаграмма Эйлера-Венна?

\( S - T = (S \setminus T) \cup (T \setminus S) \)

Q Диаграмма Эйлера-Венна?

Пусть \( A \subseteq U, B \subseteq U \).

(1) Пусть \( B\subseteq A \), тогда:

• \( n(B) <= n(A) \)
• \( n(A - B) = n(A) - n(B) \)
• \( n(B) = n(A) \implies B = A \) (!)

Q Диаграммы

Пусть \( A \subseteq U, B \subseteq U \).

(2) Пусть \( A\cap B =\varnothing \), тогда:

• \( n(A\cap B) = 0 \)
• \( n(A\cup B) = n(A) + n(B) \)

Q Диаграммы

Пусть \( A \subseteq U, B \subseteq U \).

(3) \( n(A^c) = n(U) - n(A) \)

Q Диаграммы

Преподаватель спрашивает группу:

• Как много студентов изучают академическое письмо? – 15
• Как много студентов изучают программирование? – 13
• Как много не изучают ни того, ни другого? – 5

Всего в группе 26 студентов.

Как много студентов изучают программирование, но не академическое письмо?

Противоречивые данные по Титанику: обзор

На Титанике было 1323 пассажира, о которых нам что-то известно, в том числе 86 детей и 560 взрослых в 1 и 2 классе. Найти:

• Общее количество взрослых
• Количество взрослых в 3 классе
• Количество взрослых в 3 классе и детей

Q Диаграмма?

\( A \) – взрослые, \( T \) – взрослые в 1 и 2 классе, \( L \) – взрослые в 3 классе, \( C \) – дети.

• \( n(A) = n(U) - n(C) \)
• \( n(L) = n(A) - n(T) \)

• Анализ совместных появлений (co-occurences) и ассоциаций (association analysis)
• Анализ рыночных корзин (market basket analysis)

• “Люди, которые покупают Донцову и Маринину, также покупают Дашкову”:
  • {Донцова, Маринина} \( \to \) {Дашкова}

• {Цветы, шампанское} \( \to \) ?

• Пример: Титаник

• Формирование списка транзакций (transactions):
  • {хлеб, сыр, масло}, {хлеб, сыр}, {сыр, колбаса}, {хлеб, сыр}
• Определение правил (rules) с помощью алгоритма (например, Apriori)
• Выделение интересных (нетривиальных) правил:
  • меры (характеристики): support, confidence, lift, …

• Лекцию читал: Илья Леонидович Мусабиров
• Лекция подготовлена: И. Л. Мусабиров, П. В. Окопный,
  при участии канд. пед. наук. доц Н. Г. Дмошинской
• Сайт курса: http://courses.nosoc.io
• E-mail курса: intropro2013@nosoc.io