Referanseside · Kapittel 29

Begreper & formler

Alle nøkkelbegrepene og formlene fra Polynomer og FFT, samlet på én side. Bruk denne som oppslag når du leser, øver flashcards eller tar quiz.

Øv med flashcards8 kort fra dette kapittelet

Begreper

Sentrale begreper fra kapittelet med korte definisjoner.

01Polynomrepresentasjon

Et polynom kan representeres som koeffisientliste $a_{0}, a_{1}, ..., a_{n - 1}$ .

02Røtter av enhet

Komplekse tall $ω_{n}^{k} = e^{2 πik / n}$ brukt for evaluering og interpolasjon.

03FFT

Algoritme som evaluerer et polynom i alle $n$ -te røtter av enhet i $O (n lo g n)$ tid.

04Konvolusjon

Produktet av to polynomer tilsvarer konvolusjon av deres koeffisienter.

05Inverse FFT

Brukes til å rekonstruere koeffisienter fra evaluerte verdier.

Hver formel: hva den heter, hvordan den ser ut, og hva symbolene betyr.

ω_{n} = e^{2 πi / n}

O (n lo g n)

c_{k} = i + j = k \sum a_{i} b_{j}