Понятие разбиение множества на классы. Примеры разбиения множеств на два (три, четыре, и т.д.) подмножеств. Примеры заданий на классификацию из начального курса математики.
Понятие разбиения множества на классы
Понятие множества и операций над множествами позволяют уточнить наше представление о классификации.
Классификация – это действие распределения объектов по классам на основании сходств объектов внутри класса и их отличия от объектов других классов.
Как правило, целью классификации является систематизация наших знаний. Например, в биологии имеется классификация животных, охватывающая до 1,5 млн. различных видов животных, в ботанике – классификация растений, включающая 500 тыс. видов растений. Классификация дает возможность рассмотреть это многообразие в определенной системе, выделить интересующие нас виды растений и животных.
Широко применяется классификация в математике. Например, натуральные числа делятся на четные и нечетные; углы (меньше развернутого) бывают острые, прямые и тупые.
Выясним условия, которым должны удовлетворять правильно выполненная классификация.
Любая классификация связана с расчленением некоторого множества объектов на подмножества. Если при этом каждый элемент данного множества попадает в одно и только одно подмножество, а объединение всех выделенных подмножеств совпадает со всем множеством, то говорят, что данное множество разбито на непересекающиеся подмножества или классы.
Определение. Считают, что множество Х разбито на классы Х 1 , Х 2 ,…,Х п, если:
1. подмножества Х 1 , Х 2 ,…,Х п попарно не пересекаются;
2. объединение подмножеств Х 1 , Х 2 ,…,Х п совпадает с множеством Х.
Если не выполнено хотя бы одно из этих условий, классификацию считают не правильной.
Так, множество Х треугольников можно разбить на три класса: остроугольные, прямоугольные и тупоугольные. Действительно, выделенные подмножества попарно не пересекаются (среди остроугольных нет прямоугольных и тупоугольных, среди прямоугольных – тупоугольных) и их объединение совпадает с множеством Х.
О днако не всякая система подмножеств данного множества представляет собой разбиение этого множества. Например, если из множества Х треугольников выделить подмножества равнобедренных, равносторонних и разносторонний, то разбиения множества Х на классы не мы не получим, поскольку множества равнобедренных и равносторонних треугольников пересекаются (все равносторонние треугольники являются равнобедренными).
Итак, классификация связана с выделением из множества его подмножеств. Но чтобы выделить подмножество, достаточно указать характеристическое свойство его элементов.
Рассмотрим, например, множество натуральных чисел. Его элементы обладают различными свойствами. Среди натуральных чисел есть четные, нечетные, кратные 3, кратные 5 и т.д. Предположим, что нас интересуют натуральные числа, обладающие свойством делиться на 3. Это свойство позволяет выделить из множества натуральных чисел подмножество чисел, кратных 3. Тогда про остальные натуральные числа можно сказать, что они не кратны 3, т.е. получаем еще одно подмножество множества натуральных чисел. Выделенные подмножества не пересекаются, а их объединение совпадает с множеством N натуральных чисел.
Таким образом, задание одного свойства элементов множества натуральных чисел привело к разбиению этого множества на два класса: класс чисел, кратных 3 и класс чисел, не кратных 3.
Рассмотрим разбиение множества на классы, если для его элементов указать два свойства, т.е. выделить из множества два различных подмножества.
Р ассмотрим два свойства натуральных чисел: «быть кратным 3» и «быть кратным 5».При помощи этих свойств из множества натуральных чисел можно выделить два подмножества: А- подмножество чисел, кратных 3, и В – подмножество чисел, кратных 5. Эти подмножества пересекаются, но ни одно из них не является подмножеством другого.
Проанализируем получившуюся картину. Круг, изображающий множество N натуральных чисел, разбился на 4 непересекающиеся области – они пронумерованы римскими цифрами. Каждая область изображает некоторое подмножество множества N. Определим, какие числа оказались в каждом из этих непересекающихся подмножеств. Подмножество I состоит из чисел, кратных 3 и 5; подмножество II – из чисел, кратных 3 и не кратным 5; подмножество III – из чисел, кратных 5 и не кратных 3; подмножество IY – из чисел, не кратных 3 и не кратных 5. Объединение этих четырех подмножеств есть множество N.
Понятия множества и операций над множествами позволяют уточнить наше представление о классификации - действии распределения объектов по классам.
Классификацию мы выполняем достаточно часто. Так, натуральные числа представляем как два класса - четные и нечетные. Углы на плоскости разбиваем на три класса: прямые, острые и тупые.
Любая классификация связана с разбиением некоторого множества объектов на подмножества. При этом считают, что множество X разбито на классы X 1 , Х 2 ,..., Х n ..., если:
1) подмножества Х 1 , Х 2 ,..., Х п,... попарно не пересекаются; |
2) объединение подмножеств X 1 , Х 2 , ..., Х n , ... совпадает с множеством X. |
Если не выполнено хотя бы одно из условий, классификацию считают неправильной. Например, если из множества X треугольников выделить подмножества равнобедренных, равно-сторонних и разносторонних треугольников, то разбиения мы не получим, поскольку подмно-жества равнобедренных и равносторонних треугольников пересекаются (все равносторонние треугольники являются равнобедренными). В данном случае не выполнено первое условие разбиения множества на классы.
Так как разбиение множества на классы связано с выделением его подмножеств, то классификацию можно выполнять при помощи свойств элементов множеств.
Рассмотрим, например, множество натуральных чисел. Его элементы обладают различными свойствами. Положим, что нас интересуют числа, обладающие свойством «быть кратным 3». Это свойство позволяет выделить из множества натуральных чисел подмножество, состоящее из чисел, кратных 3. Тогда про остальные натуральные числа можно сказать, что они не кратны 3, т.е. получаем еще одно подмножество
множества натуральных чисел (рис. 12). Так как выделенные подмножества не пересекаются, а их объединение совпадает с множеством натуральных чисел, то имеем разбиение этого множества на два класса.
| Рис. 12 | Рис. 13 |
Вообще, если на множестве X задано одно свойство, то это множество разбивается на два класса. Первый - это класс объектов, обладающих этим свойством, а второй - дополнение первого класса до множества X. Во втором классе содержатся такие объекты множества X, которые заданным свойством не обладают. Такую классификацию называют дихотомической.
Рассмотрим теперь ситуацию, когда для элементов множества заданы два свойства. Например, такие свойства натуральных чисел, как «быть кратным 3» и «быть кратным 5». При помощи этих свойств из множества N натуральных чисел можно выделить два подмножества: А - подмножество чисел, кратных 3, и В - подмножество чисел, кратных 5. Эти множества пересекаются, но ни одно из них не является подмножеством другого (рис. 13). Проанализируем получившийся рисунок. Конечно, разбиения множества натуральных чисел на подмножества А и В не произошло. Но круг, изображающий множество N, можно рассматривать как состоящий из четырех непересекающихся областей - на рисунке они пронумерованы. Каждая область изображает некоторое подмножество множества N. Подмножество I состоит из чисел, кратных 3 и 5; подмножество II - из чисел, кратных 3 и не кратных 5; подмножество III - из чисел, кратных 5 и не кратных 3; подмножество IV - из чисел, не кратных 3 и не кратных 5. Объединение этих четырех подмножеств есть множество N.
Таким образом, выделение двух свойств привело к разбиению множества N натуральных чисел на четыре класса.
Упражнения
1 . Из множества X = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12} выделили подмножества X, Х 2 и Х 3 . В каком из следующих случаев множество Х оказалось разбитым на классы:
а) Х 1 = {1, 3, 5, 7, 11}, Х 2 = {2, 4, 6, 8, 10, 12}, Х 3 = {9};
б) Х 1 = {1,3,5,7,9,11},Х 1 = {2,4,6,8, 10,12},Х 1 = {10, 11,12};
в) Х 1 = {3,6, 9, 12}, Х 2 = {1,5,7, 11},Х 3 = {2, 10}?
2. Из множества Х= {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12} выделим подмножества:
а) А - четных чисел, В - нечетных чисел;
б) А - чисел, кратных 2; В - чисел, кратных 3; С- чисел, кратных 4;
в) А - нечетных однозначных чисел; В - четных двузначных чисел. В каком случае произошло разбиение множества Х на классы?
3 . Из множества треугольников выделили подмножества треугольников:
а) прямоугольные, равнобедренные, равносторонние;
б) остроугольные, тупоугольные, прямоугольные;
в) равносторонние, прямоугольные, тупоугольные.
В каком случае произошло разбиение множества треугольников на классы?
4.На какие классы разбивается множество точек плоскости при помощи:
а) окружности;
в) прямой?
5.Перечертите комбинации фигур, приведенные на рисунке 15, и на каждой из них выделите (различными видами штриховки) непересекающиеся области.
6. На множестве натуральных чисел рассматривается свойство «быть кратным 7». Сколько классов разбиения множества N оно определяет? Назовите по два элемента из каждого класса.
7. Из множества четырехугольников выделили подмножество фигур с попарно параллельными сторонами. На какие классы разбивается множество четырехугольников с помощью свойства «иметь попарно параллельные стороны»? Начертите по два четырехугольника из каждого класса.
8 . Изобразите при помощи кругов Эйлера множество N натуральных чисел и его подмножества: четных чисел и чисел, кратных 7. Можно ли утверждать, что множество N разбито:
а) на два класса: четных чисел и чисел, кратных 7;
б) на четыре класса: четных чисел, кратных 7; четных чисел, не кратных 7; нечетных чисел, кратных 7; нечетных чисел, не кратных 7?
9 . На множестве четырехугольников рассматриваются два свойства: «быть прямоугольником» и «быть квадратом». На какие классы разобьется множество четырехугольников при помощи этих свойств? Начертите по два четырехугольника из каждого класса.
10 . Изменится ли ответ в упражнении 9, если на множестве четырехугольников рассмотреть свойства:
а) «быть прямоугольником» и «быть ромбом»;
б) «быть прямоугольником» и «быть трапецией»?
11. На рисунке 16 изображены множество X- студентов группы, А - множество спортсменов этой группы, В - множество отличников этой группы.
а) Укажите классы разбиения множества X, полученные с помощью свойств «быть спортсменом» и «быть отличником», и охарактеризуйте каждый из них.
б) Сколько получилось бы классов разбиения, если бы ни один отличник группы не был спортсменом?
Выполните соответствующий рисунок и назовите классы разбиения.
12 . Покажите, что решение нижеприведенных задач связано с разбиением заданного множества на классы:
а) 18 редисок связали в пучки по 6 редисок в каждом. Сколько получилось пучков?
б) 18 карандашей раздали 6 ученикам поровну. Сколько карандашей у каждого?
13. О каких множествах и операциях над ними идет речь в задачах:
а) С одной грядки сняли 25 кочанов капусты, а с другой - 15 кочанов. Всю эту капусту разложили в корзины, по 8 кочанов в каждую. Сколько потребовалось корзин?
б) Для школьного сада привезли 24 саженца яблонь. На одном участке посадили 6 саженцев, а на другом - остальные, в 3 ряда поровну. Сколько саженцев посадили в каждом ряду?
Понятие множества и операций над множествами позволяют уточнить наше представление о классификации.
Любая классификация связана с разбиением некоторого множества объектов на подмножества.
Определение . Множество А разбито на классы А 1 , А 2 , ..., А п , если:
1) подмножества А 1 , А 2 , ..., А п не пусты;
2) подмножества А 1 , А 2 , ..., А п попарно не пересекаются;
3) объединение подмножеств совпадает с множеством А .
Если не выполнено хотя бы одно свойство, то классификацию считают неправильной.
Например, если множество треугольников разбить на остроугольные, прямоугольные и тупоугольные, то разбиение будет выполнено верно, т.к. выполнены все условия, данные в определении.
Если из множества треугольников выделить подмножества равносторонних, равнобедренных и разносторонних треугольников, то разбиения мы не получим, т.к. множество равносторонних треугольников является подмножеством равнобедренных треугольников, т.е. не выполняется второе условие разбиения множества на классы.
Пример 1 . Пусть А – множество двузначных чисел. Рассмотрим на этом множестве свойство «быть четным».
|
|
А 1 – множество четных чисел,
А 2 – множество нечетных чисел, при этом
А 1 È А 2 = А и А 1 Ç А 2 = Æ.
Т.о. задание одного свойства приводит к разбиению этого множества на 2 класса.
Пример 2. Пусть А – множество треугольников. Рассмотрим на данном множестве два свойства: «быть прямоугольным» и «быть равнобедренным». При помощи этих свойств из множества треугольников можно выделить 2 подмножества: В С – множество равнобедренных треугольников. Эти множества пересекаются, но ни одно из них не является подмножеством другого.
По рисунку видно, что получилось 4 класса:
I – В Ç С – множество равнобедренных прямоугольных треугольников;
II – В Ç – множество прямоугольных, но не равнобедренных треугольников;
III – Ç С – множество равнобедренных, но не прямоугольных треугольников;
IV – Ç – множество не равнобедренных и не прямоугольных треугольников.
Т.о. с помощью двух свойств множество разбилось на 4 класса, таких, что их пересечение пусто, а их объединение составляет множество А .
Следует отметить, что задание двух свойств приводит к разбиению множества на 4 класса не всегда.
Пример 3 . Пусть А – множество треугольников. Рассмотрим на данном множестве два свойства: «быть прямоугольным» и «быть остроугольным». При помощи этих свойств из множества треугольников можно выделить 2 подмножества: В – множество прямоугольных треугольников и С – множество остроугольных треугольников. Эти множества не пересекаются. По рисунку видно, что при помощи этих свойств множество треугольников разбивается на три класса:
I – множество прямоугольных треугольников;
II – множество остроугольных треугольников;
III – множество не прямоугольных, не остроугольных треугольников.
Контрольные вопросы
1. При каких условиях считают, что множество разбито на классы?
2. Как определить число элементов в объединении двух или трех конечных множеств?
Множеств , где - некоторое множество индексов (конечное или бесконечное), называется разбиением , если:
При этом множества называются блоками или частями разбиения данного множества .
Разбиения конечных множеств
Разбиения конечных множеств, а также подсчет количества различных разбиений, удовлетворяющих тем или иным условиям, представляет особый интерес в комбинаторике . В частности, некоторые комбинаторные функции естественно возникают как количества разбиений того или иного вида.
Например, число Стирлинга второго рода представляет собой количество неупорядоченных разбиений n -элементного множества на m частей, в то время как мультиномиальный коэффициент выражает количество упорядоченных разбиений n -элементного множества на m частей фиксированного размера . Количество всех неупорядоченных разбиений n -элементного множества задается числом Белла .
Примеры
Wikimedia Foundation . 2010 .
- Индикатор (математика)
- Р (кириллица)
Смотреть что такое "Разбиение множества" в других словарях:
Разбиение - В математике Разбиение единицы Разбиение множества Разбиение интервала Разбиение числа … Википедия
Разбиение графа - Пример разбиения параллельной граф схемы алгоритма логического управления. В составе блоков, отмеченных разными цветами, нет параллельных вершин Разбиение графа на подграфы (англ. Graph partition) (иногда в литературе также употребляется… … Википедия
Разбиение Вороного
Разбиение Дирихле - Диаграмма Вороного случайного множества точек на плоскости Диаграмма Вороного конечного множества точек S на плоскости представляет такое разбиение плоскости, при котором каждая область этого разбиения образует множество точек, более близких к… … Википедия
РАЗБИЕНИЕ - 1) Р. представление заданного множества в виде объединения системы множеств, не имеющих попарно общих точек. В дискретной геометрии часто рассматривают Р. нек рого пространства на замкнутые области, к рые покрывают все пространство и попарно не… … Математическая энциклопедия
Разбиение числа - n это представление n в виде суммы положительных целых чисел, называемых частями. При этом порядок следования частей не учитывается (в отличие от композиций), то есть разбиения, отличающиеся только порядком частей, считаются равными. В… … Википедия
Мера множества - У этого термина существуют и другие значения, см. Мера. Мера множества неотрицательная величина, интуитивно интерпретируемая как размер (объем) множества. Собственно, мера это некоторая числовая функция, ставящая в соответствие каждому… … Википедия
Двоичное разбиение пространства - BSP дерево это структура данных, используемая в трехмерной графике. Аббревиатура BSP означает Binary Space Partition двоичное разбиение пространства. BSP дерево используется для эффективного выполнения следующих операций: Сортировки… … Википедия
ИЗМЕРИМОЕ РАЗБИЕНИЕ - пространства с мерой (М,m) разбиение x. этого пространства на непересекающиеся подмножества (именуемые элементами разбиения), к рое можно получить как разбиение на множества уровня нек рой измеримой функции (с числовыми значениями) на М. Это… … Математическая энциклопедия
НЕПРЕРЫВНОЕ РАЗБИЕНИЕ - топологического пространствах покрытие пространства Xпопарно непересекающимися непустыми множествами, удовлетворяющее условию: каковы бы ни были и окрестность Uмножества Fв X, найдется окрестность Vмножества Fв X, содержащаяся в Uи являющаяся… … Математическая энциклопедия
Книги
- Windows IT Pro/RE№ 06/2018 , Открытые системы. Windows IT Pro/RE– профессиональное издание на русском языке, целиком и полностью посвященное вопросам работы с продуктами семейства Windows и технологиям компании Microsoft. Журнал… Купить за 1176 руб электронная книга
- Минимакс и восстановление по вектору в графах , Мокряков Алексей Викторович, Селин Павел Сергеевич, Цурков Владимир Иванович. В предлагаемой книге развивается теория минимакса при транспортных ограничениях. Представлена основная постановка о поиске минимума максимального элемента матрицы с неотрицательными…
Введение
В наш бурно развивающийся век, казалось бы, все алгоритмы, которые можно придумать, уже придуманы. Но иногда встречаются задачи, для которых нет подходящих алгоритмов. Быть может потому, что задача редко встречается или, скорее всего для этой задачи нет эффективных алгоритмов (а, скорее всего, их и вовсе не существует).
В этой работе будет обсуждаться тема разбиений множеств.
В автор даёт несколько таких алгоритмов: генерирование всех подмножеств n-элементного множества, генерирование всех k-элементных подмножеств множества {1, …, n} в лексикографическом порядке, генерирование всех разбиений множества {1, …, n} (на этом алгоритме остановимся подробней), нахождение всех разбиений числа.
Первый из этих алгоритмов использует идею бинарного кода Грэя , остальные основаны на удалении или добавлении одного элемента. Последний алгоритм использует схему разбиения большего числа на меньшие числа.
Постановка задачи
Формулировка первой задачи, которую мы рассмотрим, выглядит так: необходимо сгенерировать все разбиения множества, содержащего n элементов.
Для формулировки второй задачи необходимо ввести некоторые понятия.
Итак, дано множество, состоящее из n элементов. Каждый элемент этого множества образует некоторое понятие. Два или больше понятия могут быть объединены в новое понятие. Отличительная черта понятий – взятие их в круглые скобки.
Задача выглядит так: сгенерировать все понятия, которые могут быть образованы из n элементов. Например, для n=3 имеем такие понятия (круглые скобки в начале и в конце опущены для краткости): (*)**, (*)(*)*, (*)(*)(*), (**)*, (**)(*), ((*)*)*, ((*)*)(*), ((*)(*))*, ((*)(*))(*).
Математическое обоснование
Под разбиением n-элементного множества Х на k блоков будем понимать произвольное семейство
, такое, что для 1£іОчевидно, что S(n,k)=0 для k>n. Принимают также S(0,0)=1, так как пустое семейство блоков является в соответствии с определением разбиением пустого множества. С числами Стирлинга второго порядка связано много любопытных тождеств:
S(n,k)=S(n-1,k-1)+kS(n-1,k) для 0 S(n,n)=1 для n≥0, (2) S(n,0)=0 для n>0. (3) Формулы (2) и (3) очевидны. Для доказательства формулы (1) рассмотрим множество всех разбиений множества {1, …, n} на k блоков. Это множество распадается на два различных класса: тех разбиений, которые содержат одноэлементный блок {n}, и тех разбиений, для которых n является элементом большего (по крайней мере, двухэлементного) блока. Мощность первого класса равна S(n-1,k-1), т. е. такова, каково число разбиений множества {1, …, n-1} на (k-1) блоков. Мощность другого класса составляет kS(n-1,k), так как каждому разбиению множества {1, …, n-1} на k блоков соответствует в этом классе в точности k разбиений, образованных добавлением элемента n поочерёдно к каждому блоку. Формулы (1)-(3) позволяют легко вычислять значения S(n,k) даже для больших значений n и k. Вот другая рекуррентная зависимость: Для доказательства тождества рассмотрим множество всех разбиений S(n,k) множества Х={1, …, n}. Это множество распадается на различные классы, соответствующие разным подмножествам множества Х, которые являются блоками, содержащими элемент n. Отметим, что для каждого b-элементного подмножества Число Белла
Другими словами, Докажем рекуррентную зависимость, связанную с числами Белла: (принимаем Теперь опишем алгоритм генерирования всех разбиений множества. Отметим, что каждое разбиение p множества {1,…, n} однозначно определяет разбиение Если нам дан список Разбиение множества {1, …, n} мы будем представлять с помощью последовательности блоков, упорядоченной по возрастанию самого маленького элемента в блоке. Этот наименьший элемент блока мы будем называть номером блока. Отметим, что номера соседних блоков, вообще говоря, не являются соседними натуральными числами. В этом алгоритме мы будем использовать переменные pred[і], sled[і], 1≤і≤n, содержащие соответственно номер предыдущего и номер следующего блока с номером і (sled[і]=0, если блок с номером і является последним блоком разбиения). Для каждого элемента і, 1≤і≤n, номер блока, содержащего элемент і, будет храниться в переменной blok[і], направление, в котором «движется» элемент і, будет закодировано в булевской переменной wper[і] (wper[і]=true, если і движется вперёд). Можно показать, что среднее число шагов, необходимых для построения каждого следующего разбиения, ограничено постоянной, не зависящей от n(конечно, если не учитывать число шагов, необходимых для написания разбиения). Табл.1. Последовательность разбиений множества {1,2,3,4}
Опишем теперь алгоритм решения задачи о перечислении всех понятий. Рекурсивный алгоритм использовать нельзя, так как все решения подзадачи меньшей размерности необходимо скомбинировать со всеми решениями подзадачи оставшейся размерности. Поэтому, будем просто перебирать все варианты. Идея такова: сохраняем все разбиения меньшей размерности и комбинируем их так, чтобы
