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



страница1/7
Дата08.05.2016
Размер0.5 Mb.
  1   2   3   4   5   6   7

,

17 (повышенный уровень, время – 2 мин)


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

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

  • таблицы истинности логических операций «И», «ИЛИ», «НЕ» (см. презентацию «Логика»)

  • если в выражении нет скобок, сначала выполняются все операции «НЕ», затем – «И», затем – «ИЛИ»

  • логическое произведение A∙B∙C∙… равно 1 (выражение истинно) только тогда, когда все сомножители равны 1 (а в остальных случаях равно 0)

  • логическая сумма A+B+C+… равна 0 (выражение ложно) только тогда, когда все слагаемые равны 0 (а в остальных случаях равна 1)

  • правила преобразования логических выражений (законы алгебры логики):

    Закон

    Для И

    Для ИЛИ

    двойного отрицания



    исключения третьего





    исключения констант

    A · 1 = A; A · 0 = 0

    A + 0 = A; A + 1 = 1

    повторения

    A · A = A

    A + A = A

    поглощения

    A · (A + B) = A

    A + A · B = A

    переместительный

    A · B = B · A

    A + B = B + A

    сочетательный

    A · (B · C) = (A · B) · C

    A + (B + C) = (A + B) + C

    распределительный

    A + B · C = (A + B) · (A + C)

    A · (B + C) = A · B + A · C

    де Моргана





  • ввод какого-то слова (скажем, кергуду) в запросе поисковой системы означает, что пользователь ищет Web-страницы, на которых встречается это слово

  • операция «И» всегда ограничивает поиск, то есть, в ответ на запрос кергуду И бамбарбия поисковый сервер выдаст меньше страниц, чем на запрос кергуду, потому что будет искать страницы, на которых есть оба этих слова одновременно

  • операция «ИЛИ» всегда расширяет поиск, то есть, в ответ на запрос
    кергуду ИЛИ бамбарбия поисковый сервер выдаст больше страниц, чем на запрос кергуду, потому что будет искать страницы, на которых есть хотя бы одно из этих слов (или оба одновременно)

  • если в запросе вводится фраза в кавычках, поисковый сервер ищет страницы, на которых есть в точности эта фраза, а не просто отдельные слова; взятие словосочетания в кавычки ограничивает поиск, то есть, в ответ на запрос "кергуду бамбарбия" поисковый сервер выдаст меньше страниц, чем на запрос кергуду бамбарбия, потому что будет искать только те страницы, на которых эти слова стоят одно за другим

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


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

Запрос

Количество страниц (тыс.)

США |Япония | Китай

450

Япония | Китай

260

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

50

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

США

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

Решение:

  1. заметим, что в силу тождества последний запрос в таблице равносилен такому:

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

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

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

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



Запрос

Количество страниц (тыс.)

А | B

450

B

260

А & B

50

А

?

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

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

  1. Ответ: 240
  1   2   3   4   5   6   7


База данных защищена авторским правом ©bezogr.ru 2016
обратиться к администрации

    Главная страница