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: 1979     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
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: 1979     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
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: 1795 Lượt xem: 83666
TỔNG HỢP CÁC BÀI TẬP C-C++ CƠ BẢN Lượt tải: 325 Lượt xem: 23563
GIÁO TRÌNH LẬP TRÌNH C++ Lượt tải: 263 Lượt xem: 14463
Hướng dãn lập trình OpenGL căn bản Lượt tải: 222 Lượt xem: 11858
Có thể bạn quan tâm
Bài tập Assembly Lượt tải: 108 Lượt xem: 9609
Mẹo lập trình Lượt tải: 0 Lượt xem: 7879