Курс «Элементы абстрактной и компьютерной алгебры» и вопросы сжатия информации

В программе курса «Элементы абстрактной и компьютерной алгебры», предназначенного для студентов педагогических ВУЗов, обучающихся по специальности «Информатика», важное место занимают темы, связанные с экономным кодированием информации. Вопросы экономного кодирования, целью которого является сжатие информации, играют важную роль в информатике. Это связано с развитием вычислительной техники и средств связи и, как следствие, с необходимостью хранения и передачи больших объемов информации.

Целью изучения разделов курса, связанных с вопросами сжатия информации, является знакомство студентов с математическими задачами, возникающими в теории кодирования, а также методами и алгоритмами их решения, которые находят реальное применение на практике.

В процессе обучения студенты знакомятся с основными причинами избыточности информации, определяющими возможности ее сжатия. Это вероятностные свойства информации, связанные с частотами появления отдельных букв, и структурные, или синтаксические, свойства, по-зволяющие сжимать информацию благодаря повторяющимся фрагментам.

Студенты изучают методы теории кодирования на примерах классических алгоритмов: Хаффмана, Фано, Шеннона, а также модификации этих алгоритмов, применяемые в реальных системах передачи информации.

При изучении вопросов сжатия, связанных со структурными свойствами информации, особое внимание уделяется результатам основателя теории информации и кодирования К. Шеннона [1]. Здесь выделяется задача моделирования английского текста посредством построения вероятностного источника с конечным числом состояний, а также метод блочного кодирования, позволяющий строить асимптотически оптимальные алгоритмы сжатия.

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

Работа выполнена при поддержке РФФИ, проект 04-01-00374.