Курсовая работа (т): Основы теории множеств и ее реализация в языке программирования Паскаль

Сколько студентов выбрали по крайней мере одну дополнительную дисциплину? Сколько из них предпочли только дисциплину «Информационные технологии в рекламе»?

Решение.

Пусть A - множество студентов, выбравших дисциплину «Информационные технологии моделирования интерьера»,- 21 «Информационные технологии в рекламе»,- «Информационные технологии моделирования ландшафта».

Для составления математической модели задачи удобно использовать диаграммы Эйлера - Венна.

Из диаграммы (Рисунок 9) видно, что на теоретико- множественном языке формулировка первого вопроса - «Чему равна мощность множества A ∪ B ∪ C?», а второго - «Какова мощность множества B \ [(A ∩ B) ∪ (B ∩ C)]?».

На основании формулы включений и исключений, имеем:

∪ B ∪ C = A + B + C − A ∩ B − B ∩ C − A ∩ C + A ∩ B ∩ C = 30 + 35 + 20 − 15 − 10 - 7 + 3 = 56.

Получаем:

\ = [(A∩ B) ∪(B ∩C] B − (A∩ B)∪(B ∩C) = B − [ A ∩ B + B ∩ C − A ∩ B ∩ C ] = 35 - (15 + 7 - 3) = 16.

Ответ:

студентов выбрали по крайней мере одну дополни- тельную дисциплину и 16 - только дисциплину «Информационные технологии в рекламе».

Задача №5

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

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

кроманьонец & (мезозой | неандерталец)

Решение (способ 1, круги Эйлера):

)        обозначим области «мезозой», «кроманьонец» и «неандерталец» буквами М, К и Н; пронумеруем подобласти, получившиеся в результате пересечений кругов (см. рисунок справа)

)        через N_i обозначим количество сайтов в области с номером i

)        нас интересует результат запроса

кроманьонец & (мезозой | неандерталец)

то есть N₂ + N₅ + N₆ (зеленая область на рисунке)

)        из первых двух запросов следует, что

N₁ + N₂ + N₄ + N₅ = 50          (мезозой)

N₂ + N₃ + N₅ + N₆ = 60          (кроманьонец)

)        складывая левые и правые части уравнений, получаем

(1)     N₁ + 2·N₂ + N₃ + N₄ + 2·N₅ + N₆ = 110

)        в то же время из запроса 4 получаем

(2)    N₁ + N₂ + N₃ + N₄ + N₅ + N₆ = 80             (мезозой | кроманьонец)

)        вычитая из уравнения (1) уравнение (2), отдельно левые и правые части, получаем

N₂ + N₅ = 30                 (мезозой & кроманьонец)

вспомним, что наша цель - определить N₂ + N₅ + N₆, поэтому остается найти N₆

)        из запросов 1 и 3 следует, что

N₁ + N₂ + N₄ + N₅ = 50          (мезозой)

N₄ + N₅ + N₆ + N₇ = 70          (неандерталец)

)        складывая левые и правые части уравнений, получаем

(3)    N₁ + N₂ + 2·N₄ + 2·N₅ + N₆ + N₇ = 120

)        в то же время из запроса 5 получаем

(4)     N₁ + N₂ + N₄ + N₅ + N₆ + N₇ = 100         (мезозой | неандерталец)

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

(5)     N₄ + N₅ = 20                 (мезозой & неандерталец)

)        теперь проанализируем запрос 6:

неандерталец & (мезозой | кроманьонец)

(6)    N₄ + N₅ + N₆ = 20

)        вычитая из уравнения (6) уравнение (5) получаем N₆ = 0, поэтому

N₂ + N₅ + N₆ = N₂ + N₅ = 30

)        таким образом, ответ - 30.

Решение (способ 2, М.С. Коротков, г. Челябинск, Лицей № 102):

)        пп. 1-3 такие же, как в первом способе;

)        из запросов 1 и 6 следует, что

(1)     N₄ + N₅ + N₆ + N₇ = 70          (неандерталец)

(2)     N₄ + N₅ + N₆ = 20                            неандерталец & (мезозой | кроманьонец)

3)      вычитая (2) из (1), сразу получаем, что N₇ = 50

)        из запросов 5 и 4 следует, что

(3)     N₁ + N₂ + N₄ + N₅ + N₆ + N₇ = 100  (мезозой | неандерталец)

(4)     N₁ + N₂ + N₃ + N₄ + N₅ + N₆ = 80    (мезозой | кроманьонец)

5)      вычитая (4) из (3), сразу получаем, что N₇ - N₃ = 20

)        в п. 3 мы уже определили, что N₇ = 50, поэтому 50 - N₃ = 20, откуда N₃ = 30

)        из запроса 2 получаем

N₂ + N₃ + N₅ + N₆ = 60 (кроманьонец)

поэтому размер интересующей нас области равен

N₂ + N₅ + N₆ = 60 - N₃ = 60 - 30 = 30

)        таким образом, ответ - 30.

Решение (способ 3, круги Эйлера, И.Б. Курбанова):

)        обозначим: М - мезозой, К - кроманьонец, Н - неандерталец.

)        нас интересует результат запроса (см. диаграмму Эйлера)

K & (M | Н)

)        т.к. по условию М = 50, К = 60, а объединение этих множеств М | К = 80, можно сделать вывод, что область пересечения

M & K = 50 + 60 - 80 = 30;

4)      т.к. по условию М = 50, Н = 70, а объединение этих множеств М | Н = 100, можно сделать вывод, что область пересечения

M & Н = 50 + 70 - 100 = 20;

5)      заметим, что M & Н = 20 и Н & (М | К) = 20, следовательно множества Н и К не пересекаются (К & Н = 0);

)        перерисуем диаграмму Эйлера так, чтобы множества К и Н не пересекались (см. рисунок справа); из новой схемы видно, что

К & (М | Н) = (К & М) | (К & Н) = К & М = 30

7)      ответ: 30 [22]

Задача №6

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

B: сканеры

C: продажа

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

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

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

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

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

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

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

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

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

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

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

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

, , ,

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

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

)        таким образом, верный ответ - 1234 . [22]

Задача № 7

Даны множества U={1, 2, …, 20}, A={1, 3, 8, 15}, B={8, 15, 3, 2}.

а) Найти их объединение.

Решение:

Запишем сначала все элементы множества А, а затем - те элементы множества В, которые не содержатся во множестве А:B={1, 3, 8, 15, 2}.

б) Найти их пересечение.

Решение:

Берем каждый элемент множества А и определяем, содержится ли он во множестве В, и если такой элемент есть, то записываем его:

А∩В={3, 8, 15}.

в) Найти разность А и В.

Решение:

Находим элементы, которые содержатся в обоих множествах, отсеиваем их из множества А и записываем оставшиеся элементы:

А\В={1}

г) Найти разность В и А.

Действуем аналогично пункту в:\A={2}

д) Найти дополнение множества А и В.

Решение:

Записываем все элементы универсального множества, кроме тех, что содержатся во множестве А (В):

¬А={2, 4, 5, 6, 7, 9, 10, 11, 12, 13, 14, 16, 17, 18, 19, 20}

¬B={1, 4, 5, 6, 7, 9, 10, 11, 12, 13, 14, 16, 17, 18, 19, 20}

Задача № 8

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

         1. Возраст <= 500 and Население <= 5000 - 300 записей

         2. Возраст >= 300 and Возраст <= 500 and Население <= 5000 - 130 записей

         3. Возраст <= 500 and Население >= 1500 and Население <= 5000 - 155 записей

         4. Возраст >= 300 and Возраст <=500 and Население >=1500 and Население <= 5000 - 45 записей

Укажите запрос к этой базе, результатом выполнения которого будет 60 записей:

) Возраст < 300 and Население >=1500 and Население <= 5000

) Возраст >= 300 and Возраст <=500 and Население <1500

) Возраст < 300 and Население <1500

) Возраст < 300 and Население <= 5000

) Возраст <= 500 and Население < 1500

) Такого запроса нет среди перечисленных [23]

Ответ: 3