Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 1: Cấu trúc dữ liệu và giải thuật - Ngô Công Thắng
1. Mối quan hệ giữa cấu trúc dữ liệu và giải thuật
1.1. Giải thuật (thuật toán, algorithms)
l Khái niệm: Giải thuật là một hệ thống các thao
tác, các phép toán được thực hiện theo trình tự
nhất định trên một số đối tượng dữ liệu nào đó,
sao cho sau một số bước hữu hạn ta có được
kết quả mong muốn.
l Giải thuật phản ánh các phép xử lý, còn đối
tượng xử lý là dữ liệu.
Trang 1
Trang 2
Trang 3
Trang 4
Trang 5
Trang 6
Trang 7
Trang 8
Trang 9
Trang 10
Tải về để xem bản đầy đủ
Bạn đang xem 10 trang mẫu của tài liệu "Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 1: Cấu trúc dữ liệu và giải thuật - Ngô Công Thắng", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
Tóm tắt nội dung tài liệu: Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 1: Cấu trúc dữ liệu và giải thuật - Ngô Công Thắng
ột giải thuật phải được biểu diễn như một hàm của n: T(n) l Các kiểu lệnh, tốc độ xử lý của máy tính, ngôn ngữ viết chương trình, chương trình dịch cũng ảnh hưởng đến tốc độ thực hiện. Nhưng những yếu tố này không đồng đều với mỗi loại máy tính, vì vậy không thể đưa chúng vào xác lập T(n). Điều đó cũng có nghĩa là T(n) không thể tính theo đơn vị giây, phút Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 01 1.19 3.2.3. Độ phức tạp tính toán của giải thuật l Cách đánh giá thời gian thực hiện giải thuật không phụ thuộc vào máy tính và các yếu tố liên quan mà chỉ phụ thuộc vào kích thước dữ liệu đầu vào được gọi là đánh giá theo “Độ phức tạp tính toán của giải thuật”. l Nếu thời gian thực hiện một giải thuật là T(n) = Cn2, trong đó C là hằng số, thì ta nói độ phức tạp tính toán của giải thuật này có cấp n2, và được kí hiệu là: T(n)= O(n2) l Tổng quát: Hàm f(n) có độ phức tạp tính toán cấp g(n), kí hiệu là f(n) = O(g(n)), nếu tồn tại các hằng số C và n0 sao cho: f(n) ≤ Cg(n) với n ³ n0 nghĩa là hàm f(n) bị chặn trên bởi Cg(n), với C là hằng số và với mọi n từ một điểm nào đó. l Ví dụ 1: f(n) = O(n3) có nghĩa độ phức tạp tính toán cấp n3 l Ví dụ 2: f(n) = O(2n) có nghĩa độ phức tạp tính toán cấp 2n Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 01 1.20 3.2.3. Độ phức tạp tính toán của giải thuật (tiếp) l Các hàm thể hiện độ phức tập tính toán của giải thuật có các dạng sau: nn, n!, 2n, n3, n2, nlog2n, n, log2n. Các hàm này đã được sắp theo giá trị giảm dần, có nghĩa là với cùng một giá trị của n, hàm nn là lớn nhất, log2n là nhỏ nhất. Các hàm này có dạng đồ thị như sau: Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 01 1.21 3.2.3. Độ phức tạp tính toán của giải thuật (tiếp) l Các hàm nn , n! , 2n gọi là các hàm mũ. Một gíải thuật có độ phức tạp tính toán cấp hàm mũ thì rất chậm, do đó khó được chấp nhận. l Các hàm n3, n2, nlog2n, n, log2n là các hàm loại đa thức. Độ phức tạp tính toán của giải thuật có cấp đa thức thì chấp nhận được. Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 01 1.22 3.2.4. Xác định độ phức tạp tính toán l Quy tắc cộng: l Giả sử T1(n) và T2(n) là thời gian thực hiện 2 đoạn chương trình P1 và P2 mà T1(n)= O(f(n)), T2(n)=O(g(n)), thì thời gian thực hiện P1 rồi đến P2 tiếp theo sẽ là: T1(n) + T2(n) = O(max(f(n),g(n))) l Ví dụ: Chương trình có 3 bước, mỗi bước có độ phức tạp tính toán lần lượt là O(n3), O(n), O(nlog2n). Vậy thời gian thực hiện 3 bước là: T1(n) + T2(n) + T3(n) = O(max(n3, n, nlog2n) = O(n3) Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 01 1.23 3.2.4. Xác định độ phức tạp tính toán (tiếp) l Quy tắc nhân: l Nếu tương ứng với 2 bước P1 và P2 là T1(n) = O(f(n)),T2(n) = O(g(n)) thì thời gian thực hiện P1 và P2 lồng nhau là : T1(n).T2(n) = O(f(n).g(n)) l Ví dụ: Câu lệnh x:=x+1 có thời gian thực hiện bằng hằng số C => T(n) =O(1) Câu lệnh: For i :=1 To n Do x :=x+1; có thời gian thực hiện là: T(n)=O(n.1)=O(n) Câu lệnh For i :=1 To n Do For j :=1 To n Do x:=x+1; có thời gian thực hiện được đánh giá là: T(n)= O(n.n) = O(n2) Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 01 1.24 3.2.4. Xác định độ phức tạp tính toán (tiếp) l Quy tắc bỏ hằng số l O(c.f(n)) = O(f(n), trong đó c là một hằng số. l Ví dụ: O(n2/3) = O(n2) l Chú ý 1: Khi đánh giá thời gian thực hiện giải thuật ta chỉ cần chú ý tới các bước tương ứng với một phép toán được gọi là phép toán tích cực. Đó là phép toán mà thời gian thực hiện nó không ít hơn thời gian thực hiện các phép toán khác. Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 01 1.25 3.2.4. Xác định độ phức tạp tính toán (tiếp) l Các bước xác định O của một giải thuật: B1: Xác định phép toán tích cực trong giải thuật. B2: Đếm số lần thực hiện phép toán tích cực, biểu diễn số đếm này thành một hàm phụ thuộc vào kích thước dữ liệu đầu vào n, f(n) B3: Coi O(f(n)), sử dụng định nghĩa O và các quy tắc xác định O để tìm ra O cuối cùng. Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 01 1.26 3.2.4. Xác định độ phức tạp tính toán (tiếp) l Ví dụ: ex = 1+ x/1! + x2/2! + . . .+ xn/n! với x và n cho trước. l Giải thuật 1: 1) Read(x,n); s:=1; 2) For i :=1 To n Do begin p:=1; For j :=1 To i Do p:=p*x/j ; s:=s+p; end; end. Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 01 1.27 3.2.4. Xác định độ phức tạp tính toán (tiếp) l Trong giải thuật 1 phép toán tích cực ở đây là p:=p*x/j. Ta thấy nó được thực hiện với số lần là: 1+2+3+ . . . + n = n(n+1)/2 Vậy thời gian thực hiện giải thuật là: T(n) = O(n2) Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 01 1.28 3.2.4. Xác định độ phức tạp tính toán (tiếp) l Giải thuật 2: 1) Read(x,n); s:=1; p:=1; 2) For i :=1 To n Do begin p:=p*x/i; s:=s+p; end; end. Thời gian thực hiện giải thuật 2 là: T(n) = O(n) Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 01 1.29 3.2.4. Xác định độ phức tạp tính toán (tiếp) l Giải thuật 3: 1) Read(x); s:=1; p:=1; i:=0; 2) Repeat i:=i+1; p:=p*x/i; s:=s+p; Until | p | < Epsilon; end. 3) Write(s); Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 01 1.30 3.2.4. Xác định độ phức tạp tính toán (tiếp) l Chú ý 2: Có những trường hợp thời gian thực hiện giải thuật không chỉ phụ thuộc vào kích thước của dữ liệu vào mà còn phụ thuộc vào chính tình trạng của dữ liệu đó nữa. l Khi phân tích thời gian thực hiện giải thuật ta phải xét xem với mọi dữ liệu vào có kích thước n thì T(n) trong trường hợp thuận lợi nhất, trường hợp trung bình và trường hợp xấu nhất như thế nào? l Việc xác định T(n) trong trường hợp trung bình thường khó vì phải dùng tới những công cụ toán đặc biệt. Bởi vậy người ta thường đánh giá giải thuật bằng T(n) trong trường hợp xấu nhất. Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 01 1.31 3.2.4. Xác định độ phức tạp tính toán (tiếp) l Ví dụ: Cho véc tơ a có n phần tử a1, a2,..., an. Tìm trong a phần tử đầu tiên có giá trị = x cho trước. l Giải thuật như sau: Found := False; i:=1; While (i<=n) and Not Found Do If a[i] =x then begin Found:=True; k:=i; Write(k); end else i:=i+1; End. T(n) trong trường hợp tốt T(n)=O(1) T(n) trong trường hợp xấu T(n)=O(n) . Vây suy ra T(n)=O(n) Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 02 2.32 4. Giải thuật đệ quy 4.1. Khái niệm đệ quy l Ta nói một đối tượng là đệ quy nếu nó được định nghĩa dưới dạng chính nó. l Ví dụ 1: Trên màn hình của vô tuyến truyền hình lại xuất hiện hình ảnh của chính cái màn hình vô tuyến đó. l Ví dụ 2: Trong toán học hay gặp định nghĩa đệ quy: 1. Định nghĩa số tự nhiên a) x là số tự nhiên nếu x-1 là số tự nhiên b) 1 là số tự nhiên 2. Hàm n! a) n! = n*(n-1)! nếu n>0 b) n!=1 nếu n=0 Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 02 2.33 4.2. Giải thuật đệ quy và thủ tục đệ quy l Nếu lời giải của một bài toán T được thực hiện bằng lời giải của bài toán T’ có dạng giống như T thì đó là một lời giải đệ quy. Trong đó T’ tuy giống T nhưng nó phải nhỏ hơn T. l Giải thuật tương ứng với lời giải đệ quy gọi là giải thuật đệ quy. l Thủ tục viết cho bài toán có giải thuật đệ quy gọi là thủ tục đệ quy. Trong thủ tục đệ quy có lời gọi tới chính nó, mỗi lần gọi thì kích thước bài toán thu nhỏ hơn và dần dần tiến tới trường hợp đặc biệt là trường hợp suy biến. Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 02 2.34 Ví dụ: Bài toán tìm 1 từ trong cuốn từ điển l Giải thuật đệ quy của bài toán này như sau: IF từ điển là một trang THEN tìm từ trong trang ấy ELSE BEGIN Mở từ điển vào trang giữa; Xác định xem nửa nào chứa từ IF từ nằm trong nửa trước THEN tìm trong nửa trước ELSE tìm trong nửa sau END Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 02 2.35 Ví dụ: Bài toán tìm 1 từ trong cuốn từ điển l Trong giải thuật này có 2 điểm cần chú ý: l Điểm 1: Sau mỗi lần từ điển được tách đôi, một nửa thích hợp sẽ được tìm kiếm theo chiến thuật đã dùng. l Điểm 2: Có trường hợp đặc biệt là sau khi tách đôi từ điển chỉ còn 1 trang, giải quyết trực tiếp bằng cách tìm từ trong trang đó. Trường hợp đặc biệt này gọi là trường hợp suy biến. l Giải thuật này gọi là giải thuật chia đôi: Bài toán được tách đôi ra bài toán nhỏ hơn, bài toán nhỏ hơn lại dùng chiến thuật chia đôi, cho tới khi gặp trường hợp suy biến. Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 02 2.36 Ví dụ: Bài toán tìm 1 từ trong cuốn từ điển l Thủ tục đệ quy của bài toán được viết như sau: Procedure timkiem(Tudien, tu) IF Tudien chỉ còn một trang THEN tìm từ trong trang ấy ELSE BEGIN Mở từ điểm vào trang giữa Xác định xem nửa nào chứa từ IF Từ nằm ở nửa trước THEN CALL timkiem(Tudien1, tu) ELSE CALL timkiem(Tudien2, tu) END RETURN Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 02 2.37 4.3. Thiết kế giải thuật đệ quy l Khi bài toán đang xét hoặc dữ liệu đang xử lý được định nghĩa dưới dạng đệ quy thì việc thiết kế các giải thuật đệ quy tỏ ra rất thuận lợi. l Khi thiết kế giải thuật đệ quy cần trả lời các câu hỏi sau: 1. Có thể định nghĩa bài toán dưới dạng một bài toán cùng loại nhưng có quy mô nhỏ hơn. 2. Có trường hợp đặc biệt của bài toán (trường hợp suy biến) mà ở đó kết thúc đệ quy. Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 02 2.38 Bài toán 1: Tính n! l Định nghĩ đệ quy của hàm n! như sau: GiaiThua(n) = 1 nếu n=0 GiaiThua(n)=n´GiaiThua(n-1) nếu n>0 Thuật giải đệ quy được viết dưới dạng hàm: Function GiaiThua(n) If n=0 then begin GiaiThua :=1; return; end Else GiaiThua := n * GiaiThua(n-1); Return Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 02 2.39 Bài toán 1: Tính n! l Khử đệ quy của hàm tính giai thừa: Function FAC(n) If n=0 then gt:=1; Else begin gt:=1; For i:=1 to n do gt:=gt*I; end; FAC:=gt; Return Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 02 2.40 Bài toán 1: Tính n! l Đối chiếu với 3 đặc điểm của thủ tục đệ quy ta thấy: l Lời gọi tới chính nó đứng sau Else l Mỗi lần gọi đệ quy giá trị giảm đi: FAC(4)®FAC(3)®FAC(2)® FAC(1) l Trường hợp suy biến là FAC(0): FAC(0) = 1 Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 02 2.41 Bài toán 2: Lập dãy số FIBONACCI 1 1 2 3 5 8 13... l Định nghĩa F(n) như sau: F(n) = 1 nếu n £ 2 F(n)=F(n-2)+F(n-1) nếu n>2 l Thủ tục đệ quy thể hiện giải thuật tính F(n) như sau: Function F(n:integer) If n<=2 then F:=1 Else F:=F(n-2)+F(n-1) Return Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 02 2.42 Bài toán 3: Bài toán “Tháp Hà nội” l Nội dung: Có n đĩa kích thước nhỏ dần, đĩa có lỗ ở giữa. Có thể xếp chồng chúng lên nhau xuyên qua một cái cọc, to dưới nhỏ trên để cuối cùng có một chồng đĩa dạng như hình tháp. Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 02 2.43 Bài toán 3: Bài toán “Tháp Hà nội” l Yêu cầu đặt ra: Chuyển chồng đĩa từ cọc A sang cọc C theo những điều kiện sau: l Mỗi lần chỉ được chuyển một đĩa l Không khi nào có tình huống đĩa to ở trên đĩa nhỏ ở dưới l Được phép sử dụng 1 cọc trung gian (cọc B) để đặt tạm thời. Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 02 2.44 Bài toán 3: Bài toán “Tháp Hà nội” l Ta xét một vài trường hợp đơn giản: l Trường hợp 1 đĩa: lChuyển từ cọc A sang cọc C l Trường hợp 2 đĩa: lChuyển đĩa thứ nhất từ cọc A sang cọc B lChuyển đĩa thứ hai từ cọc A sang cọc C lChuyển đĩa thứ nhất từ cọc B sang cọc C Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 02 2.45 Bài toán 3: Bài toán “Tháp Hà nội” l Trường hợp n đĩa (n>2): Ta coi n-1 đĩa ở trên như đĩa thứ nhất và xử lý giống như trường hợp 2 đĩa: l Chuyển n-1 đĩa từ cọc A sang cọc B l Chuyển đĩa thứ n từ cọc A sang cọc C l Chuyển n-1 đĩa từ cọc B sang cọc C l Chuyển n-1 đĩa từ cọc B sang cọc C thuật giải sẽ là: l Chuyển n-2 đĩa từ cọc B sang cọc A l Chuyển 1 đĩa từ cọc B sang cọc C l Chuyển n-2 đĩa từ cọc B sang cọc C l Cứ làm như vậy cho đến khi trường hợp suy biến xảy ra, đó là trường hợp ứng với bài toán chuyển 1 đĩa. Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 02 2.46 Bài toán 3: Bài toán “Tháp Hà nội” l Thủ tục của bài toán “Tháp Hà nội” như sau: Procedure Hanoi(n,A,B,C) If n=1 then chuyển đĩa từ A sang C Else Begin Call Hanoi(n-1,A,C,B) Call Hanoi(1,A,B,C) Call Hanoi(n-1,B,A,C) End; Return Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 02 2.47 Bài tập 1. Thế nào là giải thuật đệ quy? 2. Ưu nhược điểm của giải thuật đệ quy? 3. Trong bộ nhớ của máy tính dùng vùng nhớ nào để dùng cho giải thuật đệ quy. 4. Trường hợp suy biến là trường hợp như thế nào trong giải thuật đệ quy. 5. Thường hay dùng cấu trúc lập trình nào để thể hiện giải thuật đệ quy 6. Viết giải thuật đệ quy cho bài toán sau: Acker(m,n)= n+1 nếu m=0 Acker(m,n)= Acker(m-1,1) nếu n=0 Acker(m,n)= Acker(m-1,Acker(m,n-1)) với các trường hợp khác. Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 02 2.48 Thủ tục đệ quy Bài 6 Function Acker(m,n:integer) If m=0 then Acker:=n+1 else if n=0 then Acker:=Acker(m-1,1) else Acker:=Acker(m-1,Acker(m,n-1)) Return Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 02 2.49 Bài tập (tiếp) 7. Giải thuật tính ước số chung lớn nhất của hai số nguyên dương a và b (a>b) như sau: Gọi r là số dư của phép chia a cho b. - Nếu r=0 thì b là ước số chung lớn nhất - r khác 0 thì gán a:=b; b:=r rồi lặp lại. Hãy xây dựng giải thuật đệ quy tính ước số chung lớn nhất USCLN(a,b) Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 02 2.50 Thủ tục đệ quy bài 7 Bài toán: Tìm USCLN của 2 số nguyên dương a,b Cách 1: Dùng đệ quy Function USCLN(a,b) If b=0 then begin USCLN := a; return; end; If b # 0 then USCLN := USCLN(b,a mod b); Return Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 02 2.51 Thủ tục đệ quy bài 7 Bài toán: Tìm USCLN của 2 số nguyên dương a,b Cách 2: Khử đệ quy Function USCLN(a,b) 1) r := a mod b; 2) while r # 0 do begin a:=b; b:=r; r:= a mod b end; 3) USCLN:=b; Return Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 02 2.52 Bài tập (tiếp) 8. Hàm C(n,k) với n, k là các giá trị nguyên không âm và k<=n, được định nghĩa như sau: C(n,n)=1 C(n,0)=1 C(n,k)=C(n-1,k-1)+C(n-1,k) nếu 0< k<n Hãy xây dựng giải thuật đệ quy cho bài toán trên 9. Viết thủ tục đệ quy in ngược một dòng kí tự cho trước. Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 02 2.53 Thủ tục đệ quy bài 8 Function C(n,k:integer) If k=0 then C:=1 else if k=n then C:=1 else C:=C(n-1,k-1)+C(n-1,k); Return
File đính kèm:
- bai_giang_cau_truc_du_lieu_va_giai_thuat_chuong_1_cau_truc_d.pdf