Добавил:
Upload
Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз:
Предмет:
Файл:ЭлектрОТИ-Сложность1.docx
X
- •Э.Н.Гордеев теория информации и сложность алгоритмов
- •Гордеев Эдуард Николаевич теория информации и сложность алгоритмов.
- •Раздел 1. Информация и Алгоритм. Коды объектов. 6
- •Раздел 2. Сжатие информации. 11
- •Предмет курса
- •Основная цель курса
- •Что такое информация?
- •Раздел 1. Информация и Алгоритм. Коды объектов. 5
- •2.2 Основной вывод: информация и алгоритм – взаимообусловленные понятия. 8
- •Раздел 2. Сжатие информации. 11
- •Раздел 1. Информация и Алгоритм. Коды объектов.
- •Введение
- •Подходы к определению информации.
- •Описательный подход
- •Использование аналогии и эквивалентности
- •Основной вывод: информация и алгоритм – взаимообусловленные понятия.
- •Представление (кодирование) информации.
- •Раздел 2. Сжатие информации.
- •Кодирование информации. Количество информации. Сжатие информации.
- •Энтропия по Хартли.
- •Энтропия по Шеннону.
- •Математическая модель: алфавитное кодирование случайного источника.
- •Энтропия по Шеннону и энтропия по Хартли.
- •Свойства энтропии.
- •Алгоритмы кодирования
- •Алгоритм Шеннона (Фано).
- •Алгоритм Хаффмана
- •Блочное кодирование Хаффмена.
- •Замечание. О длине блока и сложности кодирования.
- •Блочное кодирование и теорема Шеннона.
- •Раздел 3. Передача информации. Защита от искажений.
- •Передача информации по каналу с шумом.
- •Передача информации по двоичному симметричному каналу с шумом
- •Корректирующие способности кодов. Границы мощности.
- •Теорема Шеннона для канала с шумом.
- •Факты из теории вероятности.
- •XI → канал → y
- •Вероятностное доказательство теоремы.
- •Комбинаторное доказательство теоремы.
- •Примеры кодов, исправляющих ошибки. Линейные коды.
- •Спектр кода.
- •Линейные коды.
- •Теорема об эквидистнантных кодах
- •Рекомендованная литература
Рекомендованная литература
Лидовский В.В. Теория информации: Уч. пособие. - М.: Компания Спутник+, 2004.
Потапов В.Н. Теория информации. Кодирование вероятностных источников.- Уч. пособие / Новосибирский государственный университет. -- Новосибирск, 1999.
Панин В.В. Основы теории информации: учебное пособие для вузов. - 3-е изд. испр. - М.: БИНОМ. Лаборатория знаний, 2009.
Кузьмин И.В. Основы теории информации и кодирования.- Электронный учебник. www.info.oglib.ru/bgl/4607.html.
У. Питерсон, Э. Уэлдон. Коды, исправляющие ошибки. – Мир, 1976.
Леонтьев В.К. Теория кодирования.- М., Знание, 1977.
Соловьева Ф.И. Введение в теорию кодирования. Уч. Пособие. – Новосибирск, 2006.
Гордеев Э.Н. Имя и информация. – В печати.
Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]