Как работает формула включений-исключений при решении задач на поиск информации в интернете?

Формула включений-исключений позволяет решать задачи о количестве страниц, найденных по запросу в интернете, где для обозначения логической операции «ИЛИ» используется символ «|», а для логической операции «И» — символ «&». www.bolshoyvopros.ru inf-ege.sdamgia.ru

Формула для двух областей выглядит так: N A | B = N A + N B − N A & B, где N X — количество страниц, которые выдаёт поисковая система по запросу X. inf-ege.sdamgia.ru

Формула для трёх областей имеет вид: N A | B | C = N A + N B + N C − N A & B − N A & C − N B & C + N A & B & C. inf-ege.sdamgia.ru

Пример решения задачи: informatics-in-school.ru

Есть таблица с запросами и количеством найденных по ним страниц: informatics-in-school.ru

• «Соболь | Куница» — 6400 страниц; informatics-in-school.ru
• «Соболь & Куница» — 550 страниц; informatics-in-school.ru
• «Соболь» — 4300 страниц. informatics-in-school.ru Нужно найти, сколько страниц будет найдено по запросу «Куница». informatics-in-school.ru

Решение: informatics-in-school.ru

1. Обозначим множества как A и B. informatics-in-school.ru
2. Применим формулу включений-исключений для двух множеств: (A | B) = (A) + (B) – (A & B). informatics-in-school.ru
3. Пусть A — запрос «Соболь», B — «Куница». informatics-in-school.ru
4. Подставим в формулу известные значения: 6400 = 4300 + (B) – 550. informatics-in-school.ru
5. Решим уравнение: 6400 – 4300 + 550 = B, B = 2650. informatics-in-school.ru

Считается, что все запросы выполнялись практически одновременно, так что набор страниц, содержащих все искомые слова, не изменялся за время выполнения запросов. www.bolshoyvopros.ru informatics-in-school.ru