[Toán rời rạc/Chương III] Thuật toán và số nguyên

 

CHƯƠNG III: THUẬT TOÁN VÀ SỐ NGUYÊN

I, Thuật toán (Algorithms)

- Định nghĩa: Là 1 tập hợp hữu hạn các hướng dẫn chính xác để thực hiện 1 phép tính hoặc giải quyết vấn đề

* Các thuộc tính của thuật toán

+ Input: Thuật toán có giá trị đầu vào từ tập hợp được chỉ định

+ Output: Từ mỗi giá trị đầu vào, thuật toán tạo ra các giá trị đầu ra

+ Definiteness (Tính xác định): Các bước của thuật toán phải được xác định chính xác

+ Correctness (Tính chính xác): 1 thuật toán phải tạo ra các giá trị đầu ra chính xác cho mỗi giá trị đầu vào

+ Finiteness (Tính hữu hạn): 1 thuật toán phải tạo ra đầu ra mong muốn sau 1 số lượng hữu hạn các bước

+ Effectiveness (Tính hiệu quả): Phải có khả năng thực hiện từng bước của 1 thuật toán chính xác và trong 1 khoảng thời gian hữu hạn

+ Generality( Tính tổng quát): Thuật toán phải áp dụng được cho tất cả các vấn đề có dạng mong muốn, không chỉ 1 tập hợp các giá trị đầu vào cụ thể

II, Hàm tăng trưởng (The growth of Functions)

- Các hàm tăng dần theo thứ tự là: 

                    1, logn, \( \sqrt[3]{n}\), \( \sqrt[2]{n}\), n, nlogn, \(n^2\), \(n^3\), \(2^n\), \(3^n\), n!

* Big-O

- Định nghĩa: Hàm f*(x) được gọi là big-O của g(x), viết f(x) là O(g(x)), nếu tồn tại 1 hằng số C và k sao cho 

                                            |f(x)| \(\leq\) C|g(x)|, với x > k

- Chú ý:

+ Khi f(x) là O(g(x)) thì f(x) tăng (trưởng) chậm hơn 1 số bội số lần cố định của g(x) khi x \(\rightarrow\) \(\infty\)

+ f(x) là O(g(x)) đôi khi được viết là f(x) = O(g(x)) nhưng dấu bằng trong này không thể hiện sự bằng nhau

+ Có thể viết f(x) \(\in\) O(g(x)) vì O(g(x)) là tập hợp các hàm có O(g(x)) (tức là O(g(x)) không là duy nhất của 1 hàm số nào)

Ví dụ: Chứng minh rằng f(x) = 2\(x^3\) + 3x là O(\(x^3\))

Với C = 3 và k = 2, ta có \(x^3\) > 3x khi x > 2 và

                    |2\(x^3\) + 3x| = 2\(x^3\) + 3x < 3\(x^3\) khi x > 2 (đpcm)

* Big-O cho hàm đa thức

- Với p(x) = \(a_nx^n + a_{n-1}x^{n-1} + \cdots + a_1n^1 + a_0 \) là O(\(x^n\))

* Tính chất của Big-O

- Cho f(x) = O(F(x)) và g(x) = O(G(x)) thì

+ cf(x) = O(F(x)) với c là hằng số 

+ f(x) + g(x) = O(max{|F(x), |G(x)|})

+ f(x).g(x) = O(F(x).G(x))

Ví dụ: Cho f(x) = x và g(x) = 1 thì f(x) + g(x) = O(max{x,1}) = O(x) (cái nào tăng trưởng nhanh hơn thì Big-O là cái đó)

* Định lý: Cho f, g, h là các hàm mà f(x) = O(g(x)) và g(x) = O(h(x)) thì f(x) = O(h(x))

* Big-theta

- Nếu Big-O là chặn trên và Big-omega là chặn dưới thì Big-theta là gộp của 2 cái này

                \(C_1\)|g(x)| \(\leq\) |f(x)| \(\leq\) \(C_2\)|g(x)|, với \(C_1, C_2 >0\) và x > k

- Kí hiệu: f(x) = \(\ominus\)(g(x))

Ví dụ: Chứng minh \(3x^2 + 8xlogx \text{là} \ominus(x^2)\)

Ta dễ dàng thấy \(3x^2 + 8xlogx = O(x^2)\) và \(x^2 = O(3x^2 + 8xlogx)\)

hay \(3x^2 \leq 3x^2 + 8xlogx \leq 11x^2\) \(\Rightarrow\) \(3x^2 + 8xlogx = \ominus(x^2)\)

III, Độ phức tạp của thuật toán (Complexity of Algorithms)

- Độ phức tạp không gian (Space complexity): Máy tính yêu cầu 1 lượng bộ nhớ để chạy thuật toán

- Độ phức tạp thời gian (Time complexity): Thời gian yêu cầu để chạy thuật toán. Độ phức tạp thời gian có thể được thể hiện theo số phép toán được thuật toán sử dụng. Các phép toán đó có thể là phép so sánh hoặc phép toán số học cơ bản

Ví dụ: Trong Linear Search (LS) để tìm được số cần tìm thì máy tính sẽ phải so sánh số mình nhập với số có sẵn trong dãy và tổng số phép so sánh được sử dụng là 2n + 2 = O(n)

IV, Số nguyên và phép chia (The integers và Division)

- Cho a, b là các số nguyên với a \(\neq\) 0. Ta nói b chia hết cho a nếu tồn tại 1 số nguyên m sao cho b = ma. Kí hiệu: a|b

* Định lý: Cho a, b, c là các số nguyên, thì:

+ Nếu a|b và a|c thì a|(b+c)

+ Nếu a|b thì a|bc với mọi c

+ Nếu a|b và b|c thì a|c

* Phép chia lấy phần nguyên (Division)

- Cho a là số nguyên và d là 1 số nguyên dương. Tồn tại cặp số q và r khác biệt với 0 \(\leq\) r < d sao cho a = q.d + r

- Trong phép chia lấy phần nguyên, a gọi là số bị chia, d là số chia, q là thương và r là số dư. Ta viết: q = a div d, r = a mod d

Ví dụ: 23 div 7 = q = 3 và r = 2

* Phép chia lấy phần dư (Modular)

- Cho a, b là các số nguyên và m là 1 số nguyên dương. Ta nói a đồng dư (congruent) b modulo (mod) m là nếu nó có cùng số dư khi chia cho m. Kí hiệu: a \(\equiv\) b mod m

* Tính chất: 

+ a \(\equiv\) b mod m \(\Leftrightarrow\) a - b \(\equiv\) 0 mod m \(\Leftrightarrow\) a = b + km với k là số nguyên

+ Nếu a \(\equiv\) b mod m và c \(\equiv\) d mod m thì a + c \(\equiv\) b + d mod m và ac \(\equiv\) bd mod m 

V, Số nguyên tố và Ước chung lớn nhất (Primes and GCD)

- 1 số nguyên p lớn hơn 1 gọi là số nguyên tố nếu nó chỉ chia hết cho 1 và chính nó

- 1 số nguyên lớn hơn 1 nhưng không phải là số nguyên tố thì gọi là hợp số

* Định lý: 1 số nguyên tố bất kì có thể viết dưới dạng tích của các lũy thừa của các số nguyên tố khác nhau

* Lưu ý: Có vô hạn số nguyên tố

- Cho a và b là 2 số nguyên khác 0. Số nguyên lớn nhất d mà cả 2 số a và b đều chia hết cho d gọi là ước chung lớn nhất (greatest common divisor), kí hiệu là gcd(a,b)

- Tương tự, số nhỏ nhất d mà chia hết cho cả a và b thì gọi là bội chung nhỏ nhất (least common multiple), kí hiệu là lcm(a,b)

* Cách tìm gcd và lcm

- Để tìm gcd và lcm của a và b, ta viết a, b dưới dạng tích lũy thừa các số nguyên tố khác nhau

 

Sau đó, tính gcd và lcm: 

* Lưu ý: gcd là lấy phần số mũ chung nhỏ nhất còn lcm lấy cả chung cả riêng lớn nhất

* Tương đối nguyên tố của từng cặp (Pairwise relatively prime)

- Định lý: Cho 2 số a và b dương thì a.b = gcd(a,b).lcm(a,b)

- Tính chất: + 2 số dương a, b gọi là tương đối nguyên tố (relatively prime) nếu gcd(a,b) = 1

                     + Tập hợp số nguyên gọi là tương đối nguyên tố từng cặp (pairwise relatively prime) nếu lấy 2 số nguyên bất kì đều có relatively prime.

Ví dụ: {13, 24, 49} là pairwise relatively prime

           {14, 23, 35, 61} không là pairwise relatively prime vì gcd(14,35) = 7 

P/s: Bài tập và tài liệu nghiên cứu thêm (nếu cần) được tổng hợp ở link dưới sau:

https://drive.google.com/drive/folders/1F0E9eOcKKAZTDe8jYYkeX_9FaL2qp9y4?usp=sharing

Video bổ trợ bài học này