Редактирование: Список заданий по ДМ 2020 осень

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

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 56: Строка 56:
 
# Докажите, что не существует схем константной глубины для функций $x_1 \vee ... \vee x_n$, $x_1 \wedge ... \wedge x_n$, $x_1 \oplus ... \oplus x_n$.
 
# Докажите, что не существует схем константной глубины для функций $x_1 \vee ... \vee x_n$, $x_1 \wedge ... \wedge x_n$, $x_1 \oplus ... \oplus x_n$.
 
# Докажите формулу разложения Шеннона по переменной $x$: $f(x, y_2, y_3, \ldots, y_n)=x\wedge f(1, y_2, y_3, \ldots, y_n)\vee \neg x\wedge f(0, y_2, y_3, \ldots, y_n)$
 
# Докажите формулу разложения Шеннона по переменной $x$: $f(x, y_2, y_3, \ldots, y_n)=x\wedge f(1, y_2, y_3, \ldots, y_n)\vee \neg x\wedge f(0, y_2, y_3, \ldots, y_n)$
# Для булевых векторов $\alpha$ и $\beta$ обозначим как $\alpha\vee\beta$ побитовое $\vee$ этих векторов, аналогично введём $\alpha \wedge \beta$. Обозначим как $\succeq$ отношение доминирования на булевых векторах, $\alpha\succeq\beta$, если для всех $i$ выполнено $a_i\ge b_i$. Докажите, что $\alpha \wedge \beta$ удовлетворяет свойству, что $(\alpha \succeq\gamma)\wedge(\beta \succeq \gamma) \Leftrightarrow (\alpha\wedge\beta)\succeq \gamma$. Докажите, что $\alpha \vee \beta$ удовлетворяет свойству, что $\left((\gamma \succeq \alpha) \wedge (\gamma \succeq \beta)\right) \Leftrightarrow \gamma\succeq(\alpha\vee\beta)$.  
+
# Для булевых векторов $\alpha$ и $\beta$ обозначим как $\alpha\vee\beta$ побитовое $\vee$ этих векторов, аналогично введём $\alpha \wedge \beta$. Обозначим как $\succeq$ отношение доминирования на булевых векторах, $\alpha\succeq\beta$, если для всех $i$ выполнено $a_i\ge b_i$. Докажите, что $\alpha \wedge \beta$ удовлетворяет свойству, что $(\alpha \succeq\gamma)\wedge(\beta \succeq \gamma) \Leftrightarrow (\alpha\wedge\beta)\succeq \gamma$. Докажите, что $\alpha \vee \beta$ удовлетворяет свойству, что $\gamma \succeq \alpha \wedge \gamma \succeq \beta \Leftrightarrow \gamma\succeq(\alpha\vee\beta)$.  
 
# Докажите равенства $\alpha \wedge(\beta\vee\gamma)=(\alpha \wedge\beta)\vee(\alpha\wedge\gamma)$ и $\alpha \vee(\beta\wedge\gamma)=(\alpha \vee\beta)\wedge(\alpha\vee\gamma)$.
 
# Докажите равенства $\alpha \wedge(\beta\vee\gamma)=(\alpha \wedge\beta)\vee(\alpha\wedge\gamma)$ и $\alpha \vee(\beta\wedge\gamma)=(\alpha \vee\beta)\wedge(\alpha\vee\gamma)$.
 
# Будем говорить, что булевый вектор $\alpha = (a_1, a_2, \ldots, a_n)$ префиксно мажорирует вектор $\beta = (b_1, b_2, \ldots, b_n)$, если для любого $k$ выполнено $a_1+\ldots+a_k \ge b_1+\ldots+b_k$ и писать $\alpha \ge_p \beta$. Докажите, что отношение $\ge_p$ является частичным порядком.  
 
# Будем говорить, что булевый вектор $\alpha = (a_1, a_2, \ldots, a_n)$ префиксно мажорирует вектор $\beta = (b_1, b_2, \ldots, b_n)$, если для любого $k$ выполнено $a_1+\ldots+a_k \ge b_1+\ldots+b_k$ и писать $\alpha \ge_p \beta$. Докажите, что отношение $\ge_p$ является частичным порядком.  
 
# Докажите. что $\alpha$ префиксно мажорирует $\beta$ тогда и только тогда, когда $\overline{\beta}$ префиксно мажорирует $\overline{\alpha}$ ($\overline{\alpha}$ означает побитовую инверсию).
 
# Докажите. что $\alpha$ префиксно мажорирует $\beta$ тогда и только тогда, когда $\overline{\beta}$ префиксно мажорирует $\overline{\alpha}$ ($\overline{\alpha}$ означает побитовую инверсию).
# Докажите, что для любых двух векторов $\alpha$ и $\beta$ существует и единственный вектор $\alpha \curlywedge \beta$, такой что $((\alpha \ge_p \gamma) \wedge (\beta \ge_p \gamma)) \Leftrightarrow (\alpha\curlywedge\beta)\ge_p\gamma$. Предложите алгоритм построения такого вектора.
+
# Докажите, что для любых двух векторов $\alpha$ и $\beta$ существует и единственный вектор $\alpha \curlywedge \beta$, такой что $\alpha \ge_p \gamma \wedge \beta \ge_p \gamma \Leftrightarrow (\alpha\curlywedge\beta)\ge_p\gamma$. Предложите алгоритм построения такого вектора.
# Докажите, что для любых двух векторов $\alpha$ и $\beta$ существует и единственный вектор $\alpha \curlyvee \beta$, такой что $((\gamma \ge_p \alpha) \wedge (\gamma \ge_p \beta)) \Leftrightarrow \gamma\ge_p(\alpha\curlyvee\beta)$. Предложите алгоритм построения такого вектора.
+
# Докажите, что для любых двух векторов $\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)$.
 
# Докажите равенства $\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 \le_p y$ следует, что $f(x) \le f(y)$. Как связаны регулярные и монотонные функции?
 
# Будем называть функцию $f$ регулярной, если из $x \le_p y$ следует, что $f(x) \le f(y)$. Как связаны регулярные и монотонные функции?

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)