Bài giảng Thiết kế và đánh giá thuật toán: Phần 1 - ĐH Sư Phạm Kỹ Thuật Nam Đị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. Mời các bạn cùng tham khảo phần 1 bài giảng Thiết kế và đánh giá thuật toán dưới đây.
Nội dung trích xuất từ tài liệu:
Bài giảng Thiết kế và đánh giá thuật toán: Phần 1 - ĐH Sư Phạm Kỹ Thuật Nam Định BỘ LAO ĐỘNG - THƯƠNG BINH VÀ Xà HỘITRƯỜNG ĐẠI HỌC SƯ PHẠM KỸ THUẬT NAM ĐỊNH tËp bµi gi¶ng thiÕt kÕ vµ ®¸nh gi¸ thuËt to¸n Mà SỐ TB2012-02-06 BIÊN SOẠN: PHẠM CAO HÀO NAM ĐỊNH 2012 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ấttrong 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ántố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ácthuậ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ệcgiả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ọcmá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ốimỗ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ếnthứ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ếtmộ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àiliệ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ợihơ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ậttoá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ọcsư 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 dungcá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ớisự độ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ệukhô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àiliệu ngày càng hoàn thiện hơn. Phạm Cao Hào ii MỤC LỤCChương 1. Tổng quan về thiết kế và đánh giá thuật toán 11.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 11.2. Sự cần thiết của thiết kế và đánh giá thuât toán 21.3. Diễn tả thuật toán 31.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ế 81.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 19Bài tập chương 1. 31Chương 2. Kỹ thuật chia để trị 372.1 Nội dung kỹ thuật 372.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 ...