From 3ceb114ee9fb91f3bac1a49740f9148fa0620676 Mon Sep 17 00:00:00 2001 From: Franciszek Malinka Date: Tue, 2 Mar 2021 13:20:08 +0100 Subject: AiSD l0 --- Semestr 4/aisd/Lista 0/L0Z8.md | 51 +++++++++++++++++++++ Semestr 4/aisd/Lista 0/Rozw L0.pdf | Bin 0 -> 1964392 bytes Semestr 4/aisd/Lista 0/lista0.pdf | Bin 0 -> 83161 bytes .../Wyk\305\202ady/Notatka 1 - Preliminaria.pdf" | Bin 0 -> 211162 bytes .../aisd/Wyk\305\202ady/Notatka 2 - Kopiec.pdf" | Bin 0 -> 150213 bytes Semestr 4/aisd/lista0.pdf | Bin 83161 -> 0 bytes Semestr 4/aisd/rozw.cpp | 10 ---- 7 files changed, 51 insertions(+), 10 deletions(-) create mode 100644 Semestr 4/aisd/Lista 0/L0Z8.md create mode 100644 Semestr 4/aisd/Lista 0/Rozw L0.pdf create mode 100644 Semestr 4/aisd/Lista 0/lista0.pdf create mode 100644 "Semestr 4/aisd/Wyk\305\202ady/Notatka 1 - Preliminaria.pdf" create mode 100644 "Semestr 4/aisd/Wyk\305\202ady/Notatka 2 - Kopiec.pdf" delete mode 100644 Semestr 4/aisd/lista0.pdf delete mode 100644 Semestr 4/aisd/rozw.cpp 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 Binary files /dev/null and b/Semestr 4/aisd/Lista 0/Rozw L0.pdf differ diff --git a/Semestr 4/aisd/Lista 0/lista0.pdf b/Semestr 4/aisd/Lista 0/lista0.pdf new file mode 100644 index 0000000..31b9daa Binary files /dev/null and b/Semestr 4/aisd/Lista 0/lista0.pdf differ diff --git "a/Semestr 4/aisd/Wyk\305\202ady/Notatka 1 - Preliminaria.pdf" "b/Semestr 4/aisd/Wyk\305\202ady/Notatka 1 - Preliminaria.pdf" new file mode 100644 index 0000000..dc4ee1c Binary files /dev/null and "b/Semestr 4/aisd/Wyk\305\202ady/Notatka 1 - Preliminaria.pdf" differ diff --git "a/Semestr 4/aisd/Wyk\305\202ady/Notatka 2 - Kopiec.pdf" "b/Semestr 4/aisd/Wyk\305\202ady/Notatka 2 - Kopiec.pdf" new file mode 100644 index 0000000..c8e76a7 Binary files /dev/null and "b/Semestr 4/aisd/Wyk\305\202ady/Notatka 2 - Kopiec.pdf" differ diff --git a/Semestr 4/aisd/lista0.pdf b/Semestr 4/aisd/lista0.pdf deleted file mode 100644 index 31b9daa..0000000 Binary files a/Semestr 4/aisd/lista0.pdf and /dev/null differ 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 -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 -- cgit v1.2.3