МИНОБРНАУКИ РОССИИ

федеральное государственное бюджетное образовательное учреждение высшего образования
«Алтайский государственный университет»

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

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

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

Часов по учебному плану	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 Информационная безопасность
утвержденного учёным советом вуза от 25.06.2019 протокол № 9.

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

Протокол от 06.06.2019 г. № 9/2018-19
Срок действия программы: 2019-2020 уч. г.

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

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

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

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

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

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

1.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.
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. Помехоустойчивое кодирование.
Реализовать один из рассмотренных алгоритмов помехо-устойчивого кодирования. Продемонстрировать на при-мерах преимущества и недостатки использованного ал-горитма.

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