Giáo trình Lý thuyết thuật toán

Giải bài toán có nghĩa là xuất phát từ dữ liệu vào, thực hiện một dãy hữu hạn những thao tác có có sở khoa học thích hợp để tìm được dữ liệu ra theo yêu cầu của bài toán. Độ phức tạp dữ liệu vào của bài toán được hiểu là số lượng dữ liệu vào các bài toán.
Nội dung trích xuất từ tài liệu:
Giáo trình Lý thuyết thuật toánGiáo trình Lýthuyết thuật toánGiáo trình Lý thuyết thuật toán-Bộ môn Khoa học máy tính-2010 MỤC LỤCNội dung TrangChương 1: Kỹ thuật phân tích đánh giá thuật toán 41.1. Khái niệm bài toán và độ phức tạp dữ liệu vào 41.1.1. Khái niệm bài toán 41.1.2. Độ phức tạp dữ liệu vào của bài toán 41.2. Các mô hình tính toán 41.2.1. Máy Turing 51.2.2. Máy xử lý thuật toán viết bằng ngôn ngữ tựa ALGOL 71.3. Khái niệm thuật toán và độ phức tạp của thuật toán 71.3.1. Thuật toán(Algorithm) 71.3.2 Chi phí phải trả cho một quá trình tính toán và các khái 7 niệm về độ phức tạp thuật toán1.4. Cách tính độ phức tạp 101.4.1. Các quy tắc cơ bản 101.4.2. Độ phức tạp của các chương trình đệ quy 111.5. Thuật toán không đơn định đa thức(Nodeterministic 14Polynomial NP)1.5.1. Sự phân lớp các bài toán. 161.5.2. Khái niệm “dẫn về được” (Phép quy dẫn) 171.5.3 Lớp bài toán NP - khó (NP - hard) và NP - đầy đủ (NP – 18Complate)1.6. Thuật toán xấp xỉ (Heuristic) 221.6.1. Các khái niệm 221.6.2. Thuật toán ε - xấp xỉ tuyệt đối 241.6.3.Thuật toán ε - xấp xỉ 261.7. Chứng minh tính đúng đắn của thuật toán 281.7.1. Ví dụ: 281.7.2. Phương pháp thử 281.7.3. Kiểm chứng tính đúng đắn 29Chương 2: Các thuật toán Sắp xếp 312.1. Bài toán sắp xếp 312.1.1. Tầm quan trọng của bài toán sắp xếp 312.1.2. Sắp xếp trong và sắp xếp ngoài 312.1.3. Tổ chức dữ liệu và ngôn ngữ cài đặt 312.1.4. Thuật toán sắp xếp 322.2. Các phương pháp sắp xếp đơn giản 322.2.1. Sắp xếp chọn (Selection Sort) 322.2.2. Sắp xếp chèn (InsertionSort) 332.2.3. Sắp xếp nổi bọt(Bubble Sort) 352.3. Sắp xếp nhanh QUICK SORT 362.3.1. Ý tưởng 362.3.2. Thiết kế giải thuật 362.3.3. Đánh giá độ phức tạp 382.4. Sắp xếp kiểu vun đống (Heapsort) 392.4.1. Định nghĩa HEAP 392.4.2. Sắp xếp kiểu vun đống 40 1Giáo trình Lý thuyết thuật toán-Bộ môn Khoa học máy tính-20102.4.3. Độ phức tạp tính toán 402.5. Sắp xếp hòa nhập (Merge Sort) 432.5.1. Ý tưởng 432.5.2. Thiết kế giải thuật 442.5.3. Đánh giá độ phức tạp 462.6. Cấu trúc dữ liệu và giải thuật xử lý ngoài 462.6.1. Mô hình xử lý ngoài 462.6.2. Đánh giá các giải thuật xử lý ngoài 472.6.3. Sắp xêp ngoài - MergeSorting 472.6.4. Cải tiến sắp xếp trộn 512.6.5. Trộn nhiều đường 52Chương 3: Kỹ thuật thiết kế thuật toán 543.1. Chia để trị 543.1.1. Nội dung 543.1.2. Một số bài toán áp dụng 553.2. Quy hoạch động (Dynamic) 583.2.1. Nội dung 583.2.2. Ví dụ áp dụng 593.3. Phương pháp tham lam (Greedy Method) 633.3.1. Bài toán tối ưu tổ hợp 633.3.2. Nội dung 643.4. Phương pháp nhánh cận (Branch- and- Bound) 683.4.1. Nội dung 683.4.2. Các bài toán áp dụng 69Chương 4: Lý thuy ...