Открытые теоретические задачи

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

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


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


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




Задача «Задачи/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-13»©


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




Задача «Задачи/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»©


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



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


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




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


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




Задача «Задачи/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-1-26-b»©


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

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

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

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




Задача «Задачи/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»©


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

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

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

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

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

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




Задача «Задачи/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»




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




[ Хронологический вид ]Комментарии

(нет элементов)

Войдите, чтобы комментировать.