CHƯƠNG I: 1. Tìm một số nguyên n nhỏ nhất sao cho f(x) là O(xn) đối với các hàm f(x) sau: a) f(x) = 2x3 + x2log x. Chứng minh rằng a) x2 + 4x + 7 là O(x3), nhưng x3 không là O(x2 +4x + 17). Cho một đánh giá big-O đối với các hàm cho dưới đây.
Đối với hàm g(x) trong đánh giá f(x) là O(g(x)), hãy chọn hàm đơn giản có bậc thấp nhất. Cho Hn là số điều hoà thứ n: 1 1 1 Hn = 1 + + +. + 2 3 n Chứng minh rằng Hn là O(logn). Lập một thuật toán tính tổng tất cả các số nguyên trong một bảng.
Lập thuật toán tính xn với x là một số thực và n là một số nguyên. Mô tả thuật toán chèn một số nguyên x vào vị trí thích hợp trong dãy các số nguyên a1, a2, ., an xếp theo thứ tự tăng dần. Tìm thuật toán xác định vị trí gặp đầu tiên của phần tử lớn nhất trong bảng liệt kê các số nguyên, trong đó các số này không nhất thiết phải khác nhau. Tìm thuật toán xác định vị trí gặp cuối cùng của phần tử nhỏ nhất trong bảng liệt kê các số nguyên, trong đó các số này không nhất thiết phải khác nhau.
Mô tả thuật toán đếm số các số 1 trong một xâu bit bằng cách kiểm tra mỗi bit của xâu để xác định nó có là bit 1 hay không. Thuật toán tìm kiếm tam phân. Xác định vị trí của một phần tử trong một bảng liệt kê các số nguyên theo thứ tự tăng dần bằng cách tách liên tiếp bảng liệt kê đó thành ba bảng liệt kê con có kích thước bằng nhau (hoặc gần bằng nhau nhất có thể được) và giới hạn việc tìm kiếm trong một bảng liệt kê con thích hợp. Hãy chỉ rõ các bước của thuật toán đó.
Lập thuật toán tìm trong một dãy các số nguyên số hạng đầu tiên bằng một số hạng nào đó đứng trước nó trong dãy. Lập thuật toán tìm trong một dãy các số nguyên tất cả các số hạng lớn hơn tổng tất cả các số hạng đứng trước nó trong dãy. Cho đánh giá big-O đối với số các phép so sánh được dùng bởi thuật toán trong Bài tập 10. Đánh giá độ phức tạp của thuật toán tìm kiếm tam phân được cho trong Bài tập 11.
Đánh giá độ phức tạp của thuật toán trong Bài tập 12. Mô tả thuật toán tính hiệu của hai khai triển nhị phân. Lập một thuật toán để xác định a > b, a = b hay a < b đối với hai số nguyên a và b ở dạng khai triển nhị phân. Đánh giá độ phức tạp của thuật toán tìm khai triển theo cơ số b của số nguyên n qua số các phép chia được dùng.
Hãy cho thuật toán đệ quy tìm tổng n số nguyên dương lẻ đầu tiên. Hãy cho thuật toán đệ quy tìm số cực đại của tập hữu hạn các số nguyên. Mô tả thuật toán đệ quy tìm xn mod m với n, x, m là các số nguyên dương. Hãy nghĩ ra thuật toán đệ quy tính a 2 trong đó a là một số thực và n là một số nguyên dương.
Hãy nghĩ ra thuật toán đệ quy tìm số hạng thứ n của dãy được xác định như sau: a0=1, a1 = 2 và an = an-1 an-2 với n = 2, 3, 4,. Thuật toán đệ quy hay thuật toán lặp tìm số hạng thứ n của dãy trong Bài tập 24 là có hiệu quả hơn? CHƯƠNG II BÀI TOÁN ĐẾM Lý thuyết tổ hợp là một phần quan trọng của toán học rời rạc chuyên nghiên cứu sự phân bố các phần tử vào các tập hợp. Thông thường các phần tử này là hữu hạn và việc phân bố chúng phải thoả mãn những điều kiện nhất định nào đó, tùy theo yêu cầu của bài toán cần nghiên cứu. Mỗi cách phân bố như vậy gọi là một cấu hình tổ hợp.
Chủ đề này đã được nghiên cứu từ thế kỹ 17, khi những câu hỏi về tổ hợp được nêu ra trong những công trình nghiên cứu các trò chơi may rủi. Liệt kê, đếm các đối tượng có những tính chất nào đó là một phần quan trọng của lý thuyết tổ hợp. Chúng ta cần phải đếm các đối tượng để giải nhiều bài toán khác nhau. Hơn nữa các kỹ thuật đếm được dùng rất nhiều khi tính xác suất của các biến cố.
CƠ SỞ CỦA PHÉP ĐẾM. Những nguyên lý đếm cơ bản: 1) Quy tắc cộng: Giả sử có k công việc T1, T2,. Các việc này có thể làm tương ứng bằng n1, n2, ., nk cách và giả sử không có hai việc nào có thể làm đồng thời. Khi đó số cách làm một trong k việc đó là n1+n2+.
Thí dụ 1: 1) Một sinh viên có thể chọn bài thực hành máy tính từ một trong ba danh sách tương ứng có 23, 15 và 19 bài. Vì vậy, theo quy tắc cộng có 23 + 15 + 19 = 57 cách chọn bài thực hành. 2) Giá trị của biến m bằng bao nhiêu sau khi đoạn chương trình sau được thực hiện? m := 0 for i1 := 1 to n1 m := m+1 for i2 :=1 to n2 m := m+1. for ik := 1 to nk m := m+1 Giá trị khởi tạo của m bằng 0.
Khối lệnh này gồm k vòng lặp khác nhau. Sau mỗi bước lặp của từng vòng lặp giá trị của k được tăng lên một đơn vị. Gọi Ti là việc thi hành vòng lặp thứ i. Có thể làm Ti bằng ni cách vì vòng lặp thứ i có ni bước lặp.
Do các vòng lặp không thể thực hiện đồng thời nên theo quy tắc cộng, giá trị cuối cùng của m bằng số cách thực hiện một trong số các nhiệm vụ Ti, tức là m = n1+n2+. Quy tắc cộng có thể phát biểu dưới dạng của ngôn ngữ tập hợp như sau: Nếu A1, A2, ., Ak là các tập hợp đôi một rời nhau, khi đó số phần tử của hợp các tập hợp này bằng tổng số các phần tử của các tập thành phần. Giả sử Ti là việc chọn một phần tử từ tập Ai với i=1,2,. Có |Ai| cách làm Ti và không có hai việc nào có thể được làm cùng một lúc.
Số cách chọn một phần tử của hợp các tập hợp này, một mặt bằng số phần tử của nó, mặt khác theo quy tắc cộng nó bằng |A1|+|A2|+. 2) Quy tắc nhân: Giả sử một nhiệm vụ nào đó được tách ra thành k việc T1, T2,. Nếu việc Ti có thể làm bằng ni cách sau khi các việc T1, T2,. Ti-1 đã được làm, khi đó có n1.nk cách thi hành nhiệm vụ đã cho.
Thí dụ 2: 1) Người ta có thể ghi nhãn cho những chiếc ghế trong một giảng đường bằng một chữ cái và một số nguyên dương không vượt quá 100. Bằng cách như vậy, nhiều nhất có bao nhiêu chiếc ghế có thể được ghi nhãn khác nhau? Thủ tục ghi nhãn cho một chiếc ghế gồm hai việc, gán một trong 26 chữ cái và sau đó gán một trong 100 số nguyên dương. Quy tắc nhân chỉ ra rằng có 26.100=2600 cách khác nhau để gán nhãn cho một chiếc ghế. Như vậy nhiều nhất ta có thể gán nhãn cho 2600 chiếc ghế.
2) Có bao nhiêu xâu nhị phân có độ dài n. Mỗi một trong n bit của xâu nhị phân có thể chọn bằng hai cách vì mỗi bit hoặc bằng 0 hoặc bằng 1. Bởi vậy theo quy tắc nhân có tổng cộng 2n xâu nhị phân khác nhau có độ dài bằng n. 3) Có thể tạo được bao nhiêu ánh xạ từ tập A có m phần tử vào tập B có n phần tử? Theo định nghĩa, một ánh xạ xác định trên A có giá trị trên B là một phép tương ứng mỗi phần tử của A với một phần tử nào đó của B.
Rõ ràng sau khi đã chọn được ảnh của i - 1 phần tử đầu, để chọn ảnh của phần tử thứ i của A ta có n cách. Vì vậy theo quy tắc nhân, ta có n.n=nm ánh xạ xác định trên A nhận giá trị trên B. 4) Có bao nhiêu đơn ánh xác định trên tập A có m phần tử và nhận giá trị trên tập B có n phần tử? Nếu m > n thì với mọi ánh xạ, ít nhất có hai phần tử của A có cùng một ảnh, điều đó có nghĩa là không có đơn ánh từ A đến B. Bây giờ giả sử m n và gọi các phần tử của A là a1,a2,.
Rõ ràng có n cách chọn ảnh cho phần tử a1. Vì ánh xạ là đơn ánh nên ảnh của phần tử a2 phải khác ảnh của a1 nên chỉ có n - 1 cách chọn ảnh cho phần tử a2. Nói chung, để chọn ảnh của ak ta có n - k + 1 cách. Theo quy tắc nhân, ta có n! n(n 1)(n 2).(n m + 1) = ( n m)! đơn ánh từ tập A đến tập B.
5) Giá trị của biến k bằng bao nhiêu sau khi chương trình sau được thực hiện? m := 0 for i1 := 1 to n1 for i2 := 1 to n2. for ik := 1 to nk k := k+1 Giá trị khởi tạo của k bằng 0. Ta có k vòng lặp được lồng nhau. Gọi Ti là việc thi hành vòng lặp thứ i.
Khi đó số lần đi qua vòng lặp bằng số cách làm các việc T1, T2,. Số cách thực hiện việc Tj là nj (j=1, 2,., k), vì vòng lặp thứ j được duyệt với mỗi giá trị nguyên ij nằm giữa 1 và nj. Theo quy tắc nhân vòng lặp lồng nhau này được duyệt qua n1. Vì vậy giá trị cuối cùng của k là n1.
Nguyên lý nhân thường được phát biểu bằng ngôn ngữ tập hợp như sau., Ak là các tập hữu hạn, khi đó số phần tử của tích Descartes của các tập này bằng tích của số các phần tử của mọi tập thành phần. Ta biết rằng việc chọn một phần tử của tích Descartes A1 x A2 x.x Ak được tiến hành bằng cách chọn lần lượt một phần tử của A1, một phần tử của A2, ., một phần tử của Ak. Theo quy tắc nhân ta có: |A1 x A2 x. Nguyên lý bù trừ: Khi hai công việc có thể được làm đồng thời, ta không thể dùng quy tắc cộng để tính số cách thực hiện nhiệm vụ gồm cả hai việc.
Để tính đúng số cách thực hiện nhiệm vụ này ta cộng số cách làm mỗi một trong hai việc rồi trừ đi số cách làm đồng thời cả hai việc. Ta có thể phát biểu nguyên lý đếm này bằng ngôn ngữ tập hợp. Cho A1, A2 là hai tập hữu hạn, khi đó |A1 A2| = |A1| + |A2| |A1 A2|.