f₁ : B^∗ → {^{0, 1}}^∗                                                                         f₂ : L→ {^{0, 1}}^∗

    Алгоритм  Хаффмана                                                           С учетом структуры   

раз.

    Пример  2.13. Пусть

    Рассмотрим  схему кодирования

    Схема  f₁ задает взаимно-однозначное кодирование языка L₁, так как фрагмент abc может быть закодирован одним символом 0, для взаимной однозначности кодирования достаточно каким-то образом кодировать число вхождений фрагмента abc в слово языка.

Пример  2.14. Пусть (Здесь a+ означает произвольную непустую последовательность букв a).

    Буквы b и c контекстно-различимы, их можно кодировать одинаково. Поэтому следующая схема кодирования f₂ задает взаимно-однозначное кодирование языка L₂:

    Пусть L неприводимый язык и F(L) – множество всех взаимно-однозначных кодирований языка L, задаваемых схемами алфавитного кодирования.

    Пусть на множестве букв алфавита B языка L задано распределение вероятностей P. Обозначим через C *(L,P) стоимость оптимального алфавитного кодирования, учитывающего синтаксис языка L, и через C *(B*,P) стоимость кодирования по алгоритму Хаффмана (обозначавшуюся ранее как C *(P) ). Для a ∈ L через C *(L,a) обозначим  , где f * - оптимальное алфавитное кодирование, учитывающее синтаксис языка L, и через C*(B*,a) - длину кода слова a ∈ L , построенного по алгоритму Хаффмана.

    В качестве меры эффективности кодирования, учитывающего синтаксис языка  L, рассмотрим коэффициент сжатия

Теорема 2.10. Пусть L – неприводимый язык. Тогда 

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

алфавитного кодирования  не более чем в два раза.

    Теорема 2.11. Для почти всех неприводимых языков

Z(L) =1. 
 

     Заключение 

    В ходе курсовой работы была рассмотрена  задача кодирования, которая включает в себя:

    1.Обеспечение  экономичности передачи информации  посредством устранения избыточности.

    2. Обеспечение надежности (помехоустойчивости) передачи информации.

    3.Согласование скорости передачи информации с пропускной способностью канала.

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

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

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

    На  основании приведенных примеров можно сделать вывод, что почти все неприводимые языки несжимаемы с помощью алфавитного кодирования.

    При рассмотрении алфавитного кодирования, учитывающего синтаксические свойства

языка, возникают  две задачи:

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

2. Задача оптимального  кодирования.

    Проблема  распознавания взаимной однозначности  алфавитного кодирования для языков, описываемых источниками с конечным числом состояний, решена Ал.А.Марковым (1961 г.)

    Задача  оптимального алфавитного кодирования  для конечных источников сложная  – она остается открытой. Задача решена для отдельных подклассов источников. 
 
 
 
 

     Список  литературы

1. Андерсон  Д.А. Дискретная математика и комбинаторика / Д.А. Андерсон. – М.: Издательский дом «Вильямс», 2003. – 960 с.
2. Белоусов А.И. Дискретная математика: Учеб. для втузов / А.И.Белоусов, С. Б. Ткачев; Под ред.: В.С. Зарубина, А.П. Крищенко. - 2-е изд., стер. - М.: Изд-во МГТУ им. Н.Э. Баумана, 2002. - 744с.
3. Жильцова Л.П. Об алгоритмической сложности задач оптимального алфавитного кодирования для контекстно-свободных языков // Дискретная математика. - 1989. - Том 1, вып. 2. С. 38 - 51.
4. Марков А.А. Введение в теорию кодирования. - М.: Наука, 1982. – 192 с.
5. Марков А.А. Об алфавитном кодировании. – ДАН СССР, 1960, 132, №3, с. 521 – 523; 1961, 139, №3, с. 560 – 561.
6. Новиков Ф.А. Дискретная математика для программистов: Учеб. пособие для вузов / Ф. А. Новиков. - 2-е изд. - СПб.: Питер, 2005. - 368с.
7. Шеннон К. Математическая теория связи. // Работы по теории информации и кибернетике. - М.: ИЛ, 1963. - С. 243 - 332.
8. Яблонский С.В. Введение в дискретную математику. - М.: Наука,2000.