Биохимия спиртового брожения: Основу технологии получения пива составляет спиртовое брожение, - при котором сахар превращается...
Типы оградительных сооружений в морском порту: По расположению оградительных сооружений в плане различают волноломы, обе оконечности...
Топ:
Оценка эффективности инструментов коммуникационной политики: Внешние коммуникации - обмен информацией между организацией и её внешней средой...
Методика измерений сопротивления растеканию тока анодного заземления: Анодный заземлитель (анод) – проводник, погруженный в электролитическую среду (грунт, раствор электролита) и подключенный к положительному...
Когда производится ограждение поезда, остановившегося на перегоне: Во всех случаях немедленно должно быть ограждено место препятствия для движения поездов на смежном пути двухпутного...
Интересное:
Наиболее распространенные виды рака: Раковая опухоль — это самостоятельное новообразование, которое может возникнуть и от повышенного давления...
Инженерная защита территорий, зданий и сооружений от опасных геологических процессов: Изучение оползневых явлений, оценка устойчивости склонов и проектирование противооползневых сооружений — актуальнейшие задачи, стоящие перед отечественными...
Принципы управления денежными потоками: одним из методов контроля за состоянием денежной наличности является...
Дисциплины:
2017-12-12 | 201 |
5.00
из
|
Заказать работу |
|
|
В этом разделе мы будем рассматривать просто кодировки. (То есть такие, когда одно слово представляется в виде другого слова).
Во всех случаях рассматривается следующая модель. Есть два алфавита
А = (а 1, …, аn) иB = (b 1, …, bq).
Кодирование φ это отображение словα в алфавите А в слова β=φ(α) в алфавите В.
Кодирование будет дешифруемым, если по слову β однозначно восстанавливаетсяα. Тогда отображение φ – биекция.
Кодирование слов и поиск минимального кода
Пусть у нас есть кодируемые объекты x - слова в алфавите A.
Везде далее булев куб размерности n будем обозначать через Bn.
Нельзя ли найти минимальную длину K(x) кода объектаx, пусть даже в другом алфавите B?
Оказывается, эта задача алгоритмически неразрешима.
Теорема: Не существует МТ, которая строит код минимальной длины.
Доказательство. От противного.
Упорядочим все элементы всех булевых кубов Bn (сначала по увеличению размерности, а потом в лексикографическом порядке):
0, 1, 00, 01, 11, 000, 001… (*)
Пусть есть МТ Т 1, которая умеет по х строить К (х). Используя Т 1, строим другую МТ Т 2 = F (T 1, …). Эта машина переводит натуральное m в первое по порядку (слева направо в последовательности (*) слово x такое, что K (x)> m. (T 2 в (*)идет слева направо и на каждом шаге применяет Т 1.) Следовательно, m – код х, так как по m однозначно восстанавливается x. При этом длинаmравна l(m)= log m, но K (x) – наименьшая возможная длина кода. Значит, K (x) ≤ log m.
Получили противоречие.
Теорема доказана.
Если информация связана с кодом объекта, то одной из мер информации является длина этого кода. Аналогичной мерой для алгоритма является его сложность.
Пример. Задача: Требуется найти количество единиц в двоичной записи целого числа.
|
Если число n задается в виде n+1 единицы *1...1*, то длина входа n+3. Если число задается в десятичной форме, это уже lg n. К этим двум способам добавим двоичную запись числа n. Ее длина log 2n. Трудоемкость решения пропорциональная длине входа.
Но рассмотрим еще один подход к решению задачи. Пусть у нас есть 2n перенумерованных ячеек памяти, в каждой из которых содержится число, равное количеству единиц в двоичной записи номера ячейки. Тогда длина входа задачи для числа n равна 2n log 2n.Трудоемкость решения равна константе.
Есть и обратные примеры, когда стремление к сжатию информации, т.е. минимизация длины входа задачи, может привести к непропорционально большому росту сложности алгоритма.
Признаковое кодирование.
Этот метод можно использовать в разных ситуация, но типичное его применение – кодирование неформализованных объектов.
Субъект |
Множество объектов |
Код |
s1 |
sm |
p1 |
pk |
Признаки:
Рассматривается множество объектовs1,…,sm (люди, болезни, месторождения и т.п.), которое нужно кодировать, т.е. каждому объекту нужно сопоставить слово в алфавите. При этом есть другое множество объектов, называемых признаками, которые мы умеем кодировать. Тогда кодом объекта при признаковом кодировании является вектор, компонентами которого являются коды (значения) признаков, применительно к данному объекту.
При признаковом кодировании объекта признаком называется отображение , где Df— множество допустимых значений признака. Если заданы признакиf1,…,fn, то вектор x=(f1(x),…,fn(x)) называется признаковым описанием объекта x. Если признаковые описания отождествляют с самими объектами, то множество называют признаковым пространством.
В зависимости от множества признаки делятся на следующие типы:
1. бинарный признак: Df=(0,1);
2. номинальный признак: Df- конечное множество;
3. порядковый признак: Df - конечное упорядоченное множество;
4. количественный признак: Df - множество действительных чисел.
|
Можно использовать характеристические вектора признаков, например,
α (si) = (α 1, …, αk) .
Пример. s 1 … sn – люди.
Признаки:
1. Цвет волос
2. Рост
В случае бинарных значений признаков или использовании характеристических векторов при признаковом кодировании объектом исследования является матрица векторов признаков.
Опр. Тест - это множество столбцов в T (A) такое, что все строки в подматрице, образованной этим множеством, попарно различны.
Выше мы уже говорили о стремлении строить неизбыточные коды. С этой задачей связана известная проблема дискретной математики – проблема поиска минимальных тестов таблицы.
Длина теста – количество столбцов в тесте.
Тест будет тупиковым, если никакое его подмножество уже не будет тестом.
Минимальный тест – тест с минимальным количеством столбцов. Длину минимального теста обозначим через t(A).
Когда таблица T (A) – это признаковая таблица множества объектов (строки таблицы – вектора признаков объектов), то длина теста указывает на количество признаков, которых достаточно для различения объектов. Эти признаки соответствуют стобцам теста. Но будет ли их достаточно, если количество объектов увеличиться? В связи с этим вопросом тестовая тематика возникает и при определении качества выбора множества признаков.
Конечно, как математический объект, тест – это скорее тема таких дисциплин как комбинаторика, дискретная математика, теория распознавания, но, так как он тесно связан с проблемой грамотного представления информации, то это объект и теории информации.
Для получения содержательных результатов в области построения минимальных тестов необходимо накладывать ограничение на вид и структуру векторов признаков. В качестве примеров приведем несколько утверждений, доказательство которых либо очевидно, либо является несложным упражнением.(Обозначение приведены выше. Если не оговорено обратное – основание логарифма равно двум).
Утв. Справедливо неравенство
t(A)≥logm.
Заметим, что данное утверждение тесно связано с приведенным ниже понятием энтропия по Хартли. Оно означает, что если объектам даются битовые идентификаторы, то число бит в таком идентификаторе для различения mобъектов не может быть меньше log m.
|
Утв. Пусть строки матрицы Т(А) устроены так, что вместе с любой парой строк в матрице есть и строка, равная сумме этой пары по модулю два, тогда в такой матрице любой тупиковый тест будет минимальным и
t(A)=logm.
Данное утверждение станет для вас совершенно очевидным, если заметить, что в данном случае множество строк матрицы – подпространство булева куба.
(Ниже мы вернемся к этому вопросу, когда будем рассматривать, так называемые, линейные коды.)
Утв. Число тупиковых тестов таблицы не превосходит .
Утв. Если строками матрицы являются все наборы с четным числом единиц, то число тупиковых тестов такой таблицы равно числу ее столбцов.
Утв. Если строками матрицы являются все наборы с фиксированным числом единиц, то число тупиковых тестов такой таблицы равно числу ее столбцов.
|
|
История развития пистолетов-пулеметов: Предпосылкой для возникновения пистолетов-пулеметов послужила давняя тенденция тяготения винтовок...
Индивидуальные и групповые автопоилки: для животных. Схемы и конструкции...
Состав сооружений: решетки и песколовки: Решетки – это первое устройство в схеме очистных сооружений. Они представляют...
Общие условия выбора системы дренажа: Система дренажа выбирается в зависимости от характера защищаемого...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!