• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

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