§8. Разность множеств
ИнфоКонсалтинг
Образовательный сервис


Новости сайта

24.08.2017 Поздравляем учителей, преподавателей, учащихся и их родителей с началом нового учебного года! Пусть он окажется успешным и даст много полезных и нужных знаний.

24.08.2017 Успейте подобрать репетитора на новый учебный год! Это можно сделать на соответствующей странице нашего сайта, притом по любому предмету, в любом городе России и с учётом индивидуальных требований.

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

Найти репетитора

Отправить заявку

24.08.2017 Страницы сайта переиндексированы для системы поиска ИнфоКонсалтинг.

Поиск по нашему сайту

04.10.2016 В разделе "К экзамену" появилось решение задачи 23 демо-версии КИМ ЕГЭ по информатике от 2017 г.

Задача 23 демо-версии 2017 г. по информатике

04.10.2016 В разделе "К экзамену" появилось решение задачи 26 демо-версии КИМ ЕГЭ по информатике от 2017 г.

Задача 26 демо-версии 2017 г. по информатике


§8. Разность множеств


Payeer

§8. Разность множеств

Разность множеств

Рис. 8.1. Разность множеств показана оранжевым цветом

    • Разность множеств (обозначается A \ B) — подмножество множества A, включающее в себя элементы A, не относящиеся к множеству B.

    • Можно выделить четыре случая определения двух множеств, при которых их разность представляется отличающимися результатами, хотя эти результаты очевидны.

      Пусть B ⊊ A. Тогда A \ B = A ∩ ∁B, B \ A = ∅.

      Если B = A, то A \ B = B \ A = ∅.

      Предположим, что A ∩ B ≠ ∅. Тогда A \ B = A \ (A ∩ B), хотя это равенство действительно всегда (как, впрочем, и A \ B = A ∩ ∁B). Эти равенства останутся справедливыми, если в них заменить A на B и наоборот.

      Наконец, последний случай, при котором A и B не пересекаются (не имеют общих точек): A ∩ B = ∅. Тогда A \ B = A, B \ A = B.

Во всех случаях разность двух множеств можно определить одним из равенств (8.1):

(8.1)
Разность множеств есть разность множества и его пересечения с другим множеством
(8.1)

Мощность разности двух множеств можно получить путём вычисления значений характеристических функций для всех элементов u, принадлежащих как минимум объединению множеств, что показывает (8.2):

(8.2)
Число элементов разности множеств, вычисляемое через характеристические функции этих множеств
(8.2)

Для вычисления числа элементов разности множеств чаще других используют формулу (8.3):

(8.3)
Число элементов разности множеств
(8.3)

В Примерах 1 и 2 показано, как можно использовать эту операцию с множествами. При этом решение задачи Примера 2 потребует применения равенства (6.8) (см. §6).

  • 1

    • Задача. На экране монитора сначала были видны изображения трёх кругов красного, зелёного и синего цветов, каждый из которых составлен k пикселами. Затем круги были сдвинуты так, что образовали пересечения, как это показано на рисунке, при этом ввиду оптического смешения цветов появились разноцветные области, и одна из них — белого цвета, состоящая из w пикселов. Красных же точек осталось r, зелёных — g, синих — b. Сколько светящихся пикселов образуют каждую из цветовых областей полученного изображения, отмеченных буквами X, Y и Z? Считать, что изображения исходных кругов составлены пикселами, светящимися с неизменными и равными интенсивностями своих цветовых каналов (границы между цветовыми областями на рисунке показаны исключительно для наглядности).


      Решение. Первое, что необходимо сделать для решения практически любой задачи — прокомментировать предоставленные и ввести новые условные обозначения, используемые на этапе вычислений. Пусть множество всех составляющих красный круг пикселов обозначено R, зелёный — G, синий — B; заметим, что мощности этих множеств одинаковы: k = |R| = |G| = |B|. Множество всех оставшихся после пересечения кругов красных экранных точек обозначим R1, зелёных — G1, синих — B1, при этом их мощности даны: r = |R1|, g = |G1|, b = |B1|. Пусть также множество пикселов белой области есть W (его мощность известна, она составляет w), а множества пикселов, составляющих области полученных цветов, обозначены так, как на рисунке, при этом x = |X|, y = |Y|, z = |Z|. Последнее, что мы сделаем на этом этапе, — введём константу ε, которая потребуется для облегчения представления результатов: ε = k – (r + g + b + w).

      Каждый круг после пересечения с другими кругами оказывается разделённым на четыре непересекающиеся цветовые зоны (множества пикселов) следующим образом:
      R = R1 ∪ X ∪ Z ∪ W,
      G = G1 ∪ X ∪ Y ∪ W,
      B = B1 ∪ Y ∪ Z ∪ W.

      Так записывается система уравнений в терминах множеств. Из этого следует, что
      X ∪ Z = (R \ R1) \ W,
      X ∪ Y = (G \ G1) \ W,
      Y ∪ Z = (B \ B1) \ W.

      Поскольку области X, Y и Z попарно не пересекаются, то возможна такая запись этой системы в терминах мощностей:
      x + z = k – w – r,
      x + y = k – w – g,
      y + z = k – w – b,
      откуда
      z = k – w – r – x,
      y = k – w – g – x,
      y + z = k – w – b.

      Подставим в последнее уравнение системы оба выражения, описывающие y и z:
      k – w – g – x + k – w – r – x = k – w – b, из чего следует, что
      2x = k – w – g – r + b.

      Употребляя введённую ранее константу ε, имеем: x = ε/2 + b. Тем самым, мощность одного из неизвестных множеств найдена.

      Подставляя полученное выражение для x во второе и первое уравнения системы соответственно, находим оставшиеся неизвестные y и z: y = ε/2 + r, z = ε/2 + g.

      Можно заметить следующую закономерность, связывающую площади разных областей пересечений: при постоянных площадях кругов любая область, заполненная некоторым производным цветом (кроме белого), тем больше, чем больше площадь части круга, закрашенная исходным его цветом, не участвующим в образовании этого производного цвета, и чем меньше площадь пересечения всех трёх кругов. Другими словами, при пересечении трёх разноцветных кругов с эффектом оптического смешения цветов площади их областей, одна из которых заполнена производящим цветом, а другая — производным, не являющихся смежными, прямо пропорциональны.

      Ответ. |X| = ε/2 + b, |Y| = ε/2 + r, |Z| = ε/2 + g, где ε = k – (r + g + b + w).

  • 2

    • Задача. В школьном тестировании по истории принимали участие 70 учащихся. На один из вопросов теста требовалось дать ответ, заключающийся в выборе нескольких событий из четырёх предложенных вариантов, при этом можно было отметить от одного до всех четырёх вариантов событий. После тестирования учитель выполнял анализ распределения ответов учащихся на этот вопрос, в ходе которого выяснилось следующее. Во всех ответах первый вариант событий был выбран 17 учащимися, второй — 45, третий — 26, четвёртый — 47. Первый и второй, а также первый и четвёртый варианты упоминались в ответах 9 человек, второй и третий, третий и четвёртый варианты — 14, первый и третий — 6 учеников. Некоторые из участников тестирования выбрали по три или даже четыре варианта: первый, второй и третий были обозначены в ответах 2 человек, первый, второй и четвёртый, а также первый, третий и четвёртый — 3 учеников, второй, третий и четвёртый — 7. Считать количество заведомо неправильных ответов в виде отметки всех четырёх вариантов событий учитель не стал. Сколько учащихся дали правильный ответ на этот вопрос теста, если он состоит в выборе второго и четвёртого вариантов событий?


      Решение. Будем обозначать множество ответов, содержащих выбранным хотя бы один вариант события, буквой с одним индексом (например, A2 — множество всех ответов, в которых выбрано хотя бы одно, но именно второе событие), хотя бы двух событий — буквой с двумя индексами (например, A14 есть множество всех ответов, в которых выбраны хотя бы первое и четвёртое события) и т. д. Для всех последующих записей при i ≠ j, i ≠ k, j ≠ k:
      Aij ≡ Aji,
      Aijk ≡ Aikj ≡ Akij ≡ Ajik ≡ Ajki ≡ Akji,
      т. е. во всех случаях любой набор индексов при букве, с которыми она обозначает конкретное множество, есть неупорядоченный, полученный выбором без возвращения (см. §30 раздела "Введение в информатику"). При этом подразумевается, что Aij = Ai ∩ Aj и Aijk = Ai ∩ Aj ∩ Ak.

      Также введём специальные обозначения для двух множеств: X = A24, Y = A1234.

      Заметим, однако, что найдя |X|, мы не ответим на вопрос задачи, потому что X содержит в себе не только ответы с выбранными исключительно вторым и четвёртым вариантами событий, но, например, и множество ответов A234, и, как следствие, даже множество Y. Нам потребуется рассматривать подмножества B каждого множества A, содержащие только те ответы, в которых выбраны события с номерами вариантов, полностью совпадающими с индексами конкретного из этих подмножеств. Таким образом, общая запись множеств всех ответов, в которых отмечено не менее трёх событий, выглядит так: Aijk = {Bijk, Y}. Особо обратим внимание на то обстоятельство, что Y ≐ A1234 = B1234 (значок "≐" читается "равно по определению"). Найти же требуется |B24|.

      Учитывая, что общее количество учеников (и, соответственно, их ответов) составляет 70 (т. е. |A1 ∪ A2 ∪ A3 ∪ A4| = 70), равенство (6.8) (см. §6) для нашей задачи приобретает такой вид:
      |X| = |A1| + |A2| + |A3| + |A4| –

      – |A12| – |A13| – |A14| – |A23| – |A34| +

      + |A123| + |A124| + |A134| + |A234| – |Y| – 70.

      Подставляя известные величины в качестве мощностей множеств, получаем:
      |X| = 28 – |Y|.

      Логично, что Y = A123 ∩ A124 ∩ A134 ∩ A234, при этом из упомянутых множеств наименьшей мощностью обладает A123: |A123| = 2. Значит, согласно (5.3) — см. §5, 0 ≤ |Y| ≤ 2. Но ни в коем случае нельзя показывать возможные значения |X| с помощью двойного неравенства: вполне возможно, что не при всех полученных таким образом значениях |Y| условие задачи окажется соблюдённым. На следующем этапе решения придётся определять (при разных значениях |Y|), сколько конкретных видов ответов получилось после тестирования, т. е. вычислять мощность каждого множества B. Будем надеяться, что эта большая работа окажется не напрасной.

      Рассчитаем мощности каждого множества B. Будем исходить из того, что
      Bijk = Aijk \ Y,
      Bij = (Aij \ k Bijk) \ Y,
      Bi = (Ai \ (j Bij ∪ j,k Bijk)) \ Y.

      Тогда
      |Bijk| = |Aijk| – |Y|,
      |Bij| = |Aij| – k |Bijk| – |Y|,
      |Bi| = |Ai| – j |Bij| – j,k |Bijk| – |Y|.

      При |Y| = 2 получаем такие значения:
      |B123| = 0, |B124| = 1, |B134| = 1, |B234| = 5,
      |B12| = 6, |B13| = 3, |B14| = 5, |B23| = 7, |B24| = 18, |B34| = 6,
      |B1| = –1…

      Вот отрицательных значений у мощностей множеств не может быть точно, иначе как объяснить, что отметку первого варианта события как единственную поставил –1 ученик?.. Таким образом, |Y| ≠ 2, потому что становятся невозможными множества ответов.

      При |Y| = 1 имеем следующее распределение ответов:
      |B123| = 1, |B124| = 2, |B134| = 2, |B234| = 6,
      |B12| = 5, |B13| = 2, |B14| = 4, |B23| = 6, |B24| = 18, |B34| = 5,
      |B1| = 0, |B2| = 6, |B3| = 3, |B4| = 9.

      Вроде бы всё сходится (т. е. такие множества имеют право на существование), но необходимо проверить общее число участников тестирования: а вдруг не выйдет 70 человек в общем количестве? Сложим количество элементов всех множеств B, 70 ответов учащихся в сумме вышло. Выберем вычисленное выше значение |B24| = 18 для последующей записи ответа.

      Последний вариант остался: |Y| = 0. Вот, что получилось:
      |B123| = 2, |B124| = 3, |B134| = 3, |B234| = 7,
      |B12| = 4, |B13| = 1, |B14| = 3, |B23| = 5, |B24| = 18, |B34| = 4,
      |B1| = 1, |B2| = 6, |B3| = 4, |B4| = 9.

      Опять множества по отдельности имеют право на существование, каждое с показанным количеством элементов. Но сложатся ли у нас 70 человек? Определим сумму элементов всех множеств B, и ожидаемое число вновь подтверждено.

      В списке мощностей множеств отыскиваем |B24| и пишем ответ с учётом вычисленного на предыдущем этапе проверки количества элементов этого множества. Оно, впрочем, совпадает с полученным только что.

      Ответ. 18.



Поддержите нас!


Обращаем Ваше внимание:

Ваш браузер недостаточно эффективен. Установите достойный браузер здесь.

Все анонсы? / ?



Индекс цитирования
CY, Page Rank
Яндекс.Метрика