Погода
Календарь
Март 2019
Пн Вт Ср Чт Пт Сб Вс
« Сен    
 123
45678910
11121314151617
18192021222324
25262728293031
Страницы сайта

Запросы для поисковых систем с использованием логических выраженй.

Что нужно знать:

  • таблицы истинности логических операций «И», «ИЛИ», «НЕ»
  • если в выражении нет скобок, сначала выполняются все операции «НЕ», затем – «И», затем  – «ИЛИ»
  • логическое произведение A∙B∙C∙… равно 1 (выражение истинно) только тогда, когда все сомножители равны 1 (а в остальных случаях равно 0)
  • логическая сумма A+B+C+… равна 0 (выражение ложно) только тогда, когда все слагаемые равны 0 (а в остальных случаях равна 1)
  • правила преобразования логических выражений (законы алгебры логики):
  • ввод какого-то слова (скажем, кергуду) в запросе поисковой системы означает, что пользователь ищет Web-страницы, на которых встречается это слово
  • операция «И» всегда ограничивает поиск, то есть, в ответ на запрос кергуду И бамбарбия поисковый сервер выдаст меньше страниц, чем на запрос кергуду, потому что будет искать страницы, на которых есть оба этих слова одновременно
  • операция «ИЛИ» всегда расширяет поиск, то есть, в ответ на запрос
    кергуду ИЛИ бамбарбия поисковый сервер выдаст больше страниц, чем на запрос кергуду, потому что будет искать страницы, на которых есть хотя бы одно из этих слов (или оба одновременно)
  • если в запросе вводится фраза в кавычках, поисковый сервер ищет страницы, на которых есть в точности эта фраза, а не просто отдельные слова; взятие словосочетания в кавычки ограничивает поиск, то есть, в ответ на запрос «кергуду бамбарбия» поисковый сервер выдаст меньше страниц, чем на запрос кергуду бамбарбия, потому что будет искать только те страницы, на которых эти слова стоят одно за другим

Круги Эйлера

Большинство задач, связанных с поисковыми запросами, проще решать, используя круги Эйлера.

Пример использования кругов Эйлера:

Известно количество сайтов, которых находит поисковый сервер по следующим запросам :

Ключевое
слово
Количество сайтов, для которых
данное слово является
ключевым
Глинка & Лист320
Бах & Лист280
(Глинка | Бах) & Лист430

Сколько сайтов будет найдено по запросу

Глинка & Бах & Лист

Решение заданий

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

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

США

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

Решение:

  • заметим, что в силу тождества A * B + A * C=A * (B + C)  последний запрос в таблице равносилен такому:

(США & Япония) | (США & Китай) <=> США & (Япония | Китай)

  • тогда вводя обозначение для областей

A = США,       B = Япония | Китай,

получаем стандартную задачу с двумя переменными:

  • имеем по формуле (см. решения ниже)

     NA = NA|B NB + NA&B = 450 – 260 + 50 = 240

         Ответ: 240

Задание 2: Некоторый сегмент сети Интернет состоит из 5000 сайтов. Поисковый сервер в автоматическом режиме составил таблицу ключевых слов для сайтов этого сегмента. Вот ее фрагмент:

Сколько сайтов будет найдено по запросу (принтеры | мониторы) & сканеры если по запросу принтеры | сканеры было найдено 600 сайтов, по запросу принтеры | мониторы – 900, а по запросу сканеры | мониторы – 750.

Решение:

1) для сокращения записи обозначим через C, П, М высказывания «ключевое слово на сайте – сканер» (соответственно принтер, монитор) и нарисуем эти области виде диаграммы (кругов Эйлера); интересующему нас запросу (П | M) & C соответствует объединение областей 4, 5 и 2 («зеленая зона» на рисунке)

2)количество сайтов, удовлетворяющих запросу в области i, будем обозначать через Ni
3) составляем уравнения, которые определяют запросы, заданные в условии:
сканер: N1 + N2 + N4 + N5 = 300
принтер: N2 + N3 + N5 + N6 = 400
принтер | сканеры: N1 + N2 + N3 + N4 + N5 + N6 = 600
Из первого и третьего получаем, что N3 + N6 = 600 — 300 = 300
Из второго и третьего получаем, что N1 + N4 = 600 — 400 = 200
Помимо этого:
принтеры | мониторы: N7 + N2 + N3 + N4 + N5 + N6 = 900
сканеры | мониторы : N1 + N2 + N4 + N5 + N6 + N7 = 750
монитор: N4 + N5 + N6 + N7 = 500
Преобразуем, учитывая выкладки выше:
N7 + N2 + N4 + N5 = 600
N2 + N5 + N6 + N7 = 550
N4 + N5 + N6 + N7 = 500
Из первого и второго:
N3 — N1 = 150
N3 + N4 = 350
N2 + N5 = 100
N3 + N6 = 300
принтеры | мониторы: N7 + N4 = 500
N4 + N5 + N6 + N7 = 500 следовательно, N5 + N6 = 0, следовательно N5 = N6 = 0.
N1 + N2 + N4 + N7 = 750
N7 + N2 + N4 = 600
следовательно, используя уравнения выше:
N1 = 150
N1 + N4 = 200, N4 = 50
N1 + N2 + N4 = 300, 150 + N2 + 50 = 300, N2 = 100.
Следовательно ответ N2 + N4 + N5 = 150.
Ответ: 150

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

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

                           

По запросу Динамо & Красс ни одной страницы найдено не было.

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

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

Решение:

Наша цель — N1 + N4 + N2 + N5 + N3.
Количество запросов в данной области будем обозначать Ni.
Тогда из таблицы находим, что:
N1 + N4 = 49 000
N5 + N3 = 2 000
N2 + N4 + N5 = 45 000
N5 = 1 700
N4 = 36 000
Из первого и последнего уравнения: N1 = 13 000.
Из второго и предпоследнего уравнения: N3 = 300
Таким образом:
N1 + (N4 + N2 + N5) + N3 = 13 000 + 45 000 + 300 = 58300.

Ответ: 58300.

Top