Всем привет! Я Елена, и на канале TeachYOU мы разбираем задачи из экзаменов по информатике. Обычно я пишу статьи с разбором задач из ЕГЭ, но этот материал пригодится и 9му классу, и 11му. Если вы готовитесь к ЕГЭ и считаете, что эта тема вам не нужна, то советую заглянуть в задания 279 (прототип 24), 5627 (прототип 9) и 2557 (прототип 8) с kompege. Они намного проще решаются, когда обладаешь навыком решения задач на круги Эйлера.
Множества
Чтобы начать говорить о кругах Эйлера, нужно ввести понятие множества. Множество - это набор объектов, объединенных каким-то признаком. Например, множество квадратных объектов, множество предметов, изучаемых в 9 классе и пр.
Рассмотрим множество объектов оранжевого цвета. В него входят рыжий кот, спасательный жилет, апельсин, осенний кленовый лист, и много других объектов оранжевого цвета. На рисунке изобразим круг и будем предполагать, что все оранжевые предметы находятся внутри него:
Теперь возьмем множество животных кошачьего семейства. Здесь будут домашние кошки, тигры, львы, гепарды и остальные представители данного семейства.
Пересечение множеств
Заметим, что рыжий кот входит в оба множества. Поэтому, если мы изобразим эти множества рядом, должны будем расположить их следующим образом:
Область, в которой сидит рыжий кот, называется пересечением множеств. Множества принято обозначать заглавными латинскими буквами: A, B, C, ... Пересечение обозначают символом & : A & B, читается как "пересечение множеств A и B".
В общем случае произвольные два множества располагаются именно так: есть элементы, входящие в оба множества (то есть пересечение множеств непустое), а есть элементы, которые не входят только в одно из множеств.
Объединение
В гости к Пете едет его любимая бабушка. Она поинтересовалась у внука, что можно купить ему в подарок. Он сказал, что любит книжки и машины. В магазине бабушка увидела разные игрушки, и в блокноте изобразила круги Эйлера - один с множеством машин, второй - с множеством книжек. В пересечение этих кругов попала книга о машинах. Вне кругов расположились шарик, вертолет, матрешка и медвежонок - они не входят в множество предполагаемых подарков для Пети:
Область, похожая на перевернутую восьмерку, иллюстрирует множество машинок и книжек - подходящих подарков. Такое множество называется объединением. В него входят все элементы изначальных множеств, причем те, которые находятся на пересечении, входят только один раз:
Мощность множеств
Мощность множества - это количество элементов в нем. Обозначается так: |A|. Мощность множества может быть равна нулю (пустое множество), конечному числу (мощность множества десятичных цифр равна 10) или равна бесконечности (мощность множества натуральных чисел).
Частные случаи расположения элементов двух множеств
Случай 1. Равенство
Рассмотрим картинку с изображениями людей.
Выберем из них два множества:
- А - люди с длинными волосами
- В - женщины
Получилось, что в оба множества входят одни и те же элементы. В этом случае говорят о равенстве множеств:
- A = B - множество А равно множеству В
- A & B = A (= B) - пересечение множеств совпадает с множеством А (или В)
- А | В = А (=В) - объединение множеств равно множеству А (или В)
Что в этом случае происходит с мощностями множеств?
- |A | B| = |A & B| = |A| = |B|
Случай 2. Включение
Все элементы одного множества могут входить в другое множество - тогда говорят о включении одного множества в другое (A ⊂ B). Пусть А - множество домашних кошек. Оно включено в B - множество представителей семейства кошачьих (также можно сказать "множество домашних кошек является подмножеством множества представителей семейства кошачьих").
Заметим, что пересечение множеств в этом случае совпадает с множеством домашних кошек, а объединение - с множеством представителей семейства кошачьих:
- A ⊂ B (А включено в В, А является подмножеством В)
- A & B = A (пересечение множеств совпадает с множеством А)
- A | B = B (объединение множеств равно множеству В)
Для мощностей множеств можно сформулировать следующие утверждения:
- |A| < |B|
- |A & B| = |A|
- |A | B| = |B|
Случай 3. Непересечение
Бывает, что у множеств нет общих элементов. Про такие множества говорят, что они не пересекаются или что их пересечение равно пустому множеству (A & B = ∅). Давайте изобразим множества представителей кошачьих и собачьих (сложно придумать животного, которое будет одновременно кошкой и собакой):
- A & B = ∅ - множества не пересекаются (пересечение множеств равно пустому множеству)
О мощностях:
- |A & B| = 0
- |A | B| = |A| + |B|
Формула включения/исключения для двух областей
Вернемся к примеру с бабушкой и Петей. Пусть бабушка хочет посчитать, сколько вариантов выбрать один подарок у нее есть. Она знает мощность множества А - подарков на "машинную" тематику, мощность множества книг В и мощность их пересечения A&B.
То, что хочет найти бабушка, называется мощностью объединения множеств A | B. Логично предположить, что для его поиска нужно сложить мощности множеств A и B: 4 "машинковых" подарка + 3 книги = 7 подарков. Но на картинке видно, что всего подарков 6! Дело в том, что при суммировании мощностей множеств A и B элемент, находящийся на их пересечении, мы посчитали два раза. Тогда его нужно один раз отнять. Итого формула нахождения мощности множества объединения двух множеств такова:
|A | B| = |A| + |B| - |A & B|
Ее называют формулой включения - исключения.
Задание 8 ОГЭ по информатике
Наконец мы добрались до заданий из ОГЭ. Оговорюсь, что знание теории, описанной выше, поможет решить не все задачи - в сборниках встречаются задания на три множества. Подобные мы разберем в другой раз.
Задание 1369 с сайта К.Ю. Полякова
Задание: Ниже приведены запросы и количество страниц, которые нашел поисковый сервер по этим запросам в некотором сегменте Интернета:
шахматы | теннис 7770
теннис 5500
шахматы & теннис 1000
Сколько страниц будет найдено по запросу
шахматы?
Решение: обозначим множество страниц, которое находится по запросу шахматы как Ш, а по запросу теннис как Т. Тогда формула включения-исключения примет вид:
|Ш | Т| = |Ш| + |Т| - |Ш & Т|
Подставим в нее известные величины:
7770 = |Ш| + 5500 - 1000
И выразим неизвестную:
|Ш| = 7770 - 5500 + 1000 = 3270
Ответ: 3270
Задание 1365 с сайта К.Ю. Полякова
Задание: Ниже приведены запросы и количество страниц, которые нашел поисковый сервер по этим запросам в некотором сегменте Интернета:
лебедь & (рак | щука) 320
лебедь & рак 200
лебедь & рак & щука 50
Сколько страниц будет найдено по запросу
лебедь & щука?
Решение: может показаться, что эта задача на три множества и силами теории, описанной в этой статье, ее не решить. Но давайте заметим, что во всех строках условия встречается "лебедь &". Предлагаю на данном этапе не углубляться в теорию множеств, а довериться мне и сократить на лебедя:
лебедь & (рак | щука) 320лебедь & рак 200лебедь & рак & щука 50
Сколько страниц будет найдено по запросу
лебедь & щука?
Теперь это задача на два множества (я их фамильярно называю задачами на два кружочка). Выписываем формулу:
|Р | Щ| = |Р| + |Щ| - |Р & Щ|
Подставляем известные величины, выражаем неизвестную:
|Щ| = 320 + 50 - 200 = 170.
Ответ: 170
Домашнее задание
Сайт К.Ю. Полякова, номера 1368, 1357, 1351, 1364, 1362.
Что с тремя множествами?
Я буду писать статью о трех множествах, где расскажу и об общем случае их пересечения, и о частном под кодовым названием "микки-маус" (или "гусеничка"). Если вам важно, чтобы этот материал вышел поскорее, напишите об этом в комментариях или поставьте лайк - тогда я узнаю, что вы его ждете.
Успехов вам с подготовкой от меня и канала TeachYOU :)