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

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

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

Аннотация

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

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

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

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

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

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

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

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

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

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

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

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

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

  • Шапцев В. А., Бидуля Ю. В.-ТЕОРИЯ ИНФОРМАЦИИ. ТЕОРЕТИЧЕСКИЕ ОСНОВЫ СОЗДАНИЯ ИНФОРМАЦИОННОГО ОБЩЕСТВА. Учебное пособие для вузов-М.:Издательство Юрайт,2019-177-Высшее образование-978-5-534-02989-5: -Текст электронный // ЭБС Юрайт - https://biblio-online.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