Теория кодирования решает задачи исправления/обнаружения ошибок при передаче/хранении информации. Математические модели сводят эти весьма практические задачи к задачам о плотной упаковке (равных) шаров в некоторых специальных дискретных пространствах. Например, в пространстве двоичных n-мерных векторов с расстоянием определяемым как число координат, в которых векторы различаются (так называемое пространство Хэмминга). Нахождение максимального числа непересекающихся шаров заданного радиуса t в пространстве Хэмминга (центры шаров и образуют двоичный код длины n, исправляющий t ошибок) - сложная, далекая от своего решения задача (даже в простейшем случае t=1), имеющая глубокие связи с различными областями алгебры, геометрии и комбинаторики. Например, методами теории кодирования получены наилучшие оценки для плотности упаковки равных шаров в n-мерном Евклидовом пространстве, начиная с n=4.
Другая тема этого курса - криптография. Несмотря на довольно общее заблуждение, что коды и криптография - суть одно и тоже, до недавнего времени эти две области имели весьма незначительное пересечение как по задачам, так и по методам их решения. В курсе будут изложены некоторые задачи современной криптографии, такие как "разделение секрета", "цифровые отпечатки пальцев" и "цифровые водяные знаки", решении которых было найдено с помощью методов и идей теории кодирования.
Основные темы курса:
