- CẤU TRÚC DỮ LIỆUVÀ THUẬT TOÁN Data Structures and Algorithms NguyỄN ĐỨC NGHĨA Bộ môn Khoa học Máy tính Đại học Bách khoa Hà nộiTel Off Mob)
[email protected] Chương 1 CÁC KIẾN THỨC CƠ BẢNCấu trúc dữ liệu và thuật toán - N.Đ.
- Bộ môn KHMT NỘI DUNG 1.1.
- Thuật toán và độ phức tạp 1.3.
- Một số kĩ thuật phân tích thuật toánCấu trúc dữ liệu và thuật toán - N.Đ.
- Để đơn giản ta gọi dãy con có trọng lượng lớn nhất là dãy con lớn nhất.• Ví dụ: Nếu dãy đã cho là thì cần đưa ra câu trả lời là 20 (là trọng lượng của dãy con Cấu trúc dữ liệu và thuật toán - N.Đ.
- Bộ môn KHMTThuậ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ể ai, ai+1.
- n = n2/2 + n/2 .Cấu trúc dữ liệu và thuật toán - N.Đ.
- Bộ môn KHMTThuật toán trực tiếp• Thuật toán này có thể cài đặt trong đoạn chương trình sau: int maxSum = 0.
- ai-1, ai .Cấu trúc dữ liệu và thuật toán - N.Đ.
- n.Cấu trúc dữ liệu và thuật toán - N.Đ.
- }}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.Cấu trúc dữ liệu và thuật toán - N.Đ.
- Bộ môn KHMT NỘI DUNG1.1.
- Thuật toán và độ phức tạp1.3.
- an, mµ ®Ó biÓu diÔn d·y sè nµy chóng ta cã thÓ sö dông x©u nhÞ ph©n.Cấu trúc dữ liệu và thuật toán - N.Đ.
- Bộ môn KHMTKhái niệm thuật toán• §Þnh nghÜa.
- cho.Cấu trúc dữ liệu và thuật toán - N.Đ.
- Thuật toán (Algorithms.
- Cấu trúc dữ liệu.
- Cách tổ chức lưu trữ dữ liệu vào - raCấu trúc dữ liệu và thuật toán - N.Đ.
- Bộ môn KHMTVòng đời của phần mềmThe Life Cycle of Software• Vòng đời của phần mềm – Là một quá trình dài và liên tục – Đòi hỏi để phát triển một phần mềm có chất lượng tốt – Lập trình viên có thể di chuyển từ một pha trong vòng đời sang bất kỳ pha nào còn lạiCấu trúc dữ liệu và thuật toán - N.Đ.
- Bộ môn KHMT Vòng đời của phần mềm The Life Cycle of Software Vòng đời của phần mềm như là một bánh lái có thể quay từ một pha đến một pha khác bất kỳ Nguyễn Đức Nghĩa - Bộ 1-35Cấu trúc dữ liệu và thuật toán - N.Đ.
- Bộ môn KHMT môn KHMT ĐHBKHN Vòng đời của phần mềm The Life Cycle of Software9 pha:• Phase 1: Chỉ rõ đặc điểm kỹ thuật (Specification) (đặc tả)• Phase 2: Thiết kế (Design)• Phase 3: Phân tích rủi ro (Risk Analysis)• Phase 4: Kiểm thử (Verification)• Phase 5: Lập trình (Coding)• Phase 6: Test thử (Testing)• Phase 7: Tinh chế lời giải (Refining the Solution)• Phase 8: Sản xuất (Production)• Phase 9: Bảo trì (Maintenance) Nguyễn Đức Nghĩa - Bộ 1-36Cấu trúc dữ liệu và thuật toán - N.Đ.
- Chương trình mẫu (Chương trình mô phỏng dáng điệu của một phần của sản phẩm phần mềm cần phát triển)Cấu trúc dữ liệu và thuật toán - N.Đ.
- Chỉ rõ mục đích của mỗi module – Chỉ rõ dòng dữ liệu trong các modules – Xác định giao diện (Interfaces - Cơ cấu giao tiếp giữa các mô đun)Cấu trúc dữ liệu và thuật toán - N.Đ.
- Chứng minh tính đúng đắn của thuật toán bằng các phương pháp hình thức.
- Dữ liệu đúng đắn với kết quả biết trước • Dữ liệu không đúng đắn • Dữ liệu ngẫu nhiên • Dữ liệu thực tếCấu trúc dữ liệu và thuật toán - N.Đ.
- Cải tiến một số bộ phận để đáp ứng yêu cầu của người dùng tốt hơnCấu trúc dữ liệu và thuật toán - N.Đ.
- Bộ môn KHMT Độ 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.
- Trong giáo trình này ta đặc biệt quan tâm đến đánh giá thời gian cần thiết để thực hiện thuật toán mà ta sẽ gọi là thời gian tính của thuật toán.• Thời gian tính phụ thuộc vào dữ liệu vào.• §Þnh nghÜa.
- Ta gäi kÝch thíc d÷ liÖu ®Çu vµo (hay độ dài dữ liệu vào) lµ sè bÝt cÇn thiÕt ®Ó biÓu diÔn nã.• Ta sẽ tìm cách đánh giá thời gian tính của thuật toán bởi một hàm của độ dài dữ liệu vào.
- Cấu trúc dữ liệu và thuật toán - N.Đ.
- Thêi gian nh vËy sÏ ®îc gäi lµ thêi gian tÝnh trung b×nh cña thuËt to¸n.Cấu trúc dữ liệu và thuật toán - N.Đ.
- Thuật toán và độ phức tạp1.4.
- Bộ môn KHMT Ký hiệu tiệm cận Asymptotic Notation Q, W, O • Được sử dụng để mô tả thời gian tính của thuật toán • Thay vì nói chính xác thời gian tính, ta nói (n2.
- Được xác định đối với các hàm nhận giá trị nguyên không âm • Dùng để so sánh tốc độ tăng của hai hàm Cấu trúc dữ liệu và thuật toán - N.Đ.
- c2g(n), với mọi n n0 } Ta nói rằng g(n) là đánh giá tiệm cận đúng cho f(n) Cấu trúc dữ liệu và thuật toán - N.Đ.
- Đối với hàm đa thức: Để so sánh tốc độ tăng cần nhìn vào số hạng với số mũ cao nhấtCấu trúc dữ liệu và thuật toán - N.Đ.
- cg(n) với mọi n n0 } Ta nói g(n) là cận trên tiệm cận của f(n)Cấu trúc dữ liệu và thuật toán - N.Đ.
- f(n) với mọi n n0 } Ta nói g(n) là cận dưới tiệm cận cho f(n) Cấu trúc dữ liệu và thuật toán - N.Đ.
- W(g(n)) Cấu trúc dữ liệu và thuật toán - N.Đ.
- W(f(n))Cấu trúc dữ liệu và thuật toán - N.Đ.
- Mọi thuật toán sắp xếp đều đòi hỏi duyệt qua tất cả các phần tử, vì thế bài toán sắp xếp có thời gian W(n) trong tình huống tốt nhất.
- Trên thực tế, sử dụng (chẳng hạn) sắp xếp trộn (merge sort), bài toán sắp xếp có thời gian (n log n) trong tình huống tồi nhất.Cấu trúc dữ liệu và thuật toán - N.Đ.
- Trong ví dụ trên, (n2) thay thế cho 3n2 + 2n + 1Cấu trúc dữ liệu và thuật toán - N.Đ.
- Bộ môn KHMTĐồ thị của một số hàm cơ bảnCấu trúc dữ liệu và thuật toán - N.Đ.
- Bộ môn KHMTGiá trị của các hàm cơ bản n logn n nlogn n2 n3 2n Cấu trúc dữ liệu và thuật toán - N.Đ.
- a = bCấu trúc dữ liệu và thuật toán - N.Đ.
- g(n)] không xác định không thể nói gì nCấu trúc dữ liệu và thuật toán - N.Đ.
- Bộ môn KHMTVí dụ A B • 5n2 + 100n 3n2 + 2 • log3(n2) log2(n3)Cấu trúc dữ liệu và thuật toán - N.Đ.
- log3(n2) log2(n3)Cấu trúc dữ liệu và thuật toán - N.Đ.
- A = 2lgn / lg3, B = 3lgn, A/B =2/(3lg3)Cấu trúc dữ liệu và thuật toán - N.Đ.
- O(g(n))Cấu trúc dữ liệu và thuật toán - N.Đ.
- Bộ môn KHMTVí dụ – 2n2 = O(n3): 2n2 ≤ cn3 2 ≤ cn c = 1 and n0= 2 – n2 = O(n2): n2 ≤ cn2 c ≥ 1 c = 1 and n0= 1 – 1000n2+1000n = O(n2): 1000n2+1000n ≤ cn2 c=1001 and n0 = 1000 – n = O(n2): n ≤ cn2 cn ≥ 1 c = 1 and n0= 1Cấu trúc dữ liệu và thuật toán - N.Đ.
- Bộ môn KHMTVí dụ – 5n2 = W(n.
- 0 Do n dương cn n 105/c vô lý: n không thể nhỏ hơn hằng số – n = W(2n), n3 = W(n2), n = W(logn)Cấu trúc dữ liệu và thuật toán - N.Đ.
- ¼ n2 c1= ¼ n ≠ (n2): c1 n2 ≤ n ≤ c2 n2 chỉ đúng với: n ≤ 1/c1Cấu trúc dữ liệu và thuật toán - N.Đ.
- n ≥ n0 – không thể xảy ra Cấu trúc dữ liệu và thuật toán - N.Đ.
- 100n + 5 ≤ 100n + n = 101n ≤ 101n2 với mọi n ≥ 5 n0 = 5 và c = 101 là các hằng số cần tìm – 100n + 5 ≤ 100n + 5n = 105n ≤ 105n2 với mọi n ≥ 1 n0 = 1 and c = 105 cũng là các hằng số cần tìm• Chỉ cần tìm các hằng c và n0 nào đó thoả mãn bất đẳng thức trong định nghĩa công thức tiệm cận Cấu trúc dữ liệu và thuật toán - N.Đ.
- Cho bài toán P, ta nói cận trên cho thời gian tính của P là O(g(n)) nếu để giải P tồn tại thuật toán giải với thời gian tính là O(g(n.
- Cho bài toán P, ta nói cận dưới cho thời gian tính của P là (g(n)) nếu mọi thuật toán giải P đều có thời gian tính là W(g(n.
- Cho bài toán P, ta nói thời gian tính của P là Q(g(n)) nếu P có cận trên là O(g(n)) và cận dưới là W(g(n)) .Cấu trúc dữ liệu và thuật toán - N.Đ.
- Bộ môn KHMTMột số lớp thuật toán• Một số lớp thuật toán đặc biệt.
- O(nk): đa thức (polynomial) (k ≥ 1)Cấu trúc dữ liệu và thuật toán - N.Đ.
- Bộ môn KHMTMô tả thuật toán: giả ngôn ngữ• Để mô tả thuật toán có thể sử dụng một ngôn ngữ lập trình nào đó.
- Tuy nhiên điều đó có thể làm cho việc mô tả thuật toán trở nên phức tạp đồng thời rất khó nắm bắt.• Vì thế, để mô tả thuật toán người ta thường sử dụng giả ngôn ngữ (pseudo language), trong đó cho phép vừa mô tả thuật toán bằng ngôn ngữ đời thường vừa sử dụng những cấu trúc lệnh tương tự như của ngôn ngữ lập trình.• Dưới đây ta liệt kê một số câu lệnh chính được sử dụng trong giáo trình để mô tả thuật toán.Cấu trúc dữ liệu và thuật toán - N.Đ.
- Bộ môn KHMTMô tả thuật toán: phỏng ngôn ngữ• Khai báo biến integer x,y.
- y=a*y+2;Cấu trúc dữ liệu và thuật toán - N.Đ.
- Bộ môn KHMTMô tả thuật toán: giả ngôn ngữ• Cấu trúc điều khiển if condition then dãy câu lệnh else dãy câu lệnh endif.
- while condition do dãy câu lệnh endwhile;Cấu trúc dữ liệu và thuật toán - N.Đ.
- Bộ môn KHMTMô tả thuật toán: phỏng ngôn ngữ repeat Câu lệnh case: dãy câu lệnh.
- print(data) hoặc print(thông báo)Cấu trúc dữ liệu và thuật toán - N.Đ.
- Bộ môn KHMTMô tả thuật toán: giả ngôn ngữ• Hàm và thủ tục (Function and procedure) Function name(các tham số) begin mô tả biến.
- end;Cấu trúc dữ liệu và thuật toán - N.Đ.
- Bộ môn KHMTMô tả thuật toán: phỏng ngôn ngữ• Ví dụ: Thuật toán tìm phần tử lớn nhất trong mảng A(1:n) Function max(A(1:n)) begin datatype x.
- end max;Cấu trúc dữ liệu và thuật toán - N.Đ.
- Bộ môn KHMTMô tả thuật toán: giả ngôn ngữ• Ví dụ: Thuật toán hoán đổi nội dung hai biến Procedure swap(x, y) begin temp=x.
- end swap;Cấu trúc dữ liệu và thuật toán - N.Đ.
- Bộ môn KHMTMô tả thuật toán: giả ngôn ngữ• Ví dụ.
- Sử dụng hàm này này ta xây dựng thuật toán giải bài toán đặt ra.• Nếu m=a*b với 1 < a, b < m, thì một trong hai thừa số a, b sẽ không vượt quá m .
- .Cấu trúc dữ liệu và thuật toán - N.Đ.
- Bộ môn KHMTMô tả thuật toán: giả ngôn ngữ• Thuật toán kiểm tra một số nguyên dương có phải là nguyên tố hay không.• Đầu vào: Số nguyên dương m.• Đầu ra: true nếu m là số nguyên tố, false nếu ngược lại.
- end Is_Prime;Cấu trúc dữ liệu và thuật toán - N.Đ.
- Bộ môn KHMTBình luận• Thuật toán này chỉ có thể sử dụng đối với những số có dưới 25 chữ số.• Nếu áp dụng đối với những số có nhiều chữ số hơn, chẳng hạn với thuật toán không thể dùng được.
- Nếu giả thiết là một phép chia có thể thực hiện trong thời gian 1 nanosecond thì thuật toán sẽ chạy trong 1013 năm!Cấu trúc dữ liệu và thuật toán - N.Đ.
- Bộ môn KHMTMô tả thuật toán: giả ngôn ngữ• Thuật toán tìm số nguyên tố lớn hơn số nguyên dương n.• Thuật toán sẽ sử dụng Is_prime như chương trình con.• Đầu vào: Số nguyên dương n.• Đầu ra: m - số nguyên tố lớn hơn n.
- end;• Do tập các số nguyên tố là vô hạn, nên thuật toán Lagre_Prime là hữu hạn.Cấu trúc dữ liệu và thuật toán - N.Đ.
- Bộ môn KHMTCác kỹ thuật cơ bảnphân tích độ phức tạp của thuật toán• Cấu trúc tuần tự.
- (max(Time(P), Time(Q)).Cấu trúc dữ liệu và thuật toán - N.Đ.
- Khi đó thời gian thực hiện vòng lặp for sẽ là m t(i) i 1Cấu trúc dữ liệu và thuật toán - N.Đ.
- c.k c k c k 1 k 1 2Cấu trúc dữ liệu và thuật toán - N.Đ.
- Còn để xác định số lần lặp ta cần phải khảo sát xem giá trị của hàm giảm như thế nào.• Việc phân tích vòng lặp Repeat được tiến hành tương tự như phân tích vòng lặp While.Cấu trúc dữ liệu và thuật toán - N.Đ.
- end case endwhileend;Cấu trúc dữ liệu và thuật toán - N.Đ.
- 1 còn d 2Cấu trúc dữ liệu và thuật toán - N.Đ.
- d/2• Do vòng lặp kết thúc khi d 1, nên từ đó suy ra thuật toán phải kết thúc.• Gọi dp là giá trị của j - i + 1 ở lần lặp thứ p 1 và d0 = n.
- Khi đó dp dp-1/2, p 1.• Thuật toán kết thúc tại bước p nếu dp 1, điều đó xảy ra khi p = log n.
- Vậy thời gian tính của thuật toán là O(log n)Cấu trúc dữ liệu và thuật toán - N.Đ.
- Bộ môn KHMT Các mô tả khác của thuật toán Binary SearchFunction mid=bsearch1(L,p,q,key) Function mid=bsearch2(L,p,q,key)while q>p while q>p mid=floor((p+q)/2).
- if key Để đánh giá thời gian tính có thể đếm số lần thực hiện câu lệnh đặc trưngCấu trúc dữ liệu và thuật toán - N.Đ.
- Bộ môn KHMTVí dụ: Thuật toán 1 ví dụ mở đầu int maxSum =0