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

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

Примеры:

1. отношение равенства на любом множестве является отношением эквивалентности;

2. утверждение вида (a+b)(b-a)=a²-b² - формулы соединенные знаком равенства задают бинарное отношение. Такое отношение называют отношением равносильности. Оно отличается от равенства, т. к. может выполняться для различных формул.

3. Отношение подобия геометрических фигур, «быть соседями по квартире», «быть ровесниками» так же являются отношениями эквивалентности.

Каждое отношение эквивалентности является в определенном смысле равенством, например, отношение «быть ровесником» означает равенство возрастов.

Задание №3

Какие из перечисленных отношений являются отношениями эквивалентности, а какие - отношениями порядка: <, (на множестве действительных чисел), предшествовать (на множестве слов в словаре), быть однофамильцем (на множестве учащихся в данном вузе).

Решение: необходимо проверить каждое из свойств отношений (аналогично заданию №2) и определить эквивалентность или порядок отношений.

2. МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ

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

2.1 Преобразование к модели

Эксперимент на модели должен быть проще эксперимента на оригинале.

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

Существуют различные модели, которые используют в физике и математике.

В физике под моделью понимается реальный объект, в математике модель не обязательно является реальным объектом. однако суть этих моделей одинакова:

модель должна отражать характеристики и свойства объекта,

модель должна прогнозировать поведение объекта,

модель должна быть более простой, чем оригинал, но с другой стороны она должна как можно полнее отражать свойства объекта.

2.2 Способы моделирования

Макетное. Широко применяется в строительстве.

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

Электрическое моделирование.

Математическое моделирование.

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

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

Математическая операция по определенному правилу любым двум элементам множества ставит в соответствие третий элемент, принадлежащий этому же множеству.

Характерным для математической модели может быть отсутствие объектов в физическом мире. Такие абстрактные модели являются отражением физических процессов, например, счет, упорядочение и т. д. Однако математическая модель будет воспроизводить физические стороны объекта, если будут установлены правила соответствия специфических свойств объекта математическим объектам и отношениям.

2.3 Алгебраические модели

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

3. ТЕОРИЯ КОДИРОВАНИЯ

В теории передачи информации существует проблема кодирования - декодирования, обеспечивающая надежную передачу информации при наличии помех.

Пусть А и В два конечных алфавита.

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

И R - некоторое множество конечных слов в алфавите А. Однозначное отображение множества R в некоторое множество слов в алфавите В называется кодированием множества R.

Образ С множества R при отображении называется кодом множества R. Слова из С называются кодовыми словами; при этом, если слово w из R отображается в слово v из С, то v называется кодом слова w. Слова из R называются сообщениями, алфавит А - алфавитом сообщений, алфавит В - кодирующим алфавитом. Если кодирующий алфавит В состоит из двух букв (в этом случае будем полагать, что ), то кодирование и соответствующий код С называется двоичным (с ними мы и будем работать).

Код называется равномерным или блочным, если все кодовые слова имеют одинаковую длину.

Блочный двоичный код, в котором каждое кодовое слово имеет длину n, представляет собой подмножество вершин n-мерного куба.

Пример: геометрическая модель трехзначного двоичного кода есть фигура трехзначного пространства, т. е. куб.

b=b₁, b₂, b₃

b=000

b=001

b=010

b=011

b=100

b=101

b=110

b=111

Каждой вершине куба присвоена кодовая комбинация по принципу: если проекция на ось равна нулю, то в комбинации ставится ноль, а если проекция равна единице, то в комбинации ставится единица. Порядок проекций должен быть одним и тем же: b₁, b₂, b₃. Длина ребра куба равна единице. d - это длина между соседними разрядами или кодовое расстояние.

Данный способ кодирования обозначим (2,3). В этой ситуации невозможно ни обнаружить ошибку ни исправить ее.

Пусть разрешенными кодами являются 000 и 111 , тогда количество возможных кодов - 8, количество разрешенных кодов - 2, расстояние между разрешенными кодами = 3.

Для того чтобы определить кодовое расстояние между двумя комбинациями двоичного кода достаточно просуммировать эти комбинации по модулю 2 и подсчитать число единиц в полученной комбинации. Пример:

000

111

. 111 число единиц = 3. Значит d=3.

Получаем сообщение с одной ошибкой в разряде. Тогда отнесем ошибочный код к той вершине, которая отстает на единицу. Вместо ошибочного кода запишем координату вершины (0,0,0), получим исправляющийся код тогда возможны три ситуации:

(3,3) когда количество сообщений = 8, количество кодов = 8. В этом случае ошибочный код будет совпадать с одним из сообщений и поэтому ошибку обнаружить невозможно.

(2,3) количество сообщений = 4, количество кодов = 8, тогда получим 4 разрешенных кода, совпадающих с вершинами (рис. 8).

1

67

Ошибку обнаружить можно, но исправить нельзя.

(1,3) ошибку можно и обнаружить и исправить.

Если мы хотим построить код, который может обнаружить n ошибок, то расстояние между кодовыми словами d = k + 1.

Если мы хотим исправлять ошибку, то расстояние должно быть d=2s+1

Если мы хотим построить код одновременно обнаруживающий и исправляющий ошибку, то минимальное кодовое расстояние должно быть

d=k+s+1.

Для того, чтобы в принятом сообщении можно было обнаружить ошибку, это сообщение должно обладать некоторой избыточностью информации, позволяющей отличить ошибочный код от правильного. Например, если переданное сообщение состоит из трех абсолютно одинаковых частей, то в принятом сообщении отделение правильных символов от ошибочных может быть осуществлено по результатам накопления посылок одного вида. Для двоичных кодов этот метод можно проиллюстрировать следующим примером:

10110 - переданная кодовая комбинация

10010 - 1-я принятая комбинация

10100 - 2-я принятая комбинация

00110 - 3-я принятая комбинация

10110 - накопленная комбинация

Как видим на всех трех комбинациях, были ошибки, но накопленная комбинация ошибок не содержит.

Еще одним методом обнаружения ошибок является проверка на четность или нечетность, суть которого состоит в том, что к исходным кодам добавляются нули либо единицы таким образом, чтобы их сумма всегда была четной или нечетной. Сбой любого одного символа всегда нарушит условие четности (нечетности) и ошибка будет обнаружена. В этом случае комбинации друг от друга должны отличаться в двух символах. Запрещенными являются все нечетные комбинации при проверке на четность и наоборот).

3.1 Коды с обнаружением ошибок

Имеем кодовое слово а=а₁, а₂,…, а_m; составляем другое кодовое слово с добавлением символа - b=b₁, b₂…b_m, b_m+1

a_i=b_i

b_m+1=………..

получим на входе нечетный код, он является всегда ошибочным. Ошибку обнаружить можно но исправить нельзя. Данный код соответствует разработанному примеру (2,3)

3.2 Корректирующие коды

а=а₁, а₂,…, а_m

b= a₁ a₁ a₁, a₂ a₂ a₂,…a_m a_m a_m

a_i=b_i, длина кода 3_m

а₂ а₂ а₂

если 0 0 0, то ошибки нет

если 1 1 1, то ошибки нет

если 0 1 1, то ошибка есть

Такие корректирующие коды надежность, причем их надежность возрастает с увеличением дублирующих, но не экономичны.

Аксиомы расстояния:

d(a,b)0

d(a,b)=0, если a=b

d(a,b)= d(b,a)

d(a,b)+d(b,c) d(a,c)

3.3 Групповые коды

Рассмотрим множество двоичных кодов с заданной операцией (сложение по модулю).

Запишем таблицу истинности для операции «сложение по модулю»

a+(b+c)=(a+b)+c

a+b=b+a

a+a=0, (a^-1=a)

a+0=a

На множестве кодов задана группа (В,+,0) в свою очередь множество принятых сообщений С образуют группу (С,+,0). Для рассмотренного примера множество кодов b= c=. Очевидно, что множество b является подгруппой множества С.

3.4 Классы

классы.

Смежным классом В и С называется множество В+С, где С - фиксированный элемент, а b пробегает все значения множества В. для примера построим левый смежный класс.

Два смежных класса пересекаются либо совпадают, а множество левых классов образуют разбиение множества С.

Восемь левых смежных классов:

b c

000 +000=000 000+111=111

001+000=001 001+111=110

010+000=010 010+111=101

011+000=011 011+111=100

100+000=100 100+111=011

101+000=101 101+111=010

110+000=110 110+111=001

111+000=111 111+111=000

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

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

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

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

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

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

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

Если а, то а*=

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

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

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

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

Таб.1

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

,

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

Проекцией П_р (R₂/A_i1, A_i2,…A_in) n-арного отношения называется множество кортежей (а_i1, a_i2,…,a_im), где , каждый из которых является частью элемента n-арного отношения R_n. операция проекции определяет построение «вертикального» подмножества отношения, т. е. множество подмножества кортежей, получаемого выбором одних доменов и исключения других доменов.

Пример: проекция П_р(R₅/D_2,, D₃) порождает множество пар, каждая из которых определяет дисциплину и экзаменатора.

Таб. 2

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

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

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

Таб. 3.а

Таб.3б

Таб.3в

Аналогично можно определить операцию соединения не только по условию «равенства», но и по другим условиям сравнения: <,>. Определим например операцию соединения по условию > соединение по условию > отношения R_а по атрибуту х и отношения R_b по атрибуту у (атрибуты х, у являются атрибутами одного и тог же домена общего для отношений R_{а ,} R_b ), х>у называется множество всех кортежей , таких, что - конкатенация кортежа а_i, принадлежащего R_b, где х - часть а_i, у - часть b_i и х>у.

Запрос в реляционной БД будет выполнен тем быстрее, чем меньше операций над отношениями он содержит Таким образом представляет практический интерес рассматриваемая выше задача упрощения представления множества через введенные операции.