Читать онлайн «Введение в теорию информации. Учебное пособие»

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ Механико-математический факультет В. Н. Потапов ВВЕДЕНИЕ В ТЕОРИЮ ИНФОРМАЦИИ Учебное пособие Новосибирск 2009  УДК ББК Потапов В. Н. Введение в теорию информации / Новосиб. гос. ун-т. Новоси- бирск, 2009. 104 с. ISBN Учебное пособие представляет собой систематическое изложение основ теории информации, которая является математическим фундаментом для развития методов передачи и обработки информации. Учебное пособие предназначено для студентов математических факультетов уни- верситетов, а также может быть полезно для студентов-программистов и студентов естественнонаучных специальностей, связанных с обработкой информации. Рецезенты Учебное пособие подготовлено в рамках реализации Программы развития НИУ-НГУ c Новосибирский государственный университет, 2009 c Потапов В. Н. , 2009  3 Содержание Введение 4 Глава 1. Три подхода к понятию сложности сообщений 5 1. 1. Алгоритмический подход 5 1. 2. Комбинаторный подход 7 1. 3. Вероятностный подход 9 Глава 2. Определение и свойства энтропии разбиения 12 Глава 3. Цепи Маркова 19 3. 1. Эргодическая теорема для марковской цепи 19 3. 2. Закон больших чисел для марковской цепи 23 Глава 4. Модели источников сообщений 25 4. 1. Конечные автоматы 25 4. 2. Параметры модели источника сообщений 26 4. 3. Контекстная модель 28 4. 4. Метод трансфер-матрицы 30 4. 5. Скрытые марковские модели 32 Глава 5. Энтропия источника сообщений 35 5. 1. Стационарные источники. Энтропия стационарного источника 35 5. 2. Энтропия марковского источника 37 5. 3. Энтропия источника Бернулли 40 Глава 6. Кодирование 43 6. 1. Префиксные и разделимые множества слов 43 6. 2. Кодирование натуральных чисел 47 6. 3. Теорема кодирования Шеннона 48 6. 4.