Новосибирск: НГУ, 2013. — 109 с.
Учебное пособие представляет собой систематическое изложение основ
теориии нформации, которая является математическим фундаментом для
развития методов передачи и обработки текстов и сигналов. Пособие
предназначено для студентов и аспирантов математических факультетов
университетов, а также может быть полезно для
студентов-программистов и студентов естественнонаучных
специальностей, связанных с анализом и преобразованием информации.
Введение
Три подхода к понятию сложности сообщений
Алгоритмический подход
Комбинаторный подход
Вероятностный подход Определение и свойства энтропии разбиения Цепи Маркова
Эргодическая теорема для марковской цепи
Закон больших чисел для марковской цепи Модели источников сообщений
Конечные автоматы
Параметры модели источника сообщений
Контекстная модель
Метод трансфер-матрицы
Скрытые марковские модели Энтропия источника сообщений
Стационарные источники. Энтропия стационарного источника
Энтропия марковского источника
Энтропия источника Бернулли Кодирование
Префиксные и разделимые множества слов
Кодирование натуральных чисел
Теорема кодирования Шеннона
Побуквенное кодирование
Равноблочное на выходе кодирование
Нумерационное кодирование
Арифметическое кодирование
Адаптивное и универсальное кодирования
Интервальное кодирование
Преобразование Барроуза — Уилера Сложность слова относительно программы
Схема Лемпела — Зива
Схема конкатенации Недоопределённые данные
Энтропия недоопределённых данных
Энтропия разбиения, при заданной точности воспроизведения
Кодирование недоопределённых данных Передача сообщений по каналам связи, допускающим ошибки
Канал связи и его пропускная способность
Теорема кодирования для канала связи, допускающего ошибки
Обращение теоремы о помехоустойчивом кодировании
Избыточность универсального кодирования как пропускная способность некоторого канала Предметный указатель
Именной указатель
Литература
Алгоритмический подход
Комбинаторный подход
Вероятностный подход Определение и свойства энтропии разбиения Цепи Маркова
Эргодическая теорема для марковской цепи
Закон больших чисел для марковской цепи Модели источников сообщений
Конечные автоматы
Параметры модели источника сообщений
Контекстная модель
Метод трансфер-матрицы
Скрытые марковские модели Энтропия источника сообщений
Стационарные источники. Энтропия стационарного источника
Энтропия марковского источника
Энтропия источника Бернулли Кодирование
Префиксные и разделимые множества слов
Кодирование натуральных чисел
Теорема кодирования Шеннона
Побуквенное кодирование
Равноблочное на выходе кодирование
Нумерационное кодирование
Арифметическое кодирование
Адаптивное и универсальное кодирования
Интервальное кодирование
Преобразование Барроуза — Уилера Сложность слова относительно программы
Схема Лемпела — Зива
Схема конкатенации Недоопределённые данные
Энтропия недоопределённых данных
Энтропия разбиения, при заданной точности воспроизведения
Кодирование недоопределённых данных Передача сообщений по каналам связи, допускающим ошибки
Канал связи и его пропускная способность
Теорема кодирования для канала связи, допускающего ошибки
Обращение теоремы о помехоустойчивом кодировании
Избыточность универсального кодирования как пропускная способность некоторого канала Предметный указатель
Именной указатель
Литература