Основные положения дискретной математики

Столбцы данной таблицы есть разбиение множества С. Известно, что разбиение определяет некоторое отношение эквивалентности, тогда процесс декодирования можно производить следующим образом: допустим, что получено сообщение Сi =011. Таким образом теория групп может рассматриваться математической основой теории кодирования.

ЛИНЕЙНАЯ АЛГЕБРА

Вектор (0, 0, ,0) со всеми координатами равными нулю, называется нулевым. Это единственный n-мерный вектор, для которого выполняются условия:

Если r/, то r/+= r/

Если r/, то r/-= r/

Если r/, то r/- r/=

Если r/, то 0* r/=

Если а, то а*=

РЕЛЯЦИОННАЯ АЛГЕБРА

Реляционная алгебра широко используется при создании реляционных БД. Носитель реляционной алгебры представляет собой множество отношений, где кроме операций конъюнкции, дизъюнкции, разности и декартового произведения используются операции выбора, проекции и соединения.

Операция выбора представляет собой процедуру построения «горизонтального» подмножества, т. е. подмножества кортежей (строк), обладающими заданными свойствами.

Пример: с помощью операции выбора построим отношение R/5 (расписание экзаменов профессора Иванова). Результатом операции выбора являются строки, в которых домен (столбец) D3 представлен значением профессор Иванов: это 1,6,8-я строки.

Таб.1

Для определения проекций отношений множество в реляционной алгебре разбивается на два подмножества в случае бинарного отношения и на n подмножеств в случае n-арного отношения:

,

Проекцией Пр (R2/A) бинарного отношения R2, R2на А называется множество элементов .

Проекцией Пр (R2/Ai1, Ai2,…Ain) n-арного отношения называется множество кортежей (аi1, ai2,…,aim), где , каждый из которых является частью элемента n-арного отношения Rn. операция проекции определяет построение «вертикального» подмножества отношения, т. е. множество подмножества кортежей, получаемого выбором одних доменов и исключения других доменов.

Пример: проекция Пр(R5/D2,, D3) порождает множество пар, каждая из которых определяет дисциплину и экзаменатора.

Таб. 2

одинаковые строки в таблице объединены в одну.

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

Пример: найдем по двум заданным таблицам (таб.3.а, таб.3.б) результат операции соединения по домену D1 (таб.3.в)

Таб. 3.а

 Скачать реферат