12. Rekurencja. Ciągi zadane rekurencyjnie. - Wstęp do matematyki 06-DPMALI0

Treści kształcenia: Ciągi zadane rekurencyjnie w informatyce. Granice ciągów, algorytmy obliczania granic (problem zbieżności). Problem stopu w algorytmach. Interpretacja geometryczna (aplety) (na ćwiczeniach: obliczanie granic, punkty skupienia ciągów).

Efekty kształcenia: Student potrafi operować ciągami rekurencyjnymi, badać ich zbieżność i granice. Potrafi określić podstawowe wady i zalety takich ciągów w zastosowaniach informatycznych.

Wstęp - Rekurencja¶

Rekurencja - odwoływanie się np. funkcji lub definicji do samej siebie.

Dalej będziemy się jednak zajmować głównie ciągami zdefiniowanymi rekurencyjnie. O rekurencji już mówiliśmy przy okazji wprowadzenia pojęcia ciągu. Teraz poszerzymy i usystematyzujemy materiał. To naturalna metoda definiowania wielu ciągów.

Na początek: znany (być może) ciąg Fibonacciego

a_1 = 1 \ , \ a_2 = 1 \ , a_{n+2} = a_{n+1} + a_n \qquad n = 1,2,3,...

ma wzór analityczny (ogólny) - co wykażemy, czyli możemy też nie korzystać z rekurencji:

a_n = \frac{1}{\sqrt{5}} \cdot ( \varphi^n - (1 - \varphi)^n ) ,

gdzie $\varphi$ jest tzw. ,,złotą proporcją’’ ( $\varphi =\frac{\sqrt{5}+1}{2}$ ).

Wyprowadzimy ten wzór i posłuży nam do wprowadzenia ogólnej metody badania ciągów rekurencyjnych (tylko podstawowe zasady!). Zastanowimy się, która z metod definiowania ciągu jest lepsza (i kiedy).

A inne znane nam ciągi zadane rekurencyjnie? Wspomnijmy też o ciągu arytmetycznym $a_n = a_{n-1} + r$ oraz geometrycznym $b_n = q \cdot b_{n-1}$ , których definicje są oczywiście rekurencyjne.

Nie zapominajmy też o rekurencyjnym definiowaniu silni: $(n+1)! = n! \cdot (n+1)$ , czyli dla $a_n = n!$
mamy $a_0 = a_1 = 1$ oraz $a_{n+1} = a_n \cdot (n+1)$ . Tak samo rekurencyjnie definiujemy też potęgi o wykładniku naturalnym...

I podstawowa informacja dla informatyków: jak się okaże, rekurencja to jedna z podstawowych metod obliczeniowych (i algorytmicznych), w trakcie zajęć postaramy się podać wiele ich zastosowań. W wielu problemach algorytmy wykorzystujące ciągi rekurencyjne są najprostszym, eleganckim, o krótkim kodzie i najbardziej naturalnym sposobem ich rozwiązywania, ale jednocześnie ma niekiedy wady (np. wzrost złożoności czasowej). Stąd warto poznać możliwości wprowadzania ciągów rekurencyjnych, ale i ich zamiany (o ile to możliwe) na wzory ogólne i procedury iteracyjne.

Rozpoczniemy od najprostszych pytań (zadania maturalne!):

Ćwiczenie 1¶

Ciąg $(a_n)$ dla każdego $n = 0,1,2,...,2016$ spełnia warunek

a_{n+1} = 3 a_{2017- n} + n .

Wyraz $a_3$ tego ciągu jest równy:

$A) - 755,5 \quad B) - 1511 \quad C) - 6044 \quad D) - 1510,5$

Rozwiązanie.

Podstawiamy w danym wzorze rekurencyjnym kolejno $n = 2$ , a potem $n = 2014$ . Czyli

a_3 = 3a_{2015} + 2

a_{2015} = 3a_3 + 2014 .

Podstawiamy teraz z drugiego równania do pierwszego:

a_3 = 3(3a_3 + 2014) + 2

- 6044 = 8a_3 \Rightarrow a_3 = - 755,5.

Odpowiedź: A).

Ćwiczenie 2¶

Ciąg $(a_n )$ jest określony wzorem

a_{n+1} + a_{n-1} = a_n - a_{n-2} + 5

dla każdej liczby naturalnej $n \geq 3$ . Wiadomo ponadto, że $a_2 = 3, a_4 = - 4$ i $a_6 = 9$ . Wyraz $a_3$ jest równy:

$A) - 1 \quad B) \ 0 \quad C) \ 5 \quad D) - 2$

Rozwiązanie.

Podstawiamy w danym wzorze rekurencyjnym $n = 4$ oraz $n = 5$ :

a_5 + a_3 = a_4 - a_2 + 5

a_6 + a_4 = a_5 - a_3 + 5

czyli

a_5 + a_3 = - 4 - 3 + 5

9 - 4 = a_5 - a_3 + 5

a_5 + a_3 = - 2 \qquad \qquad a_5 - a_3 = 0 .

Odejmujemy teraz od pierwszego równania drugie i mamy $2a_3 = - 2$ , $a_3 = - 1$ .

Odpowiedź: A).

Ćwiczenie 3¶

Ciąg $(a_n )$ jest określony wzorem

a_{n+1} = 3 - a_n

dla każdej liczby naturalnej $n$ . Oblicz sumę pięćdziesięciu początkowych wyrazów tego ciągu. Uwaga: $a_1$ - dowolne!

(samodzielnie)

Ćwiczenie 4¶

Pierwszymi wyrazami ciągu są: 2, 8, 14, ... Znajdź parametry $A$ i $B$ , dla których określa go następujący wzór rekurencyjny

a_1 = A \ , \ a_n = a_{n-1} + B .

Odpowiedź: $A=2, B=6$ .

Informatycy pewnie nie zwrócili na to uwagi - ale istotne jest pytanie: skąd wiemy, że rekurencja poprawnie nam coś definiuje? Na szczęście mamy

Twierdzenie. Niech $X$ będzie dowolnym zbiorem. Załóżmy, że $a \in X$ i $F: X \to X$ . Istnieje wtedy dokładnie jedna funkcja $g: {\mathbb{N}} \to X$ taka, że $g(0) = a$ oraz $g(n + 1) = F (g(n))$ dla $n \in {\mathbb{N}}$ .

Pytanie. Ważną kwestią jest, czy ciąg zdefiniowany rekurencyjnie możemy zapisać wzorem ogólnym (a wiemy, że tak jest dla ciągu arytmetycznego i geometrycznego)? A odwrotnie?

A co więcej: jeśli ciąg wyrazimy w obu postaciach, to która z postaci jest ``korzystniejsza’’ - choćby pod względem symulacji komputerowych?

Odpowiedzi nie są oczywiste, ale pokażemy, że w przypadku rekurencji liniowej znamy algorytm uzyskiwania wzoru ogólnego (choć nie zawsze będzie efektywny - np. dla rekurencji wyższych stopni!). Na drugie pytanie też nie ma łatwej odpowiedzi - to ważny problem w informatyce. Warto prześledzić to na przykładzie problemu wież Hanoi ...

A dlaczego warto rozważać obie postacie (rekurencyjną i wzór ogólny)? Prosty

Przykład¶

Obliczanie żądanego wyrazu w ciągu. Rozpatrzmy dla ciąg arytmetyczny ( $a_1$ i $r$ są ustalone)

a_{n+1} = a_n + r .

Zadanie polega na obliczeniu wyrazu $a_{1000}$ .

Ze wzoru rekurencyjnego wymaga to obliczenia wszystkich poprzednich. Za to wykorzystanie wzoru ogólnego

a_{n+1} = a_n + r = (a_{n-1} + r) + r = a_{n-1} + 2r = (a_{n-2} + r) + 2r = a_{n-2} + 3r = ... = a_1 + n\cdot r \ .

Tak dla przypomnienia: powyższy dowód formalnie wymaga zastosowania indukcji matematycznej - polecam to jako samodzielne ćwiczenie. Za to z tego wzoru mamy w jednym prostym kroku

a_{1000} = a_1 + 999\cdot r .

Złożoność obliczeniowa jest znacznie mniejsza (1 krok zamiast 999 kroków obliczeniowych).

Są więc sytuacje, w których warto znać wzór ogólny (choć nie zawsze to będzie możliwe). Pokażemy, jak to zrobić w przypadku rekurencji liniowej... Ale rozpoczniemy od rozwiania wątpliwości, czy w ogóle potrzebujemy narzędzi matematycznych - może wystarczy komputer?

Rekurencja - pułapki komputera...¶

Czy komputer może być przydatny? Albo w ogóle zastąpić obliczenia matematyczne? Po kolei odpowiemy na te pytania. Czy może być przydatny - tak, ale...

Przykład (A)¶

Rozpatrzmy najpierw próbę wyznaczenia wartości przybliżonej liczby $\pi$ . Zastosujemy algorytm Archimedesa: geometryczną metodę opartą o wpisywanie kolejnych wielokątów foremnych w koło.

Liczymy $a_2$ , czyli wpisujemy kwadrat. Promień okręgu wynosi $\frac{1}{2}$ , czyli przekątna kwadratu ma długość 1, a więc bok $a_2 = \frac{\sqrt{2}}{2}$ . W tej konstrukcji dokonujemy w kolejnych krokach podwojenia liczby boków, czyli

w trójkącie o 2 bokach równych promieniowi (czyli: $r = \frac{1}{2} = |OC| = |OD|$ ) oraz trzecim boku będącym odcinkiem o końcach na okręgu (bok wielokąta $CD$ ) o długości $a_n = 2s$ jego wysokość $h = |ON|$ (z twierdzenia Pitagorasa) wyniesie

h^2 = \left(\frac{1}{2}\right)^2 - \left(\frac{a_n}{2}\right)^2 .

W takim razie w trójkącie równoramiennym o bokach $a_n$ (podstawa) i $a_{n+1}$ (ramiona) jego wysokość $H = |NM|$ wyniesie

H = \frac{1}{2} - h = \frac{1}{2} - \sqrt{\left(\frac{1}{2}\right)^2 - \left(\frac{a_n}{2}\right)^2 } .

Ponownie stosując twierdzenie Pitagorasa uzyskamy

H^2 + \left(\frac{a_n}{2}\right)^2 = a_{n+1}^2 .

Czyli ostatecznie podstawiając i porządkując wyrazy uzyskujemy

a_{n+1} = \frac{1}{2} \sqrt{2 - \sqrt{4- 4 a_n^2}} .

Teraz obliczamy obwód tego wielokąta

O_n = 2^n \cdot a_n .

Jeżeli ten ciąg jest zbieżny (o czym później), to do liczby $\pi$ .
O tym, jak badać istnienie granicy - już wkrótce (do tematu wrócimy), a teraz o sile i słabości obliczeń na komputerze. Czy musimy użyć matematyki, a może wystarczy komputer? Wykonamy symulację w oparciu o obliczenia na komputerze kolejnych wyrazów ciągu i spójrzmy, czy faktycznie dostaniemy poprawną hipotezę.

Obliczmy:

R = RealField(55)
a = sqrt(R(2))/2
m = 4
n = 1
nmax = 34

while n < nmax:
    O = m*a
    print("O[%s]=%s"%(n,O))
    m = m*2
    a=sqrt(2-sqrt(4-4*a*a))/2 
    n = n+1

O[1]=2.828427124746190
O[2]=3.061467458920718
O[3]=3.121445152258052
O[4]=3.136548490545939
O[5]=3.140331156954757
O[6]=3.141277250932793
O[7]=3.141513801144290
O[8]=3.141572940366725
O[9]=3.141587725277645
O[10]=3.141591421513899
O[11]=3.141592345574021
O[12]=3.141592576693229
O[13]=3.141592634056147
O[14]=3.141592647692809
O[15]=3.141592645321216
O[16]=3.141592645321216
O[17]=3.141592607375720
O[18]=3.141592910939673
O[19]=3.141594125195191
O[20]=3.141596553704820
O[21]=3.141596553704820
O[22]=3.141674265021758
O[23]=3.141829681889201
O[24]=3.142451272494134
O[25]=3.142451272494134
O[26]=3.162277660168379
O[27]=3.162277660168379
O[28]=3.464101615137755
O[29]=4.000000000000000
O[30]=0.0000000000000000
O[31]=0.0000000000000000
O[32]=0.0000000000000000
O[33]=0.0000000000000000

I - niestety - efekt jest inny od oczekiwanego! Mogło się wydawać, że niezłe przybliżenie

\pi \approx 3,141592653589

jest osiągane (dla $n=14$ ), a tu zwiększanie liczby boków sugeruje wynik zero (??). Czy w związku z tym ciąg w ogóle jest zbieżny???

Dlaczego symulacja nie działa? No cóż - to nie jest najlepszy algorytm, obliczamy wartości niewymierne i nawet wykorzystanie dobrej biblioteki systemowej z funkcją sqrt nie pomogło (problem: zero maszynowe). Zastanowimy się jeszcze, jak obliczane są pierwiastki w typowych bibliotekach, co pozwoli z nich nie korzystać pisząc jedynie własny algorytm!

Dla chętnych - spróbować poprawić ten program!

Należy zachować ostrożność we wnioskach symulacji na komputerze. Prezentacja: ciąg rekurencyjny w prezentacji CDF - wymaga CDF Player

Ale czy wiemy, że nasze symulacje granic innych ciągów będą poprawne i pewne? Nie możemy być tego pewni, tylko matematyka to rozstrzyga! A dla nas to cenna informacja: niestety (?) - bez matematyki się nie obejdzie...

Problem podzielimy na dwa: po pierwsze wykażemy, że granica istnieje i dopiero w drugim kroku możemy ją wyznaczyć - ale - jak widać - kontrolując ograniczenia komputera. Do tego przykładu wrócimy, gdy już będziemy wiedzieli, jak sprawdzić zbieżność tego ciągu.

Uwaga też na kolejne zjawisko: pozorną zbieżność ciągu. To sytuacja, gdy wykonując symulację i obliczając pewną liczbę elementów wydaje się (!), że mamy kandydata na granicę, a ciąg w ogóle nie jest zbieżny!
Sprawdźmy:

a_{n+2} = c\cdot a_n + d\cdot a_{n+1}^2 + k

dla ustalonych $a_1$ i $a_2$ oraz odpowiednio dobierając $c$ , $d$ i $k$ .

R = RealField(55)
c = R(14/10)
d = R(3/10)
k = 1
a0 = R(136.462554878752)
a1 = R(5.39650717129623)
nmax = 60

for n in range(1,nmax+1):
    a2=d*a0+k-c*a1*a1
    print("a[%s] = %s"%(n,a0))
    a0,a1 = a1, a2

a[1] = 136.4625548787520
a[2] = 5.396507171296230
a[3] = 1.167560953833307
a[4] = 0.7104741381062694
a[5] = 0.6435853848650074
a[6] = 0.6332592347753053
a[7] = 0.6316514536600149
a[8] = 0.6314007879574576
a[9] = 0.6313616990513867
a[10] = 0.6313556033465619
a[11] = 0.6313546526874743
a[12] = 0.6313545045457987
a[13] = 0.6313544812318629
a[14] = 0.6313544780035630
a[15] = 0.6313544767163468
a[16] = 0.6313544780233880
a[17] = 0.6313544753266455
a[18] = 0.6313544804860390
a[19] = 0.6313544705562790
a[20] = 0.6313544896578526
a[21] = 0.6313544529113052
a[22] = 0.6313545236020490
a[23] = 0.6313543876115133
a[24] = 0.6313546492217822
a[25] = 0.6313541459519106
a[26] = 0.6313551141116017
a[27] = 0.6313532516247501
a[28] = 0.6313568345614775
a[29] = 0.6313499419209406
a[30] = 0.6313632015394381
a[31] = 0.6313376934149013
a[32] = 0.6313867640848043
a[33] = 0.6312923638183979
a[34] = 0.6314739611638526
a[35] = 0.6311246000663658
a[36] = 0.6317966232166535
a[37] = 0.6305036176687572
a[38] = 0.6329902503142495
a[39] = 0.6282037655105725
a[40] = 0.6374011156919475
a[41] = 0.6196688744536965
a[42] = 0.6536350151541888
a[43] = 0.5877664360862457
a[44] = 0.7124333678009192
a[45] = 0.4657441058472500
a[46] = 0.9100454093562396
a[47] = -0.01973247417233714
a[48] = 1.272468504055125
a[49] = -1.272766273588904
a[50] = -0.8861670308430030
a[51] = -0.4812386912510168
a[52] = 0.4099229416073111
a[53] = 0.6203768473463076
a[54] = 0.5841624766695118
a[55] = 0.7083689353957711
a[56] = 0.4727475749136202
a[57] = 0.8996243031973389
a[58] = 0.008770830809469499
a[59] = 1.269779592496878
a[60] = -1.254645049687312

Ale jeśli liczymy dalej (np. $nmax = 60$ ), to teraz nie ma pomysłu, co jest granicą (przykład za: [1.])!

Pamiętajmy: najpierw zapewniamy sobie, że badany ciąg jest zbieżny, a dopiero później robimy symulacje! A tu granica nie istnieje, ale dowód tego jest trudny - zamiast tego polecam symulację np. dla $nmax = 5000$ .

A kto nie wierzy w słabości symulacji, to poproszę samodzielnie - w dowolnym programie - obliczyć wyrazy ciągu

a_n = \sum_{k=3}^n \frac{1}{k \ln k \ln (\ln k)} .

i sformułować hipotezę o jego zbieżności lub nie. Proszę o ostrożność...

Uwaga: proszę nie spodziewać się, że ciągi rekurencyjne to łatwe obiekty do badań czy symulacji komputerowych. Są bardzo ważne w zastosowaniach ciągi jak np. równanie logistyczne (rekurencyjne)

a_{n+1} = r \cdot a_n\cdot (1 - a_n) \ , a_1 = A .

Nawet nie wiadomo, czy przy dowolnych $r, A$ te ciągi są zbieżne! Wszyscy ufający symulacjom komputerowym: proszę eksperymentować, np. dla

r = -0.5 , \ 2,\ 3, \ 3.2 , \ 4

i zobaczyć to na rysunku... (w ostatnim przypadku - uważać = to tzw. chaos)

Uwaga: Mówiliśmy o ciągach rekurencyjnych, a wcześniej również o arytmetyce komputerowej. No to teraz przykład, gdy błędy obliczeń w arytmetyce ... pomagają. Szczegóły wymagają - niestety - więcej informacji zarówno z algebry, jak i informatyki! Krótko wyjaśnimy, o co chodzi.

Metoda potęgowa służy do przybliżania unormowanego wektora własnego odpowiadającego największej wartości własnej macierzy $A$ , nieosobliwej i dodatnio określonej. Idea tej metody jest bardzo prosta: dla wektora startowego $x_0$ mnożymy macierz przez ten wektor

x_n = A\cdot x_{n-1} ,

czyli to rekurencja...

Okazuje się, że podczas sukcesywnego wymnażania przez macierz $A$ najszybciej rośnie składowa w kierunku wektora odpowiadającego największej wartości własnej. Co więcej, jeżeli $x_n$ zostanie w każdym kroku wydzielone przez swoją długość (znormalizowane), to składowe w pozostałych kierunkach będą wygaszane (coraz mniejsze). Algorytm powinien znajdować największą wartość własną macierzy $A$ (zastosowanie np. w macierzy wyszukiwań algorytmu ‘‘GooglePageRank’’ to odpowiada najbardziej trafnej odpowiedzi na pytanie zadane w wyszukiwaniu).

To gdzie problem? Wektor początkowy $x_0$ musi mieć niezerowy rzut na prostą wyznaczaną przez poszukiwany wektor własny. W przeciwnym wypadku (teoretycznie) ciąg nie jest zbieżny.

Ale - i tu uwaga błędy zaokrągleń - w praktyce obliczeniowej, nawet jeśli $x_0$ ma zerową składową w kierunku wektora odpowiadającego największej wartości własnej, to po kilku iteracjach ta składowa będzie niezerowa dzięki błędom zaokrągleń. Powoduje to, że metoda potęgowa jest (praktycznie) zbieżna dla każdego $x_0$ .

Ćwiczenie 5. Korzystamy z rekurencji: bierzemy kwadrat o boku $a$ i w kolejnych krokach dodajemy kolejne takie same kwadraty z prawej i u góry, ale tak, by nadal tworzyło to kwadrat. Czyli w kroku drugim mamy dodatkowo 3 kwadraty (góra, prawo i ‘‘narożnik’’ prawo-góra). Procedurę powtarzamy.

... można zrobić rysunek na tablicy ...

Pytanie: ile takich kwadratów będzie w $n$ -tym kroku? Wyprowadzić wzór rekurencyjny.

Odp.: $x_1 = 1$ , $x_n = x_{n-1} + 2n -1$

Zadania dodatkowe¶

(1) Definiujemy rekurencyjnie ciąg za pomocą wzorów: $a_0 = a_1 = 1$ oraz $a_n = a_{n-1} + 2 a_{n-2}$ dla $n \geq 2$ . Obliczyć $a_6$ i pokazać, że wszystkie wyrazy ciągu są nieparzyste.

(2) Definiujemy rekurencyjnie ciąg za pomocą wzorów: $b_0 = b_1 = 1$ oraz $b_n = 2b_{n-1} + b_{n-2}$ dla $n \geq 2$ . Obliczyć $b_6$ i pokazać, że wszystkie wyrazy ciągu są nieparzyste.

(3) Podaj definicję rekurencyjną ciągu $2 \ , \ 2^2 \ , \ (2^2)^2 \ , ((2^2)^2)^2 , ...$ i wyraz ogólny tego ciągu.

(4) Mamy alfabet złożony z 0 i 1. Ciąg $a_n$ oznacza liczbę słów w tym alfabecie o długości $n$ , ale niezawierających układu znaków ‘‘01’’ (w takiej ustalonej kolejności). Obliczyć 5 pierwszych wyrazów tego ciągu i znaleźć wzór ogólny Odp.: $2,3,4,5,6$ , $a_n = n+1$

(5) Dany jest ciąg rekurencyjny

P_0 = 1, P_1 = 2, P_{n+2} = 2P_{n+1} + P_n \ .

Obliczyć 5 pierwszych liczb. Dla ambitnych: pokazać, że $(P_n)^2 + (P_{n+1})^2 = P_{2n+2}$ . Nieco później poszukamy wzoru ogólnego na ten ciąg (czyli: $\frac{1}{2\sqrt{2}} ((1+\sqrt{2})^{n+1} - (1-\sqrt{2})^{n+1})$ ).

(6) Zbadaj zbieżność ciągu

a_1 = 1 \ , a_{n+1} = \frac{2}{a_n} .

(7) Wieże Hanoi. Proszę samodzielnie zapoznać się z problemem wież Hanoi i przeanalizować wzór rekurencyjny i wzór jawny (np. M. Sysło ,,Algorytmy’') Odp.: $H_0 = 0, H_{n+1} = 2H_n +1$ oraz $H_n = 2^n - 1$

(8) Oblicz sumę $n$ początkowych wyrazów ciągu $(a_n)$ określonego dla $n \geq 1$ , w którym

a_1 = 3 \quad , \quad a_{n+1} = 10 a_n + 3 ,

dla $n \in {\mathbb{N}}$ .

Rozwiązanie:

Najpierw skorzystamy ze wzoru na sumę kolejnych wyrazów ciągu geometrycznego:

a_n = 33...30 + 3 = 33333...3 = 3 + 3\cdot10 + 3\cdot 10^2 + ... + 3\cdot 10^{n-1} = 3\cdot \frac{1 - 10^n}{1 - 10} = \frac{10^n - 1}{3} .

Stąd

a_1 + a_2 + ... + a_n = \frac{10^1 - 1}{3} + \frac{10^2 - 1}{3} + \ldots + \frac{10^n - 1}{3} = \frac{10 + 10^2 + ... + 10^n}{3} - \frac{n}{3} = \frac{10}{3} \cdot \frac{1 - 10^n}{1 - 10} - \frac{n}{3}

= \frac{10}{27} \cdot (10^n - 1) - \frac{n}{3} = \frac{1}{27}10^{n+1} - \frac{1}{3} n - \frac{10}{27}.

(9) Kupujemy na raty telewizor. Każda kolejna rata ma być mniejsza od poprzedniej o stałą kwotę. Ile zapłacimy za telewizor, jeśli spłacamy go w 7 ratach, z których czwarta rata była równa 350 zł?

(10) Podobnie jak w ćwiczeniu 5. podać wzór rekurencyjny dla takiej konstrukcji w 3 wymiarach, czyli bierzemy kostkę, a w kolejnych krokach dodajemy kostki w prawo, w głąb i w górę plus uzupełniamy wszystko do kostki sześciennej. Podać wzór rekurencyjny na ilość kostek potrzebnych w $n$ -tym kroku.

(11) Ułożyć własne zadanie na wzór ćwiczenia 5 i zadania (10): dwu- i trójwymiarowe konstrukcje mile widziane...