Đề tài Các vấn đề về độ phức tạp thuật toán

Bài tập lý thuyết thuật toán Sinh Viên: Ngô Công Huân Lớp : K5H Đề Bài: Khái niệm thuật toán. Trình bày các mô hình tính toán thông dụng Máy Turing và máy xử lý thuật toán tựa ALGOL. Trình bày các vấn đề về độ phức tạp thuật toán. Cài đặt có minh họa bằng đồ họa thuật toán sắp xếp chèn Insertion sort. Đánh giá độ phức tạp của thuật toán sắp xếp. Phần I : Khái niệm thuật toán Thuật toán: 1.Bài toán: Bài toán là phát biểu có dạng : Giả thiết. Kết luận. Yêu cầu: Từ giả thiết cần phải đi tìm lời giải cho kết luận hoặc khẳng định kết luận đó là đúng hay sai. 2.Khái niệm thuật toán: Thuật toán 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 lời giải của bài toán. Các đặc trưng của thuật toán: Đầu vào (Input) :Thuật toán nhận dữ liệu đầu vào từ một tập nào đó. Đầu ra (Output) : Với mỗi một tập dữ liệu đầu vào ,thuật toán đưa ra các dữ 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 thực hiện của thuật toán phải được mô tả chính xác. Hữu hạn (Finiteness) : Thuật toán cần phải được đầu sau một số hữu hạn (có thể rất lớn) bước với mọi dữ liệu đầu vào. Đơn vị (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ác đơn vị và chỉ phụ thuộc vào đầu vào và các kết quả của các bước trước. Tổng quát (Generality) : Thuật toán có thể áp dụng để giải mọi bài toán có dạng đã cho. Ví dụ về thuật toán: Cho 3 số nguyên a,b,c , mô tả thuật toán tìm số lớn nhất trong 3 số đã cho. Giải: Bước 1 : Đặt max:=a; Bước 2 : Nếu max<b thì max:=b; Bước 3 : Nếu max<c thì max:=c; Tư tưởng của thuật toán là duyệt lần lượt các giá trị của từng số và giữ lại giá trị lớn nhất vào biến max.Kết thúc thuật toán x cho số nguyên lớn nhất trong 3 số đã cho. Ký hiệu max:=a trong mô tả của thuật toán là thay thế giá trị của max bởi giá trị của a.Khi phép toán thực hiện xong thì giá trị của a không bị thay đổi.Giả sử a=1 ,b =5, c =3 Tại bước 1 max=a(1),đến bước 2 khi max=1c nên max phép gán max:=c không được thực hiện. Sau các bước thực hiện ,thuật toán kết thúc cho trở lại giá trị max=5. Thuật toán có đầu vào : 3 số nguyên a,b,c Đầu ra : số max chứa giá trị lớn nhất trong 3 số Chính xác : Các bước của thuật toán được mô tả chính xác có thể viết chương trình. Hữu hạn : Thuật toán thực hiện sau 3 bước thì kết thúc. Tổng quát : Thuật toán thực hiện được với mọi dữ liệu vào có 3 số nguyên a,b,c. Phần II : Mô hình tính toán thông dụng I.Mở đầu: Để mô tả thuật toán có hai mô hình thông dụng là mô hình máy Turing và máy xử lý thuật toán tựa Algol. II.Mô hình máy Turing : 1.Cấu tạo: +)Bộ nhớ : Gồm một băng tuyến tính vô hạn,chia thành các ô nhớ,mỗi ô nhớ chứa được một ký tự nguyên tố. +)Bộ điều khiển: Có hữu hạn trạng thái,điều khiển một đầu đọc,ghi,tại mỗi thời điểm nhòm vào một ô nhớ. 2.Hoạt động: Theo thời gian “rời rạc” ,được điều khiển bởi bộ điều khiển. Một bước hoạt động cơ bản của máy bao gồm các động tác sau: Trạng thái trong bộ điều khiển dịch chuyển sang trạng thái khác. Đầu đọc dịch chuyển sang trái,sang phải hoặc đứng yên. Một cách hình thức ,xem máy Turing là một bộ T(Q,X,Y,qo,F, δ) trong đó: Q : Tập hữu hạn các trạng thái. X : Tập các ký hiệu trên băng trong đó X có thể chứa ký hiệu rỗng B (BLANK). Y : Tập các ký hiệu vào. q0: Trạng thái ban đầu. FQ: Tập các trạng thái kết thúc δ : Hàm chuyển trạng thái : δ : Q x X -> Q x {X – {B}} x {L,R,S} Tại thời điểm t máy Turing ở trạng thái p,đầu đọc – ghi nhòm vào ô nhớ có kí hiệu là X.Taih thời điểm tiếp theo t+1 (một đơn vị thời gian) máy ở trạng thái q,ký hiệu X đã thay bằng Y,đầu đọc-ghi dịch chuyển sang phải hay sang trái hoặc đứng nguyên δ : (p,X) -> (q,Y,d) d {L,R,S} Hay viết (p,X) -> (q,Y,d) là một mệnh lệnh của máy T,xâu CpXD được gọi là một hình trạng của máy T. CpXD->C1qZD1 được gọi là một bước chuyển hình trạng ,nếu giá trị (q,Z) δ thì xem như một quá trình xử lý đã kết thúc hay C1qZD1 là hình trạng cuối cùng. Nếu δ là hàm đơn trị thì T được gọi là máy đơn định. Nếu δ là hàm đa trị thì T được gọi là máy không đơn định Đơn vị nhớ : Là ô nhớ chứa một ký hiệu,nếu dùng mã nhị phân thì đơn vi nhớ là 1 bít Đơn vị thời gian : Là thời gian cần thiết để thực hiện một bước hoạt động cơ bản (bước chuyển hình trạng) Nhận xét : Máy Turing có cấu tạo cực kỳ đơn giản nhưng lại làm được mọi việc liên quan tới tính toán các phép tính.Từ mô hình này có thể định nghĩa ra phép cộng ( mã hóa dạng nhị phân ) bằng các bước dịch chuyển đầu đọc 0,1 và từ đó định nghĩa ra các phép tính khác. III.Máy xử lý thuật toán viết bằng ngôn ngữ tựa ALGOL - Đơn vị nhớ : Một ô nhớ chứa trọn vẹn một dữ liệu. - Đơn vị thời gian: Thời gian để thực hiện một phép tính số học cơ bản hay logic như cộng trừ nhân chia. Phần III:Các vấn đề về độ phức tạp thuật toán I.Độ phức tạp của thuật toán: Một chương trình máy tính được cài đặt dựa trên một thuật toán đúng để giải quyết bài toán hay vấn đề.Tuy nhiên ngay cả với khi thuật toán đúng,chương trình vẫn có thể không sử dụng được đối với một dữ liệu đầu vào nào đó vì thời gian để cho kết quả là quá lâu hoặc sử dụng quá nhiều bộ nhớ (vượt ra ngoài khả năng đáp ứng của máy tính). Khi tiến hành phân tích thuật toán nghĩa là chúng ta tìm ra một đánh giá về thời gian và “không gian” cần thiết để thực hiện thuật toán.Không gian ở đây được hiểu là các vấn đề về yêu cầu bộ nhớ,thiết bị lưu trữ,… của máy tính để thuật toán có thể làm việc. Việc xem xét về không gian của thuật toán phụ thuộc phần lớn vào cách tổ chức dữ liệu của thuật toán.Trong phần này khi nói đến độ phức tạp của thuật toán,chúng ta chỉ đề cập đến đánh giá về mặt thời gian mà thôi. 1.Chi phí phải trả cho một quá trình tính toán: Thường chỉ quan tâm đến chi phí không gian (bộ nhớ) và thời gian Chi phí thời gian của một quá trình tính toán là thời gian cần thiết để thực hiện một quá trình tính toán. + Đối với máy Turing : Chi phí thời gian là số bước chuyển hình trạng từ trạng thái q0 đến trạng thái kết thúc qn. + Đối với thuật toán tựa ALGOL : Chi phí thời gian là số các phép tính số học logic cơ bản cần thực hiện trong quá trình tính toán.Còn chi phí không gian là số ô nhớ cần thiết cho quá trình tính toán. Gọi A là thuật toán với bộ dữ liệu vào e thì tA(e) : Chi phí thời gian để hoàn thành thuật toán với bộ dữ liệu vào e lA(e) : Chi phí bộ nhớ để hoàn thành thuật toán với bộ dữ liệu vào e Cùng một thuật toán A với bộ dữ liệu vào khác nhau thì phải trả giá khác nhau. Ví dụ: Cho dãy số nguyên S={ x1,x2,…,xn }, số phần tử n.Tìm số lớn nhất trong dãy. Bài toán được biểu diễn như sau : Input : Dãy S={ x1,x2,…,xn }, số n Output: Số max của dãy. Thuật toán A: Begin Max:=x1; For i:=2 to n do If Max<xi Max:=xi; End; Xét bộ dữ liệu vào e={4,0,9,1,5} lA(e)= 1+1+1+5=8 (1 biến cho biến chạy i, một biến cho max,một biến cho n và 5 biến cho các xi) tA(e)=5+1=6 vì max:=4 thực hiện 1 phép tính vì x2=0<max=4 thực hiện 1 phép tính x3=9>max=4 nên max:=9 thực hiện 2 phép tính x4=1<max=9 thực hiện 1 phép tính x5=5<max=9 thực hiện 1 phép tính tổng cộng thực hiện 6 phép tính. 2.Các định nghĩa về độ phức tạp thuật toán: a)Độ phức tạp trong trường hợp xấu nhất: Cho một thuật toán A với đầu vào n khi đó: Độ phức tạp về bộ nhớ trong trường hợp xấu nhất : LA(n)=max{ lA(e) | |e|≤n } Độ phức tạp thời gian trong trường hợp xấu nhất : TA(n)=max{ tA(e)| |e|≤n } b)Độ phức tạp trung bình : Là tổng các độ phức tạp khác nhau ứng với từng bộ dữ liệu khác nhau chia cho tổng số đó. c)Độ phức tạp tiệm cận : Thuật toán A với đầu vào là n có độ phức tạp O(f(n)) nếu tồn tại hằng số C,N0 : TA(n) ≤C.f(n) , n≥N0.Tức là TA(n) có tốc độ tăng là O(f(n)). d)Độ phức tạp đa thức (Polynomial): Thuật toán được coi là độ phức tạp đa thức khi tồn tai đa thức P(n) mà TA(n) ≤C.P(n), n≥N0. e)Thuật toán đa thức : Thuật toán được gọi là độ phức tạp đa thức nếu độ phức tạp thời gian trong trường hợp xấu nhất của nó là đa thức. Độ phức tạp Thuật ngữ O(1) O(nlog(n)) O(n) O(nk) (k>=2) O(kn) (k>1) O(n!) Độ phức tạp hằng số Độ phức tạp logarit Độ phức tạp tuyến tính Độ phức tạp đa thức Độ phức tạp hàm mũ Độ phức tạp giai thừa 3.Cách tính độ phức tạp : a)Quy tắc cộng : Nếu T1(n) và T2(n) là thời gian thực hiện 2 chương trình P1 và P2 và T1(n)=O(f1(n)) T2(n)=O(f2(n)) thì thời gian thực hiện 2 đoạn chương trình nối tiếp nhau là : T(n)=O(max(f1(n),f2(n))) b)Quy tắc nhân : Nếu T1(n) và T2(n) là thời gian thực hiện 2 chương trình P1 và P2 và T1(n)=O(f1(n)) T2(n)=O(f2(n)) thì thời gian thực hiện 2 đoạn chương trình lồng nhau là : T(n)=O(f1(n).f2(n))) c)Độ phức tạp của chương trình đệ quy: Phương trình đệ quy là một phương trình biểu diễn mối quan hệ giữa T(n) và T(k) trong đó T(n) là thời gian thực hiện với kích thước dữ liệu nhập vào là n, T(k) là thời gian thực hiện với kích thước dữ liệu nhập vào là k ≤ n. Để thành lập phương trình đệ quy cần căn cứ vào phương trình đệ quy. Để giải phương trình đệ quy cần sử dụng phương pháp truy hồi tức là thay thế T(m) bất kỳ m ≤ n vào phía vế phải của chương trình đệ quy đến khi tất cả các T(m) với m>1 được thay thế bởi T(1). Định lý : (Nghiệm của phương trình truy hồi) T(n)=b nếu n=1 ngược lại bằng nếu n>1 T(n)= O(n) nếu a<c T(n)= O(nlogc(n) nếu a=c T(n)= O(nlogc(a)) nếu a>c Phần V : Đánh giá độ phức tạp thuật toán Insertion Sort. Lời mở đầu: Thuật toán sắp xếp “Insertion sort” là một trong những thuật toán sắp xếp trong cơ bản được sử dụng để sắp xếp những danh sách tuyến tính không quá lớn với thời gian đa thức.Ngoài ra còn một số thuật toán sắp xếp trong khác tương đương như thuật toán sắp xếp nổi bọt “Bubbles sort”, thuật toán sắp xếp chọn “Selection sort” nhưng chúng khác nhau về tư tưởng của việc sắp xếp.Ta hãy xem xét kỹ hơn về tư tưởng và thuật toán,cũng như đánh giá độ phức tạp của thuật toán này,những ưu nhược điểm của nó. Thuật toán sắp xếp chọn Insertion sort: 1.Tư tưởng thuật toán: Xuất phát từ thực tế trong việc xếp hàng,chỉnh đốn hàng ngũ mà thuật toán Insertion sort ra đời. Trong quân,khi có hiệu lệnh của người chỉ huy tất cả các chiến sĩ từ mọi nơi đổ về địa điểm tập trung hàng ngũ.Yêu cầu khi tập trung là khi xếp hàng dọc,đội hình đội ngũ chỉnh tề,người thấp ở đầu ,những người còn lại tuy chiều cao của mình mà tìm vị trí thích hợp ở sau người đầu hàng sao cho chiều cao tăng dần từ đầu hàng đến cuối hàng.Có 3 điều cần lưu ý ở đây: +) Ngay khi có hiệu lệnh tập trung,ai cũng có thể là người đứng đầu ,tuy nhiên sau khi chỉnh đốn lại thì chỉ có người thấp nhất mới được đứng đầu,người cao hơn người đứng đầu phải đứng ngay sau người đứng đầu đó.Cứ như vậy cho đến khi xếp song hàng hoàn chỉnh. +)Trong một tập thể quân số rất đông không ai có thể nhớ được mình cao hơn ai,không thể nhớ được vị trí chính xác của mình phải đứng trong hàng lần trước vì vị trí xếp hàng là thay đổi.Chỉ có thể so sánh được chiều cao của hai người đứng kế tiếp nhau trong hàng. Vậy làm sao để sếp được hàng đảm bảo điều kiện trên? Rất đơn giản,ban đầu ai cũng có thể đứng vào vị trí thứ nhất (vị trí đầu tiên tính từ bên trái của hàng),những người còn lại ai cúng có thể đứng vào vị trí thứ 2,thứ 3 …. cứ như vậy đến vị trí thứ n thì hàng đã tạo thành nhưng chưa được sắp xếp. Để xắp xếp thì xuất phát từ người đứng ở vị trí thứ 2,người này đứng sau người đầu hàng,có thể tự xét được xem mình có thấp hơn anh ta không,nếu có thì bảo anh ta đổi chỗ cho mình.Sau đó đến người ở vị trí thứ 3 từ đầu hàng ,anh này cũng làm vậy.Cứ thế lần lượt từ người thứ ở vị trí thứ 2 đến người ở vị trí thứ n,nếu người đứng trước mình cao hơn thì đổi chỗ cho anh ta.Kết thúc quá trình trên thì hàng đã được xếp đảm bao tiêu chuẩn,người thấp đứng trước,người cao đứng sau. Như vậy ta có bài toán sắp xếp một dãy có n phần tử với giải pháp như sau Giả sử có 1 dãy số A gồm n phần tử ,cần sắp xếp theo chiều tăng dần của giá trị các số Ký hiệu A[j] phần tử ở vị trí thứ j trong dãy A,mỗi phần tử tại một thời điểm chỉ có 1 vị trí duy nhất. Với mọi j=2..n nếu A[j]1 thì đổi chỗ A[j] với A[j-1],sau khi đổi chỗ nếu vẫn còn thỏa điều kiện thì tiếp tục đổi chỗ cho A[j-1] với A[j-2]. Đó chính là tư tưởng thuật toán. 2.Thuật toán Insertion sort. Dựa trên tư tưởng trên thì thuật toán được phát biểu như sau Input : Dãy A có n phần tử Output : Dãy A đã được sắp xếp tăng dần. Bước 1 : Xét A[2] nếu A[2]<A[1] thì đổi chỗ Bước 2 : Xét A[3] nếu A[3]<A[2] thì đổi chỗ Khi đổi chỗ song nếu A[2]<A[1] quay lại bước 1 ….. Bước k : Nếu A[k]1 thì đơi chỗ A[k] với A[k-1] Nếu A[k-1]<A[k-2] thì quay lại bước k-1 Chứng minh sự đúng đắn của thuật toán : Ta sẽ chứng minh qui nạp theo sỗ phần tử của mảng: Trường hợp cơ sở : Dãy có 1 phân tử (Đúng) Dãy có 2 phần tử,nếu dùng thuật toán trên để sắp xếp thì vẫn (Đúng) Giả sử thuật toán trên đúng cho việc sắp xếp dãy có k phần tử tức là ta có dãy đã sắp xếp A[1]<=A[2]<=A[3]<=…<=A[k] Ta chứng minh là đúng với dãy có k+1 phần tử: Bây giờ với dãy đã sắp xếp có k phần tử ta thêm 1 phần tử vào vị trí k+1 Nếu A[k]<=A[k+1] thì thuật toán trên không tác động làm thay đổi dãy và hiển nhiên ta có 1 dãy gồm k+1 phần tử đã sắp tăng dần. Khi A[k+1]<A[k] thì thuật toán sẽ đổi chỗ A[k] với A[k+1],sau khi đổi chỗ nếu A[k]<A[k-1] thì lại đổi chỗ A[k] với A[k-1],cứ như vậy xét đên khi k=2. Như vậy sau khi thực hiện xong thuật toán ta có : A[1]<=A[2]<=A[3]<=…<=A[i]<=A[i+1]<=…<=A[k]<=A[k+1] Tức là dãy đã được sắp xếp tăng.Đó là điều phải chứng minh 3.Mô phỏng thủ tục thuật toán: Const n=100; Var A:Array[1..n] of Integer; Procedure Insertion_Sort(n:Integer); Var j,I,tg:Integer; Begin 1) For i:=2 to n do {Thực hiện n-1 lần} Begin 2) j=i; {O(1)} While (j>1) and (A[j]<A[j-1]) do {Thực hiện i-1 lần O(1)} Begin {Đổi chỗ} 4) tg=A[j]; {O(1)} 5) A[j]=A[i]; {O(1)} 6) A[i]=tg; {O(1)} 7) j=j-1; {O(1)} End; End; End; 4.Độ phức tạp của thuật toán (Theo ALGOL): a)Không gian: Sỗ ô nhớ cần thiết N+1+1+1+1 : N: Số ô nhớ dùng cho dãy số A 1: Cho biến n 1: Cho biến tạm j 1: Cho biến j 1: Cho biến tạm tg b)Thời gian: Vòng For (1) thực hiện (n-1) lần mỗi lần O(1) Lệnh gán (2) cần thời gian O(1) Các lệnh (4),(5),(6),(7) là các lệnh gán mỗi lệnh O(1),các lệnh này thực hiện tuần tự do đó theo quy tắc cộng cả khối Begin End trong vòng While là O(1). Vòng while (3) thì phần kiểm tra điều kiện O(2) do có 2 phép so sánh,thân vòng lặp while thực hiện (i-1) lần mỗi lần do đõ theo quy tắc nhân cả vòng while tốn thời gian là O(2*(i-1)). Vì vòng while nằm trong for nên theo quy tắc nhân ta có cả thuật toán thực hiện cần O().Ta có == Do nên độ phức tạp thuật toán Insertion sort là O(n2)