Teoretyczne informatyka convolution

Znalezienie świadka w minkowskiej sumie liczb całkowitych

Niech i będą podzbiorami . Interesuje nas znalezienie sumy Minkowskiego .ZAAABBB{0,…,n}{0,…,n}\{0,\ldots,n\}A+B={a+b | a∈A,b∈B}A+B={a+b | a∈A,b∈B}A+B=\{a+b~|~a\in A,b\in B\} χX:{0,…,2n}→{0,1}χX:{0,…,2n}→{0,1}\chi_X:\{0,\ldots,2n\}\to \{0,1\} jest charakterystyczną funkcją ifXXXχX(x)={1 if x∈X0 otherwiseχX(x)={1 if x∈X0 otherwise\chi_X(x) = \begin{cases} 1 \text{ if } x\in X\\ 0 \text{ otherwise}\end{cases} Niech będzie dyskretne splot i , a , wtedy i …

16 convolution fft

Złożoność splotu w pierścieniu max / plus

Możemy wykonać splot w O(nlogn)O(nlog⁡n)O(n\log n) dla wielomianów dodatnich / wielokrotnych za pomocą FFT. Jednak podejście to nie wydaje się zbyt ogólne w odniesieniu do pierścieni w ogóle. Czy nastąpił postęp w stosunku do naiwnego splotu O(n2)O(n2)O(n^2) dla pierścienia max / plus? soft-max(x,y)=log(ex+ey)=max(x,y)+log(1+emin(x,y)−max(x,y))soft-max(x,y)=log⁡(ex+ey)=max(x,y)+log⁡(1+emin(x,y)−max(x,y))\text{soft-max}(x,y)=\log(e^x+e^y) = \max(x,y) + \log(1+e^{\min(x,y)-\max(x,y)})

10 algebra polynomials fft convolution

Pytania otagowane jako convolution