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

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



НазваниеТема : Составление запросов для поисковых систем с использованием логических выражений
страница1/5
Дата конвертации24.06.2012
Размер352.55 Kb.
ТипЗакон
  1   2   3   4   5

© К. Поляков, 2009-2012

B12 (повышенный уровень, время – 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

    де Моргана



    gif" name="object5" align=absmiddle width=95 height=18>

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

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

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

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

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


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

1) принтеры & сканеры & продажа

2) принтеры & сканеры

3) принтеры | сканеры

4) принтеры | сканеры | продажа

Решение (вариант 1, рассуждение с использованием свойств операций «И» и «ИЛИ»):

  1. меньше всего результатов выдаст запрос с наибольшими ограничениями – первый (нужны одновременно принтеры, сканеры и продажа)

  2. на втором месте – второй запрос (одновременно принтеры и сканеры)

  3. далее – третий запрос (принтеры или сканеры)

  4. четвертый запрос дает наибольшее количество результатов (принтеры или сканеры или продажа)

  5. таким образом, верный ответ – 1234 .

Возможные проблемы:

    • нужно внимательно читать условие, так как в некоторых задачах требуется перечислить запросы в порядке убывания количества результатов, а в некоторых – в порядке возрастания

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

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

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

Решение (вариант 2, через таблицы истинности):

  1. каждое из условий можно рассматривать как сложное высказывание

  2. обозначим отдельные простые высказывания буквами:

A: принтеры (на странице есть слово «принтеры»)

B: сканеры

C: продажа

  1. запишем все выражения-запросы через логические операции

, , ,

  1. здесь присутствуют три переменные, А, B и C (хотя второе и третье выражения от С не зависят!), поэтому для составления таблицы истинности нужно рассмотреть 8 = 232333 всевозможных комбинаций этих логических значений

  2. выражение равно 1 (истинно) только при , в остальных случаях – равно 0 (ложно)

  3. выражение равно 1 только при , в остальных случаях – равно 0

  4. выражение равно 0 только при , в остальных случаях – равно 1

  5. выражение равно 0 только при , в остальных случаях –  1

  6. запишем результаты пп. 5-8 в виде таблицы истинности

    A

    B

    C









    0

    0

    0

    0

    0

    0

    0

    0

    0

    1

    0

    0

    0

    1

    0

    1

    0

    0

    0

    1

    1

    0

    1

    1

    0

    0

    1

    1

    1

    0

    0

    0

    0

    1

    1

    1

    0

    1

    0

    0

    1

    1

    1

    1

    0

    0

    1

    1

    1

    1

    1

    1

    1

    1

    1

    1

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

  8. область, где , включает в себя1 всю область, где и еще один вариант, поэтому «поисковик» выдаст больше запросов, чем для первого случая

  9. аналогично делаем вывод, что область включает всю область и расширяет ее, а область – это расширение области

  10. таким образом, верный ответ – 1234 .

Возможные проблемы:

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

    • если переменных более трех, таблица получается большая, хотя заполняется несложно

Решение (вариант 3, через диаграммы):

  1. запишем все ответы через логические операции

, , ,

  1. покажем области, определяемые этими выражениями, на диаграмме с тремя областями



  1. сравнивая диаграммы, находим последовательность областей в порядке увеличения: (1,2,3,4), причем каждая следующая область в этом ряду охватывает целиком предыдущую (как и предполагается в задании, это важно!)

  2. таким образом, верный ответ – 1234 .

^ Возможные проблемы:

    • получается громоздкий рисунок, если используется более трех переменных (более трех кругов)
  1   2   3   4   5




Похожие:

Тема : Составление запросов для поисковых систем с использованием логических выражений iconУказания по статистической оценке эффективности поисковых машин
Цель работы состоит в сравнении эффективности поиска заданных студенту поисковых машин не по одному запросу, а по статистике различных...
Тема : Составление запросов для поисковых систем с использованием логических выражений iconПостроение таблиц истинности логических выражений Приоритет логических операций
При вычислении значения логического выражения (формулы) логические операции вычисляются в определенном порядке, согласно их приоритету:...
Тема : Составление запросов для поисковых систем с использованием логических выражений iconСоставление выражений по схемам

Тема : Составление запросов для поисковых систем с использованием логических выражений iconТема : Преобразование логических выражений
Автор, к своему стыду, до сих пор иногда путает  и . Поэтому на его уроках операция «НЕ» обозначается чертой сверху, «И» – знаком...
Тема : Составление запросов для поисковых систем с использованием логических выражений iconТема : Преобразование логических выражений
Автор, к своему стыду, до сих пор иногда путает  и . Поэтому на его уроках операция «НЕ» обозначается чертой сверху, «И» – знаком...
Тема : Составление запросов для поисковых систем с использованием логических выражений iconТема : Преобразование логических выражений
Автор, к своему стыду, до сих пор иногда путает  и . Поэтому на его уроках операция «НЕ» обозначается чертой сверху, «И» – знаком...
Тема : Составление запросов для поисковых систем с использованием логических выражений iconТема : Построение таблиц истинности логических выражений
Автор, к своему стыду, до сих пор иногда путает  и . Поэтому на его уроках операция «НЕ» обозначается чертой сверху, «И» – знаком...
Тема : Составление запросов для поисковых систем с использованием логических выражений iconТема : Построение таблиц истинности логических выражений
Автор, к своему стыду, до сих пор иногда путает  и . Поэтому на его уроках операция «НЕ» обозначается чертой сверху, «И» – знаком...
Тема : Составление запросов для поисковых систем с использованием логических выражений iconТема : Построение таблиц истинности логических выражений
Автор, к своему стыду, до сих пор иногда путает  и . Поэтому на его уроках операция «НЕ» обозначается чертой сверху, «И» – знаком...
Тема : Составление запросов для поисковых систем с использованием логических выражений iconТема : Преобразование логических выражений. Формулы де Моргана
Автор, к своему стыду, до сих пор иногда путает  и . Поэтому на его уроках операция «НЕ» обозначается чертой сверху, «И» – знаком...
Разместите кнопку на своём сайте:
Документы


База данных защищена авторским правом ©podelise.ru 2000-2014
При копировании материала обязательно указание активной ссылки открытой для индексации.
обратиться к администрации
Документы

Разработка сайта — Веб студия Адаманов