Урок 19
§12. Множества и логика
Содержание урока
Количество элементов во множестве
Сложные запросы в поисковых системах
Сложные запросы в поисковых системах
Для решения задач, в которых используются множества, например множества страниц, полученных от поисковой системы в ответ на какой-то запрос, удобно применять диаграммы Эйлера-Венна.
Задача 1. Известно количество страниц, которые находит поисковый сервер по следующим запросам (здесь символ «&» обозначает операцию И, а «|» — операцию ИЛИ):
собаки | кошки 770
кошки 550
собаки & кошки 100
Сколько страниц будет найдено по запросу собаки?
Введём два множества: А — множество страниц, где есть слово «собаки», В — множество страниц со словом «кошки». По формуле, которая получена в предыдущем пункте, получаем:
NA = NA|B - NB + NA&B = 770 - 550 + 100 = 320.
Известно количество страниц, которые находит поисковый сервер по следующим запросам:
незабудка 220
лилия & незабудка 100
лилия | незабудка 450
Сколько страниц найдёт этот сервер по запросу лилия?
Известно количество страниц, которые находит поисковый сервер по следующим запросам:
енот 200
кашалот 300
кашалот | енот 450
Сколько страниц найдет этот сервер по запросу
кашалот & енот?
Известно количество страниц, которые находит поисковый сервер по следующим запросам:
Италия 320
Франция 450
Франция & Италия 80
Сколько страниц найдёт этот сервер по запросу
Франция | Италия?
Рассмотрим теперь более сложную задачу с тремя областями.
Задача 2. Известно количество страниц, которые находит поисковый сервер по следующим запросам:
собаки & лемуры 320
кошки & лемуры 280
(кошки | собаки) & лемуры 430
Сколько страниц будет найдено по запросу
кошки & собаки & лемуры?
Заметим, что во всех запросах есть часть & лемуры. Это означает, что область поиска во всех случаях ограничена страницами, на которых встречается слово «лемуры».
Обозначим буквами С, К и Л области (группы страниц), содержащие ключевые слова «собаки», «кошки» и «лемуры» соответственно. Нас интересует только область, выделенная фоном на рис. 2.41, а.
Рис. 2.41
Эта область образована в результате пересечения двух областей (рис. 2.41, б):
А = собаки & лемуры
В = кошки & лемуры
Поэтому задачу можно свести к задаче с двумя областями.
Известно количество страниц, которые находит поисковый сервер по следующим запросам:
А 320
В 280
А | В 430
Сколько страниц будет выдано по запросу А & В?
Используя формулу включений и исключений, полученную в предыдущем пункте, находим:
NА&B = NА + NB - NA|B = 320 + 280 - 430 = 170.
Известно количество страниц, которые находит поисковый сервер по следующим запросам:
берёза & сирень 220
берёза & сирень & арбуз 30
сирень & (берёза | арбуз) 340
Сколько страниц найдёт этот сервер по запросу
арбуз & сирень?
Известно количество страниц, которые находит поисковый сервер по следующим запросам:
яхта & диван 270
диван & пирог 350
яхта & диван & пирог 80
Сколько страниц найдёт этот сервер по запросу
(пирог | яхта) & диван?
Задачу с тремя областями не всегда удаётся свести к более простой задаче с двумя областями. Серьёзным упрощением может стать то, что какие-то два множества не имеют общих элементов.
Если два множества не имеют общих элементов, что можно сказать об их изображении на диаграмме Эйлера-Венна?
Задача 3. Известно количество страниц, которые находит поисковый сервер по следующим запросам:
собаки 200
кошки 250
лемуры 450
кошки | собаки 450
кошки & лемуры 40
собаки & лемуры 50
Сколько страниц найдёт этот сервер по запросу
(кошки | собаки) & лемуры?
Здесь часть & лемуры встречается не во всех запросах, поэтому свести задачу к задаче с двумя областями не удаётся. Используя те же обозначения, что и в задаче 2, построим диаграмму с тремя переменными и выделим интересующую область, которая соответствует запросу (кошки I собаки) & лемуры.
На рисунке 2.42 эта область выделена фоном.
Рис. 2.42
В общем виде задача с тремя областями очень сложна. Попробуем найти какое-нибудь упрощающее условие. Например, выделим три условия:
собаки 200
кошки 250
кошки | собаки 450
Это означает, что область кошки | собаки равна сумме областей кошки и собаки, т. е. эти области не пересекаются! Таким образом, в нашем случае диаграмма выглядит так (рис. 2.43).
Рис. 2.43
Размеры областей 1 (собаки & лемуры) и 2 (кошки & лемуры) нам известны, они составляют соответственно 40 и 50 страниц, поэтому по запросу
(кошки | собаки) & лемуры
поисковый сервер найдёт 40 + 50 = 90 страниц.
Известно количество страниц, которые находит поисковый сервер по следующим запросам:
солнце 230
крабы 220
лето 100
крабы | солнце 450
крабы & лето 60
солнце & лето 20
Сколько страниц найдёт этот сервер по запросу
крабы | солнце | лето?
Следующая страница 
Выводы
Cкачать материалы урока
