Образовательная программа среднего профессионального образования Комплект контрольнооценочных средств по учебным

• Название: Образовательная программа среднего профессионального образования Комплект контрольнооценочных средств по учебным
• Дата: 03.05.2023
• Размер: 0.96 Mb.
• Имя файла: 0000ec2b-08a5ffa8.docx
• Тип: Образовательная программа; #1105706
• страница: 5 из 6

Отношения на множестве.

Если в декартовом произведении в качестве множества В выбрать множество А ( то есть А Х А= А ), то отношение k из А называется отношением на множестве.

Для отношений на множестве вводятся понятия:

• 
  Обратное отношение-это множество пар (а,b) таких, что (b,a) А .
  

• 
  Дополнение-это множество пар (а,b) k.
  

• 
  Тождественное отношение-множество пар (а, а) таких, что, а А,
  

I= {(a, a), a A}

• 
  Универсальное отношение U={(a,b),a A, b _А}
  

Виды отношений:

1. 
   Инъекция.
   

Е сли каждый элемент множества А соответствует элементу из множества В, то отношение f называется инъективным.

Рис.2. Инъекция.

2. 
   Сюръекция.
   

Если для каждого элемента y множества В существует элемент х А, соответствующий элементу y, то такое отношение f называется сюръекцией.



Рис.3.Сюръекция.

3. 
   Биекция.
   

Если для каждого элемента y B существует ровно один элемент х А, которому соответствует y , то такое отношение называется биективным.

Биективное отношение инъективно и сюръективно.

Биективное отношение имеет обратное отношение.



Рис.4. Биекция.

18. 
    Отношение эквивалентности.
    

Определение.Отношение называется отношением эквивалентности (или просто эквивалентностью), если оно рефлексивно, симметрично и транзитивно.

Эта система обладает следующими свойствами:

1. 
   она образует разбиение множества , то есть классы попарно не пересекаются;
   
2. 
   любые два элемента из одного класса эквивалентны;
   
3. 
   любые два элемента из разных классов не эквивалентны.
   

Все эти свойства прямо следуют из определения отношения эквивалентности.

19. 
    Исследование бинарных отношений на рефлексивность, симметричность и
    

транзитивность; выделение классов эквивалентности

Определение 1. Отношение называется отношением нестрогого порядка, если оно является рефлексивным, антисимметричным и транзитивным.

Определение 2. Отношение называется отношением строгого порядка, если оно является антирефлексивным, антисимметричным и транзитивным.

Оба типа отношений вместе называются отношениями порядка. Элементы сравнимы по отношению порядка , если выполняется одно из двух отношений или . Множество , на котором задано отношение порядка, называется полностью упорядоченным, если любые два его элемента сравнимы. В противном случае, множество называется частично упорядоченным.

20. 
    Композиция отображений
    

Определение.Пусть нам даны соответствия fÍАхВ, gÍCхD, то композицию соответствия gf будет представлять собой gfÍ АхD и действовать так:
"аÎ А: (gf)(а)= g(f(а))

Пример. fÍRх[-1;1] gÍ [-1;2]х[-4;8]

f(х)=sinх g(х)=4х

Нужно построить gf и fg.

gfÍRх[-4;8] fgÍ [-1;2]х[-1;1]

1) фиксируем элемент хR

(gf)(х)= g(f(х))= 4sinх

2) фиксируем элемент х[-1;2]

(fg)(х)=f(g(х))= 4sinх

21. 
    Операции над подстановками
    

Операция над (на) множеством M это функция [7]:



Из определения операции видно, что она замкнута на множестве М, т.е. результат операции не выходит за пределы этого множества.

Еще одно свойство операции – однозначность результата, т.е.

упорядоченный набор n элементов (операндов) дает в результате операции только один элемент.

Порядок операции – это количество ее операндов: n = 1 соответствует унарной (монадической) операции, n = 2 – бинарной (диаедической) операции и т.д.

Далее рассматриваются только бинарные операции. Они могут быть заданы в одной из трех форм:

infix ( например, x + y);

prefix ( +xy );

postfix ( xy+ ).

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

22. 
    Решение задач на запись циклического разложения подстановки
    

Подстановка на множестве M – это биекция [7]:

MN_n, n = |M| N.

В случае конечного множества M (как выше) количество подстановок определяется как количество перестановок из n элементов:



Можно считать, n ящиков заполняются объектами x₁, …, x_n, x_iM.

Поскольку MбиективноN_n, можно определить подстановку как N_nN_n, т.е. иметь дело только с натуральными числами:



{i₁, i₂, … , i_n} = N_n.

Обычно подстановка задается в форме стандартной таблицы, имеющей две строки. Верхняя строка всегда содержит последовательные натуральные числа, начиная с 1. В нижней строке, конечно, не должно быть повторений.

Например:



Подстановка, как и любое бинарное отношение, может быть составной



.

Видно, что в «контрпримере» , т.е. «произведение» подстановок некоммутативно.

В составе любой подстановки можно выделить циклы. Их длина может составлять 1, 2,…, n. Цикл длины 1 – это фактически вырожденный цикл, стационарный элемент.

23. 
    Выполнение операций и решение простейших уравнений в алгебре подстановок.
    

1: Коммутативность.

x y = y x, x, yM.

Например, на множестве целых чисел Zоперация сложения коммутативна – в отличие от операции вычитания.

2: Ассоциативност ь.

(x y) z = x (y z), x, y, zM.

Фактически речь идет об изменении порядка действий (задаваемого скобками).

Например, операция вычитания не ассоциативна.

3: Единица.

l x = x, l, xM, l– леваяединица.

x r = x, r, xM, r – правая единица.

e x = x e = x, e, xM, е – двусторонняя или просто единица.

Например, сложение на множестве вещественных чисел Rимеет единицу (аддитивную):

a + 0 = 0 + a = a.

Вычитание имеет только правую единицу:

a – 0 = a, но 0 – a a (если a  0).

Единица операции умножения (типа умножения) – мультипликативная, обозначается обычно «1» .

4: Обратный элемент.

х – левый обратный элемент по отношению к у, а у – правый по отношению х, если

х  у = е.

«Просто» обратный элемент (взаимно обратные элементы), если

х  у = у х = е.

Существование и единственность единицы и обратного элемента позволяет решать простейшие уравнения (п.4).

5: Идемпотентность.

х х = х, х  М.

Вообще-то количество одинаковых элементов в выражении может быть любым. Идемпотентность позволяет в необходимых случаях сжимать или, наоборот, растягивать выражение. То же, кстати, было и в алгебре логике для операций дизъюнкция и конъюнкция.

6: Дистрибутивность.

Здесь уже требуются две операции, обозначаемые, например,  (операция типа умножение) и  (операция типа сложение).

Дистрибутивность  по отношению к:

х  (у z) = (х  у)  (х z),

(х  у) z= (х z)  (у z),

x, y, zM.

24. 
    Понятие вычета по модулю N. Операции над вычетами. Шифрование
    

Вычетом числа a по модулюm называется остаток от деления a на m

Из определения видно, что вычеты связаны с делением с остатком.

Разделить натуральное число aна нату­ральное число b с остатком означает yнайти неотрицательные числа два числа qи г, причем г
а = q·b + г

25. 
    Метод математической индукции
    

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

2.) Переход индукции: если верно какое-то утверждение ряда (неважно, какое именно), то верно и следующее за ним утверждение ряда.

26. 
    Решение задач на выполнение операций в алгебре вычетов
    

Для степени y=2ⁿ(n–натуральное число) установить классы сравнимости. Установить зависимость последней цифры этой степени от ее показателя.

Решение и комментарии.

Как известно, натуральные степени числа 2 оканчиваются циф­рами {2, 4, 8, 6}. См. таблицу нескольких степеней числа 2.

Опреде­лим функцию, которая ставит в соответствие каждому натуральному числу ппоследнюю цифру числа 2^я:

n	2n	Последняя цифра 2т
1	2	2
2	4	4
3	8	8
4	16	6
5	32	2
6	64	4
7	128	8
8	256	6

f: N®{2, 4, 8, 6},

Эта функция f(n) периодична с периодом 4. Это значит, что для целого числа k: f(n)=f(n+4)= f(n+4k),.

Причем справедливы так же равенства: f(n)=f(n-4)= f(n-4k)

Последнее равенство означают, что для любого пнужно найти минимальное натуральное т, такое, что f(m) = f(m + 4k) = f(n).

Но это задача на делении с остатком числа n на 4:

n=4k+m, k-частное, т - остаток.

Очевидно, последняя цифра числа 2" зависит от остатка, полученного при делении показателя n степени 2 ⁿ на 4.

Отразим этот факт в записи функции: f(n)= f(nmod 4)

Из этой формулы можно установить, если f(nmod 4)=0, то

При делении чисел на 4 "nÎN, останки могут быть: 0,1,2,3. Таким образом, в частности, множество всех возможных показателей степени 2 ⁿ для любого n состоит из четырех подмножеств: 4k, 4k+ 1, 4k+ 2, 4k+3.

27. 
    Генерирование К-элементных подмножеств данного множества
    

Для каждого сгенерированного элемента затем проверяются какие-то свойства для конкретной задачи. Задачи, в которых требуется определить количество возможных операций, называется комбинаторными. Пусть имеется группа некоторых объектов , , которые мы будем называть элементами.

Из этой группы элементов будем образовывать подгруппы. Такие подгруппы будем называть соединениями.

Из этих соединений выделим классы, которые будем называть размещениями.