Всего на сайте:
119 тыс. 927 статей

Главная | Информатика

Сканер 200  Просмотрен 148

США

Считается, что все запросы выполнялись практически одновременно, так что набор страниц, содержащих все искомые слова, не изменялся за время выполнения запросов.

Решение:

1) заметим, что в силу тождества последний запрос в таблице равносилен такому:

(США & Япония) | (США & Китай) Û США & (Япония | Китай)

2) тогда вводя обозначение для областей

A = США, B = Япония | Китай,

получаем стандартную задачу с двумя переменными:

Запрос Количество страниц (тыс.)
А | B  
B  
А & B  
А ?

3) имеем по формуле (см. решения ниже)

NA = NA|B - NB + NA&B = 450 – 260 + 50 = 240

4) Ответ: 240

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

Р-06. В таблице приведены запросы и количество найденных по ним страниц некоторого сегмента сети Интернет:

Запрос Количество страниц (тыс.)
Ростов & (Орёл & Курск | Белгород)  
Ростов & Белгород  
Ростов & Орёл & Курск & Белгород  

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

Ростов & Орёл & Курск

Считается, что все запросы выполнялись практически одновременно, так что набор страниц, содержащих все искомые слова, не изменялся за время выполнения запросов.

Решение:

1) заметим, что во всех четырёх запросах есть «сомножитель» «Ростов &», поэтому эта задача равносильна такой:

Запрос Количество страниц (тыс.)
Орёл & Курск | Белгород  
Белгород  
Орёл & Курск & Белгород  
Орёл & Курск ?

2) теперь обозначим A = Орёл & Курск и получим задачу с двумя областями:

Запрос Количество страниц (тыс.)
A | Белгород  
Белгород  
A & Белгород  
A ?

3) по формуле для задачи с двумя областями (см. задачи, разобранные ниже)

NA|B = NA + NB - NA&B

получаем

NA = NA|B - NB + NA&B

4) вычисляем: 370 – 204 + 68 = 234.

5) Ответ: 234.

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

Р-05. В таблице приведены запросы и количество найденных по ним страниц некоторого сегмента сети Интернет:

Запрос Количество страниц (тыс.)
Ухо  
Подкова  
Наковальня  
Ухо | Подкова | Наковальня  
Ухо & Наковальня  
Ухо & Подкова  

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

Подкова & Наковальня

Считается, что все запросы выполнялись практически одновременно, так что набор страниц, содержащих все искомые слова, не изменялся за время выполнения запросов.

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

1) построим диаграмму Эйлера-Венна

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

3) здесь 5 областей, причём известны следующие данные:

4) нас интересует область 4. Находим ответ прямой подстановкой:

5) таким образом, ответ – 20.

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

1) пп. 1-2 такие же, как в варианте 1

2) заметим, что в прямую сумму величин областей Ухо, Подкова и Наковальня дважды входят области 2 и 4, поэтому для вычисления достаточно вычесть из суммы Ухо+Подкова+Наковальня размер их объединения (Ухо | Подкова | Наковальня) и величину области 2 (Ухо & Наковальня).

3) тогда сразу получаем

.

4) ответ – 20.

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

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

Запрос Количество страниц (тыс.)
пирожное & выпечка  
пирожное  
выпечка  

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

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

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

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

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

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

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

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

N1 + N2 = 8700

N3 + N2 = 7500

N2 = 3200

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

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

5) таким образом, ответ – 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

5) в данной задаче

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

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

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

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

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

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

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

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

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

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

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

N1 = 8700 - N2 = 8700 – 3200 = 5500

N3 = 7500 - N2 = 7500 – 3200 = 4300

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

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

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

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

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

Запрос Количество страниц (тыс.)
Динамо & Рубин  
Спартак & Рубин  
(Динамо | Спартак) & Рубин  

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

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

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

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

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

Запрос Области Количество страниц (тыс.)
Динамо & Рубин 1+2  
Спартак & Рубин 2+3  
(Динамо | Спартак) & Рубин 1+2+3  
Рубин & Динамо & Спартак ?

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

N2 = (320 + 280) – 430 = 170

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

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

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

X & Рубин

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

Запрос Количество страниц (тыс.)
Динамо-1  
Спартак-1  
Динамо-1 | Спартак-1  

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

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

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

NA|B = NA + NB - NA&B

5) из которой следует

NA&B = NA + NB - NA|B

6) в данном случае получаем

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

B: сканеры

C: продажа

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

, , ,

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

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

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

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

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

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

A B C
      
      
      
      
      
      
      
      

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

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

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

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

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

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

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

, , ,

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

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

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

Возможные проблемы: · получается громоздкий рисунок, если используется более трех переменных (более трех кругов)

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

Р-01. Некоторый сегмент сети Интернет состоит из 1000 сайтов. Поисковый сервер в автоматическом режиме составил таблицу ключевых слов для сайтов этого сегмента. Вот ее фрагмент:

Ключевое слово Количество сайтов, для которых данное слово является ключевым
сканер  
принтер  
монитор  

Сколько сайтов будет найдено по запросу

(принтер | сканер) & монитор

если по запросу принтер | сканер было найдено 450 сайтов, по запросу принтер & монитор – 40, а по запросу сканер & монитор – 50.

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

1) обратим внимание на такой факт[2] (справа указано количество сайтов по каждому запросу)

сканер 200

Предыдущая статья:Атлантида. Уроки исчезнувшего континента; Примечания Следующая статья:Принтер 250
page speed (0.0223 sec, direct)