Глава 12 множества и деревья


Содержание

Представление множеств. Деревья. Сбалансированные деревья.

14.1. Представление множеств с помощью деревьев

Полное двоичное дерево. T-деревья

Нарисуем точку. Из нее проведем две стрелки (влево вверх ивправо вверх) в две другие точки. Из каждой из этих точек проведем по две стрелки итак далее. Полученную картинку (в -ом слое будет точек) называют полным двоичным деревом . Нижнюю точку называют корнем . У каждой вершины есть два сына (две вершины, в которые идут стрелки) — левый и правый. У всякой вершины, кроме корня, есть единственный отец .

Пусть выбрано некоторое конечное множество вершин полного двоичного дерева , содержащее вместе с каждой вершиной и всех ее предков. Пусть на каждой вершине этого множества написано значение фиксированного типа (то есть задано отображение множества вершин в множество значений типа ). То, что получится, будем называть -деревом. Множество всех -деревьев обозначим .

Рекурсивное определение . Всякое непустое -дерево разбивается на три части: корень (несущий пометку из ), левое и правое поддеревья (которые могут быть пустыми). Это разбиение устанавливает взаимно однозначное соответствие между множеством непустых -деревьев и произведением . Обозначив через empty пустое дерево, можно написать

Поддеревья. Высота

Фиксируем некоторое -дерево. Для каждой его вершины определено ее левое поддерево (левый сын вершины и все его потомки), правое поддерево (правый сын вершины и все его потомки) и поддерево с корнем в x (вершина и все ее потомки).

Левое и правое поддеревья вершины могут быть пустыми, а поддерево с корнем в всегда непусто (содержит по крайней мере ). Высотой поддерева будем считать максимальную длину цепи его вершин, в которой — сын для всех . ( Высота дерева из одного корня равна единице, высота пустого дерева — нулю.)

Упорядоченные T-деревья

Пусть на множестве значений типа фиксирован порядок. Назовем -дерево упорядоченное дерево , если выполнено такое свойство: для любой вершины все пометки в ее левом поддереве меньше пометки в а все пометки в ее правом поддереве больше пометки в .

14.1.1. Доказать, что в упорядоченном дереве все пометки различны.

Указание. Индукция по высоте дерева.

Представление множеств с помощью деревьев

Каждое дерево будем считать представлением множества всех пометок на его вершинах. При этом одно и то же множество может иметь различные представления.

Благодаря упорядоченности каждый элемент может легко «найти свое место» в дереве: придя в какую-то вершину и сравнив себя с тем, кто там находится, элемент решает, идти ему налево или направо.

Всюду далее мы предполагаем, что на значениях типа задан порядок, и рассматриваем только упорядоченные деревья.

Деревья: ориентированные, упорядоченные и бинарные.

Дерево — это граф, который характеризуется следующими свойствами:

1. Cуществует единственный элемент (узел или вершина), на который не ссылается никакой другой элемент — и который называется КОРНЕМ .

2. Начиная с корня и следуя по определенной цепочке указателей, содержащихся в элементах, можно осуществить доступ к любому элементу структуры.

3. На каждый элемент, кроме корня, имеется единственная ссылка, т.е. каждый элемент адресуется единственным указателем.

Название «дерево» проистекает из логической эквивалентности древовидной структуры абстрактному дереву в теории графов. Линия связи между парой узлов дерева называется обычно ВЕТВЬЮ. Те узлы, которые не ссылаются ни на какие другие узлы дерева, называются ЛИСТЬЯМИ (или терминальными вершинами) Узел, не являющийся листом или корнем, считается промежуточным или узлом ветвления (нетерминальной или внутренней вершиной).

Для ориентированного графа число ребер, исходящих из некоторой начальной вершины V, называется ПОЛУСТЕПЕНЬЮ ИСХОДА этой вершины. Число ребер, для которых вершина V является конечной, называется ПОЛУСТЕПЕНЬЮ ЗАХОДА вершины V, а сумма полустепеней исхода и захода вершины V называется ПОЛНОЙ СТЕПЕНЬЮ этой вершины.

Дерево

Лес

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

Ориентированное дерево — это такой ациклический орграф (ориентированный граф), у которого одна вершина, называемая корнем, имеет полустепень захода, равную 0, а остальные — полустепени захода, равные 1. Ориентированное дерево должно иметь по крайней мере одну вершину. Изолированная вершина также представляет собой ориентированное дерево.

Вершина ориентированного дерева, полустепень исхода которой равна нулю, называется КОНЦЕВОЙ (ВИСЯЧЕЙ) вершиной или ЛИСТОМ; все остальные вершины дерева называют вершинами ветвления. Длина пути от корня до некоторой вершины называется УРОВНЕМ (НОМЕРОМ ЯРУСА) этой вершины. Уровень корня ориентированного дерева равен нулю, а уровень любой другой вершины равен расстоянию (т.е. модулю разности номеров уровней вершин) между этой вершиной и корнем. Ориентированное дерево является ациклическим графом, все пути в нем элементарны.

Во многих приложениях относительный порядок следования вершин на каждом отдельном ярусе имеет определенное значение. При представлении дерева в ЭВМ такой порядок вводится автоматически, даже если он сам по себе произволен. Порядок следования вершин на некотором ярусе можно легко ввести, помечая одну вершину как первую, другую — как вторую и т.д. Вместо упорядочивания вершин можно задавать порядок на ребрах. Если в ориентированном дереве на каждом ярусе задан порядок следования вершин, то такое дерево называется УПОРЯДОЧЕННЫМ ДЕРЕВОМ.

Введем еще некоторые понятия, связанные с деревьями.

Узел X называется ПРЕДКОМ (или ОТЦОМ), а узлы Y и Z называются НАСЛЕДНИКАМИ (или СЫНОВЬЯМИ) их соответственно между собой называют БРАТЬЯМИ. Причем левый сын является старшим сыном, а правый — младшим. Число поддеревьев данной вершины называется СТЕПЕНЬЮ этой вершины. ( В данном примере X имеет 2 поддерева, следовательно СТЕПЕНЬ вершины X равна

Если из дерева убрать корень и ребра, соединяющие корень с вершинами первого яруса, то получится некоторое множество несвязанных деревьев. Множество несвязанных деревьев называется ЛЕСОМ

Мы видели, что последовательности и списки можно опре­делить следующим образом: любая последовательность (спи­сок) с базовым типом Т — это либо:

пустая последовательность (список); либо

конкатенация (цепочка) из элемента типа Т и последова­тельности с базовым типом Т.

Здесь для определения принципов структурирования (сле­дования или итерации) используется рекурсия. Следование и итерация встречается настолько часто, что их обычно счи­тают фундаментальными «образами» как структур данных, так и «управления» в программах. Однако всегда следует помнить, что с помощью рекурсий их только можно опреде­лять, но рекурсии можно эффективно и элегантно использо­вать для определения более сложных структур.

Хорошо известным примером служат деревья. Пусть дре­вовидная структура определяется следующим образом:дре­вовидная структура с базовым типом Т — это либо:

1) пустая структура; либо

2) узел типа Т, с которым связано конечное число древовид­ных структур с базовым типом Т, называемых подде­ревьями.

Из сходства рекурсивных определений последовательно­стей и древовидных структур видно, что последовательность (список) есть древовидная структура, у которой каждый узел имеет не более одного «поддерева». Поэтому последователь­ность (список) называется также вырожденным деревом.

Существует несколько способов изображения древовидной структуры. Например, пусть базовый тип Т есть множество букв; такая древовидная структура разными способами изо­бражена на рис. Все эти представления демонстрируют одну и ту же структуру и поэтому эквивалентны. С помощьюграфа можно наглядно представить разветвляющиеся связи, которые по понятным причинам привели к общеупотребитель­ному термину «дерево». Однако довольно странно, что де­ревья принято рисовать перевернутыми или — если кто-то предпочитает иначе выразить этот факт — изображать корни дерева. Но последняя формулировка вводит в заблуждение, так как верхний узел (Л) обычно называюткорнем. Хотя мысознаем, что в природе деревья представляют собой не­сколько более сложные образования, чем наши абстракции, мы будем в дальнейшем древовидные структуры называть просто деревьями.


Упорядоченное дерево — это дерево, у которого ветви каж­дого узла упорядоченные. Следовательно, два упорядочен­ных дерева— это особые, отличные друг от друга деревья. Узел у, который находится непосредственно под узлом х, называется (непосредственным) потомком х; если л находится науровне I, то говорят, чтоу — на уровнеi-\-\. Наоборот, узелх называется (непосредственным)предком у. Считается, что корень дерева расположен на уровне 1. Макси­мальный уровень какого-либо элемента дерева называется его глубиной или высотой.

Если элемент не имеет потомков, он называется терми­нальным элементом или листом, а элемент, не являющийся терминальным, называетсявнутренним узлом. Число (непо­средственных) потомков внутреннего узла называется егостепенью. Максимальная степень всех узлов есть степень де­рева. Число ветвей, или ребер, которые нужно пройти, чтобы продвинуться от корня к узлух, называетсядлиной пути.Корень имеет длину пути 1, его непосредственные потомки — длину пути 2 и т. д. Вообще, узел на уровне i имеет длину пути L Длина пути дерева определяется как сумма длин пу­тей всех его узлов. Она также называется длиной внутрен­него пути. Например, длина внутреннего пути дерева, изображенного на рис. 2.1, равна 52.

Рис 2.1.Представления древовидной структуры.

Для того чтобы определить, что называется длиной внешнего пути, мы будем дополнять дерево специальным узлом каждый раз, когда в нем встре­чается нулевое поддерево. При этом мы считаем, что все узлы должны иметь одну и ту же степень — степень дерева. Следо­вательно, подобное расширение дерева предполагает заполнение пустых ветвей, разумеется, при этом специальные узлы не имеют дальнейших потомков. Дерево на рис. 2.1, допол­ненное специальными узлами, показано на рис. 2.3, где спе­циальные узлы изображены квадратиками.

Рис. 2.2 Два различных бинарных дерева.

Рис. 2.3. Тернарное дерево со специальными узлами.

Длина внешнего пути теперь определяется как сумма длинпутей всех специальных узлов. У дерева, приведенного на рис. 2.3, длина внешнего пути равна 153.

Число специальных узлов т, которые нужно добавить к дереву степени d, непосредственно зависит от числа п ис­ходных узлов. Заметим, что на каждый узел указывает ровно одна ветвь. Следовательно, в расширенном поддереве имеется m -f- n ветвей. С другой стороны, из каждого исходного узла выходят d ветвей, а из специальных узлов — ни одной. По­этому всего имеетсяdn -f- 1 ветвей (1 дает ветвь, указываю­щую на корень). Из этих двух формул мы получаем следую­щее равенство между числом m специальных узлов и п исход­ных узлов: dn + 1 = m -f- n, или

Максимальное число узлов в дереве заданной высоты h достигается в случае, когда все узлы имеют d поддеревьев, кроме узлов уровня h, не имеющих ни одного. Тогда в дереве степени d первый уровень содержит 1 узел (корень),уровень2 содержит d его потомков, уровень 3 содержит d 2 потомков d узлов уровня 2 и т. д. Это дает следующую величину:

в качестве максимального числа узлов для дерева с высотой h и степенью d. При d = 2 мы получаем

Упорядоченные деревья степени 2 играют особо важную роль. Они называются бинарными деревьями. Мы определяем упорядоченное бинарное дерево как конечное множество эле­ментов (узлов), каждый из которых либо пуст, либо состоит из корня (узла), связанного с двумя различными бинарными деревьями, называемыми левым и правым поддеревом корня. В следующих пунктах этого раздела мы будем рассматривать исключительно бинарные деревья и поэтому будем употреб­лять слово «дерево», имея в виду «упорядоченное бинарное дерево». Деревья, имеющие степень больше 2, называются сильно ветвящимися деревьями (multiway trees)..

Знакомыми примерами бинарных деревьев являются фамильное (генеалогическое) дерево с отцом и матерью человека в качестве его потомков (!), история теннисного турнира, где узлом является каждая игра, определяемая ее победителем, а поддеревьями — две предыдущие игры соперников; арифметическое выражение с двухместными операциями, где каждаяоперация представляет собой ветвящийся узел с операндами в качестве поддеревьев.

Энтропия и деревья принятия решений

Деревья принятия решений являются удобным инструментом в тех случаях, когда требуется не просто классифицировать данные, но ещё и объяснить почему тот или иной объект отнесён к какому-либо классу.

Давайте сначала, для полноты картины, рассмотрим природу энтропии и некоторые её свойства. Затем, на простом примере, увидим каким образом использование энтропии помогает при создании классификаторов. После чего, в общих чертах сформулируем алгоритм построения дерева принятия решений и его особенности.

Комбинаторная энтропия

Рассмотрим множество разноцветных шариков: 2 красных, 5 зеленых и 3 желтых. Перемешаем их и расположим в ряд. Назовём эту операцию перестановкой:

Давайте посчитаем количество различных перестановок, учитывая что шарики одного цвета — неразличимы.

Если бы каждый шарик имел уникальный цвет, то количество перестановок было бы 10!, но если два шарика одинакового цвета поменять местами — новой перестановки не получится. Таким образом, нужно исключить 5! перестановок зеленых шариков между собой (а также, 3! желтых и 2! красных). Поэтому, в данном случае, решением будет:

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

Все перестановки можно пронумеровать числами от до (W — 1). Следовательно, строка из log2(W) бит однозначно кодирует каждую из перестановок.

Поскольку перестановка состоит из N шариков, то среднее количество бит, приходящихся на один элемент перестановки можно выразить как:

Эта величина называется комбинаторной энтропией:

Чем более однородно множество (преобладают шарики какого-то одного цвета) — тем меньше его комбинаторная энтропия, и наоборот — чем больше различных элементов в множестве, тем выше его энтропия.

Энтропия Шеннона

Давайте рассмотрим подробнее описанное выше выражение для энтропии:

Учитывая свойства логарифмов, преобразуем формулу следующим образом:

Предположим, что количество шариков достаточно велико для того чтобы воспользоваться формулой Стирлинга:

Применив формулу Стирлинга, получаем:

(где k — коэффициент перехода к натуральным логарифмам)

Учитывая что выражение можно преобразовать:

Поскольку общее количество шариков N, а количество шариков i-го цвета — Ni, то вероятность того, что случайно выбранный шарик будет именно этого цвета является: . Исходя из этого, формула для энтропии примет вид:

Данное выражение является энтропией Шенонна.

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

Илон Маск рекомендует:  Что такое код asp iisftpservice

Сравнение двух энтропий представлено на следующем рисунке, который рассчитан для множеств, содержащих два типа объектов — А и В (суммарное количество элементов в каждом множестве — 100):

Термодинамика

Аналогичные выражения для энтропии можно получить в термодинамике:

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

Понятие энтропии играет фундаментальную роль в термодинамике, фигурируя в формулировке Второго начала термодинамики: если изолированная макроскопическая система находится в неравновесном состоянии, то наиболее вероятным является её самочинный переход в состояние с большим значением энтропии:

Демон Максвелла

Чтобы подчеркнуть статистическую природу Второго начала термодинамики в 1867 году Джеймс Максвелл предложил мысленный эксперимент: «Представим сосуд, заполненный газом определённой температуры, сосуд разделен перегородкой с заслонкой, которую демон открывает чтобы пропускать быстрые частицы в одну сторону, а медленные — в другую. Следовательно, спустя некоторое время, в одной части сосуда сконцентрируются быстрые частицы, а в другой — медленные. Таким образом, вопреки Второму началу термодинамики, демон Максвелла может уменьшать энтропию замкнутой системы»:

Позже, Лео Сциллард разрешил парадокс, но это обсуждение несколько выходит за рамки данной статьи.

Демон Максвелла == Классификатор


Если вместо «быстрых» и «медленных» частиц рассматривать объекты, принадлежащие к различным классам, тогда демона Максвелла можно рассматривать в качестве своеобразного классификатора.

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

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

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

Из рисунка видно что если разделить множество на две части, при условии что одна часть будет содержать все элементы с координатой х ≤ 12, а другая часть — все элементы, у которых х > 12, то средняя энтропия будет меньше исходной на ∆S. Это значит, что данный предикат обобщает некоторую информацию о данных (легко заметить, что при х > 12 — почти все шарики жёлтые).

Если использовать относительно простые предикаты («больше», «меньше», «равно» и т.п.) — то, скорее всего, одного правила будет недостаточно для создания полноценного классификатора. Но процедуру поиска предикатов можно повторять рекурсивно для каждого подмножества. Критерием остановки является нулевое (или очень маленькое) значение энтропии. В результате получается древовидный набор условий, который называется Деревом принятия решений:

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

В рассмотренном примере, для упрощения, все объекты характеризуются только одним атрибутом — координатой х, но точно такой же подход можно применить и к объектам со множественными атрибутами.

Также, не накладывается ограничений на значения атрибутов объекта — они могут иметь как категориальную, так и числовую или логическую природу. Нужно только определить предикаты, которые умеют правильно обрабатывать значения атрибутов (например, вряд ли есть смысл использовать предикаты «больше» или «меньше» для атрибутов с логическими значениями).

Алгоритм построения дерева принятия решений

В общих чертах, алгоритм построения дерева принятия решений можно описать следующим образом:
(мне кажется, что алгоритм описанный «человеческим языком» легче для восприятия)

Что значит «ищем предикат»?
Как вариант, можно считать, что на основе каждого элемента исходного множества можно построить предикат, который разбивает множество на две части. Следовательно, алгоритм можно переформулировать:

Как можно «на основе каждого элемента множества генерировать предикат»?
В самом простом случае, можно использовать предикаты, которые относятся только к значению какого-нибудь атрибута (например «x ≥ 12», или «цвет == жёлтый» и т.п.). Следовательно, алгоритм примет вид:

На самом деле, если рассматривать классифицируемые объекты как точки в многомерном пространстве, то можно увидеть, что предикаты, разделяющие множество данных на подмножества, являются гиперплоскостями, а процедура обучения классификатора является поиском ограничивающих объёмов (в общем, как и для любого другого вида классификаторов).

Главным достоинством является, получаемая в результате, древовидная структура предикатов, которая позволяет интерпретировать результаты классификации (хотя в силу своей «жадности», описанный алгоритм, не всегда позволяет обеспечить оптимальность дерева в целом).

Одним из краеугольных камней описанного алгоритма является критерий остановки при построении дерева. В описанных выше псевдокодах, я прекращал построение дерева только при достижении множества, в котором все элементы принадлежат к одному классу (энтропия == 0). Такой подход позволяет полностью подогнать дерево принятия решений под обучающую выборку данных, но это не всегда эффективно с практической точки зрения (полученное дерево является переобученным).

Одним из возможных критериев остановки может быть небольшое значение ∆S. Но при таком подходе, всё же, невозможно дать универсальный совет: при каких значениях ∆S следует прекращать построение дерева.

Random forest

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

Полученный в результате ансамбль деревьев (упрощённая версия Random forest) можно использовать для классификации, прогоняя классифицируемый объект через все деревья. Каждое дерево как будто «голосует» за принадлежность объекта к определённому классу. Таким образом, на основе того, какая часть деревьев проголосовала за тот или иной класс — можно заключить с какой вероятностью объект принадлежит к какому либо классу.

Данный метод позволяет достаточно адекватно обрабатывать пограничные области данных:

Можно заметить, что единичное дерево принятия решений описывает область, которая полностью содержит красные точки, в то время как ансамбль деревьев описывает фигуру, которая более близка к окружности.

Если есть желание поэкспериментировать

Я создал небольшое приложение, для сравнения дерева принятия решений и random forest. При каждом запуске приложения создаётся случайный набор данных, соответствующий красному кругу на зелёном фоне, а в результате выполнения приложения получается картинка, типа той, которая изображена выше.

  • У Вас должна быть установлена среда выполнения Java
  • Загрузите отсюда бинарник dec_tree_demo.jar
  • Для запуска приложения наберите в командной строке: java -jar dec_tree_demo.jar out.png

Исходники есть на гитхабе.

Вместо заключения

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

ДЕРЕВЬЯ, ДВУДОЛЬНЫЕ ГРАФЫ, РАЗДЕЛЯЮЩИЕ МНОЖЕСТВА И РАЗРЕЗЫ

В условиях задач принятия решений для построения электрических сетей, выбора иерархических уровней управления ими, классификации и выявления причин отказов электрооборудования и других, вводится понятие дерева.

Граф называется деревом, если он связный и не имеет циклов (рис. 5.11). Удаление любого ребра из дерева делает его несвязным. Дерево определяется как минимально связный граф, где минимальность понимается в том смысле, что он не содержит подграфа, состоящего из всех вершин, и является связным.

Рис. 5.11. Граф-дерево

Начальная вершина такого графа называется корнем. Ребра, выходяшие из корня, называются ветвями. Дерево с п вершинами имеет п — 1 ребер.

Если все вершины графа принадлежат дереву Т, то дерево Т покрывает граф (рис. 5.12).

Граф, не имеющий циклов и состоящий из к компонент, называется лесом из к деревьев. Лес из к деревьев, содержащий п вершин, имеет п — к ребер. Число различных деревьев, которые можно построить на п данных вершинах, равно

Рис. 5.12. Дерево T=h е* е4, еД, покрывающее граф

При анализе связей технологического процесса со схемой электроснабжения, устройств кодирования и передачи информации, автоматики, телемеханики, различного рода измерений применяются двудольные графы. Граф называется двудольным, если все его вершины могут быть разбиты на два непересекающихся подмножества V< и V2 (доли) так, что каждое ребро имеет одну граничную точку в V% а другую — в V2. Две вершины в нем смежны только тогда, когда они принадлежат разным множествам. Чтобы подчеркнуть эту особенность, множества вершин располагают в разных столбцах или строках (рис. 5.13).

Рис. 5.13. Двудольный граф

Все циклы двудольного графа имеют четную длину. Двудольный граф, имеющий нечетное число вершин, не содержит гамильтонова цикла.

Прикладное значение понятия двудольного графа связано с тем, что с его помощью моделируются отношения между объектами двух типов («продукт х используется при производстве изделия у*, «источник х связан с потребителем у», обмен информацией происходит между объектами х и у»).

При изучении вопросов, связанных с отделением одного множества вершин данного графа от другого, важную роль играют понятия разделяющего множества и разреза. Такие задачи возникают при изучении потоков в сетях, при оценке надежности сложных систем. Здесь фундаментальную роль играет изучение поперечных сечений (пропускной способности), а также нахождение ограничивающего поперечного сечения, которое является «узким местом», определяющим пропускную способность в целом. Другая задача связана с компоновкой отдельных элементов какого-либо устройства в отдельные блоки с минимизацией числа внешних соединений с целью повышения надежности системы (схемы), технологичности и простоты конструктивного оформления.


Разделяющим множеством называется множество ребер связного графа, после удаления которых он становится несвязным.

Например, на рис. 5.14, б множество ребер 2, е9, е$, е3> графа G является разделяющим и его удаление приводит к появлению двух компонент G ‘ и G « исходного графа.

Разрезом называется разделяющее множество, которое не имеет собственного разделяющего подмножества.

Например, множество ребер е9, е$, е3> не является разрезом, так как оно

В системах электроснабжения разрез — совокупность минимального количества элементов, одновременный отказ которых приводит к полной потере питания узла нагрузки. Это определение определяет реберную связность.

Минимальные разрезы называются простыми. Разрез, состоящий из одного ребра е (рис. 5.14, г), называется мостом. Если удаление ребер, принадлежащих разрезу, делит граф на три и более компоненты, то разрез не простой.

В задачах электроэнергетики связи между вершинами графа могут быть определены (7] как слабые, жёсткие, средние, основные, ма,юзначимые.

Слабыми являются связи (сечения), пропускная способность которых Незначительно меньше номинальной мощности генерирующих узлов Pqh* чт0 обусловлено конструктивными особенностями схемы, образованной электрически неравнопрочными связями

— меньшая величина из и Р^; е — коэффициент пропорциональности.

Жёсткими можно считать связи, для которых Wq сравнимо с Р?’ п :

Связи, не относящиеся к слабым и жёстким, являются средними.

Жёсткие, средние, а в ряде случаев и слабые связи могут быть основными, значимыми для работы ЭЭС. Основные связи составляют структуру ЭЭС. Их отключение или повреждение может привести к существенному изменению режима работы системы и нарушению сё устойчивости.

Малозначимые связи (сечения) — долевое участие которых в формировании связности узлов меньше заданного

содержит разделяющее подмножество <е?, е$, е$) (рис. 5.14, в). Это подмножество не имеет собственных разделяющих подмножеств и поэтому является разрезом.

Рис. 5.14. Разде.гяющие множества и разрезы:

а — исходный граф; б — исходный граф после удаления ребер, принадлежащих разделяющему множеству; в — исходный граф после уда.1ения ребер, принадлежащих разрезу; гмост

и пренебрежение ими, как правило, не вносит заметной погрешности в параметры режима или оценку устойчивости ЭЭС, но существенно упрощает структуру системы.

Глава 12 множества и деревья

Дерево считается ориентированным, если в корень не заходит ни одно ребро.

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

Узел является экземпляром одного из двух типов элементов графа, соответствующим объекту некоторой фиксированной природы. Узел может содержать значение, состояние или представление отдельной информационной структуры или самого дерева. Каждый узел дерева имеет ноль или более узлов-потомков, которые располагаются ниже по дереву (по соглашению, деревья ‘растут’ вниз, а не вверх, как это происходит с настоящими деревьями). Узел, имеющий потомка, называется узлом-родителем относительно своего потомка (или узлом-предшественником, или старшим). Каждый узел имеет не больше одного предка. Высота узла — это максимальная длина нисходящего пути от этого узла к самому нижнему узлу (краевому узлу), называемому листом. Высота корневого узла равна высоте всего дерева. Глубина вложенности узла равна длине пути до корневого узла.

Корневые узлы

Самый верхний узел дерева называется корневым узлом. Быть самым верхним узлом подразумевает отсутствие у корневого узла предков. Это узел, на котором начинается выполнение большинства операций над деревом (хотя некоторые алгоритмы начинают выполнение с «листов» и выполняются, пока не достигнут корня). Все прочие узлы могут быть достигнуты путём перехода от корневого узла по рёбрам (или ссылкам). (Согласно формальному определению, каждый подобный путь должен быть уникальным). В диаграммах он обычно изображается на самой вершине. В некоторых деревьях, например, кучах, корневой узел обладает особыми свойствами. Каждый узел дерева можно рассматривать как корневой узел поддерева, «растущего» из этого узла.

Поддеревья

Поддерево — часть древообразной структуры данных, которая может быть представлена в виде отдельного дерева. Любой узел дерева T вместе со всеми его узлами-потомками является поддеревом дерева T. Для любого узла поддерева либо должен быть путь в корневой узел этого поддерева, либо сам узел должен являться корневым. То есть поддерево связано с корневым узлом целым деревом, а отношения поддерева со всеми прочими узлами определяются через понятие соответствующее поддерево (по аналогии с термином «соответствующее подмножество»).

Упорядочивание деревьев

Существует два основных типа деревьев. В рекурсивном дереве или неупорядоченном дереве имеет значение лишь структура самого дерева без учёта порядка потомков для каждого узла. Дерево, в котором задан порядок (например, каждому ребру, ведущему к потомку, присвоены различные натуральные числа) называется деревом с именованными рёбрами или упорядоченным деревом со структурой данных, заданной перед именованием и называемой структурой данных упорядоченного дерева.

Упорядоченные деревья являются наиболее распространёнными среди древовидных структур. Двоичное дерево поиска — одно из разновидностей упорядоченного дерева.

Представление деревьев

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

Илон Маск рекомендует:  Что такое код pdf_open_jpeg

Деревья как графы

В теории графов дерево — связанный ациклический граф. Корневое дерево — это граф с вершиной, выделенной в качестве корневой. В этом случае любые две вершины, связанные ребром, наследуют отношения «родитель-потомок». Ациклический граф со множеством связанных компонентов или набор корневых деревьев иногда называется лесом.

Методы обхода

Пошаговый перебор элементов дерева по связям между узлами-предками и узлами-потомками называется обходом дерева. Зачастую, операция может быть выполнена переходом указателя по отдельным узлам. Обход, при котором каждый узел-предок просматривается прежде его потомков называется предупорядоченным обходом или обходом в прямом порядке (pre-order walk), а когда просматриваются сначала потомки, а потом предки, то обход называется поступорядоченным обходом или обходом в обратном порядке (post-order walk). Существует также симметричный обход, при котором посещается сначала левое поддерево, затем узел, затем — правое поддерево, и обход в ширину, при котором узлы посещаются уровень за уровнем (N-й уровень дерева — множество узлов с высотой N). Каждый уровень обходится слева направо.

Дерево

Дерево – структура данных, представляющая собой древовидную структуру в виде набора связанных узлов.

Бинарное дерево — это конечное множество элементов, которое либо пусто, либо содержит элемент ( корень ), связанный с двумя различными бинарными деревьями, называемыми левым и правым поддеревьями . Каждый элемент бинарного дерева называется узлом . Связи между узлами дерева называются его ветвями .

Способ представления бинарного дерева:

  • A — корень дерева
  • В — корень левого поддерева
  • С — корень правого поддерева

Корень дерева расположен на уровне с минимальным значением.


Узел D , который находится непосредственно под узлом B , называется потомком B . Если D находится на уровне i , то B – на уровне i-1 . Узел B называется предком D .

Максимальный уровень какого-либо элемента дерева называется его глубиной или высотой .

Если элемент не имеет потомков, он называется листом или терминальным узлом дерева.

Остальные элементы – внутренние узлы (узлы ветвления).

Число потомков внутреннего узла называется его степенью . Максимальная степень всех узлов есть степень дерева.

Число ветвей, которое нужно пройти от корня к узлу x , называется длиной пути к x . Корень имеет длину пути равную 0 ; узел на уровне i имеет длину пути равную i .

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

Имеется много задач, которые можно выполнять на дереве.

Распространенная задача — выполнение заданной операции p с каждым элементом дерева. Здесь p рассматривается как параметр более общей задачи посещения всех узлов или задачи обхода дерева.

Если рассматривать задачу как единый последовательный процесс, то отдельные узлы посещаются в определенном порядке и могут считаться расположенными линейно.

Способы обхода дерева

Пусть имеем дерево, где A — корень, B и C — левое и правое поддеревья.

Существует три способа обхода дерева:

  • Обход дерева сверху вниз (в прямом порядке): A, B, C — префиксная форма.
  • Обход дерева в симметричном порядке (слева направо): B, A, C — инфиксная форма.
  • Обход дерева в обратном порядке (снизу вверх): B, C, A — постфиксная форма.
Реализация дерева

Узел дерева можно описать как структуру:

При этом обход дерева в префиксной форме будет иметь вид

Обход дерева в инфиксной форме будет иметь вид

Обход дерева в постфиксной форме будет иметь вид

Бинарное (двоичное) дерево поиска – это бинарное дерево, для которого выполняются следующие дополнительные условия (свойства дерева поиска):

  • оба поддерева – левое и правое, являются двоичными деревьями поиска;
  • у всех узлов левого поддерева произвольного узла X значения ключей данных меньше, чем значение ключа данных самого узла X ;
  • у всех узлов правого поддерева произвольного узла X значения ключей данных не меньше, чем значение ключа данных узла X .

Данные в каждом узле должны обладать ключами, на которых определена операция сравнения меньше.

Как правило, информация, представляющая каждый узел, является записью, а не единственным полем данных.

Для составления бинарного дерева поиска рассмотрим функцию добавления узла в дерево.

Глава 12 множества и деревья

Дерево считается ориентированным, если в корень не заходит ни одно ребро.

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

Узел является экземпляром одного из двух типов элементов графа, соответствующим объекту некоторой фиксированной природы. Узел может содержать значение, состояние или представление отдельной информационной структуры или самого дерева. Каждый узел дерева имеет ноль или более узлов-потомков, которые располагаются ниже по дереву (по соглашению, деревья ‘растут’ вниз, а не вверх, как это происходит с настоящими деревьями). Узел, имеющий потомка, называется узлом-родителем относительно своего потомка (или узлом-предшественником, или старшим). Каждый узел имеет не больше одного предка. Высота узла — это максимальная длина нисходящего пути от этого узла к самому нижнему узлу (краевому узлу), называемому листом. Высота корневого узла равна высоте всего дерева. Глубина вложенности узла равна длине пути до корневого узла.

Корневые узлы

Самый верхний узел дерева называется корневым узлом. Быть самым верхним узлом подразумевает отсутствие у корневого узла предков. Это узел, на котором начинается выполнение большинства операций над деревом (хотя некоторые алгоритмы начинают выполнение с «листов» и выполняются, пока не достигнут корня). Все прочие узлы могут быть достигнуты путём перехода от корневого узла по рёбрам (или ссылкам). (Согласно формальному определению, каждый подобный путь должен быть уникальным). В диаграммах он обычно изображается на самой вершине. В некоторых деревьях, например, кучах, корневой узел обладает особыми свойствами. Каждый узел дерева можно рассматривать как корневой узел поддерева, «растущего» из этого узла.

Поддеревья

Поддерево — часть древообразной структуры данных, которая может быть представлена в виде отдельного дерева. Любой узел дерева T вместе со всеми его узлами-потомками является поддеревом дерева T. Для любого узла поддерева либо должен быть путь в корневой узел этого поддерева, либо сам узел должен являться корневым. То есть поддерево связано с корневым узлом целым деревом, а отношения поддерева со всеми прочими узлами определяются через понятие соответствующее поддерево (по аналогии с термином «соответствующее подмножество»).

Упорядочивание деревьев

Существует два основных типа деревьев. В рекурсивном дереве или неупорядоченном дереве имеет значение лишь структура самого дерева без учёта порядка потомков для каждого узла. Дерево, в котором задан порядок (например, каждому ребру, ведущему к потомку, присвоены различные натуральные числа) называется деревом с именованными рёбрами или упорядоченным деревом со структурой данных, заданной перед именованием и называемой структурой данных упорядоченного дерева.

Упорядоченные деревья являются наиболее распространёнными среди древовидных структур. Двоичное дерево поиска — одно из разновидностей упорядоченного дерева.

Представление деревьев

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

Деревья как графы


В теории графов дерево — связанный ациклический граф. Корневое дерево — это граф с вершиной, выделенной в качестве корневой. В этом случае любые две вершины, связанные ребром, наследуют отношения «родитель-потомок». Ациклический граф со множеством связанных компонентов или набор корневых деревьев иногда называется лесом.

Методы обхода

Пошаговый перебор элементов дерева по связям между узлами-предками и узлами-потомками называется обходом дерева. Зачастую, операция может быть выполнена переходом указателя по отдельным узлам. Обход, при котором каждый узел-предок просматривается прежде его потомков называется предупорядоченным обходом или обходом в прямом порядке (pre-order walk), а когда просматриваются сначала потомки, а потом предки, то обход называется поступорядоченным обходом или обходом в обратном порядке (post-order walk). Существует также симметричный обход, при котором посещается сначала левое поддерево, затем узел, затем — правое поддерево, и обход в ширину, при котором узлы посещаются уровень за уровнем (N-й уровень дерева — множество узлов с высотой N). Каждый уровень обходится слева направо.

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки

Вход Регистрация Donate FAQ Правила Поиск

Деревья в теории множеств

Теорема Кнастера — Тарского нужна для индуктивных определений. Пример. Если засунуть в неё функцию , то она докажет существование множества всех чётных натуральных чисел.

Я правильно понимаю, что с помощью этой теоремы нельзя доказать существование ? (Разумеется, при условии, что аксиома о существовании удалена из теории множеств.) Как в теории множеств доказать, что существует множество всех Лисп-деревьев? (Лисп-дерево сконструировано из пар и элементов .) Как доказать существование произвольного рекурсивного типа данных?

Заслуженный участник

Последний раз редактировалось george66 29.08.2020, 11:48, всего редактировалось 2 раз(а).

В теории множеств есть аксиома бесконечности. Допустим, есть множество , взаимно однозначно отобразимое на собственную часть. Это значит, есть функция со свойством

и элемент , в который ничего не переходит

Берём функцию , которая к любому подмножеству добавляет и

Наименьшая неподвижная точка этой функции будет множеством натуральных чисел. Без аксиомы бесконечности, конечно, ничего сделать нельзя. Множество деревьев можно строить аналогично: надо сначала найти множество, содержащее все натуральные числа и замкнутое относительно образования пары, а затем выделить из него наименьшее подмножество с такими свойствами. Но, если уже есть натуральные числа, можно проще. Полагаем

Спасибо за ответ. Меня интересует, как это сделано, исходя из официальных аксиом теории множеств. Всё-таки теория множеств претендует на звание фундамента математики. Я не помню, чтобы ради деревьев вводили какие-то специальные аксиомы.

Заслуженный участник

Заслуженный участник

Последний раз редактировалось arseniiv 01.09.2020, 16:23, всего редактировалось 6 раз(а).

Наверно, в теории типов, а не в теории множеств? И в некоторых теориях типов индуктивные типы вводятся определениями, и никто не жалуется.

По-моему, для определения произвольных индуктивных множеств всё давно придумано. Правда, прямо сейчас не вспомню последовательность действий.

— Пт сен 01, 2020 17:45:33 —

Нужно всего-то показать, что для всех разумных объединение существует, где , . Вот как теоретико-множественными средствами выделяется как наименьшее множество, удовлетворяющее аксиоме бесконечности, примерно так же можно будет определить и .

— Пт сен 01, 2020 17:52:48 —

Куратовский, Мостовский. Теория множеств, гл. III §2 Определения по индукции; теорема 1.

— Пт сен 01, 2020 18:21:46 —

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

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

Пришлось выдумывать , чтобы определить «протоконструкторы», использованные для индуктивного определения , да. Можно ли определить всё без этого, не в курсе.

Заслуженный участник

Последний раз редактировалось arseniiv 01.09.2020, 16:39, всего редактировалось 1 раз.

Кстати, я читал тему-читал, а когда стал писать, забыл. Вместо должны быть всевозможные натуральные числа и т. д..

Ещё одно дополнение: можно спросить, зачем было городить огород с , если george66 уже предложил кандидат на такое множество, из которого можно выделить множество деревьев. Ответ в том, что аналогичное построение легко сделать для произвольного множества конструкторов без угадывания подходящего множества.

(Извиняюсь, что долго не отвечал. Ну, математика срочной не бывает. )

Это я сказал, не подумав. Каждое натуральное число по фон Нейману содержит пустое множество. Все элементы каждой пары по Куратовскому населены. Так что эти понятия не совместимы.

Можно уточнить, что такое «наследственно конечные множества»? Гугл не выдаёт ничего толкового. Наверное, есть другое название?

Именно в теории множеств.

Всё придумано для определения произвольных индуктивных подмножеств . Теорема Кнастера-Тарского. Индуктивное определение задаёт подмножество какого-то множества . надо определить ранее. Да, если есть множество деревьев любого типа, из них можно выделять списки, кодировать деревья других типов…

Заслуженный участник

Последний раз редактировалось arseniiv 10.09.2020, 20:28, всего редактировалось 1 раз.

Если вы о путанице, является ли множество натуральным числом или парой, то её в таком случае быть не должно: если — натуральное, то и натуральное, а если — пара, то . Значит, если оно и то, и то, оно есть или и не является парой.

Хм, ну раз все наследственно конечные множества составляют множество (счётное), то как-то выделить его в ZFC должно быть можно. Что-то мне не приходит в голову только. Однако это должно быть просто.


Заслуженный участник

Страница 1 из 1 [ Сообщений: 9 ]

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей

Глава 12 множества и деревья

Введение в теорию множеств и комбинаторику

Сведения из теории

Понятие множества не определяется, а лишь поясняется на примерах. Можно говорить о множестве стульев в аудитории, о множестве деревьев в парке, о множестве машин на улицах города, о множестве людей на планете, о множестве людей в Европе, о множестве климатических зон, о множестве точек на прямой, о множестве натуральных чисел и т. п.

Объекты, из которых состоит множество, называются его элементами. Если в множестве A имеется элемент x , то пишут x A или A x и говорят, что элемент x входит в множество A (принадлежит множеству A , содержится в множестве A ) или что множество A содержит элемент x . Если элемент x в множество A не входит, то пишут x А .

Множества бывают конечные, бесконечные и пустые.

Множество называется конечным , если в нем содержится конечное число элементов. Например, множество рек в России конечно, множество пустынь на Земле конечно, множество деревьев в тайге конечно.

Множество называется пустым , если оно не содержит ни одного элемента. Например, множество гор Подмосковья, высота которых более 5000 м., пустое.

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

Задать множество – это значит указать необходимое и достаточное условие попадания элемента в данное множество, другими словами, указать набор признаков, по которым для любого объекта мы можем сказать, является этот объект элементом данного множества или не является.

Илон Маск рекомендует:  Сервис определения оператора мобильного абонента России MNP API json service

Если множество конечное и все его элементы известны, то говорят, что множество задано перечислением своих элементов. При этом если множество A состоит из элементов a, b , c , то пишут:

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

Характеристическим свойством элементов данного множества называется необходимое и достаточное условие попадания объекта в данное множество, выраженное словесно или с помощью математических символов. Например, читаем: множество A состоит из таких элементов , которые являются вещественными числами, большими или равными 1. Характеристическое свойство элементов, входящих в множество A, состоит из трёх ограничений:

1) объект должен быть числом ;

2) объект должен быть вещественным числом ;

3) объект должен быть вещественным числом, большим или равным единицы.

Элемент , который фигурирует в записи этого множества, называют текущим элементом множества А .

Пустые множества обозначают символом .

При задании множества учитываются указанные ниже договорённости:

1. При записи множества порядок символов, обозначающих элемент данного множества, не существен. Т. е. если множество А состоит из трёх элементов, обозначенных символами a, b , с , то мы можем записать: А = < а ; b ; с >, а можем записать: А = < с ; а ; b >. Заметим, всего видов записи множества A , состоящего из трёх элементов а, b , с, шесть.

2. Один и тот же символ нельзя употреблять для обозначения двух разных элементов. Т. е. если один из элементов множества обозначен символом а , то другой элемент символом а обозначить нельзя. Нужно применить иной символ, например а ¹.

3. Два разных символа нельзя употреблять для обозначения одного и того же элемента. Заметим, ограничения 2 и 3 позволяют сделать вывод, что если мы имеем запись А = < а; b; с >, то это значит, что в множестве А имеется в точности три различных элемента, а если мы имеем запись: A = < а ; а ; b >, то это не запись множества.

4. Элемент из множества можно взять столько раз, сколько это нужно для рассуждений, т. е., вынимая из множества элемент а , мы не лишаемся его в множестве. Он там по-прежнему присутствует. И его можем вынимать столько раз, сколько нам требуется для рассуждений.

Пусть даны множества A и В . При этом мы не указываем, какие это множества – конечные, бесконечные или пустые. Если каждый элемент множества A является элементом множества B , т. е.

то говорят, что множество А есть подмножество множества В , и пишут А В . При этом говорят, что множество В есть надмножество множества А , и пишут В А .

По определению, В и В В . Другими словами, у непустого множества всегда есть, по крайней мере, два подмножества. Т.е. непустое множество В всегда имеет, по крайней мере, два подмножества: Ǿ и В . Эти подмножества называются несобственными подмножествами (тривиальными). Все остальные подмножества множества В называются собственными подмножествами.

Если множество М конечное и состоит из n элементов, то говорят, что множество М имеет длину n и пишут: | М | = n . Если | М | = n , то подмножеств у него 2 n . Например, если М = < а; b; с >, т.е. | М | = 3, то оно имеет 2 3 = 8 подмножеств: , М , М 1 = < а >, М 2 = < b >, М 3 = < с >, М 4 = < а , b >, М 5 = < а , с >, М 6 = < b , с >. Других подмножеств у множества М нет.

Пусть даны множества A и В . Если А В и В А , то множества А и B называются равными . Другими словами, множества A и B называются равными, если выполняются следующие условия:

При этом пишут: А = В .

С помощью множеств А и В можно образовать другие множества.

Объединением множеств А и В называется такое множество С , которое состоит из всех элементов множества А и всех элементов множества В и только из этих элементов. Объединение множеств А и В обозначается символом А В . Итак,

Например, если А = < а; b; с >, В = < a; c; k >, то А В = < а; b; c; k >.

Пересечением множеств А и В называется такое множество К , которое состоит из элементов, принадлежащих одновременно и множеству А и множеству В , и только из таких элементов. Пересечение множеств А и В обозначают символом А ∩ В . Итак,

Например, если А = < a; b; с >и В =< a; c; k >, то А ∩ В = < а; c >.

Разностью множеств А и В называется такое множество М , которое состоит из элементов множества А , не входящих в множество В , и только из этих элементов. Разность множеств А и В обозначают символом А \ В . Итак,

Например, если А = < a; b; с >, В = < a; c; k >, то А \ В = < b >, а
В \ А = < d >.

В частности, если В А , то А \ В называют дополнением множества В до множества А и обозначают символом А. Например, если


Чтобы наглядно изобразить множества и их взаимосвязи, часто рисуют круги, находящиеся в аналогичных взаимосвязях. Каждый круг на рисунке изображает некоторое множество. При этом точки круга не ассоциируют с элементами множества. Т. е. круг может соответствовать как конечному множеству, так и бесконечному, так и пустому. Это изображение аналогично представлению множества в виде мешка, в котором находятся элементы множества. Мешок может содержать конечное число элементов, бесконечное число элементов, быть пустым. Круги, с помощью которых наглядно изображаются множества, называются кругами Эйлера-Венна , а способ изображения множеств с помощью кругов называется диаграммами Эйлера-Венна. Рассмотрим некоторые диаграммы Эйлера-Венна:

Каждая диаграмма соответствует определенной взаимосвязи множеств А и В :

  1. А В (рис.1);
  2. А В (рис.2 – заштрихованная часть);
  3. А ∩ В (рис. 3 – заштрихованная часть);
  4. А \ В (рис. 4 – заштрихованная часть).

Нередко бывает так, что рассматривают только подмножества одного и того же множества J . Такое множество J называют универсальным множеством. Понятие универсального множества относительно. Для каждой задачи оно свое. Например, если А – множество студентов первого курса географического факультета, В – множество студентов географического факультета, специальности «Геоэкология», С – множество спортсменов – студентов Московского госуниверситета, D – множество старост академических групп факультетов, находящихся в корпусе № 1, то в качестве универсального множества J можно взять множество студентов Московского государственного университета. Если же А – множество рек Сибири, В – множество озер Европы, С – множество морей, то в качестве универсального множества можно взять гидросферу Земли. На диаграмме Эйлера-Венна универсальное множество J изображают в виде прямоугольника (рис. 5).

Заметим, дополнение множества А до универсального множества J обозначают символом .

Нужно отметить общепринятые обозначения некоторых специальных множеств:

N – множество натуральных чисел;

Z – множество целых чисел;

Q – множество рациональных чисел;

R – множество вещественных чисел.

[ a ; b ] – множество вещественных чисел x таких, что a ≤ x ≤ b ,

[ a ; b [ – множество вещественных чисел x таких, что a ≤ x b или иначе [ a ; b );

] a ; b ] – множество вещественных чисел x таких, что а x ≤ b или иначе ( a ; b ];

] а ; b [ – множество вещественных чисел x таких, что а x b или иначе ( a ; b ).

Множество. Число элементов множества. Подмножество

Урок 11. Информатика 3 класс

Конспект урока «Множество. Число элементов множества. Подмножество»

Сегодня на уроке мы познакомимся с таким понятием, как множество и с числом элементов множества.

Ребята, на уроках информатики вы уже научились описывать состав объектов, выделять их отличительные признаки, отвечать на вопросы «Что это такое?» и «Кто это такой?». Также научились отвечать на вопрос «Как это делается?» с помощью составления алгоритма. Но существуют и другие вопросы, на которые нужно уметь отвечать. Например, как определить относится ли объект к данной группе? А чтобы узнать, как ответить на этот вопрос, давайте для начала отгадаем загадки.

Он любит мёд
Зимой он спит
Весной хороший аппетит!

Крепко сбит да невысок,
На носу – крепкий рог,
Кто его дразнить посмеет –
Того он на свой рог подденет.

Он один сидит на ветке,
Зорок глаз и когти цепки,
Всех в два счёта б поборол,
Потому что он – .

Гнездо своё он в поле вьёт,
Где тянутся растения.
Его и песни, и полет
Вошли в стихотворения
!

Симпатичен, сер, усат,
Его хвостик полосат.
Пищу грязной не грызёт —
Моет всё в воде
.

Днём спит, ночью летает,
Ухает, людей пугает.
В темноте горят глаза –
Всем мышам она гроза.

Он хвостатый и усатый,
И, конечно, полосатый.
̶ Рррр, ̶ рычит, ̶ мне не до игр.
Кто же это, дети?

Эта птица всем знакома ̶
Важно ходит возле дома

Кар-Кар-Кар вдруг закричит,
И спокойно улетит.

Он других не обижает.
Ест траву, в лесу гуляет,
Но ветвистыми рогами
Может справиться с волками!

По велению волшебной палочки объекты все распределились вот так!

И получилось две группы. Как мы разделили объекты? По общему признаку. В одной группе у нас находятся животные, а в другой птицы.

А теперь посмотрите – из первых букв можно сложить слово. Какое? Слово «Множество«. И это очень важное слово для нашего урока!

Под множеством понимают объединение объектов на основе каких-то общих свойств или признаков.

Чтобы узнать принадлежит объект данному множеству или нет, достаточно выделить характерный признак, по которому точно можно определить, что этот объект можно включить в данное множество. Другой же предмет, у которого этот признак отсутствует, включать в это множество нельзя.

Глядя на две наши группы, можно сказать, что у нас есть два множества: множество животных и множество птиц.

Какие объекты входят в эти множества?

В первое множество входят: медведь, енот, олень, носорог, тигр.

Во второе множество: орёл, жаворонок, сова, ворона.

Объекты, которые принадлежат множеству, называются элементами множества.

Как вы думаете, от какого слова произошло название «множество»? Много.

А сколько это много? Точно мы сказать не можем.

Во множестве может быть любое количество элементов, даже один элемент. Может быть бесконечно большое число элементов, например, множество чисел. А также может быть и такое, что во множестве не будет ни одного элемента. Такое множество называется пустым. Например, множество чисел, которые делятся на ноль. Мы знаем, что нет таких чисел, которые бы делились на ноль, ведь на ноль делить нельзя.


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

А сколько всего элементов в наших множествах? Во множестве животных пять, а во множестве птиц четыре.

А как нам отмечать объекты во множестве, не рисовать же рисунки всё время? А отмечать объекты мы будем точками.

И так в нашем множестве животных пять объектов, значит, ставим пять точек: раз, два, три, четыре, пять.

Как можно показать, что они вместе составляют одно множество? Обвести их.

Теперь тоже самое делаем для множества птиц. Ставим четыре точки и обводим их.

Итак, ребята у нас получилось множество животных, в которое входит пять элементов и множество птиц, в это множество входят четыре элемента.

А сейчас я предлагаю вам построить пирамиду множеств.

На первом этаже будут жить четыре элемента, на втором – три, на третьем – два. На четвёртом этаже будет жить один элемент, а на чердаке – никто не будет жить. Давайте посмотрим какие это множества, и разместим их по этажам, так, чтобы на каждом этаже находилось множество с соответствующим количеством элементов.

Итак! Согласные в слове «пирамида». Сколько согласных в слове «пирамида»? Четыре. Значит, это множество разместим на этаж, где будут жить четыре элемента.

Крылья у птицы. У птицы два крыла, значит, помещаем туда, где два элемента.

Ученики шестнадцатого класса. Шестнадцатого класса? Хм, это пустое множество, нет в школе 16 класса. Помещаем на чердак.

Зимние месяцы. Их три. Помещаем на второй этаж.

Гласные в слове «торт». В этом слове одна гласная – это буква о. Помещаем на четвёртый этаж.

Множества расставлены по своим местам. И пирамида готова!

Но, несмотря на то, что на чердаке находится пустое множество, там не так уж и пусто. Оказывается, там лежала записка.

А я очень любопытная и мне хочется её прочитать. Надеюсь, вы не против…

«Это письмо множества. Если вы его нашли, то обязаны выполнить одно очень важное задание. Выбрасывать это письмо или не выполнять задание нельзя. Если вы его всё-таки выбросите, то получать вам по информатике только двойки. » Я не хочу получать по информатике двойки, как и вы, надеюсь, поэтому будем выполнять.

А вот и само задание!

«Необходимо, разместить объекты во множества. Но будьте очень внимательны. Всё не так просто, как вам может показаться».

Для начала давайте прочитаем названия элементов множеств: сосна, яблоня, ель, вишня, дуб, ромашка.

А теперь прочитаем названия множеств: деревья, плодовые деревья, растения.

Какой фигурой обозначено множество плодовых деревьев? Кругом.

Какие элементы войдут в это множество? Яблоня, вишня.

Перенесём название элементов в круг.

А теперь запишем элементы множества деревьев.

Сосна, яблоня, ель, вишня, дуб. Впишем их в квадрат.

А как получилось, что яблоня и вишня входят в оба множества?

Яблоня и вишня, это – плодовые деревья. Все плодовые деревья входят и во множество деревьев.

Какое множество больше: плодовых деревьев или всех деревьев?

Множества деревьев больше, так как в него входят все плодовые деревья и остальные деревья тоже.

По велению волшебной полочки получилось следующее.

Оказывается, если ВСЕ элементы одного множества входят в другое более крупное множество, то первое является подмножеством второго. Значит, во множестве деревьев есть подмножество плодовые деревья.

Однако есть ещё одно множество – растений. Назовём его элементы. Это все элементы в списке: сосна, яблоня, ель, вишня, дуб, ромашка. Они все растения.

Ребята, получается, что это множество ещё больше: в него входят все элементы, из предыдущих множеств и ещё ромашка. Впишем эти элементы в прямоугольник.

По велению нашей волшебной палочки произошло следующее.

Рассмотрите, что получилось. Есть большое множество растений, в которое входят ромашка и подмножество Деревья. А в подмножество Деревья входит подмножество Плодовые деревья.

Ребята, сегодня вы узнали, что такое множество.

Множество – это объединение объектов на основе каких-то общих свойств или признаков.

Сколько же элементов может быть во множестве? Сколько угодно. И один, и два, и бесконечно много, и даже ни одного. Такое множество называется пустым.

А так же вы узнали, что есть множество, которое входит в другое множество и оно называется подмножеством.

Я надеюсь, что урок для вас был и полезным, и интересным.

Понравилась статья? Поделиться с друзьями:
Кодинг, CSS и SQL