Bài giảng Phân tích và thiết kế giải thuật: Chương 1 - PGS.TS. Dương Tuấn Anh

Bài giảng chương 1 trình bày các khái niệm căn bản trong phân tích và thiết kế giải thuật. Các nội dung cụ thể trong chương gồm có: Đệ quy và hệ thức truy hồi, phân tích độ phức tạp giải thuật, phân tích giải thuật lặp, phân tích giải thuật đệ quy, chiến lược thiết kế giải thuật, thiết kế giải thuật kiểu “trực tiếp” (Bruce-force). Mời các bạn cùng tham khảo.
Nội dung trích xuất từ tài liệu:
Bài giảng Phân tích và thiết kế giải thuật: Chương 1 - PGS.TS. Dương Tuấn AnhMôn học:Phân tích và Thiết kế Giải thuậtSố tín chỉ: 3 BÀI GIẢNG ĐIỆN TỬ Biênsoạnbởi:PGS.TS.DươngTuấnAnh KhoaKhoaHọcvàKỹThuậtMáyTính TrườngĐ.H.BáchKhoa ĐạihọcQuốcGiaTpHồChíMinh 1Tài liệu tham khảo[1] Cormen, T. H., Leiserson, C. E, and Rivest, R. L.,Introduction to Algorithms, The MIT Press, 1997.[2] Levitin, A., Introduction to the Design and Analysisof Algorithms, Addison Wesley, 2003[3] Sedgewick, R., Algorithms in C++, Addison-Wesley, 1998[4] Weiss, M.A., Data Structures and AlgorithmAnalysis in C, TheBenjamin/Cummings Publishing,1993 2Đề cương Môn học1. Các khái niệm căn bản2. Chiến lược chia-để-trị3. Chiến lược giảm-để-trị4. Chiến lược biến thể-để-trị5. Qui hoạch động và giải thuật tham lam6. Giải thuật quay lui7. Vấn đề NP-đầy đủ8. Giải thuật xấp xỉ 3 Mônhọc:Phântíchvàthiếtkếgiảithuật Chương 1 CÁC KHÁI NIỆM CĂN BẢN 4Nội dung1. Đệ quy và hệ thức truy hồi2. Phân tích độ phức tạp giải thuật3. Phân tích giải thuật lặp4. Phân tích giải thuật đệ quy5. Chiến lược thiết kế giải thuật6. Thiết kế giải thuật kiểu “trực tiếp” (bruce-force) 51. Đệ quyHệthứctruyhồiThídụ1:HàmtínhgiaithừaN!=N.(N1)! vớiN 1 0!=1Nhữngđịnhnghĩahàmđệquymàchứanhữngđốisốnguyênđượcgọilànhữnghệthứctruyhồi(recurrencerelation).functionfactorial(N:integer):integer;beginifN=0thenfactorial:=1elsefactorial:=N*factorial(N1);end; 6Hệ thức truy hồiThídụ2:SốFibonacciHệthứctruyhồi:FN=FN1+FN2 forN 2 F0=F1=11,1,2,3,5,8,13,21,…functionfibonacci(N:integer):integer;beginifNSố Fibonacci – Cây đệ quy computed Có nhiều tính toán dư thừa khi tính số Fibonacci bằng hàm đệ quy. 8Mộtcáchkhác:Tacóthểdùngmộtmảngđểchứanhữngtrịsốđitrướctrongkhitínhhàmfibonacci.Tacómộtgiảithuậtkhôngđệquy.procedure fibonacci; Giải thuật không đệ quyconst max = 25; thường làm việc hữu hiệuvar i: integer; và dễ kiểm soát hơn 1 giảiF: array [0..max] of integer; thuật đệ quy.begin F[0]: = 1; F[1]: = 1; Nhờ vào sử dụng stack, ta for i: = 2 to max do có thể chuyển đổi một giải F[i]: = F[i-1] + F[i-2] thuật đệ quy thành một giảiend; thuật lặp tương đương. 92. Phân tích độ phức tạp giải thuậtVớiphầnlớncácbàitoán,thườngcónhiềugiảithuậtkhácnhauđểgiảimộtbàitoán.Làmcáchnàođểchọngiảithuậttốtnhấtđểgiảimộtbàitoán?Làmcáchnàođểsosánhcácgiảithuậtcùnggiảiđượcmộtbàitoán?Phântíchđộphứctạpcủamộtgiảithuật:dựđoáncáctàinguyênmàgiảithuậtđócần.Tàinguyên:Chỗbộnhớ ThờigiantínhtoánThờigiantínhtoánlàtàinguyênquantrọngnhất. 10Hai cách phân tíchThờigiantínhtoáncủamộtgiảithuậtthườnglà mộthàmcủakíchthướcdữliệunhập.Chúngtaquantâmđến: Trườnghợptrungbình(averagecase):thờigian tínhtoánmàmộtgiảithuậtcầnđốivớimột “dữliệunhâpthôngthường”(typicalinput data). Trườnghợpxấunhất(worstcase):thờigian tínhtoánmàmộtgiảithuậtcầnđốivớimột “dữliệunhâpxấunhất” 11Khung thức của sự phân tích Bước1:Đặctrưnghóadữliệunhậpvàquyếtđịnhkiểuphântíchthíchhợp.Thôngthường,tatậptrungvàoviệcchứngminhrằngthờigiantínhtoánluônnhỏhơnmột“cậntrên”(upperbound),haydẫnxuấtrathờigianchạytrungbìnhđốivớimộtdữliệunhậpngẫunhiên. Bước2:nhậndạngthaotáctrừutượng(abstractoperation)màgiảithuậtdựavàođólàmviệc. Thídụ:thaotácsosánhtronggiảithuậtsắpthứtự.Tổngsốthaotáctrừutượngthườngtùythuộcvàomộtvàiđạilượng. Bước3:thựchiệnphântíchtoánhọcđểtìmracácgiátrịtrungbìnhvàgiátrịxấunhấtcủacácđạilượngquantrọng. 12Hai trường hợp phân tích • Thườngthìkhôngkhóđểtìmracậntrêncủathời giantínhtoáncủamộtgiảithuật. • Nhưngphântíchtrườnghợptrungbìnhthườngđòi ...