1. Цели освоения дисциплины
| 1.1. | Цель курса «Теория информации» состоит в освоении студентами основ теории информации и теории кодирования, а также в получении знаний о современных технологиях передачи и преобразования информации. Основными задачами курса являются: овладение фундаментальными знаниями по теории информации и теории кодирования; овладение технологиями кодирования и сжатия, восстановления и хранения информации; приобретение практических навыков реализации кодирующих и декодирующих алгоритмов. |
|---|
2. Место дисциплины в структуре ООП
| Цикл (раздел) ООП: Б1.О.06 |
3. Компетенции обучающегося, формируемые в результате освоения дисциплины
| ПК-3 | Владеет современными аналитическими системами обработки и визуализации данных, а также системами визуального и логического проектирования документов |
| ПК-3.1 | Знает принципы и технологии работы современных систем визуального и логического проектирования документов. |
| ПК-3.2 | Умеет представлять результаты научноисследовательской деятельности с использованием современных технологий. |
| ПК-3.3 | Владеет навыками работы с системами подготовки документации, а также аналитическими системами обработки и визуализации данных. |
| В результате освоения дисциплины обучающийся должен | |
| 3.1. | Знать: |
|---|---|
| 3.1.1. | основные понятия и теоремы теории информации и кодирования; основные принципы и способы кодирования и декодирования; характеристики кодов разного типа, понятие оптимального и помехоустойчивого кодирования; методы исследования кодов и их применений в ЭВМ и системах защиты информации. основные классы кодов, их параметры и алгоритмы кодирования/декодирования. |
| 3.2. | Уметь: |
| 3.2.1. | вычислять количество информации в сообщениях дискретного источника канала связи; кодировать и декодировать сообщения источника одним из изученных кодов, оценивать его оптимальность и помехоустойчивость; оценивать количество информации, вероятность ошибки на выходе канала связи и вероятность ошибочного декодирования; выбирать, реализовывать и применять кодирующие и декодирующие алгоритмы для различных классов задач. |
| 3.3. | Иметь навыки и (или) опыт деятельности (владеть): |
| 3.3.1. | навыками реализации кодирующих и декодирующих алгоритмов; навыками сравнительного анализа кодов и алгоритмов.основными. |
4. Структура и содержание дисциплины
| Код занятия | Наименование разделов и тем | Вид занятия | Семестр | Часов | Компетенции | Литература |
|---|---|---|---|---|---|---|
| Раздел 1. Основы теории информации и кодирования | ||||||
| 1.1. | Энтропия вероятностной схемы; аксиомы Хинчина и Фаддеева; условная энтропия; взаимная информация и ее свойства; | Лекции | 1 | 2 | Л2.2, Л1.3, Л1.1 | |
| 1.2. | Источники информации; энтропия источников; дискретный источник без памяти; теоремы Шеннона об источниках; марковские и эргодические источники; информационная дивергенция; граница Симмонса; | Лекции | 1 | 2 | Л1.3, Л2.3 | |
| 1.3. | Изучение леционного материала, основной и дополнительной литературы. | Сам. работа | 1 | 20 | Л1.3, Л2.3 | |
| Раздел 2. Оптимальное кодирование и сжатие данных | ||||||
| 2.1. | Оптимальное кодирование; префиксные коды; неравенство Крафта; линейные коды; параметры кодов и их границы; корректирующие свойства кодов; циклические коды; БЧХ - коды; код Хемминга; сверточные коды; математическая модель канала связи; пропускная способность канала связи; прямая и обратная теоремы кодирования. | Лекции | 1 | 3 | Л2.2, Л1.3, Л1.1, Л2.3 | |
| 2.2. | Шифрование подстановкой и раскрытие шифра методом частотного анализа. | Лабораторные | 1 | 2 | Л1.1 | |
| 2.3. | Кодирование методом Шеннона-Фано. | Лабораторные | 1 | 1 | Л1.1 | |
| 2.4. | Кодирование методом Хаффмана. | Лабораторные | 1 | 1 | Л1.1 | |
| 2.5. | Арифметическое кодирование. | Лабораторные | 1 | 2 | Л1.1 | |
| 2.6. | Словарные алгоритмы. Методы Лемпела-Зива. | Лекции | 1 | 1 | Л1.1 | |
| 2.7. | LZ-сжатие данных. Разновидности алгоритмов. Особенности реализации. | Лабораторные | 1 | 2 | Л1.1 | |
| 2.8. | Сжатие с потерями. Основные идеи, методы и форматы данных. | Лекции | 1 | 1 | Л1.3, Л1.1 | |
| 2.9. | Сжатие с потерями. Анализ распространенных современных форматов данных использующих сжатие с потерями. | Лабораторные | 1 | 2 | Л1.3, Л1.1 | |
| 2.10. | Основы методов фрактального сжатия. | Лекции | 1 | 2 | ||
| 2.11. | Работа с лекционным материалом, основной и дополнительной литературой. Выполнениие лабораторных работ. | Сам. работа | 1 | 20 | Л1.1 | |
| Раздел 3. Теоретические основы передачи данных | ||||||
| 3.1. | Сигналы с ограниченным спектром. Теорема Котельникова (Найквиста-Шеннона). | Лекции | 1 | 1 | Л1.1, Л1.2 | |
| 3.2. | Математическая модель канала связи. Емкость канала. Прямая и обратная теоремы кодирования. Предельные скорости передачи данных через канал без помех/с помехами. | Лекции | 1 | 1 | Л1.1, Л1.2 | |
| 3.3. | Временные и спектральные характеристики дискретных сигналов. Преобразование Фурье и вейвлет-преобразование. | Лекции | 1 | 1 | Л1.1, Л1.2 | |
| 3.4. | Работа с лекционным материалом, основной и дополнительной литературой. Выполнение лабораторных работ. | Сам. работа | 1 | 18 | Л1.1, Л1.2, Л2.3 | |
| Раздел 4. Помехоустойчивое кодирование и контроль ошибок | ||||||
| 4.1. | Помехоустойчивое кодирование. Основные подходы. Неравенство Крафта-Макмиллана. | Лекции | 1 | 2 | Л1.1, Л1.2, Л2.3 | |
| 4.2. | Матричное кодирование. Групповые коды. Совершенные и квазисовершенные коды. Код Хемминга. | Лекции | 1 | 1 | Л1.1, Л1.2, Л2.3 | |
| 4.3. | Полиномиальные коды. Коды БЧХ. Коды Рида-Соломона. Циклические избыточные коды. | Лекции | 1 | 1 | Л1.1, Л1.2, Л2.3 | |
| 4.4. | Сверточные коды. Турбо-коды. | Лекции | 1 | 1 | Л1.1, Л1.2, Л2.3 | |
| 4.5. | Помехоустойчивое кодирование (особенности реализации алгоритмов). | Лабораторные | 1 | 2 | Л1.1, Л1.2 | |
| 4.6. | Основные положения квантовой теории информации. Квантовые компьютеры. Квантовые алгоритмы. Квантовая криптография. | Лекции | 1 | 1 | Л1.3, Л2.1 | |
| 4.7. | Работа с лекционным материалом, основной и дополнительной литературой. Выполнение лабораторных работ. | Сам. работа | 1 | 18 | Л1.3, Л1.1, Л1.2, Л2.1 | |
5. Фонд оценочных средств
| 5.1. Контрольные вопросы и задания для проведения текущего контроля и промежуточной аттестации по итогам освоения дисциплины |
| Примеры вопросов закрытого типа 1. Чему равен объем данных, необходимый для кодирования результата бросания игральной кости? а. log_2(6) бит б. 2 бита в. 3 бита г. 6 бит Ответ в. 2. Чему в вероятностном подходе равно количество информации, получаемое в результате бросания игральной кости? а. log_2(6) бит б. 2 бита в. 3 бита г. 6 бит Ответ а. 3. Выберите утверждение, наиболее точно отражающее смысл основной теоремы о кодировании при отсутствии помех (первой теоремы Шеннона). а. Максимальная скорость передачи данных по каналу связи равна логарифму отношения сигнал/шум. б. При кодировании любой дискретной случайной величины существует такой алгоритм кодирования, при котом объем данных по крайней мере в 2 раза меньше энтропии этой этой дискретной случайной величины в. Количество информации не может быть меньше 1 бита. г. Среднее количество бит,приходящихся наодно кодируемое значение дискретной случайной величины, не может быть меньшим, чем энтропия этой дискретной случайной величины Ответ г. 4. В чем ключевое отличие алгоримтма Шеннона-Фано от алгоритмя Хаффмана а. Алгоритмя Шеннона-Фано всегдя уступает алгоритму Хаффмана, т.к. последний является однопроходным и не требует априорного знанния распределения кодируемой случайной величины б. Алгоритм Шеннона-Фано основан на построении бинарного дерева кодирования, а алгоритм Хаффмана - сильно ветвящегося дерева в. Дерево кодирования в алгоримне Шеннона-Фано строится от листьев к корню, а в алгоритме Хаффмана - от корня к листьям г. Дерево кодирования в алгоримне Шеннона-Фано строится от корня к листьям, а в алгоритме Хаффмана - от листьев к корню Ответ г. 5. В чем ключевое отличие адаптивных алгоритмов сжатия от неадаптивных? а. Адаптивный алгоритм является однопроходным и не требует предварительного анализа или априорного знания статистических характеистики данных б. Адаптивный алгоритм сжимает данные без потерь в. Адаптивный алгоритм работает только с текстовыми данными г. Адаптивный метод адаптируется к типу данных (числовые, текст, мультимедиа...) Ответ а. 6. Какой из алгоритмов сжатия данных принципиально позволяет добиться среденего значения объема данных на одну единицу сообщения менее 1 бита? а. Арифметическое кодирование б. Алгоритм Хаффмана в. Алгоритм Шеннона-Фано г. Алгоритм LZW Ответ а. 7. Какой тип алгоритмов обычно является предпочтительным (более практичным, быстрым при сравнимаой эффективности) для кодирование текстов? а. Алгоритм Хаффмана б. Арифметическое кодирование в. Словарные аллгоритмы г. Хеширование Ответ в. 8. Каков основной принцип помехоустойчивого кодирования? а. Добавление к данным избыточности, которая используется для выявления и коррекции ошибок б. Сжатие данных с потерями для уменшения вероятности ошибок в. Уменшение уровня шума в канале связи г. Повышение скорости передачи данных Ответ а. 9. Для каких данных применяется сжатие с потерями а. Данные, заведомо имеющие избыточность с точки зрения практического использования (например, мультимедиа - графика, звук, видео) б. Данные, избыточные по причине большого количества ошибок в. Любые данные большого объема, не позволяющего обеспечить их эффективное хранение и передачу г. Только текстовые данные в кодировках семейства Unicode Ответ а. 10. Минимальное расстояние между кодовыми словами 2k+1 обеспечивает: а. Обнаружение ошибок кратности k и менее б. Обнаружение ошибок кратности 2k и менее в. Коррекцию ошибок кратности 2k и менее г. Коррекцию ошибок кратности k и менее Ответ г. 11. Минимальное расстояние между кодовыми словами k+1 обеспечивает: а. Обнаружение ошибок кратности k и менее б. Обнаружение ошибок кратности 2k и менее в. Коррекцию ошибок кратности 2k и менее г. Коррекцию ошибок кратности k и менее Ответ а. 12. Для чего применяется код Хемминга? а. Для коррекции одиночной ошибки и установления факта двойной ошибки. б. Для сжатия видео в. Для коррекции n ошибок в n^2 бит данных г. Для обнаружения многочисленных кратных ошибок в больших объхемах данных Ответ а. 13. Для чего применяются циклические избыточные коды? а. Для проверки целостности данных (обнаружения ошибок) б. Для коррекции ошибок в небольших блоках в. Как аналог электронной цифровой подписи в отсуствие независимого удостоверяющего центра г. Для генерации уникальных идентификаторов Ответ в. 14. Сигнал – это а. изменяющаяся во времени физический процесс б. выделенный бит данных, принимающй одно из двух возможных значений - 0 или 1 в. данные, закодированные в двоичном цифровом коде г. данные, хранящиеся в виде десятичных числовых значений Ответ а. 15. Данные - это а. Последовательности символов из заранее определенного набора б. Зарегистрированные сигналы вне зависимости от способа и формы их кодирования в. Последовательности чисел, записанные в двоичном цифрорвом коде г. Система знаков и условных обозначений, применяемая при кодирования Ответ б. |
| 5.2. Темы письменных работ для проведения текущего контроля (эссе, рефераты, курсовые работы и др.) |
| Изучение и сравнительный анализ формата WebP. Изучение и сравнительный анализ формата WebM. Применение вейвлет-переобразований при сжатии данных с потерями. Фрактальное сжатие изображений. Основы квантовой теории информации. Квантовые алгоритмы. Основы технологии "Блокчейн" |
| 5.3. Фонд оценочных средств для проведения промежуточной аттестации |
| См. прилагаемый файл. |
| Приложения |
6. Учебно-методическое и информационное обеспечение дисциплины
| 6.1. Рекомендуемая литература | ||||
| 6.1.1. Основная литература | ||||
| Авторы | Заглавие | Издательство, год | Эл. адрес | |
| Л1.1 | Иордан В.И., Гуляев П.Ю. | Основы теории информации и кодирования: учеб. пособие : | Барнаул : Изд-во АлтГУ, 2004 | |
| Л1.2 | Сидельников В. М. | Теория кодирования: | М.: Физматлит, 2008 | biblioclub.ru |
| Л1.3 | Балюкевич Э.Л. | Теория информации: Учебно-методический комплекс | М.: Евразийский открытый институт // ЭБС "ONLINE", 2009 | biblioclub.ru |
| 6.1.2. Дополнительная литература | ||||
| Авторы | Заглавие | Издательство, год | Эл. адрес | |
| Л2.1 | Хренников А. Ю. | Введение в квантовую теорию информации: | М.: Физматлит, 2008 | e.lanbook.com |
| Л2.2 | Ю. Н. Мальцев, Е. П. Петров | Элементы дискретной математики: Элементы комбинаторики, теории графов, теории кодирования и криптографии: [учеб. пособие] | Барнаул: Изд-во АлтГУ, 2004 | |
| Л2.3 | Чечёта С. И. | Введение в дискретную теорию информации и кодирования: | М.: МЦНМО, 2011 | biblioclub.ru |
| 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 | ||
| 6.3. Перечень программного обеспечения | ||||
| Компилятор языка прграммирования высокого уровня и среда разработки.Microsoft Office 2010 (Office 2010 Professional, № 4065231 от 08.12.2010), (бессрочно); Microsoft Windows 7 (Windows 7 Professional, № 61834699 от 22.04.2013), (бессрочно); Chrome (http://www.chromium.org/chromium-os/licenses), (бессрочно); 7-Zip (http://www.7-zip.org/license.txt), (бессрочно); AcrobatReader (http://wwwimages.adobe.com/content/dam/Adobe/en/legal/servicetou/Acrobat_com_Additional_TOU-en_US-20140618_1200.pdf), (бессрочно); ASTRA LINUX SPECIAL EDITION (https://astralinux.ru/products/astra-linux-special-edition/), (бессрочно); LibreOffice (https://ru.libreoffice.org/), (бессрочно); Веб-браузер Chromium (https://www.chromium.org/Home/), (бессрочно); Антивирус Касперский (https://www.kaspersky.ru/), (до 23 июня 2024); Архиватор Ark (https://apps.kde.org/ark/), (бессрочно); Okular (https://okular.kde.org/ru/download/), (бессрочно); Редактор изображений Gimp (https://www.gimp.org/), (бессрочно) | ||||
| 6.4. Перечень информационных справочных систем | ||||
7. Материально-техническое обеспечение дисциплины
| Аудитория | Назначение | Оборудование |
|---|---|---|
| Учебная аудитория | для проведения занятий лекционного типа, занятий семинарского типа (лабораторных и(или) практических), групповых и индивидуальных консультаций, текущего контроля и промежуточной аттестации, курсового проектирования (выполнения курсовых работ), проведения практик | Стандартное оборудование (учебная мебель для обучающихся, рабочее место преподавателя, доска) |
| Помещение для самостоятельной работы | помещение для самостоятельной работы обучающихся | Компьютеры, ноутбуки с подключением к информационно-телекоммуникационной сети «Интернет», доступом в электронную информационно-образовательную среду АлтГУ |
| 001вК | склад экспериментальной мастерской - помещение для хранения и профилактического обслуживания учебного оборудования | Акустический прибор 01021; виброизмеритель 00032; вольтметр Q1202 Э-500; вольтметр универсальный В7-34А; камера ВФУ -1; компьютер Турбо 86М; масспектрометр МРС -1; осциллограф ЕО -213- 2 ед.; осциллограф С1-91; осциллограф С7-19; программатор С-815; самописец 02060 – 2 ед.; стабилизатор 3218; терц-октавный фильтр 01023; шкаф вытяжной; шумомер 00026; анализатор АС-817; блок 23 Г-51; блок питания "Статрон" – 2 ед.; блок питания Ф 5075; вакуумный агрегат; весы; вольтметр VM -70; вольтметр В7-15; вольтметр В7-16; вольтметр ВУ-15; генератор Г-5-6А; генератор Г4-76А; генератор Г4-79; генератор Г5-48; датчик колебаний КВ -11/01; датчик колебаний КР -45/01; делитель Ф5093; измеритель ИМП -2; измеритель параметров Л2-12; интерферометр ИТ 51-30; источник "Агат" – 3 ед.; источник питания; источник питания 3222; источник питания ЭСВ -4; лабораторная установка для настройки газовых лазеров; лазер ЛГИ -21; М-кальк-р МК-44; М-калькул-р "Электроника"; магазин сопротивления Р4075; магазин сопротивления Р4077; микроскоп МБС -9; модулятор МДЕ; монохроматор СДМС -97; мост переменного тока Р5066; набор цветных стекол; насос вакумный; насос вакуумный ВН-01; осциллограф С1-31; осциллограф С1-67; осциллограф С1-70; осциллограф С1-81; осциллоскоп ЕО -174В – 2 ед.; пентакта L-100; пирометр "Промень"; пистонфон 05001; преобразователь В9-1; прибор УЗДН -2Т; скамья оптическая СО 1м; спектограф ДФС -452; спектограф ИСП -51; стабилизатор 1202; стабилизатор 3217 – 4 ед.; стабилизатор 3218; стабилизатор 3222 – 3 ед.; станок токарный ТВ-4; усилитель мощности ЛВ -103 – 4 ед.; усилитель У5-9; центрифуга ВЛ-15; частотомер Ч3-54А; шкаф металлический; эл.двигатель; электродинамический калибратор 11032 |
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. Помехоустойчивое кодирование. Реализовать один из рассмотренных алгоритмов помехо-устойчивого кодирования. Продемонстрировать на при-мерах преимущества и недостатки использованного ал-горитма. Цель самостоятельной работы - систематизация, закрепление и расширение теоретических и практических знаний с использованием современных информационных технологий и литературных источников. Самостоятельная работа включает: работу с лекционным материалом, основной и дополнительной литературой, Интернет-ресурсами, выполнение и подготовку отчетов по лабораторным работам, выполнение итоговых индивидуальных заданий. |