Изменения

Перейти к: навигация, поиск

Список заданий по ДМ 2020 осень

2 байта убрано, 18:36, 5 октября 2020
Нет описания правки
# Докажите, что для любых двух векторов $\alpha$ и $\beta$ существует и единственный вектор $\alpha \curlyvee \beta$, такой что $\gamma \ge_p \alpha \wedge \gamma \ge_p \beta \Leftrightarrow \gamma\ge_p(\alpha\curlyvee\beta)$. Предложите алгоритм построения такого вектора.
# Докажите равенства $\alpha \curlywedge(\beta\curlyvee\gamma)=(\alpha \curlywedge\beta)\curlyvee(\alpha\curlywedge\gamma)$ и $\alpha \curlyvee(\beta\curlywedge\gamma)=(\alpha \curlyvee\beta)\curlywedge(\alpha\curlyvee\gamma)$.
# Будем называть функцию $f$ регулярной, если из $x \preceq le_p y$ следует, что $f(x) \le f(y)$. Как связаны регулярные и монотонные функции?
# Докажите, что если функция $f$ является пороговой и $a_1 \ge a_2 \ge \ldots \ge a_n \ge 0$, то $f$ является регулярной.
# Опишите алгоритм, выполняющий преобразование Мебиуса, который работает за время $O(3^n)$.
# Опишите алгоритм, выполняющий преобразование Мебиуса, который работает за время $O(2^n n)$.
Анонимный участник

Навигация