Tài liệu

Bài giảng môn học phân tích và thiết kế thuật toán

Chia sẻ bởi
Lượt xem: 2436     Tải về: 16     Lượt mua: 0     Định dạng:  
Báo lỗi
Bình luận
Nhúng
/ 48
Tài liệu Bài giảng môn học phân tích và thiết kế thuật toán - tài liệu, sách iDoc.VnBài giảng môn học phân tích và thiết kế thuật toán,Học phần “Thuật toán và đánh giá độ phức tạp thuật toán” được viết cho sinh viên khoa CNTT sau khi đã  học xong các học phần: CẤU…
1
B GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC PHƯƠNG ĐÔNG
KHOA CÔNG NGH THÔNG TIN
--------------------------
BÀI GING MÔN HC
PHÂN TÍCH VÀ THI
T K THUT TOÁN
HÀ N
I, 2008
2
Mục lục
Mục lục..................................................................................................................................2
L
ời nói đầu............................................................................................................................4
Ch
ương I: Mở đầu về thiết kế, đánh giá thuật toán và kiến thức bổ trợ..........................5
Giới thiệu chương ............................................................................................................5
1.1. Khái ni
ệm thuật toán .................................................................................................5
1.1.1. Khái niệm về thuật toán ............................................................................................5
1.1.2. Các yêu cầu về thuật toán ........................................................................................6
1.2. Thiết kế thuật toán.....................................................................................................7
1.3. Tính đúng đắn của thuật toán...................................................................................7
1.4. Phân tích thu
ật toán ..................................................................................................8
1.5. Đánh giá hiệu quả của thuật toán.............................................................................8
1.6. Các ph
ương pháp biểu diễn thuật toán ...................................................................8
1.6.1. Phương pháp liệt kê từng bước ...............................................................................9
1.6.2. Phương pháp sơ đồ..................................................................................................9
1.7. Một số cấu trúc dữ liệu cơ bản...............................................................................10
1.7.1. Danh sách ...............................................................................................................10
1.7.2. Đồ thị .......................................................................................................................12
1.7.3. Cây ..........................................................................................................................12
1.7.4. Tập hợp...................................................................................................................15
1.8. Ngôn ngữ tựa Pascal...............................................................................................16
1.8.1. Bảng chữ cái và ký tự chủ yếu ...............................................................................16
1.8.2. Một số câu lệnh chính .............................................................................................16
Bài tập chương ...............................................................................................................20
Chương II: Độ phức tạp tính toán và tính hiệu quả của thuật toán................................21
2.1 TỔNG QUAN..............................................................................................................21
2.1.1. Mục tiêu ...................................................................................................................21
2.1.2. Kiến thức cơ bản cần thiết......................................................................................21
2.1.3. Nội dung cốt lõi........................................................................................................21
2.2. SỰ CẦN THIẾT PHẢI PHÂN TÍCH THUẬT TOÁN....................................................21
2.3 TH
ỜI GIAN THỰC HIỆN CỦA CHƯƠNG TRÌNH..................................................22
2.3.1. Thời gian thực hiện chương trình...........................................................................22
2.3.2 Ðơn vị đo thời gian thực hiện...................................................................................22
2.3.3. Thời gian thực hiện trong trường hợp xấu nhất.....................................................23
Liên hệ quảng cáo

3
2.4. TỶ SUẤT TĂNG VÀ ÐỘ PHỨC TẠP CỦA GIẢI THUẬT...........................................23
2.4.1. Tỷ suất tăng.............................................................................................................23
2.4.2. Khái niệm độ phức tạp của giải thuật .....................................................................23
2.5. CÁCH TÍNH ÐỘ PHỨC TẠP .....................................................................................24
2.5.1. Qui tắc cộng ............................................................................................................24
2.5.2. Qui tắc nhân............................................................................................................24
2.5.3. Qui tắc tổng quát để phân tích một chương trình ..................................................24
2.5.4. Ðộ phức tạp của chương trình có gọi chương trình con không đệ qui..................26
2.6. PHÂN TÍCH CÁC CHƯƠNG TRÌNH ÐỆ QUY...........................................................27
2.6.1. Thành lập phương trình đệ quy ..............................................................................28
2.6.2. Giải phương trình đệ quy........................................................................................31
2.7. TỔNG KẾT CHƯƠNG...............................................................................................37
BÀI T
ẬP CHƯƠNG..........................................................................................................37
Chương III: Phương pháp “Tham lam” ............................................................................39
3.1. Đặc trưng của chiến lược tham lam ..........................................................................39
3.1.1 Bài toán ti ưu t hp............................................................................................39
3.1.2 N
i dung kĩ thuật tham ăn .....................................................................................39
3.1.3. Đặc tính la chn tham lam .................................................................................40
3.1.4. C
u trúc con ti ưu...............................................................................................40
3.2. Sơ đồ chung của phương pháp.................................................................................40
3.2.1. Đặc điểm chung ca thut toán tham lam...........................................................40
3.2.2. S
ơ đồ thut toán ...................................................................................................41
3.2.3. Ch
ứng minh tính đúng đắn ..................................................................................42
3.3. Bài toán trả tiền của máy rút tiền tự động ATM ........................................................42
3.4. Bài toán v
ề các đoạn thẳng không giao nhau...........................................................43
3.5. Bài toán cái túi.............................................................................................................46
Liên hệ quảng cáo

Liên hệ quảng cáo

Liên hệ quảng cáo

Liên hệ quảng cáo

Liên hệ quảng cáo

Liên hệ quảng cáo

Liên hệ quảng cáo

Liên hệ quảng cáo

Liên hệ quảng cáo

Liên hệ quảng cáo

Liên hệ quảng cáo

Liên hệ quảng cáo

Liên hệ quảng cáo

Liên hệ quảng cáo

Liên hệ quảng cáo

Liên hệ quảng cáo

Liên hệ quảng cáo

Liên hệ quảng cáo

Liên hệ quảng cáo

Liên hệ quảng cáo

Liên hệ quảng cáo

Liên hệ quảng cáo

Liên hệ quảng cáo

Liên hệ quảng cáo

Liên hệ quảng cáo

Liên hệ quảng cáo

Liên hệ quảng cáo

Liên hệ quảng cáo

Liên hệ quảng cáo

Liên hệ quảng cáo

Liên hệ quảng cáo

Liên hệ quảng cáo

Liên hệ quảng cáo

Liên hệ quảng cáo

Liên hệ quảng cáo

Liên hệ quảng cáo

Liên hệ quảng cáo

Liên hệ quảng cáo

Liên hệ quảng cáo

Liên hệ quảng cáo

Liên hệ quảng cáo

Liên hệ quảng cáo

Liên hệ quảng cáo

Liên hệ quảng cáo

Liên hệ quảng cáo

Bài giảng môn học phân tích và thiết kế thuật toán

Học phần “Thuật toán và đánh giá độ phức tạp thuật toán” được viết cho sinh viên khoa CNTT sau khi đã  học xong các học phần: CẤU TRÚC DỮ LIỆU VÀ  GIẢI THUẬT, LẬP TRÌNH  NÂNG  CAO,  TOÁN  RỜI RẠC... Học phần trình  bày  các  kỹ thuật thiết kế giải thuật nâng cao, phương pháp phân tích đánh giá giải thuật, các giải thuật cơ bản, các giải thuật đồ thị, và một số các giải thuật cơ bản khác như chia để trị, qui hoạch động, thuật toán tham lam và các thuật toán trên đồ thị.

Chia sẻ bởi
Lượt xem: 2436     Tải về: 16     Lượt mua: 0     Định dạng:  
Gửi nhận xét của bạn về tài liệu này
comments powered by Disqus
Tài liệu liên quan
Bài tập, lời giải ngôn ngữ lập trình C Lượt tải: 2373 Lượt xem: 106087
TỔNG HỢP CÁC BÀI TẬP C-C++ CƠ BẢN Lượt tải: 564 Lượt xem: 32740
GIÁO TRÌNH LẬP TRÌNH C++ Lượt tải: 377 Lượt xem: 18099
Có thể bạn quan tâm
Hướng dãn lập trình OpenGL căn bản Lượt tải: 251 Lượt xem: 14095
Bài tập Assembly Lượt tải: 145 Lượt xem: 12417
Lập trình ứng dụng web với ASP.NET và C# Lượt tải: 304 Lượt xem: 11387