Độ phức tạp thuật toán

Tóm tắt lại:
- Big-O , Omega, Theta đều là $\lim n\to \infty$
- Big-O của $f(n)$ là $g(n)$ khi: $f(n)\le C. g(n)$
- Big-Omega của f(n) là g(n) khi: $f(n)\ge C. g(n)$
- Big-Theta của f(n) là g(n) khi: $C1 .g(n) \le f(n) \le C2. g(n)$
a) Với mọi số thực $x$ kí hiệu $\left \lfloor x \right \rfloor$ là số nguyên lớn nhất nhỏ hơn hoặc bằng $x$, chứng minh rằng $\left \lfloor n^2/3 \right \rfloor=\Theta (n^2),$ trong đó $n$ là số nguyên không âm.

Tìm hệ thức truy hồi và điều kiện đầu để tính số xâu nhị phân độ dài n bit luôn chứa hai bít 1 liên tiếp.

Tìm hệ thức truy hồi và điều kiện đầu để tính số xâu nhị phân độ dài n bit luôn chứa hai bít 1 liên tiếp.
Giải

Có bao nhiêu cách chia 20 viên kẹo cùng loại cho 3 người, trong đó mỗi người không được ít hơn 3 viên kẹo và không quá 10 viên kẹo.

Có bao nhiêu cách chia 20 viên kẹo cùng loại cho 3 người, trong đó mỗi người không được ít hơn 3 viên kẹo và không quá 10 viên kẹo.

Tìm số nghiệm nguyên $(x,y,z)$ của bất phương trình

Tìm số nghiệm nguyên $(x,y,z)$ của bất phương trình $x+y+z\le -2$ thỏa mãn $x\ge -20,y\ge -8,3\le z<10$

Bài tập ôn toán rời rạc

Logic mệnh đề
1) Kiểm tra suy luận sau
\[\begin{array}{l}
t \to u\\
r \to \left( {s \vee t} \right)\\
\left( {\neg p \vee q} \right) \to r\\
\underline {\neg \left( {s \vee u} \right)\,\,\,\,\,\,\,\,\,\,\,\,\,\,} \\
\therefore p

\end{array}\]

Bài toán cho 3 đứa trẻ

Bài toán cho 3 đứa trẻ: Ba đứa trẻ  thông minh đi chơi công viên. Khi cha chúng tới tìm chúng thì ông thấy trán của cả  ba đều bị  dính bùn.
Ông nói: “Trong các con, có ít nhất một đứa có trán bị  lấm bùn” và rồi hỏi: “Các con có tự  nhận ra liệu trán con bị dính bùn hay không?”.
 Cả 3 đứa đồng thanh: “Không phải con!”
Nghe vậy, ông liền nhắc lại câu hỏi lần thứ  hai: “Các con có tự  nhận ra liệu trán con bị dính bùn hay không?”
Lần này, 2 trong ba đứa trẻ  đồng thanh: “Là con!” trong khi đứa còn lại thì
nói: “không phải con!”
Nghe vậy, ông liền nhắc lại câu hỏi lần thứ  ba: “Các con có tự  nhận ra liệu trán con bị dính bùn hay không?”
Hỏi lần này, hai đứa trẻ  sẽ  trả  lời thế  nào biết rằng ba đứa trẻ  không thể  tự nhìn thấy bùn có lấm trên trán của mình hay không và cả  ba đều trả  lời cùng một lúc một cách hết sức trung thực.
Giải
Gọi P là mệnh đề "Đứa trẻ thứ nhất dính bùn"
Q: "Đứa trẻ thứ hai dính bùn"
R: "Đứa trẻ thứ ba dính bùn"

$P\vee Q$ hoặc $P\vee R$ hoặc $R\vee Q$ đúng.
3 đứa đều trả lời "không phải con!" vì mỗi đứa đều thấy bùn dính trên trán đứa khác. Vậy đứa thứ nhất biết $Q,R$ đúng nhưng không biết $P$ đúng còn đứa thứ 2 không biết $Q$ đúng mà chỉ biết $P,R$ đúng, đứa thứ 3 không biết $R$ đúng mà chỉ biết $P,Q$ đúng.
Sau khi ông bố nói “Các con có tự  nhận ra liệu trán con bị dính bùn hay không?” thì ba đứa đều biết rằng $P,Q,R$ đều đúng. Điều này bởi vì ở câu hỏi đầu tiên đứa bé thứ nhất biết $R,Q$ đúng nhưng không biết $P$ đúng, tương tự với đứa 2,3.
Như vậy sau khi nghe câu hỏi thứ 3 cả bả đều đồng thanh "Là con!"