Giáo trình Phân tích thiết kế thuật toán (Nghề Lập trình máy tính): Phần 1 - Tổng cục dạy nghề

Giáo trình Phân tích thiết kế thuật toán (Nghề Lập trình máy tính): Phần 1 cung cấp cho người học những kiến thức tổng quan về phân tích thiết kế thuật toán, các kiểu dữ liệu trừu tượng và các cấu trúc dữ liệu cơ bản. Để hiểu rõ hơn, mời các bạn tham khảo chi tiết nội dung giáo trình này.
Nội dung trích xuất từ tài liệu:
Giáo trình Phân tích thiết kế thuật toán (Nghề Lập trình máy tính): Phần 1 - Tổng cục dạy nghề BỘ LAO ĐỘNG - THƯƠNG BINH VÀ XÃ HỘI TỔNG CỤC DẠY NGHỀ DỰ ÁN GIÁO DỤC KỸ THUẬT VÀ DẠY NGHỀ (VTEP) GIÁO TRÌNHMôn học: PHÂN TÍCH THIẾT KẾ THUẬT TOÁN Mã số: ITPRG3_12 Nghề: LẬP TRÌNH MÁY TÍNH Trình độ (lành nghề) Đà Lạt - 2007Phân tích thiết kế thuật toán Tuyên bố bản quyền: Tài liệu này thuộc loại sách giáo trình Cho nên các nguồn thông tin có thể được phép dùng nguyên bản hoặc trích dùngcho các mục đích về đào tạo và tham khảo . Mọi mục đích khác có ý đồ lệch lạc hoặc sử dụng với mục đích kinh doanh thiếulành mạnh sẽ bị nghiêm cấm. Tổng Cục Dạy nghề sẽ làm mọi cách đểbảo vệ bản quyền của mình. Tổng Cục Dạy Nghề cám ơn và hoannghênh các thông tin giúp cho việc tu sửa và hoàn thiện tốt hơn tàI liệu này. Địa chỉ liên hệ: Dự án giáo dục kỹ thuật và nghề nghiệp Tiểu Ban Phát triển Chương trình Họcliệu ……………………………………………… ................................................................ 2Phân tích thiết kế thuật toán LỜI TỰA Đây là tài liệu được xây dựng theo chương trình của dự án giáo dục kỹ thuật và dạy nghề, đểcó đươc giáo trình này dự án đã tiến hành theo hai giai đoạn. Giai đoạn 1 : Xây dựng chương trình theo phương pháp DACUM, kết quả của gian đoạnnày là bộ khung chương trình gồm 230 trang cấp độ 2 và 170 trang cấp độ 3. Giai đoạn 2 : 29 giáo trình và 29 tài liệu hướng dẫn giáo viên cho nghề lập trình máy tính 2cấp độ. Để có được khung chương trình chúng tôi đã mời các giáo viên, các chuyên gia đang làmviệc trong lĩnh vực công nghệ thông tin cùng xây dựng chương trình. Trong giai đoạn viết giáo trình chúng tôi cũng đã có những sự điều chỉnh để giáo trình cótính thiết thực và phù hợp hơn với sự phát triển của lĩnh vực công nghệ thông tin. Trong quá trình biên soạn, mặc dù đã cố gắng tham khảo nhiều tài liệu và giáo trình khácnhưng tác giả không khỏi tránh được những thiếu sót và hạn chế. Tác giả chân thành mong đợinhững nhận xét, đánh giá và góp ý để cuốn giáo trình ngày một hoàn thiện hơn. Tài liệu này được thiết kế theo từng mô đun/ môn học thuộc hệ thống mô đun/môn họccủa một chương trình, để đào tạo hoàn chỉnh nghề Lập trình máy tính ở cấp trình độ lành nghề vàđược dùng làm Giáo trình cho học viên trong các khoá đào tạo, cũng có thể được sử dụng chođào tạo ngắn hạn hoặc cho các công nhân kỹ thuật, các nhà quản lý và người sử dụng nhân lựctham khảo. Đây là tài liệu thử nghiệm sẽ được hoàn chỉnh để trở thành giáo trình chính thức trong hệthống dạy nghề. Đà lạt ,Tháng 10 năm 2007 3Phân tích thiết kế thuật toán MỤC LỤC TÊN BÀI TRANG 1. BàI1:TỔNG QUAN VỀ PHÂN TÍCH THIẾT KẾ THUẬT TOÁN 5 2. Bài2:CÁC KIỂU DỮ LIỆU TRỪU TƯỢNG 20 3. Bài3:CÁC CẤU TRÚC DỮ LIỆU CƠ BẢN 51 4. Bài4:PHƯƠNG PHÁP CHIA ĐỂ TRỊ 109 5. Bài5:PHƯƠNG PHÁP THAM LAM 116 6. Bài6:PHƯƠNG PHÁP QUAY LUI 124 7. Bài7:QUY HOẠCH ĐỘNG 135 8. Bài7(tiếp theo):NÉN DỮ LIỆU 145 9. Bài 8:LỚP BÀI TOÁN NP ĐẦY ĐỦ 159 10.CÁC BÀI THỰC HÀNH 172 11. TÀI LIỆU THAM KHẢO 185 4Phân tích thiết kế thuật toánBÀI 1 : TỔNG QUAN VỀ PHÂN TÍCH THIẾT KẾ THUẬT TOÁN Mã bài : ITPRG3_12.1 Giới thiệu Phân tích thiết kế thuật toán là một khâu quan trọng quyết định sự thành công của một chươngtrình máy tính. Nó giúp chúng ta lựa chọn, xây dựng và đánh giá các thuật toán trước khi viết mãchương trình. Chúng ta chỉ có thể có được một chương trình máy tính tốt nếu và chỉ nếu có mộtthuật toán tốt. Phân tích thiết kế thuật toán còn có một ý nghĩa vô cùng quan trọng trong trườnghợp làm việc theo nhóm (cho phép chia sẻ công việc và đảm bảo sự thống nhất giữa các lập trìnhviên) và bảo trì, nâng cấp hệ thống chương trình sau này. Trong phần này chúng ta sẽ làm quen với các khái niệm cơ bản về phân tích thiết kế thuậttoán, các phương pháp biểu diễn và đánh giá thời gian thực hiện thuật toán. Mục tiêu thực hiện Học xong bài này học viên sẽ có khả năng:  Nắm được các khái niệm cơ bản và tầm quan trọng của việc phân tích và thiết kế thuật t ...