03 июня 2014 г.

  Н.Ю. Золотых (ННГУ, ВМиК)

"Расшифровка пороговых функций и близкие задачи"

         Пороговой функцией называется отображение k-ичного n-мерного гиперкуба {0,1,…, k–1}ⁿ в множество {0,1}, такое, что существует гиперплоскость, отделяющая множество нулей функции от множества единиц. В каком подмножестве точек области определения достаточно знать функцию, чтобы восстановить ее значения во всех остальных точках? Как найти это подмножество? Как уменьшить мощность этого подмножества? В докладе будут даны ответы на эти вопросы. Также будет рассматриваться связь этой задачи с дискретной оптимизацией (сложность задачи о рюкзаке), теорией чисел (диофантовы приближения), дискретной геометрией (разбиения плоскости).

Наверх