Поиск

Полнотекстовый поиск:
Где искать:
везде
только в названии
только в тексте
Выводить:
описание
слова в тексте
только заголовок

Рекомендуем ознакомиться

'Документ'
Можно ввести в интерьер комнаты желтый и фиолетовый цвета, поскольку они повышают интеллектуальную активность. Для этого бывает достаточно какой-либо ...полностью>>
'Конкурс'
Министерство здравоохранения Сахалинской области сообщает, что победителями конкурса на замещение вакантных должностей государственной гражданской слу...полностью>>
'Документ'
Цель программы формирования УУД :обеспечить  регулирование  различных аспектов освоения метапредметных умений, т.е. способов деятельности, применимых ...полностью>>
'Документ'
Причитающуюся к возврату сумму НДФЛ прошу перечислить на мой банковский счет по следующим реквизитам: л/с в р/с , к/с ,БИК , ИНН ....полностью>>

Главная > Документ

Сохрани ссылку в одной из сетей:
Информация о документе
Дата добавления:
Размер:
Доступные форматы для скачивания:

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

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

    де Моргана

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

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

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

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

Еще пример задания:

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

Запрос

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

пирожное & выпечка

3200

пирожное

8700

выпечка

7500

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

пирожное | выпечка

Решение (вариант 1, рассуждения по диаграмме):

  1. построим диаграмму Эйлера-Венна, обозначив области «пирожное» (через П) и «выпечка» (В) :

  2. количество сайтов, удовлетворяющих запросу в области i, будем обозначать через Ni

  3. несложно сообразить, что число сайтов в интересующей нас области равно

N1 + N2 + N3 = (N1 + N2) + (N3 + N2) – N2

  1. поскольку нам известно, что по условию

N1 + N2 = 8700

N3 + N2 = 7500

N2 = 3200

сразу получаем

N1 + N2 + N3 = 8700 + 7500 - 3200 = 13000

  1. таким образом, ответ – 13000.

Решение (вариант 2, общая формула):

  1. сначала выведем формулу, о которой идет речь; построим диаграмму Эйлера-Венна для двух переменных A и B:

  2. обозначим через NA, NB, NA&B и NA|B число страниц, которые выдает поисковый сервер соответственно по запросам A, B, A & B и
    A | B

  3. понятно, что если области A и B не пересекаются, справедлива формула NA|B=NA+NB

  4. если области пересекаются, в сумму NA+NB область пересечения NA&B входит дважды, поэтому в общем случае

NA|B = NA + NB - NA&B

  1. в данной задаче

NП = 8700, NВ = 7500, NП&В = 3200

  1. тогда находим число сайтов в интересующей нас области по формуле

NП|B = NП + NB NП&B = 8700 + 7500 – 3200 = 13000

  1. таким образом, ответ – 13000.

Решение (вариант 3, решение системы уравнений):

  1. нарисуем области «пирожное» (обозначим ее через П) и «выпечка» (В) в виде диаграммы (кругов Эйлера); при их пересечении образовались три подобласти, обозначенные числами 1, 2 и 3;

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

пирожное & выпечка N2 = 3200

пирожное N1 + N2 = 8700

выпечка N2 + N3 = 7500

  1. подставляя значение N2 из первого уравнения в остальные, получаем

N1 = 8700 - N2 = 8700 – 3200 = 5500

N3 = 7500 - N2 = 7500 – 3200 = 4300

  1. количество сайтов по запросу пирожное | выпечка равно

N1 + N2 + N3 = 5500 + 3200 + 4300 = 13000

  1. таким образом, ответ – 13000.

Еще пример задания:

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

Запрос

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

Динамо & Рубин

320

Спартак & Рубин

280

(Динамо | Спартак) & Рубин

430

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

Рубин & Динамо & Спартак

Решение (вариант 1, круги Эйлера, полная диаграмма):

  1. в этой задаче неполные данные, так как они не позволяют определить размеры всех областей; однако их хватает для того, чтобы ответить на поставленный вопрос

  2. обозначим области, которые соответствуют каждому запросу

    Запрос

    Области

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

    Динамо & Рубин

    1+2

    320

    Спартак & Рубин

    2+3

    280

    (Динамо | Спартак) & Рубин

    1+2+3

    430

    Рубин & Динамо & Спартак

    2

    ?

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

N2 = (320 + 280) – 430 = 170

  1. таким образом, ответ – 170.

Решение (вариант 2, круги Эйлера, неполная диаграмма):

  1. заметим, что в этой задаче все запросы (в том числе и тот, результат которого нужно найти, имеют вид

X & Рубин

  1. поэтому часть «& Рубин» в каждом из запросов можно просто отбросить, тогда останется только две области:

Запрос

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

Динамо-1

320

Спартак-1

280

Динамо-1 | Спартак-1

430

здесь добавление «-1» в имени области обозначает «пересечение с областью Рубин»

  1. требуется найти размер области «Динамо-1 & Спартак-1»

  2. для диаграммы с двумя областями можно использовать общую формулу

NA|B = NA + NB - NA&B

  1. из которой следует

NA&B = NA + NB - NA|B

  1. в данном случае получаем

NA&B = (320 + 280) – 430 = 170

  1. таким образом, ответ – 170.

Ещё пример задания:

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

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 .

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

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

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



Похожие документы:

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

    Документ
    ... B10 (повышенный уровень, время – 5 мин) Тема: Составление запросов для поисковых систем с использованием логических выражений. Что нужно знать: таблицы истинности ...
  2. Тема : Составление запросов для поисковых систем с использованием логических выражений (1)

    Документ
    ... уровень, время – 5 мин) Тема: Составление запросов для поисковых систем с использованием логических выражений. Что нужно знать: смысл логических операций «И», «ИЛИ», порядок ...
  3. Тема : Вычисление информационного объема сообщения (3)

    Документ
    ... . B10 (повышенный уровень, время – 5 мин) Тема: Составление запросов для поисковых систем с использованием логических выражений. Что нужно знать: таблицы истинности ...
  4. Решение. Рассуждения, приводящие к правильному ответу

    Решение
    ... отводится 4 мин. Тема задания: «Составление запросов для поисковых систем с использованием логических выражений» В таблице приведены запросы к поисковому серверу. Расположите номера запросов в порядке возрастания ...
  5. Межшкольные консультационные пункты по биологии для учащихся 11-х классов

    Документ
    ... A3) Составление таблицы истинности логической функции ... истинности логического выражения. Решение логических задач. ... запросы для поисковых систем. (B15) Логические ... С) 20 Использование математических приёмов ... для учащихся 11-х классов №п\п Название темы ...

Другие похожие документы..