Модель является отображением чего-либо. В науке о природе моделирование используется как метод познания.
2.1 Преобразование к модели
1. Эксперимент на модели должен быть проще эксперимента на оригинале.
2. Информация об объекте, полученная в результате эксперимента на модели должна быть переносима на объект.
Существуют различные модели, которые используют в физике и математике.
В физике под моделью понимается реальный объект, в математике модель не обязательно является реальным объектом. однако суть этих моделей одинакова:
ü модель должна отражать характеристики и свойства объекта,
ü модель должна прогнозировать поведение объекта,
ü модель должна быть более простой, чем оригинал, но с другой стороны она должна как можно полнее отражать свойства объекта.
2.2 Способы моделирования
1. Макетное. Широко применяется в строительстве.
2. Физическое. Основой для такого моделирования является теория подобия.
3. Электрическое моделирование.
4. Математическое моделирование.
|
|
Мы остановимся на математическом моделировании. Модель представляет собой совокупность зависимостей, позволяющих прогнозировать заданные свойсвта объекта. В математике термин «модель» применяется наряду с обычным толкованием. Может означать, например, теорию подобную другой теории. Математика использует символические модели. Такая модель охватывает определенное множество абстрактных объектов: это числа, векторы и т. д. И отношения между ними.
Математическое отношение – это гипотетическое правило, связывающее между собой два или несколько символических объектов. Многие отношения могут быть выражены с помощью математических операций.
Математическая операция по определенному правилу любым двум элементам множества ставит в соответствие третий элемент, принадлежащий этому же множеству.
Характерным для математической модели может быть отсутствие объектов в физическом мире. Такие абстрактные модели являются отражением физических процессов, например, счет, упорядочение и т. д. Однако математическая модель будет воспроизводить физические стороны объекта, если будут установлены правила соответствия специфических свойств объекта математическим объектам и отношениям.
2.3 Алгебраические модели
Предположим, что объектом изучения являются элементы некоторого множества, о природе и свойствах которого мы ни чего не знаем. Подчиним элементы этого множества операциям, предварительно будем считать, что мы ни чего не знаем об этих операциях, но
3. ТЕОРИЯ КОДИРОВАНИЯ
В теории передачи информации существует проблема кодирования – декодирования, обеспечивающая надежную передачу информации при наличии помех.
|
|
Пусть А и В два конечных алфавита.
Алфавит – это конечное множество, элементами которого являются символы (буквы, цифры, знаки препинания, знаки операций и т. д.).
И R – некоторое множество конечных слов в алфавите А. Однозначное отображение множества R в некоторое множество слов в алфавите В называется кодированием множества R.
Образ С множества R при отображении называется кодом множества R. Слова из С называются кодовыми словами; при этом, если слово w из R отображается в слово v из С, то v называется кодом слова w. Слова из R называются сообщениями, алфавит А – алфавитом сообщений, алфавит В – кодирующим алфавитом. Если кодирующий алфавит В состоит из двух букв (в этом случае будем полагать, что ), то кодирование и соответствующий код С называется двоичным (с ними мы и будем работать).
Код называется равномерным или блочным, если все кодовые слова имеют одинаковую длину.
Блочный двоичный код, в котором каждое кодовое слово имеет длину n, представляет собой подмножество вершин n-мерного куба.
Пример: геометрическая модель трехзначного двоичного кода есть фигура трехзначного пространства, т. е. куб.
b=b1, b2, b3
b=000
b=001
b=010
b=011
b=100
b=101
b=110
b=111
Каждой вершине куба присвоена кодовая комбинация по принципу: если проекция на ось равна нулю, то в комбинации ставится ноль, а если проекция равна единице, то в комбинации ставится единица. Порядок проекций должен быть одним и тем же: b1, b2, b3. Длина ребра куба равна единице. d – это длина между соседними разрядами или кодовое расстояние.
Данный способ кодирования обозначим (2,3). В этой ситуации невозможно ни обнаружить ошибку ни исправить ее.
Пусть разрешенными кодами являются 000 и 111, тогда количество возможных кодов – 8, количество разрешенных кодов – 2, расстояние между разрешенными кодами = 3.
Для того чтобы определить кодовое расстояние между двумя комбинациями двоичного кода достаточно просуммировать эти комбинации по модулю 2 и подсчитать число единиц в полученной комбинации. Пример:
. 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 Коды с обнаружением ошибок
Имеем кодовое слово а=а1, а2,…, аm; составляем другое кодовое слово с добавлением символа – b=b1, b2…bm, bm+1
ai=bi
bm+1=………..
получим на входе нечетный код, он является всегда ошибочным. Ошибку обнаружить можно но исправить нельзя. Данный код соответствует разработанному примеру (2,3)
3.2 Корректирующие коды
а=а1, а2,…, аm
b= a1 a1 a1, a2 a2 a2,…am am am
ai=bi, длина кода 3m
а2 а2 а2
если 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 |
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 | II |
Столбцы данной таблицы есть разбиение множества С. Известно, что разбиение определяет некоторое отношение эквивалентности, тогда процесс декодирования можно производить следующим образом: допустим, что получено сообщение С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
R5 | D1 | D2 | D3 | D4 | D5 |
K 5-01 | Теория автоматов | Пр. Иванов | 03.01 | Ауд.210 | |
K 5-02 | Теория автоматов | Пр. Иванов | 09.01 | Ауд.211 | |
K 5-04 | Матем. статистика | Пр. Иванов | 10.01 | Ауд.210 |
Для определения проекций отношений множество в реляционной алгебре разбивается на два подмножества в случае бинарного отношения и на n подмножеств в случае n-арного отношения:
,
Проекцией Пр (R2/A) бинарного отношения R2, R2 на А называется множество элементов .
Проекцией Пр (R2/Ai1, Ai2,…Ain) n-арного отношения называется множество кортежей (аi1, ai2,…,aim), где , каждый из которых является частью элемента n-арного отношения Rn. операция проекции определяет построение «вертикального» подмножества отношения, т. е. множество подмножества кортежей, получаемого выбором одних доменов и исключения других доменов.
Пример: проекция Пр(R5/D2,, D3) порождает множество пар, каждая из которых определяет дисциплину и экзаменатора.
Таб. 2
R2 | D3 | D3 |
теория автоматов | пр. Иванов | |
математическая статистика | пр. Петров | |
физика | пр. Сидоров | |
алгоритмические языки | пр. Иванов |
одинаковые строки в таблице объединены в одну.
Операция соединения по двум таблицам, имеющим общий домен, позволят построить одну таблицу, каждая строка которой образуется соединением двух строк исходных таблиц. Из заданных таблиц берут строки, содержащие одно и то же значение из общего домена; общему домену сопоставляется один столбец.
Пример: найдем по двум заданным таблицам (таб.3.а, таб.3.б) результат операции соединения по домену D1 (таб.3.в)
Таб. 3.а
R5 | D1 | D2 | D3 | D4 | D5 |
K5-01 | теория автоматов | пр. Иванов | 03.01 | ауд. 210 | |
K5-02 | математ. статистика | пр. Петров | 03.01 | ауд. 211 | |
K5-03 | физика | пр. Сидоров | 05.01 | ауд. 211 | |
K5-04 | алгоритмич. языки | пр. Иванов | 05.01 | ауд. 210 |
Таб.3б
R5 | D1 | D2 | D3 | D4 | D5 |
K5-01 | физика | пр. Сидоров | 09.01 | ауд. 210 | |
K5-04 | математ. статистика | пр. Иванов | 10.01 | ауд. 210 | |
K5-02 | теория автоматов | пр. Иванов | 09.01 | ауд. 211 | |
K5-03 | алгоритмич. языки | пр. Петров | 10.01 | ауд. 211 |
Таб.3в
R5 | D1 | D2 | D3 | D4 | D5 | D/2 | D/3 | D/4 | D/5 |
K5-01 | теор.автом. | пр. Ив | 03.01 | а.210 | физика | пр.Сид | 09.01 | а.210 | |
K5-02 | мат. стат. | пр. Пет | 03.01 | а.211 | т. авт. | пр.Ив | 09.01 | а.211 | |
K5-03 | физика | пр. Сид | 05.01 | а.211 | алг.яз. | пр.Пет | 10.01 | а.211 | |
K5-04 | алг. языки | пр. Ив | 05.01 | а.210 | мат. ст. | пр.Ив | 10.01 | а.210 |
Аналогично можно определить операцию соединения не только по условию «равенства», но и по другим условиям сравнения: <,>. Определим например операцию соединения по условию > соединение по условию > отношения Rа по атрибуту х и отношения Rb по атрибуту у (атрибуты х, у являются атрибутами одного и тог же домена общего для отношений Rа, Rb), х>у называется множество всех кортежей , таких, что - конкатенация кортежа аi, принадлежащего Rb, где х - часть аi, у – часть bi и х>у.
Запрос в реляционной БД будет выполнен тем быстрее, чем меньше операций над отношениями он содержит Таким образом представляет практический интерес рассматриваемая выше задача упрощения представления множества через введенные операции.