Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 1: Thiết kế và phân tích - Đỗ Tuấn Anh

Nội dung text: Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 1: Thiết kế và phân tích - Đỗ Tuấn Anh

1. Cấu trúc dữ liệu và giải thuật Người thực hiện: Đỗ Tuấn Anh Email: anhdt@it-hut.edu.vn ĐT: 0989095167
2. Tài liệu tham khảo zSách giáo trình: Đỗ Xuân Lôi, Cấu trúc dữ liệu và Giải Thuật, NXB ĐHQGHN zR. Sedgewick, Algorithm in C, Addison Wesley
3. Nội dung zChương 1 – Thiết kế và phân tích zChương 2 – Giải thuật đệ quy zChương 3 – Mảng và danh sách zChương 4 – Ngăn xếp và hàng đợi zChương 5 – Cấu trúc cây zChương 6 – Đồ thị zChương 7 – Sắp xếp zChương 8 – Tìm kiếm
4. Chương 1 – Thiết kế và phân tích 1. Mở đầu 2. Từ bài toán đến chương trình 2.1 Modul hóa bài toán 2.2 Phương pháp tinh chỉnh từng bước 3. Phân tích giải thuật 3.1 Độ phức tạp về thời gian thực hiện GT 3.2 O-lớn, Omega-lớn, Theta-lớn 3.3 Xác định độ phức tạp về thời gian
5. 1. Mở đầu z Giải thuật: {Các bước giải quyết bài toán {Một dãy câu lệnh xác định một trình tự các thao tác trên một số đối tượng nào đó sao cho sau một số hữu hạn bước thực hiện ta đạt được kết quả mong muốn. z Đầu vào(Input): tập các đối tượng (dữ liệu) Các bước z Đầu ra(Output): một tập các giá trị thực hiện z Cấu trúc dữ liệu: {Tập hợp dữ liệu {Có mối quan hệ với nhau trong bài toán xác định z Lựa chọn cấu trúc dữ liệu và giải thuật thích hợp: rất quan trọng {Ví dụ: viết chương trình tìm kiếm số điện thoại theo tên đơn vị Chương trình = Giải thuật + Dữ liệu
6. 1. Mở đầu (tiếp) z Biểu diễn cấu trúc dữ liệu trong bộ nhớ: { Lưu trữ trong { Lưu trữ ngoài z Diễn đạt giải thuật: { Ngôn ngữ tự nhiên { Giả ngôn ngữ { Lưu đồ { Ngôn ngữ lập trình z Cài đặt giải thuật: ngôn ngữ C/C++
7. Giả ngôn ngữ 1. Chú thích: /* */ hoặc // 2. Đánh số thứ tự các đoạn của chương trình 3. Ký tự và biểu thức { 26 chữ cái Latin + 10 chữ số { Phép toán số học: +, -, *, /, ^(lũy thừa), % { Phép toán quan hệ: , ==, =, != { Phép toán logic: &&, ||, ! { Giá trị logic: true, false { Biến chỉ số: a[i], a[i][j] { Thứ tự ưu tiên của các phép toán: như C và các ngôn ngữ chuẩn khác
8. Giả ngôn ngữ (tiếp) z Lệnh gán: a = b; c = d = 2; z Khối lệnh: { S1; S2; S3; } z Lệnh điều kiện: if (B) if (B) S; {s1;s2;s3;} if (B) S1; else S2;
9. Giả ngôn ngữ zLệnh lặp for (i = 0 ; i = 0; i ) S; do S while (B); while (B) do S;
10. Giả ngôn ngữ (tiếp) z Lệnh vào/ra: read ( ) write ( ) z Chương trình con: function ( ) { S1; S2; Sn; return; // nếu chương trình con trả lại một giá trị } z Gọi chương trình con: ( )
11. Sơ đồ Lệnh điều khiểncóthể là: {Khối lệnh Bắt đầu {Lệnh điều kiện {Lệnh lặp Nhập n Bắt đầu hoặc kết thúc R=n%2 Lệnh gán S Đ R là chẵn Lệnh vào, lệnh ra Điều kiện Số lẻ Số chẵn Nối tiếp đoạn lệnh Luồng thực hiện Kết thúc
12. Khối lệnh Cú pháp: { S1 S1; S2; S2 S3; } S3
13. Lệnh điều kiện z Cú pháp if(điều_kiện) hành_động false điều kiện true hành động
14. Lệnh điều kiện zLệnh điều kiện if (B) then false true S1; B else S2; S2 S1
15. Lệnh lặp: zCú pháp: while (B) do S; true BS false
16. Lệnh lặp for zCú pháp for (khởi_tạo; điều_kiện; cập_nhật) hành_động khởi tạo false điều kiện true hành động cập nhật
17. Lệnh lặp do-while z Cú pháp do hành_động while (điều_kiện) hành động true điều kiện false
18. 2. Từ bài toán đến chương trình Mô đun hóa và việc giải quyết bài toán {Chia bài toán lớn (module chính) thành các bài toán (module) nhỏ hơn {Mỗi module thực hiện công việc cụ thể nào đó {Lặp đi lặp lại cho đến khi các module là cô đọng và biết cách giải quyết. => chiến thuật “Chia để trị”
19. 2.1 Module hóa bài toán
20. Module hóa bài toán z Thiết kế Topdown – từ đỉnh xuống, hay từ khái quát đến chi tiết. {Bước 1: Xác định dữ kiện đầu vào, yêu cầu đặt ra {Bước 2: Xác định các công việc chủ yếu (mỗi công việc tương đương với 1 module) {Bước 3: Giải quyết từng công việc một cách chi tiết bằng cách lặp đi lặp lại bước 1 + 2 z Ví dụ Bài toán: “Quản lý và bảo trì các hồ sơ về học bổng của sinh viên, thường kỳ lập báo cáo tổng kết”.
21. Thiết kế Topdown – Bước 1 zBước 1: Xác định dữ kiện đầu vào và các yêu cầu đặt ra {Đầu vào: Tập các file bao gồm các thông tin về học bổng của sinh viên: Mã SV, ĐiểmTB, Mức HB {Yêu cầu: zTìm kiếm và hiển thị thông tin của bất kỳ sinh viên nào zCập nhật thông tin của một sinh viên cho trước zIn bản tổng kết
22. Thiết kế Topdown – Bước 2 z Bước 2: Xác định các công việc chủ yếu 1. Đọc các thông tin của sinh viên từ file vào bộ nhớ trong (Đọc file) 2. Xử lý các thông tin (Xử lý thông tin) 3. Lưu thông tin đã cập nhật vào file (Ghi file) Quản lý học bổng Đọc file Xử lý TT Ghi file
23. Thiết kế Topdown – Bước 3 zBước 3: Lặp lại bước 1 + 2 {Đọc file: zĐầu vào: File thông tin trên đĩa zYêu cầu: Đọc file và lưu vào mảng: mỗi phần tử mảng lưu thông tin của một sinh viên ⇒ Đã cô đọng - Ghi file: - Đầu vào: Mảng lưu thông tin của các sinh viên - Yêu cầu: Lưu trở lại file ⇒Đã cô đọng
24. Thiết kế Topdown – Bước 3 zXử lý TT {Đầu vào: Mảng lưu thông tin của các sinh viên {Yêu cầu: zTìm một sinh viên cho trước zHiển thị thông tin của sinh viên zCập nhật thông tin của sinh viên zIn bản tổng kết
25. Thiết kế Topdown Quản lý học bổng Đọc file Xử lý TT Ghi file Tìm SV Hiển thị Cập nhật In bản TT SV TT SV tổng kết Tìm theo Tìm theo Tìm theo Mã SV HB ĐiểmTB
26. 2.2 Phương pháp tinh chỉnh từng bước (Stepwise Refinement) zBan đầu giải thuật được trình bày ở dạng ngôn ngữ tự nhiên zChi tiết hóa dần – tinh chỉnh hướng về phía ngôn ngữ lập trình zGiai đoạn trung gian – giả ngôn ngữ Ngôn ngữ tự Giả ngôn ngữ Ngôn ngữ lập nhiên trình
27. Tinh chỉnh từng bước – Ví dụ z Bài toán: “Sắp xếp một dãy n số nguyên theo thứ tự tăng dần” z Giải thuật: {Từ dãy số nguyên chưa được sắp xếp chọn ra số nhỏ nhất và đặt vào đầu dãy đã được sắp xếp {Loại số nguyên đóra khỏi dãy chưa được sắp xếp {Lặp lại cho đến khi dãy chưa được sắp xếp là rỗng Ngôn ngữ tự nhiên 84 60 74 23 30 35 46 57 12 78 12 84 60 74 23 30 35 46 57 78 12 23 84 60 74 30 35 46 57 78
28. Tinh chỉnh từng bước – Ví dụ zCấu trúc dữ liệu: {Dãy số ban đầu được lưu trữ trong một mảng một chiều {Dãy đã sắp xếp sẽ được lưu trùng với dãy chưa sắp xếp => Giải thuật: Đặt số nhỏ nhất của lượt thứ i vào dãy đã sắp xếp = đổi chỗ với số thứ i trong dãy
29. Tinh chỉnh từng bước – Ví dụ zTinh chỉnh bước 1 for(i=0; i<n; i++) { 1. Xét từ ai đến an-1 để tìm số nhỏ nhất aj 2. Đổi chỗ ai và aj } Giả ngôn ngữ
30. Tinh chỉnh từng bước – Ví dụ z Giải thuật 1: Xét từ ai đến an-1 để tìm số nhỏ nhất aj {Coi ai là “số nhỏ nhất” ( j = i) {So sánh “số nhỏ nhất” và ai+1, số nào nhỏ hơn thì coi là “số nhỏ nhất”(nếu ai+1< aj thì j = i+1) {Tiếp tục so sánh “số nhỏ nhất” với ai+2, ai+3, an-1, an {Xác định “số nhỏ nhất” bằng cách nắm được chỉ số của nó z Tinh chỉnh bước 1 j = i; for (k = i+1; k<n; k++) if(ak < aj) j = k;
31. Tinh chỉnh từng bước – Ví dụ zGiải thuật 2: Đổi chỗ ai và aj { Sử dụng một biến trung chuyển zTinh chỉnh bước 2.2 tmp = ai; ai = aj; aj = tmp;
32. Tinh chỉnh từng bước function SapXep(a, n) /* a là mảng các số nguyên n là số phần tử mảng */ { for(i = 0; i<n; i++) { /* 1. Tìm số nhỏ nhất */ j = i; for (k = i+1; k<n; k++) if(ak < aj) j = k+1; /* 2. Đổi chỗ */ tmp = ai; ai = aj; aj = tmp; } }
33. 3. Phân tích giải thuật zTại sao cần phân tích giải thuật ? {Viết một chương trình chạy thông là chưa đủ {Chương trình có thể thực hiện chưa hiệu quả! {Nếu chương trình chạy trên một tập dữ liệu lớn, thì thời gian chạy sẽ là một vấn đề cần lưu ý
34. Ví dụ: Bài toán lựa chọn zCho một dãy gồm N số, hãy tìm phần tử lớn thứ k,vớik ≤ N. zThuật toán 1: (1) Đọc N số vào một mảng (2) Sắp xếp mảng theo thứ tự giảm dần (3) Trả lại phần tửởvị trí thứ k
35. Ví dụ: Bài toán lựa chọn zThuật toán 2: (1) Đọc k phần tử đầu tiên vào mảng và sắp xếp chúng theo thứ tự giảm dần (2) Mỗi phần tử còn lại chỉ đọc một lần zNếu phần tử đólànhỏ hơn phần tử thứ k, bỏ qua zNgược lại, đặt nó vào vị trí phù hợp của mảng, đẩy phần tử hiện tại ra khỏi mảng. (3) Phần tử tại vị trí thứ k là phần tử cần tìm. 84 60 74 23 30 35 46 57 12 78
36. Ví dụ: Bài toán lựa chọn zThuật toán nào là tốt hơn khi {N =100 và k = 100? {N =100 và k = 1? zĐiều gì sẽ xảy ra khi N = 1,000,000 và k = 500,000? zCòn có những thuật toán tốt hơn
37. Phân tích thuật toán z Chúng ta chỉ phân tích những thuật toán đúng z Một thuật toán là đúng? {Nếu, với một dữ liệu đầu vào, thuật toán dừng và đưa ra kết quả đúng z Thuật toán không đúng {Có thể không dừng với một số dữ liệu đầu vào {Dừng nhưng đưa ra kết quả sai z Phân tích thuật toán {Dự đoán lượng tài nguyên mà thuật toán yêu cầu {Tài nguyên gồm zBộ nhớ zBăng thông giao tiếp zThời gian tính – Thời gian thực hiện GT (thường là quan trọng nhất)
38. Thời gian thực hiện giải thuật zCác nhân tốảnh hưởng đến thời gian tính {Máy tính {Chương trình dịch {Thuật toán được sử dụng {Dữ liệu đầu vào của thuật toán zGiá trị của dữ liệu ảnh hưởng đến thời gian tính zThông thường, kích thước của dữ liệu đầu vào là nhân tố chính quyết định thời gian tính • VD với bài toán sắp xếp ⇒ số phần tử sắp xếp • VD bài toán nhân ma trận ⇒ tổng số phần tử của 2 ma trận
39. Độ phức tạp về thời gian Thuật toán A mất 2 phút để chạy với dữ liệu đầu vào X. Thuật toán B mất 1 phút 45 giây để chạy với cùng dữ liệu X. Liệu B có phải là thuật toán “tốt hơn” A? Không hẳn là như vậy Chỉ kiểm tra với một bộ dữ liệu X. Có thể với dữ liệu X này B chạy nhanh hơn A, nhưng với phần lớn các dữ liệu khác B chạy chậm hơn A. Thuật toán A bị ngắt bởi các tiến trình khác. Thuật toán B được chạy trên máy tính có cấu hình cao hơn. Phép đo cần phải không phụ thuộc vào máy. Đo bằng cách đếm số các phép tính cơ sở (như phép gán, so sánh, các phép tính số học, vv.)
40. Ví dụ Bài toán Tính tổng các số nguyên từ 1 đến n. Thuật toán 1 int sum = 0; for (int i = 1; i <= n; i++) sum = sum + i; Thuật toán 2 int sum = ((n+1)*n) / 2;
41. Trường hợp tồi nhất / trung bình / tốt nhất zThêi gian tÝnh tèt nhÊt: Thêi gian tèi thiÓu cÇn thiÕt ®Ó thùc hiÖn thuËt to¸n víi mäi bé dữ liÖu ®Çu vµo kÝch th-íc n. zThêi gian tÝnh tåi nhÊt: Thêi gian nhiÒu nhÊt cÇn thiÕt ®Ó thùc hiÖn thuËt to¸n víi mäi bé d÷ liÖu ®Çu vµo kÝch th-íc n. zThêi gian trung bình: cÇn thiÕt ®Ó thùc hiÖn thuËt to¸n trªn tËp hữu h¹n c¸c ®Çu vµo kÝch th-íc n.
42. Thời gian tính phụ thuộc vào kích thước dữ liệu đầu vào Điều quan trọng đối với giải thuật là mất bao nhiêu giây để chạy với dữ liệu đầu vào có kích thước n. tốc độ thay đổi của thời gian tính khi n tăng. Thuật toán có thời gian hằng số nếu thời gian chạy của nó là không đổi khi kích thước dữ liệu thay đổi. Thuật toán có thời gian tuyến tính nếu thời gian chạy của nó tỷ lệ thuận với n. Thuật toán có thời gian tính hàm số mũ nếu thời gian chạy tăng theo một hàm số mũ của n.
43. Tỉ suất tăng trưởng z Thiết lập một thứ tự tương đối cho các hàm với đầu vào n lớn z ∃ c , n0 > 0 sao cho f(n) ≤ c g(n) khi n ≥ n0 z f(n) tăng không nhanh bằng g(n) khi n “lớn”
44. Khái niệm O-lớn Một thuật toán là O(f(n))=g(n) nếu tồn tại một hằng số C > 0 và số nguyên n0 sao cho thuật toán yêu cầu không vượt quá C• g(n) phép tính có tất cả các dữ liệu đầu vào có kích thước n ≥ n0. Thuật toán 1 cần4n + 3 phép tính. int sum = 0; for (int i = 1; i <= n; i++) sum = sum + i;
45. Khái niệm O-lớn Cg(n) f(n) f(n) = O(g(n)) n0 O-lớn quan tâm đến tỉ suất tăng trưởng của thời gian tính khi n →∞. Nó không quan tâm khi dữ liệu đầu vào có kích thước nhỏ Hàm g(n) trong O(g(n)) là hàm để so sánh với các thuật toán khác
46. Nhắc lại một số hàm logarit a x= b ⇔ logbx = a logab= loga + b log logm b loga b = logm a logab = blog a alogn = nloga logab =(log a)b ≠log b a d ln x 1 = dx x
47. Một số quy tắc của O-lớn O-lớn bỏ qua các giá trị có bậc thấp hơn. Các bậc thấp hơn thường được tính bởi các bước khởi tạo phép tính đơn giản O-lớn không tính đến hệ số nhân Đây thường là khái niệm phụ thuộc vào máy tính Không cần chỉ ra cơ số của hàm logarit Hoàn toàn có thể thay đổi cơ số của hàm logarit bằng cách nhân với một hằng số
48. Thứ hạng của O-lớn nhanh nhất O(1) thời gian hằng số O(log n) thời gian logarit O(n) thời gian tuyến tính O(n log n) O(n2 ) bình phương O(n2 log n) O(n3 ) mũ 3 O(2n ) hàm số mũ n chậm nhất O(n!) giai thừa
49. Sự tăng trưởng của hàm? Thuật toán 1 2 3 4 5 Thời gian (ms.) 33n 46 n log n 13n 2 3.4 n 3 2 n KT đầu vào (n) Thời gian thực tế 10 .00033 sec. .0015s .0013s .0034s .001s 100 .003s .03s .13s 3.4s 4 • 10 yr. 1,000 .033s .45s 13s .94hr 10,000 .33s 6.1s 22 min 39 days 100,000 3.3s 1.3 min 1.5 days 108 yr. T/g cho phép Kích thước dữ liệu tối đa 1 sec. 30,000 2,000 280 67 20 1 min. 1,800,000 82,000 2,200 260 26
50. Khái niệm Omega-lớn z ∃ c , n0 > 0 sao cho f(n) ≥ c g(n) khi n ≥ n0 z f(n) tăng không chậm hơng(n)với N “lớn”
51. Khái niệm Omega-lớn zf(n) = Ω(g(n)) zTồn tại một hằng số dương c và n0 sao cho f(n) ≥ c g(n) khi n ≥ n0 zTỉ suất tăng củaf(n)thìlớn hơn hoặc bằng tỉ suất tăng của g(n).
52. Khái niệm Theta-lớn z Tỉ suất tăng củaf(n)bằng tỉ suất tăng củag(n)
53. Theta-lớn z f(n) = Θ(g(n)) nếu và chỉ nếu f(n) = O(g(n)) and f(n) = Ω(g(n)) z Tỉ suất tăng củaf(n)bằng tỉ suất tăng của g(n) z Ví dụ:f(N)=N2 , z Theta-lớnlàcận chặt nhất có thể.
54. Một số quy tắc zNếuT(N) làmột đa thức bậc k, thì T(N) = Θ(Nk). zVới các hàm logarit, T(logm N) = Θ(log N).
55. Ví dụ: z t(n) = 90 n2 + 9n + 9 { Do 60n2 + 9n + 9 ≤ 60 n2 + 9n2 + n2 = 70 n2 với mọi n ≥ 1, Chọn C1 = 70 60n2 + 9n + 9 = O(n2). { Do 60n2 + 9n + 9 ≥ 60 n2 với mọi n ≥ 1, Chọn C2=60 60n2 + 9n + 9 = Ω (n2). { Do 60n2 + 9n + 9 = O(n2) và 60n2 + 9n + 9 = Ω (n2) nên 60n2 + 9n + 9 = Θ(n2).
56. Quy tắc L' Hopital z Quy tắc L' Hopital {Nếuvlimf N (= ∞ ) àlimg N (= ∞ ) →n ∞ →n ∞ f() N f()′ N thì lim = lim →n g ∞() N →n g ∞ ()′ N z Quyết định tỉ suất tăng tương đốs i(ử dụng quy tắ ' cL Hopital khi cần thiết) f() N {Tính lim →n g ∞() N {0: f(N) = O(g(N)) và f(N) k phải là Θ(g(N)) {Hằng số ≠ 0: f(N) = Θ(g(N)) {∞: f(N) = Ω(f(N)) và f(N) k phải là Θ(g(N)) {không xác định: không có mối quan hệ gì
57. Xác định độ phức tạp về thời gian Nếu T1(n) = O(f(n)) and T2(n) = O(g(n)) thì zQuy tắc tổng: T1(n) + T2(n) = O(f(n)+g(n)) = max(O(f(n)),O(g(n))) = O(max(f(n), g(n))) zQuy tắc nhân: T1(n) * T2(n) = O(f(n) * g(n))
58. Xác định độ phức tạp thời gian zVới vòng lặp {là thời gian chạy của các câu lệnh bên trong vòng lặp (kể cả lệnh kiểm tra điều kiện) nhân với số lần lặp. zCác vòng lặp lồng nhau {là thời gian chạy của câu lệnh nhân với tích của các kích thước của tất cả vòng lặp.
59. Xác định độ phức tạp thời gian zCác câu lệnh kế tiếp {Thực hiện tính tổng {O(N) + O(N2) = O(N2) z If S1 Else S2 {thời gian của lệnh kiểm tra điều kiện + thời gian tính lớn hơn trong S1 và S2.