Запросы для поисковых систем

Задание в экзамене, которое посвящено поисковым системам, на самом деле проверяет ваше умение работать с множествами — именно поэтому оно относится к блоку «логика». В этом задании множеством является набор страниц, найденных по запросу, содержащему одно или несколько ключевых слов, связанных логическими операциями И, ИЛИ и НЕ. Процесс поиска происходит на основании поискового запроса в базах данных в соответствии с заданным условием отбора:

• если задано одно ключевое слово, то производится поиск страниц, в которых содержится данное ключевое слово, НЕЗАВИСИМО от остальных;

• если ключевое слово задано с операцией НЕ, то производится поиск страниц, в которых НЕ содержится данное поисковое слово;

• если ключевые слова связаны логической операцией И, то производится поиск страниц, в которой содержатся ВСЕ эти ключевые слова;

• если ключевые слова связаны логической операцией ИЛИ, то производится поиск страниц, в которых содержится ХОТЯ БЫ ОДНО ключевое слово.

Для визуализации и быстрого решения задания №17 удобнее всего пользоваться диаграммами Эйлера, поэтому сперва надо убедиться, что принцип работы с ними предельно понятен (подробнее см. раздел теории к уроку «Основы логики»).

Любое задание на запросы для поисковых систем решается по одному единственному алгоритму. Ниже приведен этот алгоритм с примерами решения типовых заданий.

Множества и диаграммы Эйлера

Множеством, например, можно назвать все автомобили марки Ferrari красного цвета (множество красных Ferrari). Множество состоит из элементов. Если в множестве элементов нет (т.е. количество элементов равно 0), то говорят, что это пустое множество. Любой объект можно охарактеризовать, как принадлежащий множеству (т.е. являющийся его элементом) или не принадлежащий (т.е. не являющийся его элементом). Например, желтая Ferrari не является элементом множества красных Ferrari, но является элементом множества всех Ferrari. Множества могут пересекаться. Это значит, что какие-то объекты будут входить только в одно множество, только в другое, ни в одно из них, или в оба сразу. Представим себе множество Ferrari с открытой крышей и наше множество красных Ferrari. Красные Ferrari с открытой крышей будут принадлежать обоим множествам сразу, а вот желтые с открытой крышей — только первому множеству. Желтые Ferrari без открытой крыши не будут принадлежать никакому множеству.

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

С помощью диаграмм Эйлера удобно представлять логические выражения. Например, конъюнкция — это пересечение множеств. Конъюнкция равна 1, когда обе логические переменные равны 1. Переходя на язык множеств, можно сказать, что запись A И B обозначает такие элементы, которые входят и в множество A, и в множество B. Для дизъюнкции и инверсии переход к множествам выполняется точно так же: A ИЛИ B обозначает такие элементы, которые принадлежат хотя бы одному из множеств A или B, а инверсия — элементы, не принадлежащие множеству A. Для базовых логических операций диаграммы Эйлера будут выглядеть следующим образом:

Алгоритм решения задания с помощью диаграмм Эйлера

1. Нарисовать диаграмму с учетом количества запросов;

2. Пронумеровать области на диаграмме;

3. Поставить область или сумму областей в соответствие с количеством страниц, заданных в условии, получить уравнения;

4. Составить систему из уравнений;

5. Выписать область или сумму областей, которую необходимо найти по запросу в вопросе;

6. Решить систему.

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

Пример задания.

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

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

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

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

Пример решения.

Нарисуем круги Эйлера и обозначим уникальные области.

Составим систему по имеющимся результатам запросов.

Рыбак ИЛИ Рыбка – это объединение обоих множеств – значит сумма всех трёх областей.

Рыбак – это сумма первой и второй области.

Рыбак И Рыбка – это пересечение обоих множеств – что соответствует второй области.

\(\left\{ \begin{matrix} \left( 1 \right) + \left( 2 \right) + \left( 3 \right) = 780 \\ \left( 1 \right) + \left( 2 \right) = 260 \\ \left( 2 \right) = 50 \\ \end{matrix} \right.\ \)

Надо найти количество результатов по запросу Рыбка, то есть сумму второй и третьей области.

\(\left\{ \begin{matrix} \left( 1 \right) + \left( 2 \right) + \left( 3 \right) = 780 \\ \left( 1 \right) + \left( 2 \right) = 260 \\ \left( 2 \right) = 50 \\ \left( 2 \right) + \left( 3 \right) = \ ? \\ \end{matrix} \right.\ \)

Решаем систему.

Из второго уравнения вычтем третье и получим: (1) = 260 – 50 = 210.

Теперь полученное значение для области (1) вычтем из первого уравнения и получим: (2) + (3) = 780 – 210 = 570.

Ответ: 570