Основные положения дискретной математики (стр. 3 из 11)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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), получим исправляющийся код тогда возможны три ситуации:

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

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

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

3. (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	A+b
0	0	0
0	1	1
1	0	1
1	1	0

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 пробегает все значения множества В. для примера построим левый смежный класс.

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