Теория кодирования

С появлением технической возможности хранить и пересылать большие объёмы данных немедленно появилась необходимость бороться со спорадически возникающимися в этих данных ошибками. Эта практическая потребность дала рождение теории кодирования – науке о надежном хранении и передаче информации. Типичный вопрос, изучаемый этой наукой: как передавать по каналу связи полезную информацию, если один процент пересылаемых битов теряется или искажается?

Методы, развитые в теории кодирования, оказываются эффективны в задачах, не связанных непосредственно с защитой сообщений от шума (например, в теории коммуникационной сложности, в схемах разделения секрета, при дерандомизации вероятностных алгоритмов, и т.д.).

В этом курсе мы изучим базовые результаты теории кодирования, а также рассмотрим некоторые недавние достижения этой науки. Курс будет ориентирован на студентов, изучающих computer science; особое внимание будет уделено алгоритмическим задачам теории кодирования.

Для понимания курса полезно знакомство с основами теории вероятностей и линейной алгебры.