Студопедия

Главная страница Случайная страница

Разделы сайта

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






  • Сканер 200






    США

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

    Решение:

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

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

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

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

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

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

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

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

    4) Ответ: 240

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

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

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

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

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

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

    Решение:

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

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

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

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

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

    NA|B = NA + NB - NA& B

    получаем

    NA = NA|B - NB + NA& B

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

    9) Ответ: 234.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    .

    4) ответ – 20.

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

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

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

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

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

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

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

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

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

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

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

    N1 + N2 = 8700

    N3 + N2 = 7500

    N2 = 3200

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

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

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

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

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

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

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

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

    Решение (вариант 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.

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

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

    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.

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

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

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

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

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

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

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

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

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

    сканер 200




    Заказать индивидуалку в Волгограде

    © 2023 :: MyLektsii.ru :: Мои Лекции
    Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.
    Копирование текстов разрешено только с указанием индексируемой ссылки на источник.