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

Слайд 1

Составление запросов для поисковых систем с использованием логических выражений. Коротун О.В., учитель информатики и ИКТ МОУ «СОШ №71» г. Саратова.

Слайд 2

Содержание презентации Что нужно знать Разбор задания 1 Разбор задания 2 Задачи для тренировки

Слайд 3

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

Слайд 5

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

Слайд 6

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

Слайд 7

Решение (вариант 1, рассуждение с использованием свойств операций «И» и «ИЛИ»): меньше всего результатов выдаст запрос с наибольшими ограничениями – первый (нужны одновременно принтеры, сканеры и продажа) на втором месте – второй запрос (одновременно принтеры и продажа) далее – третий запрос (принтеры или сканеры) четвертый запрос дает наибольшее количество результатов (принтеры или сканеры или продажа) таким образом, верный ответ – 1234 .

Слайд 8

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

Слайд 9

Решение (вариант 2, через таблицы истинности): каждое из условий можно рассматривать как сложное высказывание обозначим отдельные простые высказывания буквами: A : принтеры (на странице есть слово принтеры») B : сканеры C : продажа запишем все выражения-запросы через логические операции

Слайд 10

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

Слайд 11

запишем результаты пп . 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

Слайд 12

по таблице видим, что наименьшая «область действия» у первого выражения, поисковый сервер выдаст наименьшее число запросов область , где , включает в себя всю область, где и еще один вариант, поэтому «поисковик» выдаст больше запросов, чем для первого случая . ( Каждая следующая область в полученном решении должна полностью включать предыдущую. Если это не так, тогда или вы ошиблись при построении таблицы истинности, или в условии есть ошибка .) аналогично делаем вывод, что область включает всю область и расширяет ее, а область – это расширение области таким образом, верный ответ – 1234 .

Слайд 13

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

Слайд 14

Решение (вариант 3, через диаграммы): запишем все ответы через логические операции покажем области, определяемые этими выражениями, на диаграмме с тремя областями A B С A B С A B С A B С

Слайд 15

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

Слайд 16

Пример 2: Некоторый сегмент сети Интернет состоит из 1000 сайтов. Поисковый сервер в автоматическом режиме составил таблицу ключевых слов для сайтов этого сегмента. Вот ее фрагмент: Сколько сайтов будет найдено по запросу (принтер | сканер) & монитор если по запросу принтер | сканер было найдено 450 сайтов, по запросу принтер & монитор – 40, а по запросу сканер & монитор – 50. Ключевое слово Количество сайтов, для которых данное слово является ключевым сканер 200 принтер 250 монитор 450

Слайд 17

Решение (вариант 1, рассуждение с использованием свойств операций «И» и «ИЛИ»): Обратим внимание на такой факт (справа указано количество сайтов по каждому запросу) сканер 200 принтер 250 принтер | сканер 450 Поскольку последнее число равно сумме двух предыдущих, можно сразу же придти к выводу, что в этом сегменте сети нет сайтов, на которых ключевыми словами являются одновременно принтер и сканер: принтер & сканер 0

Слайд 18

С этого момента все просто: для того, чтобы определить, сколько сайтов удовлетворяют заданному условию, достаточно просто сложить числа, соответствующие запросам принтер & монитор и сканер & монитор таким образом, правильный ответ: 40 + 50 = 90 . Возможные проблемы : обратите внимание, что в условии была лишняя информация: мы нигде не использовали количество сайтов в данном сегменте Интернета (1000) и количество сайтов с ключевым словом монитор (450) не всегда удается «раскрутить» задачу в уме, здесь это несложно благодаря «удачному» условию

Слайд 19

Решение (вариант 2, таблицы истинности): Для сокращения записи обозначим через C , П, М соответственно высказывания сканер, принтер , монитор. Если рассматривать задачу с точки зрения математической логики, здесь есть три переменных, с помощью которых можно составить всего 8 запросов, выдающих различные результаты.

Слайд 20

Составим таблицу истинности, в которую добавим левый столбец и последнюю строку, где будем записывать количество сайтов, удовлетворяющих условиям строки и столбца (см. рисунок справа); например, первая строка соответствует сайтам, на которых нет ни одного из заданных ключевых слов; такая схема непривычна, но она существенно упрощает дело С П М ? 0 0 0 ? 0 0 1 ? 0 1 0 ? 0 1 1 ? 1 0 0 ? 1 0 1 ? 1 1 0 ? 1 1 1 всего 200 250 450 Сумма в последней строчке получается в результате сложения всех чисел из тех строк первого столбца, где в данном столбце стоят единицы. Например, сумма в столбце С – складывается из четырех чисел в последних четырех строчках первого столбца. Мы пока не знаем, сколько результатов возвращает каждый из восьми запросов отдельно, поэтому в первом столбце стоят знаки вопроса

Слайд 21

Добавим в таблицу истинности остальные запросы, которые есть в условии, в том числе и тот, который нас интересует: П | С = принтер | сканер 450 П & М = принтер & монитор 40 C & М = сканер & монитор 50 (П | C ) & М = (принтер | сканер) & монитор ? С П М П | С П & М C & М ( П | C ) & М ? 0 0 0 0 ? 0 0 1 0 ? 0 1 0 1 ? 0 1 1 1 ? 1 0 0 1 ? 1 0 1 1 0 1 1 0 1 0 1 1 1 1 всего 200 250 450 450 Проанализируем столбец П | С в этой таблице: его сумма (450) складывается из суммы столбцов С (200) и П (250) – выделены ярким зеленым цветом – плюс последние две строчки ( голубой фон), то есть, 450 = 200 + 250 + X, откуда сразу получаем, что X = 0, то есть, последним двум строчкам (запросам) не удовлетворяет ни одного сайта.

Слайд 22

теперь составим таблицы истинности для остальных запросов, отбросив заведомо «нулевые» варианты: С П М П | С П & М C & М (П | C ) & М ? 0 0 0 0 0 0 0 ? 0 0 1 0 0 0 0 ? 0 1 0 1 0 0 0 40 0 1 1 1 1 0 1 ? 1 0 0 1 0 0 0 50 1 0 1 1 0 1 1 всего 200 250 450 450 40 50 90 Из оставшихся шести строк таблицы запросы П & М и С & М затрагивают только по одной строчке, поэтому сразу можем вписать соответствующие числа в первый столбец; в последнем запросе, который нас интересует, присутствуют именно эти две строки, то есть, для получения нужно сложить 40 и 50. Таким образом, правильный ответ: 40 + 50 = 90 .

Слайд 23

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

Слайд 24

Количество сайтов, удовлетворяющих запросу в области i , будем обозначать через N i Составляем уравнения, которые определяют запросы, заданные в условии: сканер N 1 + N 2 + N 4 + N 5 = 200 принтер N 2 + N 3 + N 5 + N 6 = 250 принтер | сканер N 1 + N 2 + N 4 + N 5 + N 3 + N 6 = 450 из первого и третьего уравнений сразу следует 200 + N 3 + N 6 = 450  N 3 + N 6 = 250 далее из второго уравнения N 2 + N 5 + 250 = 250  N 2 + N 5 = 0 поскольку количество сайтов не может быть отрицательной величиной, N 2 = N 5 = 0 Посмотрим, что еще мы знаем (учитываем, что N 5 = 0 ): принтер & монитор N 5 + N 6 = 40  N 6 = 40 сканер & монитор N 4 + N 5 = 50  N 4 = 50 С П М (П | С) & M 1 2 3 4 5 6 7

Слайд 25

Окончательный результат: (принтер | сканер) & монитор N 4 + N 5 + N 6 = N 4 + N 6 = 40 + 50 = 90 Таким образом, правильный ответ 90 . Возможные проблемы : внимательнее с индексами переменными, очень легко по невнимательности написать N 5 вместо N 6 и получить совершенно другой результат этот метод ярко демонстрирует, что в общем случае мы получаем систему уравнения с семью неизвестными (или даже с восемью, если задействована еще и область вне всех кругов); решать такую систему вручную достаточно сложно, поэтому на экзамене всегда будет какое-то условие, сильно упрощающее дело, ищите его

Слайд 26

Задачи для тренировки В таблице приведены запросы и количество страниц, которые нашел поисковый сервер по этим запросам в некотором сегменте Интернета: Запрос Количество страниц (тыс.) пирожное & выпечка 3200 пирожное 8700 выпечка 7500 Сколько страниц (в тысячах) будет найдено по запросу пирожное | выпечка П В 1 2 3 Составляем уравнения, которые определяют запросы, заданные в условии: пирожное & выпечка N 2 = 3200 пирожное N 1 + N 2 = 8700 выпечка N 2 + N 3 = 7500 Подставляя значение N 2 из первого уравнения в остальные, получаем N 1 = 8700 - N 2 = 8700 – 3200 = 5500 N 3 = 7500 - N 2 = 7500 – 3200 = 4300 К оличество сайтов по запросу пирожное | выпечка равно N 1 + N 2 + N 3 = 5500 + 3200 + 4300 = 13000 Т аким образом, ответ – 13000 .

Слайд 27

В таблице приведены запросы к поисковому серверу. Расположите обозначения запросов в порядке возрастания количества страниц, которые найдет поисковый сервер по каждому запросу. А) физкультура Б) физкультура & подтягивания & отжимания В) физкультура & подтягивания Г) физкультура | фитнесс БВАГ

Слайд 28

В таблице приведены запросы к поисковому серверу. Расположите обозначения запросов в порядке возрастания количества страниц, которые найдет поисковый сервер по каждому запросу. А) волейбол | баскетбол | подача Б) волейбол | баскетбол | подача | блок В) волейбол | баскетбол Г) волейбол & баскетбол & подача ГВАБ

Слайд 29

В таблице приведены запросы к поисковому серверу. Расположите обозначения запросов в порядке возрастания количества страниц, которые найдет поисковый сервер по каждому запросу. A) чемпионы | (бег & плавание) Б) чемпионы & плавание В) чемпионы | бег | плавание Г) чемпионы & Европа & бег & плавание ГБАВ

Слайд 30

В таблице приведены запросы к поисковому серверу. Расположите обозначения запросов в порядке возрастания количества страниц, которые найдет поисковый сервер по каждому запросу. А) музыка | классика | Моцарт | серенада Б) музыка | классика В) музыка | классика | Моцарт Г) музыка & классика & Моцарт ГБВА

Слайд 31

В таблице приведены запросы к поисковому серверу. Расположите обозначения запросов в порядке возрастания количества страниц, которые найдет поисковый сервер по каждому запросу. А) реферат | математика | Гаусс Б) реферат | математика | Гаусс | метод В) реферат | математика Г) реферат & математика & Гаусс ГВАБ

Слайд 32

В таблице приведены запросы к поисковому серверу. Расположите обозначения запросов в порядке возрастания количества страниц, которые найдет поисковый сервер по каждому запросу. Ответ запишите в виде последовательности соответствующих букв. a ) Америка | путешественники | Колумб b ) Америка | путешественники | Колумб | открытие Америка | Колумб Америка & путешественники & Колумб dcab

Слайд 33

В таблице приведены запросы к поисковому серверу. Расположите обозначения запросов в порядке убывания количества страниц, которые найдет поисковый сервер по каждому запросу. Ответ запишите в виде последовательности соответствующих букв. а) Информатика & уроки & Excel b ) Информатика | уроки | Excel | диаграмма с) Информатика | уроки | Excel d) Информатика | Excel bcda

Слайд 34

В таблице приведены запросы к поисковому серверу, условно обозначенные буквами от А до Г. Расположите запросы в порядке возрастания количества страниц, которые найдет поисковый сервер по каждому запросу. Ответ запишите в виде последовательности соответствующих букв. А) Гренландия & Климат & Флора & Фауна Б) Гренландия & Флора В) (Гренландия & Флора) | Фауна Г) Гренландия & Флора & Фауна АГБВ

Слайд 35

В таблице приведены запросы к поисковому серверу. Расположите обозначения запросов в порядке убывания количества страниц, которые найдет поисковый сервер по каждому запросу. а) спорт | футбол b ) спорт | футбол | Петербург | Зенит с) спорт | футбол | Петербург d ) спорт & футбол & Петербург & Зенит bcad

Слайд 36

Каким условием нужно воспользоваться для поиска в сети Интернет информации о цветах, растущих на острове Тайвань или Хонсю 1) цветы & (Тайвань | Хонсю) 2) цветы & Тайвань & Хонсю 3) цветы | Тайвань | Хонсю 4) цветы & (остров | Тайвань | Хонсю) 1

Слайд 37

Некоторый сегмент сети Интернет состоит из 1000 сайтов. Поисковый сервер в автоматическом режиме составил таблицу ключевых слов для сайтов этого сегмента. Вот ее фрагмент: Ключевое слово Количество сайтов, для которых данное слово является ключевым сомики 250 меченосцы 200 гуппи 500 Сколько сайтов будет найдено по запросу сомики | меченосцы | гуппи если по запросу сомики & гуппи было найдено 0 сайтов , по запросу сомики & меченосцы – 20, а по запросу меченосцы & гуппи – 10. 920

Слайд 38

Некоторый сегмент сети Интернет состоит из 1000 сайтов. Поисковый сервер в автоматическом режиме составил таблицу ключевых слов для сайтов этого сегмента. Вот ее фрагмент: Сколько сайтов будет найдено по запросу ( сомики & меченосцы) | гуппи если по запросу сомики | гуппи было найдено 750 сайтов , по запросу сомики & меченосцы – 100, а по запросу меченосцы & гуппи – 0. Ключевое слово Количество сайтов, для которых данное слово является ключевым сомики 250 меченосцы 200 гуппи 500 600

Слайд 39

Некоторый сегмент сети Интернет состоит из 1000 сайтов. Поисковый сервер в автоматическом режиме составил таблицу ключевых слов для сайтов этого сегмента. Вот ее фрагмент: Сколько сайтов будет найдено по запросу принтер | сканер | монитор если по запросу принтер | сканер было найдено 450 сайтов, по запросу принтер & монитор – 40, а по запросу сканер & монитор – 50. Ключевое слово Количество сайтов, для которых данное слово является ключевым сканер 200 принтер 250 монитор 450 810

Слайд 40

В таблице приведены запросы к поисковому серверу, условно обозначенные буквами от А до Г. Расположите запросы в порядке возрастания количества страниц, которые найдет поисковый сервер по каждому запросу. Ответ запишите в виде последовательности соответствующих букв. А) (огурцы & помидоры) & (прополка | поливка) Б) огурцы | помидоры В) огурцы Г) огурцы & помидоры АГВБ

Слайд 41

В таблице приведены запросы к поисковому серверу, условно обозначенные буквами от А до Г. Расположите запросы в порядке возрастания количества страниц, которые найдет поисковый сервер по каждому запросу. Ответ запишите в виде последовательности соответствующих букв. А) экзамен | тестирование Б) (физика | химия) & (экзамен | тестирование) В) физика & химия & экзамен & тестирование Г) физика | химия | экзамен | тестирование ВБАГ

Слайд 42

В таблице приведены запросы к поисковому серверу, условно обозначенные буквами от А до Г. Расположите запросы в порядке возрастания количества страниц, которые найдет поисковый сервер по каждому запросу. Ответ запишите в виде последовательности соответствующих букв. А) сомики | меченосцы | содержание Б) сомики & содержание В) сомики & меченосцы & разведение & содержание Г) ( сомики | меченосцы) & содержание ВБГА

Слайд 43

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

Слайд 44

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

Слайд 45

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

Слайд 46

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

Слайд 47

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

Слайд 48

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

Слайд 49

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

Слайд 50

В таблице приведены запросы и количество страниц, которые нашел поисковый сервер по этим запросам в некотором сегменте Интернета: Запрос Количество страниц фрегат | эсмине ц 3000 фрегат 2000 эсминец 2500 Сколько страниц (в тысячах) будет найдено по запросу фрегат & эсминец 1500

Слайд 51

В таблице приведены запросы и количество страниц, которые нашел поисковый сервер по этим запросам в некотором сегменте Интернета: Запрос Количество страниц фрегат & эсмине ц 500 фрегат 2000 эсминец 2500 Сколько страниц (в тысячах) будет найдено по запросу фрегат | эсминец 4000

Слайд 52

В таблице приведены запросы и количество страниц, которые нашел поисковый сервер по этим запросам в некотором сегменте Интернета: Запрос Количество страниц фрегат & эсмине ц 500 фрегат | эсмине ц 4500 эсминец 2500 Сколько страниц (в тысячах) будет найдено по запросу фрегат 2500

Слайд 53

В таблице приведены запросы и количество страниц, которые нашел поисковый сервер по этим запросам в некотором сегменте Интернета: Запрос Количество страниц (тыс.) крейсер | линкор 7000 крейсер 4800 линкор 4500 Сколько страниц (в тысячах) будет найдено по запросу крейсер & линкор 2300

Слайд 54

В таблице приведены запросы и количество страниц, которые нашел поисковый сервер по этим запросам в некотором сегменте Интернета: Запрос Количество страниц (тыс.) торты | пироги 12000 торты & пироги 6500 пироги 7700 Сколько страниц (в тысячах) будет найдено по запросу торты 10800

Слайд 55

В таблице приведены запросы и количество страниц, которые нашел поисковый сервер по этим запросам в некотором сегменте Интернета: Сколько страниц (в тысячах) будет найдено по запросу выпечка Запрос Количество страниц (тыс.) пирожное | выпечка 14200 пирожное 9700 пирожное & выпечка 5100 9600

Слайд 56

http://kpolyakov.narod.ru/ В презентации использованы материалы с сайта