Задание 17 (презентация по типам задач к ЕГЭ)

ege17 (повышенный уровень, время – 2 мин)

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

Что нужно знать :

• Свойства логических операций

• Язык запросов

• Законы алгебры логики

Закон

Для И

двойного отрицания

Для ИЛИ

исключения третьего

исключения констант

повторения

A · 1 = A; A · 0 = 0

A · A = A

поглощения

A + 0 = A; A + 1 = 1

A + A = A

A · (A + B) = A

переместительный

A · B = B · A

сочетательный

A + A · B = A

A · (B · C) = (A · B) · C

распределительный

A + B = B + A

A + B · C = (A + B) · (A + C)

A + (B + C) = (A + B) + C

де Моргана

A · (B + C) = A · B + A · C

Пример I.

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

Запрос

Найдено страниц (в тыс)

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

3200

пирожное

8700

выпечка

7500

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

Решение

1. Выведем общую формулу.

2. Построим диаграмму Эйлера-Венна для двух переменных A и B :

A

В

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

A

В

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

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

N A|B = N A + N B - N A&B

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

N П = 8700

N В = 7500

N П&В = 3200

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

N П|B = N П + N B – N П&B =

13000

8700 + 7500 – 3200 =

Ответ: 13000

Пример II.

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

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

Запрос

Найдено страниц (в тыс)

США | Япония | Китай

450

Япония | Китай

260

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

100

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

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

Решение

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

США

Япония















Китай

США

Япония















Китай

2) Записываем уравнения с « номерами-переменными » по заданным в условии запросам.

При этом особое внимание обратим на сложный запрос в третьей строке таблицы.

США|Япония|Китай

Япония|Китай

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

США

 +  +  +  +  +  +  = 450

 +  +  +  +  +  = 260

 +  +  = 100

 +  +  +  = ?

3) Теперь главное – найти, как удобнее всего решить эту систему уравнений.

Очевидно, что из уравнений:

 +  +  +  +  +  +  = 450

и

 +  +  +  +  +  = 260

можно найти значение  ,

равное 450 – 260 = 190.

 +  +  = 100,

Тогда зная, что

сразу можно вычислить, что

 +  +  +  = 190 + 100 = 290.

Ответ: 290 .

Пример III.

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

Запрос

Найдено страниц (в тысячах)

Ростов & ( Орёл & Курск|Белгород )

370

Ростов & Белгород

204

Ростов & Орёл & Курск & Белгород

68

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

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

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

Решение

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

Запрос

Найдено страниц (в тыс)

Орёл & Курск|Белгород

370

Белгород

204

Орёл & Курск & Белгород

68

Орёл & Курск

?

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

3. по формуле для задачи с двумя областями

Запрос

A |Белгород

Страниц (в тыс.)

Белгород

370

204

A & Белгород

A

68

?

N A|B = N A + N B - N A&B

получаем

N A = N A|B - N B + N A&B

вычисляем:

370 – 204 + 68 = 234

Ответ: 234

Пример IV.

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

Запрос

Найдено страниц (в тыс)

Ухо

35

Подкова

25

Наковальня

Ухо | Подкова | Наковальня

40

70

Ухо & Наковальня

10

Ухо & Подкова

0

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

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

Решение

Ухо

35

Подкова

25

Наковальня

40

Ухо | Подкова | Наковальня

70

Ухо & Наковальня

10

Ухо & Подкова

0

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

Наковальня

4

5

3

2

1

Ухо

Подкова

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

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

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

Ответ: 20

Пример V.

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

Запрос

Найдено страниц (в тыс)

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

320

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

280

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

430

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

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

Решение

Рубин

Динамо

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

1

2

3

Запрос

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

Области

Страниц (в тыс)

1+2

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

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

320

2+3

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

280

1+2+3

430

2

?

Спартак

N 2 =(320 + 280) - 430= 170

Ответ: 170

= Паскаль & Си & Бейсик | Паскаль & Кобол добавим переменную согласно правилу поглощения В (3) : Паскаль & Си & Бейсик & Кобол = = Паскаль & Си & Бейсик & Паскаль & Кобол Выделяем одинаковые части выражений: Паскаль & Си & Бейсик Паскаль & Кобол и " width="640"

Пример VI.

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

Запрос

Кол-во страниц, тыс.

Паскаль & (Си & Бейсик | Кобол)

350

Паскаль & Кобол

Паскаль & Си & Бейсик & Кобол

187

48

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

Паскаль & Си & Бейсик ?

Решение

раскрываем скобки

В (1) : Паскаль & ( Си & Бейсик | Кобол ) =

= Паскаль & Си & Бейсик | Паскаль & Кобол

добавим переменную согласно правилу поглощения

В (3) : Паскаль & Си & Бейсик & Кобол =

= Паскаль & Си & Бейсик & Паскаль & Кобол

Выделяем одинаковые части выражений:

Паскаль & Си & Бейсик

Паскаль & Кобол

и

= =  + 139 = 302  = 163  +  = 163 + 48 = 211 = Ответ: 211 " width="640"

B

A

Введем обозначения:

A = Паскаль & Си & Бейсик







B = Паскаль & Кобол

Тогда исходные запросы будут иметь вид:

Паскаль & Си & Бейсик | Паскаль & Кобол

A + B

Паскаль & Кобол

B

 +  + 

Паскаль & Си & Бейсик & Паскаль & Кобол

Паскаль & Си & Бейсик

A * B

350

 + 

187

A



48

?

 + 

Составим уравнения:

 +  = 302

 = 139

 +  +  = 350

 +  = 187

 = 48

 + 48 +  = 350

48 +  = 187

=

=

=

 + 139 = 302  = 163  +  = 163 + 48 = 211

=

Ответ: 211

Демо – 2017

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

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

Запрос

Найдено страниц

Бабочка

22

Гусеница

40

Трактор

28

Бабочка & Гусеница

Трактор & Гусеница

20

16

Трактор & Бабочка

0

Гусеница

Бабочка

3

2

1

4

5

Трактор

Какое количество страниц (в сотнях тысяч) будет найдено по запросу Трактор | Бабочка | Гусеница ?

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

Гусеница

Бабочка

N 1 =22-N 2 =22-20=2

3

2

1

N 5 =28-N 4 =28-16=12

4

5

N 1 + N 2 +N 3 +N 4 +N 5 =

2+40+12=54

Трактор

Запрос

Найдено страниц

Бабочка

22

Гусеница

40

N 1 +N 2

Трактор

Бабочка & Гусеница

28

N 2 +N 3 +N 4

20

N 4 +N 5

Трактор & Гусеница

Трактор & Бабочка

16

N 2

0

Трактор | Бабочка | Гусеница

N 4

0

?

N 1 +N 2 +N 3 +N 4 +N 5

Ответ: 54