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 | 22 | ОПК-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 | 10 | ОПК-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. Чему равен объем данных, необходимый для кодирования результата бросания игральной кости? а. 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. Данные - это а. Последовательности символов из заранее определенного набора б. Зарегистрированные сигналы вне зависимости от способа и формы их кодирования в. Последовательности чисел, записанные в двоичном цифрорвом коде г. Система знаков и условных обозначений, применяемая при кодирования Ответ б. Примеры вопросов открытого типа 1. Чем отличаются понятия информации и данных? Данные - это зарегистрированные сигналы, информация - более сложное понятие, технически сводящееся к результату содержательной обработке данных и снятию неопределенности. 2. Какой из типов алгоритмов сжатия без потерь является наиболее строго математически обусловленным? Статистические алгоритмы. 3. Какое количество ошибок позволяет обнаружить линейный корректирующий код с минимальным расстоянием Хемминга 5? Ответ 4. 4. Какое количество ошибок позволяет исправить линейный корректирующий код с минимальным расстоянием Хемминга 5? Ответ 2. 5. Что произойдет, если вес вектора ошибки (количество ошибок в кодовом слове) равен минимальному кодовому расстоянию, а сам вектор ошибки совпадает с одним из разрешенных кодовых слов? Пропуск ошибки. 6. Что произойдет, если вес вектора ошибки (количество ошибок в кодовом слове) не превышает половины величины минимального кодового расстояния? Обнаружение и правильное автоматическое исправление ошибки 7. Как называется вид кодирования, использующий избыточное количество информации с целью последующего контроля целостности данных при записи/воспроизведении информации или при её передаче по линиям связи? Избыточное кодирование 8. Какое количество ошибок можно выявить при помощи бита четности? Одну или любое нечетное количество. 9. Как называется метрика различия строк одинаковой размерности? Расстояние Хемминга 10. Какие два метода применяются при избыточном кодировании? Блочное и сверточное. 11. Какой из алгоритмов сжатия без потерь потенциально способен обеспечить среднее количество бит на единицу сообщение, меньшее 1? Арифметическое кодирование. 12. К одому и тому же набору данных применили адаптивный и неадаптивный алгоритмы сжатия. Какой из них быстрее? Неадаптивный 12. К одому и тому же набору данных применили адаптивный и неадаптивный алгоритмы сжатия. Какой из них приведет к лучшему сжатию? Неадаптивный 13. Как раскрыть шифрование методом простой замены? Частотным анализом 14. Сколько ошибок исправляет код Хемминга 1 15. Для чего существуют БЧХ-коды? Для построения кодов с заранее заданными корректирующими характеристиками и минимально йизбыточностью. 16. Какой вид данных, как правило, на практике сжимается с потерями? Мультимедиа, заведомо избыточный 17. Чем отличаются принципиально алгоритмы сжатия jpeg и png? Jpeg сжимает за счет отказа от разрешающей способности, png - от цветовой глубины и эффективного кодировани яповторяющихся последовательностей 18. Назовите открытый векторынй графический формат. SVG 19. Какой тип графического формата следует предпочесть при кодировании схем, диаграм, графиков функций? Векторый 20. В каком случае энтропия информации, связанной со случайной величиной, равна 0? если случайная величина - константа (принимает единственное возможно езначение с вероятностью 1) |
| 5.2. Темы письменных работ для проведения текущего контроля (эссе, рефераты, курсовые работы и др.) |
| Изучение и сравнительный анализ формата WebP. Изучение и сравнительный анализ формата WebM. Применение вейвлет-переобразований при сжатии данных с потерями. Фрактальное сжатие изображений. Основы квантовой теории информации. Квантовые алгоритмы. Основы технологии "Блокчейн" |
| 5.3. Фонд оценочных средств для проведения промежуточной аттестации |
| См. прилагаемый файл. |
| Приложения |
|
Приложение 1.
ФОС Теория информации ИБ (1).docx
|
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. Перечень программного обеспечения | ||||
| Компилятор языка программирования высокого уровня и среда разработки. 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. Материально-техническое обеспечение дисциплины
| Аудитория | Назначение | Оборудование |
|---|---|---|
| Помещение для самостоятельной работы | помещение для самостоятельной работы обучающихся | Компьютеры, ноутбуки с подключением к информационно-телекоммуникационной сети «Интернет», доступом в электронную информационно-образовательную среду АлтГУ |
| Учебная аудитория | для проведения занятий лекционного типа, занятий семинарского типа (лабораторных и(или) практических), групповых и индивидуальных консультаций, текущего контроля и промежуточной аттестации, курсового проектирования (выполнения курсовых работ), проведения практик | Стандартное оборудование (учебная мебель для обучающихся, рабочее место преподавателя, доска) |
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. Помехоустойчивое кодирование. Реализовать один из рассмотренных алгоритмов помехо-устойчивого кодирования. Продемонстрировать на при-мерах преимущества и недостатки использованного ал-горитма. Цель самостоятельной работы - систематизация, закрепление и расширение теоретических и практических знаний с использованием современных информационных технологий и литературных источников. Самостоятельная работа включает: работу с лекционным материалом, основной и дополнительной литературой, Интернет-ресурсами, выполнение и подготовку отчетов по практическим работам, выполнение итоговых индивидуальных заданий. |