Вопросы с тегом «dynamic-programming»

15
Динамическое программирование никогда не бывает слабее, чем Greedy?

В сложности схемы у нас есть разделения между степенями различных моделей схемы. В сложности доказательства мы имеем разделения между степенями различных систем доказательства. Но в алгоритмическом у нас все еще есть только несколько разделений между степенями алгоритмических парадигм . Мои вопросы...

14
Является ли eta-эквивалентность для функций совместимой с операцией seke в Haskell?

Лемма: Предполагая, что эта эквивалентность у нас есть (\x -> ⊥) = ⊥ :: A -> B. Доказательство: ⊥ = (\x -> ⊥ x)по eta-эквивалентности и (\x -> ⊥ x) = (\x -> ⊥)по сокращению под лямбду. В отчете Haskell 2010, раздел 6.2, seqфункция определяется двумя уравнениями: seq :: a -> b...

14
Сложность монотонной арифметической схемы элементарных симметрических полиномов?

В ККk -й элементарный симметричный полином SNК( х1, … , ХN)SКN(Икс1,...,ИксN)S_k^n(x_1,\ldots,x_n) является суммой всех продуктов различных переменных. Меня интересует сложность монотонной арифметической схемы этого многочлена. Простой алгоритм динамического программирования (как и рис. 1 ниже)...

12
Покрывающая струна палиндромами

Дана строка , А палиндром крышка представляет собой последовательность р 1 р 2 ⋯ р м слов р я такое , что р 1 р 2 ⋯ р м = ш , и так , что каждый р я палиндром ,w = σ1σ2… ΣNw=σ1σ2…σnw=\sigma_1\sigma_2\ldots\sigma_nп1п2⋯ рмp1p2⋯pmp_1p_2\cdots p_mпяpip_iп1п2⋯ рм= шp1p2⋯pm=wp_1p_2\cdots p_m = wпяpip_i...