На главную страницу ЛШСМ-2011 К списку курсов ЛШСМ-2011

Владимир Николаевич Потапов

Совершенные комбинаторные структуры

В.Н.Потапов планирует провести 4 занятия.

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

Программа

  1. q-Значный n-мерный куб (Eq)n; шары, грани, подпространства. Комбинаторные структуры в (Eq)n: линейные коды, совершенные раскраски и коды, МДР-коды, n-арные квазигруппы и латинские кубы, корреляционно-иммунные функции.
  2. Характеры конечной абелевой группы и преобразование Фурье в (Eq)n. Описание совершенных структур в терминах коэффициентов Фурье. Теорема Фон-Дер-Флаасса и неравенство Биербрауэра–Фридмана.
  3. Перманенты (0,1)-матриц, теорема Кёнига–Холла, продолжение латинского прямоугольника до латинского квадрата. Ортогональные латинские квадраты и построение МДР-кодов с большим расстоянием.
  4. Конструкции n-арных квазигрупп и оценки их числа. Критерий представимости в виде суперпозиции. Конструкция Фелпса и существование нелинейных совершенных кодов. Решение проблемы Белоусова о существовании n-арных квазигрупп непредставимых в виде суперпозиции.

Rambler's Top100