Круги эйлера задачи по информатике: Круги Эйлера в информатике

Круги Эйлера в информатике

Сегодня разберём задачи на круги Эйлера в информатике.

Леонард Эйлер — швейцарский, немецкий и российский математик и механик, сыгравший огромную роль в развитии этих наук.

Задача (Простая)

В языке запросов поискового сервера для обозначения логической операции «ИЛИ» используется символ «|», а для логической операции «И» — символ «&». В таблице приведены запросы и количество найденных по ним страниц некоторого сегмента сети Интернет.

Какое количество страниц (в тысячах) будет найдено по запросу Пушкин & Лермонтов? Считается, что все запросы выполнялись практически одновременно, так что набор страниц, содержащих все искомые слова, не изменялся за время выполнения запросов.

Решение:

Видим, что по запросу «Пушкин» в поисковике нашлось 3500 страниц. По запросу «Лермонтов» — 2000 страниц.

Запрос «Пушкин | Лермонтов» обозначает, что поисковик выдаст страницы, где есть слова про «Пушкина», и страницы, где есть слова про «Лермонтова», а так же могут быть страницы, где написано и про «Пушкина», и про «Лермонтова» одновременно.

Если сложить страницы, в которых написано про «Пушкина» и про «Лермонтова» получается 3500 + 2000 = 5500 страниц. Но почему же при запросе «Пушкин | Лермонтов» получается меньше страниц, всего 4500 ?

Этот факт обозначает то, что когда мы подсчитывали страницы про «Пушкина» (3500 страниц), мы подсчитали и те страницы, где было написано и про «Пушкина», и про «Лермонтова» одновременно.

Тоже самое и для количества страниц, где написано про «Лермонтова» (2000 страниц). В этом числе находятся и те, в которых одновременно упоминается и про «Пушкина», и про «Лермонтова».

В вопросе спрашивается, сколько страниц будет по запросу «Пушкин & Лермонтов«. Это обозначает, что как раз нужно найти количество страниц, где будет одновременно написано и про «Пушкина», и про «Лермонтова».

Отсюда получается:

Это и будет ответ!

Теперь решим эту задачу с помощью Кругов Эйлера!

У нас всего есть две сущности: «Пушкин» и «Лермонтов». Поэтому рисуем два пересекающихся круга, желательно разными цветами.

Объединение двух кругов в общую фигуру (показано фиолетовым цветом), показывает операцию «Пушкин | Лермонтов». Эта операция всегда стремится увеличить площадь, объединить площади других фигур!

Обратите внимание, что круги пересекаются, из-за этого сумма площадей двух кругов по отдельности (3500 + 2000 = 5500) больше чем у фигуры, которая характеризует логическую операцию «ИЛИ» «Пушкин | Лермонтов» (4500).

Нужно найти площадь фигуры Пушкин & Лермонтов, которая закрашена золотистым цветом. Данная логическая операция «И» стремится уменьшить площадь. Она обозначает общую площадь других фигур.

Найдём сначала заштрихованную часть синего круга. Она равна: площадь фиолетовой фигуры (4500) минус площадь красного круга (3500).

Теперь легко найти площадь золотистой фигуры. Для этого нужно от площади синего круга вычесть площадь заштрихованной части. Получается:

Получается, что по запросу Пушкин & Лермонтов будет найдено 1000 страниц.

Рассмотрим ещё одну не сложную разминочную задачу.

Задача (Разминочная)

В языке запросов поискового сервера для обозначения логической операции «ИЛИ» используется символ «|», а для логической операции «И» – символ «&».

В таблице приведены запросы и количество найденных по ним страниц некоторого сегмента сети Интернет.

Какое количество страниц (в тысячах) будет найдено по запросу Ананас?

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

Решение:

У нас две сущности: Кокос и Ананас. Нарисуем два круга Эйлера, которые пересекаются между собой. Так же отменим все имеющееся данные.

Найдём заштрихованную часть красного круга.

Весь красный круг 2100. Золотистая область равна 900. Заштрихованная часть равна 2100 — 900 = 1200.

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

Ответ: 2200

Разберём классическую задачу из информатики по кругам Эйлера.

Задача (Классическая)

В языке запросов поискового сервера для обозначения логической операции «ИЛИ» используется символ «|», а для логической операции «И» — символ «&».

В таблице приведены запросы и количество найденных по ним страниц некоторого сегмента сети Интернет.

Какое количество страниц (в тыс. ) будет найдено по запросу Космос & Звезда?

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

Решение:

В этой задаче у нас три сущности: Космос, Планета, Звезда. Поэтому рисуем три круга Эйлера, которые пересекаются между собой.

Могут ли круги не пересекаться ? Могут! Если мы докажем, что площади по отдельности двух кругов в сумме дают площадь фигуры, которая получается при применении операции логического «ИЛИ».

Теперь отметим на нашем рисунке запрос (Космос & Звезда) | (Космос & Планета).

Сначала отменим для себя то, что находится в скобках. Первое Космос & Звезда

Теперь отметим вторую скобку Космос & Планета.

В выражении (Космос & Звезда) | (Космос & Планета) две скобки соединяет знак логического «ИЛИ». Значит, эти две области нужно объединить! Область (Космос & Звезда) | (Космос & Планета) отмечена фиолетовым цветом!

Отметим Космос & Планета ещё раз, т.к. для этого выражения известно количество страниц.

Площадь фигуры для выражения Космос & Планета & Звезда будет очень маленькая. Это общая часть для всех трёх кругов. Отметим её оранжевым цветом! Каждая точка этой фигуры должна одновременно быть в трёх кругах!

Найти нужно Космос & Звезда. Отменим на рисунке чёрным цветом ту область, которую нужно найти. Мы эту область уже отмечали салатовым цветом.

Теперь у нас есть все компоненты, чтобы решить эту задачу.

Найдём заштрихованную область.

Вся область Космос & Планета равна 600. А заштрихованная часть равна: область Космос & Планета (600) минус оранжевая область (50).

Тогда черная область легко находится: фиолетовая область (1100) минус заштрихованная область (550).

Ответ: 550

Закрепляем материал по задачам на Круги Эйлера.

Задача (На закрепление)

В языке запросов поискового сервера для обозначения логической операции «ИЛИ» используется символ «|», а для обозначения логической операции «И» – символ «&». В таблице приведены запросы и количество найденных по ним страниц некоторого сегмента сети Интернет.

Какое количество страниц (в тысячах) будет найдено по запросу Море & Пляж & Солнце? Считается, что все запросы выполнялись практически одновременно, так что набор страниц, содержащих все искомые слова, не изменялся за время выполнения запросов.

Решение:

В задаче используются три сущности: Море, Пляж, Солнце. Поэтому нарисуем три пересекающихся круга Эйлера.

Отметим все области для которых нам даны количество страниц.

В начале отметим Море & (Пляж | Солнце). Для начало нарисуем область, которая в скобках (Пляж | Солнце)

Теперь нужно очертить общую часть фиолетовой области и зелёного круга и получится Море & (Пляж | Солнце). Отметим оранжевым цветом.

Теперь отметим Море & Пляж.

Теперь отметим Море & Солнце.

Найти нужно ту область, которая получается в результате выделения общей части для всех трёх кругов! Обозначим её чёрным цветом!

Найдём заштрихованную область!

Чтобы найти искомую чёрную область, нужно из Море & Пляж (355) вычесть заштрихованную область (175).

Ответ: 180

Решим ещё одну тренировочную задачу из информатики на Круги Эйлера.

Задача (с 4 сущностями)

В языке запросов поискового сервера для обозначения логической операции «ИЛИ» используется символ «|», а для обозначения логической операции «И» – символ «&».

В таблице приведены запросы и количество найденных по ним страниц некоторого сегмента сети Интернет.

Какое количество страниц (в тысячах) будет найдено по запросу

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

Решение:

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

Четвёртый круг для Ирландии нужно нарисовать так, чтобы он проходил через область (Англия & Уэльс & Шотландия). Это нам подсказывает сама таблица, где есть количество страниц для Англия & Уэльс & Шотландия, а так же для Англия & Уэльс & Шотландия & Ирландия.

Нужно отметить на рисунке Англия & (Уэльс & Шотландия | Ирландия). Это будем делать, как всегда поэтапно.

Область Уэльс & Шотландия выглядит так:

Добавим к этой области Ирландию через логическое «ИЛИ». Получается область (Уэльс & Шотландия | Ирландия). Произошло объединение серой области и жёлтого круга!

Теперь нужно сделать операцию логического «И» получившийся области с «Англией». Тогда область Англия & (Уэльс & Шотландия | Ирландия) примет вид:

Т.е. это общее между предыдущем серым контуром и красным кругом!

Отметим Англия & Уэльс & Шотландия — это общая территория трёх кругов: Красного, Синего и Зелёного. Отмечено оранжевым цветом.

Отметим Англия & Уэльс & Шотландия & Ирландия — это общая территория четырёх кругов. Область получается ещё меньше. Если взять точку в этой области, то мы будем находится сразу в четырёх кругах одновременно. Отмечено фиолетовым цветом.

Отметим то, что нужно найти Англия & Ирландия чёрным цветом.

Искомую чёрную область легко найти, если из серой области вычесть кусочек, окрашенный в бирюзовый цвет!

Найдём, сколько страниц приходится на бирюзовый кусочек:

Найдём искомую чёрную область.

Это и будет ответ!

Ответ: 324.

Разберём задачу из реального экзамена по информатике, которая была в 2019 году в Москве! (Сейчас в 2021 задачи не встречаются на Круги Эйлера)

Задача (ЕГЭ по информатике, 2019, Москва)

В таблице приведены запросы и количество страниц, которые нашёл поисковый сервер по этим запросам в некоторым сегменте Интернета:

Сколько страниц (в тысячах) будет найдено по запросу

Решение:

Видим, что у нас три поисковых разных слова, поэтому будет три разных круга Эйлера!

Так же видим, что логическое «И» между словами Корзина и Эклер даёт 0 страниц. Это значит, что эти круги не пересекаются! Так же круги бы не пересекались, если бы операция логического «ИЛИ» совпадала бы с суммой этих кругов.

Видим, что Суфле имеет с двумя кругами пересечения, а Корзина и Эклер не пересекаются.

Отметим всё, что нам дано в условии.

Жёлтым цветом отмечено Суфле | Корзина | Эклер . Объединение всех трёх кругов. Это то, что нужно найти.

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

Левая заштрихованная область находится просто:

Так же найдём площадь правой заштрихованной области:

Теперь можно найти искомую жёлтую область

Количество страниц (Суфле | Корзина | Эклер) =
= Красный круг (450) + лев. заштрих. область (310) + прав. заштрих. область (130) =
= 450 + 330 + 130 = 910

Задача решена, можно писать ответ.

Ответ: 910

Разберём ещё одну задачу из реального ЕГЭ уже 2020 года

Задача (ЕГЭ по информатике, 2020, Москва)

В таблице приведены запросы и количество страниц, которые нашёл поисковый сервер по этим запросам в некоторым сегменте Интернета:

Сколько страниц (в тысячах) будет найдено по запросу

Решение:

Количество страниц при запросе Заря & Крейсер равно нулю. Значит, эти два круга не будут пересекаться.

Нарисуем все данные на рисунке.

Нужно найти для начала заштрихованную правую часть.

Левую заштрихованную область легко найти.

Тогда для правой заштрихованной области получается:

Тогда искомую область легко найти:

Ответ: 16

На этом всё! Надеюсь, вы теперь будете с удовольствием решать задачи по информатике с помощью Кругов Эйлера.

Решение задач с помощью кругов Эйлера

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

 Задача №1

В языке запросов поискового сервера для обозначения логической операции «ИЛИ» используется символ «|», а для логической операции «И» — символ «&».

В таблице приведены запросы и количество найденных по ним страниц некоторого сегмента сети Интернет.

Какое количество страниц (в тысячах) будет найдено по запросу Торты?Считается, что все запросы выполнялись практически одновременно, так что набор страниц, содержащих все искомые слова, не изменялся за время выполнения запросов.

Решение задачи №1

Для решения задачи отобразим множества Тортов и Пирогов в виде кругов Эйлера.

Обозначим каждый сектор отдельной буквой (А, Б, В).

Из условия задачи следует:

Торты │Пироги =  А+Б+В = 12000

Торты & Пироги = Б = 6500

Пироги = Б+В = 7700

Чтобы найти количество Тортов (Торты = А+Б), надо найти сектор А, для этого из общего множества (Торты│Пироги) отнимем множество Пироги.

Торты│Пироги – Пироги = А+Б+В-(Б+В) = А = 1200 – 7700 = 4300

Сектор А равен 4300, следовательно

Торты = А+Б = 4300+6500 = 10800

Задача №2

В языке запросов поискового сервера для обозначения логической операции «ИЛИ» используется символ «|», а для логической операции «И» — символ «&».

В таблице приведены запросы и количество найденных по ним страниц некоторого сегмента сети Интернет.

Какое количество страниц (в тысячах) будет найдено по запросу Выпечка?

Считается, что все запросы выполнялись практически одновременно, так что набор страниц, содержащих все искомые слова, не изменялся за время выполнения запросов. Решение задачи №2

Для решения задачи отобразим множества Пироженых и Выпечек в виде кругов Эйлера.

Обозначим каждый сектор отдельной буквой (А, Б, В).

Из условия задачи следует:

Пироженое & Выпечка = Б = 5100

Пироженое = А+Б = 9700

Пироженое │ Выпечка =  А+Б+В = 14200

Чтобы найти количество Выпечки (Выпечка = Б+В), надо найти сектор В, для этого из общего множества (Пироженое │ Выпечка ) отнимем множество Пироженое.

Пироженое │ Выпечка – Пироженное = А+Б+В-(А+Б) = В = 14200–9700 = 4500

Сектор В равен 4500, следовательно  Выпечка = Б + В = 4300+5100 = 9400

Задача №3
В таблице приведены запросы к поисковому серверу. Расположите номера запросов в порядке убывания количества страниц, которые найдет поисковый сервер по каждому запросу.
Для обозначения логической операции «ИЛИ» используется символ «|», а для логической операции «И» — символ «&».

Решение задачи №3

Представим множества овчарок, терьеров и спаниелей в виде кругов Эйлера, обозначим сектора буквами (А, Б, В, Г).

Преобразим условие задачи в виде суммы секторов:

спаниели │(терьеры & овчарки) = Г + Б

спаниели│овчарки = Г + Б + В

спаниели│терьеры│овчарки = А + Б + В + Г

терьеры & овчарки = Б

Из сумм секторов мы видим какой запрос выдал больше количества страниц.

Расположим номера запросов в порядке убывания количества страниц: 3 2 1 4

Задача №4

В таблице приведены запросы к поисковому серверу. Расположите номера запросов в порядке возврастания количества страниц, которые найдет поисковый сервер по каждому запросу.
Для обозначения логической операции «ИЛИ» используется символ «|», а для логической операции «И» — символ «&».

Решение задачи №4

Представим множества классицизм, ампир и классицизм в виде кругов Эйлера, обозначим сектора буквами (А, Б, В, Г).

Преобразим условие задачи в виде суммы секторов:

барокко│ классицизм │ампир = А + Б + В + Г
барокко │(классицизм & ампир) = Г + Б
классицизм & ампир = Б
барокко│ классицизм = Г + Б + А

Из сумм секторов мы видим какой запрос выдал больше количества страниц.

Расположим номера запросов в порядке возрастания количества страниц: 3 2 4 1

Задача №5В таблице приведены запросы к поисковому серверу. Расположите номера запросов в порядке возврастания количества страниц, которые найдет поисковый сервер по каждому запросу.
Для обозначения логической операции «ИЛИ» используется символ «|», а для логической операции «И» — символ «&».

Решение задачи №5

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

K —  канарейки,

Щ – щеглы,

С – содержание,

Р – разведение.

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

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

В порядке возрастания по количеству страниц запросы будут представлены в следующем порядке: 4 3 2 1

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

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

Задачи для самостоятельного решения

Задача №6

В таблице приведены запросы к поисковому серверу. Расположите номера запросов в порядке возрастания количества страниц, которые найдет поисковый сервер по каждому запросу.
Для обозначения логической операции «ИЛИ» используется символ «|», а для логической операции «И» — символ «&».

Задача №7

В таблице приведены запросы к поисковому серверу. Расположите номера запросов в порядке возрастания количества страниц, которые найдет поисковый сервер по каждому запросу.
Для обозначения логической операции «ИЛИ» используется символ «|», а для логической операции «И» — символ «&».

Использованные материалы >>> 

Решение подобных задач  по информатике >>>

Ответы к задачам для самостоятельного решения

Кенигсбергские мосты.

«В целом в математике верно утверждение, что между математическим открытием и моментом, когда оно становится полезным, существует промежуток времени». — Джон фон Нейман (1903–1957)

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

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

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

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

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

  title={Онлайн-проблема абстракции для диаграмм Эйлера},
  автор = {Дженнаро Кордаско, Росарио Де Кьяра и Эндрю Фиш},
  booktitle={ED@Диаграммы},
  год = {2012}
}