From c5fcf7179a83ef65c86c6a4a390029149e518649 Mon Sep 17 00:00:00 2001 From: Franciszek Malinka Date: Tue, 5 Oct 2021 21:49:54 +0200 Subject: Duzy commit ze smieciami --- Semestr 4/aisd/lista0/L0Z8.md | 51 ------------------------------------------- 1 file changed, 51 deletions(-) delete mode 100644 Semestr 4/aisd/lista0/L0Z8.md (limited to 'Semestr 4/aisd/lista0/L0Z8.md') diff --git a/Semestr 4/aisd/lista0/L0Z8.md b/Semestr 4/aisd/lista0/L0Z8.md deleted file mode 100644 index d9c8604..0000000 --- a/Semestr 4/aisd/lista0/L0Z8.md +++ /dev/null @@ -1,51 +0,0 @@ -# AiSD, L0Z8 - -Dane: $n$, $m$. -Wynik: (Współczynnik przy $x^2$) $\mod m$ wielomianu $\underbrace{(\ldots((x-2)^2 -2)^2\ldots - 2)^2}_{n\text{ razy}}$. - -**Obserwacja 1:** Wszystkie obliczenia możemy wykonywać $\mod m$. Nie zwiększa to złożoności obliczeniowej, a ogranicza wartości które musimy utrzymywać. - -**Obserwacja 2:** Obliczając współczynniki wielomianu nie musimy obliczać współczynników przy większej potędze $x$ niż $2$. - -Niech $w_k(x)$ = $\underbrace{(\ldots((x-2)^2 -2)^2\ldots - 2)^2}_{k\text{ razy}}$, ale bez wyrazów gdzie $x$ występuje w potędze większej niż $2$. Dla jasności przyjmujemy $w_0(x) = x$. - -Mamy w takim razie $w_k(x) = a_k + b_kx + c_kx^2$. Ponadto: -\begin{align} - w_{k+1}(x) &= (a_k + b_kx + c_kx^2 - 2)^2 \\ - &= \underbrace{(a_k^2 - 4a_k + 4)}_{a_{k+1}} + \underbrace{(2a_kb_k - 4b_k)}_{b_{k+1}}x + \underbrace{(2a_kc_k + b_k^2 - 4c_k)}_{c_{k+1}}x^2 -\end{align} - -Dostajemy zatem układ rekurencyjny: -\begin{cases} -a_0=c_0=0 \\ -b_0=1 \\ -a_{k+1} = a_k^2 - 4a_k + 4 = (a_k - 2)^2 \\ -b_{k+1} = 2a_kb_k - 4b_k \\ -c_{k+1} = 2a_kc_k + b_k^2 - 4c_k \\ -\end{cases} - -**Obserwacja 3:** $a_k = 4$ dla $k \ge 1$. Faktycznie, policzmy $a_1 = (a_0 - 2)^2 = 4$. Ale $a_2 = (4 - 2)^2 = 4$. Zatem ciąg ten jest stale równy $4$ od $k = 1$. - -**Obserwacja 4:** $b_k = -(4^k)$ dla $k \ge 1$. Korzystając z zależności rekurencyjnej dla $k \ge 1$ mamy $b_{k+1} = 2b_k(a_k - 2) = 4b_k$, ale $b_1 = -4$, zatem $b_k = -(4^k)$. - -Korzystając z obserwacji 3. i 4. upraszczamy zależność rekurencyjną na $c_{k+1}$ dla $k\ge 1$: -\begin{align} -c_{k+1} = 8c_k + 4^{2k} - 4c_k = 4c_k + 4^{2k} -\end{align} - -Stąd już dostajemy łatwą zależność (dla $k\ge 1$): - -$$ -\left[\begin{array}{cc} -4 & 1\\ -0 & 16 -\end{array}\right] -\left[\begin{array}{cc} -c_k\\ -4^{2k} -\end{array}\right] = -\left[\begin{array}{cc} -c_{k+1}\\ -4^{2(k+1)} -\end{array}\right] -$$ \ No newline at end of file -- cgit v1.2.3