Теоритический материал для задания №8 по информатике

Задание 8: Оценка количества результатов поискового запроса

Основные понятия

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

  • Операция «И» (логическое умножение) - обозначается знаком & или AND
  • Операция «ИЛИ» (логическое сложение) - обозначается знаком | или OR
  • Операция «НЕ» (логическое отрицание) - обозначается знаком ~ или NOT

Визуализация логических операций

Операция «И» (AND)

Результат = только пересечение

↓

Меньше результатов

Операция «ИЛИ» (OR)

Результат = все области

↓

Больше результатов

Множество A
Множество B

Примеры поисковых запросов

Кошки & Собаки

Найдутся страницы, где есть и кошки, и собаки

∩

Результатов меньше, чем по каждому слову отдельно

Кошки | Собаки

Найдутся страницы, где есть кошки или собаки

∪

Результатов больше, чем по каждому слову отдельно

Влияние логических операций на результаты поиска

Важно понимать, как логические операции влияют на количество результатов:

  • При использовании операции «И» (A & B) количество результатов уменьшается, так как документ должен содержать оба условия
  • При использовании операции «ИЛИ» (A | B) количество результатов увеличивается, так как документ может содержать любое из условий

Круги Эйлера-Венна

Для наглядного представления результатов поисковых запросов используются круги Эйлера-Венна:

  • Каждый круг представляет множество документов, удовлетворяющих определенному условию
  • Пересечение кругов (A & B) показывает документы, удовлетворяющие обоим условиям
  • Объединение кругов (A | B) показывает документы, удовлетворяющие хотя бы одному условию

Важные закономерности!

При решении задач на поисковые запросы помните:

  • Чем больше условий объединено операцией «И», тем меньше будет результатов
  • Чем больше условий объединено операцией «ИЛИ», тем больше будет результатов
  • Операция «НЕ» исключает указанные результаты из поиска
  • Круги Эйлера-Венна помогают визуально определить количество результатов

Главная формула для решения задач

A | B = A + B - (A & B)

Формула для связи операций "ИЛИ" (|) и "И" (&)

Почему эта формула работает?

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

A
B
A&B
  1. Когда мы складываем A + B:
    Мы учитываем все элементы из A и все элементы из B
    НО! При этом элементы из пересечения (A & B) учитываются ДВАЖДЫ
  2. Поэтому нужно вычесть пересечение один раз:
    A + B - (A & B)
    Это и даёт нам точное количество элементов в объединении (A | B)
Простой пример для понимания

Представим, что:

  • 🔵 В классе A учится 20 человек
  • 🔴 В классе B учится 15 человек
  • 🟣 5 человек ходят в оба класса

Сколько всего разных учеников? (A | B)

  1. Складываем: 20 + 15 = 35
  2. Но 5 человек посчитаны дважды!
  3. Вычитаем пересечение: 35 - 5 = 30

Ответ: 30 учеников

💡 Важно запомнить:
  • ✓ При сложении множеств их пересечение учитывается дважды
  • ✓ Чтобы получить правильный результат, нужно вычесть пересечение один раз
  • ✓ Эта формула работает для любых множеств
  • ✓ С помощью этой формулы можно найти как A | B, так и A & B

Практический пример

Условие задачи

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

Запрос Найдено страниц (в тысячах)
Швеция 3200
Финляндия 2300
Швеция & Финляндия 100

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

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

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

Швеция

3200

Финляндия

2300

Пересечение

100

Решение

Формула: A | B = A + B - (A & B)
Подставляем значения:
Швеция | Финляндия = 3200 + 2300 - 100
= 5500 - 100
= 5400
  1. Складываем количество страниц для каждого слова отдельно:
    3200 + 2300 = 5500 тыс. страниц
  2. Вычитаем количество страниц, где встречаются оба слова:
    5500 - 100 = 5400 тыс. страниц
  3. Объяснение:
    Мы вычитаем 100, потому что эти страницы были посчитаны дважды (они содержат и слово "Швеция", и слово "Финляндия")

Ответ: 5400 тысяч страниц