Bài giảng môn học Phân tích và thiết kế thuật toán

Nội dung text: Bài giảng môn học Phân tích và thiết kế thuật toán

1. Bài Giảng Môn Học Phân Tích Và Thiết Kế Thuật Toán Biên tập bởi: Đại Học Phương Đông
2. Bài Giảng Môn Học Phân Tích Và Thiết Kế Thuật Toán Biên tập bởi: Đại Học Phương Đông Các tác giả: Đại Học Phương Đông Phiên bản trực tuyến:
3. MỤC LỤC 1. Độ phức tạp tính toán và tính hiệu quả của thuật toán 2. Mở đầu về thiết kế, đánh giá thuật toán và kiến thức bổ trợ 3. Phương pháp tham lam 4. Phương pháp “chia để trị” 5. Quy hoạch động 6. Thuật toán đồ thị cơ bản Tham gia đóng góp 1/129
4. Độ phức tạp tính toán và tính hiệu quả của thuật toán Sự cần thiết phải phân tích thuật toán Trong khi giải một bài toán chúng ta có thể có một số giải thuật khác nhau, vấn đề là cần phải đánh giá các giải thuật đó để lựa chọn một giải thuật tốt (nhất). Thông thường thì ta sẽ căn cứ vào các tiêu chuẩn sau: 1. Giải thuật đúng đắn. 2. Giải thuật đơn giản. 3. Giải thuật thực hiện nhanh. Với yêu cầu (1), để kiểm tra tính đúng đắn của giải thuật chúng ta có thể cài đặt giải thuật đó và cho thực hiện trên máy với một số bộ dữ liệu mẫu rồi lấy kết quả thu được so sánh với kết quả đã biết. Thực ra thì cách làm này không chắc chắn bởi vì có thể giải thuật đúng với tất cả các bộ dữ liệu chúng ta đã thử nhưng lại sai với một bộ dữ liệu nào đó. Vả lại cách làm này chỉ phát hiện ra giải thuật sai chứ chưa chứng minh được là nó đúng. Tính đúng đắn của giải thuật cần phải được chứng minh bằng toán học. Tất nhiên điều này không đơn giản và do vậy chúng ta sẽ không đề cập đến ở đây. Khi chúng ta viết một chương trình để sử dụng một vài lần thì y ê u cầu (2) là quan trọng nhất. Chúng ta cần một giải thuật dễ viết chương trình để nhanh chóng có được kết quả, thời gian thực hiện chương trình không được đề cao vì dù sao thì chương trình đó cũng chỉ sử dụng một vài lần mà thôi. Tuy nhiên khi một chương trình được sử dụng nhiều lần thì thì yêu cầu tiết kiệm thời gian thực hiện chương trình lại rất quan trọng đặc biệt đối với những chương trình mà khi thực hiện cần dữ liệu nhập lớn do đó yêu cầu (3) sẽ được xem xét một cách kĩ càng. Ta gọi nó là hiệu quả thời gian thực hiện của giải thuật. Thời gian thực hiện của chương trình Một phương pháp để xác định hiệu quả thời gian thực hiện của một giải thuật là lập trình nó và đo lường thời gian thực hiện của hoạt động trên một máy tính xác định 2/129
5. đối với tập hợp được chọn lọc các dữ liệu vào. Thời gian thực hiện không chỉ phụ thuộc vào giải thuật mà còn phụ thuộc vào tập các chỉ thị của máy tính, chất lượng của máy tính và kĩ xảo của người lập trình. Sự thi hành cũng có thể điều chỉnh để thực hiện tốt trên tập đặc biệt các dữ liệu vào được chọn. Ðể vượt qua các trở ngại này, các nhà khoa học máy tính đã chấp nhận tính phức tạp của thời gian được tiếp cận như một sự đo lường cơ bản sự thực thi của giải thuật. Thuật ngữ tính hiệu quả sẽ đề cập đến sự đo lường này và đặc biệt đối với sự phức tạp thời gian trong trường hợp xấu nhất. Thời gian thực hiện chương trình. Thời gian thực hiện m ộ t chương t r ì n h là một hàm của kích thước dữ liệu vào, ký hiệu T(n) trong đó n là kích thước (độ lớn) của dữ liệu vào. Chương trình tính tổng của n số có thời gian thực hiện là T(n) = cn trong đó c là một hằng số. Thời gian thực hiện chương trình là một hàm không âm, tức là T(n) ≥ 0 với mọi n ≥ 0. Ðơn vị đo thời gian thực hiện. Ðơn vị của T(n) không phải là đơn vị đo thời gian bình thường như giờ, phút giây mà thường được xác định bởi số các lệnh được thực hiện trong một máy tính lý tưởng. Khi ta nói thời gian thực hiện của một chương trình là T(n) = Cn thì có nghĩa là chương trình ấy cần Cn chỉ thị thực thi. Thời gian thực hiện trong trường hợp xấu nhất. Nói chung thì thời gian thực hiện chương trình không chỉ phụ thuộc vào kích thước mà còn phụ thuộc vào tính chất của dữ liệu vào. Nghĩa là dữ liệu vào có cùng kích thước nhưng thời gian thực hiện chương trình có thể khác nhau. Chẳng hạn chương trình sắp xếp dãy số nguyên tăng dần, khi ta cho vào dãy có thứ tự thì thời gian thực hiện khác với khi ta cho vào dãy chưa có thứ tự, hoặc khi ta cho vào một dãy đã có thứ tự tăng thì thời gian thực hiện cũng khác so với khi ta cho vào một dãy đã có thứ tự giảm. Vì vậy thường ta coi T(n) là thời gian thực hiện chương trình trong trường hợp xấu nhất trên dữ liệu vào có kích thước n, tức là: T(n) là thời gian lớn nhất để thực hiện chương trình đối với mọi dữ liệu vào có cùng kích thước n. 3/129
6. Tỷ suất tăng và Ðộ phức tạp của giải thuật Tỷ suất tăng Ta nói rằng hàm không âm T(n) có tỷ suất tăng (growth rate) f(n) nếu tồn tại các hằng số C và N0 sao cho T(n) ≤ Cf(n) với mọi n ≥ N0. Ta có thể c h ứ ng minh đư ợ c rằng “Cho m ộ t hàm không âm T(n) b ấ t kỳ, ta luôn tìm đư ợ c t ỷ s u ất tăng f (n) c ủa nó”. Giả sử T(0) = 1, T(1) = 4 và tổng quát T(n) = (n+1)2. Ðặt N0 = 1 và C = 4 thì với mọi n ≥1 chúng ta dễ dàng chứng minh được rằng T(n) = (n+1)2 ≤ 4n2 với mọi n ≥ 1, tức là tỷ suất tăng của T(n) là n2. Tỷ suất tăng của hàm T(n) = 3n3 + 2n2 là n3. Thực vậy, cho N0 = 0 và C = 5 ta dễ dàng chứng minh rằng với mọi n ≥ 0 thì 3n2 + 2n2 ≤ 5n3 Khái niệm độ phức tạp của giải thuật Giả sử ta có hai giải thuật P1 và P2 với thời gian thực hiện tương ứng là T1(n) = 100n2 (với tỷ suất tăng là n2) và T2(n) = 5n3 (với tỷ suất tăng là n3). Giải thuật nào sẽ thực hiện nhanh hơn? Câu trả lời phụ thuộc vào kích thước dữ liệu vào. Với n 20 thì ngươc lại do số mũ của 100n2 nhỏ hơn số mũ của 5n3 (2 20 vì khi n<20 thì thời gian thực hiện của cả P1 và P2 đều không lớn và sự khác biệt giữa T1 và T2 là không đáng kể. Như vậy một cách hợp lý là ta xét tỷ suất tăng của hàm thời gian thực hiện chương trình thay vì xét chính bản thân thời gian thực hiện. Cho mộ t hàm T(n), T(n) g ọ i là có độ phức t ạ p f(n) n ế u t ồn t ạ i các hằng C, N 0 sao cho T(n) ≤ Cf(n) v ớ i m ọ i n ≥ N 0 (tức là T(n) có t ỷ suấ t t ăng là f(n)) và kí h i ệu T(n) là O(f(n)) ( đọc là “ô c ủ a f(n)”) T(n)= (n+1)2 có tỷ suất tăng là n2 nên T(n)= (n+1)2 là O(n2) Chú ý: O(C.f(n))=O(f(n)) với C là hằng số. Ðặc biệt O(C) = O(1) Nói cách khác độ phức tạp tính toán của giải thuật là một hàm chặn trên của hàm thời gian. Vì hằng nhân tử C trong hàm chặn trên không có ý nghĩa nên ta có thể bỏ qua vì vậy hàm thể hiện độ phức tạp có các dạng thường gặp sau: log2n, n, nlog2n, n2, n3, 2n, n!, nn. Ba hàm cuối cùng ta gọi là dạng hàm mũ, các hàm khác gọi là hàm đa thức. Một giải thuật mà thời gian thực hiện có độ phức tạp là một hàm đa thức thì chấp nhận được 4/129
7. tức là có thể cài đặt để thực hiện, còn các giải thuật có độ phức tạp hàm mũ thì phải tìm cách cải tiến giải thuật. Vì ký hiệu log2n thường có mặt trong độ phức tạp nên trong khuôn khổ tài liệu này, ta sẽ dùng logn thay thế cho log2n với mục đích duy nhất là để cho gọn trong cách viết. Khi nói đến độ phức tạp của giải thuật là ta muốn nói đến hiệu quả của thời gian thực hiện của chương trình nên ta có thể xem việc xác định thời gian thực hiên của chương trình chính là xác định độ phức tạp của giải thuật. Cách tính Ðộ phức tạp Cách tính độ phức tạp của một giải thuật bất kỳ là một vấn đề không đơn giản. Tuy nhiên ta có thể tuân theo một số nguyên tắc sau: Qui tắc cộng Nếu T1(n) và T2(n) là thời gian thực hiện của hai đoạn chương trình P1 và P2; và T1(n)=O(f(n)), T2(n)=O(g(n)) thì thời gian thực hiện của đoạn hai chương trình đó nối tiếpnhaulà T(n)=O(max(f(n),g(n))) Lệnh gán x:=15 tốn một hằng thời gian hay O(1), Lệnh đọc dữ liệu READ(x) tốn một hằng thời gian hay O(1). Vậy thời gian thực hiện cả hai lệnh trên nối tiếp nhau là O(max(1,1))=O(1) Qui tắc nhân Nếu T1(n) và T2(n) là thời gian thực hiện của hai đoạn chương trình P1và P2 và T1(n) = O(f(n)), T2(n) = O(g(n)) thì thời gian thực hiện của đoạn hai đoạn chương trình đó lồngnhaulà T(n) = O(f(n).g(n)) Qui tắc tổng quát để phân tích một chương trình Thời gian thực hiện của mỗi lệnh gán, READ, WRITE là O(1). Thời gian thực hiện của một chuỗi tuần tự các lệnh được xác định bằng qui tắc cộng. Như vậy thời gian này là thời gian thi hành một lệnh nào đó lâu nhất trong chuỗi lệnh. Thời gian thực hiện cấu trúc IF là thời gian lớn nhất thực hiện lệnh sau THEN hoặc sau ELSE và thời gian kiểm tra điều kiện. Thường thời gian kiểm tra điều kiện là O(1). 5/129
8. Thời gian thực hiện vòng lặp là tổng (trên tất cả các lần lặp) thời gian thực hiện thân vòng lặp. Nếu thời gian thực hiện thân vòng lặp không đổi thì thời gian thực hiện vòng lặp là tích của số lần lặp với thời gian thực hiện thân vòng lặp. Tính thời gian thực hiện của thủ tục sắp xếp “nổi bọt” PROCEDURE Bubble(VAR a: ARRAY[1 n] OF integer); VAR i,j,temp: Integer; BEGIN {1} FOR i:=1 TO n-1 DO {2} FOR j:=n DOWNTO i+1 DO {3} IF a[j-1]>a[j]THEN BEGIN{hoán vị a[i], a[j]} {4} temp := a[j-1]; {5} a[j-1] := a[j]; {6} a[j] := temp; END; END; Về giải thuật sắp xếp nổi bọt, chúng ta sẽ bàn kĩ hơn trong chương 2. Ở đây, chúng ta chỉ quan tâm đến độ phức tạp của giải thuật. Ta thấy toàn bộ chương trình chỉ gồm một lệnh lặp {1}, lồng trong lệnh {1} là lệnh {2}, lồng trong lệnh {2} là lệnh {3} và lồng trong lệnh {3} là 3 lệnh nối tiếp nhau {4}, {5} và {6}. Chúng ta sẽ tiến hành tính độ phức tạp theo thứ tự từ trong ra. Trước hết, cả ba lệnh gán {4}, {5} và {6} đều tốn O(1) thời gian, việc so sánh a[j-1] > a[j] cũng tốn O(1) thời gian, do đó lệnh {3} tốn O(1) thời gian. Vòng lặp {2} thực hiện (n-i) lần, mỗi lần O(1) do đó vòng lặp {2} tốn O((n-i).1) = O(n- i).Vòng lặp {1} lặp có I chạy từ 1 đến n-1nên thời gian thực hiện của vòng lặp {1} và cũng là độ phức tạp của giải thuật là: Chú ý: Trong trường hợp vòng lặp không xác định được số lần lặp thì chúng ta phải lấy số lần lặp trong trường hợp xấu nhất. Tìm kiếm tuần tự. Hàm tìm kiếm Search nhận vào một mảng a có n số nguyên và một số nguyên x, hàm sẽ trả về giá trị logic TRUE nếu tồn tại một phần tử a[i] = x, ngược lại hàm trả về FALSE. 6/129
9. Giải thuật tìm kiếm tuần tự là lần lượt so sánh x với các phần tử của mảng a, bắt đầu từ a[1], nếu tồn tại a[i] = x thì dừng và trả về TRUE, ngược lại nếu tất cả các phần tử của a đều khác X thì trả về FALSE. FUNCTION Search(a:ARRAY[1 n] OF Integer;x:Integer):Boolean; VAR i:Integer; Found:Boolean; BEGIN {1} i:=1; {2} Found:=FALSE; {3} WHILE(i<=n)AND (not Found) DO {4} IF A[i]=X THEN Found:=TRUE ELSE i:=i+1; {5} Search:=Found; END; Ta thấy các lệnh {1}, {2}, {3} và {5} nối tiếp nhau, do đó độ phức tạp của hàm Search chính là độ phức tạp lớn nhất trong 4 lệnh này. Dễ dàng thấy rằng ba lệnh {1}, {2} và {5} đều có độ phức tạp O(1) do đó độ phức tạp của hàm Search chính là độ phức tạp của lệnh {3}. Lồng trong lệnh {3} là lệnh {4}. Lệnh {4} có độ phức tạp O(1). Trong trường hợp xấu nhất (tất cả các phần tử của mảng a đều khác x) thì vòng lặp {3} thực hiện n lần, vậy ta có T(n) = O(n). Ðộ phức tạp của chương trình có gọi chương trình con không đệ quy Nếu chúng ta có một chương trình với các chương trình con không đệ quy, để tính thời gian thực hiện của chương trình, trước hết chúng ta tính thời gian thực hiện của các chương trình con không gọi các chương trình con khác. Sau đó chúng ta tính thời gian thực hiện của các chương trình con chỉ gọi các chương trình con mà thời gian thực hiện của chúng đã được tính. Chúng ta tiếp tục quá trình đánh giá thời gian thực hiện của mỗi chương trình con sau khi thời gian thực hiện của tất cả các chương trình con mà nó gọi đã được đánh giá. Cuối cùng ta tính thời gian cho chương trình chính. Giả sử ta có một hệ thống các chương trình gọi nhau theo sơ đồ sau: Chương trình A gọi hai chương trình con là B và C, chương trình B gọi hai chương trình con là B1 và B2, chương trình B1 gọi hai chương trình con là B11 và B12. Ðể tính thời gian thực hiện của A, ta tính theo các bước sau: 7/129
10. 1. Tính thời gian thực hiện của C, B2, B11 và B12. Vì các chương trình con này không gọi chương trình con nào cả. 2. Tính thời gian thực hiện của B1. Vì B1 gọi B11 và B12 mà thời gian thực hiện của B11 và B12 đã được tính ở bước 1. 3. Tính thời gian thực hiện của B. Vì B gọi B1 và B2 mà thời gian thực hiện của B1 đã được tính ở bước 2 và thời gian thực hiện của B2 đã được tính ở bước 1. 4. Tính thời gian thực hiện của A. Vì A gọi B và C mà thời gian thực hiện của B đã được tính ở bước 3 và thời gian thực hiện của C đã được tính ở bước 1. Ta có thể viết lại chương trình sắp xếp bubble như sau: Trước hết chúng ta viết thủ tục Swap để thực hiện việc hoàn đổi hai phần tử cho nhau, sau đó trong thủ tục Bubble, khi cần ta sẽ gọi đến thủ tục Swap này. PROCEDURE Swap (VAR x, y: Integer); VAR temp: Integer; BEGIN END; temp := x; x := y; y := temp; PROCEDURE Bubble (VAR a: ARRAY[1 n] OF integer); VAR i,j :Integer; BEGIN {1} FOR i:=1 TO n-1 DO {2} FOR j:=n DOWNTO i+1 DO {3} IF a[j-1]>a[j] THEN Swap(a[j-1], a[j]); END; Trong cách viết trên, chương trình Bubble gọi chương trình con Swap, do đó để tính thời gian thực hiện của Bubble, trước hết ta cần tính thời gian thực hiện của Swap. Dễ thấy thời gian thực hiện của Swap là O(1) vì nó chỉ bao gồm 3 lệnh gán. Trong Bubble, lệnh {3} gọi Swap nên chỉ tốn O(1), lệnh {2} thực hiện n-i lần, mỗi lần tốn O(1) nên tốn O(n-i). Lệnh {1} thực hiện n-1 lần nên: Phân tích các chương trình Ðệ quy Với các chương trình có gọi các chương trình con đệ quy, ta không thể áp dụng cách tính như vừa trình bày trong mục 1.5.4 bởi vì một chương trình đệ quy sẽ gọi chính bản thân nó. Có thể thấy hình ảnh chương trình đệ quy A như sau: 8/129
11. Với phương pháp tính độ phức tạp đã trình bày trong mục 1.5.4 thì không thể thực hiện được. Bởi vì nếu theo phương pháp đó thì, để tính thời gian thực hiên của chương trình A, ta phải tính thời gian thực hiện của chương trình A và cái vòng luẩn quẩn ấy không thể kết thúc được. Với các chương trình đệ quy, trước hết ta cần thành lập các phương trình đệ quy, sau đó giải phương trình đệ quy, nghiệm của phương trình đệ quy sẽ là thời gian thực hiện của chương trình đệ quy. Thành lập phương trình đệ quy Phương trình đệ quy là một phương trình biểu diễn mối liên hệ giữa T(n) và T(k), trong đó T(n) là thời gian thực hiện chương trình với kích thước dữ liệu nhập là n, T(k) thời gian thực hiện chương trình với kích thước dữ liệu nhập là k, với k < n. Ðể thành lập được phương trình đệ quy, ta phải căn cứ vào chương trình đệ quy. Thông thường một chương trình đệ quy để giải bài toán kích thước n, phải có ít nhất một trường hợp dừng ứng với một n cụ thể và lời gọi đệ quy để giải bài toán kích thước k (k<n). Để thành lập phương trình đệ quy, ta gọi T(n) là thời gian để giải bài toán kích thước n, ta có T(k) là thời gian để giải bài toán kích thước k. Khi đệ quy dừng, ta phải xem xét khi đó chương trình làm gì và tốn hết bao nhiêu thời gian, chẳng hạn thời gian này là c(n). Khi đệ quy chưa dừng thì phải xét xem có bao nhiêu lời gọi đệ quy với kích thước k ta sẽ có bấy nhiêu T(k). Ngoài ra ta còn phải xem xét đến thời gian để phân chia bài toán và tổng hợp các lời giải, chẳng hạn thời gian này là d(n). Dạng tổng quát của một phương trình đệ quy sẽ là: 9/129
12. Trong đó C(n) là thời gian thực hiện chương trình ứng với trường hợp đệ quy dừng. F(T(k)) là một đa thức của các T(k). d(n) là thời gian để phân chia bài toán và tổng hợp các kết quả. Xét hàm tính giai thừa viết bằng giải thuật đệ quy như sau: FUNCTION Giai_thua(n:Integer): Integer; BEGIN END; IF n=0 then Giai_thua :=1 ELSE Giai_thua := n* Giai_thua(n-1); Gọi T(n) là thời gian thực hiện việc tính n giai thừa, thì T(n-1) là thời gian thực hiện việc tính n-1 giai thừa. Trong trường hợp n = 0 thì chương trình chỉ thực hiện một lệnh gán Giai_thua:=1, nên tốn O(1), do đó ta có T(0) = C1. Trong trường hợp n>0 chương trình phải gọi đệ quy Giai_thua(n-1), việc gọi đệ quy này tốn T(n-1), sau khi có kết quả của việc gọi đệ quy, chương trình phải nhân kết quả đó với n và gán cho Giai_thua. Thời gian để thực hiện phép nhân và phép gán là một hằng C2. Vậy ta có Ðây là phương trình đệ quy để tính thời gian thực hiện của chương trình đệ quy Giai_thua. Chúng ta xét thủ tục MergeSort một cách phác thảo như sau: FUNCTION MergeSort (L:List; n:Integer):List; VAR L1,L2:List; BEGIN IF n=1 THEN RETURN(L) ELSE BEGIN Chia đôi L thành L1 và L2, với độ dài n/2; RETURN(Merge(MergeSort(L1,n/2),MergeSort(L2,n/2))); END; END; 10/129
13. Chẳng hạn để sắp xếp danh sách L gồm 8 phần tử 7, 4, 8, 9, 3, 1, 6, 2 ta có mô hình minh họa của MergeSort như sau: Hàm MergeSort nhận một danh sách có độ dài n và trả về một danh sách đã được sắp xếp. Thủ tục Merge nhận hai danh sách đã được sắp L1 và L2 mỗi danh sách có độ dài n/2 trộn chúng lại với nhau để được một danh sách gồm n phần tử có thứ tự. Giải thuật chi tiết của Merge ta sẽ bàn sau, chúng ta chỉ để ý rằng thời gian để Merge các danh sách có độ dài n/2 là O(n). Gọi T(n) là thời gian thực hiện MergeSort một danh sách n phần tử thì T(n/2) là thời gian thực hiện MergeSort một danh sách n/2 phần tử. Khi L có độ dài 1 (n = 1) thì chương trình chỉ làm một việc duy nhất là return(L), việc này tốn O(1) = C1 thời gian. Trong trường hợp n > 1, chương trình phải thực hiện gọi đệ quy MerSort hai lần cho L1 và L2 với độ dài n/2 do đó thời gian để gọi hai lần đệ quy này là 2T(n/2). Ngoài ra còn phải tốn thời gian cho việc chia danh sách L thành hai nửa bằng nhau và trộn hai danh sách kết quả (Merge). Người ta xác đinh được thời gian để chia danh sách và Merge là O(n) = C2n. Vậy ta có phương trình đệ quy như sau: 11/129
14. Các hàm tiến triển khác Trong trường hợp hàm tiến triển không phải là một hàm nhân thì chúng ta không thể áp dụng các công thức ứng với ba trường hợp nói trên mà chúng ta phải tính trực tiếp nghiệm riêng, sau đó so sánh với nghiệm thuần nhất để lấy nghiệm lớn nhất trong hai nghiệm đó làm nghiệm của phương trình. Vídụ2-17:Giải phương trình đệ quy sau: T(1) = 1 T(n) = 2T(n/2) + nlogn Phương trình đã cho thuộc dạng phương trình tổng quát nhưng d(n) = nlogn không phải là một hàm nhân. b Ta có nghiệm thuần nhất = nlog a = nlog2 = n Do d(n) = nlogn không phải là hàm nhân nên ta phải tính nghiệm riêng bằng cách xét trực tiếp Theo giả thiết trong phương trình tổng quát thì n = bk nên k = logbn, ở đây do b=2 nên 2k=n và k=logn, chúng ta có nghiệm riêng là O(nlog2n), nghiệm này lớn hơn nghiệm thuần nhất do đó T(n) = O(nlog2n). Bài tập chương Tính thời gian thực hiện của các đoạn chương trình sau: a) Tính tổng của các số {1} Sum := 0; 12/129
15. {2} for i:=1 to n do begin {3} readln(x); {4} Sum := Sum + x; end; b) Tính tích hai ma trận vuông cấp n C = A*B: {1} for i := 1 to n do {2} for j := 1 to n do begin {3} c[i,j] := 0; {4} for k := 1 to n do {5} c[i,j] := c[i,j] + a[i,k] * b[k,j]; end; Dành cho độc giả Giải các phương trình đệ quy sau với T(1) = 1 và a) T(n) = 3T(n/2) + n b) T(n) = 3T(n/2) + n2 c) T(n) = 8T(n/2) + n3 Dành cho độc giả Giải các phương trình đệ quy sau với T(1) = 1 và a) T(n) = 4T(n/3) + n b) T(n) = 4T(n/3) + n2. c) T(n) = 9T(n/3) + n2. Dành cho độc giả Giải các phương trình đệ quy sau với T(1) = 1 và a) T(n) = T(n/2) + 1 b) T(n) = 2T(n/2) + logn c) T(n) = 2T(n/2) + n d) T(n) = 2T(n/2) + n2 13/129
16. Dành cho độc giả Giải các phương trình đệ quy sau bằng phương pháp đoán nghiệm: a) T(1) = 2 và T(n) = 2T(n-1) + 1 với n > 1 b) T(1) = 1 và T(n) = 2T(n-1) + n với n > 1 Dành cho độc giả Cho một mảng n số nguyên được sắp thứ tự tăng. Viết hàm tìm một số nguyên trong mảng đó theo phương pháp tìmkiếmnhị phân, nếu tìm thấy thì trả về TRUE, ngược lại trả về FALSE. Sử dụng hai kĩ thuật là đệ quy và vòng lặp. Với mỗi kĩ thuật hãy viết một hàm tìm và tính thời gian thực hiện của hàm đó. Dành cho độc giả Tính thời gian thực hiện của giải thuật đệ quy giải bài toán Tháp Hà nội với n tầng? Dành cho độc giả Xét công thức truy toán để tính số tổ hợp chập k của n như sau: a) Viết một hàm đệ quy để tính số tổ hợp chập k của n. b) Tính thời gian thực hiện của giải thuật nói trên. Dành cho độc giả 14/129
17. Mở đầu về thiết kế, đánh giá thuật toán và kiến thức bổ trợ Khái niệm thuật toán Khái niệm về thuật toán Thuật toán (algorithm) là một trong những khái niệm quan trọng trong lĩnh vực tin học. Thuật ngữ thuật toán được xuất phát từ nhà toán học Arập Abu Ja’far Mohammedibn Musa al Khowarizmi (khoảng năm 825). Tuy nhiên lúc bấy giờ và trong nhiều thế kỷ sau, nó không mang nội dung như ngày nay chúng ta quan niệm. Thuật toán nổi tiếng nhất có từ thời cổ Hy lạp là thuật toán Euclid, thuật toán tìm ước chung lớn nhất của hai số nguyên. Có thể mô tả thuật toán đó như sau: ThuậttoánEuclid. Input: m, n nguyên dương Output: g (ước chung lớn nhất của m và n) Phương pháp: Bước 1: Tìm r, phần dư của m cho n Bước 2: Nếu r = 0, thì g:=n (gán giá trị của n cho g),và dừng lại. Trong trường hợp ngược lại (r≠0), thì m:=n; n:=r và quay lại bước 1. Chúng ta có thể quan niệm các bước cần thực hiện để làm một món ăn, được mô tả trong các sách dạy chế biến món ăn, là một thuật toán. Cũng có thể xem các bước cần tiến hành để gấp đồ chơi bằng giấy ,được trình bày trong sách dạy gấp đồ chơi bằng giấy là một thuật toán. Phương pháp cộng nhân các số nguuyên, chúng ta đã được học ở cấp I cũng là các thuật toán. Vì vậy ta có định nghĩa không hình thức về thuật toán như sau: Thuật toán là một dãy hữu hạn các bước, mỗi bước mô tả chính xác các phép toán, 15/129
18. hoặc hành động cần thực hiện để cho ta lời giải của bài toán. Các yêu cầu về thuật toán Định nghĩa trên về thuật toán tất nhiên còn chứa nhiều điều chưa rõ ràng. Để hiểu đầy đủ ý nghĩa của khái niệm thuật toán, chúng ta đưa ra 5 đặc trưng sau đây của thuật toán. Input Mỗi thuật toán đều có một số (có thể bằng không) các dữ liệu vào (input). Đó là các giá trị cần đưa vào khi thuật toán bắt đầu làm việc. Các dữ liệu này cần được lấy từ các tập hợp giá trị cụ thể nào đó. Chẳng hạn, trong thuật toán Euclid ở trên, các số m và n là các dữ liệu lấy từ tập các số nguyên dương. Output Mỗi thuật toán cần có một hoặc nhiều dữ liệu ra (output). Đó là các giá trị có quan hệ hoàn toàn xác định với các dữ liệu vào, và là kết quả của sự thực hiện thuật toán. Trong thuật toán Euclid, có một dữ liệu ra đó là ƯSCLN g, khi thuật toán dừng lại (trường hợp r=0) thì giá trị của g là ước chung lớn nhất của m và n. Tính xác định Ở mỗi bước, các bước thao tác phải hết sức rõ ràng, không gây nên sự nhập nhằng. Nói rõ hơn là trong cùng một điều kiện hai bộ xử lý cùng thực hiện một thuật toán phải cho cùng một kết quả như nhau. Nếu biểu diễn thuật toán bằng phương pháp thông thường không có gì đảm bảo được người đọc hiểu đúng ý của người viết thuật toán. Để đảm bảo đòi hỏi này, thuật toán cần được mô tả trong các ngôn ngữ lập trình (ngôn ngữ máy, hợp ngữ hoặc ngôn ngữ bậc cao như Pascal ). Trong các ngôn ngữ này các mệnh đề được tạo theo các qui tắc cú pháp nghiêm ngặt và chỉ có một nghĩa duy nhất. Tính khả thi/đa năng Tất cả các phép toán có mặt trong thuật toán phải đủ đơn giản . Điều đó có nghĩa là, các phép toán phải sao cho, ít nhất về nguyên tắc có thể thực hiện bởi con người chỉ bằng giấy trắng và bút chì trong một khoảng thời gian hữu hạn. Chẳng hạn, trong thuật toán Euclid ta chỉ cần thực hiện các phép chia các số nguyên, các phép gán và các phép so sánh r=0 hay r ≠ 0. Điều quan trọng nữa là thuật toán phải có tính đa năng làm việc được với tất cả các tập hợp dữ liệu có thể của đầu vào. Tính dừng Với mọi bộ dữ liệu vào thoả mãn các điều kiện của dữ liệu vào (tức là được lấy ra từ các tập của dữ liệu vào), thuật toán phải dừng lại sau một số hữu hạn bước thực hiện. 16/129
19. Thuật toán Euclid thoả mãn điều kiện này. Bởi vì giá trị của r luôn nhỏ hơn n (khi thực hiện bước 1), nếu r r =n1>r1 = n2 > r2. Dãy số nguyên dương này giảm dần và cần phải kết thúc ở 0, do đó sau một số hữu hạn bước nào đó giá trị của r phải = 0 và thuật toán phải dừng lại. Với một vấn đề đặt ra, có thể có một hoặc nhiều thuật toán giải. Một vấn đề có thuật toán giải gọi là vấn đề giải được (bằng thuật toán). Chẳng hạn, tìm nghiệm của hệ phương trình tuyến tính là vấn đề giải được. Một vấn đề không tồn tại thuật toán gọi là vấn đề không giải được (bằng thuật toán). Một trong những thành tựu suất xắc nhất của toán học thế kỷ 20 là đã tìm ra những vấn đề không giải được bằng thuật toán. Chẳng hạn thuật toán chắc thắng cho người thứ hai của cờ ca rô hoặc thuật toán xác định xem một máy Turing có dừng lại sau n bước không, đềulà những vấn đề không tồn tại thuật toán giải được. Thiết kế thuật toán Để giải một bài toán trên máy tính điện tử (MTĐT), điều trước tiên là chúng ta phải có thuật toán. Một câu hỏi đặt ra là làm thế nào để tìm ra được thuật toán cho một bài toán đã đặt ra- Lớp các bài toán được đặt ra từ các ngành khoa học kỹ thuật, từ các lĩnh vực hoạt động của con người là hết sức phong phú và đa dạng. Các thuật toán giải các lớp bài toán khác nhau cũng rất khác nhau. Tuy nhiên, có một số kỹ thuật thiết kế thuật toán chung như: Chia để trị (divide-and-conque), phương pháp tham ăn (greedy method), qui hoạch động (dynamic programming) Việc nắm được các chiến lược thiết kế thuật toán này là hết sức quan trọng và cần thiết vì nó giúp cho ta dễ tìm ra các thuật toán mới cho các bài toán mới được đưa ra. Tính đúng đắn của thuật toán Khi một thuật toán được làm ra, ta cần phải chứng minh rằng, thuật toán khi được thực hiện sẽ cho ta kết quả đúng với mọi dữ liệu vào hợp lệ. Điều này gọi là chứng minh tính đúng đắn của thuật toán. Việc chứng minh tính đúng đắn của thuật toán là một công việc không dễ dàng. Trong nhiều trường hợp, nó đòi hỏi ta phải có trình độ và khả năng tư duy toán học tốt. Sau đây ta sẽ chỉ ra rằng, khi thực hiện thuật toán Euclid, g sẽ là ước chung lớn nhất của hai số nguyên dương bất kỳ m, n. Thật vậy, khi thực hiện bước 1, ta có m = qn + r, trong đó q là số nguyên nào đó. Nếu r = 0 thì n là ước của m và hiển nhiên n (do đó g) là ước chung lớn nhất của m và n. Nếu r 0 thì một ước chung bất kỳ của m và n cũng là ước chung của n và r (vì r=m-qn). Ngược lại một ước chung bất kỳ của n và r cũng là ước chung của m và n (vì m = qn + r). Do đó ước chung lớn nhất của n và r cũng là ước chung lớn nhất của ma và n. Vì vậy, khi thực hiện lặp lại bước 1, với sự thay đổi giá trị 17/129
20. của m bởi n, và sự thay đổi giá trị của n bởi r, cho tới khi r=0 ta nhận được giá trị của g là ước chung lớn nhất của các giá trị m và n ban đầu. Phân tích thuật toán Giả sử, với một số bài toán nào đó chúng ta có một số thuật toán giải. Một câu hỏi mới xuất hiện là, chúng ta cần chọn thuật toán nào trong số các thuật toán đó để áp dụng. Việc phân tích thuật toán, đánh giá độ phức tạp của thuật toán là nội dung của phần dưới đây sẽ giải quyết vấn đề này. Đánh giá hiệu quả của thuật toán Khi giải một vấn đề, chúng ta cần chọn trong số các thuật toán, một thuật toán mà chúng ta cho là “tốt” nhất .Vậy ta cần lựa chọn thuật toán dựa trên cơ sở nào- Thông thường ta dựa trên hai tiêu chuẩn sau đây: • Thuật toán đơn giản, dễ hiểu, dễ cài đặt (dễ viết chương trình) • Thuật toán sử dụng tiết kiệm nhất các nguồn tài nguyên của máy tính, và đặc biệt chạy nhanh nhất có thể được. Khi ta viết một chương trình chỉ để sử dụng một số ít lần, và cái giá của thời gian viết chương trình vượt xa cái giá của chạy chương trình thì tiêu chuẩn (1) là quan trọng nhất. Nhưng có trường hợp ta cần viết các chương trình (hoặc thủ tục, hàm) để sử dụng nhiều lần, cho nhiều người sử dụng, khi đó giá của thời gian chạy chương trình sẽ vượt xa giá viết nó. Chẳng hạn, các thủ tục sắp xếp, tìm kiếm được sử dụng rất nhiều lần, bởi rất nhiều người trong các bài toán khác nhau. Trong trường hợp này ta cần dựa trên tiêu chuẩn 2. Ta sẽ cài đặt thuật táon có thể sẽ rất phức tạp, miễn là chương trình nhận được chạy nhanh hơn so với các chương trình khác. Tiêu chuẩn 2 được xem là tínhhiệuquảcủa thuật toán. Tính hiệu quả của thuật toán bao gồm hai nhân tố cơ bản: Dung lượng không gian nhớ cần thiết để lưu giữ các giữ liệu vào, các kết quả tính toán trung gian và các kết quả của thuật toán. Thời gian cần thiết để thực hiện thuật toán (ta gọi là thời gian chạy). Chúng ta chỉ quan tâm đến thời gian thực hiện thuậ toán, có nghĩa là ta nói đến đánh giá thời gian thực hiện. Một thuật toán có hiệu quả được xem là thuật toán có thời gian chạy ít hơn so với các thuật toán khác. 18/129
21. Các phương pháp biểu diễn thuật toán Có nhiều phương pháp biểu diễn thuật toán .Có thể biểu diễn thuật toán bằng danh sách các bước, các bước được diễn đạt bằng ngôn ngữ thông thường và các ký hiệu toán học. Có thể biểu diễn thuật toán bằng sơ đồ khối. Tuy nhiên, để đảm bảo tính xác định của thuật toán như đã trình bày trên, thuật toán cần được viết trên các ngôn ngữ lập trình. Một chương trình là sự biểu diễn của một thuật toán trong ngôn ngữ lập trình đã chọn. Thông thường ta dùng ngôn ngữ lập trình Pascal, một ngôn ngữ thường được chọn để trình bày các thuật toán trong sách báo. Ngôn ngữ thuật toán là ngôn ngữ dùng để miêu tả thuật toán .Thông thường ngôn ngữ thuật toán bao gồm ba loại: + Ngôn ngữ liệt kê từng bước; + Sơ đồ khối; + Ngôn ngữ lập trình; Phương pháp liệt kê từng bước Ngôn ngữ liệt kê từng bước nội dung như sau: Thuật toán: Tên thuật toán và chức năng. Vào: Dữ liệu vào với tên kiểu. Ra: Các dữ liệu ra với tên kiểu. Biến phụ (nếu có) gồm tên kiểu. Hành động là các thao tác với các lệnh có nhãn là các số tự nhiên. Để giải phương trình bậc hai ax2 + bx +c = 0, ta có thể mô tả thuật toán bằng ngôn ngữ liệt kê như sau: Bước 1: Xác định các hệ số a, b, c. Bước 2: Kiểm tra xem các hệ số a, b, c có khác 0 hay không- Nếu a=0 quay lại thực hiện bước 1. Bước 3: Tính biểu thức Δ= b2 – 4*a*c. 19/129
22. Bước 4: Nếu Δ <0 thông báo phương trình vô nghiệm và chuyển sang bước 8. Bước 5: − b Nếu Δ=0, tính x1=x2= 2 ∗ a và chuyển sang bước 7. − b + √Δ − b − √Δ Bước 6: Tính x1= 2a , x2= 2a và chuyển sang bước 7. Bước 7: Thông báo các nghiệm x1, x2. Bước 8: Kết thúc thuật toán. Phương pháp sơ đồ Phương pháp dùng sơ đồ khối mô tả thuật toán là dùng mô tả theo sơ đồ trên mặt phẳng các bước của thuật toán. Sơ đồ khối có ưu điểm là rất trực giác dễ bao quát. Để mô tả thuật toán bằng sơ đồ khối ta cần dựa vào các nút sau đây: Nútthaotác:Biểu diễn bằng hình chữ nhật, Nútđiềukhiển:Được biểu diễn bằng hình thoi, trong đó ghi điều kiện cần kiểm tra trong quá trình tính toán. Nútkhởiđầu,kếtthúc:Thường được biểu diễn bằng hình tròn thể hiện sự bắt đầu hay kết thúc quá trình. Cung:Đoạnnối từ nút này đến nút khác và có mũi tên chỉ hướng. 20/129
23. Một số cấu trúc dữ liệu cơ bản Danh sách Danh sách là một tập sắp thứ tự các phần tử cùng một kiểu. Đối với danh sách, người ta có một số thao tác: Tìm một phần tử trong danh sách, chèn một phần tử vào danh sách, xoá một phần tử khỏi danh sách, sắp xếp lại các phần tử trong danh sách theo một trật tự nào đó v.v Các phương pháp biểu diễn danh sách trong máy tính: - Mảng một chiều - Danh sách nối đơn 21/129
24. - Danh sách nối kép - Danh sách nối vòng một hướng - Danh sách nối vòng hai hướng Các phép toán cơ bản trên danh sách Để thiết lập kiểu dữ liệu trừu tượng danh sách (hay ngắn gọn là danh sách) ta phải định nghĩa các phép toán trên danh sách. Và như chúng ta sẽ thấy trong toàn bộ giáo trình, khôngc ó một tập hợp các phép toán nào thích hợp cho mọi ứng dụng (application). Vì vậy ở đây ta sẽ định nghĩa một số phép toán cơ bản nhất trên danh sách. Để thuận tiện cho việc định nghĩa ta giả sử rằng danh sách gồm các phần tử có kiểu là kiểu phần tử (elementType); vị trí của các phần tử trong danh sách có kiểu là kiểu vị trí và vị trí sau phần tử cuối cùng trong danh sách L là ENDLIST(L). Cần nhấn mạnh rằng khái niệm vị trí (position) là do ta định nghĩa, nó không phải là giá trị của các phần tử trong danh sách. Vị trí có thể là đồng nhất với vị trí lưu trữ phần tử hoặc không. Các phép toán được định nghĩa trên danh sách là: INSERT_LIST(x,p,L):xen phần tử x ( kiểu ElementType ) tại vị trí p (kiểu position) trong danh sách L. Tức là nếu danh sách là a1, a2, . , ap-1, ap, , an thì sau khi xen ta có kết quả a1, a2. . . ap-1, x, ap, . . . , an. Nếu vị trí p không tồn tại trong danh sách thì phép toán không được xác định. LOCATE(x,L):thực hiện việc định vị phần tử có nội dung x đầu tiên trong danh sách L. Locate trả kết quả là vị trí (kiểu position) của phần tử x trong danh sách. Nếu x không có trong danh sách thì vị trí sau phần tử cuối cùng của danh sách được trả về, tức là ENDLIST(L). - RETRIEVE(p,L):lấy giá trị của phần tử ở vị trí p (kiểu position) của danh sách L; nếu vị trí p không có trong danh sách thì kết quả không xác định (có thể thông báo lỗi). - DELETE_LIST(p,L):chương trình con thực hiện việc xoá phần tử ở vị trí p (kiểu position) của danh sách. Nếu vị trí p không có trong danh sách thì phép toán không được định nghĩa và danh sách L sẽ không thay đổi - NEXT(p,L):cho kết quả là vị trí của phần tử (kiểu position) đi sau phần tử p; nếu p là phần tử cuối cùng trong danh sách L thì NEXT(p,L) cho kết quả là ENDLIST(L):Next không xác định nếu p không phải là vị trí của một phần tử trong danh sách. 22/129
25. - PREVIOUS(p,L):cho kết quả là vị trí của phần tử đứng trước phần tử p trong danh sách. Nếu p là phần tử đầu tiên trong danh sách thì Previous(p,L) không xác định. Previous cũng không xác định trong trường hợp p không phải là vị trí của phần tử nào trong danh sách. - FIRST(L):cho kết quả là vị trí của phần tử đầu tiên trong danh sách. Nếu danh sách rỗng thì ENDLIST(L) được trả về. - EMPTY_LIST(L):cho kết quả TRUE nếu danh sách có rỗng, ngược lại nó cho giá trị FALSE. - MAKENULL_LIST(L):khởi tạo một danh sách L rỗng. - Trong thiết kế các giải thuật sau này chúng ta dùng các phép toán trừu tượng đã được định nghĩa ở đây như là các phép toán nguyên thủy. Đồ thị Các định nghĩa Một đồ thị G bao gồm một tập hợp V các đỉnh và một tập hợp E các cung, ký hiệu G=(V,E). Các đỉnh còn được gọi là nút (node) hay điểm (point). Các cung nối giữa hai đỉnh, hai đỉnh này có thể trùng nhau. Hai đỉnh có cung nối nhau gọi là hai đỉnh kề (adjacency). Một cung nối giữa hai đỉnh v, w có thể coi như là một cặp điểm (v,w). Nếu cặp này có thứ tự thì ta có cung có thứ tự, ngược lại thì cung không có thứ tự. Nếu các cung trong đồ thị G có thứ tự thì G gọi là đồ thị có hướng (directed graph). Nếu các cung trong đồ thị G không có thứ tự thì đồ thị G là đồ thị vô hướng (undirected graph). Biểu diễn đồ thị - Biểu diễn đồ thị bằng ma trận kề - Biểu diễn đồ thị bằng danh sách các đỉnh kề: Các phép duyệt đồ thị - Duyệt theo chiều sâu (depth-first search) - Duyệt theo chiều rộng (breadth-first search) 23/129
26. Cây Các thuật ngữ cơ bản trên cây Cây là một tập hợp các phần tử gọi là nút (nodes) trong đó có một nút được phân biệt gọi là nút gốc (root). Trên tập hợp các nút này có một quan hệ, gọi là mối quan hệ cha-con(parenthood), để xác định hệ thống cấu trúc trên các nút. Mỗi nút, trừ nút gốc, có duy nhất một nút cha. Một nút có thể có nhiều nút con hoặc không có nút con nào. Mỗi nút biểu diễn một phần tử trong tập hợp đang xét và nó có thể có một kiểu nào đó bất kỳ, thường ta biểu diễn nút bằng một kí tự, một chuỗi hoặc một số ghi trong vòng tròn. Mối quanhệchaconđược biểu diễn theo qui ước nútchaởdòng trênnútconởdòngdướivàđượcnốibởimộtđoạnthẳng. Một cách hình thức ta có thể định nghĩa cây một cách đệ qui như sau: Định nghĩa Một nút đơn độc là một cây. Nút này cũng chính là nút gốc của cây. Giả sử ta có n là một nút đơn độc và k cây T1, , Tk với các nút gốc tương ứng là n1, , nk thì có thể xây dựng một cây mới bằng cách cho nút n là cha của các nút n1, , nk. Cây mới này có nút gốc là nút n và các cây T1, , Tk được gọi là các cây con. Tập rỗng cũng được coi là một cây và gọi là cây rỗng kí hiệu. Xét mục lục của một quyển sách. Mục lục này có thể xem là một cây Cây m ụ c l ụ c m ột qu y ể n sách Nút gốc là sách, nó có ba cây con có gốc là C1, C2, C3. Cây con thứ 3 có gốc C3 là một nút đơn độc trong khi đó hai cây con kia (gốc C1 và C2) có các nút con. Nếu n1, , nk là một chuỗi các nút trên cây sao cho ni là nút cha của nút ni+1, với i=1 k-1, thì chuỗi này gọi là một đườngđitrêncây(hay ngắn gọn là đường đi ) từ n1 đến nk. Độdàiđườngđiđược định nghĩa bằng số nút trên đường đi trừ 1. Như vậy độ dài đường đi từ một nút đến chính nó bằng không. Nếu có đường đi từ nút a đến nút b thì ta nói a là tiềnbối (ancestor) của b, còn b gọi là hậuduệ(descendant) của nút a. Rõ ràng một nútvừalàtiềnbối vừalàhậu duệcủachínhnó. Tiền bối hoặc hậu duệ của một nút khác với chính nó gọi là tiền bối hoặc hậu duệ thực sự. Trên cây nútgốckhông có tiền bối thực sự. Một nút không có hậu duệ thực sự gọi là nútlá(leaf). Nút không phải là lá ta còn gọi là núttrung gian(interior). Cây con của một cây là một nút cùng với tất cả các hậu duệ của nó. 24/129
27. Chiềucaocủamộtnútlà độ dài đường đi lớn nhất từ nút đó tới lá. Chiềucaocủa câylà chiều cao của nút gốc. Độsâucủamộtnútlà độ dài đường đi từ nút gốc đến nút đó. Các nút có cùng một độ sâu i ta gọi là các nút có cùng một mức i. Theo định nghĩa này thì nút gốc ở mức 0, các nút con của nút gốc ở mức 1. Các thứ tự duyệt cây quan trọng Duyệt cây là một qui tắc cho phép đi qua lần lượt tất cả các nút của cây mỗi nút đúng một lần, danh sách liệt kê các nút (tên nút hoặc giá trị chứa bên trong nút) theo thứ tự đi qua gọi là danh sách duyệt cây. Có ba cách duyệt cây quan trọng: Duyệt tiềntự (preorder), duyệttrungtự(inorder), duyệt hậutự(posorder). Có thể định nghĩa các phép duyệt cây tổng quát một cách đệ qui như sau: - Cây rỗng thì danh sách duyệt cây là rỗng và nó được coi là biểu thức duyệt tiền tự, trung tự, hậu tự của cây. - Cây chỉ có một nút thì danh sách duyệt cây gồm chỉ một nút đó và nó được coi là biểu thức duyệt tiền tự, trung tự, hậu tự của cây. - Ngược lại: giả sử cây T có nút gốc là n và có các cây con là T1, ,Tn thì: + Biểu thức duyệt tiền tự của cây T là liệt kê nút n kế tiếp là biểu thức duyệt tiền tự của các cây T1, T2, , Tn theo thứ tự đó. + Biểu thức duyệt trung tự của cây T là biểu thức duyệt trung tự của cây T1 kế tiếp là nút n rồi đến biểu thức duyệt trung tự của các cây T2, , Tn theo thứ tự đó. + Biểu thức duyệt hậu tự của cây T là biểu thức duyệt hậu tự của các cây T1, T2, , Tn theo thứ tự đó rồi đến nút n. Cho cây như trong hình Biểu thức duyệt tiền tự: A B C D E F H K L Trung tự: C B E D F A K H L Hậu tự: C E F D B K L H A 25/129
28. Các phép toán trên cây - Hàm PARENT(n,T)cho nút cha của nút n trên cây T, nếu n là nút gốc thì hàm cho giá trị NULL. Trong cài đặt cụ thể thì NULL là một giá trị nào đó do ta chọn, nó phụ thuộc vào cấu trúc dữ liệu mà ta dùng để cài đặt cây. - Hàm LEFTMOST_CHILD(n,T)cho nút con trái nhất của nút n trên cây T, nếu n là lá thì hàm cho giá trị NULL. - Hàm RIGHT_SIBLING(n,T)cho nút anh em ruột phải nút n trên cây T, nếu n không có anh em ruột phải thì hàm cho giá trị NULL. - Hàm LABEL_NODE(n,T)cho nhãn tại nút n của cây T. - Hàm ROOT(T)trả ra nút gốc của cây T. Nếu Cây T rỗng thì hàm trả về NULL. - Hàm CREATEi(v,T1,T2, ,Ti),với i=0 n, thủ tục tạo cây mới có nút gốc là n được gán nhãn v và có i cây con T1, ,Ti. Nếu n= 0 thì thủ tục tạo cây mới chỉ gồm có 1 nút đơn độc là n có nhãn v. Chẳng hạn, giả sử ta có hai cây con T1 và T2, ta muốn thiết lập cây mới với nút gốc có nhãn là v thì lời gọi thủ tục sẽ là CREATE2(v,T1,T2). Cài đặt cây - Cài đặt cây bằng mảng - Biểu diễn cây bằng danh sách các con - Biểu diễn theo con trái nhất và anh em ruột phải: Cây nhị phân (Binary Trees) Cây nhị phân là cây rỗng hoặc là cây mà mỗi nút có tối đa hai nút con. Hơn nữa các nút con của cây được phân biệt thứ tự rõ ràng, một nút con gọi là nút con trái và một nút con gọi là nút con phải. Ta qui ước vẽ nút con trái bên trái nút cha và nút con phải bên phải nút cha, mỗi nút con được nối với nút cha của nó bởi một đoạn thẳng. Cây tìm kiếm nhị phân (Binary Search Trees) Cây tìm kiếm nhị phân (TKNP) là cây nhị phân mà khoá tại mỗi nút cây lớn hơn khoá của tất cả các nút thuộc cây con bên trái và nhỏ hơn khoá của tất cả các nút thuộc cây con bên phải. Lưu ý: dữ liệu lưu trữ tại mỗi nút có thể rất phức tạp như là một record chẳng hạn, trong trường hợp này khoá của nút được tính dựa trên một trường nào đó, ta gọi là trường khoá. Trường khoá phải chứa các giá trị có thể so sánh được, tức là nó phải lấy giá trị từ một tập hợp có thứ tự. 26/129
29. Tập hợp Định nghĩa Tập hợp là một khái niệm cơ bản trong toán học. Tập hợp được dùng để mô hình hoá hay biểu diễn một nhóm bất kỳ các đối tượng trong thế giới thực cho nên nó đóng vai trò rất quan trọng trong mô hình hoá cũng như trong thiết kế các giải thuật. Khái niệm tập hợp cũng như trong toán học , đó là sự tập hợp các thành viên ( members ) hoặc phần tử (elements) . Tất cả các phần tử của tập hợp là khác nhau. Tập hợp có thể có thứ tự hoặc không có thứ tự, tức là , có thể có quan hệ thứ tự xác định trên các phần tử của tập hợp hoặc không. Tuy nhiên, trong chương này, chúng ta giả sử rằng các phần tử của tập hợp có thứ tự tuyến tính, tức là , trên tập hợp S có quan hệ < và = thoả mản hai tính chấ t: - Với mọi a,b S thì a<b hoặc b<a hoặc a =b - Với mọi a,b ,c S, a <b và b<c thì a <c Các phép toán cơ bản trên kiểu dữ liệu tập hợp Cũng như các kiểu dữ liệu trừu tượng khác, các phép toán kết hợp với mô hình tập hợp sẽ tạo thành một kiểu dữ liệu trừu tượng là rất đa dạng . Tùy theo nhu cầu của các ứng dụng mà các phép toán khác nhau sẽ được định nghĩa trên tập hợp. Ở đây ta đề cập đến một số phép toán thường gặp nhất như sau : - Thủ tục UNION(A,B,C)nhận vào 3 tham số là A,B,C; Thực hiện phép toán lấy hợp của hai tập A và B và trả ra kết quả là tập hợp C = A ?B. - Thủ tục INTERSECTION(A,B,C)nhận vào 3 tham số là A,B,C; Thực hiện phép toánlấy giao của hai tập A và B và trả ra kết quả là tập hợp C = A ? B. - Thủ tục DIFFERENCE(A,B,C)nhận vào 3 tham số là A,B,C; Thực hiện phép toán lấy hợp của hai tập A và B và trả ra kết quả là tập hợp C = A\B - Hàm MEMBER(x,A)cho kết quả kiểu logic (đúng/sai) tùy theo x có thuộc A hay không. Nếu x ∈ A thì hàm cho kết quả là 1 (đúng), ngược lại cho kết quả 0 (sai). - Thủ tục MAKENULLSET(A)tạo tập hợp A tập rỗng - Thủ tục INSERTSET(x,A)thêm x vào tập hợp A - Thủ tục DELETESET(x,A)xoá x khỏi tập hợp A 27/129
30. - Thủ tục ASSIGN(A,B)gán A cho B ( tức là B:=A ) - Hàm MIN(A)cho phần tử bé nhất trong tập A - Hàm EQUAL(A,B)cho kết quả TRUE nếu A=B ngược lại cho kết quả FALSE Cài đặt tập hợp - Cài đặt tập hợp bằng vector Bit - Cài đặt bằng danh sách liên kết Ngôn ngữ tựa Pascal Bảng chữ cái và ký tự chủ yếu Ngôn ngữ tựa Pascal được sử dụng dùng để mô tả các bước của thuật toán. Nó có đặc điểm là giúp mô tả thuật toán gần gũi với một chương trình máy tính và làm mô tả thuật toán trở nên chính xác hơn. Dưới đây là liệt kê một số câu lệnh chính được sử dụng để mô tả thuật toán dùng ngôn ngữ lập trình Pascal: Ký tự và biểu thức Các ký tự la tinh: A, a Z, z. Chữ số: 0 9. Các phép toán số học: +, - , *, / Các phép toán quan hệ : , =, Giá trị logic: T (true), F (false) Phép toán logic: and, or, not Hằng đó là các giá trị cụ thể nào đó Tên biến: Là một dãy kí tự mà kí tự đầu phải là chữ cái. Có hai loại biến chính: Loại integer (biến nguyên). Var bien: integer; Loại Real (biến thực) . var bien real; Biến chỉ số. Ở đây i là các biến nguyên. Biểu thức là kết hợp các hằng, biến và các phép toán. 28/129
31. Một số câu lệnh chính Đầu chương trình program (tên chương trình) .Tên chương trình có cấu trúc giống tên biến . Program giai_pt; Các thủ tục và hàm Câu lệnh Procedure (function). Mô tả thuật toán trong ngôn ngữ phỏng Pascal, được bắt đầu bằng câu lệnh procedure (function), trong đó ta đặt tên cho thuật toán và mô tả danh sách biến của thuật toán. Chẳng hạn, câu lệnh Function max(a,b,c); Cho biết tên của thuật toán là max và các biến là a, b, c Procedure move(n,A,B,C); Cho biết tên thuật toán được mô tả là move với các biến là n, A, B, C; Các bước của thuật toán được mô tả trong thân thủ tục (hàm) được bắt đầu bởi Begin và kết thúc bởi end. Function max(a,b,c); Begin (thân hàm) End; Procedure move(n,A,B,C); Begin (thân thủ tục) end; Câu l ệnh gán Câu lệnh gán được dùng để gán giá trị cho các biến Vế trái của câu lệnh gán là tên của biến , còn vế phải là biểu thức của các hằng , biến đã gán giá trị hoặc các hàm đã được định nghĩa. Ký hiệu := được sử dụng để biểu diễn phép gán. 29/129
32. Variable := exp; Max := a; x := số lớn nhất trong các số a,b,c Khối câu lệnh Các câu lệnh có thể nhóm lại thành một khối. Để mô tả khối lệnh ta sử dụng Begin và end Begin Câu lệnh 1; Câu lệnh 2; Câu lệnh n; End; Các câu lệnh trong khối được thực hiện tuần tự. Dưới đây thuật ngữ câu lệnh được dùng để chỉ chung một câu lệnh cũng như một khối câu lệnh. (*a là số phần tử lớn nhất trong danh sách L*) k là số phần tử của danh sách L Câu lệnh điều kiện. Câu lệnh đơn giản là If điều kiện then câu lệnh; Khi thực hiện câu lệnh, điều kiện sẽ được kiểm tra, nếu nó được thoả mãn thì câu lệnh sẽ được thực hiện. Nhiều khi ta cần thực hiện một thao tác nào đó khi điều kiện được thực hiện còn nếu ngược lại ta phải thực hiện một thao tác khác. Khi đó ta có thể thực hiện câu lệnh phức tạp hơn sau đây: If điều kiện then câu lệnh 1 else câu lệnh 2; Các câu lệnh lặp. 30/129
33. Các câu lệnh sau đây sẽ được sử dụng For biến := giá trị đầu to giá trị cuối do câu lệnh; Tại đầu vòng lặp, biến được sẽ gán cho giá trị đầu, nếu giá trị đầu nhỏ hơn hơn hoặc bằng giá trị cuối và câu lệnh được thực hiện với giá trị này của biến. Tiếp đến giá trị của biến sẽ tăng lên 1và câu lệnh sẽ được thực hiện với giá trị mới của biến. Quá trình sẽ được tiếp tục cho đến khi biến bằng giá trị cuối. Sau khi thực hiện câu lệnh với biến bằng giá trị cuối sẽ chuyển sang thực hiện câu lệnh tiếp theo. Nếu giá trị đầu lớn hơn giá trị cuối thì không có câu lệnh nào được thực hiện. Câu lệnh lặp thứ hai được sử dụng là câu lệnh “while” While điều kiện do câu lệnh; Khi câu lệnh này được sử dụng, điều kiện sẽ được kiểm tra, nếu nó là đúng thì câu lệnh được thực hiện .Điều đó sẽ tiếp tục cho đến khi điều kiện sai. Câu lệnh tiếp theo được sử dụng là câu lệnh “repeat” Repeat câu lệnh until điều kiện; Khi câu lệnh này được sử dụng thì câu lệnh trong vòng lặp được thực hiện, điều đó có thể sẽ dẫn đến sự thay đổi giá trị của các biến trong điều kiện. Nếu điều kiện vẫn là đúng, thì câu lệnh lại được thực hiện. Điều đó sẽ tiếp diễn cho đến khi điều kiện là đúng. Để giải phương trình bậc hai ax2 + bx + c = 0 ta mô tả thuật toán bằng một chương trình viết trên Pascal như sau: Program giai_PT; Var a,b,c, denta, x1, x2 : real; Begin Clrscr; Write(‘Nhập hệ số:’); Repeat Write(‘a:=’);readln(a); Write(‘b:=’);readln(b); Write(‘c:=’);readln(c); Until a<>0; Denta:=sqr(b)-4*a*c; If denta<0 then Begin 31/129
34. Write(‘phương trình vô nghiệm’); Halt; End Else Begin If denta=0 then Begin End Else Begin Write(‘phương trình có nghiệm kép x=’,(b/(2*a))); Exit; X1:=(-b-sqrt(denta))/(2*a); X2:=(-b+sqrt(denta))/(2*a); Write(‘phương trình có hai nghiệm phân biệt:’); Write(‘x1 = ‘ , x1 , ’x2 = ‘,x2); Exit; End; End; Readln; End. Bài tập chương Xác định số phép tính so sánh nhiều nhất có thể trong thuật toán của bạn tìm phần tử lớn nhất của một dãy n số thực cho trước. Dành cho độc giả. Xác định số phép tính so sánh nhiều nhất có thể trong thuật toán của bạn để xếp lại một dãy có n số thực theo thứ tự tăng dần. Dành cho độc giả. 32/129
35. Xác định số bước thực hiện nhiều nhất có thể trong thuật toán của bạn nhằm xác định được nhiều nhất có thể các số liên tiếp nhau có tổng dương trong một dãy n số hạng cho trước. Dành cho độc giả. Mô tả các thuật toán của bạn bằng sơ đồ khối: a) Thuật toán tìm phần tử lớn nhất của một dãy hữu hạn số thực. b) Thuật toán tìm phần tử bé nhất của một tập con của tập hợp. c) Thuật toán xếp lại một dãy theo thứ tự tăng dần. d) Thuật toán tìm một dãy các số liên tiếp nhau (dài nhất có thể) có tổng dương trong một dãy số thực cho trước. Dành cho độc giả. Viết các thuật toán của bạn bằng ngôn ngữ tựa Pascal: a) Thuật toán tìm phần tử lớn nhất của một dãy hữu hạn số thực. b) Thuật toán tìm phần tử bé nhất của một tập hợp con của tập hợp. c) Thuật toán xếp lại một dãy theo thứ tự tăng dần. d) Thuật toán tìm một dãy các số liên tiếp nhau (dài nhất có thể) có tổng dương trong một dãy số thực cho trước. Dành cho độc giả. 33/129
36. Phương pháp tham lam Đặc trưng của chiến lược tham lam Bài toán tối ưu tổ hợp • Là một dạng của bài toán tối ưu, nó có dạng tổng quát như sau: • Cho hàm f(X) = xác định trên một tập hữu hạn các phần tử D. Hàm f(X) được gọi là hàm mục tiêu. • Mỗi phần tử X Є D có dạng X = (x1, x2 xn) được gọi là một phương án. • Cần tìm một phương án X Є D sao cho hàm f(X) đạt min (max). Phương án X như thế được gọi là phương án tối ưu. Ta có thể tìm thấy phương án tối ưu bằng phương pháp “vét cạn” nghĩa là xét tất cả các phương án trong tập D (hữu hạn) để xác đinh phương án tốt nhất. Mặc dù tập hợp D là hữu hạn nhưng để tìm phương án tối ưu cho một bài toán kích thước n bằng phương pháp “vét cạn” ta có thể cần một thời gian mũ. Các phần tiếp theo của chương này sẽ trình bày một số kĩ thuật giải bài toán tối ưu tổ hợp mà thời gian có thể chấp nhận được. Nội dung kĩ thuật tham ăn Tham ăn hiểu một cách dân gian là: trong một mâm có nhiều món ăn, món nào ngon nhất ta sẽ ăn trước và ăn cho hết món đó thì chuyển sang món ngon thứ hai, lại ăn hết món ngon thứ hai này và chuyển sang món ngon thứ ba Kĩ thuật tham ăn thường được vận dụng để giải bài toán tối ưu tổ hợp bằng cách xây dựng một phương án X. Phương án X được xây dựng bằng cách lựa chọn từng thành phần Xi của X cho đến khi hoàn chỉnh (đủ n thành phần). Với mỗi Xi, ta sẽ chọn Xi tối ưu. Với cách này thì có thể ở bước cuối cùng ta không còn gì để chọn mà phải chấp nhận một giá trị cuối cùng còn lại. Áp dụng kĩ thuật tham ăn sẽ cho một giải thuật thời gian đa thức, tuy nhiên nói chung chúng ta chỉ đạt được một phương án tốt chứ chưa hẳn là tối ưu. Có rất nhiều bài toán mà ta có thể giải bằng kĩ thuật này. Đặc tính lựa chọn tham lam Toàn bộ phương pháp tối ưu có thể đạt được từ việc chọn tối ưu trong từng bước chọn. Về khía cạnh này giải thuật tham lam khác với giải thuật quy hoạch động ở chỗ: Trong qui hoạch động chúng ta thực hiện chọn cho từng bước, nhưng việc lựa chọn này phụ thuộc vào cách giải quyết các bài toán con. Với giải thuật tham lam, tại mỗi bước chúng 34/129
37. ta chọn bất cứ cái gì là tốt nhất vào thời điểm hiện tại, và sau đó giải quyết các vấn đề phát sinh từ việc chọn này. Vấn đề chọn thực hiện bởi giải thuật tham lam không phụ thuộc vào việc lựa chọn trong tương lai hay cách giải quyết các bài toán con. Vì vậy khác với quy hoạch động, giải quyết các bài toán con theo kiểu bottom up (từ dưới lên), giải thuật tham lam thường sử dụng giải pháp top-down (từ trên xuống). Chúng ta phải chứng minh rằng với giải thuật tham lam, toàn bộ bài toán được giải quyết một cách tối ưu nếu mỗi bước việc chọn được thực hiện tối ưu. Các bước chọn tiếp theo được thực hiện tương tự như bước đầu tiên, nhưng với bài toán nhỏ hơn. Ph- ương pháp qui nạp được ứng dụng trong giải thuật tham lam có thể được sử dụng cho tất cả các bước chọn Cấu trúc con tối ưu Một bài toán thực hiện optimal substructure nếu cách giải quyết tối ưu của bài toán chứa đựng cách giải quyết tối ưu những bài toán con của nó. Tính chất này được đánh giá là một thành phần có thể áp dụng được của thuật toán quy hoạch động tốt như thuật toán tham lam. Một ví dụ của optimal substructure, nếu A là đáp án tối ưu của bài toán với hành động chọn đầu tiên là 1, thì tập hợp A’= A- {1} là đáp án tối ưu cho bài toán S’= {i Є S: si ≥ f1 }. Sơ đồ chung của phương pháp Đặc điểm chung của thuật toán tham lam Mục đích xây dựng bài toán giải nhiều lớp bài toán khác nhau, đưa ra quyết định dựa ngay vào thuật toán đang có, và trong tương lai sẽ không xem xét lại quyết định trong quá khứ. Vì vậy thuật toán dễ đề xuất, thời gian tính nhanh nhưng thường không cho kết quả đúng. • Lời giải cần tìm có thể mô tả như là bộ gồm hữu hạn các thành phần thoả mãn điều kiện nhất định, ta phải giải quyết bài toán một cách tối ưu -> hàm mục tiêu • Để xây dựng lời giải ta có một tập các ứng cử viên • Xuất phát từ lời giải rỗng, thực hiện việc xây dựng lời giải từng bước, mỗi bước sẽ lựa chọn trong tập ứng cử viên để bổ xung vào lời giải hiện có. • Xây dựng một hàm nhận biết tính chấp nhận được của lời giải hiện có -> Hàm Solution(S) -> Kiểm tra thoả mãn điều kiện chưa. Một hàm quan trọng nữa: Select(C) cho phép tại mỗi bước của thuật toán lựa chọn ứng cử viên có triển vọng nhất để bổ xung vào lời giải hiện có -> dựa trên căn cứ vào ảnh hưởng của nó vào hàm mục tiêu, thực tế là ứng cử viên đó phải giúp chúng ta phát triển tiếp tục bài toán. 35/129
38. Xây dựng hàm nhận biết tính chấp nhận được của ứng cử viên được lựa chọn, để có thể quyết định bổ xung ứng cử viên được lựa chọn bởi hàm Select vào lời giải -> Feasible(S x). Sơ đồ thuật toán Procedure Greedy; {*G i ả sử C l à t ập các ứng cử viên*} begin S :=Ø ; {* S là l ời giải xây dựng theo thuật toán *} While(C≠ 0)andnotSolution(S)do Begin x ← size 12{ leftarrow } {}Select( C ); C:=C\x; If feasible(S x) then S:=S x End; If solution(S) then return S; End; Chứng minh tính đúng đắn • Công việc này không phải đơn giản. Ta sẽ nêu một lập luận được sử dụng để chúng minh tính đúng đắn. • Để chỉ ra thuật toán không cho lời giải đúng chỉ cần đưa ra một phần ví dụ • Việc chứng minh thuật toán đúng khó hơn nhiều và ta sẽ nghiên cứu cụ thể trong phần sau: Lập luận biến đổi (Exchange A r gument) Giả sử cần chứng minh thuật toán A cho lời giải đúng. A(I) là lời giải tìm được bởi thuật toán A đối với bộ dữ liệu I. Còn O là lời giải tối ưu của bài toán với bộ dữ liệu này. Ta cần tìm cách xây dựng phép biến đổi φ để biến đổi O thành O’ sao cho: 36/129
39. 1. O’ cũng tốt không kém gì O (Nghĩa là O’ vẫn tối ưu) 2. O’ giống với A(I) nhiều hơn O. Giả sử đã xây dựng được phép biến đổi vừa nêu. Để chứng minh tính đúng đắn dựa vào hai sơ đồ chứng minh sau - CMbằngphảnchứng:Giả sử A không đúng đắn, hãy tìm bộ dữ liệu I sao cho A(I) khác với lời giải tối ưu của bài toán. Gọi O là lời giải tối ưu giống với A(I) nhất => A(I) khác O. Dùng phép biến đổi φ chúng ta có thể biến đổi O → O’ sao cho O’ vẫn tối ưu và O’ giống với A(I) hơn => mâu thuẫn giả thiết O là lời giải tối ưu giống với A(I) nhất. -CMtrựctiếp:O là lời giải tối u. Biến đổi O → O’ giống với A(I) hơn là O. Nếu O’ = A(I) thì A(I) chính là phương án tối u ngược lại biến đổi O’ → O’’ giống với A(I) hơn. Cứ thế ta thu được dãy O’, O’’, O’’’ ngày càng giống hơn, và chỉ có một số hữu hạn điều kiện để so sánh nên chỉ sau một số hữu hạn lần phép biến đổi sẽ kết thúc và đó là tại A(I). Bài toán trả tiền của máy rút tiền tự động ATM Trong máy rút tiền tự động ATM, ngân hàng đã chuẩn bị sẵn các loại tiền có mệnh giá 100.000 đồng, 50.000 đồng, 20.000 đồng và 10.000 đồng. Giả sử mỗi loại tiền đều có số lượng không hạn chế. Khi có một khách hàng cần rút một số tiền n đồng (tính chẵn đến 10.000 đồng, tức là n chia hết cho 10000). Hãy tìm một phương án trả tiền sao cho trả đủ n đồng và số tờ giấy bạc phải trả là ít nhất. Gọi X = (X1, X2, X3, X4) là một phương án trả tiền, trong đó X1 là số tờ giấy bạc mệnh giá 100.000 đồng, X2 là số tờ giấy bạc mệnh giá 50.000 đồng, X3 là số tờ giấy bạc mệnh giá 20.000 đồng và X4 là số tờ giấy bạc mệnh giá 10.000 đồng. Theo yêu cầu ta phải có X1 + X2 + X3 + X4 nhỏ nhất và X1 * 100.000 + X2 * 50.000 + X3 * 20.000 + X4 * 10.000 = n. Áp dụng kĩ thuật tham ăn để giải bài toán này là: để có số tờ giấy bạc phải trả (X1 + X2 + X3 + X4) nhỏ nhất thì các tờ giấy bạc mệnh giá lớn phải được chọn nhiều nhất. Trước hết ta chọn tối đa các tờ giấy bạc mệnh giá 100.000 đồng, nghĩa là X1 là số nguyên lớn nhất sao cho X1 * 100.000 ≤ n. Tức là X1 = n DIV 100.000. Xác định số tiền cần rút còn lại là hiệu n – X1 * 100000 và chuyển sang chọn loại giấy bạc 50.000 đồng 37/129
40. Khách hàng cần rút 1.290.000 đồng (n = 1290000), phương án trả tiền như sau: X1 = 1290000 DIV 100000 = 12. Số tiền cần rút còn lại là 1290000 – 12 * 100000 = 90000. X2 = 90000 DIV 50000 = 1. Số tiền cần rút còn lại là 90000 – 1 * 50000 = 40000. X3 = 40000 DIV 20000 = 2. Số tiền cần rút còn lại là 40000 – 2 * 20000 = 0. X4 = 0 DIV 10000 = 0. Ta có X = (12, 1, 2, 0), tức là máy ATM sẽ trả cho khách hàng 12 tờ 100.000 đồng, 1 tờ 50.000 đồng và 2 tờ 20.000 đồng. Bài toán về các đoạn thẳng không giao nhau Bài toán Đầu vào : Cho họ các đoạn thẳng mở Đầu ra : Tập các đoạn thẳng không giao nhau có lực lượng lớn nhất. Ứngdụngthựctế: Bài toán xếp thời gian biểu cho các hội thảo, bài toán phục vụ khách hành trên một máy, bài toán lựa chọn hành động (Ví dụ có nlời mời dự tiệc bắt đầu bởi aikết thúc bởi bi, hãy lựa chọn sao cho đi được nhiều tiệc nhất). Đề xuất các thuật to á n : Greedy 1: Sắp xếp các đoạn thẳng theo thứ tự tăng dần của đầu mút trái, bắt đầu từ tập S là tập rỗng ta lần lượt xếp các đoạn thẳng trong danh sách theo thứ tự đã xếp và bổ sung đoạn thẳng đang xét vào S nếu nó không có điểm chung với bất cứ đoạn nào trong S. Thuật toán : Procedure Greedy1; Begin S:=Ø;{*Slàtậpcácđoạnthẳngcần tìm*} WhileC≠ 0do Begin 38/129
41. End; (ac,bc)Є đoạnđầu tiêntrongC; C:=C\(ac,bc); If th e n S := S (ac, bc) End; Tuy nhiên Greedy1 không cho lời giải tối ưu. Ví dụ sau Ta thấy rằng thuật toán sẽ lựa chọn dạ tiệc 1, trong khi phương án tối ưu của bài toán là (Dạ tiệc 2, Dạ tiệc 3) Greedy2: Ta chọn đoạn có độ dài ngắn nhất bổ xung vào S. Tuy nhiên thuật toán tham lam này cũng không cho kết quả tối ưu. Sau đây là phản ví dụ 39/129
42. Khi đó thuật toán sẽ lựa chọn (dạ tiệc 1) trong khi lời giải tối ưu của thuật toán là (dạ tiệc 2, dạ tiệc 3). Greedy3:Xắp xếp các đoạn thẳng theo thứ tự không giảm của mút phải. Bắt đầu từ tập S là tập rỗng ta lần lượt xét các đoạn trong danh sách theo thứ tự đã sắp xếp và bổ xung đoạn thẳng đang xét vào S nếu nó không có điểm chung với bất cứ đoạn nào trong S. (Dạ tiệc nào kết thúc sớm sẽ được xét trước). Mệnhđề1: Thuật toán Greedy3 cho lời giải tối ưu của bài toán về các đoạn thẳng không giao nhau. ChứngMinh: Giả sử Greedy3 không cho lời giải đúng. Phải tìm bộ dữ liệu C sao cho thuật toán không cho lời giải tối u. Giả sử G3(C) là lời giải tìm được bởi Greedy3. Gọi O là lời giải tối ưu có số đoạn thẳng chung với G3(C) là lớn nhất. Gọi X là đoạn thẳng đầu tiên có trong G3(C) nhưng không có trong O. Đoạn này là tồn tại, vì nếu trái lại thì G3(C) ≡ O ( mâu thuẫn vì đã giả thiết G3(C) ≠ O ) hay G3(C) Є O ( Cũng mâu thuẫn vì khi đó thuật toán phải chọn đoạn thẳng X) (O cũng được sắp xếp giống G3(C)). Gọi Y là đoạn đầu tiên kể từ bên trái của O không có mắt trong G3(C). Đoạn Y cũng phải tồn tại (Chứng minh tương tự như trên). Khi đó mút phải của đoạn X phải ở bên trái (nhỏ hơn) mút phải của đoạn Y, vì nếu trái lại thuật toán sẽ chọn Y thay vì X. Xét Rõ ràng • O’ gồm các đoạn thẳng không giao với nhau, bởi vì X không giao với bất kì đoạn nào ở bên trái nó trong O’ ( do G3(C) là chấp nhận được ) cũng như không giao với bất cứ đoạn nào ở bên phải nó trong O’ (Do mút phải của X nhỏ 40/129
43. hơn mút phải của Y và Y không giao với bất cứ đoạn nào ở bên phải Y trong O’). • Do O’ có cùng lực lượng với O nên O’ cũng là tối ưu • Tuy nhiên ta thấy rằng O’ giống với G3(C) hơn là O => mâu thuẫn với giả thiết. Bài toán cái túi Bài toán: cho n đồ vật, trong lượng tương ứng của từng đồ vật là wi, và giá trị là ci(), Ta chất đồ vật vào túi có trọng lượng b, sao cho tổng trọng lượng không vượt quá b và đạt giá trị lớn nhất. Đề xuất thuật toán t h am lam Greedy1: Sắp xếp theo thứ tự không tăng của giá trị. Xét các đồ vật theo thứ tự đã xếp, lần lượt chất các đồ vật đang xét vào túi nếu dung lượng còn lại trong túi đủ chứa nó. Thuật toán tham lam này không cho lời giải tối ưu. Sau đây là phản ví dụ: Tham số của bài toán là n = 3; b = 19. Đồ vật 1 2 3 Giá trị 20 16 8 -> giátrị lớnnhưngtrọnglượngcũngrấtlớn Trọng lượng 14 6 10 Thuật toán sẽ lựa chọn đồ vật 1 với tổng giá trị là 20, trong khi lời giải tối ưu của bài toán là lựa chọn (đồ vật 2, đồ vật 3 ) với tổng giá trị là 24. Greedy2: Sắp xếp đồ vật không giảm của trọng lượng. Lần lượt chất các đồ vật vào túi theo thứ tự đã sắp xếp. Thuật toán tham lam này cũng không cho kết quả tối ưu. Sau đây là phản ví dụ Tham số của bài toán là n = 3; b = 11 41/129
44. Đồ vật 1 2 3 Giá trị 10 16 28 ->Đồvậtnhẹnhưnggiá tiềncũngrấtnhẹ Trọng lượng 5 6 10 Thuật toán sẽ lựa chọn (đồ vật 1, đồ vật 2) với tổng giá trị là 26, trong khi lời giải tối ưu của bài toán là (đồ vật 3) với tổng giá trị là 28. Greedy3: Sắp xếp các đồ vật theo thứ tự không tăng của giá trị một đơn vị trọng 1lượng (ci/wi). Lần lượt xét Tuy nhiên Greedy3 không cho lời giải tối ưu. Sau đây là phản ví dụ của bài toán Tham số của bài toán : n= 2; b≥ 2. Khi đó thuật toán chỉ lựa chọn được đồ vật 1 với tổng giá trị là 10, trong khi lời giải tối ưu của bài toán lựa chọn đồ vật 2 với tổng giá trị là 10b-1 ( ≥ 10.2-1 = 19 > 10). Greedy4:Gọi Ij là lời giải thu được theo thuật toán Greedyj (j = 1, 2, 3). Gọi Định lý : Lời giải I4 thoả mãn bất đẳng thức Trong đó f* là giá trị tối u của bài toán. 42/129
45. Phương pháp “chia để trị” Sơ đồ chung của phương pháp Bài toán ví dụ Giả sử ta có thuật toán α để giải bài toán kích thước dữ liệu với thời gian bị chặn bởi cn2. Xét thuật toánβđểgiải chính bài toán đó bằng cách • Bước 1 : Chia bài toán cần giải ra thành 3 bài toán con với kích thước n/2 • Bước 2 : Giải 3 bài toán con bằng thuật toán α • Bước3 : Tổng hợplời giải của 3 bài toán con để thu được lời giải của bài toán Giả sử bước 3 đượcthực hiện với thời gian d.n Gọi Tm(n) : thời gian của thuật toánα Tp(n): thời gian của thuật toán β Khi đó Tm(n) = cn2 Tp(n) =3 Tm(n) +dn= cn2 + dn Nên nếu dn<cn2/4 (d<cn/4) thì thuật toán β nhanh hơn α . Điều này luôn đúng với nđủ lớn. Tuy nhiên ta thấy thuật toán β mới chỉ thay đổi được nhân tử hằng số chưa thay đổiđược bậc nhưng cũng hiệu quả khi n lớn. Do đó, nếu ta tiếp tục chia bài toán con nhỏ nữa tới n0≤ 4 d/c ta sẽ thu được một thuật toán hiệu quả hơn. Xét thuật toán sau : ProcedureGamma(n)(* n kích thước bài toán*) Begin If n ≤ n0 Then Giải bài toán bằng thuật toán α Else 43/129
46. Begin End End; 1. Chia bài toán thành ba bài toán con kích thước n/2 2. Giải mỗi bài toán con bằng thuật toán Gamma 3. Tổng hợp lời giải của các bài toán con Gọi T (n) là thời gian tính của thuật toán trên, và thời gian tổng hợp lời giải của các bài toán con là? (n) thì Theo định lý thợ ta có Thuật toán thu được có thời gian tính là tốt hơn cả thuật toánαvà thuật toánβ .Hiệu quả thu được trong thuật toán?có được là nhờ ta đã triệt để khai thác hiệu quả việcsử dụng thuật toán β . Để có được mô tả chi tiết thuật toán chiađể trị chúng ta cần phải xác định : 1. Kích thước tới hạn n0 (Bài toán có kích thước nhỏ hơn n0 sẽ không cần chia nhỏ) 2. Kích thước của mỗi bài toán con trong cách chia 3. Số lượng các bài toán con như vậy 4. Thuật toán tổng hợp lời giải của các bài toán con Các phần xác định trong 2 và 3 phụ thuộc vào 4. Chia như thế nào để khi tổng hợp có hiệu quả (thường là tuyến tính) Sơ đồ thuật toán tổng quát Procedure D_and_C(n) Begin If n ( n0 Then Giải bài toán một cách trực tiếp 44/129
47. Else 1. Chia bài toán thành r bài toán con kích thước n/k 2. For (Mỗi bài toán trong r bài toán con) Do D_and_C(n) End; 1. Tổng hợp lời giải của r bài toán con đểthu được lời giải của bài toán gốc Thuật toán tìm kiếm nhị phân Bài toán : Cho mảng x[1 n] được sắp xếp theo thứ tự không giảm và y. Tìm i sao cho x[i] = y. (Giả thiết i tồn tại). Phân tích giải thuật: Số y cho trước • Hoặc là bằng phần tử nằm ở vị trí giữa mảng x • Hoặc là nằm ở nửa bên trái (y < phần tử ở giữa mảng x ) • Hoặc là nằm ở nửa bên phải (y < phần tử ở giữa mảng x ) Từ nhận xét đó ta có giải thuật sau Function Bsearch(x[1 n],Start,Finish) Begin Middle := (Start + Finish)/2; If (y = x[Middle]) then return middle Else If ( y < x[Middle] then return Bsearch(x,Start,Middle-1) Else End; Return Bsearch (x,Middle+1,Finish) Phân tích hiệu quả thuật toán : T(n) Theo định lý thợ ta có 45/129
48. Phép nhân các số nguyên lớn Xét lại vấn đề nhân các số nguyên lớn. Nhớ lại rằng thuật toán cổ điển mà phần lớn chúng ta đều được học ở trường đòi hỏi thời gian tính là Ρ(n2) để nhân các số nguyên m có n chữ số. Chúng ta cũng quen với thuật toán này đến mức có thể còn chẳng bao giờ thắc mắc về tính tối ưu của nó. Liệu chúng ta có thể làm được tốt hơn không? . Một thuật toán được bàn đến gọi là kỹ thuật Chia để trị bao gồm việc rút gọn phép nhân hai số nguyên n chữ số xuống thành bốn phép nhân hai số nguyên n/2 chữ số. -Việc nhân 2 số nguyên có 1 chữ số có thể thực hiện một cách trực tiếp (neo đệ qui), thời gian thực hiện làO(1) -Chia : n >1 thì tích củahai số nguyên có n chữ số có thể biểu diễn qua tích 4 số nguyên có n/2 chữ số,thời gian thực hiện là 4. T ( n /2) ( trong đó T(n) là thời gian thực hiện nhân hai số nguyên cón chữ số ). 46/129
49. -Tổng hợp : Cộng và dịch phải, khi đóthời gian thực hiện sẽ là?( n ) Khi đó ta có thời gian thực hiệnthuật toán là 2 Theo định lý thợ ta có độ phức tạp của thuật toán là Tn = (On ) .Như vậy thuật toán thu được cũng không gặt hái được bất kỳ cải thiện nào so với thuật toán nhân cổ điển mặc dù chúng ta đã khôn ngoan hơn. Để vượt được thuậttoán cổ điển và như vậy mới hoàn toàn thấy rõ được công dụng của phép Chia để trị, chúng ta phải tìm cách rút gọn phép nhân nguyên thuỷ không phải về bốn mà làbaphép nhân hai nửa. Chúng ta minh hoạ quá trình này bằng việc nhân 981 với 1234. Trước tiên chúng ta điền thêm vào toán hạng ngắn hơn một số không vô nghĩa để làm cho haitoán hạng có cùng độ dài, vậy là 981 trở thành 0981. Sau đó tách từng toán hạngthành hai nửa: 0981 cho ra w = 09 và x = 81, còn 1234 thành y = 12 và z= 34.Lưu ý rằng 981 = 102w + x và 1234 = 102y + z. Do đó, tíchcần tìm có thể tính được là 981 x 1234 =(102w + x)( 102y + z) = 104wy + 102(wz + xy) +xz = 1080000 + 127800 + 2754 =1210554 Thủ tục trên đến bốn phép nhân hai nửa:wy, wz, xy và xz. Để ý điểm mấu chốt ở đây là thực ra thì không cần tính cả wz lẫn xy, mà là tổng của hai số hạng này. Liệu có thể thu được wz + xy với chi phí của một phép nhân mà thôi hay không? Điều này có vẻ nhưkhông thể được cho đến khi chúngta nhớ ra rằngmình cũng cần những giá trị wy và xz để đưa vào công thức trên. Lưu ý về điểmnày, hãy xét tích: r = (w + x)(y+z) = wy +(wz + xy) + xz Chỉ sau một phép nhân, chúng ta thu đượctổng của tất cả ba số hạng cần thiết để tính được tích mình mong muốn. Điều này gợi ý một cách tiến hành như sau: p = wy = 09 * 12 =108 q = xz = 81 * 34 =2754 r = (w + x)(y+z) = 90 *46 = 4140 và cuối cùng 981 x 1234 =104p + 102(r – p – q) + q = 1080000 + 127800 + 2754 =1210554. 47/129
50. Như vậy tích của 981 và 1234 có thể rútgọn về ba phép nhân của hai số có hai chữ số (09 12, 81 34 và 90 46) cùng với một số nào đó phép dịch chuyển (nhân với luỹ thừa của 10),phép cộng và phép trừ. Chắc chắn là số các phép cộng – coi phéptrừ như là phép cộng – có nhiều hơn so với thuật toán Chia để trị nguyên thuỷ ởphần trước. Vậy thì có đáng để thực hiện bốn phép cộng nhiều hơn để tiết kiệmmột phép nhân hay không? Câu trả lời là không nếu chúng ta đang nhân số nhỏ như những số trong ví dụ này. Tuy nhiên sẽ là đáng giá nếu các số cần được nhân vớinhau đủ lớn và chúng càng lớn thì lại càng đáng làm như vậy. Khi các số hạng đủlớn, thời gian cần cho các phép cộng và dịch chuyển trở thành bỏ qua được so vớithời gian cần cho chỉ một phép nhân. Như vậy là có lý do để kỳ vọng rằng rút gọn bốn phép nhân về còn ba sẽ giúp chúng ta cắt giảm được 25% thời gian tính toán đòi hỏi cho việc nhân các số lớn. Như chúng ta sẽ thấy, sự tiết kiệm của mình sẽtốt hơn một cách đáng kể. Để giúp chúng ta hiểu thấu đượcnhững gì mình đạt được, hãy giả thiết rằng có một cài đặt của thuật toán nhân cổđiển đòi hỏi thời gian h(n) = cn2để nhân hai số có n chữ số, với hằng số c phụ thuộc vàocài đặt đó. (ở đây đã có sự đơn giản hoá vì trên thực tế thì thời gian đòi hỏicòn có dạng phức tạp hơn, chẳng hạn như cn2+ bn + a). Tương tự, chog(n) là thời gian mà thuật toán Chia để trị cần để nhân haisố n chữ số,không tính thời gian cần thiết để thực hiện ba phép nhân hai nửa. Nói cách khác,g(n) là thời gian cần thiết cho các phép cộng, dịch chuyển và các phép tính phụthêm khác. Dễ dàng cài đặt các phép tính này sao cho g(n)∈Ρ(n).Hãy tạm thời bỏ qua điều gì sẽ xảy ra nếu n lẻ và nếu các số hạng không có cùngđộ dài. Nếu từng trong số ba phép nhân hai nửađược thực hiện bằng thuật toán cổ điển, thời gian cần thiết để nhân hai số có nchữ số là: 3h(n/2) + g(n) =3c(n/2)2+ g(n) = cn2+ g(n)= h(n) +g(n). Vì h(n) rất nhỏ xo với Ρ(n2)và g(n) rất nhỏ xo với Ρ(n),số hạng g(n) là bỏ qua được so với h(n)khi n đủ lớn, có nghĩa là chúng ta tăng được tốc độ lên khoảng 25% so với thuậttoán cổ điển như đã mong đợi. Mặc dù sự cải thiện này là không thể xem thường được nhưng chúng ta vẫn không làm được thay đổi bậc của thời gian cần thiết:thuật toán mới vẫn cần thời gian tính bậc hai. Để có thể làm được tốt hơn thế, chúng tatrở lại với câu hỏi đặt ra ở đoạn mở đầu: các bài toán con cần được giải như thế nào? Nếu chúng nhỏ thôi thì thuật toán cổ điển có vẫn còn là cách làm tốt nhất. Tuy nhiên, khi những bài toán con cũng đủ lớn, chẳng lẽ sử dụng thuật toánmới của chúng ta một cách đệ quy cũng không hơn gì hay sao? Ý tưởng này tương tựnhư hưởng lợi nhuận từ một tài khoản ngân hàng có gộp vốn lẫnlãi! Nếu chúng talàm như vậy sẽ thu được một thuật toán có thể nhân hai số n chữ số trong mộtthời gian t(n) = 3t(n/2) + g(n) khi nchẵn và đủ lớn. Điều này cũng giống như phép 48/129
51. truy toán (đệ quy) ; giải ra tathu được t(n)∈O(nlg3) | n là luỹ thừa của 2. Chúng ta cần phải bằng lòng với lờighi chú tiệm cận có điều kiện vì chưa đề cập đến câu hỏi là nhân các số có độdài là lẻ như thế nào. Vì lg3 = 1.585 nhỏ hơn 2, thuật toán này có thể nhân hai số nguyên lớn nhanh hơn rất nhiều so với thuật toán nhân cổ điểnvà n càng lớn thì sự cải thiện này càng đáng giá. Mộ cài đặt tốt có thể khôngsử dụng cơ số 10, mà sử dụng cơ số lớn nhất để với cơ số đó phần cứng cho phép nhân trực tiếp hai “chữ số” với nhau. Một nhân tố quan trọng trong hiệu suất thực tế của cách tiếp cận phép nhân này và của bất kỳthuật toán Chia để trị nào là biết khi nào cần dừng việc phân chia các bài toánvà thay vào đó sử dụng thuật toán cổ điển. Mặc dù cách tiếp cận Chia để trị trởnên có ích khi bài toán cần giải đủ lớn, trên thực tế nó có thể chậm hơn so vớithuật toán cổ điển đối với những bài toán quá nhỏ. Do đó thuật toánChia để trị phải tránh việc thực hiện đệ quy khi kích thước của các bài toán con không phù hợp nữa. Chúng ta sẽ trở lại vấn đề này ở phần sau. Để đơn giản, một số vấn đề quan trọng đến nay đã bị bỏ qua. Làm thế nào để chúng ta giải quyết được những số có độ dài lẻ?Mặc dù cả hai nửa của số nhân và số bị nhân đều có kích thước n/2, có thể xảy ratrường hợp tổng của chúng bị tràn và có kích thước vượt quá 1. Do đó sẽ không hoàn toàn chính xác khi nói rằng r = (w+x)(y+z) bao hàm phép nhân hai nửa. Điềunày ảnh hưởng tới việc phân tích thời gian chạy như thế nào? Làm thế nào để nhânhai số có kích thước khác nhau? Còn những phép tính số học nào khác với phépnhân mà ta có thể xử lý hiệu quả hơn so với dùng thuật toán cổ điển? Những số có độ dài lẻ được nhân dễ dàng bằng cách tách chúng càng gần ở giữa càng tốt: một số có n chữ số được táchthành một số có |n/2| chữ số và một số có |n/2| chữ số. Câu hỏi thứ hai còn khắtkhe hơn. Xét nhân 5678 với 6789. Thuật toán của chúng ta tách các số hạng thànhw = 56, x = 78, y = 67 và z = 89. Ba phép nhân hai nửa cần thực hiện là: p = wy = 56.67 q = xz = 78.89 và r = (w+x)(y+z) =134.156 Phép nhân thứ ba bao gồm những số 3 chữ số, do vậy nó không thực sự là một nửa so với phép nhân nguyên thuỷ của các sốcó 4 chữ số. Tuy nhiên kích thước của w+x và y+z không thể vượt quá 1 +|n/2|. Để đơn giản hoá việc phân tích, cho t(n)là thời gian mà thuật toán này thực hiện trong tìn huống xấu nhất để nhân haisố có kích thước tối đa là n (thay vì chính xác bằng n). 49/129
52. Theo định nghĩa thì t(n) là một hàm không giảm.Khi n đủ lớn thuật toán của chúng ta rút gọn phép nhân hai số có kích thước tối đa n đó về ba phép nhân nhỏ hơn p = wy, q = xz và r = (w+x)(y+z) với kích thước tối đa tương ứng là |n/2|, |n/2| và 1 + |n/2|, thêm vào đó là những thao tác đơn giản chiếmthời gian là O(n). Do đó ở đây tồn tại hằng số dương c saocho: t(n) = t(|n/2|) +t(|n/2|) + t(1+|n/2|) + cn với mọi n đủ lớn. Điều này chính xác là phép đệ quy mà chúng ta đã nghiên cứu cho kết quả giờ đây đã trở nên quen thuộc là t(n)∈O( nlg 3). Do vậy luôn luôn có thể nhân các số n chữ số với thờigian O(nlg3). Phân tích tình huống tồi nhất của thuật toán này chỉ rarằng trên thực tế t(n) Ρ(nlg3),nhưng điều này không được quan tâm lắm vì còn có những thuật toán nhân nhanh hơn. Quay lại với câu hỏi nhân các số có kích thước khác nhau, giả sử u và v là những số nguyên có kích thước tương ứng là mvà n. Nếu m và n nằm trong khoảng đến hai lần của nhau, tốt nhất là điền vào sốhạng nhỏ hơn những số 0 vô nghĩa để làm cho nó có cùng độ dài như số hạng kia,như chúng ta đã làm khi nhân 981 với 1234. Tuy nhiên cách tiếp cận này khôngđược khuyến khích khi một số hạng lớn hơn số hạng kia rất nhiều. Thậm chí nó có thể tồi hơn là dùng thuật toán nhân cổđiển! Không làm mất đi tính tổng quát, giả sử rằng m≥n.Thuật toán Chia để trị sử dụng điền số và thuật toán cổ điển có thời gian tươngứng là Ρ(nlg3) và Ρ(mn) để tính các tích u và v. Xét thấy rằng hằng số Nn của biểu thức trước có vẻ lớnhơn của biểu thức sau, chúng ta thấy rằng Chia để trị sử dụng điền số là chậmhơn thuật toán cổ điển khi m = nlg(3/2)và như vậy trường hợp đặc biệt khi m = n.Mặc dù vậy rất dễ dàng kết hợp cảhai thuật toán để thu được một thuật toán thực sự tốt hơn. ý tưởng là cắt lát sốhạng dài hơn v thành những đoạn có kích thước m và sử dụng thuật toán Chia đểtrị để nhân u với từng đoạn của v sao cho thuật toán Chia để trị được dùng đểnhân những cặp số hạng có cùng kích thước. Tích cuối cùng của u và v sau đó thuđược dễ dàng bằng các phép cộng và dịch chuyển đơn giản. Thời gian chạy tổngcộng chủ yếu được dùng để thực hiện |n/m| phép nhân các số m chữ số. Vì mỗi phépnhân nhỏ hơn này chiếm thời gian Ρ(mlg3) và vì |n/m|∈Ρ(n/m) ,thời gian chạy tổng cộng để nhân một số n chữ số với một số m chữ số làΡ(nmlg(3/2))khi m = n. Sau đây là mô hình cải tiến thuật toán nhân số nguyên lớn Cải tiến để còn lại 3 phép nhân : Từ đó ta đưa ra thuật toán nhân số nguyên lớn là Function Karatsuba(x,y,n); Begin If n = 1 then Return x[0]*y[0] Else 50/129
53. Begin a := x[n-1] . x[n/2];b := x[n/2-1] . . .x[0]; c := y[n-1]. y[n/2];d := y[n/2-1] . . .y[0]; U :=Karatsuba(a,c,n/2); V :=Karasuba(b,d,n/2); W :=Karatsuba(a+b,c+d,n/2); Return U*10n+ (W-U-V)*10n/2+ V end End; Phân tích hiệu quả thuật toán : T ( n ) T (1) =1 T ( n ) = 3 T ( n /2) + cn =>Theo định lý thợ T( n ) =Ρ(nlog 3) Một số giải thuật sắp xếp Cho T[1 n] là một mảng n phần tử. Vấn đề đặt ra là sắp xếp các phần tử này theo thứ tự tăng. Chúng ta đã có thể giải quyết vấn đề này bằng các phương phápselection sort hay insertion sort hoặc là heapsort Như chúng ta đã biết thời gian dùng selection sort hay insertion sort để sắp xếp mảng T trong cả hai trường hợp: xấu nhất và trung bình đều vào cỡ n2. Còn heapsort vào khoảng nlogn. Có một số giải thuật đặc biệt cho bài toán này theo mô hình chia để trị đó làmergesortvà quicksort, chúng ta sẽ lần lượt đi nghiên cứu chúng. MergeSort Chia để trị tiếp cận tới bài toán này bằng việc tách mảng T thành hai phần màkích thước của chúng sai khác nhau càng ít càng tốt, sắp xếp các phần này bằng cách gọi đệ qui và sau đó trộn chúng lại (chú ý duy trì tính thứ tự). Để làm được điều này chúng ta cần một giải thuật hiệu quả cho việc trộn hai mảng đã được sắp U và V thành một mảng mới T mà kích thước của mảng T bằng tổng kích thước của hai mảng U và V. Vấn đề này có thể thực hiện tốt hơn nếu ta thêm vào các ô nhớ có sẵn ở cuối của mảng U và V các giá trị đứng canh (giá trị lớn hơn tất cả các giá trị trong U và V) . 51/129
54. Procedure merge(U[1 m+1],V[1 n+1],Ta[1 m+n]); (*Trộn 2 mảng U[1 m+1] và V[1 n+1] thành mảng T[1 m+n]); U[m+1],V[n+1] được dùng để chứa các giá trị cầm canh*) Begin i:=1;j:=1; U[m+1]:= ∞ ; V[n+1]:= ∞ ; For k:=1 to n+m do If U[i]<V[j] then Begin T[k]:=U[i]; i:=i+1; Else End Begin T[k]:=V[j]; j:=j+1; End; End; Giải thuật sắp xếp trộn sau đây có thể tốt hơn nếu các mảng U và V là các biến toàn cục và xem việc sắp xếp chèn Insert(T) như là giải thuật cơ bản Procedure mergesort(T[1 n]); Begin If n đủ nhỏ then Insert(T) Else 52/129
55. Begin Array U[1 1+],V[1 1+; U[1 ]:=T[1 ]; V[1 ]:=T[1+ n]; mergesort(U[1 ]); End; mergesort(V[1 ]); merge(U,V,T); Hình sau chỉ ra các bước của mergesort. Giải thuật sắp xếp này minh hoạ tất cả các khía cạnh của chia để trị. Khi số lượng các phần tử cần sắp là nhỏ thì ta thường sử dụng các giải thuật sắp xếp đơn giản. Khi số phần tử đủ lớn thì ta chia mảng ra 2 phần, tiếp đến trị từng phần một và cuối cùng là kết hợp các lời giải. Giả sử t(n) là thời gian cần thiết để giải thuật này sắp xếp một mảng n phần tử. Việc tách T thành U và V là tuyến tính. Ta cũng dễ thấy merge(U,V,T) cũng tuyến tính. Do vậy: t(n)=t([n/2]) + t([n/2]) + g(n) trong đó g( n ) = O( n ) 53/129
56. hay t( n )=2t( n /2)+g( n ) Theo định lý chủ Tacó: l=2; b=2và k=1 Nên t(n)= Ρ (nlogn), vì bk =l Như vậy hiệu quả của mergesort tương tự heapsort. Trong thực tế sắp xếp trộn có thể nhanh hơn heapsort một ít nhưng nó cần nhiều hơn bộ nhớ cho các mảng trung gian U và V. Ta nhớ lại heapsort có thể sắp xếp tại chỗ (in-place), và cảm giác nó chỉ sử dụng một ít biến phụ mà thôi. Theo lý thuyết mergesort cũng có thể làm được như vậy tuy nhiên giá thành có tăng một chút ít. Khi giải bài toán theo thuật giải chia để trị chúng ta hết sức chú ý đến việc tạo ra các bài toán con, nếu không nó có thể tạo ra những thảm hại mà không thể lường trước được. Giải thuật sau đây minh hoạ tính chất quan trọng này khi kích thước bài toán con là hỗn độn: Procedure badmergesort(T[1 n]); Begin If n đủ nhỏ then Insert(T) Else Begin Array U[1 n-1, V[1 2]; U[1 n-1]:= T[1 n-1]; V[1]:= T[n]; badmergesort(U[1 n-1]); badergesort(V[1 1]); merge(U,V,T); End; ˆ Gọi t (n) là thời gian cần để sắp n phần tử với giải thuật badmergesort trên. Rõ ràng là: ˆ ˆ ˆ ˆ t (n) = t (n-1) + t (1) + g (n), trong đó (n) ∈ Ρ(n). Sự đệ qui này tạo ra (n) ∈ Ρ(n2), như vậy việc quên cân bằng kích thước của bài toán con đã ảnh hưởng đáng kể đến hiệu quả của việc sử dụng giải thuật chia đểtrị. 54/129
57. Quicksort Giải thuật này được phát minh bởi Hoare, nó thường được hiểu như là tên gọi của nó - sắp xếp nhanh, hơn nữa nó cũng dựa theo nguyên tắc chia để trị. Không giống như mergesort nó quan tâm đến việc giải các bài toán con hơn là sự kết hợp giữa các lời giải của chúng. Bước đầu tiên của giải thuật này là chọn 1 vật trung tâm (pivot) từ các phần tử của mảng cần sắp. Tiếp đến vật trung tâm sẽ ngăn mảng này ra 2 phần: các phần tử lớn hơn vật trung tâm thì được chuyển về bên phải nó, ngược lại thì chuyển về bên trái. Sau đó mỗi phần của mảng được sắp xếp độc lập bằng cách gọi đệ qui giải thuật này. Cuối cùng mảng sẽ được sắp xếp xong. Để cân bằng kích thước của 2 mảng này ta có thể sử dụng phần tử ở giữa (median) như là vật trung tâm . Đáng tiếc là việc tìm phần ở giữa cũng mất 1 thời gian đáng kể. Để giải quyêt điều đó đơn giNn là chúng ta sử dụng 1 phần tử tuỳ ý trong mảng cần sắp như là vậttrung tâm và hi vọng nó làtốt nhất có thể. Việc thiết kế giải thuật ngăn cách mảng bằng vật trung tâm với thời gian tuyến tính không phải là sự thách đố (có thể làm được). Tuy nhiên điều đó là cần thiết để so sánh với các giải thuật sắp xếp khác như là heapsort. Vấn đề đặt ra là mảng con T[i j] cần được ngăn bởi vật trung tâm p=T[i]. Một cách làm có thể chấp nhận được là: Duyệt qua từng phần tử của của nó chỉ một lần nhưng bắt đầu từ hai phía (đầu và cuối mảng). Khi đó khởi tạo k=i; l=j+1, k tăng dần cho đến khi T[k] > p, l giảm dần cho đến khi T[l] ( l. Tiếp đến hoán vị T[k] và T[l]. Quá trình này tiếp tục cho đến khi k ( l. Cuối cùng đổi chổ T[i] và T[l] cho nhau và lúc này ta xác định đúng vị trí của phần tử trung tâm. Procedure Pivot(T[i j], var l) (* Hoán vị các phần tử trong mảng T[i j] và cuối cùng trả về giá trị l (1≤l≤j) sao cho T[l]=p ,T[k]≤p với mọi k (i≤k p với mọi k (l p) or (k≥j); repeat l:=l-1; until (T[l] < p); while (k<l) do begin End; 55/129
58. Swap(T[k],T[l]); (* Đổi chỗ T[k] và T[l] *) repeat k:=k+1; until (T[k] > p); repeat l:=l-1; until (T[l]≤p); Swap(T[i],T[l]); end; Sau đây là giải thuật sắp xếp với tên gọi là Quicksort dùng để sắp xếp mảng T[1 n]: Procedure Quicksort(T[i j]); (* Sắp xếp theo thứ tự không giảm *) Begin if n đủ nhỏ then Insert(T[i j]) else begin pivot(T[i j],l); quicksort(T[i l-1]; quicksort(T[l+1,j]; End; end; Hình vẽ sau cho thấy sự làm việc của pivot và quicksort. 56/129
59. Quicksort sẽ không hiệu quả nếu sử dụng việc gọi đệ quy của các bài toán con mà không chú ý đến sự cân bằng kích thước của chúng. Tình huống xấu nhất là khi T đã được sắp trước mà gọi quicksort và thời gian dùng quicksort để sắp là O( n 2). Gọi t( n ) là thời gian trung bình dùng quicksort để sắp mảngnphần tử T[1 n ].llà 57/129
60. giá trị trả về khi gọi pivot(T[1 n],l). Theo pivot() thì l nằm giữa 1 ( n và xác suất là 1/n. Thời gian để tìm vật trung tâm g(n) là tuyến tính. Thời gian để dùng đệ qui để sắp xếp hai mảng con kích thước (l-1) và (n-l) tương ứng là t(n-1) và t(n-l). Như vậy với n đủ lớn ta có: Hay rõ ràng hơn ta chọnn 0 là giá trị đủ lớn để sử dụng công thức trên. Nghĩa là nếu n n n 0. Với công thức như trên quả là khó phân tích độ phức tạp. Ta dự đoán nó tương tự mergesort và hi vọng nó là như vậy tức là vào cỡ O(nlogn). Thật vậy ta có định lý sau: Định lý: Quicksort cần nlogn thời gian để sắp xếp n phần tử trong trường hợp trung bình. Chứng minh Gọi t( n ) là thời gian cần thiết để sắp n phần tử trong trường hợp trung bình. a,n 0 là các hằng số giống như công thức 2.7.1 Ta chứng minh t( n ) = cnlogn với mọin≥ 2. với c là hằng số. Dùng phương pháp qui nạp để chứng minh: - Với mọinnguyên dương: (2 ≤n≤n) Dễ thấy t( n ) ≤ cnlogn - Bước qui nạp Ta có 58/129
61. Giả thiết rằng: t(k) ≤ cklogk với mọi 2 ≤ k < n Ta chỉ ra c sao cho t( n ) ≤ cnlogn Lấy a = t(0) +t(1) Theo giả thiết qui nạp : t(k) = cklogk t( n ) = cnlogn với điều kiện là , 59/129
62. hay c ≥ 2d + 4a/n2 Từ đó chúng ta chỉ xem xét với những n > n0 thoả mãn: Hay ta có t( n ) ≤ cnlogn với mọin≥ 2, và như vậy định lý được chứng minh. Như vậy quicksort có thể sắp xếp 1 mảng n phần tử khác nhau trong trường hợp trung bình là O( nlogn ). Câu hỏi đặt ra là liệu có thể sửa đổi quicksort để nó sắp xếp với thời gian O( nlogn ) trong trương hợp xấu nhất hay không. Câu trả lời là có thể!!!. Tuy nhiên nếu việc tìm phần tử ở giữa của T[i j] là tuyến tính và lấy nó làm vật trung tâm (pivot) (Finding the median) thì quicksort cũng cần O( n 2) để sắp xếpnphần tử trong trường hợp xấu nhất (khi tất cả các phần tử của mảng cần sắp là bằng nhau). Giải thuật sau đây có thể khắc phục được vấn đề này: Procedure Pivotbis(T[1 n],p; var k,l); p - là vật trung tâm T[1 n] chia ra 3 phần: T[1 k]: gồm các phần tử p k,l là các giá trị trả về của Pivotbis(T[i j],T[i],k,l) Sau khi ngăn cách mảng T[1 n] bằng việc gọi Pivotbis(T[i j],T[i],k,l), phần còn lại có thể gọi đệ qui quicksort cho T[1 k] và T[l+1 n]. Với cách sửa đổi này việc sắp mảng trên là tuyến tính. Thú vị hơn là quicksort có thể sắp với thời gian là O( nlogn ) trong trường hợp xấu nhất nếu phần tử ở giữa chọn làm vật trung tâm là tuyến tính. Tuy nhiên chúng ta đưa ra vấn đề này chỉ có tính lý thuyết 60/129
63. bởi vì để cải tiến nó thì sẽ tăng sự phức tạp của giải thuật này ở các hằng số Nn (hide constant), thà vậy thì dùng heapsort còn hơn!. Bài toán nhân ma trận Bài toán : Cho hai ma trận A, B với kích thước n*n, ta có ma trận C chứa kết quả của phép nhân hai ma trận A và B. Thuật toán nhân ma trận cổ điển như công thức dưới đây: phân tích thuật toán Với mảng một chiều (kích thước n phần tử), ma trận C được tính trong thời gian O(n), giả sử rằng phép cộng vô hướng và phép nhân là các phép tính cơ bản (có thời gian tính là hằng số). Với mảng hai chiểu (kích thước n*n) thì thời gian để tính phép nhân ma trận AB là O( n 3) Đến cuối những năm 1960, Strassen đưa ra một giải pháp cải tiến thuật toán trên, nó có tính đột phá trong lịch sử của thuật toán chia để trị, thậm chí gây ngạc nhiên không kém thuật toán nhân số nguyên lớn được phát minh ở thập kỷ trước. ý tưởng cơ bản của thuật toán Strassen cũng tương tự như thuật toán trên. Đầu tiên ta chứng minh rằng phép nhân hai ma trận với kích thước 2*2 có thể thực hiện được bằng cách sử dụng ít hơn 8 phép nhân vô hướng như thuật toán cổ điển bắt buộc. Ta xét phép nhân hai ma trận A, B như sau: Ta có các biểu thức sau, mỗi biểu thức chỉ có một phép nhân: 61/129
64. Ta có ma trận C là tích của hai ma trận A và B là: Do đó ta thấy rằng, có thể nhân hai ma trận kích thước 2*2 bằng cách chỉ sử dụng 7 phép nhân vô hướng. Nhìn thoáng qua thấy rằng thuật toán này không có gì thú vị lắm, nó sử dụng một số lượng lớn các phép cộng và phép trừ, trong khi thuật toán cổ điển chỉ cần 4 phép cộng. Bây giờ nếu ta thay thế các phần tử trong A và B bằng các ma trận có kích thước n*n, thì để thực hiện phép nhân hai ma trận A và B ta phải thực hiện 7 phép nhân hai ma trận với kích thước n*n và cũng từng đấy phép cộng, trừ của hai ma trận n*n. Nếu ta làm việc với các ma trận lớn thì phép cộng sẽ nhanh hơn rất nhiều so với phép nhân, việc tiết kiệm 1 phép nhân sẽ lợi hơn nhiều so với việc thực hiện các phép cộng cơ bản. Gọi t(n) là thời gian cần thiết để nhân hai ma trận kích thước n*n bằng cách sử dụng đệ quy hai phương trình 2.3.1 và 2.3.2. Giả sử rằng n là luỹ thừa bậc 2. Do thời gian để tình phép cộng, trừ ma trận là Do đó ta thấy rằng, có thể nhân hai ma trận kích thước 2*2 bằng cách chỉ sử dụng 7 phép nhân vô hướng. Nhìn thoáng qua thấy rằng thuật toán này không có gì thú vị lắm, nó sử dụng một số lượng lớn các phép cộng và phép trừ, trong khi thuật toán cổ điển chỉ cần 4 phép cộng. Bây giờ nếu ta thay thế các phần tử trong A và B bằng các ma trận có kích thước n*n, thì để thực hiện phép nhân hai ma trận A và B ta phải thực hiện 7 phép nhân hai ma trận với kích thước n*n và cũng từng đấy phép cộng, trừ của hai ma trận n*n. Nếu ta làm việc với các ma trận lớn thì phép cộng sẽ nhanh hơn rất nhiều so với phép nhân, việc tiết kiệm 1 phép nhân sẽ lợi hơn nhiều so với việc thực hiện các phép cộng cơ bản. 62/129
65. Gọi t(n) là thời gian cần thiết để nhân hai ma trận kích thước n*n bằng cách sử dụng đệ quy hai phương trình 2.3.1 và 2.3.2. Giả sử rằng n là luỹ thừa bậc 2. Do thời gian để tình phép cộng, trừ ma trận là, do đót ( n ) = 7 t ( n /2) +dn 2, điều này là một ví dụ minh hoạ cho chúng ta trong việc phân tích tổng quát thuật toán chia để trị. áp dụng dụng định lý thợ ta có . Đối với các trường hợp ma trận vuông nhưng kích thước không phải là luỹ thừa bậc 2 thì giải quyết vấn đề bằng cách thêm các dòng và các cột sao cho kích thước ma trận mới gấp đôi kích thước ma trận cũ và gán giá trị cho các phần tử mới thêm là 0. Điều này không làm ảnh hưởng đến thời gian tính toán. Do lg7<2,81 nên có thể thực hiện phép nhân hai ma trận kích thước n*n trong thời gian với điều kiện các phép tính vô hướng là phép tính cơ bản. Cùng với phát minh của Strassen, có một số nhà nghiên cứu cố gắng tìm kiếm thuật toán để xác định được hằng số ω, khi đó độ phức tạp tính toán phép nhân hai ma trận kích thước n*n là . Để thực hiện được điều này, việc đầu tiên phải tiến hành là nhân hai ma trận kích thước 2*2 với 6 phép nhân cơ bản. Nhưng vào năm 1971 Hopcroft và Kerr đã chứng minh điều này là không thể vì phép nhân hai ma trận không có tính chất giao hoán. Việc tiếp theo phải thực hiện là tìm cách nào để nhân hai ma trận 3*3 với nhiều nhất chỉ 21 phép nhân cơ bản. Nếu thực hiện được việc này có thể sử dụng thuật toán này để suy ra thuật toán đệ quy nhân hai ma trận n*n với thời gian , nhanh hơn thuật toán của Strassen vì . Không may mắn là điều này không thể thực hiện. Trong suốt một thập kỷ trước khi Pan phát hiện ra cách để nhân hai ma trân kích thước 70*70 với 143640 phép nhân cơ bản – so sánh với 343000 phép nhân nếu sử dụng thuật toán cổ điển và quả thực là bé hơn một chút so với lg7. Phát hiện này được gọi là cuộc chiến tranh của số thập phân (decimal war). Nhiều thuật toán, mà trong đó hiệu suất tiệm cận cao, được tìm ra sau đó. Ví dụ như cuối năm 1979, phép nhân ma trận có thời gian tính toán là . Hãy tưởng tượng rằng, ngay sau đó tháng 1 năm 1980 thời gian tính của phép nhân ma trận là . Biểu thức tiệm cận thời gian tính toán tồi nhất của thuật toán nhân ma trận kích thước n*n được Coppersmith và Winograd phát minh ra năm 1986 là . Tại vì các hằng số liên quan bị Nn nên không một thuật toán nào được tìm ra sau thuật toán của Strassen được nghiên cứu và sử dụng. Giới thiệu về khoa học mật mã Trong phần trước chúng ta đã thấy việc rút gọn số mũ trong số các phép nhân cần thiết để tínhankhông tiết kiệm được một cách đáng kể thời gian tính. Tuy nhiên, có những ứng dụng trong đó các phép nhân được coi là có chi phí ngang nhau. Đó là trường hợp khi chúng ta quan tâm đến số học đồng dư, tức là đến các phép toánanchia đồng dư cho một số nguyênz . Chúng ta đã biết rằngxmodzsẽ cho phần dư của phép chia nguyênxchoz . Ví dụ, 25 mod 7 = 4 vì 25 = 3 x 7 + 4. Nếuxvàylà các số nguyên nằm giữa 0 vàz- 1, và nếuzlà một số nguyên có kích thướcm , thì phép tính nhân đồng dưxymodzsẽ bao gồm một phép nhân thường của hai số nguyên có kích thước tối đam , mà kết quả là một số nguyên có kích thước tối đa 2 m , và tiếp theo là một phép chia tích của hai số đó choz , cũng là một số nguyên có kích thước m , kết quả mà chúng ta quan tâm sẽ là phần dư 63/129
66. của phép chia này. Như vậy thời gian cần cho mỗi phép nhân đồng dư phần nào không bị ảnh hưởng bởi giá trị của hai sốxvày . dụng những phân tích trong phần trước với một số thay đổi cần thiết cho phép chúng ta kết luận rằng thuật toán trên chỉ cần một số lượng phép nhân đồng dư vào cỡ (log n) để tínhanmodz . Phân tích một cách chính xác hơn ta thấy số lượng phép nhân đồng dư bằng số Bít trong phép triển khai nhị phân củan , cộng với số Bít 1 trong số những Bít này; tức là vào khoảng 3/2 lgn cho các giá trị đặc trưng củan . Thuật toán tương ứngexposeqđòi hỏin– 1 phép nhân cho tất cả các giá trị củan . Để rõ hơn về điều này, hãy giả dụa ,nvàzlà những số có 200 chữ số và với các số có độ lớn như vậy có thể thực hiện phép nhân đồng dư trong một phần ngàn giây. Thuật toán expomod sẽ tính anmodz trong thời gian ít hơn một giây. Trong khi thuật toánexposeqcần thời giản vào khoảng 10179 lần tuổi của vũ trụ để tínhan . Trong thực tế, liệu chúng ta có cần tính những lũy thừa đồng dư lớn như vậy hay không? Khoa học mật mã hiện đại, môn khoa học và nghệ thuật của những giao tiếp bí mật trên những kênh không an toàn, phụ thuộc chủ yếu vào những phép tính này. Chúng ta hãy xem xét trường hợp sau: Hai người là anh A và chị B trao đổi các thông điệp với nhau. Giả sử anh A muốn gửi thông điệp cá nhânmcho chị B, nhưng kênh liên lạc lại không an toàn, hay nói một cách khác là dễ dàng bị nghe trộm. Để ngăn không cho những người khác đọc được thông điệp, anh A chuyển nó thành dạng mật mãc , sau đó gửi cho chị B. Việc chuyển đổi này là kết quả của một thuật toán chuyển mã. Đầu ra của nó không những chỉ phụ thuộc vào thông điệpmmà còn phụ thuộc vào tham biếnk . Chúng ta gọi tham biến này làkhóa . Theo phương pháp kinh điển thì khóa chính là thông tin bí mật được thoả thuận giữa anh A và chị B trước khi họ trao đổi thông điệp với nhau. Nhờ có khoáknên khi nhận được thông điệp (đã mật mã hoá)c , chị B có thể tạo lại thông điệpm . Những hệ thống bí mật kiểu như vậy đều dựa trên nguyên tắc là dù kẻ nghe trộm lấy được thông điệpc , nhưng không biết khóa k thì cũng không thể đọc được nội dung thông điệpm . Phương pháp mật mã hoá này được sử dụng với những thành công nhất định trong lịch sử phát triển của nó. Việc đòi hỏi các bên tham gia phải thỏa thuận những thông tin bí mật trước khi tham gia truyền thông có thể chấp nhận được trong giới ngoại giao và quân sự, nhưng khó có thể chấp nhận đối với những người dân bình thường. Trong thời đại siêu tốc điện tử, người ta có nhu cầu truyền thông riêng tư với nhau mà không cần có sự sắp đặt từ trước. Liệu anh A và chị B có thể trao đổi thông tin với nhau một cách bí mật với sự có mặt của những người khác mà không cần thỏa thuận từ trước những quy ước bí mật với nhau? Thế hệ mật mã hóa với khóa công khai đã được khai sinh với ý tưởng của Diffie, Hellman và Merkle về sự khả thi vấn đề trên trong những năm giữa thập kỷ 70 thế kỷ 20. Tiếp theo đây chúng tôi sẽ trình bày một giải pháp độc đáo được 64/129
67. Rivest, Shamir và Adleman đưa ra ít năm sau. Giải pháp nàyn ngày nay được biết dưới cái tên hệ thống mật mã RSA, viết tắt từ tên của những người đã phát minh ra nó. Xét hai số nguyên tố có 1 trăm chữ sốpvàqđược chọn một cách ngẫu nhiên bởi chị B. Gọizlà tích củapvàq . Chị B có thể tínhzmột cách hiệu quả từpvàq . Cho dù chúng ta sở hữu những máy tính hiện đại bậc nhất, cũng không có cách nào tính đượcpvàqtừzsử dụng những thuật toán đã biết, ngay cả khi chúng ta sử dụng hết cả thời gian của vũ trụ. Gọi ϕ là tích ( p- 1)( q- 1). Gọinlà một số nguyên nằm giữa 1 vàz– 1 được chọn một cách ngẫu nhiên bởi chị B sao cho n và ϕ nguyên tố cùng nhau. (Chị B không cần kiểm tra một cách cụ thể xemncó thỏa mãn điều kiện trên hay không vì chị sẽ nhanh chóng biết được điều đó). Trong số học chúng ta đã biết là chỉ có duy nhất một số nguyên s nằm giữa 1 và z– 1 thỏa mãn điều kiện nsmod = 1. Ngoài ra có thể dễ dàng tính rastừnvà ϕ (xem lời giải bài tập 7.31) đồng thời sự tồn tại củascòn cho phép kiểm tra xemnvà ϕ có nguyên tố cùng nhau hay không. Nếuskhông tồn tại, chị B cần phải chọn một giá trị ngẫu nhiên khác chon ; xác xuất thành công của mỗi lần chọn đều như nhau. Mấu chốt trong giải pháp được trình bày ở đây là định lý:axmodz=atrong đó 0 ≤a<zvàxmod ϕ = 1. Để có thể cho phép anh A hoặc ai đó truyền thông riêng tư với mình, chị B phổ biến cho tất cả sự lựa chọn của chị về giá trị củaxvàn , nhưng giữ bí mậts . Gọimlà một thông điệp mà anh A định gửi cho chị B. Sử dụng bộ mã chuNn chẳng hạn như ASCII, anh A chuyển thông điệp của mình thành một chuỗi Bít, được hiểu như là một sốa . Để đơn giản chúng ta giả thiết rằng 0 ≤a<z– 1; trong trường hợp a ≥z- 1 anh A có thể chia thông điệpmcủa mình thành từng đoạn có kích thước phù hợp. Tiếp đó anh A sử dụng thuật toánexpomodđể tínhc=anmodz , rồi gửi thông điệp đã được mã hóac cho chị B thông qua một kênh không an toàn. Nhờ có khóa s , Chị B giải mã và nhận được sốa , và qua đó là thông điệp mcủa anh A, việc này được thực hiện bởi một phép gọi hàmexpomod ( c ,s ,z ). Điều này thực hiện được vì:csmodz= ( anmodz ) s modz= ( an ) s mod z =ansmodz=a Bây giờ chúng ta sẽ xét đến hành động của kẻ nghe trộm. Giả sử anh ta nghe được mọi trao đổi giữa anh A và chị B, như vậy anh ta sẽ biếtz ,nvàc . Mục đích của anh ta là xác định giá trị sốamà anh A gửi cho chị B, sốalà số duy nhất nằm giữa 0 vàz– 1 thỏa mãn điều kiệnc=anmodz . Để tính ra a chưa có một thuật toán hiệu quả nào được biết đến: phép tính lũy thừa đồng dư có thể thực hiện một cách hiệu quả với thuật toánexpomodnhưng điều ngược lại hình như không thể thực hiện được. Phương pháp tốt nhất được biết đến hiện nay là: phân tíchzra thành hai thừa số p và q , ( p- 1)( q- 1), tính s và tính a=csmod. Đó chính là cách chị B đã làm. Mỗi bước nêu trên đều khả thi, trừ bước đầu tiên: phân tích một số có 200 chữ số ra thừa số là một việc vượt quá khả năng cho phép của công nghệ hiện nay. Bởi vậy lợi thế của chị B trong việc giải mã chính là ở chỗ chị ta là người duy nhất biết các thừa số củaz , là những số cần thiết để tính ra ϕ 65/129
68. vàs . Chị ta biết được không phải do có tài phân tíchzra thừa số mà do chị ta tính z từ các thừa số được chị ta chọn. Hiện tại độ chắc chắn của sơ đồ mật mã hóa này vẫn chưa được xác định trên phương diện toán học: Không có chứng minh toán học nào khẳng định việc phân tích ra thừa số là không thể được và cũng không có chứng minh nào khẳng định rằng để phá mã cần phải phân tích ra thừa số. Xét trên phương diện khác thì chúng ta có thể có những thuật toán có khả năng phân tích thừa số một cách hiệu quả, nhưng chúng lại đòi hỏi những máy tính lượng tử, mà để tạo ra những máy tính đó, thì lại nằm ngoài mtầm của công nghệ hiện tại. Hệ thống mật mã hóa mà chúng tôi mô tả ở trên vẫn được coi là một trong những phát minh sáng giá nhất trong lịch sử khoa học mật mã. Bài tập chương Cho mảng số liệu sau: 10, 4, -5, 7, -45, 14, 30, -2, 50 Hãy minh họa các bước của thuật toán để tìm mảng con lớn nhất. Dành cho độc giả Cho dãy số liệu 80, 12, 47, 16, 7, 56, 14, 19, 100 Hãy minh họa các bước của thuật toán MergeSort, QuickSort để sắp xếp dãy khóa trên theo thứ tự tăng dần. Dành cho độc giả Thiết kế thuật toán nhân 2 số nguyên dương, sử dụng thuật toán chia để trị, trong đó mỗi số nguyên dương được chia làm ba phần, và tích của hai số đó sẽ tìm được sau 5 phép nhân số này với độ xấp xỉ n/3. Phân tích độ phức tạp tính toán trong thuật toán thu được Dành cho độc giả Sử dụng các kĩ thuật đánh giá độ phức tạp trong chương 1 để đánh giá độ phức tạp của các thuật toán trong chương 2. 66/129
69. Dành cho độc giả Xét ma trận F = 0 1 1 1 Hãy tính thử kết quả của phép nhân ma trận này với vector (i, j). Trong đó i, j là hai số nguyên. Có gì đặc biệt khi i, j là hai số hạng liên tiếp của dãy Fibonaci? Từ đó xây dựng thuật toán chia để trị để tính các phần tử của dãy số Fibonaci và phân tích độ phức tạp tính toán của thuật toán trong 2 trường hợp a. Coi mỗi phép toán số học là phép toán cơ bản đòi hỏi một đơn vị thời gian b. Thời gian tính tích của hai số nguyên có độ dài s và q là : O(sqa-1) (s ³ q). Lưu ý là độ dài của số Fn cỡ O(n) với số thực a > 1. Dành cho độc giả 67/129