Tập bài giảng Thiết kế và đánh giá thuật toán

Nội dung của tập bài giảng Thiết kế và đánh giá thuật toán trình bày các kỹ thuật thiết kế thuật toán thông dụng và cơ sở phân tích, đánh giá độ phức tạp của thuật toán. Tập bài giảng gồm 6 chương như sau: Chương 1 - Tổng quan về thiết kế và đánh giá thuật toán; Chương 2 - Kỹ thuật chia để trị; Chương 3 - Kỹ thuật tham lam; Chương 4 - Kỹ thuật quay lui; Chương 5 - Kỹ thuật nhánh và cận; Chương 6 - Kỹ thuật quy hoạch động. Mời các bạn cùng tham khảo.
Nội dung trích xuất từ tài liệu:
Tập bài giảng Thiết kế và đánh giá thuật toán Lời nói đầu Xây dựng một thuật toán tốt để giải bài bài toán đã cho là bước quan trọng nhất trong việc giải bài toán đó trên máy tính điện tử. Để có được một thuật một thuật toán tốt cần phải nắm vững các kỹ thuật thiết kế, phân tích, đánh giá thuật toán cùng các thuật toán cơ bản cho một số lớp bài bài toán điển hình. Tài liệu Thiết kế và đánh giá thuật toán được biên soạn nhằm phục vụ công việc giảng dạy và học tập môn học Thiết kế và đánh giá thuật toán của ngành học Khoa học máy tính thuộc khoa Công nghệ thông tin trường Đại học sư phạm kỹ thuật Nam Định. Tài liệu cũng rất cần thiết cho tất cả các ngành học thuộc khoa Công nghệ thông tin. Nội dung của tài liệu trình bày các kỹ thuật thiết kế thuật toán thông dụng và cơ sở phân tích, đánh giá độ phức tạp của thuật toán. Tài liệu gồm 6 chương: Chương 1: Tổng quan về thiết kế và đánh giá thuật toán Chương 2: Kỹ thuật chia để trị Chương 3: Kỹ thuật tham lam Chương 4: Kỹ thuật quay lui Chương 5: Kỹ thuật nhánh và cận Chương 6: Kỹ thuật quy hoạch động Trong từng chương các vấn đề đưa ra đều được minh họa bằng các ví dụ. Cuối mỗi chương đều có một hệ thống các bài tập nhằm giúp người học củng cố các kiến thức đã được học đồng thời rèn luyện khả năng vận dụng các kiến thức để giải quyết một số bài toán trong thực tế. Với các bài tập khó tài liệu đã đưa ra hướng dẫn giải để giúp người học thuận lợi trong qua trình nghiên cứu và giải quyết các bài tập. Cuối tài liệu là phần cài đặt một số thuật toán đã được thiết kế nhằm giúp người học thuận lợi hơn trong việc nắm bắt và vận dụng các kỹ thuật thiết kế thuật toán. Tài liệu được biên soạn theo chương trình môn học Thiết kế và đánh giá thuật toán của ngành học Khoa học máy tính thuộc khoa Công nghệ thông tin trường Đại học sư phạm kỹ thuật Nam Định. Nội dung tài liệu được biên soạn dựa trên cơ sở nội dung các bài giảng của tác giả trong một số năm qua tại khoa Công nghệ thông tin trường Đại học sư phạm kỹ thuật Nam Định. Trong quá trình biên soạn, tác giả đã nhận được nhiều ý kiến đóng góp cùng với sự động viên, khích lệ của bạn bè đồng nghiệp trong khoa và trong trường. Tác giả xin được tỏ lòng cảm ơn với những ý kiến đóng góp và động viên khích lệ này. i Với lần biên soạn đầu tiên, mặc dù đã hết sức cố gắng song chắc chắn tài liệu không thể tránh khỏi những thiếu sót. Rất mong nhận được các ý kiến đóng góp để tài liệu ngày càng hoàn thiện hơn. Phạm Cao Hào ii MỤC LỤC Chương 1. Tổng quan về thiết kế và đánh giá thuật toán 1 1.1. Thuật toán 1 1.1.1. Khái niệm thuật toán 1 1.1.2. Các đặc trưng cơ bản của thuật toán 1 1.2. Sự cần thiết của thiết kế và đánh giá thuât toán 2 1.3. Diễn tả thuật toán 3 1.4. Thiết kế thuật toán 7 1.4.1. Modul hoá và thiết kế từ trên xuống 7 1.4.2. Phương pháp là mịn dần (tinh chỉnh từng bước) 7 1.4.3. Một số kỹ thuật thiết kế 8 1.5. Phân tích thuật toán 9 1.5.1. Thời gian thực hiên thuật toán 9 1.5.2. Độ phức tạp tính toán của thuật toán 10 1.5.3. Ðộ phức tạp của chương trình có gọi chương trình con không đệ qui 16 1.5.4. Phân tích các thuật toán đệ quy 17 1) Thành lập phương trình truy hồi 18 2) Giải phương trình truy hồi 19 Bài tập chương 1. 31 Chương 2. Kỹ thuật chia để trị 37 2.1 Nội dung kỹ thuật 37 2.2. Các ví dụ áp dụng 37 2.2.1. Tìm min và max 37 2.2.2. Một số thuật toán sắp xếp 40 1) Sắp xếp nhanh 40 2) Sắp xếp trộn 44 2.2.3. Tìm kiếm nhị phân 51 2.2.4. Nhân các số nguyên lớn 53 Bài tập chương 2. 57 Chương 3. Kỹ thuật tham lam 62 3.1. Nội dung kỹ thuật 62 3.1.1. Bài toán tối ưu tổ hợp 62 3.1.2. Nội dung kỹ thuật tham lam 62 3.2. Các ví dụ áp dụng 62 iii 3.2.1. Bài toán người giao hàng 62 3.2.2. Bài toán chiếc ba lô 65 3.2.3. Bài toán tô màu bản đồ 70 3.2.4. Tìm cây khung nhỏ nhất 74 3.2.5. Tìm đường đi ngắn nhất 77 3.2.6. Bài toán phân công công việc 79 Bài tập chương 3. 84 Chương 4. Kỹ thuật quay lui 86 4.1. Nội dung kỹ thuật 86 4.2. Các ví dụ áp dụng ...