Book a Demo!
CoCalc Logo Icon
StoreFeaturesDocsShareSupportNewsAboutPoliciesSign UpSign In
Download
864 views
Tweet
Share
Share

Zestaw 3 - Algorytmy podstawowe

%auto

# Treść tej komórki wykona się automatycznie po otwarciu zestawu (do tego służy atrybut auto na początku)

class wielomian(object) :
    """
    Ćwiczebna klasa wielomianu
    wielomian(wspolczynniki) konstruuje wielomian nad ciałem QQ o podanych współczynnikach
    wielomian(wspolczynniki, K) j.w. ale nad ciałem K
    """
    def __init__(self, wspolczynniki = [], K = QQ):
        from sage.rings.commutative_ring import is_CommutativeRing
        assert is_CommutativeRing(K), str(K) + " nie jest pierścieniem!"
        self.pierscien_wspolczynnikow = K
        self._pscien_disp = PolynomialRing(K, 1, name='t', order='neglex')
        self._pscien = K['t']
        self._wspl   = copy(wspolczynniki)
        while self._wspl and self._wspl[-1] == 0 : 
            self._wspl.pop()
    # dwie funkcje służące do wyświetlania wielomianu
    def _repr_(self) :
        return self._pscien_disp(self._pscien(self._wspl))._repr_()
    def __repr__(self) :
        return self._repr_()
    # konwersja do LaTeX-a, w celu używania z view
    def _latex_(self) :
        return self._pscien_disp(self._pscien(self._wspl))._latex_()
    # funkcja zwracająca współczynnik wielomianu
    def __getitem__(self, j) :
        """
        f[i] zwraca i-ty współczynnik wielomianu f
        """
        return self._wspl[j]
    # funkcja mnożenia wielomianu przez stałą a*f
    def __rmul__(self, a) :
        if a == 0 :
            return wielomian( [], f.pierscien_wspolczynnikow )
        return wielomian([ a*self[j] for j in [0..self.deg()] ], f.pierscien_wspolczynnikow )
    # funkcja implementuje porównanie ==
    def __eq__(self, g) :
        return self[:self.deg()+1] == g[:g.deg()+1]
    # funkcja implementuje porównanie !=
    def __ne__(self, g) :
        return not self==g
    # funkcja zwraca stopień wieloamianu
    def deg(self) :
        """
        f.deg() jest stopniem wielomianu f
        """
        for j in [len(self._wspl)-1,len(self._wspl)-2,..,0] :
            if self._wspl[j] != 0 :
                return j
        return -1
    # funkcja zwracająca wyraz wiodący wielomianu
    def lc(self) :
        """
        f.lc() zwraca wyraz wiodący wielomianu, równoważna wywołaniu f[f.deg()]
        """
        if self.deg() < 0 :
            return 0
        return self._wspl[self.deg()]
        
# funkcja pozwala używać obu notacji f.deg() oraz deg(f)       
def deg(f) :
    return f.deg()
    
# dunkcja pozwala używać obu notacji f.lc() oraz lc(f)
def lc(f) :
    return f.lc()

Powyższa komórka, która wykonała się automatycznie definiuje ćwiczebną klasę wielomianu używaną wyłącznie na potrzeby tego zestawu. W zadaniach z tego zestawu należy zaimplementować odpowiednie algorytmy podstawowe dla powyższej klasy. Oczywiście dla wbudowanej w Sage'a normalnej klasy wielomianów, wszystkie te algorytmy są standardowo zaimplementowane.

Wielomiany z naszej klasy ćwiczebnej konstruujemy w jeden z następujących sposobów:

  • wielomian( wspolczynniki ) - konstruuje wielomian nad ciałem Q\mathbb{Q} o podanych współczynnikach
  • wielomian( wspolczynniki, K ) - j.w. ale nad ciałem KK zamiast Q\mathbb{Q}

Wypróbować na poniższych przykładach:

%auto
 # konstruujemy wielomian nad ciałem ℚ
f = wielomian([1,2,6]); view(f)
1+2t+6t2\displaystyle 1 + 2 t + 6 t^{2}
f.deg()
f.lc()
view(2*f)
2 6
2+4t+12t2\displaystyle 2 + 4 t + 12 t^{2}
# konstruujemy wielomian nad ciałem 𝔽₅
f = wielomian([1,2,6], GF(5)); view(f)
1+2t+t2\displaystyle 1 + 2 t + t^{2}
f.deg()
f.lc()
view(2*f)
2 6
2−t+2t2\displaystyle 2 - t + 2 t^{2}

Nasza ćwiczebna klasa wielomianu w tej chwili udostępnia następujące metody i funkcje:

  • deg(f) lub f.deg() to stopień wielomianu ff
  • lc(f) lub f.lc() to współczynnik wiodący wielomianu ff
  • f[i] to to ii-ty współczynnik wielomianu ff
  • a*f gdzie aa jest stałą to iloczyn wielomianu i skalara
  • f==g oraz f!=g to operatory porównania

Zadanie: Napisać funkcję znajdującą wielomian przeciwny do danego.

Wskazówka: j-ty współczynnik wielomianu ff jest dostępna jako f[j] zaś stopień tego wielomianu jako f.deg()

%auto
def przeciwny( f ) :
    """
    Ta funkcja zwraca wielomian przeciwny do bieżącego
    """
    # UZUPEŁNIĆ

%auto 
def przeciwny( f ) :
    return wielomian([-f[i] for i in [0,..,deg(f)]], f.pierscien_wspolczynnikow)


︠6e10ed26-8d8f-4211-93c8-16465d944d8aas︠
%auto# wykonanie tej komórki pozwoli stosować tradycyjną notację: -f
wielomian.__neg__ = przeciwny

# wypróbować
f = wielomian([1,2,3,4]); view(f)
view( -f )
1+2t+3t2+4t3\displaystyle 1 + 2 t + 3 t^{2} + 4 t^{3}
−1−2t−3t2−4t3\displaystyle -1 - 2 t - 3 t^{2} - 4 t^{3}

Zadanie: Zaimplementować obliczanie pochodnej wielomianu.

def pochodna(f) :
    """
    Dla podanego wielomianu $f$, funkcja zwraca $f'$
    """
    # UZUPEŁNIĆ

%auto
def pochodna(f) :
    return wielomian([i*f[i] for i in [1,..,deg(f)] ], f.pierscien_wspolczynnikow)

# wypróbować
f = wielomian([1,2,3,4]); view("f = " + latex(f))
view( "f\' = " + latex(pochodna(f)) )
f = 1 + 2 t + 3 t^{2} + 4 t^{3}
f' = 2 + 6 t + 12 t^{2}

Zadanie: Zaimplementować obliczanie pochodnej wielomianu za pomocą arkusza kalkulacyjnego.

Zadanie: Napisać funkcję obliczającą wartość wielomianu w punkcie z użyciem schematu Hornera. 

%auto
def Horner( f, a ) :
    """
    funkcja oblicza wartość $f(a)$ wielomianu $f$ w punkcie $a$
    """
    # UZUPEŁNIĆ
    w=lc(f)
    for i in [ deg(f)-1, deg(f)-2,..,0 ] :
        w=w*a+f[i]
    return w

%auto
# wykonanie tej komórki pozwoli obliczać wartości wielomianów
# za pomocą tradycyjnej notacji: f(0), f(1/3),...
wielomian.__call__ = Horner

# wypróbować latex wypisuje formule latexowa 
g = wielomian([1,-2,4,-8]); view("g = " +latex(g))
view("g(1) = " + latex(g(1)))
g = 1 - 2 t + 4 t^{2} - 8 t^{3}
g(1) = -5

%html
<p><strong>Zadanie:</strong> Obliczyć wartość wielomianu w punkcie (schematem Hornera) za pomocą arkusza kalkulacyjnego.

<p><strong>Zadanie:</strong> Napisać funkcję dodawania wielomian&oacute;w.</p>

Zadanie: Obliczyć wartość wielomianu w punkcie (schematem Hornera) za pomocą arkusza kalkulacyjnego.

Zadanie: Napisać funkcję dodawania wielomianów.

%auto
def dodawanie( f, g ) :
    """
    funkcja oblicza sumę $f+g$ podanych wielomianów
    """
    # wielomiany muszą mieć ten sam pierścień współczynników
    assert f.pierscien_wspolczynnikow == g.pierscien_wspolczynnikow, "Niezgodne pierścienie współczynników"

    # UZUPEŁNIĆ
    if deg(f)==deg(g):
        return  wielomian([f[i]+g[i] for i in [0,..,deg(f)] ], f.pierscien_wspolczynnikow)
    if deg(f)>deg(g):
        return wielomian([f[i]+g[i] for i in [0,..,deg(g)] ]+[f[i] for i in [deg(g)+1,.., deg(f)]], f.pierscien_wspolczynnikow)
    if deg(f)<deg(g):
        return wielomian([f[i]+g[i] for i in [0,..,deg(f)] ]+[g[i] for i in [deg(f)+1,.., deg(g)]], f.pierscien_wspolczynnikow)
        

%auto
# wykonanie tej komórki pozwoli dodawać wielomiany
# za pomocą tradycyjnej notacji: f+g
wielomian.__add__ = dodawanie

f=wielomian([1,2,3,4])
g=wielomian([1,0,2,3])
view(f)
view(g)
view(f+g)
1+2t+3t2+4t3\displaystyle 1 + 2 t + 3 t^{2} + 4 t^{3}
1+2t2+3t3\displaystyle 1 + 2 t^{2} + 3 t^{3}
2+2t+5t2+7t3\displaystyle 2 + 2 t + 5 t^{2} + 7 t^{3}

Zadanie: Napisać funkcję odejmowania wielomianów

%auto
def odejmowanie( f, g ) :
    """
    funkcja oblicza różnicę $f-g$ swoich argumentów
    """
    # wielomiany muszą mieć ten sam pierścień współczynników
    assert f.pierscien_wspolczynnikow == g.pierscien_wspolczynnikow, "Niezgodne pierścienie współczynników"

    # UZUPEŁNIĆ
    if deg(f)==deg(g):
        return  wielomian([f[i]-g[i] for i in [0,..,deg(f)] ], f.pierscien_wspolczynnikow)
    if deg(f)>deg(g):
        return wielomian([f[i]-g[i] for i in [0,..,deg(g)] ]+[f[i] for i in [deg(g)+1,.., deg(f)]], f.pierscien_wspolczynnikow)
    if deg(f)<deg(g):
        return wielomian([f[i]-g[i] for i in [0,..,deg(f)] ]+[-g[i] for i in [deg(f)+1,.., deg(g)]], f.pierscien_wspolczynnikow)

def odejmowanie2( f, g ) :
    """
    funkcja oblicza różnicę $f-g$ swoich argumentów
    """
    # wielomiany muszą mieć ten sam pierścień współczynników
    assert f.pierscien_wspolczynnikow == g.pierscien_wspolczynnikow, "Niezgodne pierścienie współczynników"

    # UZUPEŁNIĆ
    if deg(f)==deg(g):
        return  wielomian([f[i]-g[i] for i in [0,..,deg(f)] ], f.pierscien_wspolczynnikow)
    if deg(f)>deg(g):
        return wielomian([f[i]-g[i] for i in [0,..,deg(g)] ]+f[deg(g)+1:], f.pierscien_wspolczynnikow)
    if deg(f)<deg(g):
        return wielomian([f[i]-g[i] for i in [0,..,deg(f)] ]+przeciwny(g)[deg(f)+1:], f.pierscien_wspolczynnikow)

def odejmowanie3( f, g ) :
    """
    funkcja oblicza różnicę $f-g$ swoich argumentów
    """
    # wielomiany muszą mieć ten sam pierścień współczynników
    assert f.pierscien_wspolczynnikow == g.pierscien_wspolczynnikow, "Niezgodne pierścienie współczynników"

    # UZUPEŁNIĆ
    return f+przeciwny(g)

%auto
# wykonanie tej komórki pozwoli odejmować wielomiany
# za pomocą tradycyjnej notacji: f-g
wielomian.__sub__ = odejmowanie

f=wielomian([1,2,3,4])
g=wielomian([1,0,5,8,4])
view(f)
view(g)
view(f-g)
view(odejmowanie2(f,g))
view(odejmowanie3(f,g))
1+2t+3t2+4t3\displaystyle 1 + 2 t + 3 t^{2} + 4 t^{3}
1+5t2+8t3+4t4\displaystyle 1 + 5 t^{2} + 8 t^{3} + 4 t^{4}
2t−2t2−4t3−4t4\displaystyle 2 t - 2 t^{2} - 4 t^{3} - 4 t^{4}
2t−2t2−4t3−4t4\displaystyle 2 t - 2 t^{2} - 4 t^{3} - 4 t^{4}
2t−2t2−4t3−4t4\displaystyle 2 t - 2 t^{2} - 4 t^{3} - 4 t^{4}

Zadanie: Napisać funkcję mnożenia wielomianów algorytmem ,,szkolnym".

%auto
def mnozenie_szkolne( f, g ) :
    """
    funkcja oblicza iloczyn $f\cdot g$ argumentów, używając algorytmu "szkolnego"
    """
    # wielomiany muszą mieć ten sam pierścień współczynników
    assert f.pierscien_wspolczynnikow == g.pierscien_wspolczynnikow, "Niezgodne pierścienie współczynników"

    # UZUPEŁNIĆ
    n=deg(f)
    m=deg(g)
    fw=f[:]+[0]*m #tworzy wektor [:]
    gw= g[:] +[0]*n
    return wielomian([sum(fw[j]*gw[i-j] for j in [0..i]) for i in [0,..,(n+m)]],f.pierscien_wspolczynnikow)

f=wielomian([1,2,3,4])
view(f[:]+[0]*)
[1\displaystyle 1, 2\displaystyle 2, 3\displaystyle 3, 4\displaystyle 4, 0\displaystyle 0, 0\displaystyle 0, 0\displaystyle 0, 0\displaystyle 0]
f=wielomian([1,2,3,4])

g=wielomian([1,0,5,8])
view(f)
view(g)
view(mnozenie_szkolne(f,g))
1+2t+3t2+4t3\displaystyle 1 + 2 t + 3 t^{2} + 4 t^{3}
1+5t2+8t3\displaystyle 1 + 5 t^{2} + 8 t^{3}
1+2t+8t2+22t3+31t4+44t5+32t6\displaystyle 1 + 2 t + 8 t^{2} + 22 t^{3} + 31 t^{4} + 44 t^{5} + 32 t^{6}
%auto
# wykonanie tej komórki pozwoli mnożyć wielomiany
# za pomocą tradycyjnej notacji: f*g
wielomian.__mul__ = mnozenie_szkolne

f=wielomian([1,2,3,4])
g=wielomian([1,0,3])
view(f)
view(g)
view(f*g)
1+2t+3t2+4t3\displaystyle 1 + 2 t + 3 t^{2} + 4 t^{3}
1+3t2\displaystyle 1 + 3 t^{2}
1+2t+6t2+10t3+9t4+12t5\displaystyle 1 + 2 t + 6 t^{2} + 10 t^{3} + 9 t^{4} + 12 t^{5}
P.<x>=QQ[] #definiujemy pierscien wielomianu zmienneuj x
f1=1+2*x+3*x^2+4*x^3
g1=1+3*x^2
view(f1*g1)
f=P.random_element(5)
g=P.random_element(6)#wielomian o wspolczynnikach z P stopnia 5
view(f)
view(g)
K=f.list() #zwraca liste zawiarajaca wspolczynniki 
h=wielomian(K)
view(h)
view(P(h[:])) #wielomioan porezniesiony6 do P
12x5+9x4+10x3+6x2+2x+1\displaystyle 12 x^{5} + 9 x^{4} + 10 x^{3} + 6 x^{2} + 2 x + 1
12x5−12x4+x3+x2+3x+12\displaystyle \frac{1}{2} x^{5} - \frac{1}{2} x^{4} + x^{3} + x^{2} + 3 x + \frac{1}{2}
x6+14x5−x4+23x3−x2−32x−5\displaystyle x^{6} + \frac{1}{4} x^{5} - x^{4} + \frac{2}{3} x^{3} - x^{2} - \frac{3}{2} x - 5
12+3t+t2+t3−12t4+12t5\displaystyle \frac{1}{2} + 3 t + t^{2} + t^{3} - \frac{1}{2} t^{4} + \frac{1}{2} t^{5}
12x5−12x4+x3+x2+3x+12\displaystyle \frac{1}{2} x^{5} - \frac{1}{2} x^{4} + x^{3} + x^{2} + 3 x + \frac{1}{2}

Poniższa funkcja mnoży wielomian ff przez nn-tą potęgę zmiennej, za pomocą zapisu f << n (zwraca nowy wielomian =xn⋅f= x^n\cdot f) lub f <<= n (zastępuje ff wielomianem xn⋅fx^n\cdot f). Komórka wykona się automatycznie.


︠091932e2-11d7-4987-8d31-e52e3b124c89as︠
%auto

def przesun(self, n) :
    return wielomian( [0]*n+self._wspl, self.pierscien_wspolczynnikow )
    
def przesun_wstaw(self, n) :
    self._wspl = [0]*n + self._wspl
    return self

wielomian.__lshift__  = przesun    
wielomian.__ilshift__ = przesun_wstaw
[1, 2, 1, 3] 
# przykład użycia (wypróbować)
# wielomian f
f = wielomian([1,2,3]); view(f)
# x^2*f, ale f się nie zmienia
view( f << 2 )
# zastąp f przez x^2*f
f <<= 2
view(f)
1+2t+3t2\displaystyle 1 + 2 t + 3 t^{2}
t2+2t3+3t4\displaystyle t^{2} + 2 t^{3} + 3 t^{4}
t2+2t3+3t4\displaystyle t^{2} + 2 t^{3} + 3 t^{4}

Zadanie: Zaimplementować funkcję mnożenia wielomianów algorytmem Karatsuby

def karatsuba( f, g ):
    assert f.pierscien_wspolczynnikow == g.pierscien_wspolczynnikow
    if f.deg() < 0 or g.deg() < 0 :
        return wielomian([], f.pierscien_wspolczynnikow)
    df = deg(f)
    dg = deg(g)
    d = ceil(max(df, dg)/2)
    if d <= 0 :
        return wielomian([f[0]*g[0]], f.pierscien_wspolczynnikow)
    fl = wielomian( f[:d], f.pierscien_wspolczynnikow )
    fu = wielomian( f[d:], f.pierscien_wspolczynnikow )
    gl = wielomian( g[:d], f.pierscien_wspolczynnikow )
    gu = wielomian( g[d:], f.pierscien_wspolczynnikow )
    x = karatsuba(fl, gl)
    z = karatsuba(fu, gu)
    t = karatsuba( dodawanie(fl,fu), dodawanie(gl,gu) )
    y=odejmowanie(t,dodawanie(x,z))
    z <<= 2*d
    y <<= d
    return x+y+z

def mnozenie( f, g ) :
    """
    funkcja oblicza iloczyn $f\cdot g$ swoich argumentów, używając algorytmu Karatsuby
    """
    # wielomiany muszą mieć ten sam pierścień współczynników
    assert f.pierscien_wspolczynnikow == g.pierscien_wspolczynnikow, "Niezgodne pierścienie współczynników"

    # UZUPEŁNIĆ
    return karatsuba(f,g)


︠a909ece3-6ad0-45be-8a0a-b8b4f45b3998︠
# wykonanie tej komórki pozwoli mnożyć wielomiany
# za pomocą tradycyjnej notacji: f*g
wielomian.__mul__ = mnozenie

# sprawdzamy - przykład z wykładu
wielomian([1,2,3,4]) * wielomian([2,1,4,3])
2 + 5*t + 12*t^2 + 22*t^3 + 22*t^4 + 25*t^5 + 12*t^6

Zadanie: Napisać funkcje, które wyznaczają zawartość i część pierwotną wielomianu o współczynnikach całkowitych.

def zawartosc( f ) :
    assert f.pierscien_wspolczynnikow.is_unique_factorization_domain(), "Pierścień współczynników musi być z jednoznacznym rozkładem"

    # UZUPEŁNIĆ NWD wspolczynnikow 
    return  gcd(f[:])


f=wielomian([15,30,6,12])
zawartosc(f)
3 
def czesc_pierwotna( f ) :
    # UZUPEŁNIĆ
    return wielomian([f[i]/zawartosc(f) for i in [0..deg(f)] ])


view(czesc_pierwotna(f))
5+10t+2t2+4t3\displaystyle 5 + 10 t + 2 t^{2} + 4 t^{3}

Zadanie: Zaimplementować funkcję wyznaczania reszty i ilorazu wielomianów o współczynnikach z ciała.

Wskazówka: wyraz wiodący wielomianu ff otrzymujemy jako f.lc() lub lc(f).

def quo_rem(f, g) :
    """
    funkcja zwraca wielomiany $q$, $r$ t.ż.: $f = q\cdot g + r$ oraz $\deg r < \deg g$
    """
    # wielomiany muszą mieć to samo CIAŁO współczynników
    assert f.pierscien_wspolczynnikow.is_field(), "Pierścień współczynników musi być ciałem!"
    assert f.pierscien_wspolczynnikow == g.pierscien_wspolczynnikow, "Niezgodne ciała współczynników."

    # UZUPEŁNIĆ
    q=[]
    r=f
    c=lc(g)
    m=deg(f)
    n=deg(g)
    while m>=n:
        d=lc(r)/c
        q=[d]+q
        r=r-d*(g<<(m-n))
        k=min(m-deg(r)-1,m-n)
        q=[0]*k+q
        m=deg(r)
    q=wielomian(q,f.pierscien_wspolczynnikow)
    return (q,r)

Zadanie: Zaimplementować funkcję wyznaczania pseudo-reszty i pseudo-ilorazu.

def pquo_rem(f, g) :
    """
    funkcja wyznacza PSEUDO-iloraz i PSEUDO-resztę
    """
    # wielomiany muszą mieć ten sam pierścień współczynników
    assert f.pierscien_wspolczynnikow == g.pierscien_wspolczynnikow, "Niezgodne pierścienie współczynników"
    assert f.pierscien_wspolczynnikow.is_unique_factorization_domain(), "Pierścień współczynników musi być z jednoznacznym rozkładem"

    # UZUPEŁNIĆ
    q = []
    r = f
    c = lc(g)
    m = deg(f)
    n = deg(g)
    while m >= n :
        d = lc(r)*c^(m-n)
        q = [d] + q
        r = c*r - lc(r)*(g << (m-n))
        k = min(m - deg(r)-1, m-n)
        q = [0]*k + q
        r = c^k*r
        m = deg(r)
    q = wielomian( q, f.pierscien_wspolczynnikow )
    return (q,r)

Zadanie: Zaimplementować algorytm Euklidesa dla wielomianów o współczynnikach całkowitych.

# identyczność (funkcja pomocnicza)
# musimy użyć dużej litery, bo funkcja `id' jest funkcją wbudowaną
# (i robi zupełnie co innego)
def Id( x ) :
    return x
    
# alternatywny zapis
# Id = lambda x: x

def nwd( f, g, uprosc = Id ) :
    """
    funkcja oblicza $nwd(f,g)$ dwóch wielomianów o współczynnikach całkowitych 
    z użyciem algorytmu Euklidesa
    argumenty funkcji: 
        - f, g: wielomiany
        - uprosc: funkcja używana do upraszczania pseudo-reszty (domyślnie iddentyczność)
    """
    # współczynniki obu wielomianów muszą być całkowite, 
    # w przeciwnym razie zgłaszamy wyjątek (błąd)
    assert f.pierscien_wspolczynnikow == ZZ, "Współczynniki wielomianów muszą być całkowite!"
    assert g.pierscien_wspolczynnikow == f.pierscien_wspolczynnikow, "Oba wielomiany muszą pochodzić z tego samego pierścienia!"

    # UZUPEŁNIĆ

Zadanie: Porównać rozmiary współczynników w krokach pośrednich algorytmu Euklidesa, zależnie od użytej funkcji uprość.

Wskazówka: użyć funkcji verbose i set_verbose.

Zadanie: Wyznaczyć zespolony pierwiastek pierwotny z jedynki stopnia 16.

w=cos((2*pi)/16)+I*sin((2*pi)/16)
view(w)
view(CC(w))
12 2+2+12i −2+2\displaystyle \frac{1}{2} \, \sqrt{\sqrt{2} + 2} + \frac{1}{2} i \, \sqrt{-\sqrt{2} + 2}
0.923879532511287+0.382683432365090i\displaystyle 0.923879532511287 + 0.382683432365090i

Zadanie: Obliczyć dyskretną transformatę Fouriera wielomianu f=1+2t+3t2+4t3f = 1+2t+3t^2+4t^3 (tzn. ciągu jego współczynników) wprost z definicji.

f=wielomian([1,2,3,4])
N=deg(f)+1
view(f)
view(N)
w=cos((2*pi)/N)+I*sin((2*pi)/N)
view(w)
L=[]
var('k')

for n in [0,..,N-1]: #moja wizja
    fn1=sum(f[k]*w^(-k*n)for k in [0,..,N-1])
    L.append(fn1)
L

[sum(f[k]*w^(-k*n) for k in [0,..,N-1]) for n in  [0,..,N-1]]
1+2t+3t2+4t3\displaystyle 1 + 2 t + 3 t^{2} + 4 t^{3}
4\displaystyle 4
i\displaystyle i
k [10, 2*I - 2, -2, -2*I - 2] [10, 2*I - 2, -2, -2*I - 2] 
[f(w^(-k)) for k in [0,..,N-1]]
[10, 2*I - 2, -2, -2*I - 2]

Zadanie: Zaimplementować algorytm Cooley'a-Tukey'a szybkiej transformaty Fouriera. Obliczyć szybką transformatę Fouriera wielomianu f=1+2t+3t2+4t3f = 1+2t+3t^2+4t^3.

def fft( L, omega = 1 ) :
    """
    funkcja oblicza FFT listy L, używając algorytmu Cooley-Tukey
    lista musi mieć długość będącą potegą 2
    """

    # UZUPEŁNIĆ

Zadanie: Dla wielomianu z poprzedniego zadania, obliczyć (f(1),f(1/ω),f(1/ω2),f(1/ω3))\bigl(f(1), f(1/\omega), f(1/\omega^2), f(1/\omega^3)\bigr) bezpośrednio oraz używając FFT.

1+3t2+5t4\displaystyle 1 + 3 t^{2} + 5 t^{4}
def niepa(f):
    for i in [0,..,deg(f)]:
        if i.mod(2)==0:
            f[i]=0
    return f

f=wielomian([1])
view(niepa(f))
Error in lines 2-2 Traceback (most recent call last): File "/projects/sage/sage-6.9/local/lib/python2.7/site-packages/smc_sagews/sage_server.py", line 905, in execute exec compile(block+'\n', '', 'single') in namespace, locals File "", line 1, in <module> File "", line 4, in niepa TypeError: 'wielomian' object does not support item assignment 

︠8871fb0d-f6fa-4892-82d5-7076b9db6d68︠
def parzys(f):
    g=[0]*(deg(f)+1)
    for i in [0..deg(f)]:
        if i.mod(2)==0:
            g[i]=f[i]
    return(wielomian(g,f.pierscien_wspolczynnikow))
︠23ccb13e-9896-49d7-868a-2ee47e763be3s︠
def odejm(f,g):
    m=deg(f)
    n=deg(g)
    F=f[:]+[0]*n
    G=(g[:]+[0]*m)
    return wielomian([F[i]-G[i] for i in [0,..,(m+n)]])
1+t+2t2+t3+3t4+t5+2t6+t7+2t8+t9\displaystyle 1 + t + 2 t^{2} + t^{3} + 3 t^{4} + t^{5} + 2 t^{6} + t^{7} + 2 t^{8} + t^{9}
1+3t+4t2+5t3+6t4\displaystyle 1 + 3 t + 4 t^{2} + 5 t^{3} + 6 t^{4}
1+t+2t2+t3+3t4+t5+2t6+t7+2t8+t9\displaystyle 1 + t + 2 t^{2} + t^{3} + 3 t^{4} + t^{5} + 2 t^{6} + t^{7} + 2 t^{8} + t^{9}
1+3t+4t2+5t3+6t4\displaystyle 1 + 3 t + 4 t^{2} + 5 t^{3} + 6 t^{4}
−2t−2t2−4t3−3t4+t5+2t6+t7+2t8+t9\displaystyle -2 t - 2 t^{2} - 4 t^{3} - 3 t^{4} + t^{5} + 2 t^{6} + t^{7} + 2 t^{8} + t^{9}

Zdania dodatkowe: teoria grafów

Zadanie: Utworzyć i narysować graf `diament' (polecenie graphs.DiamondGraph())

g=graphs.DiamondGraph()
g.plot()

Zadanie: Wyznaczyć macierz sąsiedztwa tego grafu.

g.adjacency_matrix()
[0 1 1 0] [1 0 1 1] [1 1 0 1] [0 1 1 0]

Zadanie: Skonstruować i narysować graf (nieskierowany) o macierzy sąsiedztwa (011001101100100111100011111010 011100001100110101100010111110011011011100111000100 ) \begin{pmatrix} 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 1 \\ 1 & 0 & 0 & 1 & 0 & 0 & 1 & 1 & 1 \\ 1 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 \\ 0 & 1 & 0 &  0 & 1 & 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 1 & 0 & 0 & 0 & 1 & 0 \\ 1 & 1 & 1 & 1 & 1 & 0 & 0 & 1 & 1 \\ 0 & 1 & 1 & 0 & 1 & 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 & 0 & 1 & 0 & 0  \end{pmatrix} Czy jest to graf spójny? Czy jest to graf Eulera? Czy jest to graf płaski?

Wskazówka: użyć metod is_connected, is_eulerian, is_planar.

# 0, 1, 1, 0, 0, 1, 1, 0, 1  
# 1, 0, 0, 1, 0, 0, 1, 1, 1  
# 1, 0, 0, 0, 1, 1, 1, 1, 1  
# 0, 1, 0, 0, 1, 1, 1, 0, 0  
# 0, 0, 1, 1, 0, 0, 1, 1, 0  
# 1, 0, 1, 1, 0, 0, 0, 1, 0  
# 1, 1, 1, 1, 1, 0, 0, 1, 1  
# 0, 1, 1, 0, 1, 1, 1, 0, 0  
# 1, 1, 1, 0, 0, 0, 1, 0, 0

M=matrix([[0, 1, 1, 0, 0, 1, 1, 0, 1 ], [1, 0, 0, 1, 0, 0, 1, 1, 1], [ 1, 0, 0, 0, 1, 1, 1, 1, 1], [0, 1, 0, 0, 1, 1, 1, 0, 0],[0, 0, 1, 1, 0, 0, 1, 1, 0],[1, 0, 1, 1, 0, 0, 0, 1, 0],[1, 1, 1, 1, 1, 0, 0, 1, 1],[0, 1, 1, 0, 1, 1, 1, 0, 0],[1, 1, 1, 0, 0, 0, 1, 0, 0]])
view(M)
(011001101100100111100011111010011100001100110101100010111110011011011100111000100)\displaystyle \left(\begin{array}{rrrrrrrrr} 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 1 \\ 1 & 0 & 0 & 1 & 0 & 0 & 1 & 1 & 1 \\ 1 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 \\ 0 & 1 & 0 & 0 & 1 & 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 1 & 0 & 0 & 0 & 1 & 0 \\ 1 & 1 & 1 & 1 & 1 & 0 & 0 & 1 & 1 \\ 0 & 1 & 1 & 0 & 1 & 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 & 0 & 1 & 0 & 0 \end{array}\right)
g=Graph(M, format='adjacency_matrix') 
g.plot()

Zadanie: Używając metody coloring znaleźć kolorowanie grafu z poprzedniego zadania. Narysować pokolorowany graf.

P=g.coloring()
g.plot(partition=P)

Zadanie: W grafie z poprzedniego zadania wyznaczyć odległość wierzchołków 11 oraz 55. Jaka jest największa odległość wierzchołków w tym grafie (czyli jego średnica)?

Wskzaówka: metody distance oraz diameter.

g.distance(1,5)
g.diameter()
g.shortest_path(1,5)
2 2 [1, 0, 5]

Zadanie: Wyznaczyć najkrótszą ścieżkę łączącą wierzchołki 1 oraz 5.

Wskazówka: metoda shortest_path.