AiSD l0

6 files changed, 51 insertions, 10 deletions

diff --git a/Semestr 4/aisd/Lista 0/L0Z8.md b/Semestr 4/aisd/Lista 0/L0Z8.md
new file mode 100644
index 0000000..d9c8604
--- /dev/null
+++ b/Semestr 4/aisd/Lista 0/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/Lista 0/Rozw L0.pdf b/Semestr 4/aisd/Lista 0/Rozw L0.pdf
new file mode 100644
index 0000000..ab8362b
--- /dev/null
+++ b/Semestr 4/aisd/Lista 0/Rozw L0.pdf
diff --git a/Semestr 4/aisd/lista0.pdf b/Semestr 4/aisd/Lista 0/lista0.pdf
index 31b9daa..31b9daa 100644
--- a/Semestr 4/aisd/lista0.pdf
+++ b/Semestr 4/aisd/Lista 0/lista0.pdf
diff --git a/Semestr 4/aisd/Wykłady/Notatka 1 - Preliminaria.pdf b/Semestr 4/aisd/Wykłady/Notatka 1 - Preliminaria.pdf
new file mode 100644
index 0000000..dc4ee1c
--- /dev/null
+++ b/Semestr 4/aisd/Wykłady/Notatka 1 - Preliminaria.pdf
diff --git a/Semestr 4/aisd/Wykłady/Notatka 2 - Kopiec.pdf b/Semestr 4/aisd/Wykłady/Notatka 2 - Kopiec.pdf
new file mode 100644
index 0000000..c8e76a7
--- /dev/null
+++ b/Semestr 4/aisd/Wykłady/Notatka 2 - Kopiec.pdf
diff --git a/Semestr 4/aisd/rozw.cpp b/Semestr 4/aisd/rozw.cpp
deleted file mode 100644
index 8093708..0000000
--- a/Semestr 4/aisd/rozw.cpp
+++ /dev/null
@@ -1,10 +0,0 @@
-#include<iostream>
-using namespace std;
-
-int main() {
-  int a, b;
-  cin >> a >> b;
-  if (b < a) swap(a,b);
-  for (int i = a; i <= b; i++) 
-    cout << i << "\n";
-}
\ No newline at end of file