Эксперт по сдаче вступительных испытаний в ВУЗах
Практическая работа №1
Множества и операции над ними. Объединение пересечение, разность,
дополнение. Разбиение, булеан.
Цель работы.
Повторение основных понятий теории множеств, изучение операций над
ними приобретение навыков решения задач.
Теоретические положения.
Одними из основных понятий математики являются понятия множества и
элементов. Будем обозначать множества заглавными, а элементы — строчными
латинскими буквами. Элемент «а» может быть связан с множеством «А»
знаком принадлежности или отрицания принадлежности:
аА («а» принадлежит «А»), аА («а» не принадлежит «А»).
Множество может быть задано списком элементов, порождающей
процедурой или описанием характеристических свойств, которыми должны
обладать его элементы Множество, заданное списком, имеет вид:
А= {а1 а2, а3}; М={а,b,с,d} .
Список показывает, из скольких элементов и каких именно состоит
множество. Расположение элементов в списке может быть произвольным
(обычно применяется естественный порядок).
Множество, заданное порождающей процедурой:
Q= {q|q=2n, nN; 0N}.
Элементами множеств могут быть любые объекты, но всегда соблюдается
следующее требование: число элементов в множестве должно быть целым,
иначе понятие множества теряет смысл. Множества могут быть элементами
других множеств.
Если множество не содержит ни одного элемента, оно называется
пустым и обозначается .
Подмножеством А множества В называется такое множество А, все
элементы которого одновременно принадлежат В (обратное условие не
ставится). Подмножество обозначается знаком включения А В (А входит в
В). Собственным подмножеством называется такое А, что А В и в то же
время А В и А . При несоблюдении указанного условия подмножество
считается несобственным.
Пустое множество 0 в качестве несобственного подмножества входит в
любое множество.
Над множествами можно выполнять ряд операций: объединение, пересечение, разность, дополнение.
Объединением множеств называется множество элементов, принадлежащих хотя бы одному из объединяемых множеств:
AB = {а | аА или аВ}, например: А= {a, b,
c};B= {a, b, d}; С = AB= {a, b, с, d}.
Объединение является многоместной операцией, так как одновременно может объединяться любое число множеств.
Пересечением множеств (взятием общей части) называется множество, элементы которого одновременно принадлежат обоим пересекаемым
множествам:
АВ = {а | аА и аВ}, например:
А = {а, b, с}; В = {a, b, d}; С = АВ = {а, b}.
Пересечение тоже многоместно.
Разностью множеств А \ В называется множество элементов, принадлежащих А, но не принадлежащих В:
Практическая работа №2
Решение комбинаторных задач. Подстановки, алгебра подстановок. Решение
комбинаторных задач с использованием метода включения и
исключения. Задача о встречах.
Цель работы.
Приобретение навыков работы с комбинаторными конфигурациями, использования разработанных методов решения задач.
Теоретические положения.
Комбинаторика изучает комбинаторные конфигурации, т.е. возможные
варианты выбора и расположения элементов некоторого (обычно конечного) множества.
Рассмотрим в качестве примера типичную комбинаторную задачу — задачу
перечисления. Найдем мощность декартова произведения множеств. Декартово
произведение
М1М2М3 …Мm
m множеств с мощностями соответственно n1, n2, …nk состоит из кортежей длиной
m. На первом месте в каждом таком кортеже стоит один из элементов множества М1,
на втором — элемент из М2, и т.д. Соберем все кортежи с одинаковыми первыми элементами в отдельные классы. Всего таких классов будет n1 = M1. Внутри каждого класса произведем разбиение по второму элементу и т.д., пока не получим
классы, содержащие по одному элементу. В итоге общее количество элементов
декартова произведения составит
Если n = n1 =n2= … =nm. , то n=n mo =U mn — число размещений повторениями число размещений без повторений. Частный случай размещения без повторений получается при ir^m, т.е. когда число элементов в исходном
множестве совпадает с длинной рассматриваемых кортежей. Размещения этого
вида называются перестановками, а их число обозначается
Подстановкой назовем унарную операцию, позволяющую получить одну
Подстановкой назовем унарную операцию, позволяющую получить одну
перестановку из другой. Будем обозначать их буквами греческого алфавита.
Ссылка на первоисточник:
https://www.kgasu.ru
