Составление запросов для поисковых систем
Составление запросов для поисковых систем с использованием логических выражений.Коротун О.В., учитель информатики и ИКТ МОУ «СОШ №71» г. Саратова.B9 (повышенный уровень, время – 3 мин)
Содержание презентацииЧто нужно знатьРазбор задания 1Разбор задания 2Задачи для тренировки
Что нужно знать:таблицы истинности логических операций «И», «ИЛИ», «НЕ»если в выражении нет скобок, сначала выполняются все операции «НЕ», затем – «И», затем – «ИЛИ»логическое произведение A∙B∙C∙… равно 1 (выражение истинно) только тогда, когда все сомножители равны 1 (а в остальных случаях равно 0)логическая сумма A+B+C+… равна 0 (выражение ложно) только тогда, когда все слагаемые равны 0 (а в остальных случаях равна 1)правила преобразования логических выражений
ввод какого-то слова (скажем, кергуду) в запросе поисковой системы означает, что пользователь ищет Web-страницы, на которых встречается это слово операция «И» всегда ограничивает поиск, то есть, в ответ на запрос кергуду И бамбарбия поисковый сервер выдаст меньше страниц, чем на запрос кергуду, потому что будет искать страницы, на которых есть оба этих слова одновременно операция «ИЛИ» всегда расширяет поиск, то есть, в ответ на запрос кергуду ИЛИ бамбарбия поисковый сервер выдаст больше страниц, чем на запрос кергуду, потому что будет искать страницы, на которых есть хотя бы одно из этих слов (или оба одновременно) если в запросе вводится фраза в кавычках, поисковый сервер ищет страницы, на которых есть в точности эта фраза, а не просто отдельные слова; взятие словосочетания в кавычки ограничивает поиск, то есть, в ответ на запрос "кергуду бамбарбия" поисковый сервер выдаст меньше страниц, чем на запрос кергуду бамбарбия, потому что будет искать только те страницы, на которых эти слова стоят одно за другим
Пример 1: В таблице приведены запросы к поисковому серверу. Расположите номера запросов в порядке возрастания количества страниц, которые найдет поисковый сервер по каждому запросу. Для обозначения логической операции «ИЛИ» в запросе используется символ |, а для логической операции «И» – &.1) принтеры & сканеры & продажа2) принтеры & продажа3) принтеры | продажа4) принтеры | сканеры | продажа
Решение (вариант 1, рассуждение с использованием свойств операций «И» и «ИЛИ»):меньше всего результатов выдаст запрос с наибольшими ограничениями – первый (нужны одновременно принтеры, сканеры и продажа)на втором месте – второй запрос (одновременно принтеры и продажа)далее – третий запрос (принтеры или сканеры)четвертый запрос дает наибольшее количество результатов (принтеры или сканеры или продажа)таким образом, верный ответ – 1234 .
Возможные проблемы:нужно внимательно читать условие, так как в некоторых задачах требуется перечислить запросы в порядке убывания количества результатов, а в некоторых – в порядке возрастанияможно ошибиться в непривычных значках: «И» = &, «ИЛИ» = | (эти обозначения привычны для тех, кто программирует на языке Си)для сложных запросов не всегда удастся так просто расположить запросы по возрастанию (или убыванию) ограничений
Решение (вариант 2, через таблицы истинности):каждое из условий можно рассматривать как сложное высказываниеобозначим отдельные простые высказывания буквами: A: принтеры (на странице есть слово принтеры») B: сканеры C: продажа запишем все выражения-запросы через логические операции
здесь присутствуют три переменные, А, B и C (хотя второе и третье выражения от С не зависят!), поэтому для составления таблицы истинности нужно рассмотреть 8 = 23 всевозможных комбинаций этих логических значенийвыражение равно 1 (истинно) только при A=B=C=1, в остальных случаях – равно 0 (ложно)выражение равно 1 только при A=B=1, в остальных случаях – равно 0выражение равно 0 только при A=B=0, в остальных случаях – равно 1выражение равно 0 только при A=B=C=0, в остальных случаях – 1
запишем результаты пп. 5-8 в виде таблицы истинностиABC00000000010001010001101100111000011101001111001111111111
по таблице видим, что наименьшая «область действия» у первого выражения, поисковый сервер выдаст наименьшее число запросов область, где , включает в себя всю область, где и еще один вариант, поэтому «поисковик» выдаст больше запросов, чем для первого случая. (Каждая следующая область в полученном решении должна полностью включать предыдущую. Если это не так, тогда или вы ошиблись при построении таблицы истинности, или в условии есть ошибка.) аналогично делаем вывод, что область включает всю область и расширяет ее, а область – это расширение области таким образом, верный ответ – 1234 .
Возможные проблемы:решение достаточно громоздко, хотя позволяет с помощью простых операций решить задачу, не рискуя ошибиться при вычислениях «в уме» в сложных случаяхесли переменных более трех, таблица получается большая, хотя заполняется несложно
Решение (вариант 3, через диаграммы):запишем все ответы через логические операциипокажем области, определяемые этими выражениями, на диаграмме с тремя областямиABСABСABСABС
сравнивая диаграммы, находим последовательность областей в порядке увеличения: (1,2,3,4), причем каждая следующая область в этом ряду охватывает целиком предыдущую (как и предполагается в задании, это важно!)таким образом, верный ответ – 1234 .Возможные проблемы:получается громоздкий рисунок, если используется более трех переменных (более трех кругов)
Пример 2: Некоторый сегмент сети Интернет состоит из 1000 сайтов. Поисковый сервер в автоматическом режиме составил таблицу ключевых слов для сайтов этого сегмента. Вот ее фрагмент: Сколько сайтов будет найдено по запросу (принтер | сканер) & монитор если по запросу принтер | сканер было найдено 450 сайтов, по запросу принтер & монитор – 40, а по запросу сканер & монитор – 50.Ключевое словоКоличество сайтов, для которых данное слово является ключевымсканер200принтер250монитор450
Решение (вариант 1, рассуждение с использованием свойств операций «И» и «ИЛИ»):Обратим внимание на такой факт (справа указано количество сайтов по каждому запросу) сканер 200 принтер 250 принтер | сканер 450 Поскольку последнее число равно сумме двух предыдущих, можно сразу же придти к выводу, что в этом сегменте сети нет сайтов, на которых ключевыми словами являются одновременно принтер и сканер: принтер & сканер 0
С этого момента все просто: для того, чтобы определить, сколько сайтов удовлетворяют заданному условию, достаточно просто сложить числа, соответствующие запросам принтер & монитор и сканер & монитортаким образом, правильный ответ: 40 + 50 = 90.Возможные проблемы:обратите внимание, что в условии была лишняя информация: мы нигде не использовали количество сайтов в данном сегменте Интернета (1000) и количество сайтов с ключевым словом монитор (450)не всегда удается «раскрутить» задачу в уме, здесь это несложно благодаря «удачному» условию
Решение (вариант 2, таблицы истинности):Для сокращения записи обозначим через C, П, М соответственно высказывания сканер, принтер, монитор.Если рассматривать задачу с точки зрения математической логики, здесь есть три переменных, с помощью которых можно составить всего 8 запросов, выдающих различные результаты.
Составим таблицу истинности, в которую добавим левый столбец и последнюю строку, где будем записывать количество сайтов, удовлетворяющих условиям строки и столбца (см. рисунок справа); например, первая строка соответствует сайтам, на которых нет ни одного из заданных ключевых слов; такая схема непривычна, но она существенно упрощает делоСПМ?000?001?010?011?100?101?110?111всего200250450Сумма в последней строчке получается в результате сложения всех чисел из тех строк первого столбца, где в данном столбце стоят единицы. Например, сумма в столбце С – складывается из четырех чисел в последних четырех строчках первого столбца. Мы пока не знаем, сколько результатов возвращает каждый из восьми запросов отдельно, поэтому в первом столбце стоят знаки вопроса
Добавим в таблицу истинности остальные запросы, которые есть в условии, в том числе и тот, который нас интересует: П | С = принтер | сканер 450 П & М = принтер & монитор 40 C & М = сканер & монитор 50 (П | C) & М = (принтер | сканер) & монитор ? СПМП | СП &МC & М(П | C) & М?0000?0010?0101?0111?1001?10110110101111всего200250450450Проанализируем столбец П | С в этой таблице: его сумма (450) складывается из суммы столбцов С (200) и П (250) – выделены ярким зеленым цветом – плюс последние две строчки (голубой фон), то есть, 450 = 200 + 250 + X, откуда сразу получаем, что X = 0, то есть, последним двум строчкам (запросам) не удовлетворяет ни одного сайта.
теперь составим таблицы истинности для остальных запросов, отбросив заведомо «нулевые» варианты:СПМП | СП & МC & М(П | C) & М?0000000?0010000?0101000400111101?1001000501011011всего200250450450405090Из оставшихся шести строк таблицы запросы П & М и С & М затрагивают только по одной строчке, поэтому сразу можем вписать соответствующие числа в первый столбец; в последнем запросе, который нас интересует, присутствуют именно эти две строки, то есть, для получения нужно сложить 40 и 50.Таким образом, правильный ответ: 40 + 50 = 90.
Решение (вариант 3, через диаграммы): Для сокращения записи обозначим через C, П, М соответственно высказывания сканер, принтер, монитор и нарисуем эти области в виде диаграммы (кругов Эйлера); интересующему нас запросу (П | C) & M соответствует объединение областей 4, 5 и 6 («зеленая зона» на рисунке)СПМ(П | С) & M1234567
Количество сайтов, удовлетворяющих запросу в области i, будем обозначать через Ni Составляем уравнения, которые определяют запросы, заданные в условии: сканер N1 + N2 + N4 + N5 = 200 принтер N2 + N3 + N5 + N6 = 250 принтер | сканер N1 + N2 + N4 + N5 + N3 + N6 = 450из первого и третьего уравнений сразу следует200 + N3 + N6 = 450 N3 + N6 = 250далее из второго уравнения N2 + N5 + 250 = 250 N2 + N5 = 0поскольку количество сайтов не может быть отрицательной величиной, N2 = N5 = 0Посмотрим, что еще мы знаем (учитываем, что N5 = 0): принтер & монитор N5 + N6 = 40 N6 = 40 сканер & монитор N4 + N5 = 50 N4 = 50СПМ(П | С) & M1234567
Окончательный результат: (принтер | сканер) & монитор N4 + N5 + N6 = N4 + N6 = 40 + 50 = 90 Таким образом, правильный ответ 90.Возможные проблемы:внимательнее с индексами переменными, очень легко по невнимательности написать N5 вместо N6 и получить совершенно другой результатэтот метод ярко демонстрирует, что в общем случае мы получаем систему уравнения с семью неизвестными (или даже с восемью, если задействована еще и область вне всех кругов); решать такую систему вручную достаточно сложно, поэтому на экзамене всегда будет какое-то условие, сильно упрощающее дело, ищите его
Задачи для тренировкиВ таблице приведены запросы и количество страниц, которые нашел поисковый сервер по этим запросам в некотором сегменте Интернета:ЗапросКоличество страниц (тыс.)пирожное & выпечка3200пирожное8700выпечка7500Сколько страниц (в тысячах) будет найдено по запросу пирожное | выпечкаПВ123Составляем уравнения, которые определяют запросы, заданные в условии:пирожное & выпечка N2 = 3200пирожное N1 + N2 = 8700выпечка N2 + N3 = 7500Подставляя значение N2 из первого уравнения в остальные, получаемN1 = 8700 - N2 = 8700 – 3200 = 5500N3 = 7500 - N2 = 7500 – 3200 = 4300Количество сайтов по запросу пирожное | выпечка равно N1 + N2 + N3 = 5500 + 3200 + 4300 = 13000Таким образом, ответ – 13000.
В таблице приведены запросы к поисковому серверу. Расположите обозначения запросов в порядке возрастания количества страниц, которые найдет поисковый сервер по каждому запросу. А) физкультураБ) физкультура & подтягивания & отжиманияВ) физкультура & подтягиванияГ) физкультура | фитнесс БВАГ
В таблице приведены запросы к поисковому серверу. Расположите обозначения запросов в порядке возрастания количества страниц, которые найдет поисковый сервер по каждому запросу. А) волейбол | баскетбол | подачаБ) волейбол | баскетбол | подача | блок В) волейбол | баскетбол Г) волейбол & баскетбол & подачаГВАБ
В таблице приведены запросы к поисковому серверу. Расположите обозначения запросов в порядке возрастания количества страниц, которые найдет поисковый сервер по каждому запросу. A) чемпионы | (бег & плавание)Б) чемпионы & плаваниеВ) чемпионы | бег | плаваниеГ) чемпионы & Европа & бег & плаваниеГБАВ
В таблице приведены запросы к поисковому серверу. Расположите обозначения запросов в порядке возрастания количества страниц, которые найдет поисковый сервер по каждому запросу. А) музыка | классика | Моцарт | серенадаБ) музыка | классикаВ) музыка | классика | МоцартГ) музыка & классика & МоцартГБВА
В таблице приведены запросы к поисковому серверу. Расположите обозначения запросов в порядке возрастания количества страниц, которые найдет поисковый сервер по каждому запросу. А) реферат | математика | ГауссБ) реферат | математика | Гаусс | методВ) реферат | математикаГ) реферат & математика & ГауссГВАБ
В таблице приведены запросы к поисковому серверу. Расположите обозначения запросов в порядке возрастания количества страниц, которые найдет поисковый сервер по каждому запросу. Ответ запишите в виде последовательности соответствующих букв.a) Америка | путешественники | Колумбb) Америка | путешественники | Колумб | открытиеАмерика | КолумбАмерика & путешественники & Колумбdcab
В таблице приведены запросы к поисковому серверу. Расположите обозначения запросов в порядке убывания количества страниц, которые найдет поисковый сервер по каждому запросу. Ответ запишите в виде последовательности соответствующих букв.а) Информатика & уроки & Excelb) Информатика | уроки | Excel | диаграммас) Информатика | уроки | Exceld) Информатика | Excelbcda
В таблице приведены запросы к поисковому серверу, условно обозначенные буквами от А до Г. Расположите запросы в порядке возрастания количества страниц, которые найдет поисковый сервер по каждому запросу. Ответ запишите в виде последовательности соответствующих букв.А) Гренландия & Климат & Флора & ФаунаБ) Гренландия & ФлораВ) (Гренландия & Флора) | ФаунаГ) Гренландия & Флора & ФаунаАГБВ
В таблице приведены запросы к поисковому серверу. Расположите обозначения запросов в порядке убывания количества страниц, которые найдет поисковый сервер по каждому запросу. а) спорт | футболb) спорт | футбол | Петербург | Зенитс) спорт | футбол | Петербургd) спорт & футбол & Петербург & Зенитbcad
Каким условием нужно воспользоваться для поиска в сети Интернет информации о цветах, растущих на острове Тайвань или Хонсю1) цветы & (Тайвань | Хонсю)2) цветы & Тайвань & Хонсю3) цветы | Тайвань | Хонсю4) цветы & (остров | Тайвань | Хонсю)1
Некоторый сегмент сети Интернет состоит из 1000 сайтов. Поисковый сервер в автоматическом режиме составил таблицу ключевых слов для сайтов этого сегмента. Вот ее фрагмент:Ключевое словоКоличество сайтов, для которых данное слово является ключевымсомики250меченосцы200гуппи500Сколько сайтов будет найдено по запросу сомики | меченосцы | гуппиесли по запросу сомики & гуппи было найдено 0 сайтов, по запросу сомики & меченосцы – 20, а по запросу меченосцы & гуппи – 10.920
Некоторый сегмент сети Интернет состоит из 1000 сайтов. Поисковый сервер в автоматическом режиме составил таблицу ключевых слов для сайтов этого сегмента. Вот ее фрагмент:Сколько сайтов будет найдено по запросу (сомики & меченосцы) | гуппиесли по запросу сомики | гуппи было найдено 750 сайтов, по запросу сомики & меченосцы – 100, а по запросу меченосцы & гуппи – 0.Ключевое словоКоличество сайтов, для которых данное слово является ключевымсомики250меченосцы200гуппи500600
Некоторый сегмент сети Интернет состоит из 1000 сайтов. Поисковый сервер в автоматическом режиме составил таблицу ключевых слов для сайтов этого сегмента. Вот ее фрагмент:Сколько сайтов будет найдено по запросу принтер | сканер | мониторесли по запросу принтер | сканер было найдено 450 сайтов, по запросу принтер & монитор – 40, а по запросу сканер & монитор – 50.Ключевое словоКоличество сайтов, для которых данное слово является ключевымсканер200принтер250монитор450810
В таблице приведены запросы к поисковому серверу, условно обозначенные буквами от А до Г. Расположите запросы в порядке возрастания количества страниц, которые найдет поисковый сервер по каждому запросу. Ответ запишите в виде последовательности соответствующих букв.А) (огурцы & помидоры) & (прополка | поливка)Б) огурцы | помидорыВ) огурцыГ) огурцы & помидорыАГВБ
В таблице приведены запросы к поисковому серверу, условно обозначенные буквами от А до Г. Расположите запросы в порядке возрастания количества страниц, которые найдет поисковый сервер по каждому запросу. Ответ запишите в виде последовательности соответствующих букв.А) экзамен | тестированиеБ) (физика | химия) & (экзамен | тестирование)В) физика & химия & экзамен & тестированиеГ) физика | химия | экзамен | тестированиеВБАГ
В таблице приведены запросы к поисковому серверу, условно обозначенные буквами от А до Г. Расположите запросы в порядке возрастания количества страниц, которые найдет поисковый сервер по каждому запросу. Ответ запишите в виде последовательности соответствующих букв.А) сомики | меченосцы | содержаниеБ) сомики & содержаниеВ) сомики & меченосцы & разведение & содержаниеГ) (сомики | меченосцы) & содержаниеВБГА
В таблице приведены запросы к поисковому серверу. Расположите номера запросов в порядке возрастания количества страниц, которые найдет поисковый сервер по каждому запросу. Для обозначения логической операции «ИЛИ» в запросе используется символ |, а для логической операции «И» – &.1) канарейки | щеглы | содержание2) канарейки & содержание3) канарейки & щеглы & содержание4) разведение & содержание & канарейки & щеглы4321
В таблице приведены запросы к поисковому серверу. Расположите номера запросов в порядке убывания количества страниц, которые найдет поисковый сервер по каждому запросу. Для обозначения логической операции «ИЛИ» в запросе используется символ |, а для логической операции «И» – &.1) барокко | (классицизм & ампир)2) барокко | классицизм3) барокко | ампир | классицизм 4) классицизм & ампир3214
В таблице приведены запросы к поисковому серверу. Расположите номера запросов в порядке убывания количества страниц, которые найдет поисковый сервер по каждому запросу. Для обозначения логической операции «ИЛИ» в запросе используется символ |, а для логической операции «И» – &.1) барокко | (классицизм & ампир)2) барокко | классицизм3) (классицизм & ампир) | (барокко & модерн)4) барокко | ампир | классицизм4213
В таблице приведены запросы к поисковому серверу. Расположите номера запросов в порядке убывания количества страниц, которые найдет поисковый сервер по каждому запросу. Для обозначения логической операции «ИЛИ» в запросе используется символ |, а для логической операции «И» – &.1) зайцы & кролики2) зайцы & (кролики | лисицы)3) зайцы & кролики & лисицы4) кролики | лисицы4213
В таблице приведены запросы к поисковому серверу. Расположите номера запросов в порядке возрастания количества страниц, которые найдет поисковый сервер по каждому запросу. Для обозначения логической операции «ИЛИ» в запросе используется символ |, а для логической операции «И» – &.1) кролики | лисицы 2) (зайцы & кролики) | (лисицы & волки)3) зайцы & кролики & лисицы & волки4) зайцы & кролики3421
В таблице приведены запросы к поисковому серверу. Расположите номера запросов в порядке возрастания количества страниц, которые найдет поисковый сервер по каждому запросу. Для обозначения логической операции «ИЛИ» в запросе используется символ |, а для логической операции «И» – &.1) шкафы | столы | стулья2) шкафы | (стулья & шкафы)3) шкафы & столы4) шкафы | стулья3241
В таблице приведены запросы к поисковому серверу. Расположите номера запросов в порядке убывания количества страниц, которые найдет поисковый сервер по каждому запросу. Для обозначения логической операции «ИЛИ» в запросе используется символ |, а для логической операции «И» – &.1) яблоки | сливы2) сливы | (сливы & груши)3) яблоки | груши | сливы4) (яблоки | груши) & сливы3124
В таблице приведены запросы и количество страниц, которые нашел поисковый сервер по этим запросам в некотором сегменте Интернета:ЗапросКоличество страницфрегат | эсминец3000фрегат2000эсминец2500Сколько страниц (в тысячах) будет найдено по запросу фрегат & эсминец1500
В таблице приведены запросы и количество страниц, которые нашел поисковый сервер по этим запросам в некотором сегменте Интернета:ЗапросКоличество страницфрегат & эсминец500фрегат2000эсминец2500Сколько страниц (в тысячах) будет найдено по запросу фрегат | эсминец4000
В таблице приведены запросы и количество страниц, которые нашел поисковый сервер по этим запросам в некотором сегменте Интернета:ЗапросКоличество страницфрегат & эсминец500фрегат | эсминец4500эсминец2500Сколько страниц (в тысячах) будет найдено по запросу фрегат2500
В таблице приведены запросы и количество страниц, которые нашел поисковый сервер по этим запросам в некотором сегменте Интернета:ЗапросКоличество страниц (тыс.)крейсер | линкор7000крейсер4800линкор4500Сколько страниц (в тысячах) будет найдено по запросу крейсер & линкор2300
В таблице приведены запросы и количество страниц, которые нашел поисковый сервер по этим запросам в некотором сегменте Интернета:ЗапросКоличество страниц (тыс.)торты | пироги12000торты & пироги6500пироги7700Сколько страниц (в тысячах) будет найдено по запросу торты10800
В таблице приведены запросы и количество страниц, которые нашел поисковый сервер по этим запросам в некотором сегменте Интернета:Сколько страниц (в тысячах) будет найдено по запросу выпечка ЗапросКоличество страниц (тыс.)пирожное | выпечка14200пирожное9700пирожное & выпечка51009600
http://kpolyakov.narod.ru/В презентации использованы материалы с сайта Продолжить тестирование можно по адресуhttp://somit.ru/jurnal/B9.htm