МИНОБРНАУКИ РОССИИ
федеральное государственное бюджетное образовательное учреждение высшего образования
«Алтайский государственный университет»

Теория информации

рабочая программа дисциплины
Закреплена за кафедройКафедра радиофизики и теоретической физики
Направление подготовки10.03.01. Информационная безопасность
ПрофильБезопасность автоматизированных систем (в сфере профессиональной деятельности)
Форма обученияОчная
Общая трудоемкость3 ЗЕТ
Учебный план10_03_01_ИБ-2-2020
Часов по учебному плану 108
в том числе:
аудиторные занятия 36
самостоятельная работа 72
Виды контроля по семестрам
зачеты: 5

Распределение часов по семестрам

Курс (семестр) 3 (5) Итого
Недель 19
Вид занятий УПРПДУПРПД
Лекции 18 18 18 18
Практические 18 18 18 18
Сам. работа 72 72 72 72
Итого 108 108 108 108

Программу составил(и):
к.ф.-м.н., доцент кафедры радиофизики и теоретической физики, Райкин Роман Ильич

Рецензент(ы):
к.ф.-м.н., доцент кафедры прикладной физики, электроники и информационной безопасности, Рудер Давыд Давыдыч

Рабочая программа дисциплины
Теория информации

разработана в соответствии с ФГОС:
Федеральный государственный образовательный стандарт высшего образования по направлению подготовки 10.03.01 ИНФОРМАЦИОННАЯ БЕЗОПАСНОСТЬ (уровень бакалавриата) (приказ Минобрнауки России от 01.12.2016г. №1515)

составлена на основании учебного плана:
10.03.01 Информационная безопасность
утвержденного учёным советом вуза от 30.06.2020 протокол № 6.

Рабочая программа одобрена на заседании кафедры
Кафедра радиофизики и теоретической физики

Протокол от 15.06.2020 г. № 9
Срок действия программы: 2020-2021 уч. г.

Заведующий кафедрой
д.ф.-м.н., профессор Лагутин Анатолий Алексеевич


Визирование РПД для исполнения в очередном учебном году

Рабочая программа пересмотрена, обсуждена и одобрена для
исполнения в 2020-2021 учебном году на заседании кафедры

Кафедра радиофизики и теоретической физики

Протокол от 15.06.2020 г. № 9
Заведующий кафедрой д.ф.-м.н., профессор Лагутин Анатолий Алексеевич


1. Цели освоения дисциплины

1.1.Цель курса «Теория информации» состоит в освоении студентами основ теории информации и теории кодирования, а также в получении знаний о современных технологиях передачи и преобразования информации.
Основными задачами курса являются:
овладение фундаментальными знаниями по теории информации и теории кодирования;
овладение технологиями кодирования и сжатия, восстановления и хранения информации;
приобретение практических навыков реализации кодирующих и декодирующих алгоритмов.

2. Место дисциплины в структуре ООП

Цикл (раздел) ООП: Б1.Б.02

3. Компетенции обучающегося, формируемые в результате освоения дисциплины

ОПК-4 способностью понимать значение информации в развитии современного общества, применять информационные технологии для поиска и обработки информации
В результате освоения дисциплины обучающийся должен
3.1.Знать:
3.1.1.основные понятия и теоремы теории информации и кодирования;
основные принципы и способы кодирования и декодирования;
характеристики кодов разного типа, понятие оптимального и помехоустойчивого кодирования;
методы исследования кодов и их применений в ЭВМ и системах защиты информации.
основные классы кодов, их параметры и алгоритмы кодирования/декодирования.
3.2.Уметь:
3.2.1.вычислять количество информации в сообщениях дискретного источника канала связи;
кодировать и декодировать сообщения источника одним из изученных кодов, оценивать его оптимальность и помехоустойчивость;
оценивать количество информации, вероятность ошибки на выходе канала связи и вероятность ошибочного декодирования;
выбирать, реализовывать и применять кодирующие и декодирующие алгоритмы для различных классов задач.
3.3.Иметь навыки и (или) опыт деятельности (владеть):
3.3.1.основными методами кодирования и декодирования информации для различных задач.

4. Структура и содержание дисциплины

Код занятия Наименование разделов и тем Вид занятия Семестр Часов Компетенции Литература
Раздел 1. Основы теории информации и кодирования
1.1. Энтропия вероятностной схемы; аксиомы Хинчина и Фаддеева; условная энтропия; взаимная информация и ее свойства; Лекции 5 2 ОПК-4 Л2.2, Л1.2, Л1.1
1.2. Источники информации; энтропия источников; дискретный источник без памяти; теоремы Шеннона об источниках; марковские и эргодические источники; информационная дивергенция; граница Симмонса; Лекции 5 2 ОПК-4 Л1.2, Л2.1, Л1.1
1.3. Изучение леционного материала, основной и дополнительной литературы. Сам. работа 5 12 ОПК-4 Л1.2, Л2.1, Л1.1
Раздел 2. Оптимальное кодирование и сжатие данных
2.1. Оптимальное кодирование; префиксные коды; неравенство Крафта; линейные коды; параметры кодов и их границы; корректирующие свойства кодов; циклические коды; БЧХ - коды; код Хемминга; сверточные коды; математическая модель канала связи; пропускная способность канала связи; прямая и обратная теоремы кодирования. Лекции 5 2 ОПК-4 Л2.2, Л1.2, Л2.1, Л1.1
2.2. Шифрование подстановкой и раскрытие шифра методом частотного анализа. Практические 5 2 ОПК-4 Л2.3, Л1.1
2.3. Кодирование методом Шеннона-Фано. Практические 5 2 ОПК-4 Л2.3, Л1.1
2.4. Кодирование методом Хаффмана. Практические 5 2 ОПК-4 Л2.3, Л1.1
2.5. Арифметическое кодирование. Практические 5 2 ОПК-4 Л2.3, Л1.1
2.6. Словарные алгоритмы. Методы Лемпела-Зива. Лекции 5 2 ОПК-4 Л2.3, Л1.1
2.7. LZ-сжатие данных. Разновидности алгоритмов. Особенности реализации. Практические 5 4 ОПК-4 Л2.3, Л1.1
2.8. Сжатие с потерями. Основные идеи, методы и форматы данных. Лекции 5 2 ОПК-4 Л1.2, Л2.3, Л1.1
2.9. Сжатие с потерями. Анализ распространенных современных форматов данных использующих сжатие с потерями. Практические 5 4 ОПК-4 Л1.2, Л2.3, Л1.1
2.10. Основы методов фрактального сжатия. Лекции 5 2 ОПК-4
2.11. Работа с лекционным материалом, основной и дополнительной литературой. Выполнениие практических работ. Сам. работа 5 20 ОПК-4 Л2.3, Л1.1
Раздел 3. Теоретические основы передачи данных
3.1. Сигналы с ограниченным спектром. Теорема Котельникова (Найквиста-Шеннона). Математическая модель канала связи. Емкость канала. Прямая и обратная теоремы кодирования. Предельные скорости передачи данных через канал без помех/с помехами. Временные и спектральные характеристики дискретных сигналов. Преобразование Фурье и вейвлет-преобразование. Лекции 5 2 ОПК-4 Л2.3, Л1.1
3.2. Работа с лекционным материалом, основной и дополнительной литературой. Выполнение лабораторных работ. Сам. работа 5 20 ОПК-4 Л2.1, Л2.3, Л1.1
Раздел 4. Помехоустойчивое кодирование и контроль ошибок
4.1. Помехоустойчивое кодирование. Основные подходы. Неравенство Крафта-Макмиллана.Матричное кодирование. Групповые коды. Совершенные и квазисовершенные коды. Код Хемминга. Полиномиальные коды. Коды БЧХ. Коды Рида-Соломона. Циклические избыточные коды. Сверточные коды. Турбо-коды. Лекции 5 2 ОПК-4 Л2.1, Л1.1
4.2. Помехоустойчивое кодирование (особенности реализации алгоритмов). Практические 5 2 ОПК-4 Л2.3, Л1.1
4.3. Основные положения квантовой теории информации. Квантовые компьютеры. Квантовые алгоритмы. Квантовая криптография. Лекции 5 2 ОПК-4 Л1.2
4.4. Работа с лекционным материалом, основной и дополнительной литературой. Выполнении лабораторных работ. Сам. работа 5 20 ОПК-4 Л1.2, Л2.3, Л1.1

5. Фонд оценочных средств

5.1. Контрольные вопросы и задания для проведения текущего контроля и промежуточной аттестации по итогам освоения дисциплины
1. Общефизические основы теории информации. Термодинамика и энтропия. Информация, содержащаяся в экспериментальных данных и теоретическом законе.
2. Информация и данные. Кодирование. Цифровые коды. Понятие об экономичном кодировании.
3. Вероятностный подход к измерению количества информации. Энтропия Шеннона. Семантическая информация.
4. Взаимная информация и информационная дивергенция. Энтропия источников. Теоремы Шеннона об источниках.
1. Кодирование Шеннона-Фэно.
2. Кодирование Хаффмана.
3. Арифметическое кодирование.
4. Адаптивные алгоритмы.
5. Методы Лемпела-Зива.
6. Сжатие с потерями. Основные методы и форматы данных.
7. Основы методов фрактального сжатия.
8. Сигналы с ограниченным спектром. Теорема Котельникова (Найквиста-Шеннона).
9. Математическая модель канала связи. Емкость канала. Прямая и обратная теоремы кодирования. Предельные скорости передачи данных через канал без помех/с помехами.
10. Временные и спектральные характеристики дискретных сигналов. Преобразование Фурье и вейвлет-преобразование.
11. Помехоустойчивое кодирование. Неравенство Крафта-Макмиллана.
12. Матричное кодирование.
13. Групповые коды. Совершенные и квазисовершенные коды.
14. Код Хемминга.
15. Полиномиальные коды.
16. Коды Боуза-Чоудхури-Хоккенгема. Коды Рида-Соломона.
17. Циклические избыточные коды.
18. Сверточные коды.
19. Турбо-коды.
20. Основные положения квантовой теории информации. Квантовые компьютеры. Квантовые алгоритмы. Квантовая криптография.
21. Основы технологии "Блокчейн"
5.2. Темы письменных работ для проведения текущего контроля (эссе, рефераты, курсовые работы и др.)
Изучение и сравнительный анализ формата WebP.
Изучение и сравнительный анализ формата WebM.
Применение вейвлет-переобразований при сжатии данных с потерями.
Фрактальное сжатие изображений.
Основы квантовой теории информации. Квантовые алгоритмы.
Основы технологии "Блокчейн"
5.3. Фонд оценочных средств для проведения промежуточной аттестации
См. прилагаемый файл.

6. Учебно-методическое и информационное обеспечение дисциплины

6.1. Рекомендуемая литература
6.1.1. Основная литература
Авторы Заглавие Издательство, год Эл. адрес
Л1.1 В.В. Лидовский Основы теории информации и криптографии : курс: Национальный Открытый Университет "ИНТУИТ". - Москва : Интернет-Университет Информационных Технологий, 2007 // ЭБС "Университетская библиотека online" biblioclub.ru
Л1.2 Балюкевич Э.Л. Теория информации: Учебно-методический комплекс М.: Евразийский открытый институт // ЭБС "ONLINE", 2009 biblioclub.ru
6.1.2. Дополнительная литература
Авторы Заглавие Издательство, год Эл. адрес
Л2.1 Чечёта С. И. Введение в дискретную теорию информации и кодирования: М.: МЦНМО, 2011 biblioclub.ru
Л2.2 Ю. Н. Мальцев, Е. П. Петров Элементы дискретной математики: Элементы комбинаторики, теории графов, теории кодирования и криптографии: [учеб. пособие] Барнаул: Изд-во АлтГУ, 2004
Л2.3 Литвинская О.С., Чернышев Н.И. Основы теории передачи нформации: М.: КноРус, 2017
6.2. Перечень ресурсов информационно-телекоммуникационной сети "Интернет"
Название Эл. адрес
Э1 В.В. Лидовский. Теория информации. [Электронный ресурс]: Московский центр непрерывного математического образования. Режим доступа: http://www.mccme.ru/free-books/izdano/2004/it_ebook1.pdf 10.10.2011.
Э2 Все о сжатии данных, изображений и видео. [Электронный ресурс]. Режим доступа: http://www.compression.ru 10.10.2012.
Э3 Курс на Едином образовательном портале АлтГУ portal.edu.asu.ru
Э4 Курс "Автоматические инструменты измерений и методы анализа данных" online.edu.ru
6.3. Перечень программного обеспечения
Компилятор языка программирования высокого уровня и среда разработки.
6.4. Перечень информационных справочных систем

7. Материально-техническое обеспечение дисциплины

Аудитория Назначение Оборудование
Учебная аудитория для проведения занятий лекционного типа, занятий семинарского типа (лабораторных и(или) практических), групповых и индивидуальных консультаций, текущего контроля и промежуточной аттестации, курсового проектирования (выполнения курсовых работ), проведения практик Стандартное оборудование (учебная мебель для обучающихся, рабочее место преподавателя, доска)
Помещение для самостоятельной работы помещение для самостоятельной работы обучающихся Компьютеры, ноутбуки с подключением к информационно-телекоммуникационной сети «Интернет», доступом в электронную информационно-образовательную среду АлтГУ

8. Методические указания для обучающихся по освоению дисциплины

Практические занятия нацелены на приобретение навыков выбора и реализации кодирующих и декодирующих алгоритмов.
При выполнении практических заданий и итоговых индивидуальных заданий используются электронные учебно-методические материалы по курсу, размещенные на образовательном портале АлтГУ (http://http://portal.edu.asu.ru)

Перечень тем, выносимых на практические занятия.
1. Шифрование подстановкой и раскрытие шифра методом частотного анализа.
2. Кодирование методом Шеннона-Фано.
3. Кодирование методом Хаффмана.
4. Арифметическое кодирование.
5. LZ-сжатие данных. Разновидности алгоритмов. Особенности реали-зации.
6. Сжатие с потерями. Анализ распространенных современных форматов данных использующих сжатие с потерями.
7. Помехоустойчивое кодирование (особенности реализации алгоритмов).

Планы практических занятий и методические рекомендации по подготовке к ним
1. Шифрование подстановкой и раскрытие шифра методом ча-стотного анализа.
Продемонстрировать уязвимость "шифра простой заме-ны" по отношению к частотному анализу.
Выполнитиь частотный анализ открытого текста_1 (не менее 100 тыс. знаков). Выполнить шифрование простой заменой текста_2 (не менее 100 тыс. знаков). Выполнить частотный анализ шифротекста_2. Сопоставив результа-ты частотного анализа, восстановить ключ (таблицу под-становки). С использованием восстановленного ключа расшифровать случайно выбранную строку шифротекста_2.
2. Кодирование методом Шеннона-Фано.
Выполнить сжатие данных методом Шеннона-Фано. Продемонстрировать на примерах преимущества и недостат-ки использованного алгоритма.
3. Кодирование методом Хаффмана.
Выполнить сжатие данных методом Хаффмана. Продемонстрировать на примерах преимущества и недостатки использованного алгоритма.
4. Арифметическое кодирование
Выполнить арифметическое кодирование. В случае, если в предыдущей работе был использован неадаптивный ме-тод Хаффмана, применить адаптивное арифметическое кодирование. Продемонстрировать на примерах пре-имущества и недостатки использованного алгоритма.
5. LZ-сжатие данных.
Выполнить сжатие данных при помощи словарно-ориентированного алгоритма (конкретную версию выбрать самостоятельно). Продемонстрировать на примерах преимущества и недостатки использованного алго-ритма.
6. Код Хемминга
Реализовать (7,4) и (9,5) коды Хемминга. Выполнить сравнительный анализ избыточности и корректирующей мощности кодов.
7. Помехоустойчивое кодирование.
Реализовать один из рассмотренных алгоритмов помехо-устойчивого кодирования. Продемонстрировать на при-мерах преимущества и недостатки использованного ал-горитма.

Цель самостоятельной работы - систематизация, закрепление и расширение теоретических и практических знаний с использованием современных информационных технологий и литературных источников.
Самостоятельная работа включает: работу с лекционным материалом, основной и дополнительной литературой, Интернет-ресурсами, выполнение и подготовку отчетов по практическим работам, выполнение итоговых индивидуальных заданий.