На что похожи множества вложенные одни в другие

Открытый урок по информатике «Вложенность множеств» (2-й класс, УМК «Школа–2100»)

Класс: 2

Цели:

Предварительная подготовка:

Ход урока:

— Молодцы, справились с этим заданием! Смотрите, появился драгоценный перстень. Отправляемся в следующую комнату.5 слайд
БРОШЬ— Мы не можем идти дальше пока не разберемся: Правильно ли нарисованы овалы для множеств? Докажите.
(№ 51 с.22 в слайд)6 слайд
ДИАДЕМА— Нас в следующей комнате встречает житель замка, он предлагает поработать вам в парах.
Задание «Назови подмножество» (работа в парах с карточками)

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

Самостоятельная работа с последующей проверкой (работа в тетрадях)

— Здесь вам предстоит поработать самостоятельно
№ 52 с. 22
(проверка с экраном)
— Молодцы! Для вас появляется следующая награда.5. Физкультминутка
— Как живешь?
— Вот так!
— Как идешь?
— Вот так!
— Как бежишь?
— Вот так!
— Ночью спишь?
— Вот так!
— Как берешь?
— Вот так!
— Как даешь?
— Вот так!
— Как шалишь?
— Вот так!
— Как грозишь?
— Вот так!
— Как стоишь?
— Вот так!
— А как сидишь?
(сесть на место)7 слайд
АЛМАЗ6. Продолжение работы по теме урока
— Итак, мы с вами поднимаемся в следующие покои, и по дороге вам тоже предстоит справиться с заданием.
— Сейчас вам предлагают поработать корректорами.
— Кто такие корректоры? Вот вам сейчас и предстоит поработать корректорами.
— Читаем задание в № 54 с.23
— Проверка с экраном.
— Молодцы, получаем награду и отправляемся дальше.8 слайд
БРАСЛЕТ8. Игра «Найди себя»
(Собрать на доске из цветной бумаги два вложенных множества: ДЕТИ и ДЕВОЧКИ. Затем каждый вызванный ученик должен «попасть» (написать букву своего имени) в нужное место чертежа)
— Сколько элементов в каждом множестве?
— А куда попадет имя учителя? (не попадет, т.к. не ребенок)

9. Работа по учебнику
— Сейчас на предстоит справиться с трудным заданием, но я верю, что у вас все получится.
№ 56 с.23
— Прочитайте задание. Какое нам дано отношение множеств? (Четырехугольники-прямоугольники)
— Что будет подмножеством? (прямоугольники)
— Что мы называем прямоугольниками? (это четырехугольники, у которого все углы прямые)
— Давайте найдем место для каждой фигуры. Докажите, почему так.
— Сколько элементов во множестве ПРЯМОУГОЛЬНИКИ?
— Сколько элементов во множестве ЧЕТЫРЕХУГОЛЬНИКИ?9. Работа с доской
— Посмотрите внимательно на эти множества и найдите место для животных.
— Сколько элементов в каждом множестве?

— А теперь вы работаете самостоятельно
— Читаем задание № 57 с.24
— Сколько элементов в каждом множестве?

Источник

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

Вы когда-нибудь спрашивали 5-летнего ребенка, кого на свете больше – женщин или людей? Ответы можно услышать весьма любопытные:)

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

Мы недавно с Максом (7 лет) обсудили серию таких задачек. Получилось замечательно. Делюсь.

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

Вот, к примеру, 5 картинок – кукла, мячик, корабль, машина и самолет. А еще 2 круга – из веревочек, бумаги или проволоки.

1 задание: разложи-ка, дружок, в один круг карточки с игрушками, в другой – с транспортом.

Нет проблем, понятно.

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

3 задание: Положи в первый круг все неживое, во второй – транспорт. Макс опять выкладывает пересекающиеся круги.

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

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

А теперь более серьезная задача: а что будет с тремя множествами? Во-первых, как они могут располагаться друг относительно друга. Вопрос интересный: случаев получается довольно много. Макс всерьез озадачился и начал рисовать.

Вы сумеете найти ВСЕ оставшиеся случаи?:)

Отдельная задачка – доказать, что две нарисованные схемы разные. Или одинаковые. Макс, к примеру, предлагал нарисовать один круг поменьше – тогда, говорит, по-другому получится. После некоторых размышлений передумал.

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

А потом случилось то, ради чего, собственно, я и занимаюсь с собственным ребенком и другими детками. У сына загорелись глаза, он нарисовал вот такую штуку и сказал: «Мам, а давай я задачку к этой схеме придумаю!»

Схема, нарисованная Максом

Вот он, момент, когда ребенку стало интересно и он что-то хочет сделать и исследовать САМ!

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

Вот что придумал Макс

Меня распирало чувство гордости. Подозреваю, сравнимое по силе с восторгом Макса, когда он изобретал свое решение:)

В качестве бонуса задачки на множества от Жени Кац.

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

Источник

Урок информатики «Вложенность множеств»

Урок информатики во 2 классе

Тема урока : Вложенность множеств.

Формирование универсальных учебных действий обучающихся:

1.Познавательные : анализ и преобразование информации, формирование основных мыслительных операций (классификации, синтеза, аналогии).

2. Регулятивные: планирование своей деятельности, умение самостоятельно двигаться по заданному плану, самостоятельная оценка и корректировка полученного результата.

3. Коммуникативные : формирование и развитие математического языка, использование в речи терминов и понятий информатики, умение работать в парах

Основные предметные цели:

Изучить отношения между множествами.

Познакомить с понятием «вложенности» (включения) множеств.

Познакомить с понятием «подмножество».

Изучить равенство множеств, как частный случай «включения»

Подготовить карточки с заданием

Подготовить разноуровневую проверочную работу

Напечатать таблички «Множество», «Подмножество».

1. Организационный момент

3. Новый материал
— У ворот замка стоит стражник. Он в недоумении: в замок принесли дары, но свалили их все в кучу. Помогите стражнику разложить их по мешочкам, а за это он нас пропустит в замок.

На доске в хаотичном расположении рисунки игрушек: 4 куклы, 4 машинки, 3 смешарика. На доске нарисованы 3 мешка . Задание : разложить предметы по мешочкам. Выходит ученик, раскладывает игрушки по мешочкам с помощью магнитов.

— Молодец! Правильно разложил подарки по мешочкам. Садись на своё место.

— Ребята, как можно назвать первое получившееся множество? ( множество КУКЛЫ) Второе получившиеся множество? (множество МАШИНКИ). Третье получившиеся множество? ( множество СМЕШАРИКИ)
— Сколько элементов в каждом множестве? (4, 4, 3)
— Мы получили много мешков, а теперь мы можем все эти мешочки положить в один большой мешок (появляется большой мешок). Как можно назвать этот мешок? (игрушки)
— Скажите, чего больше: кукол или игрушек? Машинок или игрушек? Смешариков или игрушек?
— Одно множество может быть часть другого множества.
Такое отношение множеств называется включением (или вложенностью множеств), при этом маленькие множества (мешочки) называются подмножества большого множества (мешка). (на доску вывешиваются таблички МНОЖЕСТВО, ПОДМНОЖЕСТВО)
Все элементы маленьких множеств (например, Смешарики) называются элементами большого множества (Игрушки)
— Ну я смотрю, что вы и впрямь готовы к приключениям, и стражник готов нас впустить.

4. Первичное закрепление
— В замке задания встречаются на каждом шагу, точнее в каждой комнате. Но замок Небес всегда вознаграждает за внимательность, сообразительность и работу.
— Во дворе замка нас встречает один из его обитателей (появляется гномик ) и предлагает вам с ним сыграть в игру «Кого на свете больше?»
— Помним, что чего больше – это множество, а чего меньше – это подмножества.

Воробьев или птиц (птиц…)

Яблок или фруктов (фруктов…)

Цветов или ромашек (цветов…)

Берез или деревьев (деревьев…)

Зверей или зайцев (зверей…)

Бабочек или насекомых (насекомых…)

Шапок или головных уборов (головных уборов…)

Слив или ягод (ягод…)

Чашек или посуды (посуды…)

Птиц или попугаев (птиц…)

Предметов мебели или шкафов (предметов мебели…)

Мальчиков или детей (детей…)

Растений или деревьев (растений…)

Мячей или игрушек (игрушек…)

— Молодцы, справились с этим заданием! Смотрите, появился драгоценный перстень. Отправляемся в следующую комнату.

— Мы не можем идти дальше пока не разберемся : Правильно ли нарисованы овалы для множеств? Докажите.
( № 51 с.22 в слайд)

— Нас в следующей комнате встречает житель замка, он предлагает поработать вам в парах.
Задание «Назови подмножество» (работа в парах с карточками)

Волки и звери (волки – подмножества зверей)

Мужчины и люди (мужчины – подмножества людей)

Кроссовки и обувь (кроссовки – подмножества людей)

Музыкальные инструменты и гитары (гитары – подмножества музыкальных инструментов)

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

Самостоятельная работа с последующей проверкой (работа в тетрадях)

6. Продолжение работы по теме урока
— Итак, мы с вами поднимаемся в следующие покои, и по дороге вам тоже предстоит справиться с заданием.
— Сейчас вам предлагают поработать корректорами.
— Кто такие корректоры? Вот вам сейчас и предстоит поработать корректорами.
— Читаем задание в № 54 с.23
— Проверка с экраном.
— Молодцы, получаем награду и отправляемся дальше.

8. Игра «Найди себя»
(Собрать на доске из цветной бумаги два вложенных множества: ДЕТИ и ДЕВОЧКИ. Затем каждый вызванный ученик должен «попасть» (написать букву своего имени) в нужное место чертежа)
— Сколько элементов в каждом множестве?
— А куда попадет имя учителя? ( не попадет, т.к. не ребенок )

9. Работа по учебнику
— Сейчас на предстоит справиться с трудным заданием, но я верю, что у вас все получится.
№ 56 с.23
— Прочитайте задание. Какое нам дано отношение множеств? ( Четырехугольники-прямоугольники)
— Что будет подмножеством? ( прямоугольники)
— Что мы называем прямоугольниками? (это четырехугольники, у которого все углы прямые)
— Давайте найдем место для каждой фигуры. Докажите, почему так.
— Сколько элементов во множестве ПРЯМОУГОЛЬНИКИ?
— Сколько элементов во множестве ЧЕТЫРЕХУГОЛЬНИКИ?

— А теперь вы работаете самостоятельно
— Читаем задание № 57 с.24 и выполняйте его самостоятельно.

(Дети самостоятельно выполняют задание)

— Как назвали первое множество? (животные) Сколько в нём элементов? (13)

— Как назвали второе множество? (домашние животные) Сколько в нём элементов? (6)
— Какое множество является подмножеством? (домашние животные)

— Ну что же, молодцы, справились и с этим заданием и получаете заслуженную награду. Идем дальше.

9. Равные множества
— Вот мы с вами и в центральном зале. И снова гномик приготовил вам задание. Прочитайте вопрос.
— Какие множества называются равными? (состоящие из одинакового числа, одинаковых элементов)
— Встаньте с места ученики первого ряда. Сядьте.
— Встаньте с места дети первого ряда. Сядьте.
— Встаньте с места школьника первого ряда. Сядьте.
— Какие множества я назвала? Что вы можете сказать о множествах детей, учеников, школьников? Какой знак между ними можно поставить?
— А можно ли эти множества вложить в друг друга?
— Выполните самостоятельно задание № 58 с.24
Проверка с доской
— Молодцы. Идем дальше. И впереди вас ждет комната контроля знаний.

10. Проверка знаний
Здесь житель замка предлагает вам проверить свои знания.
Найдите в конверте на столе листок с тестом. Решите его.

Дети выполняют самостоятельную работу ( работа по вариантам)

11. Итог урока
— Давайте вспомним, что мы узнали сегодня на уроке по плану
1. Когда одно множество можно вложить в другое, это называют – включением, или вложенностью. Меньшее множество будет называться – подмножеством.
2. Элементы подмножества – это часть большого множества
3. Но множества могут быть равными, тогда их нельзя вложить в друг друга.

— Молодцы, и вы получаете еще одну драгоценность.

12. Самооценка. Рефлексия.
— Перед вами оценочная лесенка, посмотрите внимательно и подумайте, на какую ступеньку вы себя поставите? Покажите карточку с номером ступеньки. ( спросить некоторых детей, почему так) и напишите номер ступеньки на тесте. А я, когда проверю ваши работы, посмотрю на сколько совпадают наши оценки.
1. Плохо: многое не выполнил, не знаю как делать
2. Слабо: выполнил часть заданий, есть ошибки
3. Не совсем хорошо: задания выполнил не полностью, не уверен в правильности
4. Хорошо: задания выполнил, ошибки исправил
5. Отлично: задания выполнил полностью, без ошибок

13. Релаксация
— Вы сегодня молодцы, очень хорошо поработали и собрали целую шкатулку драгоценностей. Но посмотрите внимательно, что вы заметили необычного?
— Какое слово можно составить из выделенных букв? (ПОДАРОК)

Источник

Дерево каталогов NESTED SETS (вложенные множества) и управление им

автор: Сергей Томулевич
phoinix@asit.ru

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

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

На схеме представлено дерево, описанное по всем правилам метода «Вложенных множеств». Квадратами обозначены узлы дерева, синие цифры в верхнем правом и верхнем левом углах узла — уровень и уникальный идентификатор соответственно, а красные цифры в нижних углах — это левый и правый ключ. Именно в этих двух цифрах — левом и правом ключе заложена вся информация о дереве. И если информацию о ключах занести в базу данных, то работа с деревом намного упрощается. Обратите внимание на то, в каком порядке проставлены эти ключи. Если мысленно пройтись по порядку от 1 до 32, то вы обойдете все узлы дерева слева направо. Фактически это путь обхода всех узлов дерева слева направо.

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

Создадим таблицу, где мы будем хранить наше дерево:

Теперь определим, какие данные мы можем из неё (таблицы) выбрать:

1. Собственно само дерево:

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

3. Выбор родительской «ветки»:

4. Выбор ветки в которой участвует наш узел:

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

Единственным затруднением может возникнуть выборка родительского узла, чтобы его получить можно сделать запрос:

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

Управление деревом каталогов

Прежде чем начинать управлять деревом, создадим проверку целостности ключей, что бы линий раз не наступать на «грабли». Для этого определим основные правила:

Отсюда, создаем проверочные запросы:

Если все правильно то результата работы запроса не будет, иначе, получаем список идентификаторов неправильных строк;

Получаем количество записей (узлов), минимальный левый ключ и максимальный правый ключ, проверяем значения.

Если все правильно то результата работы запроса не будет, иначе, получаем список идентификаторов неправильных строк;

Если все правильно то результата работы запроса не будет, иначе, получаем список идентификаторов неправильных строк;

Здесь, я думаю, потребуется некоторое пояснение запроса. Выборка по сути осуществляется из одной таблицы, но в разделе FROM эта таблица «виртуально» продублирована 3 раза: из первой мы выбираем все записи по порядку и начинаем сравнивать с записями второй таблицы (раздел WHERE) в результате мы получаем все записи неповторяющихся значений. Для того, что бы определить сколько раз запись не повторялась в таблице, производим группировку (раздел GROUP BY) и получаем число «не повторов» (COUNT(t1.id)). По условию, если все ключи уникальны, то число не повторов будет меньше на одну единицу чем общее количество записей. Для того, чтобы определить количество записей в таблице, берем максимальный правый ключ (MAX(t3.right_key)), так как его значение — двойное число записей, но так как в условии отбора для записи с максимальным правым ключом — максимальный правый ключ будет другим, вводится третья таблица, при этом число «неповторов» увеличивается умножением его на количество записей. SQRT(4*rep +1) — решение уравнения x^2 + x = rep. Если все правильно то результата работы запроса не будет, иначе, получаем список идентификаторов неправильных строк;

Примечание: Хотя данное тестирование не дает 100% гарантии, но определит большее количество ошибок.

Создание узла

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

1. Обновляем ключи существующего дерева, узлы стоящие за родительским узлом:

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

2. Обновляем родительскую ветку:

3. Теперь добавляем новый узел :

Теперь можно объединить первые два запроса в один, что бы не делать лишних действий.

Удаление узла

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

** Получить эти данные не сложно одним простейшим запросом.

1. Удаляем узел (ветку):

2. Обновляем ключи оставшихся веток:

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

2.1. Обновление родительской ветки:

*** Так как мы не знаем точное количество подчиненных узлов, мы вычисляем длину диапазона (смещения) ключей удаляемой ветки (узла).

2.2. Обновление последующих узлов:

Теперь можно объединить последние два запроса в один, что бы не делать лишних действий.

Перемещение узла

Перемещение узла – самое сложное действие в управлении деревом. На схеме показаны области, на которые можно разделить наше дерево. Из её можно увидеть, что узел может перемещаться только в две разные области: вышестоящих и нижестоящих узлов. Вообще, чем примечательно использование Nested Set, что с помощью двух ключей ветки возможен выбор узлов любой области.

Для начала выберем ключи следующих узлов:

1. Ключи и уровень перемещаемого узла;

2. Уровень нового родительского узла (если узел перемещается в «корень» то сразу можно подставить значение 0):

3. Правый ключ узла за который мы вставляем узел (ветку):

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

Данная переменная берется в зависимости от действия:

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

4. Определяем смещения:

Где у нас изменяются ключи по дереву во время переноса узла показано на схеме:

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

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

Возможно обновление ключей в три этапа: каждая ветка отдельно и диапазон между ними. Но так как мы меняем только два ключа, причем изменение на одно и то же число, то можно обойтись и двумя командами (UPDATE).

При перемещении вверх по дереву выделяем следующие области:

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

Теперь можно переместить ветку:

После оптимизации этих запросов получаем всего один:

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

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

При перемещении вниз по дереву выделяем следующие области:

Теперь можно переместить ветку:

После оптимизации этих запросов получаем всего один:

Замечания те же, что и при перемещении ветки вверх по дереву.

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

Спасибо Максу (Maxim Matyukhin) за помощь в написании данной статьи. (12.08.2004)

Источник