Open Exercises

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

Дважды бросают честный k-гранный кубик с числами от 1 от k до k на гранях кубика, получая значения X1 и X2.

  • E[max(X1, X2)] = ?
  • E[min(X1, X2)] = ?

Покажите, что E[max(X1 , X2)] + E[min(X1 , X2)] = E[X1] + E[X2].




Задача «Задачи/eupce-2-7-c»©


Беру задачу «Вероятность/Задачи/eupce-2-7-c» себе!

X и Y — независимые случайные величины с геометрическим распределением, с параметрами P и Q соответственно.

P(min(X, Y) = k) = ?




Задача «Задачи/MAX-CUT-NPC»©


Задача зарезервирована: OMShitikov 10:00, 25 декабря 2023 (UTC)

Докажите, что задача MAX-CUT, в форме задачи разрешения («правда, ли, что для графа G есть разрез больше K?») NP-полна.




Задача «Задачи/eupce-6-2-a»©


Докажите, что для каждого целого числа n существует раскраска ребер полного графа в два цвета, такое что полное число одноцветных подграфов K_n будете не больше чем K_4

Задача зарезервирована: StasFomin 11:32, 19 мая 2023 (UTC)




Задача «Задачи/eupce-6-20»©


Беру задачу «MAX-CUT: вероятностное округление/Задачи/eupce-6-20» себе!

Eupce-6-20 2023-05-19 12-27-59 image0.png




Задача «Задачи/eupce-6-19»©


Беру задачу «MAX-CUT: вероятностное округление/Задачи/eupce-6-19» себе!

Eupce-6-19 2023-05-19 12-22-45 image0.png Eupce-6-19 2023-05-19 12-23-03 image0.png




Задача «Задачи/eupce-6-17»©


Беру задачу «MAX-CUT: вероятностное округление/Задачи/eupce-6-17» себе!

Eupce-6-17 2023-05-18 19-57-47 image0.png




Задача «Задачи/eupce-6-15»©


Беру задачу «MAX-SAT: дерандомизация/Задачи/eupce-6-15» себе!

Eupce-6-15 2023-05-18 19-51-41 image0.png




Задача «Задачи/eupce-6-14»©


Беру задачу «MAX-CUT: вероятностное округление/Задачи/eupce-6-14» себе!

Eupce-6-14 2023-05-18 19-44-29 image0.png




Задача «Задачи/eupce-6-13»©


Беру задачу «MAX-CUT: вероятностное округление/Задачи/eupce-6-13» себе!

Eupce-6-13 2023-05-18 19-43-15 image0.png




Задача «Задачи/eupce-6-11»©


Беру задачу «MAX-CUT: вероятностное округление/Задачи/eupce-6-11» себе!

Eupce-6-11 2023-05-18 19-41-29 image0.png




Задача «Задачи/eupce-6-10»©


Беру задачу «MAX-CUT: вероятностное округление/Задачи/eupce-6-10» себе!

Eupce-6-10 2023-05-18 19-38-29 image0.png Eupce-6-10 2023-05-18 19-38-53 image0.png




Задача «Задачи/eupce-6-9»©


Беру задачу «MAX-CUT: вероятностное округление/Задачи/eupce-6-9» себе!

Eupce-6-9 2023-05-18 19-35-59 image0.png



Задача «Задачи/eupce-6-8»©


Беру задачу «MAX-CUT: вероятностное округление/Задачи/eupce-6-8» себе!

Eupce-6-8 2023-05-18 19-34-01 image0.png




Задача «Задачи/eupce-6-7»©


Беру задачу «MAX-CUT: вероятностное округление/Задачи/eupce-6-7» себе!

Eupce-6-7 2023-05-18 19-27-32 image0.png




Задача «Задачи/eupce-6-4»©


Беру задачу «MAX-SAT: дерандомизация/Задачи/eupce-6-4» себе!

Eupce-6-4 2023-05-18 19-16-39 image0.png




Задача «Задачи/eupce-6-3-b»©


Беру задачу «MAX-SAT: вероятностное округление/Задачи/eupce-6-3-b» себе!

  • Дан n-вершинный неориентированный граф G=(V, E)

Рассмотрим следующий метод генерации независимого множества.

Для заданной перестановки вершин σ, определим подмножество S(σ) вершин следующим образом: для каждой вершины i, i ∈ S(σ) тогда и только тогда, когда никакой ни один сосед j вершины i не предшествует i в перестановке σ.

Предложите вероятностный алгоритм для поиска σ

для которого можно показать, что ожидаемый размер d\left(\{c_{\pi(m)},c_{\pi(1)}\}\right)+\displaystyle\sum\limits_{i=1}^{m-1} d\left(\{c_{\pi(i)},c_{\pi(i+1)}\}\right)

где означает степень вершины i.

Докажите, что в G существует независимое множество размера как минимум




Задача «Задачи/eupce-6-3-a»©


Беру задачу «MAX-SAT: вероятностное округление/Задачи/eupce-6-3-a» себе!

  • Дан n-вершинный неориентированный граф G=(V, E)

Рассмотрим следующий метод генерации независимого множества.

Для заданной перестановки вершин σ, определим подмножество S(σ) вершин следующим образом: для каждой вершины i, i ∈ S(σ) тогда и только тогда, когда никакой ни один сосед j вершины i не предшествует i в перестановке σ.

Покажите, что каждый S(σ) будет независимым множеством в G.




Задача «Задачи/eupce-6-1-b»©


Беру задачу «MAX-SAT: дерандомизация/Задачи/eupce-6-1-b» себе!

Предложите алгоритм дерандомизации методом условных вероятностей для алгоритма из MAX-SAT: вероятностное округление/Задачи/eupce-6-1-a‎.




Задача «Задачи/eupce-6-1-a»©


Беру задачу «MAX-SAT: вероятностное округление/Задачи/eupce-6-1-a» себе!

Рассмотрим K-ESAT, SAT, когда в каждой скобке ровно k литералов.

Предложите Лас-Вегас алгоритм выполняющий минимум

скобок, и проанализируйте матожидание его времени выполнения.




Задача «Задачи/eupce-2-13-b»©


Беру задачу «Вероятность/Задачи/eupce-2-13-b» себе!