Open Exercises — различия между версиями

Бонусная задача

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

Предположим, что независимо бросают два стандартных шестисторонних кости, X₁ — то, что выпадает на первой, X₂ — на второй, а X — сумма обоих значений.

E[X₁ | X = 9] = ?

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

Бонусная задача

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

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

P(X = Y) = ?

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

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

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

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

Бонусная задача

Докажите, что для каждого целого числа n существует раскраска ребер полного графа \binom{n}{4} 2^{-5} в два цвета, такое что полное число одноцветных подграфов будете не больше чем

Задача «Задачи/NP-sums»^©

Проверить принадлежность классу следующей задачи: по заданному конечному множеству натуральных чисел, представленных в своей бинарной записи, определить возможность разделения этого множества на два подмножества с одинаковыми суммами.

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

Докажите, что k ≥ 1 для любого целого

S(\sigma) = \sum_{i=1}^{n} \frac{1}{d_i + 1}

.

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

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

Частота ошибок первого рода (false negative) мала: если у вас есть расстройство, вероятность того, что тест вернет положительный результат, составляет 0.999.

Частота ошибок второго рода (false positive) тоже невелика: если у вас нет расстройства, вероятность того, что тест вернет положительный результат, составляет всего 0.005.

Предположим, что эту болезнь имеет 2% населения.

Если мы проверяем человека, выбранного равномерно из популяции, и получается положительный результат, какова вероятность того, что эта болезнь у него действительно есть?

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

Предположим, что бросают десять стандартных шестисторонних костей.

Какова вероятность того, что их сумма будет деленной на 6, предполагая, что броски независимы?

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

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

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

Мы берем карты равномерно случайным образом с из колоды из n карт, выбранную карту добавляют в колоду (она будет всегда полна).

• Каково ожидаемое число карт, которые мы должны вытянуть, пока не увидим все n карт в колоде?
• Если мы возьмем 2n карт, то каково ожидаемое число карт в колоде, которые
  • не будут выбраны вообще?
  • выбраны ровно один раз?

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

Покажите, что в графе с n вершинами и m ребрами, существует разрез, размера как минимум mn/(2n-1).

Задача «Задачи/eupce-2-1»^©

Предположим, мы бросаем честный k-сторонний кубик с числами 1 через K на гранях. Если x — это выпавшее число, то каково матожидание — E[x]?

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

Предположим, что Алиса и Боб решили продолжать заводить детей, пока у них не родится девочка.

Если предположить, что это возможно, то каково ожидаемое количество мальчиков у них родится?

Задача «Задачи/eupce-1-23»^©

В графе может быть несколько одинаково минимальных разрезов. Покажите, что их не больше n(n − 1)/2.

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

Бонусная задача

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

Бонусная задача

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

Бонусная задача

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

Бонусная задача

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

Бонусная задача

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

Бонусная задача

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

Бонусная задача

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

Бонусная задача

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

Бонусная задача

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

Бонусная задача

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

Бонусная задача

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

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

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

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

для которого можно показать, что ожидаемый размер

где p = \frac{1 − q}{2} означает степень вершины i.

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

Задача «Задачи/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-a‎.

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

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

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

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

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

Решите обобщенную версию задачи [[../eupce-2-13]]:

• kn различных купонов, организованных в n непересекающихся наборов из k купонов.
• нужен один купон из каждого набора.

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

• Каждая коробка хлопьев содержит один из 2n различных купонов (купон в каждой коробке выбирается независимо и равномерно случайным образом из 2n).
• Купоны организованы в n пар, так что купоны 1 и 2 составляют пару, купоны 3 и 4 составляют пару и так далее.
• Получив по одному купону из каждой пары, вы можете получить приз.

Какое ожидаемое количество коробок, надо для этого купить?

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

Алиса и Боб решили заводить детей до тех пор, пока у них не родится девочка или пока у них не будет k ≥ 1 детей.

Предположим, что каждый ребенок будет мальчиком или девочкой независимо с вероятностью 1/2 и что многоплодных родов не бывает.

• Каково ожидаемое число детей женского пола?
• Каково ожидаемое число детей мужского пола?

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

Предположим, что независимо бросают два стандартных шестисторонних кости, X₁ — то, что выпадает на первой, X₂ — на второй, а X — сумма обоих значений.

• 2 ≤ k ≤ 12
• E[X₁ - X₂ | X = k] = ?

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

Предположим, что независимо бросают два стандартных шестисторонних кости, X₁ — то, что выпадает на первой, X₂ — на второй, а X — сумма обоих значений.

E[X | X₁ = X₂] = ?

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

Предположим, что независимо бросают два стандартных шестисторонних кости, X₁ — то, что выпадает на первой, X₂ — на второй, а X — сумма обоих значений.

E[X | X₁ — четное] = ?

Задача «Задачи/eupce-2-5»^©

Если X — случайная величина с биномиальным распределением B(n, 1/2) для n ≥ 1, покажите, что вероятность того,

что X — четное будет 1/2.

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

Обычные крестики-нолики скучные, при оптимальной стратегии в них выигрывают крестики.

Рассмотрим вероятную модификацию этой игры.

• Как обычно, крестики и нолики ходят по очереди и нолик идет первым. Как обычно, выигрывает тот, кто первый добъется «три в ряд», или ничья, если никто.
• Но на каждом ходе позиция и у крестиков и у ноликов выбирается независимо и равномерно среди свободных квадратов.

Найдите вероятность, выигрыша для «крестиков» и для «ноликов».

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

Обычные крестики-нолики скучные, при оптимальной стратегии в них выигрывают крестики.

Рассмотрим вероятную модификацию этой игры.

• Изначально, бросая честную монетку, разметим каждый из девяти квадратов либо X, либо O.
• Если только один из игроков имеет «три в ряд» → он победил.
• Если оба или никто → ничья.

Определите вероятность, что «X» выиграет.

Задача «Задачи/eupce-1-18»^©

• Есть функция t \leftarrow 1^{t}
• и известно что L_{1SUBSETSUM}.

Единственный способ вычисления F — использовать таблицу поиска, в которой хранится значения F. К сожалению, злой противник изменил значение 1/5 записей в этой таблице.

Опишите простой рандомизированный алгоритм, который, учитывая входной Z, выводит значение, которое равняется f(z) с вероятностью не менее 1/2.

Ваш алгоритм должен работать для каждого значения Z, независимо от того, какие записи изменил противник.

Дополнительно, предположим, вам разрешено повторить этот ваш начальный алгоритм три раза.

Как этим воспрользоваться, чтобы максимально увеличить вероятность правильного ответа, и какова эта вероятность?

Задача «Задачи/eupce-1-16-d»^©

Рассмотрим игру, основанную на бросках трех стандартных шестисторонних костей.

Цель → получить одинаковое число на всех трех костях, кто первый этого добьется, тот выиграл.

• Игрок начинает с броска всех трех кубиков.
• После первого броска игрок может выбрать одну, две или три кости и бросить их снова.
• После второго броска игрок один из трех кубиков и перебросить его.

Предположим, что игрок использует следующую оптимальную стратегию:

• если все три кости одинаковые → останавливаемся и выигрываем;
• если два кубика совпадают, игрок перебрасывает тот, который «выбивается из коллектива».
• если все не совпадают — перебрасываем их всех.

Рассматривая все возможные возможные выпадения костей, найдите вероятность того, что игрок выиграет.

Задача «Задачи/eupce-1-16-c»^©

Рассмотрим игру, основанную на бросках трех стандартных шестисторонних костей.

Цель → получить одинаковое число на всех трех костях, кто первый этого добьется, тот выиграл.

• Игрок начинает с броска всех трех кубиков.
• После первого броска игрок может выбрать одну, две или три кости и бросить их снова.
• После второго броска игрок один из трех кубиков и перебросить его.

Предположим, что игрок использует следующую оптимальную стратегию:

• если все три кости одинаковые → останавливаемся и выигрываем;
• если два кубика совпадают, игрок перебрасывает тот, который «выбивается из коллектива».
• если все не совпадают — перебрасываем их всех.

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

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

Рассмотрим игру, основанную на бросках трех стандартных шестисторонних костей.

Цель → получить одинаковое число на всех трех костях, кто первый этого добьется, тот выиграл.

• Игрок начинает с броска всех трех кубиков.
• После первого броска игрок может выбрать одну, две или три кости и бросить их снова.
• После второго броска игрок один из трех кубиков и перебросить его.

Предположим, что игрок использует следующую оптимальную стратегию:

• если все три кости одинаковые → останавливаемся и выигрываем;
• если два кубика совпадают, игрок перебрасывает тот, который «выбивается из коллектива».
• если все не совпадают — перебрасываем их всех.

Найдите вероятность того, что ровно два из трех кубиков показывают одинаковое число в первом броске.

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

Рассмотрим игру, основанную на бросках трех стандартных шестисторонних костей.

Цель → получить одинаковое число на всех трех костях, кто первый этого добьется, тот выиграл.

• Игрок начинает с броска всех трех кубиков.
• После первого броска игрок может выбрать одну, две или три кости и бросить их снова.
• После второго броска игрок один из трех кубиков и перебросить его.

Предположим, что игрок использует следующую оптимальную стратегию:

• если все три кости одинаковые → останавливаемся и выигрываем;
• если два кубика совпадают, игрок перебрасывает тот, который «выбивается из коллектива».
• если все не совпадают — перебрасываем их всех.

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

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

Я играю в турнире ракетбола против игрока, против которого раньше не играл, но видел его в игре.

Априори рассматриваю три равновероятные возможности:

• мы одинаково талантливы, каждый из нас в равной степени может выиграть каждую игру;
• Я немного лучше, и поэтому я выигрываю каждую игру независимо с вероятностью 0.6;
• Он немного лучше, и поэтому он выигрывает каждую игру независимо с вероятностью 0.6.

В рокетбол играют, пока один игрок не выиграет три сета. В нашей игре, я выиграл только второй сет, а противник выиграл первый, третий и четвертый.

В апостеорной модели, с какой вероятностью я должен верить, что мой оппонент немного лучше, чем я?

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

• Пытаемся передать один бит (0 или 1) через промежуточные узлы, каждый из которых независимо может инвертировать бит с вероятностью «p».
• Скажем, узел имеет смещение «q», если это

P^{\Sigma^p_{k}}=P^{\Pi^p_{k}} , «смещение» будет вещественным числом на отрезке [−1, 1].

Докажите, что прохождение бита через узлы со смещениями «q1» и «q2» эквивалентно прохождению бита через один узел со смещением «q1×q2».

Задача «Задачи/eupce-1-11-c»^©

Пытаемся передать один бит (0 или 1) через «n» промежуточных узлов, каждый из которых независимо

может инвертировать бит с вероятностью «p».

Докажите, что вероятность получения корректного бита:

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

• Честную монету бросили «n» раз.
• Для k>0, найдите верхнюю границу вероятности, что будет последовательность из последовательных орлов.

Задача «Задачи/E13SAT-NPC»^©

Покажите, что NP-полна и такая вариация 3SAT, когда язык состоит из таких 3КНФ, которые

• выполнимы
• и в этом выполняющем наборе, в каждой скобке ровно один истинный литерал.

Задача «[[Открытые теоретические задачи|]]»^©

Всего страниц найдено: 53.

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

Бонусная задача

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

Бонусная задача

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

Бонусная задача

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

Бонусная задача

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

Бонусная задача

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

Бонусная задача

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

Бонусная задача

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

Бонусная задача

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

Бонусная задача

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

Бонусная задача

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

Бонусная задача

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

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

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

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

для которого можно показать, что ожидаемый размер

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

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

Задача «Задачи/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-a‎.

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

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

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

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

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

Решите обобщенную версию задачи [[../eupce-2-13]]:

• kn различных купонов, организованных в n непересекающихся наборов из k купонов.
• нужен один купон из каждого набора.

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

• Каждая коробка хлопьев содержит один из 2n различных купонов (купон в каждой коробке выбирается независимо и равномерно случайным образом из 2n).
• Купоны организованы в n пар, так что купоны 1 и 2 составляют пару, купоны 3 и 4 составляют пару и так далее.
• Получив по одному купону из каждой пары, вы можете получить приз.

Какое ожидаемое количество коробок, надо для этого купить?

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

Дважды бросают честный 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-8-a»^©

Алиса и Боб решили заводить детей до тех пор, пока у них не родится девочка или пока у них не будет k ≥ 1 детей.

Предположим, что каждый ребенок будет мальчиком или девочкой независимо с вероятностью 1/2 и что многоплодных родов не бывает.

• Каково ожидаемое число детей женского пола?
• Каково ожидаемое число детей мужского пола?

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

Предположим, что независимо бросают два стандартных шестисторонних кости, X₁ — то, что выпадает на первой, X₂ — на второй, а X — сумма обоих значений.

• 2 ≤ k ≤ 12
• E[X₁ - X₂ | X = k] = ?

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

Предположим, что независимо бросают два стандартных шестисторонних кости, X₁ — то, что выпадает на первой, X₂ — на второй, а X — сумма обоих значений.

E[X₁ | X = 9] = ?

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

Предположим, что независимо бросают два стандартных шестисторонних кости, X₁ — то, что выпадает на первой, X₂ — на второй, а X — сумма обоих значений.

E[X | X₁ = X₂] = ?

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

Предположим, что независимо бросают два стандартных шестисторонних кости, X₁ — то, что выпадает на первой, X₂ — на второй, а X — сумма обоих значений.

E[X | X₁ — четное] = ?

Задача «Задачи/eupce-2-5»^©

Если X — случайная величина с биномиальным распределением B(n, 1/2) для n ≥ 1, покажите, что вероятность того,

что X — четное будет 1/2.

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

Обычные крестики-нолики скучные, при оптимальной стратегии в них выигрывают крестики.

Рассмотрим вероятную модификацию этой игры.

• Как обычно, крестики и нолики ходят по очереди и нолик идет первым. Как обычно, выигрывает тот, кто первый добъется «три в ряд», или ничья, если никто.
• Но на каждом ходе позиция и у крестиков и у ноликов выбирается независимо и равномерно среди свободных квадратов.

Найдите вероятность, выигрыша для «крестиков» и для «ноликов».

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

Обычные крестики-нолики скучные, при оптимальной стратегии в них выигрывают крестики.

Рассмотрим вероятную модификацию этой игры.

• Изначально, бросая честную монетку, разметим каждый из девяти квадратов либо X, либо O.
• Если только один из игроков имеет «три в ряд» → он победил.
• Если оба или никто → ничья.

Определите вероятность, что «X» выиграет.

Задача «Задачи/eupce-1-18»^©

• Есть функция
• и известно что .

Единственный способ вычисления F — использовать таблицу поиска, в которой хранится значения F. К сожалению, злой противник изменил значение 1/5 записей в этой таблице.

Опишите простой рандомизированный алгоритм, который, учитывая входной Z, выводит значение, которое равняется f(z) с вероятностью не менее 1/2.

Ваш алгоритм должен работать для каждого значения Z, независимо от того, какие записи изменил противник.

Дополнительно, предположим, вам разрешено повторить этот ваш начальный алгоритм три раза.

Как этим воспрользоваться, чтобы максимально увеличить вероятность правильного ответа, и какова эта вероятность?

Задача «Задачи/eupce-1-16-d»^©

Рассмотрим игру, основанную на бросках трех стандартных шестисторонних костей.

Цель → получить одинаковое число на всех трех костях, кто первый этого добьется, тот выиграл.

• Игрок начинает с броска всех трех кубиков.
• После первого броска игрок может выбрать одну, две или три кости и бросить их снова.
• После второго броска игрок один из трех кубиков и перебросить его.

Предположим, что игрок использует следующую оптимальную стратегию:

• если все три кости одинаковые → останавливаемся и выигрываем;
• если два кубика совпадают, игрок перебрасывает тот, который «выбивается из коллектива».
• если все не совпадают — перебрасываем их всех.

Рассматривая все возможные возможные выпадения костей, найдите вероятность того, что игрок выиграет.

Задача «Задачи/eupce-1-16-c»^©

Рассмотрим игру, основанную на бросках трех стандартных шестисторонних костей.

Цель → получить одинаковое число на всех трех костях, кто первый этого добьется, тот выиграл.

• Игрок начинает с броска всех трех кубиков.
• После первого броска игрок может выбрать одну, две или три кости и бросить их снова.
• После второго броска игрок один из трех кубиков и перебросить его.

Предположим, что игрок использует следующую оптимальную стратегию:

• если все три кости одинаковые → останавливаемся и выигрываем;
• если два кубика совпадают, игрок перебрасывает тот, который «выбивается из коллектива».
• если все не совпадают — перебрасываем их всех.

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

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

Рассмотрим игру, основанную на бросках трех стандартных шестисторонних костей.

Цель → получить одинаковое число на всех трех костях, кто первый этого добьется, тот выиграл.

• Игрок начинает с броска всех трех кубиков.
• После первого броска игрок может выбрать одну, две или три кости и бросить их снова.
• После второго броска игрок один из трех кубиков и перебросить его.

Предположим, что игрок использует следующую оптимальную стратегию:

• если все три кости одинаковые → останавливаемся и выигрываем;
• если два кубика совпадают, игрок перебрасывает тот, который «выбивается из коллектива».
• если все не совпадают — перебрасываем их всех.

Найдите вероятность того, что ровно два из трех кубиков показывают одинаковое число в первом броске.

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

Рассмотрим игру, основанную на бросках трех стандартных шестисторонних костей.

Цель → получить одинаковое число на всех трех костях, кто первый этого добьется, тот выиграл.

• Игрок начинает с броска всех трех кубиков.
• После первого броска игрок может выбрать одну, две или три кости и бросить их снова.
• После второго броска игрок один из трех кубиков и перебросить его.

Предположим, что игрок использует следующую оптимальную стратегию:

• если все три кости одинаковые → останавливаемся и выигрываем;
• если два кубика совпадают, игрок перебрасывает тот, который «выбивается из коллектива».
• если все не совпадают — перебрасываем их всех.

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

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

Я играю в турнире ракетбола против игрока, против которого раньше не играл, но видел его в игре.

Априори рассматриваю три равновероятные возможности:

• мы одинаково талантливы, каждый из нас в равной степени может выиграть каждую игру;
• Я немного лучше, и поэтому я выигрываю каждую игру независимо с вероятностью 0.6;
• Он немного лучше, и поэтому он выигрывает каждую игру независимо с вероятностью 0.6.

В рокетбол играют, пока один игрок не выиграет три сета. В нашей игре, я выиграл только второй сет, а противник выиграл первый, третий и четвертый.

В апостеорной модели, с какой вероятностью я должен верить, что мой оппонент немного лучше, чем я?

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

• Пытаемся передать один бит (0 или 1) через промежуточные узлы, каждый из которых независимо может инвертировать бит с вероятностью «p».
• Скажем, узел имеет смещение «q», если это , «смещение» будет вещественным числом на отрезке [−1, 1].

Докажите, что прохождение бита через узлы со смещениями «q1» и «q2» эквивалентно прохождению бита через один узел со смещением «q1×q2».

Задача «Задачи/eupce-1-11-c»^©

Пытаемся передать один бит (0 или 1) через «n» промежуточных узлов, каждый из которых независимо

может инвертировать бит с вероятностью «p».

Докажите, что вероятность получения корректного бита:

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

• Честную монету бросили «n» раз.
• Для k>0, найдите верхнюю границу вероятности, что будет последовательность из последовательных орлов.

Задача «Задачи/accept-after-t-steps-in-npc»^©

Язык L состоит из пар (M, t), где

M

одноленточная машина Тьюринга над бинарным алфавитом.

t

число t единичной системе (t единиц).

• Существует вход x, M(x) останавливается и возвращает 1, после t шагов.

Покажите, что это NP-полная задача.

Задача «Задачи/NP-sums»^©

Проверить принадлежность классу следующей задачи: по заданному конечному множеству натуральных чисел, представленных в своей бинарной записи, определить возможность разделения этого множества на два подмножества с одинаковыми суммами.

Задача «Задачи/unary-in-p-then-time2kn-in-time2cn»^©

Докажите, что если каждый унарный язык из NP также лежит в P, то то для любого языка из для какого-либо k, он тажке лежит в для любого c.

Задача «Задачи/dtime-n2-is-closed-carp-reduction»^©

• Класс сложности С замкнут относительно какой-то сводимости, если L→L' и , то .

Рассмотрим класс .

Замкнут ли он относительно полиномиальной сводимости по Карпу?

Задача «Задачи/conp-as-yes»^©

Покажите, что язык L лежит в co-NP тогда и только тогда, если существует недетерминированная машина M, и полином p, такой, что M останавливается за время p(n) для всех входов x длины n, и L состоит точно только из таких строк x, у которых все пути вычисления M(x) приводят к ответу «1».

Задача «Задачи/DHAM3»^©

Пусть

• — задача поиска гамильтонового цикла в графе , где V — делиться на 3.
• — задача подтверждения наличия гамильтонового цикла в таком графе.

Докажите, что и — NP-трудны.

Задача «Задачи/ptas-for-minimal-scheduling»^©

Разработайте PTAS-алгоритм для Планирование Задач на Одинаковых Машинах используя этот подход.

Задача «Задачи/maximum-k-choice-knapsack-dynamic-programming»^©

Придумайте алгоритм динамического программирования, находящий оптимальное решение задачи Maximum Integer k-choice Knapsack.

Задача «Задачи/scheduling-ident-machines-in-npc»^©

Рассмотрим задачу разрешения для оптимизационной задачи Планирование Задач на Одинаковых Машинах («если ли планировка с максимальным временем меньше k»).

Покажите, что эта задача, даже в случае p=2, NP-полна.

Задача «Задачи/USUBSETSUM-IN-P»^©

Вспомним задачу булев-рюкзак выполнимость, и потребуем, чтобы все веса и размер рюкзака задавались в унарной системе ().

Покажите, что тогда язык таких выполнимых рюкзаков, лежит в классе P.

Задача «Задачи/QBEQ-NPC-NPC»^©

Покажите NP-полноту языка совместимых систем квадратичных уравнений в булевых переменных. Т.е. разрешимых систем вида

и где сложение по модулю 2.

Задача «Задачи/NTIME-NlogN-reduction-3SAT»^©

Покажите, что для любого языка , можно построить полиномиальную Карп-сводимость, от слов длины n, к 3SAT-формулам длины .

Задача «Задачи/Свойство Sigma i=PH»^©

.

Задача «Задачи/P^BPP»^©

Какой класс будет

Задача «Задачи/\Sigma^p k=NP^(\Sigma^p (k-1))»^©

Докажите

Задача «Задачи/P^(\Sigma^p k)=P^(\Pi^p k)»^©

Докажите

Задача «Задачи/Порядок закачек — NPC»^©

Представим распределенный сервис стриминга видеофильмов. Центральный сервер с полной БД фильмов получает от периферийных кеширующих узлов запросы на требуемые фильмы и ориентировочные сроки, когда люди собираются их посмотреть.

Однако пропускная способность от сервера с дисками к внешнему миру ограничена, и требуется составить работающее расписание отгрузки фильмов.

Конкретно, узел контроля планирования получает n-заданий вида:

• «начать_не_раньше, закончить_не_позже, размер_фильма»_i, 1<=i<=n
• максимальная пропускная способность не больше МаксКанал

И говорит «OK» (или «Паника-Паника!» в противном случае), если существует такое расписание из n команд отгрузки, соответствующих заданию (1<=i<=n ):

• «время_начала, время_окончания, ширина_канала»_i,
• время_начала_i >= начать_не_раньше_i
• время окончания_i <= закончить_не_позже_i
• ширина_канала_i <= МаксКанал
• ширина_канала*(время_окончания — время_начала)_i >= размер_фильма_i

Докажите NP-полноту задачи.

Hint: Можно через «Рюкзак-выполнимость» или «SUBSET-SUM»

Задача «Задачи/Жадное вершинное покрытие для почти всех исходных данных»^©

Рассмотрим жадный алгоритм для вершинного покрытия («брать вершину максимальной степени, ребра удалять»), на случайных графах, у которых

• n-вершин
• ребра между любой парой вершин возникают с вероятностью p.

Какова точность алгоритма для почти всех исходных данных?

(упрощенный вариант — для фиксированного p=½).

Задача «Задачи/Квадрат букв»^©

Задача «Задачи/P^BPP»^©

Какой класс будет

Задача «Задачи/\Sigma^p k=NP^(\Sigma^p (k-1))»^©

Докажите

Задача «Задачи/Свойство Sigma i=PH»^©

.

Задача «Задачи/DHAM3»^©

Пусть

• — задача поиска гамильтонового цикла в графе , где V — делиться на 3.
• — задача подтверждения наличия гамильтонового цикла в таком графе.

Докажите, что и — NP-трудны.

Задача «Задачи/NTIME-NlogN-reduction-3SAT»^©

Покажите, что для любого языка , можно построить полиномиальную Карп-сводимость, от слов длины n, к 3SAT-формулам длины .

Задача «Задачи/QBEQ-NPC-NPC»^©

Покажите NP-полноту языка совместимых систем квадратичных уравнений в булевых переменных. Т.е. разрешимых систем вида

и где сложение по модулю 2.

Задача «Задачи/USUBSETSUM-IN-P»^©

Вспомним задачу булев-рюкзак выполнимость, и потребуем, чтобы все веса и размер рюкзака задавались в унарной системе ().

Покажите, что тогда язык таких выполнимых рюкзаков, лежит в классе P.

Задача «Задачи/accept-after-t-steps-in-npc»^©

Язык L состоит из пар (M, t), где

M

одноленточная машина Тьюринга над бинарным алфавитом.

t

число t единичной системе (t единиц).

• Существует вход x, M(x) останавливается и возвращает 1, после t шагов.

Покажите, что это NP-полная задача.

Задача «Задачи/conp-as-yes»^©

Покажите, что язык L лежит в co-NP тогда и только тогда, если существует недетерминированная машина M, и полином p, такой, что M останавливается за время p(n) для всех входов x длины n, и L состоит точно только из таких строк x, у которых все пути вычисления M(x) приводят к ответу «1».

Задача «Задачи/scheduling-ident-machines-in-npc»^©

Рассмотрим задачу разрешения для оптимизационной задачи Планирование Задач на Одинаковых Машинах («если ли планировка с максимальным временем меньше k»).

Покажите, что эта задача, даже в случае p=2, NP-полна.

Задача «Задачи/unary-in-p-then-time2kn-in-time2cn»^©

Докажите, что если каждый унарный язык из NP также лежит в P, то то для любого языка из для какого-либо k, он тажке лежит в для любого c.

Задача «Задачи/Квадрат букв»^©

Задача «Задачи/Порядок закачек — NPC»^©

Представим распределенный сервис стриминга видеофильмов. Центральный сервер с полной БД фильмов получает от периферийных кеширующих узлов запросы на требуемые фильмы и ориентировочные сроки, когда люди собираются их посмотреть.

Однако пропускная способность от сервера с дисками к внешнему миру ограничена, и требуется составить работающее расписание отгрузки фильмов.

Конкретно, узел контроля планирования получает n-заданий вида:

• «начать_не_раньше, закончить_не_позже, размер_фильма»_i, 1<=i<=n
• максимальная пропускная способность не больше МаксКанал

И говорит «OK» (или «Паника-Паника!» в противном случае), если существует такое расписание из n команд отгрузки, соответствующих заданию (1<=i<=n ):

• «время_начала, время_окончания, ширина_канала»_i,
• время_начала_i >= начать_не_раньше_i
• время окончания_i <= закончить_не_позже_i
• ширина_канала_i <= МаксКанал
• ширина_канала*(время_окончания — время_начала)_i >= размер_фильма_i

Докажите NP-полноту задачи.

Hint: Можно через «Рюкзак-выполнимость» или «SUBSET-SUM»

Задача «Задачи/ptas-for-minimal-scheduling»^©

Разработайте PTAS-алгоритм для Планирование Задач на Одинаковых Машинах используя этот подход.

Задача «Задачи/dtime-n2-is-closed-carp-reduction»^©

• Класс сложности С замкнут относительно какой-то сводимости, если L→L' и , то .

Рассмотрим класс .

Замкнут ли он относительно полиномиальной сводимости по Карпу?

Задача «Задачи/maximum-k-choice-knapsack-dynamic-programming»^©

Придумайте алгоритм динамического программирования, находящий оптимальное решение задачи Maximum Integer k-choice Knapsack.

Задача «Задачи/Жадное вершинное покрытие для почти всех исходных данных»^©

Рассмотрим жадный алгоритм для вершинного покрытия («брать вершину максимальной степени, ребра удалять»), на случайных графах, у которых

• n-вершин
• ребра между любой парой вершин возникают с вероятностью p.

Какова точность алгоритма для почти всех исходных данных?

(упрощенный вариант — для фиксированного p=½).

Задача «Задачи/P^(\Sigma^p k)=P^(\Pi^p k)»^©

Докажите

Задача «Задачи/ex-turing-copy-lowerbound»^©

Задача «Задачи/ex-turing-max-time-grows»^©

Задача «Задачи/ex-union-decideable-decideable»^©

Задача «Задачи/ex-unsolvable-exists»^©

Докажите, что существуют невычислимые по Тьюрингу функции y=f(x), используя мощностные соображения.

Задача «Задачи/Возведение в степень за логарифмическое время»^©

Формально об алгоритмах. Вычислительные модели.Возведение в степень за логарифмическое время

Постройте RAM-программу, которая по входу (a,b), где a,b > 1, вычисляет a^b. Время работы программы должно быть О(log b)

Задача «Задачи/Конкатенция P»^©

Задача «Задачи/Разрешимость конкатенации»^©

Задача «Задачи/Теорема о неподвижной точке»^©

Задача «Задачи/сolorization»^©

Не используя факта -полноты задачи , доказать, что задача отыскания раскраски графа в три цвета сводится по Куку к задаче проверки три-раскрашиваемости графа

Задача «Задачи/ex-greedy-sat-is-2-approx»^©

Покажите, что алгоритм Greedy algorithm for SAT находит 2-приближенное решение для MAX SAT (т.е. не хуже оптимального больше чем в два раза).

Задача «Задачи/ex-greedy-sat-is-2-approx-weighted»^©

Как задача [[../ex-greedy-sat-is-2-approx]], только покажите, что 2-приближенность сохранится, если будет MAX-SAT-Weighted

Задача «Задачи/ex-sat-average-expect-max-nk»^©

Докажите, что (определения см. в тексте лекций или книге):

Задача «Задачи/ex-sat-dynp-bad-data»^©

Какие входные данные для алгоритма «alg-sat-dynp» заставят его работать экспоненциально долго?

Задача «Задачи/ex-sat-dynp-good-data»^©

На каких входных данных алгоритм из этой темы, будет работать ?

Задача «Задачи/Проблемы определения «в среднем»»^©

Вероятностное распределение

Вероятность появления каждой входной строки.

вход длины n.

Задача «Задачи/ex-packing-average-bad-and-good-data»^©

• Какие входные данные для алгоритма динамического программирования для упаковки

заставят его работать экспоненциально долго?

• А какие — за ?

Задача «Задачи/MTSP NP-полна»^©

Покажите, что метрическая задача коммивояжера NP-полна.

Задача «Задачи/nearest-neighbour-not-good-for-tsp»^©

Неграмотный программист, недолго погуглив, решил использовать для задачи оптимизационной коммивояжера TSP алгоритм Nearest neighbour

Докажите, что для любой константы c>1 и для любого n>3,

существует экземпляр TSP с n-городами, на котором этот алгоритм будет находить решение, в С раз хуже (т.е. больше).

Задача «Задачи/nearest-neighbour-tsp-infty-bas-cases»^©

Начальная ситуация как в Приближенный алгоритм для метрической задачи коммивояжера/Задачи/nearest-neighbour-not-good-for-tsp.

Покажите, что для любой константы C, таких плохих входных данных (для разных n), бесконечное количество.

Подсказка: для любого i>0, сконструируйте входную задачу, где NN-алгоритм будет находить решение, минимум в (i+2)/6 раз большее оптимального.

Задача «Задачи/Плохой пример»^©

Придумайте пример, входной метрический граф, на котором алгоритм Кристофидеса дает наихудшую точность, т.е. 3/2.

Задача «Задачи/Четность вершин нечетной степени в MST»^©

Задача «Задачи/sorting-convex-hull»^©

Задача «[[Уникальность минимального остовного дерева|]]»^©

Задача «Задачи/ex-exists-enumeration-of-halts»^©

Существует ли алгоритм, который выписывает одну за другой все машины Тьюринга, которые останавливаются, будучи запущенными на пустой ленте?

Задача «Задачи/ex-halt-empty-tape»^©

Докажите, что также неразрешима версия задачи HALT — «остановка на пустом слове», т.е. для данной МТ T определить, остановится ли она на пустом слове.

Задача «Задачи/ex-lost»^©

Задача «Задачи/ex-no-enumeration-of-cycled»^©

Докажите, что не существует алгоритма, который выписывает одну за другой все машины Тьюринга, которые не останавливаются, будучи запущенными на пустой ленте.

Задача «Задачи/ex-obfuscation-undecidable»^©

Докажите, что неразрешима «Проблема недостижимого кода» - нет алгоритма, который для заданной машины Тьюринга T и ее состояния выясняет: попадет ли машина в это состояние хотя бы для одного входного слова x?

Задача «Задачи/Tautology in coNP»^©

Задача «Задачи/Unary-lang-and-NP»^©

Рассмотрим языки, в которых строки-слова состоят только из последовательности нулей. Покажите, что если существует один из таких языков , что , то .

Задача «Задачи/Vcover-clique»^©

Задача «Задачи/a^b eq c mod d in P»^©

Задача «Задачи/double-sat»^©

Язык L состоит из формул SAT, для которых есть по крайней мере два выполняющих набора. Покажите, что .

Задача «Задачи/ex-2sat-in-p»^©

Покажите, что задача 2SAT лежит в P.

Задача «Задачи/ex-equiv-in-3knf»^©

Выразите логическое отношение эквивалентности в виде 3-КНФ формулы.

Задача «Задачи/ex-hamilton-cycle-in-np»^©

Покажите, что

• задача распознавания гамильтоновых графов (т.,е. графов, содержащих гамильтонов цикл) принадлежит NP,
• а задача распознавания негамильтоновых графов (т.,е. графов, не содержащих ни одного гамильтонова цикла)

принадлежит coNP.

Задача «Задачи/ex-limited-3sat-npc»^©

Рассмотрим ограниченную версию задачи 3SAT, где на КНФ-формулу дополнительно наложено ограничение, что в ней каждая переменная может входить не больше трех раз, причем каждый литерал - не больше двух.

Покажите, что и эта задача NP-полна.

Задача «Задачи/ex-p-in-np-and-conp»^©

Покажите, что .

Задача «Задачи/ex-polynomial-diofant-is-in-np»^©

Задача «Задачи/ex-triange-in-p»^©

Придумайте полиномиальный алгоритм для проверки, есть ли в заданном графе хотя бы один «треугольник».

Задача «Задачи/k-подсемейство множеств - NPC»^©

Докажите NP-полноту следующей проблемы. Исходное данное: конечное семейство конечных множеств и натуральное . Существует ли подсемейство, состоящее из попарно непересекающихся множеств?

Задача «Задачи/knights-np-complete»^©

Задача «Задачи/nonapprox TSP»^©

Покажите, что если то для задачи коммивояжера не существует полиномиального приближенного алгоритма с мультипликативной ошибкой не превышающей величины, зависящей только от числа вершин графа.

Задача «Задачи/np-closed-under-coding»^©

K(L) — кодировка.

Докажите, что класс NP замкнут относительно кодировок.

Т.е. покажите, что если , а KOD — какая-то кодировка над алфавитом L, то

Задача «Задачи/p-looks-unclosed-under-coding»^©

K(L) — кодировка.

Докажите, что класс P замкнут относительно кодировок тогда и только тогда, если P=NP.

Задача «Задачи/strong-nmt-good-characterization»^©

Пусть есть язык L, для которого

• есть некая МТ M, возвращает «0», «1», «?».
• для любого , все пути вычисления M(x) за полиномиальное время приводят к ответам «1» или «?», при том есть хотя бы один путь к «1».
• для любого , все пути вычисления M(x) за полиномиальное время приводят к ответам «0» или «?», при том есть хотя бы один путь к «0».

Покажите, что

Задача «Задачи/Гамильтонов граф»^©

Покажите, что если язык ГАМИЛЬТОНОВ ГРАФ ∈ P , то за полиномиальное время можно не только определить, что граф гамильтонов, но и найти в нем какой-нибудь гамильтонов цикл (если он существует).

Задача «Задачи/НМТ для Subset Sum»^©

Постройте недетерминированный полиномиальный алгоритм для задачи Subset Sum

Задача «Задачи/Раскраска графа в два цвета»^©

Задача «Задачи/Язык планарных графов»^©

Задача «Задачи/tsp-greedy-bad»^©

Докажите, что жадный алгоритм в задаче коммивояжера, т.е. алгоритм стартующий с некоторой вершины и пытающийся добавлять наиболее дешевые ребра к еще непосещенным вершинам, не гарантирует нахождение оптимального решения.

Задача «Задачи/Поиск решения уравнения за полиномиальное время»^©

Задача «Задачи/Корректность алгоритма Люби»^©

Почему в алгоритме Люби построенное множество:

• а) является независимым

• б) максимальным по включению

Задача «Задачи/NP!=co-NP»^©

Доказать, что NP ≠ coNP, если P ≠ NP

Задача «Задачи/NP^SAT=\Sigma^p 2»^©

Докажите

Задача «Задачи/NP \cup co-NP \subseteq P^NP»^©

Докажите

Задача «Задачи/PH \subseteq PSPACE»^©

Докажите, что

Задача «Задачи/PH collapse if PHC exists»^©

Задача «Задачи/P\poly contains unsolvable»^©

Показать, что содержит некоторые невычислимые функции.

Задача «Задачи/P^SAT=P^NP»^©

Докажите

Задача «Задачи/3ESAT-NPC»^©

Покажите, что 3ESAT — NP-полная задача.

Задача «Задачи/3SAT-TAUTOLOGY-reducibility»^©

Покажите, что если 3SAT и TAUTOLOGY полиномиально сводятся к друг другу по Карпу, то NP = CoNP.

Задача «Задачи/3КНФ→Клика»^©

Постройте полиномиальную сводимость задачи 3SAT к задаче CLIQUE.

Задача «Задачи/3КНФ→Клика (сохраняя число решений)»^©

Получите сводимость как в Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Задачи/3КНФ→Клика, но дополнительно требуется, чтобы количество решений сохранялось.

Т.е. если 3КНФ F полиномиально преобразуется в (граф G, число k), то количество выполняющих наборов переменных для F равно количеству клик размера k в графе G).

Задача «Задачи/HALT-and-NP»^©

HALT = {(M,x)} — язык пар (М,x), таких, что машина Тьюринга M останавливается на x за конечное число шагов.

Является ли HALT:

• NP-полным
• NP-трудным
• PSPACE-полным

Задача «Задачи/NPC «k бригад обслуживания»»^©

Задача «Задачи/Packing=MaxClique»^©

Покажите, что задача об упаковке (в заданном семействе подмножеств найти максимальное число попарно непересекающихся подмножеств) полиномиально эквивалентна задаче о нахождении максимальной клики в графе.

Задача «Задачи/ex-max-maxmatching-1-2»^©

Найдите приближенный алгоритм с точностью для нахождения паросочетания максимального размера.

Задача «Задачи/ex-min-maxmatching-1-2»^©

---

---

---

Задача «Задачи/exersize-greedy-covering-1»^©

---

Беру задачу «Жадный алгоритм в задачах о покрытии/Задачи/exersize-greedy-covering-1» себе!

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

---

---

---

Задача «Задачи/fist-fit-for-vector-packing»^©

---

Беру задачу «Жадный алгоритм в задачах о покрытии/Задачи/fist-fit-for-vector-packing» себе!

Рассмотрим многомерное обобщение задачи Упаковки в контейнеры, называемое Vector Packing.

Там размеры всех предметов → d-мерный вектор,

контейнеры тоже d-мерный вектора (V,…,V), и цель — упаковать все предметы в минимум контейнеров, так, чтобы упакованные в контейнеро предметы, после векторного суммирования^[1], не вылезали за его границы.

Покажите, что приближенный алгоритм, типа First Fit, обобщенный для многомерности,

найдет (d+1)-оптимальное решение.

---

---

---

Задача «Задачи/graph-coloring-smallest-last-not-good»^©

---

Беру задачу «Жадный алгоритм в задачах о покрытии/Задачи/graph-coloring-smallest-last-not-good» себе!

Покажите, что для существенно больших n, существует раскрашиваемый в три цвета граф из n вершин, для которого алгоритм Smallest Last будет использовать цветов.

---

---

---

Задача «Задачи/internal-cover»^©

---

Беру задачу «Жадный алгоритм в задачах о покрытии/Задачи/internal-cover» себе!

---

---

---

Задача «Задачи/k-cover»^©

---

Беру задачу «Жадный алгоритм в задачах о покрытии/Задачи/k-cover» себе!

Предложите k-приближенный полиномиальный алгоритм для задачи о покрытии, когда известно, что в исходных данных, каждый элемент покрывается не более, чем k подмножествами.

---

---

---

Задача «Задачи/lpt-rule-for-scheduling»^©

---

Беру задачу «Жадный алгоритм в задачах о покрытии/Задачи/lpt-rule-for-scheduling» себе!

Рассмотрим задачу Планирование Задач на Одинаковых Машинах и применим к ней LPT^[2]-эвристику:

• отсортировать задачи по убыванию длины
• для каждой задачи:
  • применять жадный алгоритм загрузки: бросать задачу на самую малозагруженную машину

Докажите, что в,

• OPT(x) — значение этого оптимального решения.
• — значение, найденное алгоритмом

---

---

---

Задача «Задачи/lpt-rule-for-scheduling-min-lj»^©

---

Беру задачу «Жадный алгоритм в задачах о покрытии/Задачи/lpt-rule-for-scheduling-min-lj» себе!

Рассмотрим задачу Планирование Задач на Одинаковых Машинах и применим к ней LPT^[3]-эвристику:

• отсортировать задачи по убыванию длины
• для каждой задачи:
  • применять жадный алгоритм загрузки: бросать задачу на самую малозагруженную машину

Докажите, что в случае этот алгоритм находит оптимальное решение. (OPT(x) — значение этого оптимального решения).

---

---

---

Задача «Задачи/lpt-rule-for-scheduling-p-is-2»^©

---

Беру задачу «Жадный алгоритм в задачах о покрытии/Задачи/lpt-rule-for-scheduling-p-is-2» себе!

Рассмотрим задачу Планирование Задач на Одинаковых Машинах и применим к ней LPT^[4]-эвристику:

• отсортировать задачи по убыванию длины
• для каждой задачи:
  • применять жадный алгоритм загрузки: бросать задачу на самую малозагруженную машину

Докажите, что в случае p=2,

• OPT(x) — значение этого оптимального решения.
• — значение, найденное алгоритмом.

См. также Жадный алгоритм в задачах о покрытии/Задачи/lpt-rule-for-scheduling

---

---

---

Задача «Задачи/minimum-hitting-set-k»^©

---

Беру задачу «Жадный алгоритм в задачах о покрытии/Задачи/minimum-hitting-set-k» себе!

Рассмотрим задачу Minimum Hitting Set.

Пусть k — максимальный размер подмножеств из C.

Постройте k-оптимальный полиномиальный алгоритм.

Hint

Minimum Hitting Set является обобщением минимального вершинного покрытия.

---

---

---

Задача «Задачи/minimum-multicover-approx-with-linear-relaxation»^©

---

Беру задачу «Жадный алгоритм в задачах о покрытии/Задачи/minimum-multicover-approx-with-linear-relaxation» себе!

Рассмотрим задачу Minimum Multicover.

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

P-оптимальное решение, где

---

---

---

Задача «Задачи/vertex-cover»^©

---

Беру задачу «Жадный алгоритм в задачах о покрытии/Задачи/vertex-cover» себе!

Для известного 2-приближенного алгоритма для задачи о вершинном покрытии привести пример графа, для которого «этот алгоритм с паросочетаниями» строит покрытие с числом вершин

---

---

---

Задача «Задачи/Greedy-Subset-Sum»^©

---

Беру задачу «Жадный алгоритм в задаче о рюкзаке/Задачи/Greedy-Subset-Sum» себе!

Рассмотрим алгоритм, который для любого набора камней произвольного веса разбивает их на две кучи по принципу «очередной камень кладем туда, где суммарный вес меньше». Докажите, что этот приближенный алгоритм имеет мультипликативную ошибку не превышающую 2 (целевая функция — минимизировать максимум по весам в обоих кучах).

---

---

---

Задача «Задачи/sorted weight and cost»^©

---

Беру задачу «Жадный алгоритм в задаче о рюкзаке/Задачи/sorted weight and cost» себе!

Предположим, что в задаче о рюкзаке порядок сортировки по увеличению веса совпадает с порядком сортировки по уменьшению cтоимости. Сформулируйте эффективный алгоритм для поиска оптимального решения этой разновидности задачи о рюкзаке и обоснуйте его корректность.

---

---

---

Задача «Задачи/Нижняя оценка точности модифицированного жадного»^©

---

Беру задачу «Жадный алгоритм в задаче о рюкзаке/Задачи/Нижняя оценка точности модифицированного жадного» себе!

Приведите пример данных, на которых модифицированный жадный алгоритм дает (хотя бы в пределе) наихудшую оценку точности.

---

---

---

Задача «Задачи/Тупая жадность - очень плохо»^©

---

Беру задачу «Жадный алгоритм в задаче о рюкзаке/Задачи/Тупая жадность - очень плохо» себе!

---

---

---

Задача «[[Корректность алгоритма Прима|]]»^©

---

Беру задачу «Корректность алгоритма Прима» себе!

Докажите корректность алгоритма Прима построения минимального остовного дерева взвешенного связного неориентированного графа.

---

---

---

Задача «Задачи/ex-dijksta-not-work-on-negative-weight»^©

---

Беру задачу «Несложно о сложности. Примеры алгоритмов/Задачи/ex-dijksta-not-work-on-negative-weight» себе!

Приведите пример графа с отрицательными весами, но без циклов отрицательной длины, для которого алгоритм Дейкстры даст неправильный ответ.

---

---

---

Задача «Задачи/ex-fast-power»^©

---

Беру задачу «Несложно о сложности. Примеры алгоритмов/Задачи/ex-fast-power» себе!

---

---

---

Задача «Задачи/ex-network-reliability»^©

---

Беру задачу «Несложно о сложности. Примеры алгоритмов/Задачи/ex-network-reliability» себе!

---

---

---

Задача «Задачи/l-eq-p-then-pspace-eq-exptime»^©

---

Беру задачу «Временная и пространственная сложность алгоритмов/Задачи/l-eq-p-then-pspace-eq-exptime» себе!

Покажите, что если DLOGSPACE = P, то PSPACE = EXPTIME.

---

---

---

Задача «Задачи/st-connectivity-log-diameter»^©

---

Беру задачу «Временная и пространственная сложность алгоритмов/Задачи/st-connectivity-log-diameter» себе!

---

---

---

Задача «Задачи/Машина Тьюринга. Количество.»^©

---

Беру задачу «Временная и пространственная сложность алгоритмов/Задачи/Машина Тьюринга. Количество.» себе!

---

---

---

Задача «Задачи/замки и ключи»^©

---

Беру задачу «Временная и пространственная сложность алгоритмов/Задачи/замки и ключи» себе!

---

---

---

Задача «Задачи/Dynamic Voltage Scaling»^©

---

Беру задачу «Динамическое программирование для задачи о рюкзаке/Задачи/Dynamic Voltage Scaling» себе!

DVS (Dynamic Voltage Scaling) — технология позволяет снижать напряжение на процессоре, и добиваться экономии электроэнергии за счет увеличения времени выполнения задачи.

Пусть процессор поддерживает два уровня напряжения — .

Есть набор из n задач, каждая из которых имеет энергоемкость и время выполнения для обоих режимов~--- т.\,е. :

энергоемкости

и

длительности

и .

Нужно выполнить все задачи на одном процессоре за время не более T, при этом добиться минимального энергопотребления.

Сведите задачу к классическому оптимизационному рюкзаку.

---

---

---

Задача «Задачи/multidimentional-knapsack-dynamic-programming»^©

---

Беру задачу «Динамическое программирование для задачи о рюкзаке/Задачи/multidimentional-knapsack-dynamic-programming» себе!

Придумайте алгоритм динамического программирования для Maximum Integer d-dimentional Knapsack.

---

---

---

Задача «Задачи/workaholic»^©

---

Беру задачу «Динамическое программирование для задачи о рюкзаке/Задачи/workaholic» себе!

Каждый день можно выбирать между

• отдыхом,
• легкой работой
• или тяжелой работой .

Перед днем тяжелой работы требуется день отдыхать, то есть, если работать день , то нужно отдыхать день .

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

Цель, разумеется, выполнить максимальный объем работ.

• Простой жадный алгоритм для этой задачи будет сравнивать с .
  • Если тяжелая работа выгоднее, тогда отдыхаем день и выполняем тяжелую в , иначе выполняем легкую.
  • Затем рассматриваем день.

Покажите, что для любого $k$, можно представить входные данные , на которых жадный алгоритм выдаст в раз худшее решение.

• Разработайте оптимальный полиномиальный алгоритм, чтобы найти максимальный объем работ за дней, когда известны () для каждого дня.

---

---

---

Задача «Задачи/Гвоздики»^©

---

Беру задачу «Динамическое программирование для задачи о рюкзаке/Задачи/Гвоздики» себе!

На прямой дощечке вбиты N гвоздиков.

Любые два гвоздика можно соединить ниточкой.

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

Построить полиномиальный от N алгоритм решающий задачу.

---

---

---

Задача «Задачи/Задача о построении дерева»^©

---

Беру задачу «Динамическое программирование для задачи о рюкзаке/Задачи/Задача о построении дерева» себе!

---

---

---

Задача «Задачи/Копейка рубль бережет»^©

---

Беру задачу «Динамическое программирование для задачи о рюкзаке/Задачи/Копейка рубль бережет» себе!

---

---

---

Задача «Задачи/Худший случай для алгоритма Немхаузера Ульмана»^©

---

Беру задачу «Динамическое программирование для задачи о рюкзаке/Задачи/Худший случай для алгоритма Немхаузера Ульмана» себе!

Придумайте входные наборы для алгоритма Немхаузера-Ульмана, на которых он будет работать экспоненциальное время.

---

---

---

Задача «Задачи/Худший случай для алгоритма с отбором «дорогих» решений»^©

---

Беру задачу «Динамическое программирование для задачи о рюкзаке/Задачи/Худший случай для алгоритма с отбором «дорогих» решений» себе!

Придумайте входные наборы для этого алгоритма, на которых он будет работать экспоненциальное время.

---

---

---

Задача «Задачи/Худший случай для алгоритма с отбором «легких» решений»^©

---

Беру задачу «Динамическое программирование для задачи о рюкзаке/Задачи/Худший случай для алгоритма с отбором «легких» решений» себе!

Придумайте входные наборы для этого алгоритма, на которых он будет работать экспоненциальное время.

---

---

---

Задача «Задача о покрытии отрезков точками»^©

---

Беру задачу «Жадные алгоритмы/Задача о покрытии отрезков точками» себе!

---

---

---

Задача «Задачи/Hitting-set»^©

---

Беру задачу «Жадный алгоритм в задачах о покрытии/Задачи/Hitting-set» себе!

Предложите детерминированный приближенный алгоритм для Minimum Hitting Set и оцените его точность.

Решение, по возможности, оформите в виде jupyter notebook.

---

---

---

Задача «Задачи/bin packing problem-first-fit-sometimes-better-than-best-fit»^©

---

Беру задачу «Жадный алгоритм в задачах о покрытии/Задачи/bin packing problem-first-fit-sometimes-better-than-best-fit» себе!

Рассмотрим Bin Packing Problem и алгоритмы (там же по ссылке) first fit и best fit.

Найдите примеры входных данных, когда first fit лучше best fit.

---

---

---

Задача «Задачи/bin packing problem-maximize»^©

---

Беру задачу «Жадный алгоритм в задачах о покрытии/Задачи/bin packing problem-maximize» себе!

Рассмотрим Bin Packing Problem и модификацию этой задачи — пусть у нас можно потратить эти самые m контейнеров объема V, нет задачи упаковать все предметы, но надо постараться максимизировать число упакованных предметов.

И пусть суммарный вес всех n предметов не больше M*V.

Рассмотрим простой последовательный алгоритм для этого, типа first fit.

• Берем предметы в исходном порядке
• Пытаемся упаковать каждый в первый попавшийся контейнер, в который он лезет.
• Если не лезет ни в один из m, контейнеров, выкидываем этот предмет.

Докажите, что этот алгоритм упакует как минимум n/2 предметов.

---

---

---

Задача «Задачи/chromatic-numbers-for-graph-with-degree»^©

---

Беру задачу «Жадный алгоритм в задачах о покрытии/Задачи/chromatic-numbers-for-graph-with-degree» себе!

---

---

---

Задача «Задачи/chromatic-numbers-for-graphs»^©

---

Беру задачу «Жадный алгоритм в задачах о покрытии/Задачи/chromatic-numbers-for-graphs» себе!

---

---

---

Задача «Задачи/ex-acyclic-subgraph-1-2»^©

---

Беру задачу «Жадный алгоритм в задачах о покрытии/Задачи/ex-acyclic-subgraph-1-2» себе!

Решение, по возможности, оформите в виде jupyter notebook.

---

---

---

Задача «Задачи/ex-greedy-covering-bound-asymptotic»^©

---

Беру задачу «Жадный алгоритм в задачах о покрытии/Задачи/ex-greedy-covering-bound-asymptotic» себе!

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

---

---

---

Задача «Задачи/ex-greedy-k-covering-bound-asymptotic»^©

---

Беру задачу «Жадный алгоритм в задачах о покрытии/Задачи/ex-greedy-k-covering-bound-asymptotic» себе!

---

---

---

Задача «Задачи/ex-zpp-notnull»^©

---

Беру задачу «Вероятностные вычисления. Классы RP, coRP, ZPP, BPP/Задачи/ex-zpp-notnull» себе!

---

---

---

Задача «Задачи/las-vegas-k-ammplification»^©

---

Беру задачу «Вероятностные вычисления. Классы RP, coRP, ZPP, BPP/Задачи/las-vegas-k-ammplification» себе!

Пусть A — вероятностный алгоритм, возращающий или правильный ответ f(x), или «?».

• P(A(x)=f(x)) >= p

Алгоритм B — вызывает A, пока не добьется определенного ответа, но не больше k раз.

Оцените k(q) — количество повторений для заданного уровня вероятности правильного ответа q в алгоритме B.

---

---

---

Задача «Задачи/mc-amplification»^©

---

Беру задачу «Вероятностные вычисления. Классы RP, coRP, ZPP, BPP/Задачи/mc-amplification» себе!

• A — Монте-Карло алгоритм с вероятностью правильного вычисления f(x):

Сколько k(|x|) повторений вызова A надо сделать, чтобы добится вероятности правильного вычисления большей (1-q)?

Если:

---

---

---

Задача «Задачи/random-walk-for-directed-graph»^©

---

Беру задачу «Вероятностные вычисления. Классы RP, coRP, ZPP, BPP/Задачи/random-walk-for-directed-graph» себе!

Покажите, что метод случайного блуждания не работает для решения задачи связности на ориентированных графах.

Представьте пример ориентированного графа c n вершинами, в котором даже есть путь из s в t, но матожидание нахождения этого или другого пути s→t будет .

---

---

---

Задача «Задачи/Необратимое семейство перестановок»^©

---

Беру задачу «Вероятностные вычисления. Классы RP, coRP, ZPP, BPP/Задачи/Необратимое семейство перестановок» себе!

Доказать, что существует необратимое семейство перестановок (под перестановками подразумеваются биекции).

Необратимость означает, что для любого вероятностного полиномиального алгоритма для всех достаточно больших вероятность события меньше (случайно взятый длины и случайное бросание алгоритма).

---

---

---

Задача «Задачи/Casino-n-k»^©

---

Беру задачу «Вероятность/Задачи/Casino-n-k» себе!

Игрок приходит в казино с k долларами и играет в игру, где на каждом шаге можно или выиграть 1 доллар, или проиграть 1 доллар с равной вероятностью. Игрок играет до тех пор, пока не проиграет все деньги или пока не выиграет определенную сумму . Какова вероятность, что игрок проиграет все деньги?

---

---

---

Задача «Задачи/Curse-of-dimensionality»^©

---

Беру задачу «Вероятность/Задачи/Curse-of-dimensionality» себе!

---

---

---

Задача «Задачи/alice-bob-three-strange-dice»^©

---

Беру задачу «Вероятность/Задачи/alice-bob-three-strange-dice» себе!

После обеда, Алиса и Боб решают, кому платить.

Алиса достала из кармана три честные (все грани выпадают равновероятно), но нестандартные кости с следующими цифрами на гранях:

A

1, 1, 6, 6, 8, 8

B

2, 2, 4, 4, 9, 9

C

3, 3, 5, 5, 7, 7

Правила игры просты:

• Участники берут по одной кости.
• Выбранные кости бросаются
• Проигравший — у кого цифра меньше (одинаковых быть не может), он и платит за обед.

Алиса благородно представляет право выбора первой кости Бобу.

Покажите, что несмотря на это «благородство», что вероятность выигрыша Алисы больше ½.

---

---

---

Задача «Задачи/coin-game-n-k»^©

---

Беру задачу «Вероятность/Задачи/coin-game-n-k» себе!

Двое играют в игру, бросая честную монету, — каждый раз выигрывает тот, кому выпал «орел». Игра заканчивается, когда кто-нибудь выиграет n-раз.

Какова вероятность, что проигравший к концу игры выиграет k-раундов?

---

---

---

Задача «Задачи/coin-ten-times»^©

---

Беру задачу «Вероятность/Задачи/coin-ten-times» себе!

Бросаем честную монетку 10 раз. Найдите вероятность следующих событий:

• Одинаковое число «орлов» и «решек».
• Больше «орлов», чем «решек».
• Для всех 0<i<6, i-й и 11-i-й броски будут одинаковы.
• Будет выброшено подряд четыре «орла».

---

---

---

Задача «Задачи/estimate-probability»^©

---

Беру задачу «Вероятность/Задачи/estimate-probability» себе!

Имеется приближенный алгоритм, который выдает верное значение с вероятностью . Покажите, что можно уменьшить вероятность ошибки с до любой желаемой , выполнив некоторое число экспериментов и взяв среднее значение. Оценить сверху как функцию от .

---

---

---

Задача «Задачи/random-cloning-n-times»^©

---

Беру задачу «Вероятность/Задачи/random-cloning-n-times» себе!

В аквариуме плавают существа типа A и B. Изначально их двое — A и B. Каждым ходом мы случайно выбираем одно существо, светим на него лучем жизни, после чего оно клонируется (превращается в двух существ такого же типа).

Покажите, что после n-ходов, число существ типа A будет равновероятно распределено между 1 и n+1.

---

---

---

Задача «Задачи/roll-two-dice»^©

---

Беру задачу «Вероятность/Задачи/roll-two-dice» себе!

Бросаем две обычных шестигранных игральных кости. Кости честные, исходы бросков независимы. Найдите вероятнотсь следующих событий:

• Выпадут два одинаковых результата.
• Число на первой кости больше, чем на второй.
• Сумма обоих результатов — четная.
• Произведение результатов — квадрат какого-то целого числа.

---

---

---

Задача «Задачи/PSPACE in EXPTIME»^©

---

Беру задачу «Временная и пространственная сложность алгоритмов/Задачи/PSPACE in EXPTIME» себе!

Докажите, что .

---

---

---

Задача «Задачи/QSAT in PSPACE»^©

---

Беру задачу «Временная и пространственная сложность алгоритмов/Задачи/QSAT in PSPACE» себе!

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

Если кванторы у всех переменных, то свободных переменных нет, и можно спрашивать — истинна ли формула или нет?

Пример:

Докажите, что QSAT in PSPACE.

---

---

---

Задача «Задачи/SAT-in-LOGSPACE»^©

---

Беру задачу «Временная и пространственная сложность алгоритмов/Задачи/SAT-in-LOGSPACE» себе!

---

---

---

Задача «Задачи/dlogspace-pspace-gap»^©

---

Беру задачу «Временная и пространственная сложность алгоритмов/Задачи/dlogspace-pspace-gap» себе!

Покажите, что должно выполняться хотя бы одно из неравенств (несовпадений) классов сложности:

• DLOGSPACE ≠ P
• PSPACE ≠ P

• Заметим, что если у вас вряд ли получится доказать эти неравенства по отдельности.

---

---

---

Задача «Задачи/ex-braces-parse-in-logspace»^©

---

Беру задачу «Временная и пространственная сложность алгоритмов/Задачи/ex-braces-parse-in-logspace» себе!

---

---

---

Задача «Задачи/ex-limited-halt»^©

---

Беру задачу «Временная и пространственная сложность алгоритмов/Задачи/ex-limited-halt» себе!

---

---

---

Задача «Задачи/ex-logspace-in-p»^©

---

Беру задачу «Временная и пространственная сложность алгоритмов/Задачи/ex-logspace-in-p» себе!

---

---

---

Задача «Задачи/merge-vertices»^©

---

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

Минимальный разрез в графе (стягивание вершин)

Рассмотрим рандомизированный алгоритм Каргера-Штейна для неориентированных графов с кратными ребрами. Пусть дан мультиграф c вершинами и ребрами.

Алгоритм основан на операции стягивания ребра между двумя вершинами. После стягивания ребра получим новый граф без вершины в котором каждое ребро вида заменено ребром (петли также удаляются).

Алгоритм следующий

for i=0 to n-2:
   выбрать случайное ребро e
   стянуть ребро e

В конце, «восстанавливаем разрез» — каждая его часть соответствует вершинам, содержащимся в одной из метавершин.

---

Доказать, что вероятностный алгоритм вычисляет минимальный разрез с вероятностью

---

---

---

Задача «Задачи/Верхняя оценка разреза в случайном графе»^©

---

Беру задачу «MAX-CUT: вероятностное округление/Задачи/Верхняя оценка разреза в случайном графе» себе!

Оцените сверху матожидание числа «больших» разрезов (разрезов, больше чем , где с<8), в случайных графах из n вершин с вероятностью зарождения ребра — ½.

Hint

Сначала надо правильно решить MAX-CUT: вероятностное округление/Задачи/Матожидание разреза.

---

---

---

Задача «Задачи/Детерминированный 2-приближенный алгоритм для задачи MAX-CUT»^©

---

Беру задачу «MAX-CUT: вероятностное округление/Задачи/Детерминированный 2-приближенный алгоритм для задачи MAX-CUT» себе!

Предложите детерминированный 2-приближенный полиномиальный алгоритм для задачи MAX-CUT.

---

---

---

Задача «Задачи/Матожидание разреза»^©

---

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

Рассмотрим случайные графы

• из n вершин,
• ребро возникает между любой парой вершин с вероятностью ½.

Напишите формулу матожидания средней величины разреза по всем таким случайным графам из n-вершин.

---

---

---

Задача «Задачи/MAX-3ESAT»^©

---

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

Рассмотрим задачу «MAX-3ESAT», это «MAX-SAT», только в КНФ в каждой скобке ровно три литерала.

Предложите вероятностный алгоритм с точностью .

---

---

---

Задача «Задачи/max-sat-local-opt--1-2»^©

---

Беру задачу «MAX-SAT: вероятностное округление/Задачи/max-sat-local-opt--1-2» себе!

Опишите алгоритм локального поиска для MAX-SAT, покажите, что он находит решение не хуже половины от оптимума.

---

---

---

Задача «Задачи/не более половины скобок»^©

---

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

Приведите пример задачи max-sat (невырожденный случай, т.е. КНФ для любого числа переменных, а не просто пустая формула), для которой на любом наборе переменных выполнено не более половины скобок.

• А менее половины скобок?

---

---

---

Задача «Задачи/2-приближенный алгоритм для максимальной совместной подсистемы»^©

---

Беру задачу «MAX-SAT: дерандомизация/Задачи/2-приближенный алгоритм для максимальной совместной подсистемы» себе!

---

---

---

Задача «Задачи/ex-derand-maxsat-f0-f1»^©

---

Беру задачу «MAX-SAT: дерандомизация/Задачи/ex-derand-maxsat-f0-f1» себе!

---

---

---

Задача «Задачи/shell-game»^©

---

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

Честный попутчик в поезде предлагает вам сыграть в следующую игру, вариант классического «наперстка». т. е. есть

• три наперстка,
• шарик,
• ваша задача
  • обнаружить шарик - тогда вы выигрываете,
  • иначе - выигрывает сдающий.

Каждый раз на кон, вы и сдающий, ставите по 50 рублей.

Сдающий тасует три наперстка, и прячет под одним из них шарик.

Затем он предлагает вам выбрать наперсток.

После того, как вы выбрали наперсток (пусть это будет наперсток «A»), вы можете

• открыть его, либо,
• заплатив еще 10 рублей, потребовать от сдающего, открыть пустой наперсток из двух оставшихся (пусть открытый будет «B»), после чего выбрать один из двух закрытых наперстков (т.е. «A» или «С»).

Заметим, что сдающий и предметы честные — никаких «исчезающих» шариков и прочего мошенничества, наперсток для шарика выбирается совершенно случайно.

Какая стратегия оптимальна?

• Не играть. Выигрыш - «0».
• Выбрать наперсток «A» и открыть его.
• Выбрать наперсток «A», «купить» открытие пустого наперстка «B», но выбрать наперсток «A».
• Выбрать наперсток «A», «купить» открытие пустого наперстка «B», и выбрать наперсток «С».

Дорога длинная, играть можно много раз, правильная стратегия может привести к существенному обогащению, неправильная - к разорению…

Обоснуйте.

Подсчитайте матожидание выигрыша для каждой из стратегий.

---

---

---

Задача «Задачи/Комбинированная дерандомизация»^©

---

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

А можно ли добиться путем дерандомизации построения -приближенного детерминированного полиномиального алгоритма для задачи MAX-SAT?

---

---

---

Задача «Задачи/TSP-approx»^©

---

Беру задачу «PCP и аппроксимируемость/Задачи/TSP-approx» себе!

Покажите, что если существует полиномиальный f(n)-приближенный алгоритм для задачи о коммивояжере на полном графе с положительными весами, где f любая функция, то P=NP.

---

---

---

Задача «Задачи/ex-max2sat-in-npc»^©

---

Беру задачу «PCP и аппроксимируемость/Задачи/ex-max2sat-in-npc» себе!

Рассмотрим максимизационную версию задачи 2SAT, где дополнительно к 2SAT-формуле задается параметр K, и спрашивается, можно ли выполнить больше чем K, количество скобок.

Покажите, что эта задача NP-полна.

---

---

---

Задача «Задачи/Перечислимость описаний»^©

---

Беру задачу «Введение в теорию вычислимости/Задачи/Перечислимость описаний» себе!

Является ли

• а). перечислимым

• б). ко-перечислимым множество описаний машин Тюринга, останавливающихся на пустом входе?

Ответ обосновать.

---

---

---

Задача «Задачи/Порядок»^©

---

Беру задачу «Введение в теорию вычислимости/Задачи/Порядок» себе!

Пусть -- перечислимый язык. Доказать, что если его слова можно лексикографически упорядочить, то тогда является и разрешимым.

---

---

---

Задача «Задачи/determinant»^©

---

Беру задачу «Вероятностная проверка тождеств/Задачи/determinant» себе!

---

---

---

Задача «Задачи/BPP in PSPACE»^©

---

Беру задачу «Вероятностные вычисления. Классы RP, coRP, ZPP, BPP/Задачи/BPP in PSPACE» себе!

Докажите, что .

Не используя теорему Лаутемана (не палите из пушек по воробьям!).

Просто посмотрите на определения обоих классов.

---

---

---

Задача «Задачи/RP in PPoly»^©

---

Беру задачу «Вероятностные вычисления. Классы RP, coRP, ZPP, BPP/Задачи/RP in PPoly» себе!

Докажите, что .

---

---

---

Задача «Задачи/amplify-optimization»^©

---

Беру задачу «Вероятностные вычисления. Классы RP, coRP, ZPP, BPP/Задачи/amplify-optimization» себе!

Есть оптимизационный алгоритм A, который для входа x находит оптимальное решение с вероятностью 1/|x|.

Как сделать из него максимально эффективный алгоритм B, чтобы

Prob(B(x)=OPT) → 1 при |x|→∞.

---

---

---

Задача «Задачи/amplify-when-specific-error-bounded»^©

---

Беру задачу «Вероятностные вычисления. Классы RP, coRP, ZPP, BPP/Задачи/amplify-when-specific-error-bounded» себе!

Пусть A — вероятностный алгоритм, вычисляющий f(x).

Но не очень полезный:

• Prob(A(x)=f(x)) >= ⅓

Правда известен факт, что для любого неверного результата w

• Prob(A(x)=w) <= ¼

Можно ли как-то из A сделать полезный алгоритм?

---

---

---

Задача «Задачи/ex-fix-spoj-23»^©

---

Беру задачу «Вероятностные вычисления. Классы RP, coRP, ZPP, BPP/Задачи/ex-fix-spoj-23» себе!

---

---

---

Задача «Задачи/ex-fix-spoj-recovery»^©

---

Беру задачу «Вероятностные вычисления. Классы RP, coRP, ZPP, BPP/Задачи/ex-fix-spoj-recovery» себе!

Все то же, что и в упражнении Вероятностные вычисления. Классы RP, coRP, ZPP, BPP/Задачи/ex-fix-spoj-23.

---

---

---

Задача «Задачи/0.5-приближенный вероятностный для MAX-CUT»^©

---

Беру задачу «MAX-CUT: вероятностное округление/Задачи/0.5-приближенный вероятностный для MAX-CUT» себе!

---

---

---

Задача «Задачи/2-boolean system»^©

---

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

---

---

---

Задача «Задачи/ex-maxcut-trivial-greedy-1-2»^©

---

Беру задачу «MAX-CUT: вероятностное округление/Задачи/ex-maxcut-trivial-greedy-1-2» себе!

Студент предлагает для невзвешенной задачи MAX-CUT приближенный алгоритм с точностью ½:

• положить первую вершину в одну часть, последнюю — в другую,
• затем по-очереди добавлять оставшиеся вершины, к множеству, с которым у этой вершины меньше ребер-связей.

Прав ли студент?

---

---

---

Задача «Задачи/ex-min-maxmatching-1-2»^©

---

Беру задачу «MAX-CUT: вероятностное округление/Задачи/ex-min-maxmatching-1-2» себе!

---

---

---

Задача «Задачи/max-cut-equal-partition-polinomial-local-search»^©

---

Беру задачу «MAX-CUT: вероятностное округление/Задачи/max-cut-equal-partition-polinomial-local-search» себе!

Рассмотрим частную версию задачи MAX-CUT — потребуем, чтобы граф был с четным числом вершин, а делить вершины надо на две одинаковые команды.

Придумайте полиномиальный алгоритм для этой задачи.

---

---

---

Задача «[[Зарезервированные практические задачи|]]»^©

---

Беру задачу «Зарезервированные практические задачи» себе!

Всего страниц найдено: 13.

----

Задача «Optprob/Художник продает картины галереям»

Престижный художник создал 4 произведения искусства. Галереи A, B и C заинтересованы в их приобретении и готовы заплатить за каждую работу суммы (в миллионах денежных единиц), указанные в таблице:

. Картина1 Картина2 Картина3 Картина4 А 12 10 8 10 B 14 11 6 7 C 15 13 8 9

Художник собирается продать все произведения искусства, и каждая галерея должна приобрести хотя бы одно произведение (им, в общем, все равно, что продадут). Хотя известно, что галерея A купит только одну картину.

Как художник будет распределять произведения искусства между галереями, чтобы максимизировать свой доход?

Вариант: художник добавил следующее ограничение: работы 2 и 4 должны висеть рядом, и быть проданы в одну и ту же галерею.

Задача зарезервирована: VoyakinaES 12:30, 11 ноября 2024 (UTC)

---

---

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

Задача зарезервирована: EjenY 15:43, 10 ноября 2024 (UTC)

Бонусная задача

---

---

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

Задача зарезервирована: Solovev 15:41, 10 ноября 2024 (UTC)

Бонусная задача

---

---

Задача «MAX-SAT: дерандомизация/Задачи/eupce-6-2-a»

Задача зарезервирована: Solovev 15:12, 10 ноября 2024 (UTC)

Бонусная задача

Докажите, что для каждого целого числа n существует раскраска ребер полного графа K_n в два цвета, такое что полное число одноцветных подграфов K_4 будете не больше чем \binom{n}{4} 2^{-5}

---

---

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

Задача зарезервирована: Solovev 15:16, 10 ноября 2024 (UTC)

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

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

---

---

Задача «Вероятность/Задачи/eupce-2-7-a»

Задача зарезервирована: EjenY 15:19, 10 ноября 2024 (UTC)

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

P(X = Y) = ?

---

---

Задача «Вероятность/Задачи/eupce-2-4»

Докажите, что E[X^k] ≥ E[X]^k для любого целого k ≥ 1.

Задача зарезервирована: Ermakov

---

---

Задача «Вероятность/Задачи/eupce-1-15»

Предположим, что бросают десять стандартных шестисторонних костей.

Какова вероятность того, что их сумма будет деленной на 6, предполагая, что броски независимы?

Задача зарезервирована: Ermakov

---

---

Задача «Вероятность/Задачи/eupce-1-13»

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

Частота ошибок первого рода (false negative) мала: если у вас есть расстройство, вероятность того, что тест вернет положительный результат, составляет 0.999.

Частота ошибок второго рода (false positive) тоже невелика: если у вас нет расстройства, вероятность того, что тест вернет положительный результат, составляет всего 0.005.

Предположим, что эту болезнь имеет 2% населения.

Если мы проверяем человека, выбранного равномерно из популяции, и получается положительный результат, какова вероятность того, что эта болезнь у него действительно есть?

Задача зарезервирована: Ermakov

---

---

Задача «Open Exercises»

showtotal=yes namespace=Main limit=500 order=lastedit desc,pagename output=template template=IncludeCard2 redirect=no category=Теоретические_задачи notcategory=Solved notcategory=Решенные_задачи notcategory=OptimizationProblems ignore=Permission denied ignore=A ignore=Open_Exercises ignore=Открытые_теоретические_задачи

---

---

Задача «Optprob/Назначение инженеров на проекты»

Мы планируем распределять инженеров по проектам компании.

В течение следующего года компания имеет возможность участвовать в десяти инженерных проектах.

Каждый проект требует персонала (для проекта j потребуется Aj инженеров любого типа), приносит доход (G_j) и имеет общие расходы (C_j).

Projects	1	2	3	4	5	6	7	8	9	10
A	3	3	3	2	2	2	4	4	4	5
C	10000	20000	25000	40000	10000	40000	20000	25000	10000	30000
G	55000	60000	60000	90000	30000	100000	65000	50000	50000	60000

Инженеры компании делятся на две категории:

• S: Старший инженер (с опытом)
• JJ: Младший инженер (без достаточного опыта)

Каждый инженер имеет годовую зарплату M.

В настоящее время компания располагает штатом, состоящим из семи старших инженеров и четырех младших инженеров.

Engineers	1	2	3	4	5	6	7	8	9	10	11
S	1	1	0	0	0	1	0	1	0	1	0
JJ	0	0	1	1	1	0	1	0	1	0	1
M	50000	45000	30000	35000	28000	58000	36000	55000	35000	50000	33000

Каждый инженер, будь то старший или младший, подходит для каждого из проектов, в зависимости от их подготовки. Эта пригодность измеряется в виде непрерывного индекса от 0 (нет) до 1 (оптимально).

	1	2	3	4	5	6	7	8	9	10
1	0	1	0.5	0.5	0.5	1	0.3	0.2	0.4	0.8
2	0.5	0.5	1	0.3	0.2	0.4	1	1	0	0
3	1	1	0	0	1	0	0.4	0.5	0.6	0.5
4	2	0.5	0.5	1	0.3	0.2	0.4	2	0.3	0.5
5	0.5	1	0.3	0.2	0.4	1	1	1	0.3	0
6	0.2	0.5	0.5	3	0	0	1	1	1	0.6
7	1	0.6	0.7	0.5	0.5	1	0.3	0.2	0.4	0.6
8	1	3	3	3	0.5	1	0.3	0.2	0.4	1
9	0	1	1	0.5	0.5	1	0.3	0.2	0.4	0.1
10	0.5	1	0.3	0.2	0.5	1	0.3	0.2	0.4	1
11	0.5	1	0.3	0.2	0.5	1	0.3	0.2	0.4	1

Компания имеет возможность нанимать новых инженеров.

Затраты, которые компания оценивает для найма новых сотрудников, следующие

следующим образом:

• Старший инженер: $50 000/год
• Младшие инженеры: $35 000/год

Для новых инженеров компания присваивает пригодность 75% старшим инженерам и 50% младшим, так как персонал будет подбираться в соответствии к проектам.

Существует два типа назначений для инженеров:

• частичная занятость
• полный рабочий день

Компания позволяет назначить инженера на неполный или полный рабочий день на проекты. Если он работает полный рабочий день, он может быть занят только в одном проекте.

Если неполный рабочий день — может быть максимум в двух.

Новые инженеры могут быть назначены только эксклюзивно.

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

Количество инженеров, необходимых проекту, всегда является величиной, предполагающей исключительности.

Если инженеры назначены на неполный рабочий день, то два инженера на неполный рабочий день считаются как

один инженер.

Компания хочет, чтобы

• в каждом проекте, в котором она участвует, был как минимум один старший инженер (новый или уже работающий) на полную ставку.
• общая пригодность инженеров, назначенных на проект, была выше 50% — расчет общей пригодности производится как сумма пригодности инженеров, назначенных на проект, деленная на количество назначенных инженеров, независимо от того, работают ли они неполный или полный рабочий день.

Помимо всего этого, существуют и другие спецификации:

• В проекте не должно быть более трех инженеров, работающих неполный рабочий день.
• Проекты 5 и 6 не могут иметь ни одного общего инженера в этих двух проектах.
• Участие в проекте 2 на неполный рабочий день требует участия в проекте 3.

Цель компании — максимизация прибыли: «Доход от проектов» - «Расходы» (расходы на заработную плату + общие расходы).

Задача зарезервирована: Evvnes 07:21, 14 ноября 2024 (UTC)

---

---

Задача «Optprob/Планируем генерацию электричества»

Долгосрочный план выработки электроэнергии учитывает график работы существующих энергоблоков и график установки новых электростанций для удовлетворения спроса на электроэнергию в течение ряда будущих (5) лет при минимально возможных затратах.

Период планирования; 5 лет

Потребность в электроэнергии описывается кривой продолжительности нагрузки (LDC), как показано на рис (цифры на картинке приблизительны, точные будут дальше текстом), по оси ординат — мегаватты, по оси абсцисс — часы.

Площадь под графиком соответствует потребностям производства электроэнергии в мегаватт-часах.

Чтобы модель была простой, например линейной, график аппроксимируется кусочно-постоянной функцией, показанной в виде гистограммы (ступенчатой функции), с

• «Bars=4».
• TD — отсечки по горизонтали

 2920 3650 1280 910

Первый столбец обозначает минимальную нагрузку, столбец «4» — пиковую нагрузку, а два промежуточных — представляют потребность в средней нагрузке.

В любой компании или стране для производства электроэнергии используется несколько различных типов (n=5) технологий, таких как

• паровые турбины
• газовые турбины
• гидроэлектростанции
• дизель-генераторы
• комбинированные генераторы

Эти энергоблоки требуют различных затрат, затрат на установку и переменных затрат, и переменная по времени генерации (что-то ломается, что-то амортизируется, что-то улучшается).

$CE\_\{it\},\; 1\; \backslash leq\; i\; \backslash leq\; n$; — планируемые мощности существующих генерирующих типов по времени.

    15000 18000  20000  21000  21000
    40000 350000 300000 280000 280000 
    50000 400000 400000 400000 300000
    10000 100000 120000 130000 150000
     1000  11000 12000  14000  16000 

$VC\_\{it\}$; Переменная (на мегаватт) годовая стоимость старой установки типа «i»

    4 4 4 4 4
    5 5 5 5 5
    3 3 3 3 3
    3 3 3 3 3
    1 1 1 1 1 

---

Кроме того, в будущем могут быть добавлены дополнительные мощности.

Например, предположим, что модель решила установить новую установку типа «j=1» мощностью 50 МВт в период «1», она будет существовать в системе до истечения технического срока службы этой установки (Это потому, что продолжительность горизонта планирования, рассматриваемого в этой задаче, короче, чем технический срок службы любого нового энергоблока, доступного на рынке).

$FC\_\{jt\}$; Фиксированная годовая стоимость новой установки типа «j»

    100 110 110 120 120
    200 200 200 200 200 
    300 290 290 285 285
    200 190 190 180 180
    50 50 50 50 50  ~

$FC\_\{jt\}$; Фиксированная годовая стоимость новой установки типа «j»

!AF; 80 80 85 85 85

    85 85 85 85 85
    90 90 90 90 90
    90 90 95 95 95
    85 85 90 90 90~

!PD; 6000 6000 6000 6000 6000

    9000 10000 110000 12000 13000
    25000 27000 27000 27000 27000
    50000 58000 58000 58000 57000~

!W; 20 50 10 10 10~

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

Задача планирования состоит в том, чтобы определить

• график работы существующих установок,
• установок нового поколения, которые будут запущены в будущем,
• и график введения новых установок путем минимизации суммы затрат на установку и эксплуатацию за заданное количество

лет, соблюдая при этом технические и финансовые ограничения.

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

С другой стороны, администрация имеет предпочтение между различными типами технологий, то есть между различными генерирующими установками в случае новых установок.

Это предпочтение описывается процентным коэффициентом от минимума, который должен иметь каждый новый блок, по сравнению с общей энергией, установленной в новых блоках.

Пока не додумано, надо доработать

Задача зарезервирована: StasFomin 16:33, 27 ноября 2022 (UTC)

---

---

Задача «Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Задачи/MAX-CUT-NPC»

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

Задача зарезервирована: Ermakov

---

1. ↑ Т.е. это не как упаковка в многомерном тетрисе
2. ↑ Largest Processing Time
3. ↑ Largest Processing Time
4. ↑ Largest Processing Time

---

---