zmiana nazw

3 files changed, 51 insertions, 0 deletions

diff --git a/Semestr 4/aisd/lista0/L0Z8.md b/Semestr 4/aisd/lista0/L0Z8.md
new file mode 100644
index 0000000..d9c8604
--- /dev/null
+++ b/Semestr 4/aisd/lista0/L0Z8.md
@@ -0,0 +1,51 @@
+# 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
diff --git a/Semestr 4/aisd/lista0/Rozw L0.pdf b/Semestr 4/aisd/lista0/Rozw L0.pdf
new file mode 100644
index 0000000..d39c13b
--- /dev/null
+++ b/Semestr 4/aisd/lista0/Rozw L0.pdf
diff --git a/Semestr 4/aisd/lista0/lista0.pdf b/Semestr 4/aisd/lista0/lista0.pdf
new file mode 100644
index 0000000..31b9daa
--- /dev/null
+++ b/Semestr 4/aisd/lista0/lista0.pdf