СОСТАВЛЕНИЕ ЗАПРОСОВ ДЛЯ ПОИСКОВЫХ СИСТЕМ С ИСПОЛЬЗОВАНИЕМ ЛОГИЧЕСКИХ ВЫРАЖЕНИЙ. Коротун О. В., учитель информатики и ИКТ МОУ « СОШ 71» г. Саратова.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3. Составим таблицу истинности, в которую добавим левый столбец и последнюю строку, где будем записывать количество сайтов, удовлетворяющих условиям строки и столбца ( см. рисунок справа ); например, первая строка соответствует сайтам, на которых нет ни одного из заданных ключевых слов ; такая схема непривычна, но она существенно упрощает дело СПМ ? 000 ? 001 ? 010 ? 011 ? 100 ? 101 ? 110 ? 111 всего Сумма в последней строчке получается в результате сложения всех чисел из тех строк первого столбца, где в данном столбце стоят единицы. Например, сумма в столбце С – складывается из четырех чисел в последних четырех строчках первого столбца. Мы пока не знаем, сколько результатов возвращает каждый из восьми запросов отдельно, поэтому в первом столбце стоят знаки вопроса

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В презентации использованы материалы с сайта