Пятница, 19 сентября, ауд. 203. Начало в 17:00.
Докладчик: А.М. Шур (Уральский федеральный университет).
Тема: Генератор бесквадратных слов.
Abstract
Конструктивное доказательство локальной леммы Ловаса Мозером и Тардошем в 2010 году дало мощный толчок как для ревизии и усиления чисто "экзистенциальных" комбинаторных результатов, полученных с помощью этой знаменитой леммы, так и для построения рандомизированных алгоритмов, использующих локальный ресэмплинг, как в доказательстве Мозера-Тардоша. Мы исследуем один из таких алгоритмов: он преобразует случайную последовательность символов в бесквадратную, т.е. в такую, в которой никакие два соседних фрагмента (произвольной длины) не равны между собой. Мы покажем, что такой алгоритм неожиданно эффективен, т.е. ожидаемое количество случайных символов, требуемых для получения бесквадратной последовательности длины N, лишь незначительно превышает N.
