Поисковые запросы и множества: как решать задание № 8 ОГЭ по информатике

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

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

Для пользователя всё это выглядит проще: мы вводим запрос и получаем список найденных страниц. Именно эту часть работы и моделирует задание № 8 ОГЭ. Для его решения нам не нужно разбираться во всех технических особенностях работы поисковых систем. Важно понять основную идею: с помощью запроса мы задаём системе условия, которым должны соответствовать найденные страницы.

В реальном поиске условия могут быть очень сложными, но в ОГЭ используется упрощённая математическая модель. Каждому слову соответствует своё множество страниц, а операции над запросами превращаются в операции над множествами.

В задании № 8 ОГЭ используются два основных оператора:

• & — логическое И (конъюнкция);
• | — логическое ИЛИ (дизъюнкция).

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

Оператор И (&)

Запрос Котики & Природа означает, что страница должна содержать и слово «Котики», и слово «Природа» одновременно. То есть подходят только те страницы, которые находятся сразу в двух множествах:

• страницы со словом «Котики»;
• страницы со словом «Природа».

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

Оператор ИЛИ (|)

Запрос: Котики | Природа означает, что подходят все страницы, которые входят хотя бы в одно из двух множеств:

• страницы со словом «Котики»;
• страницы со словом «Природа»;
• страницы, содержащие оба слова.

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

Поисковые запросы можно представить с помощью множеств. Обозначим через A страницы, на которых встречается первое слово, а через B — страницы со вторым словом. Оператор И позволяет найти страницы, принадлежащие обоим множествам одновременно.

При запросе A & B поисковая система найдёт только страницы из пересечения A и B. Поэтому их количество не может превышать количество страниц в каждом из исходных множеств.

Для операции ИЛИ каждая страница из исходных множеств входит в объединение. Поэтому результат поиска содержит все страницы из первого множества и все страницы из второго множества. При запросе A | B объединяются два множества страниц, поэтому результат поиска будет содержать не меньше страниц, чем каждое из множеств по отдельности.

Удобно запомнить:

• И — результатов не больше.
• ИЛИ — результатов не меньше.

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

Запросы удобно рассматривать как операции над множествами страниц. Пусть $A$ — множество страниц, содержащих первое слово, а $B$ — множество страниц, содержащих второе слово.

Тогда поисковому запросу A & B соответствует пересечение множеств: $A\cap B$.
Поисковому запросу A | B соответствует объединение множеств: $A\cup B$.
Будем обозначать через $N(X)$ количество страниц, входящих в множество $X$.

Обычно начинают со схемы двух кругов, а их взаимное расположение уточняют по условию. Зона пересечения множеств соответствует операции A & B. Вся область, принадлежащая хотя бы одному из двух множеств, соответствует запросу A | B.

Формула работает очень просто. При сложении количества страниц множества $A$ и количества страниц множества $B$ страницы из пересечения учитываются дважды. Поэтому их нужно один раз вычесть, чтобы получить правильный результат.

Для задач с тремя множествами (слова $A$, $B$, $C$) схема будет сложнее и включает три круга. В некоторых заданиях дополнительно указано, что два множества не пересекаются. При таком условии круги $A$ и $B$ не имеют общей области. При этом третье множество $C$ может пересекаться с каждым из них отдельно. Поскольку $N(A \& B) = 0$, то $N(A \& B \& C) = 0$, и соответствующие нулевые слагаемые можно убрать из формулы включений-исключений.

В некоторых заданиях встречаются составные запросы со скобками, например:
Волга & (Ока | Кама).

Сначала нужно определить, какие множества объединяются внутри скобок. Запрос Ока | Кама означает поиск страниц, содержащих хотя бы одно из двух слов — «Ока» или «Кама». Затем оператор & требует, чтобы на странице дополнительно встречалось слово «Волга».

Такой запрос можно представить как объединение двух множеств:

Поэтому количество страниц вычисляется по формуле:

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

Для решения таких задач используй следующий алгоритм:

1. Выписать данные и ввести обозначения для множеств.
2. Определить, что означают операторы &, | и скобки. Если запрос составной, при необходимости преобразовать его с помощью операций над множествами.
3. При необходимости нарисовать диаграмму Эйлера — Венна и отметить известные области.
4. Записать подходящую формулу включений-исключений.
5. Подставить известные значения.
6. Выполнить вычисления и найти неизвестное количество страниц.

Посмотрим, как применять алгоритм на практике.

Задача 1. Два множества (ОГЭ, открытый банк ФИПИ)

В таблице приведено количество найденных страниц:

Угол | Прямая — 180
Угол — 60
Прямая — 140

Какое количество страниц найдётся по запросу Угол & Прямая?

Шаг 1. Вводим обозначения. Пусть $У$ — множество страниц, содержащих слово «Угол», а $П$ — множество страниц, содержащих слово «Прямая».

Известно:
$N(У\cup П)=180$
$N(У)=60$
$N(П)=140$

Нужно найти $N(У\cap П)$.

Шаг 2. Нарисуем диаграмму Эйлера — Венна для визуализации.

Шаг 3. Вспоминаем формулу: $N(У\cup П)=N(У)+N(П)-N(У\cap П)$.

Шаг 4. Подставляем числа:

Шаг 5. Считаем итог:

Ответ: 20.

Задача 2. Три множества (ОГЭ, открытый банк ФИПИ)

Количество найденных страниц (в тысячах):

Пушкин & Лермонтов — 0
Лермонтов & Тургенев — 130
Пушкин | Лермонтов | Тургенев — 705
Пушкин & Тургенев — 145
Лермонтов — 240
Пушкин — 320

Какое количество страниц найдётся по запросу Тургенев?

Шаг 1. Сокращаем названия до букв: П, Л, Т.

Известно:
$N(П \& Л) = 0$
$N(Л \& Т) = 130$
$N(П|Л|Т)=705$
$N(П \& Т) = 145$
$N(Л)=240$
$N(П)=320$

Нам нужно найти $N(Т)$.

Шаг 2. Нарисуем диаграмму Эйлера — Венна для визуализации.

Шаг 3. Вспоминаем формулу:

Шаг 4. Обращаем внимание на условие $N(П \& Л) = 0$. Следовательно, и страниц, одновременно принадлежащих $П$, $Л$ и $Т$, быть не может.

Перепишем общую формулу с учётом того, что пересечение множеств $П$ и $Л$ пусто.

Шаг 5. Составляем уравнение, заменив $N(Т)$ на переменную $x$:

Шаг 6. Находим неизвестное:

Следовательно, по запросу «Тургенев» найдено 420 тысяч страниц.

Ответ: 420.

При решении задания № 8 можно перепутать операторы, забыть учесть пересечение множеств или выбрать неподходящую формулу. Разберём типичные ошибки и способы их избежать.

Ошибка 1. Путать операторы И и ИЛИ

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

Важно помнить:

• & — ищем только общую часть множеств;
• | — берём всё, что входит хотя бы в одно множество.

Удобно представлять это визуально:

• И — это пересечение кругов;
• ИЛИ — это вся область двух кругов вместе.

Ошибка 2. Забывать про пересечение при объединении множеств

При использовании оператора ИЛИ нельзя просто сложить количество страниц двух запросов. Например: $N(A|B) = N(A)+N(B)-N(A\&B)$.

Общая часть двух множеств учитывается дважды, поэтому её нужно вычесть один раз.

Ошибка 3. Решать задачу без визуализации

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

• какие множества пересекаются;
• какие множества не имеют общей части;
• где находится нужная область.

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

Ошибка 4. Выбирать неправильную формулу

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

• два множества;
• три множества;
• составной запрос со скобками.

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

Оцени своё понимание темы с помощью небольшого теста.

Вопрос 1

Какой запрос найдёт только страницы, содержащие одновременно слова «Яблоко» и «Груша»?

А) Яблоко | Груша
Б) Яблоко & Груша
В) Яблоко | Груша | Банан

Вопрос 2 (ОГЭ по информатике, задание 8)

Дано: Арбуз | Дыня — 500, Арбуз — 300, Арбуз & Дыня — 100. Найдите количество страниц, найденных по запросу «Дыня».

Чтобы решить задание № 8 ОГЭ по информатике, нужно разобраться, как поисковые запросы связаны с множествами страниц. Здесь используются два оператора и скобки:

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

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

Закрепи тему на практике: в открытом банке заданий ОГЭ по информатике от «100балльного репетитора» тебя ждут задания в экзаменационном формате. Выбирай задачу, применяй алгоритм из статьи и проверяй ответ.