Information Theory

2021/2022

Academic Year

RUS

Instruction in Russian

5

ECTS credits

Delivered at:

Department of Informatics

Course type:

Elective course

When:

3 year, 3, 4 module

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

Аннотация

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

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

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

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

• Знает определение количества информации по Хартли и основные свойства, определение энтропии Шеннона и основные её свойства, основные определения из коммуникационной сложности, определение колмоговской сложности и основные её свойства.
• Умеет оценивать количество информации по Хартли, применять свойства и соотношения на энтропию Шеннона для оценки энтропии различных случайных величин, применять свойства и соотношения на колмогоровскую сложность для оценки колмогоровской сложности, доказывать оценки на коммуникационную сложность.
• Владеет основными методами работы с энтропией Шеннона и оценками на колмогоровскую сложность, основными техниками доказательства оценок на коммуникационную сложность.

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

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

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

• Домашнее задание
  Домашнее задание выдается студентам в одном варианте и состоит из 8 задач. Срок выполнения домашнего задания - 2 недели. Форма представления обучающимися домашнего задания - представленные в письменном виде решения задач.
• Письменный экзамен
  Письменный экзамен проводится в форме ответов на вопросы экзаменационного билета. Экзаменационный билет содержит два вопроса из перечня вопросов к экзамену. На подготовку ответа выделяется 2,5 часа.

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

• 2021/2022 учебный год 3 модуль
  0.5 * Письменный экзамен + 0.5 * Домашнее задание
• 2021/2022 учебный год 4 модуль
  0.5 * Письменный экзамен + 0.5 * Домашнее задание

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

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

• Крупский В. Н. - ТЕОРИЯ АЛГОРИТМОВ. ВВЕДЕНИЕ В СЛОЖНОСТЬ ВЫЧИСЛЕНИЙ 2-е изд., испр. и доп. Учебное пособие для вузов - М.:Издательство Юрайт - 2021 - 117с. - ISBN: 978-5-534-04817-9 - Текст электронный // ЭБС ЮРАЙТ - URL: https://urait.ru/book/teoriya-algoritmov-vvedenie-v-slozhnost-vychisleniy-473006

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

• 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