[ Pobierz całość w formacie PDF ]
U(x) = x/((1-2x)(1-3x))
Mimo iż U(x) jest już dobrze wyrażoną funkcją tworzącą, nie jesteśmy w
stanie odgadnąć jej współczynników będących zarazem rozwiązaniem równania
rekurencyjnego. W tym celu musimy rozpisać otrzymany wynik na ułamki
proste, a następnie tak dobrać stałe A i B, by funkcja tworząca pozostała bez
zmian:
U(x) = x/((1-2x)(1-3x)) = A/(1-2x) + B/(1-3x)
87
- Grafy i rekurencje -
Stąd A = -1, B = 1
Czyli ostatecznie U(x) = 1/(1-3x) -1/(1-2x)
Skoro (1-�x)-1 = 1 + �x + �2x2 + �3x3 + �4x4 ...
to un = 3n 2n.
Formalizacja:
Funkcja tworząca dla równania rekurencyjnego k-tego stopnia ma postać:
U(x) = R(x) / (1 + a1x + a2x2 + ... + akxk ) (*)
gdzie a1, a2,... są liczbami z równania rekurencyjnego un+k+ a1un+k-1+...+akun = 0
Dla takiej funkcji tworzącej definiuje się równanie pomocnicze:
tk + a1tk-1 + a2tk-2 + ... +ak = 0 (**)
Równanie (**) ma w zbiorze liczb zespolonych k pierwiastków. Wśród
nich wyróżniamy pierwiastki �1, �2, ... ,�s z odpowiednimi krotnościami
m1, m2, ... ,ms , przy czym suma wszystkich krotności wynosi k. Równanie (**)
może być więc zapisane w następujący sposób:
(t- �1)m1 * (t- �2)m2 * ... * (t- �s)ms = 0
co po podstawieniu za t�! 1/x i pomnożeniu przez xk daje:
(1- �1x)m1 * (1- �2x)m2 * ... * (1- �sx)ms = 0
stąd funkcja tworząca może być zapisana jako:
U(x) = R(x)/ ((1- �1x)m1 * (1- �2x)m2 * ... * (1- �sx)ms)
Teraz pozostaje już tylko rozłożyć funkcję tworzącą na czynniki, które pomogą
nam zidentyfikować wartości równania rekurencyjnego.
U(x) = (...)/(1- �1x)m1 + (...)/(1- �2x)m2 + ... + (...)/(1- �sx)ms
Gdyby krotność każdego rozwiązania równania była równa 1, to rozkład byłby
trywialny, a dobór odpowiednich czynników natychmiastowy. Gdy jednak
krotności są różne od 1, należy przeprowadzić następującą redukcję:
Ci, j
(...) m
= gdzie Ci,j są odpowiednimi stałymi.
"
j
(1-�i x)m j=1 (1-�i x)
Jako przykład wezmy następujące równanie rekurencyjne:
u0 = 0, u1 = -9, u2 = 1, u3 = 21
un+4 5un+3 + 6un+2 + 4un+1 8un = 0
88
- Grafy i rekurencje -
którego równanie pomocnicze ma postać:
t4 5t3 + 6t2 + 4t 8 = 0
lub (t - 2)3(t + 1) = 0
Każdemu pierwiastku tego równania będzie w rozwiązaniu równania
rekurencyjnego odpowiadał wielomian stopnia o jeden mniejszego niż krotność
pierwiastka:
un = (An2 + Bn + C)*2n + D*(-1)n
Po rozwiązaniu zestawu równań wyznaczającego wartości A, B, C, D:
u0 = 0 = C + D
u1 = -9 = 2A + 2B + 2C D
u2 = -1 = 16A +8B +4C + D
u3 = 21 = 72A + 24B + 8C D
otrzymujemy końcowy wzór na n- ty element równania rekurencyjnego:
un = (n2 - n - 3)*2n + 3*(-1)n
Na koniec przedstawimy jeszcze równanie rekurencyjne liniowe, które
posiada czynnik wolny i wyznaczymy jego funkcję tworzącą:
u0 = 0, u1 = 1
un+2 un+1 6un = n
U(x) = u0 + u1x + u2x2 + u3x3 + ...
= x + (u1 + 6u0 + 0)x2 + (u2 + 6u1+1)x3 + (u3 + 6u2 + 2)x4 + ...
= x + (u1x2 + u2x3 + u3x4 +...) + 6(u0x2 + u1x3 + u2x4 + ...) +
+ (x3 +2x4 + 3x5 +...)
= x + xU(x) + 6x2U(x) + x3(1 + 2x + 3x2 + ...)
= x + xU(x) +6x2U(x) + x3(1-x)-2
czyli funkcja tworząca ma postać:
U(x) = (x3(1 - x)-2 + x)/(1 x 6x2)
Wyznaczenie kolejnych wyrazów odpowiadającego jej równania
rekurencyjnego może być dobrym ćwiczeniem utrwalającym przedstawioną
teorię.
89
- Grafy i rekurencje -
Rozdział VIII Przykładowe procesy rekurencyjne
VIII. 1 Stan rejestru przesuwającego
Załóżmy, że dany jest przerzutnik pokazany na poniższym rysunku:
d
q0
c
d napięcie danych
c impuls zapisu
q0 napięcie stanu przerzutnika
Rysunek 40 Przerzutnik danych
Pod wpływem impulsu c do przerzutnika zapisywana jest dana d, tzn.
stan q przyjmuje wartość d.
Rejestr przesuwający jest szeregowym zestawem przerzutników
pokazanym na poniższym rysunku.
qN qN-1 qn qn-1 q1
QN QN-1 QQ Q1
d
n n-1
Nn ... 1
...
c
Qn stan n- tego przerzutnika
Rysunek 41 Rejestr przesuwający
W rejestrze tym pod wpływem impulsu zapisu c stan Qn-1 zostaje zapisany
do następnego przerzutnika.
Oznaczamy stan początkowy rejestru przez:
Q0 = [ qN0, ...,qn0 ,..., q10 ]
Po pierwszym impulsie zapisu stan rejestru przyjmuje postać:
Q1 = [ qN1, ..., qn1 , ..., qn1 ]
90
- Grafy i rekurencje -
przy czym
q11 = d
q21 = q10
...........................
qn1 = qn-10
...........................
qN1 = qN-10
W analogiczny sposób modyfikowany jest stan rejestru przesuwającego
po kolejnych impulsach zapisu. W rejestrach przesuwających ze sprzężeniem
zwrotnym sygnał d jest funkcją stanu rejestru:
d = f ( qN,...,qn ,..., q1 )
Funkcję tę realizuje układ bramek logicznych. Tak więc stany rejestru
opisują równania rekurencyjne:
q1k = f(q1k-1, ..., qnk-1, & , qNk-1 )
qnk = qn-1k-1 n=2, ..., N
Na podstawie danego stanu początkowego Q� można wygenerować graf
stanów Qk, k = 1,...,K.
q4 q3 q2 q1
4321
q3* q4
Rysunek 42 Przykładowa modyfikacja rejestru przesuwającego
Stan początkowy rejestru:
Q0 = [q40 q30 , q20 , q10 ] = [ 1101 ]
,
Kolejne stany tworzą ciąg przedstawiony na rysunku
Q0 = [ 1101 ]
Q1 = [ 1011 ]
Q2 = [ 0110 ]
Q3 = [ 1100 ]
Q4 = [ 1001 ]
Q5 = [ 0010 ]
91
- Grafy i rekurencje -
Q6 = [ 0100 ]
Q7 = [ 1000 ]
Q8 = [ 0000 ]
Po 8 impulsach rejestr znajdzie się w ustalonym stanie [ 0, 0, 0, 0, 1 ].
W analogiczny sposób można podstawić zmiany stanu rejestru przesuwającego
dowolnego układu realizującego funkcję f.
VIII. 2 Stan procesu montażu
Załóżmy, że dana jest linia montażowa pokazana na poniższym rysunku
....
0 1 n N
....
Rysunek 43 Linia montażowa
Linia składa się z N stacji montażowych. Operacje na stacjach są
wykonywane przez roboty przemysłowe. Stacja ni 0 służy do sprowadzania
nowych obiektów do montażu.
W trakcie cyklu każdy robot wykonuje operacje na obiekcie
znajdującym się na jego stacji. Po zakończeniu operacji przez wszystkie roboty,
każdy obiekt jest przesuwany (synchronicznie) na kolejną stację.
Na linii montowane są równocześnie obiekty M różnych wersji. Czasy
montażu obiektów różnych wersji na stacjach dane są macierze:
T = [ tm, n ]
m = 1,..,M
n = 1,...,N
gdzie: tm,n czas montażu obiektu m tej wersji na n-tej stacji
Czas każdego cyklu wyznaczamy jako
Ck = max Cnk
1d" n d" N
gdzie: Cnk =tm, n jeśli w k- tym takcie na n- tej stacji był montowany obiekt
m- tej wersji.
92
- Grafy i rekurencje -
Załóżmy, że zamówienia na obiekty dane są w wektorze;
Z = [ Zm ]
m = 1,...,M
gdzie: Zm liczba obiektów m- tej wersji
Problem polega na zmontowaniu zamówionych obiektów w najkrótszym czasie.
Oznaczamy przez Xk wektor stanu linii montażowej po k- tym cyklu,
( k = 0, 1, ..., K ).
Stan ten definiujemy następująco;
Xk = [ Xnk ]
n = 0,1, ... , N
gdzie: Xnk - numer wersji obiektu znajdującego się na n- tej stacji po k- tym
cyklu.
Stan początkowy X0 jest dany. Załóżmy, że
X00 = 0
Xn0 > 0 n =1, ...,N
To znaczy, że na każdej stacji montażowej znajduje się jakiś obiekt. Czas
pierwszego cyklu wyznaczamy z warunku:
C1 = max Cn1
1 d" n d" N
przy czym Cn1 = tm,n
oraz m = Xn0
W trakcie pierwszego ( i każdego następnego )cyklu do stacji
załadunkowej jest podawany obiekt wybranej wersji. Decyzja o obiekcie
załadowanym do linii w k-tym cyklu będzie oznaczona przez dk , przy czym:
m, jeśli w k- tym cyklu do linii jest załadowany
obiekt m tej wersji
{
dk = 0, jeśli w k-tym cyklu do linii nie jest załadowany
żaden obiekt
93
- Grafy i rekurencje -
Stan linii montażowej po takcie k jest zależny od stanu linii po
poprzednim takcie oraz od decyzji w k- tym takcie. Rekurencyjne równania
stanu mają postać:
Xk = fx (X k-1 , dk )
k = 1,..., K
W postaci jawnej mamy
Xnk = Xn-1k-1
n = 2,...,N
X1k = dk
Ponadto obliczamy czas cyklu Ck, k = 1, ..., K.
W analogiczny sposób można przedstawić rekurencyjne równanie
zamówień:
Zk = fz ( Zk-1 , Xk-1 )
k =1, ..., K
W postaci jawnej mamy:
Zmk-1 1 , dla XNk-1 = m
{
Zmk = Zmk-1 , dla XNk-1 `" m
[ Pobierz całość w formacie PDF ]
zanotowane.pldoc.pisz.plpdf.pisz.plalternate.pev.pl
|
