Information Theory

2019/2020

Academic Year

RUS

Instruction in Russian

4

ECTS credits

Delivered at:

Department of Informatics

Course type:

Elective course

When:

3 year, 3 module

Instructor

Bliznets, Ivan

Программа дисциплины

Аннотация

Является дисциплиной по выбору. Данная дисциплина направлена на овладение знаниями и алгоритмами в области теории информации. Курс посвящён изучению подходов к определению понятия „количество информации“. В курсе будет рассмотрено три подхода к определению „количества информации“: комбинаторный (информация по Хартли), вероятностный (энтропия Шеннона) и алгоритмический (Колмогоровская сложность). Кроме этого, мы поговорим про различные применения аппарата теории информации в различных областях компьютерных наук: в криптографии, в коммуникационной сложности, в теории кодирования, в теории конечных автоматов, в теории сложности вычислений и некоторых других. В результате освоения дисциплины студент должен:  знать определение количества информации;  уметь применять базовые алгоритмы из области теории кодирования и криптографии;  владеть математическим аппаратом необходимым для разработки и использования алгоритмов в теории кодирования, в теории конечных автоматов, в теории сложности вычислений

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

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

Планируемые результаты обучения

• Владеет понятием информация по Хартли: Мотивация и определение, информация в проекциях, игра в 10 вопросов, цена информации, упорядочение камней по весу, поиск фальшивой монетки (разные вариации), логика знаний. Владеет понятием энтропия Шеннона: мотивация и определение, свойства энтропии, энтропия пары, условная энтропия, взаимная информация, применение энтропии к задаче о поиске фальшивой монетки.
• Знает основную терминологию, применяемую в области теории информации: однозначно декодируемые коды, неравенство Крафта-Макмилана, префиксные коды, теоремы Шеннона об однозначно декодируемых кодах, код Шеннона-Фано, код Хаффмана, блоковое кодирование, арифметическое кодирование,теоремы Шеннона о блоковом кодировании с ошибками.
• Знает различные методы представления теории информации. Умеет оценивать количество информации и давать оценку сложности. Владеет навыками работы с энтропией и сложностью. Знает понятие сложности и энтропии. Находит коммуникационную и формульную сложность булевых функций. Владеет навыками применения Kолмогоровской сложности.

Содержание учебной дисциплины

• Информация по Хартли. Энтропия Шеннона.
• Кодирование. Теория информации в криптографии.
• Коммуникационная сложность и формульная сложность булевых функций. Колмогоровская сложность. Применение Kолмогоровской сложности.

Элементы контроля

• Домашнее задание
• Письменный экзамен
  Экзамен проводится на платформе Zoom. Экзамен проводится в устной форме (опрос по материалам курса). По просьбе преподавателя студент должен быть готов выполнить некоторые задания в письменном виде, после чего сфотографировать и выслать на почту преподавателю. К экзамену необходимо подключиться согласно расписанию, высланному преподавателем на корпоративные почты студентов накануне экзамена. Компьютер студента должен удовлетворять требованиям: наличие рабочей камеры и микрофона, поддержка платформы Zoom. Для участия в экзамене студент обязан: выбрать себе имя в Zoom совпадающее с его именем и фамилией, явиться на экзамен согласно точному расписанию, при ответе включить камеру и микрофон. Во время экзамена студентам запрещается выключать камеру. Ипользование конспектов или других справочных материалов допускается только с разрешения преподавателя. Кратковременным нарушением связи во время экзамена считается нарушение связи менее 5 минут. Долговременным нарушением связи во время экзамена считается нарушение 5 минут и более. При долговременном нарушении связи возможность продолжения студентом участие в экзамене определяется преподавателем. Процедура пересдачи подразумевает использование усложненных заданий

Промежуточная аттестация

• Промежуточная аттестация (3 модуль)
  0.5 * Домашнее задание + 0.5 * Письменный экзамен

Список литературы

Рекомендуемая основная литература

• Шапцев В. А., Бидуля Ю. В. - ТЕОРИЯ ИНФОРМАЦИИ. ТЕОРЕТИЧЕСКИЕ ОСНОВЫ СОЗДАНИЯ ИНФОРМАЦИОННОГО ОБЩЕСТВА. Учебное пособие для вузов - М.:Издательство Юрайт - 2019 - 177с. - ISBN: 978-5-534-02989-5 - Текст электронный // ЭБС ЮРАЙТ - URL: https://urait.ru/book/teoriya-informacii-teoreticheskie-osnovy-sozdaniya-informacionnogo-obschestva-434455

Рекомендуемая дополнительная литература

• Dehmer, M., & Emmert-Streib, F. (2009). Information Theory and Statistical Learning. New York: Springer. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsebk&AN=261561