# Toan Roi Rac
## 1. Lý thuyết
1. **Chương 5**: Trình bày và đánh giá độ phức tạp của thuật toán chia đôi để tính $a^n$ với $a\in R, n \in N$.
<pre>
x = 1
i = n
while i > 0:
if i % 2 == 1:
x = x * a
a = a * a
i = i // 2
</pre>
**Độ phức tạp:**
Cần chứng minh: $f(n) \leq 1 + log_2n$
1. $f(1) = 1 \leq 1 + log_21$ : Đúng
2. Giả sử $f(k) \leq 1 + log_2k$ đúng $\forall k=\overline{1,n}$. Xét thuật toán với n + 1.
Sau lần đầu tiên, $i = \left\lfloor \frac{n+1}{2} \right\rfloor$ nên $f(n+1) = 1 + f(\left\lfloor \frac{n+1}{2} \right\rfloor)$.
Mặt khác $1 \leq \frac{n+1}{2} \leq n$ nên $1 \leq \left\lfloor \frac{n+1}{2} \right\rfloor \leq n$
Suy ra, $f(\left\lfloor \frac{n+1}{2} \right\rfloor) \leq 1 + log_2\left\lfloor \frac{n+1}{2} \right\rfloor \leq 1 + log_2\frac{n+1}{2} =log_2(n+1)$
Do đó, $f(n+1) \leq 1 + log_2(n+1) \in log_2(n)$. **Thuật toán có độ phức tạp Loga**

2. **Chương 7**: Phát biểu, chứng minh công thức hàm **Euler phi** tìm các số nguyên dương nhỏ hơn $n$ và nguyên tố cùng nhau với $n$. Tìm $\Phi(1984)$
1. Phát biểu
Cho số nguyên dương $n \geq 2$. Theo **định lý cơ bản của số học**, $n$ có phân tích $n = p_1^{e_1}p_2^{e_2}...p_k^{e_k}$ trong đó $p_i$ là số nguyên tố, $e_i \in \mathbb{Z^+}, 1 \leq i \leq k$. Khi đó
$\Phi(n) = n \displaystyle \prod_{i=1}^k(1-\frac{1}{p_i})$
2. Chứng minh
Với phân tích nguyên tố này của $n$, một số nguyên dương $m$ nguyên tố cùng nhau với $n$ nếu $p_i$ không là ước của m, $1 \leq i \leq k$. Trong các số m từ $1$ tới $n$ xét điều kiện
**$c_i: p_i$ là ước của m** và cần tính
$N(\overline{c_1} \overline{c_2} ... \overline{c_k})= N_0 - N_1+N_2-N_3+....+(-1)^k N_k$ trong
* $N_0=n$
* $N_1=\displaystyle \sum_{1 \leq i\leq k} N(c_i) = \displaystyle \sum_{1 \leq i\leq k}\left\lfloor \frac{n}{p_i} \right\rfloor = \displaystyle \sum_{1 \leq i\leq k}\frac{n}{p_i}$
* $N(c_ic_j), 1 \leq i < j \leq k$, là số các số từ 1 tới n là bội của $p_i$ và $p_j$, tức là bội của $lcm(p_i,p_j)$. Mặt khác, $p_i, p_j$ là hai số nguyên tố cùng nhau, nên $lcm(p_i, p_j) = p_ip_j$. Suy ra $N(c_ic_j)=\left\lfloor \frac{n}{p_ip_j}\right\rfloor=\frac{n}{p_ip_j}$
$N_2 = \displaystyle \sum_{1 \leq i < j\leq k} N(c_ic_j)=\displaystyle \sum_{1 \leq i < j\leq k}\frac{n}{p_ip_j}$
* Tương tự
$N_3 = \displaystyle \sum_{1 \leq i < j < l\leq k} N(c_ic_jc_l) = \displaystyle \sum_{1 \leq i < j < l\leq k}\frac{n}{p_ip_jp_l},...$
$N_r = \displaystyle \sum_{1 \leq i_1 < i_2 < .... < i_r\leq k}N(c_{i_1}c_{i_2}...c_{i_r}) = \displaystyle \sum_{1 \leq i_1 < i_2 < .... < i_r\leq k}\frac{n}{p_{i_1}p_{i_2}...p_{i_r}},...$
$N_k = N(c_1,c_2,...c_k)=\frac{n}{p_1p_2...p_k}$
* Các số này có thừa số chung là n, nên
$N(\overline{c1}\overline{c2}...\overline{ck}) = n(1 - \displaystyle \sum_{1 \leq i\leq k}\frac{1}{p_i} + \displaystyle \sum_{1 \leq i < j\leq k}\frac{1}{p_ip_j} - \displaystyle \sum_{1 \leq i < j < l\leq k}\frac{1}{p_ip_jp_l} +...+ (-1)^{r-1}\displaystyle \sum_{1 \leq i_1 < i_2 < .... < i_r\leq k}\frac{1}{p_{i_1}p_{i_2}...p_{i_r}} +(-1)^k\frac{1}{p_1p_2...p_k})$
$=n\displaystyle\prod_{i=1}^{k}(1-\frac{1}{p_i})$
3. $\Phi(1984)$
$1984 = 2^6 \times 31$
$p_1 = 2, p_2 = 31$
$\Phi(1984) = 1984 \times \displaystyle \prod_{i=1}^{2}(1 - \frac{1}{p_i}) = 960$

3. **Chương 8**: Số Catalan là gì? Trình bày hệ thức đệ quy của số Catalan, và phương pháp hàm sinh để tìm công thức tường minh của nó
1. Số catalan: Số Catalan là số cách tính tích các ma trận $A = A_0 A_1 A_2 A_3...A_n$.
2. Hệ thức đệ quy
$c_n = \displaystyle \sum_{k=0}^{n-1}c_kc_{n-k-1}$
với $c_1 = 1, c_0 = 1$
3. Dùng hàm sinh
Xét $f(x) = \displaystyle \sum_{n=0}^{\infty}c_nx^n$, ta có$[f(x)]^2 = \displaystyle \sum_{n=0}^{\infty}a_nx^n$ với $a_n=\displaystyle \sum_{k=0}^{n}c_kc_{n-k}=c_{n+1}$. Suy ra
$[f(x)]^2 = \displaystyle \sum_{n=0}^{\infty}c_{n+1}x^n=\frac{1}{x}\displaystyle \sum_{n=0}^{\infty}c_{n+1}x^{n+1}=\frac{1}{x}\displaystyle \sum_{n=1}^{\infty}c_{n}x^{n}=\frac{1}{x}[f(x)-1]$
$\Rightarrow x[f(x)]^2 - f(x) + 1 = 0 \Rightarrow f(x)=\frac{1\pm \sqrt{1-4x}}{2x}$
Hệ số của $x^n$ trong $f(x)$ tương ứng với mỗi nghiệm, là:
$c_n = \pm \frac{1}{2} \bigg( \begin{array}{c} \frac{1}{2} \\ {n+1} \end{array} \bigg)(-4)^{n+1} = \pm \frac{1}{2} \frac{\frac{1}{2}(\frac{1}{2}-1)(\frac{1}{2}-2)...(\frac{1}{2}-n)}{(n+1)!}(-4)^{n+1}$
Ta chọn nghiệm $f(x)$ ứng với dấu - để hệ số này dương. Cuối cùng,
$c_n=\frac{1.2.3...(2n-1)(2n)}{2.4...(2n)}\frac{2^n}{n!(n+1)}=\frac{1}{n+1}\frac{(2n)!}{n!n!}=\frac{1}{n+1}\bigg(\begin{array}{c} 2n \\ n \end{array} \bigg)$
4. **Chương 9:** Phát biểu, chứng minh định lý **Léma** về đánh giá thuật toán **Euclid** tìm ước chung lớn nhất của hai số nguyên dương. Trình bày thuật toán **Euclid** tìm gcd(2023, 1984)
1. Phát biểu
(Định lý). Cho $a,b \in \mathbb{Z^+}, a,b \geq 2$. Số phép chia dùng trong thuật toán Euclid để tìm ước chung lớn nhất của a và b không quá 5 lần số chữ số của b
3. Chứng minh
Đặt $r_0=a$ và $r_1=b$, ta có
$r_0 = r_1q_1 + r_2,(0 < r_2<r_1)$
$r_1 = r_2q_2 + r_3$ $,(0 < r_3<r_2)$
$r_2 = r_3q_3 + r_4$ $,(0 < r_4<r_3)$
$...................$
$r_{n-2} = r_{n-1}q_{n-1}+r_n$ $,(0 < r_n < n_{n-1})$
$r_{n-1}=r_nq_n$
Khi đó, $gcd(a,b)=r_n$, là phần dư khác 0 cuối cùng, và thuật toán thực hiện n phép chia.
Ta thấy, $q_i\geq1, \forall i=\overline{1,n}$. Riêng $q_n \geq 2$, vì $r_{n-1}=r_nq_n$ mà $0<r_n<r_{n-1}$. Như vậy
$r_n>0\Rightarrow r_n \geq 1 = F_2$
$r_{n-1}=r_nq_n\geq 1\cdot2=2=F_3$
$r_{n-2}=r_{n-1}q_{n-1}+r_n\geq F_3\cdot1+F_2 = F_4$
$r_{n-3}=r_{n-2}q_{n-2}+r_{n-1}\geq F_4\cdot1+F_3 = F_5$
$..........................$
$r_2=r_3q_3+r_4\geq F_{n-1}\cdot1+F_{n-2}=F_n$
$b=r_1=r_2q_2+r_3\geq F_n\cdot1+F_{n-1}=F_{n+1}$
Dẫn đến
$b \geq F_{n+1}>\alpha^{(n+1)-2}=\alpha^{n-1}$
$\Rightarrow n-1 < log_\alpha b = log_\alpha10\cdot log_{10}b=4.784971log_{10}b<5log_{10}b$
Nếu $b$ có $k$ chữ số, thì $10^{k-1}\leq b < 10^k$, nên $log_{10}b<k$. Do đó $n-1<5k$, hay $n\leq 5k$, tức là số phép chia trong thuật toán Euclid không quá 5 lần số chữ số của b.
7. gcd(2023, 1984)
* $2023 = 1984 \cdot1 + 39$
* $1984 = 39 \cdot50 + 34$
* $39 = 34 \cdot1 + 5$
* $34 = 5 \cdot6 + 4$
* $5 = 4 \cdot1 + 1$
* $4 = 1\cdot4 + 0$
* $\Rightarrow gcd(2023, 1984) = 1$
6. **Chương 9:** Trình bày và đánh giá độ phức tạp của thuật toán **sắp xếp trộn**
1. Trình bày
* Nếu dãy chỉ có 1 số, ta không cần làm gì cả. Ngược lại, chuyển xuống thực hiện bước (2)
* Chia đôi dãy được hai dãy con $a_1, a_2, ..., a_k$ và $a_{k+1}, ..., a_n$ cỡ $\frac{n}{2}$. Sắp xếp hai dãy này, được hai dãy tăng
* Trộn hai dãy tăng cho thành một dãy tăng.
2. Đánh giá độ phức tạp
Gọi $f(n)$ là số chu trình tối giản của thuật toán với dãy cỡ n. Ta có
$f(n)=2f(\frac{n}{2})+n$
Xét n = $2^k \Leftrightarrow k = log_2n$, và $a_k=f(n)=f(2^k)$ thì
$a_k=2f(x^{k-1})+2^k=2a_{k-1}+2^k$
trong đó $a_0=f(1)=0$
Giaỉ hệ thức đệ quy này ta được $a_k=2^kk$, tức là $f(n)=nlog_2n$. Thuật toán có độ phức tạp $nlog_2n$.
## 2. Bài tập trình bày lời giải
1.
<pre>
for i = 1 to 10 do
for j = 1 to i do
for k = 1 to j - 1 do:
print i, j, k
</pre>
* C1:
i = 1:
* j = 1, không in

i = 2:
* j = 1, không in
* j = 2, k = 1: in 1 lần

i = 3:
* j = 1, không in
* j = 2, k = 1: in 1 lần
* j = 3, k = 1, 2: in 2 lần

...
i = 10:
* j = 1, không in
* j = 2, k = 1: in 1 lần
* j = 3, k = 1, 2: in 2 lần
* ...
* j = 10, k = 1, 2, 3, ..., 9: in 9 lần

**Tổng số lần in:** $0 + (0 + 1) + (0 + 1 + 2) + ... + (0 + 1 + 2 + ... + 9)$
$= \displaystyle \sum_{i=0}^{9} (\displaystyle \sum_{j = 0}^{i}j)$
* C2
$\begin{cases}
1 \leq i \leq 10 \\
1 \leq j \leq i \\
1 \leq k \leq j-1
\end{cases}$
2. Bằng quy nạp, chứng minh $\displaystyle \sum_{i=1}^n\frac{1}{i(i+1)} = \frac{n}{n+1}$
Xét khẳng định mở $S(n) = \displaystyle \sum_{i=1}^n\frac{1}{i(i+1)} = \frac{n}{n+1}$
$S(1): \frac{1}{2}=\frac{1}{2}$ Đúng
Giả sử với n cho trước, S(n) đúng. Ta chứng minh S(n+1) đúng. Thật vậy
$\displaystyle \sum_{i=1}^{n+1}\frac{1}{i(i+1)} = \displaystyle \sum_{i=1}^n\frac{1}{i(i+1)} + \frac{1}{(n+1)(n+2)}$
$=\frac{n}{n+1} + \frac{1}{(n+1)(n+2)}$ vì $S(n)$ đúng
$= \frac{n^2+2n+1}{(n+1)(n+2)}=\frac{(n+1)^2}{(n+1)(n+2)}=\frac{n+1}{n+2}$
Theo nguyên lý quy nạp, $S(n)$ đúng $\forall n \in \mathbb{Z^+}$
3. **Chương 6:** Cho quan hệ $\mathbb{R}$ trên tập $A$ cỡ $n=4,5,6$. Tìm bao đóng bắc cầu $\mathbb{R^*}$ và $\mathbb{R}$ bằng thuật toán:
* nhân ma trận: ghi ra các ma trận $M, M^2,...,M^n$ và $M^*$
<pre>
import numpy as np
M = np.array([[0, 1, 0, 1],
[0, 1, 0, 0],
[1, 0, 0, 0],
[0, 0, 1, 0]], dtype=bool)
n = len(M)
A = M.copy()
L = M.copy()
for k in range(2, n+1):
L = M.dot(L)
A += L
print(k, np.array(L, dtype=int))
print("R* ", np.array(A, dtype=int))
</pre>
* Warshall: ghi ra các ma trận $W_0,W_1,W_2,...,W_{n-1}$và$W^*$
<pre>
import numpy as np
W = np.array([[0, 1, 0, 1],
[0, 1, 0, 0],
[1, 0, 0, 0],
[0, 0, 1, 0]], dtype=bool)
n = len(W)
for k in range(n):
for i in range(n):
for j in range(n):
W[i, j] += W[i, k] * W[k, j]
print(k+1, np.array(W, dtype=int))
</pre>
4. **Chương 9** Cho hàm $a(n)$ định nghĩa bằng đệ quy
<pre>
def a(n):
if n == 0:
return 1
return 2*a(n-1) + 1
</pre>
* $a(3)$
$a(3) =15$
* Đặt $f(n)$ là số phép toán số học và phép so sánh dùng để tính $a(n)$. Lập hệ thức đệ quy cho dãy $f(n)$ và giải $f(n)$
* $f(0)$: số phép toán số học và so sánh để tính $a(0)$
$f(0)=1$
* Để tính $a_n$ cần 1 phép so sánh với 0, cần tính $a_{n-1}$, kiểm tra sau đó nhân 2 và cộng 1 (2 phép toán số học) để tính $a{n-1}$ cần $f{n-1}$ phép tính.
* Như vậy $f(n)=f(n-1)+3$ với $f(0) = 1$
* Giải $f(n)$
* $f(n) = f(n-1)+3$ với $f(0) =1$ là cấp số cộng ứng với $d = 3 , c = 1$, có nghiệm $f(n)=3\cdot n+1$
## Các thuật toán, công thức
1. Giải hệ thức đệ quy
<pre>
rsolve(<Phương trình>, <biểu thức cần giải>, <Số liệu cho trước>)

from sympy import *
n = symbols('n')
a = symbols('a', cls=Function)
print(rsolve(a(n) - a(n-1) - 3, a(n), {a(0) : 3}))
</pre>
2. Chuyển số hệ b sang hệ 10
<pre>
int(<Số cần chuyển dạng string>, <hệ>)
int('10101', 2)
</pre>
3. Phân tích thừa số nguyên tố
<pre>
from sympy import *
factorint(1900)
</pre>
4. Số $a_1^{e_1}\cdot a_2^{e_2}\cdot a_n^{e_n}$ có $(e_1+1)\cdot(e_2+1)\cdot(e_3+1)$ ước
5. Số **hàm** từ tập cỡ **m** vào tập cỡ **n** (hay số cách xếp **m vật** vào **n hộp**): $n^m$
6. Số **đơn ánh** từ tập cỡ **m** vào tập cỡ **n** (hay số cách xếp **m vật** vào **n hộp** sao cho **mỗi hộp không quá một vật**): $P(n,m)$
7. Có bao nhiêu **toàn ánh** từ tập cỡ **n** vào tập cỡ **m** (hay số cách xếp **m vật** vào **n hộp** sao cho **không hộp nào trống**)
$\displaystyle \sum_{k=0}^n(-1)^k\cdot C(n, n-k)\cdot (n-k)^m$
8. Số Stirling S(m, n) (hay số cách chia **m vật** thành **n phần** khác rỗng, **không quan tâm thứ tự các phần**): $S(m, n) = S(m-1, n-1) + n \cdot S(m-1, n)$ với khi $m=n$, $S(m,n)=1$ và khi $n=1$ , $S(m,n)=1$
9. Số **quan hệ** từ tập cỡ **m** vào tập cỡ **n**: $2^{m\cdot n}$
10. Xếp không hộp nào cùng số
$n!\cdot [1-\frac{1}{1!} + \frac{1}{2!}-\frac{1}{3!}+...+\frac{(-1)^n}{n!}]$
11. Số cách $x_1+x_2+...+x_n = r$: $C(n+r-1, r)$