В каких случаях говорят что множества не пересекаются информатика
Информатика online
Теория и практика решения олимпиадных задач и задач ЕГЭ по информатике. Теория информатики от 5 до 11 класса.
четверг, 24 ноября 2011 г.
Отношения между множествами и операции над ними
Отношения между множествами
Говорят, что множество А строго включено в множество B, если А включено в B и не равно ему:
A ⊂ B
В этом случае множество B строго включает в себя множество А; А является собственным множеством множества В.
Собственное множество — множество, которое является частью другого и не равно ему. В обоих случаях принято называть множество А подмножеством множества В; в свою очередь, множество В будет надмножеством множества А.
Говорят, что множества не пересекаются, если у них нет общих элементов.
Операции над множествами
Если имеется два множества или более, то с ними можно выполнить ряд операций. К таким операциям относятся:
— пересечение,
— объединение,
— дополнение,
— разность,
— симметрическая разность.
Все перечисленные операции, кроме дополнения, являются бинарными, т. е. выполняющимися с двумя множествами. Дополнение — унарная операция (выполняемая с одним множеством), которая, однако, может быть осуществлена лишь с учётом всех других множеств, предоставленных по условию задачи: дополнение всегда осуществляется до конкретного множества.
При этом пересечение, объединение и дополнение являются базовыми операциями, через которые могут быть выражены остальные.
Пересечение множеств (обозначается X ∩ Y ) — множество, включающее в себя элементы, которые одновременно входят в состав каждого из исходных множеств.
Можно сказать, что пересечение содержит элементы, общие для обоих множеств.
Операция пересечения коммутативна и ассоциативна:
1. X ∩ Y = Y ∩ X;
2. A ∩ (B ∩ C) = (A ∩ B) ∩ C;
Очевидно, что мощность пересечения не превосходит наименьшую мощность пересекающихся множеств:
| X ∩ Y| ≤ min (|X|,|Y|)
Объединение множеств (обозначается X ∪ Y ) — множество, включающее в себя все элементы, входящие в состав хотя бы одного из исходных множеств.
Операция объединения также коммутативна и ассоциативна.
Объединением множеств является множество, включающее в себя каждое из объединяемых множеств
Дополнение множества (обозначается ∁ Y или Ẏ ) — другое множество, включающее в себя все элементы, не входящие в состав исходного.
Несмотря на то, что операция дополнения является унарной, наличие другого множества учитывается.
Понятно, что исходное множество Y должно являться частью другого ( X ), на котором можно выбирать не принадлежащие Y элементы. Если множества Y и X совпадают, то дополнением Y является пустое множество.
Из математической записи дополнения напрямую не следует, до какого именно множества дополняется указанное. Cчитается, что дополнение всегда выполняется до универсума.
Понятие “Множество” в математике и информатике играет очень важную роль. В математике существует целая теория множеств.
Первое знакомство с данной темой может быть у учащихся как в начальной школе, если у них есть курс информатики, так и у учащихся 5-6 классов, которые раньше не изучали информатику. Данный материал подготовлен для учащихся 5-6 классов. Теме “Множества” желательно посвятить как минимум 2 урока. Материал может быть полезен и для преподавания информатики в начальной школе.
В курсе А.В. Горячева “Информатика в играх и задачах”, рассчитанного на учащихся начальной школы, тема “Множества” рассматривается и во 2 классе, и в 3 и в 4 классах. Естественно, что эта тема прорабатывается с детьми не один урок, а задания постепенно усложняются.
1. На первом уроке по теме “Множества” важно сразу же дать четкие определения тех терминов, которые потом будут использоваться в самых различных заданиях. Урок основан на использовании презентации (см. Приложение 1).
Множество произошло от слова “много”. Но в математике понятие “множество” используется более широко.
Множество может объединять любое количество предметов, чисел, существ. Каждый предмет множества называется элементом множества.
Множество, которое не содержит элементов, называется пустым.
Множество может иметь подмножества.
Множества могут пересекаться, не пересекаться, объединяться.
Равными называются множества, состоящие из одинакового числа одинаковых элементов.
(Желательно, чтобы эти определения были записаны учащимися в тетрадь, чтобы потом они могли к ним вернуться.)
Эти определения необходимо закрепить на простейших примерах, например: множество животных имеет несколько подмножеств: рыбы, птицы, звери, насекомые – и они не пересекаются. Если же мы возьмем множество морских животных, то оно будет пересекаться с множеством птиц и множеством зверей (приводятся несколько примеров). В качестве пустого множества можно дать такой пример: в яркий солнечный день на небе нет облаков, поэтому в этот день множество облаков (такое множество естественно существует) – пустое, а в другой день оно уже не будет пустым. Этот пример используется в тетради А.В. Горячева “Информатика в играх и задачах” 3 класс, часть 2. Можно привести и другие примеры, когда какое-то множество в конкретной ситуации будет пустым.
Также для удобства выполнения различных заданий необходимо ввести систему обозначения множеств (геометрические фигуры), подчеркнув, что это только условное обозначение, но оно очень удобно. Элементы множеств обозначаются точками.
Для закрепления понятия “элементы множества” учащимся предлагается следующее задание 1 (приложение 2) (его можно давать как домашнее задание, которое вклеивается в тетрадь).
2. Далее вводятся понятия, связанные с использованием логических связок в названиях множеств.
В названиях множеств и высказываниях могут употребляться логические связки: “и”, “не”, “или” и их комбинация: “не … и”, “не … или”. “не … и не …”
Если в названии множества есть связка “не”, то его элементы находятся за пределами фигуры, обозначающей это множество.
Если в названии множества есть связка “и”, то его элементы находятся на пересечении фигур, обозначающих множества.
Если в названии множества есть связка “или”, то это означает, что его элементы находятся в нескольких фигурах.
Эти схемы также необходимо закрепить с учащимися на разных примерах, включенных в задания в тетради (курс Горячева для начальной школы), а также на тех, где они сами приводят примеры различных множеств. Для закрепления понятий пересечения и объединения множеств учащимся предлагается дополнительное задание 2.
3. На следующем(их) уроке(ах) следует продолжить подробный разбор заданий, например, включив задания на пересечение трех множеств. (Желательно также, чтобы эти схемы были зарисованы учащимися в тетрадях).
При пересечении 2-х множеств образуется IV области: 2 области без пересечения, одна область пересечения множеств и одна область, лежащая за пределами выделенных множеств.
При пересечении 3-х множеств образуется VIII областей: 3 области без пересечения, 4 области пересечения множеств и 1 область, лежащая за пределами выделенных множеств.
При пересечении двух множеств закрашивается вся область пересечения этих множеств. При объединении двух множеств закрашиваются оба множества. При пересечении трех множеств закрашивается общая часть всех трех множеств. При отрицании всех трех множеств закрашивается область, не включающая в себя сами множества.
Данные схемы сделаны для задания, когда надо распределить слова, в состав которых входят буквы “С”, “Т” и “О”. Набор слов должен включать слова только с “Т”, только с “С”, только с “О”, а также одновременно с двумя и тремя буквами. Два-три слова должны быть без букв “С”, “Т”, “О”. (Например: рельсы, купе, проводник, скорость, колесо, электровоз, тамбур, вагон, сумка, место, шпалы, поезд, машинист, билет, состав, дверь, станция).
В курсе информатики А.В. Горячева в тетради 2 класса есть аналогичное задание на множества “Круглые”, “Желтые”, “Шары”.
Закрепление теоретического материала должно сопровождаться решением задач. Простейшие задачи, например, “Про коз и коров”, “Фиалки и подруги”, “Газеты и журналы” могут быть использованы даже во 2 классе (см. приложение 4). Для более сильных учеников и для более старших классов, соответственно, можно подобрать задачи нужного уровня, а можно также использовать какие-то задачи и для проведения конкурсов, КВНов, школьных олимпиад, недели математики и информатики. Подобные задачи удобно решать, используя схему множеств и обозначая элементы просто точками (если числа малые) или указывая число элементов в соответствующей области (в пересечении, без пересечения).
Система непересекающихся множеств и её применения
Добрый день, Хабрахабр. Это еще один пост в рамках моей программы по обогащению базы данных крупнейшего IT-ресурса информацией по алгоритмам и структурам данных. Как показывает практика, этой информации многим не хватает, а необходимость встречается в самых разнообразных сферах программистской жизни.
Я продолжаю преимущественно выбирать те алгоритмы/структуры, которые легко понимаются и для которых не требуется много кода — а вот практическое значение сложно недооценить. В прошлый раз это было декартово дерево. В этот раз — система непересекающихся множеств. Она же известна под названиями disjoint set union (DSU) или Union-Find.
Условие
Поставим перед собой следующую задачу. Пускай мы оперируем элементами N видов (для простоты, здесь и далее — числами от 0 до N-1). Некоторые группы чисел объединены в множества. Также мы можем добавить в структуру новый элемент, он тем самым образует множество размера 1 из самого себя. И наконец, периодически некоторые два множества нам потребуется сливать в одно.
Формализируем задачу: создать быструю структуру, которая поддерживает следующие операции:
На рисунке я продемонстрирую работу такой гипотетической структуры.
Реализация
Классическая реализация DSU была предложена Bernard Galler и Michael Fischer в 1964 году, однако исследована (включая временную оценку сложности) Робертом Тарьяном уже в 1975. Тарьяну же принадлежат некоторые результаты, улучшения и применения, о которых мы сегодня ещё поговорим.
Хранить структуру данных будем в виде леса, то есть превратим DSU в систему непересекающихся деревьев. Все элементы одного множества лежат в одном соответствующем дереве, представитель дерева — его корень, слияние множеств суть просто объединение двух деревьев в одно. Как мы увидим, такая идея вкупе с двумя небольшими эвристиками ведет к поразительно высокому быстродействию получившейся структуры.
Для начала нам потребуется массив p, хранящий для каждой вершины дерева её непосредственного предка (а для корня дерева X — его самого). С помощью одного только этого массива можно эффективно реализовать две первые операции DSU:
MakeSet(X)
Чтобы создать новое дерево из элемента X, достаточно указать, что он является корнем собственного дерева, и предка не имеет.
Find(X)
Представителем дерева будем считать его корень. Тогда для нахождения этого представителя достаточно подняться вверх по родительским ссылкам до тех пор, пока не наткнемся на корень.
Но это еще не все: такая наивная реализация в случае вырожденного (вытянутого в линию) дерева может работать за O(N), что недопустимо. Можно было бы попытаться ускорить поиск. Например, хранить не только непосредственного предка, а большие таблицы логарифмического подъема вверх, но это требует много памяти. Или хранить вместо ссылки на предка ссылку на собственно корень — однако тогда при слиянии деревьев (Unite) придется менять эти ссылки всем элементам одного из деревьев, а это опять-таки временные затраты порядка O(N).
Мы пойдем другим путём: вместо ускорения реализации будем просто пытаться не допускать чрезмерно длинных веток в дереве. Это первая эвристика DSU, она называется сжатие путей (path compression). Суть эвристики: после того, как представитель таки будет найден, мы для каждой вершины по пути от X к корню изменим предка на этого самого представителя. То есть фактически переподвесим все эти вершины вместо длинной ветви непосредственно к корню. Таким образом, реализация операции Find становится двухпроходной.
На рисунке показано дерево до и после выполнения операции Find(3). Красные ребра — те, по которым мы прошлись по пути к корню. Теперь они перенаправлены. Заметьте, как после этого кардинально уменьшилась высота дерева.
Исходный код в рекурсивной форме написать достаточно просто:
Unite(X, Y)
Со слиянием двух деревьев придется чуть повозиться. Найдем для начала корни обоих сливаемых деревьев с помощью уже написанной функции Find. Теперь, помня, что наша реализация хранит только ссылки на непосредственных родителей, для слияния деревьев достаточно было бы просто подвесить один из корней (а с ним и все дерево) сыном к другому. Таким образом все элементы этого дерева автоматически станут принадлежать другому — и процедура поиска представителя будет возвращать корень нового дерева.
Встает вопрос: какое дерево к какому подвешивать? Всегда выбирать какое-то одно, скажем, дерево X, не годится: легко подобрать пример, на котором после N объединений мы получим вырожденное дерево — одну ветку из N элементов. И тут в ход вступает вторая эвристика DSU, направленная на уменьшение высоты деревьев.
Будем хранить помимо предков еще один массив Rank. В нем для каждого дерева будет храниться верхняя граница его высоты — то есть длиннейшей ветви в нем. Заметьте, не сама высота — в процессе выполнения Find длиннейшая ветвь может самоуничтожиться, а тратить еще итерации на нахождение новой длиннейшей ветви слишком дорого. Поэтому для каждого корня в массиве Rank будет записано число, гарантированно больше или равное высоте его дерева.
Теперь легко принять решении о слиянии: чтобы не допустить слишком длинных ветвей в DSU, будем подвешивать более низкое дерево к более высокому. Если их высоты равны — не играет роли, кого подвешивать к кому. Но в последнем случае новоиспеченному корню надо не забыть увеличить Rank.
Вот так производится типичный Unite (например, с параметрами 8 и 19):
Однако на практике оказывается, что можно и не тратить дополнительные O(N) памяти на махинации с рангами. Достаточно выбирать корень для переподвешивания случайным образом — как ни удивительно, но такое решение дает на практике скорость, вполне сравнимую с оригинальной ранговой реализацией. Автор данной статьи всю жизнь пользуется именно рандомизированным DSU, и еще не было случая, когда тот бы подвёл.
Быстродействие
В силу применения двух эвристик скорость работы каждой операции сильно зависит от структуры дерева, а структура дерева — от списка выполненных до того операций. Исключение составляет только MakeSet — её время работы очевидно O(1) 🙂 Для остальных двух скорость очень неочевидна.
Итак, имеем:
MakeSet(X) — O(1).
Find(X) — O(1) амортизированно.
Unite(X, Y) — O(1) амортизированно.
Расход памяти — O(N).
Практические применения
Для DSU известно большое число различных использований. Большинство связано с решением некоторой задачи в режиме оффлайн — то есть когда список запросов касательно структуры, которые поступают программе, известен заранее. Я приведу здесь несколько таких задач вместе с краткими идеями решений.
Остов минимального веса
Дан неориентированный связный граф со взвешенными ребрами. Выкинуть из него некоторые ребра так, чтобы в итоге получилось дерево, причем суммарный вес ребер этого дерева должен быть наименьшим.
Одно из известных мест, где встает эта задача (хотя и решается иначе) — блокирование избыточных связей в Ethernet-сети для избегания возможных циклов пакетов. Протоколы, созданные с этой целью, широко известны, причем половина серьезных модификаций в них сделана Cisco. Более подробно см. Spanning Tree Protocol.
На рисунке показан взвешенный граф с выделенным минимальным остовом.
Алгоритм Краскала для решения этой задачи: отсортируем все ребра по возрастанию веса и будем поддерживать текущий лес минимального веса с помощью DSU. Изначально DSU состоит из N деревьев, по одной вершине в каждом. Идем по ребрам в порядке возврастания; если текущее ребро объединяет разные компоненты — сливаем их в одну и запоминаем ребро как элемент остова. Как только количество компонент достигнет единицы — мы построили искомое дерево.
Алгоритм Тарьяна для поиска LCA оффлайн
Дано дерево и набор запросов вида: для данных вершин u и v вернуть их ближайшего общего предка (least common ancestor, LCA). Весь набор запросов известен заранее, т.е. задача сформулирована в режиме оффлайн.
Компоненты связности в мультиграфе
Дан мультиграф (граф, в котором пара вершин может быть соединена более чем одним непосредственным ребром), к которому поступают запросы вида «удалить некоторое ребро» и «а сколько сейчас в графе компонент связности?» Весь список запросов известен заранее.
Решение банально. Выполним сначала все запросы на удаление, посчитаем количество компонент в итоговом графе, запомним его. Получившийся граф запихнем в DSU. Теперь будем идти по запросам удаления в обратном порядке: каждое удаление ребра из старого графа означает возможное слияние двух компонент в нашем «flashback-графе», хранящемся в DSU; в таком случае текущее количество компонент связности уменьшается на единичку.
Сегментирование изображений
Рассмотрим некоторое изображение — прямоугольный массив пикселей. Его можно представить как сетчатый граф: каждая вершина-пиксель непосредственно связана ребрами со своими четырьмя ближайшими соседями. Задача заключается в том, чтобы выделить на изображении одинаковые смысловые зоны, например, похожего цвета, и уметь для двух пикселей быстро определять, находятся ли они в одной зоне. Так, например, раскрашиваются старые черно-белые фильмы: для начала нужно выделить области с примерно одинаковыми оттенками серого.
Есть два подхода к решению этой проблемы, оба в конечном итоге используют DSU. В первом варианте мы проводим ребро не между каждой парой соседних пикселей, а только между теми, которые достаточно близки по цвету. После этого обычный прямоугольный обход графа заполнит DSU, и мы получим набор компонент связности — они же однотонные области изображения.
Второй вариант более гибкий. Не будем полностью убирать ребра, а присвоим каждому из них вес, рассчитанный на основании разности цветов и еще каких-то дополнительных факторов — своих для каждой конкретной задачи сегментирования. В полученном графе достаточно найти какой-нибудь лес минимального веса, например, тем же алгоритмом Краскала. На практике в DSU записывают не любое текущее соединяющее ребро, а только те, для которых на данный момент две компоненты не сильно отличаются по меркам другой специальной весовой функции.
Генерация лабиринтов
Задача: сгенерировать лабиринт с одним входом и одним выходом.
Алгоритм решения:
Начнем с состояния, когда установлены все стены, за исключением входа и выхода.
На каждом шаге алгоритма выберем случайную стену. Если ячейки, между которыми она стоит, еще никак не соединены (лежат в разных компонентах DSU), то уничтожаем её (сливаем компоненты).
Продолжаем процесс до некоторого состояния сходимости: например, когда вход и выход соединены; либо, когда осталась одна компонента.
Однопроходные алгоритмы
Существуют варианты реализации Find(X), которые требуют одного прохода до корня, а не двух, однако сохраняют ту же или почти ту же степень быстродействия. Они реализуют другие стратегии сокращения высоты дерева, в отличие от path compression.
Вариант №1: path splitting. По пути от вершины Х до корня перенаправить родительскую связь каждой вершины с её предка на предка предка (дедушку).
Вариант №2: path halving. Взять идею path splitting, однако перенаправлять связи не всех вершин по пути, а только тех, на которых делаем перенаправления — то есть «дедушек».
На рисунке взято все то же дерево, в нем выполняется запрос Find(3). По центру показан результат с применением path splitting, справа — path halving.
Функциональная реализация
У системы непересекающихся множеств есть один большой недостаток: она не поддерживает ни в какой форме операцию Undo, потому что реализована насквозь в императивном стиле. Гораздо удобнее была бы реализация DSU в функциональном стиле, когда каждая операция не изменяет структуру на месте, а возвращает слегка модифицированную новую структуру, в которой произведены требуемые изменения (при этом большая часть памяти у старой и новой структур общая). Такие структуры данных в английской терминологии носят название persistent, они широко применяются в чистом функциональном программировании, где доминирует идея неизменяемости данных.
В силу чисто императивной идеи алгоритмов DSU её функциональная реализация с сохранением быстродействия долгое время казалась немыслимой. Тем не менее, в 2007 году Sylvain Conchon и Jean-Christophe Filliâtre представили в своей работе искомый функциональный вариант, в котором операция Unite возвращает измененную структуру. Если говорить честно, он не совсем функциональный, он использует императивные присваивания, однако они надежно скрыты внутри реализации, а интерфейс persistent DSU — чисто функциональный.
Основная идея реализации — использование структур данных, реализующих «персистентные массивы»: они поддерживают те же операции, что и массивы, однако все так же не модифицируют память, а возвращают измененную структуру. Такой массив можно легко реализовать с помощью какого-нибудь дерева, однако в таком случае операции с ним будут занимать O(log2 N) времени, а для DSU такая оценка оказывается уже чрезмерно большой.
За дальнейшими техническими подробностями отсылаю читателей к оригинальной статье.
Литература
Системы непересекающихся множеств в объеме данной статьи обсуждаются в знаменитой книге — Кормен, Лейзерсон, Ривест, Штайн «Алгоритмы: построение и анализ». Там же можно найти и доказательство того, что выполнение операций занимает порядка α(N) времени.
На сайте Максима Иванова можно найти полную реализацию DSU на C++.
В статье Wait-free Parallel Algorithms for the Union-Find Problem обсуждается парралельная версия реализации DSU. В ней отсутствуют блокировки потоков.
Пересечение множеств чисел – примеры, определение, формула (8 класс, информатика)
Математическая логика занимается изучением логических законов, применяемых в теории множеств. Основы алгебры логики рассматриваются в курсе информатики 8 класса. Над множествами можно выполнять различные действия, одним из которых является пересечение.
Пересечение множеств
Важным разделом в информатике является алгебра логики. Знание логических законов и правил дает возможность быстро решать сложные задачи в любой области деятельности — в области правовых и экономических наук, в технике и технологии.
Множество чисел
Множеством называется совокупность определенных и различных между собой объектов, воспринимаемых как единое целое.
Например, совокупность учеников класса, совокупность целых положительных чисел.
Множества могут быть конечными и бесконечными. Количество учеников в классе — это конечное множество, можно четко назвать конкретное число учеников. Количество целых положительных чисел — бесконечное множество оно может быть бесконечно большим.
В математике множество обозначают прописными латинскими буквами.
Например, множество А= <1,5,12,6,7>и множество В= <2,4,12,3,7>конечные множества целых положительных чисел
С множествами можно выполнять различные действия. Одним из таких действий является пересечение множеств чисел.
Пересечение множеств чисел
С точки зрения математики, пересечением двух множеств Х и Y является третье множество Z, в состав которого входят элементы, как первого, так и второго множеств. Приведем примеры пересечения множеств чисел.
Для множеств чисел Х= <1, 2,4,5,6,8>и Y= <2,3,4,6,7,9>пересечением будет третье множество Z=<2, 4, 6>.
В качестве элементов множеств могут выступать не только числа.
Для множеств А= <А, Б, В, Г, Д, Е>и B= <Г, Д, Е, Ё, Ж>пересечением будет третье множество, элементы которого — буквы, одинаковые в исходных множествах C=<Г, Д, Е>.
Обозначение пересечения
Операцию пересечения называют и обозначают по-разному, но суть от этого не меняется. В теории множеств для обозначения пересечения используется знак ∩, а формула выглядит так: А ∩ B = C
Пересечение также называют произведением множеств, и для обозначения операции используют знак умножения: А ∙ В = С
В математической логике, работающей с высказываниями, используют понятие «конъюнкция». Для ее обозначения используют символ &: А & В = С. Допустимо конъюнкцию обозначать буквой И: А И В = С.
Визуальное представление пересечения
Для визуального отображения действий с множествами используют диаграммы Эйлера, которые представляют собой две окружности, частично наложенные друг на друга. Окружности — это множества. Закрашенная область, принадлежащая одновременно каждой окружности, образованная путем наложения — это область пересечения.
Рис. 1. Диаграмма Эйлера для пересечения множеств.
Круги Эйлера представляют собой простой инструмент, который доходчиво объясняет суть основ теории множеств. Широко известен цикл работ Леонарда Эйлера под названием «Письма к немецкой принцессе о разных физических и философских материях», написанный для дочерей маркграфа Бранденбург-Шведт. В письмах 102 – 104 второго тома этого произведения использован данный графический метод.
Рис. 2. Портрет Леонарда Эйлера.
Определение результатов операций над множествами с использованием кругов Эйлера значительно облегчает решение логических задач.
Таблица истинности
В алгебре логики объектом, к которому применяются логические операции, является высказывание. Оно представляет собой некоторое повествовательное предложение, содержание которого можно однозначно определить как истинное или ложное. Если высказывание истинно, то его обозначают единицей, если ложно — то это ноль.
Например, высказывание «Москва — столица РФ» истинное высказывание. «Площадь квадрата определяется как сумма его сторон» — это ложное высказывание.
Высказывание не может быть вопросительным или побудительным предложением, числовые выражения, которые не содержат логических операций, или содержащие переменные, также не являются высказываниями.
Для обозначения всех возможных вариантов высказываний используются таблицы истинности.
Рис. 3. Таблица истинности для конъюнкции.
По таблице видно, что в результате операции конъюнкции (пересечения) истинное выражение (равно 1) тогда и только тогда, когда оба исходные выражения истинны. Во всех других случаях результат равен нулю (ложь).
Что мы узнали?
Пересечение двух множеств представляет собой третье множество, содержащее элементы общие для исходных множеств. Операцию пересечения можно обозначать по-разному. Пересечение также называется произведением множеств и конъюнкцией. Визуально пересечение удобно представлять с помощью диаграмм Эйлера. Для отображения всех вариантов высказываний используют таблицы истинности. Для пересечения результат принимает значение истина только в случае, когда истинны оба операнда.