Information Theory

2023/2024

Academic Year

RUS

Instruction in Russian

5

ECTS credits

Delivered at:

Department of Informatics

Course type:

Elective course

When:

3 year, 3, 4 module

Instructors

Kuznetsov, Anton

Павлов Дмитрий Александрович

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

Аннотация

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

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

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

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

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

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

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

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

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

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

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

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

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

• Крупский, В. Н.  Теория алгоритмов. Введение в сложность вычислений : учебное пособие для вузов / В. Н. Крупский. — 2-е изд., испр. и доп. — Москва : Издательство Юрайт, 2021. — 117 с. — (Высшее образование). — ISBN 978-5-534-04817-9. — Текст : электронный // Образовательная платформа Юрайт [сайт]. — URL: https://urait.ru/bcode/473006 (дата обращения: 27.08.2024).

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

• 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

Авторы

• Кузнецов Антон Михайлович