Список заданий по продвинутым алгоритмам 2021 осень — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 24: Строка 24:
 
# Сведите задачу $R|pmtn|C_{max}$ к задаче линейного программирования.
 
# Сведите задачу $R|pmtn|C_{max}$ к задаче линейного программирования.
 
# $P|intree, p_i=1|L_{max}$
 
# $P|intree, p_i=1|L_{max}$
 +
# $F | p_{ij} = 1 | \sum C_i$
 +
# $F2 | pmtn | C_{max}$
 +
# $F | p_{ij} = 1 | \sum U_i$
 +
# $F | p_{ij} = 1 | \sum w_iU_i$
 +
# $O | p_{ij} = 1 | C_{max}$
 +
# $O | p_{ij} = 1 | \sum C_i$
 +
# $O | p_{ij} = 1 | \sum w_iC_i$
 +
# $O | p_{ij} = 1, d_i | -$
 +
# $O | p_{ij} = 1 | \sum U_i$
 +
# $O | p_{ij} = 1 | \sum w_iU_i$
 +
# $O | p_{ij} = 1, r_i | C_{max}$
 +
# $O2 | p_{ij} = 1, prec | \sum C_i$

Версия 16:21, 1 октября 2021

  1. $1 | p_i=1 | L_{max}$.
  2. $1 | r_i, d_i=d | L_{max}$.
  3. $1 | prec, r_i, p_i=1 | L_{max}$.
  4. Рассмотрим задачу $1 | p_i = 1, d_i | -$. Докажите, что подмножества работ, которые можно выполнить, образуют семейство независимых множеств некоторого матроида.
  5. $1 | p_i = 1, d_i | \sum w_iU_i$. Время $O(n\log n)$.
  6. $1 | p_i = 1, d_i, r_i | \sum U_i$. Время - полином от $n$.
  7. $1 | p_i = 1, d_i, r_i | \sum w_iU_i$. Время - полином от $n$.
  8. $1 | p_i = p, pmtn, r_i | \sum w_iU_i$ за $O(n^{10})$.
  9. $1 || \sum U_i$
  10. $1 | r_i, p_i = p | \sum w_iC_i$ за $O(n^7)$
  11. Обозначение outtree означает, что граф зависимостей представляет собой исходящее дерево: каджая работа зависит не более чем от одной другой. $1 | outtree | \sum w_iC_i$
  12. Обозначение intree означает, что граф зависимостей представляет собой входящее дерево: от каждой работы зависит не более одной другой. $1 | intree | \sum w_iC_i$
  13. $P | pmtn, r_i | C_{max}$
  14. $P | pmtn, r_i | L_{max}$
  15. $Q | pmtn, r_i | C_{max}$
  16. $P | p_i = p, r_i, d_i | \sum C_i$ за $O(n^3 \log n)$ (бонус за $O(n^3 \log\log n)$)
  17. $P | p_i = 1 | \sum w_iU_i$ - доведите доказательство с пары до конца
  18. $P | p_i = 1 | \sum w_iC_i$
  19. $P | p_i = 1, pmtn | \sum w_iC_i$
  20. $Q | pmtn | \sum C_i$
  21. $Q | pmtn | \sum f_i$ (напомним, что f_i - произвольная неубывающая функция, может быть своя у каждой работы)
  22. $Q | pmtn | f_{max}$
  23. $P2 | p_i = 1, prec, r_i | \sum C_i$ за $O(n^9)$
  24. Сведите задачу $R|pmtn|C_{max}$ к задаче линейного программирования.
  25. $P|intree, p_i=1|L_{max}$
  26. $F | p_{ij} = 1 | \sum C_i$
  27. $F2 | pmtn | C_{max}$
  28. $F | p_{ij} = 1 | \sum U_i$
  29. $F | p_{ij} = 1 | \sum w_iU_i$
  30. $O | p_{ij} = 1 | C_{max}$
  31. $O | p_{ij} = 1 | \sum C_i$
  32. $O | p_{ij} = 1 | \sum w_iC_i$
  33. $O | p_{ij} = 1, d_i | -$
  34. $O | p_{ij} = 1 | \sum U_i$
  35. $O | p_{ij} = 1 | \sum w_iU_i$
  36. $O | p_{ij} = 1, r_i | C_{max}$
  37. $O2 | p_{ij} = 1, prec | \sum C_i$