Теория кодирования - довольно молодая ветвь дискретной математики, возникшая 50 лет назад из практической задачи об исправлении ошибок в цифровой информации. Основная математическая задача формулируется просто - найти в n-мерном кубе максимальное число A(n,d) вершин таких, что для любых двух вершин кратчайший путь состоит из как минимум d ребер. Или, равносильно, найти множество С n-мерных двоичных векторов таких, что d(x,y)= |x_1 -y_1|+...+|x_n -y_n|>= d для любых двух векторов x и y из С (множество С называется кодом, и код способен исправить t ошибок при 2t<d). Несмотря на кажущуюся простоту (или благодаря ей?)задача оказалась сложной и интересной, с глубокими связями с различными областями математики. Так, развитые в теории кодирования методы оценивания сверху величины A(n,d) помогли улучшить известные оценки на плотность плотнейшей упаковки шаров в n-мерном евклидовом пространстве и были использованы в недавнем доказательстве гипотезы об оптимальности гранецентрированной кубической упаковки (так как лежат апельсины на прилавке). Методы "случайного кодирования" оказались полезными при решении многих комбинаторных задач. С другой стороны, использование алгебраической геометрии привело к построению новых классов кодов, лучших, чем это было известно "неконструктивно".
В рамках данного курса предполагается познакомить студентов с основными понятиями, методами и результатами теории кодирования. А именно: конечные поля и линейная алгебра над ними; основные классы линейных кодов (Хэмминга, БЧХ,РМ); коды и последовательности; вероятностные методы доказательства существования кодов; верхние оценки мощности кодов; связь между кодами и некоторыми задачами криптографии.
Исторический пример: A(7,3)=16 (Хэмминг, 1949); A(8,3)=20,A(9,3)=40(Бест, 1980); A(10,3)=72 (1999),A(11,3)=144???, но A(12+i,3)=2^{8+i} для i=1,2,3 (1949 и 1973).
