Ищется оптимальная конструкция кодов-векторов для передачи сообщений с минимумом ошибок. Рассматривается случай сферы внутри n-мерного пр-ва, n+1 вектора и белого гауссовского шума. Утверждается, что тогда наилучшим расположением будут вершины правильного n-мерного симплекса.
В докладе будет рассказано об общих идеях нескольких работ последних лет, в которых улучшаются верхние оценки для диагональных чисел Рамсея. Основное внимание будет уделено следующим двум теоремам.
1. Для всех достаточно больших $k \in \mathbb{N}_1$ имеет место неравенство $R_2(k) \leq 3.8^{k + o(k)}$.
2. Для каждого $r \in \mathbb{N}_1$, $r \geq 2$ существует такое $\delta = \delta(r) > 0$,...
Данная работа посвящена исследованию вычислительной сложности настольных и компьютерных игр. Основной результат заключается в доказательстве PSPACE-полноты игры Diamond Rush с использованием подхода, изложенного в книге Games, Puzzles, and Computation авторов R.A.Hearn и E.D.Demaine.
В данной работе изучаются оценки чисел Рамсея, обобщённые на случай произвольных последовательностей графов. Вводятся обобщения классического числа Рамсея: $R_{\min}(\{G_n\}, k)$ — минимальное число $m$ для натурального $k$, при котором в любом остовном подграфе $G$ или его дополнении $G_m \setminus G$ содержится индуцированный подграф изоморфный некому индуцированному подграфу $G_m$ на $k$...
Экстракторы - это функции, преобразующие источники случайности в близкие к равномерным. Существование экстракторов с хорошими параметрами может быть доказано вероятностным методом, но для приложений нужны явные конструкции. В работе представлены современные результаты по явным конструкциям экстракторов с одним и двумя независимыми источниками. Изложена конструкция экстрактора с одним...
В работе рассматриваются числа ван дер Вардена для многомерных арифметических прогрессий. Дано определение многомерной прогрессии и обосновано существование соответствующих чисел w(l₁; l₂; … ; lₘ; r). Приводится верхняя оценка этих чисел на основе классической теоремы ван дер Вардена и теоремы Гауэрса.
