MỞ ĐẦU Bài toán tìm dãy con lớn nhất. ; đục Dãy số ø¿ đmi,., ø với Ì S7 %7 Sn được gọi là đấy con của dãy đã cho và J > a, duge goi 1a trọng hrợng của day con nay. k=f Vấn đề đặt ra là: Hãy tim trọng lượng lớn nhất của dấy con, tức là tìm cực đại giá trị Ít; ay, Để đơn giản ta gọi đấy con có trọng lượng lớn nhất là đấy con lớn nhất. Ví dụ: Nếu day da cho là ~2, 11, ~4, 13, -5, 2 thì cần đưa ra câu trả lời là 20 (là trọng lượng của dãy con 11, —4, 13).
Thuật toán trực tiếp Thuật toán đơn giản đầu tiên có thể nghĩ để giải bài toán đặt ra là: duyệt tất cả các dãy con có thể: a, Gin, wa G VỚI Ì SiSjSn và tính tổng của mỗi dãy con để tìm ra trọng lượng lớn nhất. Trước hết nhận thấy rằng, tổng số các dãy con có thể của dãy đã cho là: C(n2) t+ n= 7/2 + n/2, Thuật toán này có thê cài đặt trong đoạn chương trình sau: int maxSum = 0; for (int i=0; i<n; i++) { for (int j=i; j<n; j++) { int sum = 0; for (int k=i; k<=j; k++) sum += alk]; if sum > maxSum maxSum = sum; } Phân tích thuật toán: Ta sẽ tính số lượng phép cộng mà thuật toán phải thực hiện, tức là đếm xem dòng lệnh:. Sum += a[k] phải thực hiện bao nhiêu lần. Số lượng phép cộng sẽ là: nel aol aa SVG-i4D =Š'd+2+.+0~0)= DĐ taQ jot imo 2 =1 Ÿ#@+I) R Py Sepa dnteenanen Mì ne} 7 2m 2L£ kel 2 6 2 7 wn 6 2 3 1.
Thuật toán nhanh hơn Để ý rằng tổng các số hạng từ ¡ đến ÿ có thể thu được từ tổng của các số hạng từ ¡ đến j — 1 bởi một phép cộng, cụ thê ta có: Šã1- aj] +S att Nhận xét này cho phép rút bớt vòng tp for f trong củng. Ta có thể cài đặt như sau: int maxSum = a[0]; for (int i=0; i<n; itt) { int sum = 0; for (int j=i; j<n; j++) { sum += al[j]; if sum > maxSum maxSum = sum; } Phân tích thuật toán: Ta lại tính số lần thực hiện phép cộng và thu được kết quả sau; tel n DK n—Ù=n+(n~l)+. 10 Để ý rằng số này đứng bằng số lượng dãy con. Dường như thuật toán thu được là rất tốt, vì ta phải xét mỗi đấy con đúng một lần.
Thuật toán đệ quy Ta còn có thể xây dựng thuật toán tốt hơn nữa bằng cách sử dụng kỹ thuật chia để trị. Kỹ thuật này bao gồm các bước sau: ~ Chia bài toán cần giải ra thành các bài toán con củng đạng; ~ Giải mỗi bài toán con một cách đệ quy; ~— Tổ hợp lời giải của các bài toán con đề thu được lời giải của bài toán xuất phát. Áp dụng kỹ thuật này đối với bài toán tìm trọng lượng lớn nhất của các dãy con. Ta chia day da cho ra thành hai dãy sử đụng phân tử ở chính giữa và thu được hai đãy số (gọi tắt là đấy bên trái và dãy bên phải) với độ dài giảm đi một nửa.
Để tổ hợp lời giải, nhận thấy rằng chỉ có thể xảy ra một trong ba trường hợp: — Day con lớn nhất nằm ở dãy con bên trái (nửa trái); — Dãy cơn lớn nhất nằm ở đấy con bên phải (nửa phải); ~ Day con lớn nhất bắt đầu ở nửa trái và kết thúc ở nửa phải (giữa). Đo đó, nếu ký hiệu trọng lượng của day cơn lớn nhất ở nửa trái là w_, ở nữa phải là wạ và ở giữa là w thì trọng lượng cần tìm sẽ là: Max (WI, Wr, Wm). Việc tìm trọng lượng của dãy con lớn nhất ở nửa trái (wu) và nửa phải (wạ) có thể thực hiện một cách đệ quy. Để tìm trọng lượng w của dãy con lớn nhất bắt đầu ở nữa trái và kết thúc ở nửa phải, ta thực hiện như sau: / — Tính trọng lượng của day con lớn nhất trong nửa trái kết thúc ở điểm chia (wa); ~ Tính trọng lượng của đấy con lớn nhất trong nửa phải bất đầu ở điểm chia (wor); ~ Khi d6 wy = wa + Wer.
Để tính trọng lượng của đấy con lớn nhất ở nửa trái (từ a[ï] đến a[ï]) kết thúc ở a[j], ta dùng thuật toán sau: MaxLeft(a, i, j); { maxSum:= -0; sum:=0; for k:= j downto i { sum:= sumta[k]; maxSum:= max(sum, maxSum); 11 } return maxSum; } Dé tinh trọng lượng của dãy con lớn nhất ở nửa phải (từ a[i] đến a[]]) bất đầu từ đ[ï], ta dùng thuật toán sau: MaxRight(a, i, j); { TaxSum:= —oo; sum:=0; for k:= i to j { sum:= sumta[k]; maxSum:= max(sum, maxSum); } return maxSum; } Sơ đồ của thuật toán đệ quy có thể mô tả như sau: MaxSub(a, i, 3); { if (i = 3) return a[i] else { m:= (113)/2; wi:= MaxSub(a, i, m); wR:= MaxSub(a, m+i, 4); wM:= MaxLeft(a, i, m)+ MaxRight (a, mt1, 4); return max(wL, wR, wM); } } Phân tích thuật toán: Ta cần tính xem lệnh gọi MaxSub(a,1,n) để thực hiện thuật toán đòi hỏi bao nhiêu phép cộng? Truớc hết, ta nhận thấy MaxLeft và MaxRight đòi hỏi: n/2 + n/2 = n phép cộng. Vì vậy, nếu gọi 7ø) là số phép cộng cần tìm, ta có công thức đệ quy sau: 0 n=l T@)=4_ on n BC TC)+T7C)+n=2TC)+n z”>1 Ta khang định rằng 7(2° = k2" và chứng minh bằng quy nạp. 12 — Cơ sở quy nạp: Nếu & = 0 thì T2) = 7(1) = 0 = 0.20, — Chuyển quy nạp: Nếu k> 0, giả sử rằng T2“) = (k— 1)2* là đúng. Khi đó: T25=2T0T9+22=<2 =1) 2?1+ 2? = k2, — Quay lại với ký hiệu n, ta có: Tín) = n log n.
Kết quả cho thấy thuật toán thu được nhanh hơn thuật toán thứ hai. Thuật toán Quy hoạch động Ta còn có thể phát triển thuật toán nhanh hơn nữa nhờ sử dụng kỹ thuật quy hoạch động. Việc phát triển thuật toán dựa trên quy hoạch động bao gồm ba giai đoạn: 1. Phân rã: chia bài toán cần giải thành những bài toán con nhỏ hơn có cùng dạng với bài toán ban đầu.
Ghi nhận lời giải: lưu trữ lời giải của các bài toán con vào một bảng. Tổng hợp lời giải: lần lượt từ lời giải của các bài toán con kích thước nhỏ hơn tìm cách xây dựng lời giải của bài toán kích thước lớn hơn, cho đến khi thu được lời giải của bài toán xuất phát (là bài toán con có kích thước lớn nhất). Phân rã: Gọi s; là trọng lượng của day con lớn nhất trong dy ay, do,. Rõ ràng s„ là giá trị cần tìm.
Tổng hợp lời giải: Trước hết, ta có: đi Cái. Giả sử ¡ > 1 và s¿ là đã biết với & = 1, 2,. Ta cần tính s; là trọng lượng day con lớn nhất của day:. Do day con lớn nhất cha đấy này hoặc là có chứa phần tử ø; hoặc không chứa phần tử ø¡, nên nó chỉ có thể là một trong hai đấy: ~ Day con lén nhat cia day a, a2, ., dias — Day con lớn nhất của đẩy ai, aa,., đị kết thúc tại a; Từ đó suy ra: 5) = max {5.4 6}, 1= 2, 0 T8, Trong đó: e; là trọng lượng dấy con lớn nhất của day ay, a, ., a kết thúc tại ø; Để tính ø, ta cũng có thể sử đụng công thức đệ quy sau: @ = ay e; = max fa; e-) + af, i= 2,.
13 Tổng hợp các kết quả ta đi đến thuật toán sau: MaxSub (a) ; { - smax = a[1l]; (* smax - trọng lượng của đây con lớn nhất *) : maxendhere = a[1]; imax = 1; (* imax ~¬ vị trí kết thúc của dãy con lớn nhất *) for i = 2 ton{ u maxendhere + a[i]; v= a[i]; Lf (u > v) maxendhere = u else maxendhere = v; if (maxendhere > smax)then { smax := maxendhere; ảimax := i; } } Phân tích thuật toán: Dễ thấy số phép toán cộng phải thực hiện trong thuật toán (số lần thực hiện câu lệnh u = maxendhere + a[i];) là n. So sánh các thuật toán — Cùng một bài toán ta đã để xuất bốn thuật toán đòi hỏi số lượng phép toán khác nhau và vì thế sẽ đời hỏi thời gian tính khác nhau. — Các bảng trình bày dưới đây cho thấy thời gian tính với giá thiết máy tính có thể thực hiện 10° phép cộng trong 1 giây. ng n=10 Thời gian n=100 Thời gian log@) 3.6x 10-6 gidy TẾ 100 10%giay .| 10000 102 giây P 1x 103 102 giây 1x106 10-2 gidy e 2:2x10 2x10^giây | 2.69x108 || >1025thế kỷ 14 phép ¬ toán n=10000 | Thờigian n=10° Thai gian logứn 13.3 106giây 19,9 <102 giây rlog(n) || 133x105 102 giây 1.
THUẬT TOÁN VÀ ĐỘ PHỨC TẠP 1. Khái niệm bài toán và thuật toán Định nghĩa: Bài đoán tinh toán Ƒ là ánh xạ từ tập các xâu nhị phân độ dài hữu hạn vào tập các xâu nhị phân độ dai hữu hạn: F: {0, 1}* — {0,1}*. Vi du: -Mỗi số nguyên x đều có thể biếu điễn dưới đạng xâu nhị phân là cách viết trong hệ đêm nhị phân của nó. — Hệ phương trình tuyến tính Ax = b có thể biển diễn đưới dạng xâu là ghép nối của các xâu biểu diễn nhị phân của các thành phần của ma trận 44 và vectơ 6.
— Đa thức một biến P(x) = ay + ai x +. + a„ z” hoàn toàn xác định bởi đấy số ri, ao, A},. a„ mà để biểu điễn dãy số này chúng fa có thể sử dụng xâu nhị phân. Định nghĩa: Ta biểu thuật todn giải bài toán đặt ra là một thủ tục xác định bao gỗm một dãy hữu hạn các bước cần thực hiện để thu được đầu ra cho một đầu vào cho trước của bài toán.
"Thuật toán có các đặc trưng sau đây:. — Đầu vào (Input): Thuật toán nhận đữ liệu vào từ một tip nao đồ, — Dau ra (Output): Với mỗi tập các dữ liệu đầu vào, thuật toán đưa ra cdc dit liệu tương ứng với lời giải của bài toán. / ~ Chính xác (Precision): Các bước của thuật toán được mô tá chính xác. — Hữu han (Finiteness): Thuat toán cần phải đưa được đầu ra sau một số hữu hạn (có thé rât lớn) bước với mọi đầu vào.
— Đơn trị (Uniqueness): Các kết quả trung gian của từng bước thực: hiện thuật toán được xác định một cách đơn trị và chỉ phụ thuộc vào đầu vào cũng như các kết quả của các bước trước. — Tổng quát (Generalify): Thuật toán có thể áp dụng để giải mọi bài toán có dạng đã cho. Độ phức tạp của thuật toán Đảnh giá độ phức tạp tính toán của thuật toán là đánh giá lượng tài nguyên các loại mà thuật toán đôi hỏi sử dụng.