Теория информации

Бакалавриат 2023/2024

Статус: Курс по выбору (Прикладная математика и информатика)

Направление: 01.03.02. Прикладная математика и информатика

Кто читает: Департамент информатики

Где читается: Школа информатики, физики и технологий

Когда читается: 3-й курс, 3, 4 модуль

Формат изучения: без онлайн-курса

Охват аудитории: для всех кампусов НИУ ВШЭ

Преподаватели: Кузнецов Антон Михайлович, Павлов Дмитрий Александрович

Язык: русский

Кредиты: 5

Контактные часы: 48

Дополнительные материалы в LMS Задать вопрос

Аннотация

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

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

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

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

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

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

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

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

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

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

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

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

Авторы

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

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