Викиконспекты - Вклад участника [ru]

Теория сложности 2019

2019-02-16T10:09:05Z

120.52.147.55:

# Докажите, что объединение и пересечение языков из $P$ является языком из $P$
# Докажите, что дополнение языка из $P$ является языком из $P$
# Докажите, что конкатенация и замыкание Клини языков $P$ является языком из $P$
# Докажите, что объединение и пересечение языков из $NP$ является языком из $NP$
# Докажите, что конкатенация и замыкание Клини языков $NP$ является языком из $NP$
# Почему рассуждение из задания 2 не применимо к языкам из $NP$?
# Когда мы задаем числа, мы обычно записываем их в десятичной системе счисления. Докажите, что выбор для формата ввода любой системы счисления с основанием $b \ge 2$ не влияет на принадлежность языка классу $P$.
# В унарной системе счисления число $n$ задаётся как $1^n$. Докажите, что язык $FAC.UNARY = \{\langle 1^n, 1^q \rangle |$ у $n$ существует делитель $t$, такой что $2 \le t \le q < n\}$ лежит в $P$.
# В унарной системе счисления число $n$ задаётся как $1^n$. Докажите, что язык $UNARY.SUBSET.SUM = \{\langle 1^s, [1^{a_1}, 1^{a_2}, \ldots, 1^{a_n}] \rangle |$ можно выбрать подмножество $\{a_1, a_2,\ldots, a_n\}$ с суммой $s\}$ лежит в $P$.
# Завершите доказательство, что $PRIMES \in NP$, доказав, суммарный размер рекурсивных сертификатов простоты простых делителей $n-1$ и время на их проверку является полиномом от длины $n$.
# Задача останова $HALT = \{\langle m, x \rangle | m$ - машина Тьюринга, $m(x) = 1\}$. Докажите, что $HALT$ является $NP$-трудной. Является ли она $NP$-полной?

Теория сложности 2019

2019-02-16T09:57:32Z

120.52.147.55: Новая страница: «# Докажите, что объединение и пересечение языков из $P$ является языком из $P$ # Докажите, чт…»

# Докажите, что объединение и пересечение языков из $P$ является языком из $P$
# Докажите, что дополнение языка из $P$ является языком из $P$
# Докажите, что конкатенация и замыкание Клини языков $P$ является языком из $P$
# Докажите, что объединение и пересечение языков из $NP$ является языком из $NP$
# Докажите, что конкатенация и замыкание Клини языков $NP$ является языком из $NP$
# Почему рассуждение из задания 2 не применимо к языкам из $NP$?
# Когда мы задаем числа, мы обычно записываем их в десятичной системе счисления. Докажите, что выбор для формата ввода любой системы счисления с основанием $b \ge 2$ не влияет на принадлежность языка классу $P$.
# В унарной системе счисления число $n$ задаётся как $1^n$. Докажите, что язык $FAC.UNARY = \{\langle 1^n, 1^q \rangle |$ у $n$ существует делитель $t$, такой что $2 \le t \le q < n\}$ лежит в $P$. Что можно сказать про аналогичную задачу, где ввод задается в двоичной системе счисления?
# Задача останова $HALT = \{\langle m, x \rangle | m$ - машина Тьюринга, $m(x) = 1\}$. Докажите, что $HALT$ является $NP$-трудной. Является ли она $NP$-полной?

Список заданий по ДМ 2019 весна

2019-02-16T09:50:13Z

120.52.147.55: Новая страница: «# Чему равна вероятность, что две случайно вытянутые кости домино можно приложить друг к…»

# Чему равна вероятность, что две случайно вытянутые кости домино можно приложить друг к другу по правилам домино?
# Чему равна вероятность, что на двух брошенных честных игральных костях выпадут числа, одно из которых делит другое?
# Чему равна вероятность, что если вытянуть из 52-карточной колоды две случайные карты, одной из них можно побить другую (одна из мастей назначена козырем, картой можно побить другую, если они одинаковой масти или если одна из них козырь)?
# Чему равна вероятность, что на двадцати брошенных честных монетах выпадет поровну нулей и единиц?
# Петя и Вася три раза бросают по одной честной игровой кости. Вася два раза выкинул строго больше, чем Петя, а один раз строго меньше. При этом Петя в сумме выкинул строго больше, чем Вася. С какой вероятностью такое могло произойти?
# Приведите пример трех событий, для которых $P(A \cap B \cap C) = P(A)P(B)P(C)$, но которые не являются независимыми, причем вероятности всех трех событий больше 0
# Доказать или опровергнуть, что для независимых событий $A$ и $B$ и события $C$, где $P(C) > 0$ выполнено $P(A \cap B|C) = P(A|C)P(B|C)$
# Доказать или опровергнуть, что для независимых событий $A$ и $B$ и события $C$, где $P(A) > 0$, $P(B) > 0$ выполнено $P(C|A \cap B) = P(C|A)P(C|B)$
# Доказать или опровергнуть: если $P(A|B) = P(B|A)$, то $P(A) = P(B)$
# Доказать или опровергнуть: если $P(A|B) = P(B|A)$, то $A$ и $B$ независимы
# Доказать или опровергнуть: если $P(A|C) = P(B|C)$, то $P(C|A) = P(C|B)$
# Доказать или опровергнуть: если $A$ и $B$ независимы, то $\Omega \setminus A$ и $\Omega \setminus B$ независимы
# Петя собирается смотреть серию матчей финала Флатландской хоккейной лиги. В финале две команды играют до 5 побед, ничьих не бывает, таким образом максимум в финале будет не более 9 матчей. Вася рассказал Пете, что всего в финале было 7 матчей. Петя считает матч интересным, если перед его просмотром он не знает, кто выиграет финал. Пусть все возможные последовательности исходов матчей, удовлетворяющих описанным условиями, равновероятны. Какова вероятность, что будет хотя бы 4 интересных матча?
# Петя собирается смотреть серию матчей финала Флатландской хоккейной лиги. В финале две команды играют до 5 побед, ничьих не бывает, таким образом максимум в финале будет не более 9 матчей. Вася рассказал Пете, что всего в финале было 7 матчей. Петя считает матч зрелищным, если перед его просмотром он не знает, кто его выиграет. Пусть все возможные последовательности исходов матчей, удовлетворяющих описанным условиями, равновероятны. Какова вероятность, что будет хотя бы 5 зрелищных матчей?