§9. Симметрическая разность множеств
ИнфоКонсалтинг
Образовательный сервис


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

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

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

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

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

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

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

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

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

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

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

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


§9. Симметрическая разность множеств




§9. Симметрическая разность множеств

Симметрическая разность множеств

Рис. 9.1. Симметрическая разность множеств показана оранжевым цветом

    • Симметрическая разность (обозначается A ∆ B) — множество, составленное исключением пересечения двух множеств из их объединения.

Итак, симметрическая разность по её определению вычисляется согласно формуле (9.1):

(9.1)
Определение симметрической разности
(9.1)
    • Если A = B, то результатом симметрической разности этих множеств является пустое множество: A ∆ B = ∅.

      Если одно из двух множеств, для которых определяется симметрическая разность, является пустым, то симметрическая разность совпадает с непустым множеством: A ∆ ∅ = A.

Симметрическая разность, как показывает (9.2), есть коммутативная операция:

(9.2)
Коммутативность симметрической разности
(9.2)

Симметрическая разность множеств ассоциативна — см. (9.3):

(9.3)
Ассоциативность симметрической разности
(9.3)

Число элементов симметрической разности можно найти, непосредственно используя её определение (9.1). В этом случае подобный расчёт осуществляется по формуле (9.4):

(9.4)
Мощность симметрической разности
(9.4)

Однако, используя характеристические функции множеств, равенство (9.4) получит несколько другой вид, а именно (9.5):

(9.5)
Мощность симметрической разности, рассчитываемая через характеристические функции образующих её множеств
(9.5)

Формула (9.5) фактически предоставляет нам возможность расчёта мощности симметрической разности, зная мощности каждого образующего её множества в отдельности и их пересечения. В терминах мощностей (9.5) выглядит как равенство (9.6):

(9.6)
Мощность симметрической разности
(9.6)

Применение знаний о симметрической разности показано в Примере 1 (стандартный тип задач КИМ ЕГЭ).

  • 1

    • Задача. Поисковая система веб-сайта позволяет показать ссылки на его страницы, содержащие информацию о разных странах мира. В процессе создания запроса можно использовать следующие специальные знаки: "&", наличие которого означает возвращение ссылок на страницы, содержащие сразу два слова, расположенные левее и правее "&", "|", который позволяет получить ссылки на страницы, содержащие хотя бы одно из слов, показанных левее и правее "|", и "!", указывающий на необходимость отсутствия на странице слова, записанного после него. Запросы "Бразилия & !Чили" и "!Бразилия & Чили", выполненные последовательно, привели к отображению в сумме 700 ссылок, а запрос "Бразилия | Чили" — 772 ссылок. Сколько ссылок на разные страницы этого веб-сайта будет возвращено после запроса "Бразилия & Чили"?


      Решение. Введём обозначения множеств. Пусть множество страниц, содержащих хотя бы одно из заданных слов, — "Бразилия", — обозначается PБ, а множество страниц, в которых есть слово "Чили", — PЧ. Тогда можно представить исходные данные следующим образом:
      |PБ ∩ ∁PЧ| + |∁PБ ∩ PЧ| = 700;
      |PБ ∪ PЧ| =772.

      Замечаем, что (PБ ∩ ∁PЧ) ∪ (∁PБ ∩ PЧ) = PБ ∆ PЧ, следовательно, по определению симметрической разности в терминах мощностей (9.4) количество ссылок, полученных по искомому запросу, составляет
      |PБ ∩ PЧ| = |PБ ∪ PЧ| – |PБ ∆ PЧ| = 72.

      Ответ. 72.

    • Заметим, что в решении задачи Примера 1 из предыдущего параграфа для выбранной константы ε можно было установить такое соответствие: ε = k – |R ∆ G ∆ B|, ведь множество R ∆ G ∆ B включает в себя все пикселы областей, сохранивших красный, зелёный и синий цвета, а также пикселы "белой" области.



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


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

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

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



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