Zadanie: W ciele liczb zespolonych wyznaczyć zespolony pierwiastek pierwotny z jedynki stopnia 16
{{{id=1| /// }}}Zadanie: Napisać funkcję, która oblicza pierwiastek pierwotny z jedynki podanego stopnia.
{{{id=7| def pierw_pierw( n, K = CC ) : """ Funkcja wyznacza pierwiastek pierwotny z 1 stopnia `n` w ciele `K`. """ # UZUPEŁNIĆ /// }}}Zadanie: Obliczyć dyskretną transformatę Fouriera ciągu $(1,\dotsc, 8)$ wprost z definicji.
{{{id=4| /// }}}Twierdzenie: Dyskretna transformata Fouriera wielomianu $f$ (sensu stricte jego ciągu współczynników), względem pierwiastka pierwotnego z jedynki $\omega$ stopnia $1+\deg f$, stanowi ciąg wartości $f$ na kolejnych potęgach $\frac1\omega$.
Zadanie: Obliczyć tę samę transformatę Fouriera korzystając z powyższego twierdzenia.
{{{id=6| /// }}}Poniższa komórka zawiera funkcję podziel_liste z zestawu 2. Wykona się ona automatycznie (do tego służy atrybut %auto).
{{{id=11| %auto def podziel_liste( L ) : """ Funkcja zwraca dwie listy E oraz O, składające się z elementów listy L, mających odpowiednio parzyste i nieparzyste indeksy. """ n = len(L) E = [ L[j] for j in [0,2,..,n-1] ] O = [ L[j] for j in [1,3,..,n-1] ] return E,O /// }}}Zadanie: Obliczyć krok po kroku dyskretną transformatę Fouriera ciągu $(1,2,3,4)$ za pomocą algorytmu Cooley'a-Tukey'a.
1. Skonstruować ciąg i podzielić go na część o indeksach parzystych oraz nieparzystych.
{{{id=12| /// }}}2. Ponownie podzielić każdą z otrzymanych części.
{{{id=14| /// }}}3. Zastsować (trywialną) dyskretną transformatę Fouriera dla otrzymanych singletownów.
{{{id=15| /// }}}4. Scalić pary singletonów, w transformaty Fouriera ciągów dwueleementowych.
{{{id=16| /// }}}5. Scalić ciągi otrzymane w poprzednim kroku w wynikową transformatę Fouriera.
{{{id=17| /// }}}Zadanie: Zaimplementować algorytm Cooley'a-Tukey'a szybkiej transformaty Fouriera.
{{{id=18| def fft( L, omega = 0 ) : """ Funkcja oblicza FFT listy ``L``, używając algorytmu Cooley-Tukey. Długość listy musi być potęgą 2 Argumenty: - ``L`` lista - ``omega`` - pierwiastek pierwotny z jedynki stopnia len( L ). Można go pominąć przy wywołaniu funkcji. Zostanie wtedy obliczony w locie. """ # UZUPEŁNIĆ /// }}}