Главная » Помощь в учебе » Школьные знания, ответы и решения школьных заданий » Информатика

Ответы по параграфу 1.3 Элементы теории множеств и комбинаторики

Нашли ошибку? Напишите нам
0.0/5, Голосов: 0

Учебник по Информатике 8 класс Босова

Немного теории по теме «Элементы теории множеств и комбинаторики»:
Пересечением (обозначается ⋂) двух множеств называется множество их общих элементов.
Например: A = {1, 2, 3}; B = {2, 5, 7}; A ⋂ B = {2}
Объединение (обозначается ∪) двух множеств называется множество, состоящее из всех элементов этих множеств и не содержащее никаких других элементов.
Например: A = {1, 2, 3}; B = {2, 5, 7}; A ∪ B = {1, 2, 3, 5, 7}

Задание 2. Задайте путем перечисления всех элементов:
а) множество О всех цифр, используемых для записи чисел в восьмеричной системе счисления;
б) множество К всех цепочек из 0 и 1, состоящих ровно из трех символов.

а) О = {0, 1, 2, 3, 4, 5, 6, 7}
б) К = {000, 001, 010, 011, 100, 101, 110, 111}

Задание 3. Пусть М = {а, б, в}, Р = {а, б, г, д, и}, К = {г, д, и}. Обсудите в группе и запишите с помощью фигурных скобок или знака ∅:
а) M ⋂ P = {а, б}
б) M ⋂ K = ∅
в) K ⋂ P = {г, д, и}
г) M ∪ P = {а, б, в, г, д, и}
д) M ∪ K = {а, б, в, г, д, и}
е) K ∪ P = {а, б, г, д, и}
ж) дополнение К до Р = {а, б}
з) дополнение ∅ до М = {а, б, в}

Задание 4. Обсудите в группе и запишите с помощью фигурных скобок множества:


Задание 5. Из каких элементов состоит:
а) объединение К и М;
б) пересечение К и М;
в) дополнение К до М;
г) дополнение пересечения М и А до М?


а) K ∪ M = {3, 4, 5, 6, 7}
б) K ⋂ M = {6, 7}
в) дополнение К до М = {3, 4, 5}
г) дополнение (M ⋂ A = {3}) до М = {4, 5, 6, 7}

Задание 6. В классе 35 учеников. 20 – из них занимаются в математическом кружке, 11 – в биологическом, а 10 ничем не занимаются. Сколько ребят занимаются и математикой, и биологией?

1) Найдем тех ребят, которые посещают кружки, убрав из общего числа учеников тех, кто ничем не занимается: 35 – 19 = 25 учеников.
2) (20 + 11) – 25 = 6 учеников занимаются и математикой и биологией.

Задание 7. Для составления цепочек используются бусины, помеченные буквами: M, N, O, P, S. Сколько разных цепочек можно составить из трех бусин, для которых выполняются следующие условия:
1) в середине цепочки стоит одна из бусин M, O, S;
2) третья бусина – любая гласная, если первая буква согласная, и любая согласная, если первая буква гласная;
3) на первом месте – одна из бусин O, P, S, не стоящая в цепочке в середине?


Ответ: 13 различных цепочек.
По середине у нас бусины M, O, S (1-е условие), по 3-му условию на первом месте у нас бусины O, P, S, не стоящие в цепочке в середине.
Для М на первом месте могут быть O, P, S. Для O на первом месте могут быть P, S (O не может быть на первом месте, так как в середине уже стоит такая бусина). Для S на первом месте могут быть O, P.
Чтобы выбрать третью бусину, мы придерживаемся 2-му условию. Так у нас получится 13 вариантов цепочек.

Задание 8. Сколько существует способов составить слово «ВИРУС», начиная с буквы В и двигаясь вправо или вниз до последней буквы?


Ответ: 16 способов

Задание 9. Алла Радугина защитила свой компьютер одним из четырехсимвольных паролей, составленных из букв «А» и «Р». Сколько всего существует вариантов таких паролей? Перечислите их.

M – максимально возможное количество слов;
N – количество символов в используемом алфавите;
k – длина слова.

Перечислим варианты:
АААА; АААР; ААРА; ААРР; АРАА; АРАР; АРРА; АРРР; РААА; РААР; РАРА; РАРР; РРАА; РРАР; РРРА; РРРР.

Задание 10. Каждый пользователь некой компьютерной системы получает уникальный идентификатор, представляющий собой k-символьную цепочку в четырехбуквенном алфавите. Укажите наименьшее k, позволяющее зарегистрировать в системе не менее тысячи пользователей.


Задание 11. Иван разработал приложение для планшета и защитил его оригинальным графическим ключом, использовав в качестве узлов вершины пятиугольника (каждую из вершин надо задействовать ровно один раз). Прав ли Иван, утверждая, что количество комбинаций его графического ключа ничуть не меньше, чем количество вариантов трехзначного цифрового пароля, вводимого со стандартной цифровой клавиатуры?

Посчитаем количество комбинаций в графическом ключе(в виде пятиугольника, вершину можно использовать один раз) и в трехзначном цифровом пароле.

Графический ключ:
Выбор первого элемента можно осуществить пятью способами. Второго – четырьмя способами. Третьего – тремя способами. Четвертого – двумя способами. Пятого элемента – одним. Посчитаем всевозможные перестановки по правилу произведения и получаем:
5*4*3*2*1=120 различных комбинаций у графического ключа, разработанным Иваном.

Трехзначный цифровой пароль:
Длина пароля равна k = 3. Если считать, что нами используются буквы английского алфавита (в нем 26 букв), тогда у нас N = 26.
Максимальное количество комбинаций: M=N^k=26^3=17576. Намного больше комбинаций, чем при использовании графического ключа. То есть Иван не прав.
Ответ: Иван не прав.

Задание 12. Итак, в двоичном алфавите можно составить 25 различных 5-символьных слов или цепочек из пяти 0 и 1: 00000, 00001, …., 11110, 11111. Вернемся к нашему множеству М = {1, 3, 5, 7, 9}. Попробуем закодировать его подмножество полученными двоичными цепочками: если на первом месте в цепочке присутствует единица, то в соответствующее подмножество входит цифра 1; если единица присутствует на втором месте в цепочке, то в соответствующее подмножество входит цифра 3 и т.д. Запишите подмножества, соответствующие цепочкам 00000, 01110, 00111, 11111. Что вы можете теперь сказать о количестве подмножеств множества М?

00000 – ∅ пустое подмножество
Так как все нули, то подмножество будет пустым.

01110 – {3, 5, 7}
Так как на 2, 3, 4 местах присутствует 1, то подмножество будет {3, 5, 7}

00111 – {5, 7, 9}
Так как на 3, 4 и 5 местах присутствует 1, то подмножество будет {5, 7, 9}

11111 – {1, 3, 5, 7, 9}
Так как везде присутствует 1, то подмножество будет {1, 3, 5, 7, 9}
Можно сказать, что у множества М может быть 32 различных подмножеств. Решение заданий из учебника Информатика 8 класс Босова, параграф 1.3 Элементы теории множеств и комбинаторики. Множество, операции над множествами, правила суммы и произведения.

Просмотров: 790