Tiểu luận ngành Khoa học máy tính: Thiết kế và phân tích thuật toán

Nội dung của tiểu luận bao gồm 3 chương với các nội dung: độ phức tạp thuật toán; phương pháp đệ quy; phương pháp quy hoạch động. Để nắm chi tiết hơn nội dung nghiên cứu, mời các bạn cùng tham khảo tiểu luận.
Nội dung trích xuất từ tài liệu:
Tiểu luận ngành Khoa học máy tính: Thiết kế và phân tích thuật toán TRƢỜNG ĐẠI HỌC KHOA HỌC HUẾ KHOA CÔNG NGHỆ THÔNG TIN BÀI TẬP - TIỂU LUẬNTHIẾT KẾ VÀ PHÂN TÍCH THUẬT TOÁNLỚP CAO HỌC: NGÀNH KHOA HỌC MÁY TÍNH GVHD: TS: HOÀNG QUANG HVTH: CAO CHÍ HIỂN 0985945261 GIA LAI, 01/ 2019 MỤC LỤCLỜI NÓI ĐẦU ......................................................................................................... 1PHẦN I: NỘI DUNG .............................................................................................. 2I: ĐỘ PHỨC TẬP THUẬT TOÁN........................................................................ 2 1. Độ phức tạp thuật toán: .................................................................................. 2 2: Bài tập:.............................................................................................................. 3 Bài 1: So sánh độ phức tập thuật toán O( N ) và O(log 2 n) ............................. 3 Bài 2: Viết hàm tính an (với a  real, n  word) có độ phức tạp tính toán là O(1) ..................................................................................................................... 3II. PHƢƠNG PHÁP ĐỆ QUY................................................................................ 5 1. Tim hiểu đệ quy................................................................................................ 5 2. Bài tập Đệ quy trên kiểu dữ liệu mảng .......................................................... 6 Bài 3: Xóa tất cả các phần tử của dãy A gồm n phần tử có giá trị là X .......... 6 Bài 4. Viết chương trình tìm Max của dạy A gồm n phần tử (n>0) ................ 7 3. Bài tập Đệ quy trên kiểu dữ liệu danh sách liên kết đơn ............................. 9 Bài 5: Xóa tất cả các nút có trường Info là giá trị x. ....................................... 9 Bài 6: Tìm Max của trường Info trong danh sách liên kết đơn. ..................... 9 4. Bài tập Đệ quy trên kiểu dữ liệu cây nhi phân ........................................... 12 Bài 7. Viết hàm đếm số nút của cây có trường Info = x ................................ 13 Bài 8. Viết thủ tục đệ quy bổ sung 1 nút lá vào cây tìm kiếm nhị phân ........ 13 Cây tìm kiếm nhị phân: ................................................................................... 13III. PHƢƠNG PHÁP QUY HOẠCH ĐỘNG 1. Cơ sở lý thuyết ................................................................................................ 17 a) Tư tưởng của phương pháp: ....................................................................... 17 b) Phạm vi áp dụng: ......................................................................................... 17 c) Nguyên lý của phương pháp: ...................................................................... 17 2. Phương pháp thực hiện ................................................................................. 17 3. Giải bài toán bằng phương pháp Quy hoạch động: (gồm 4 bước) ........... 17 4. Một số bài toán Giải bằng phương pháp Quy hoạch động ........................ 17 Bài 9. Bài toán cái túi nguyên (Số lượng các loại đổ vật không hạn chế) .... 17 Bài 10. Bài toán Sinh viên ôn thi .................................................................... 21 Bài 11. Người đi du lịch ................................................................................... 25 Bài 12: Bài toán xâu trong cực đại: ................................................................ 30TÀI LIỆU THAM KHẢO .................................................................................... 34 LỜI NÓI ĐẦU Việc xác định độ phức tạp tính toán của một thuật toán là một công việckhông hề đơn giản, trước đây chúng ta ít quan tâm đến việc đánh giá thuật toán màchỉ dừng lại ở mức độ đưa ra một thuật toán để giải quyết bài toán. Tuy nhiên mộtbài toán có thể có nhiều thuật toán để giải. Do đó ta phải lựa chọn thuật đoán tốiưu. Độ phức tạp thuật toán là cơ sở để đánh giá thuật toán đó có tốt hơn thuật toánkhác hay không. Đối với những thuật toán phức tạp thì việc xác định độ phức tạpmột cách chính xác là rất khó khăn đặc biệt đối với những thuật toán sử dụng giảithuật đệ qui. Trong phần náy, nhóm tôi đánh giá độ phức tạp của một số thuật toán. Đưara một số bài toán giải hệ thức truy hồi: - Dùng phương pháp Đệ quy để giải các bài toán trên nhiều kiểu dữ liệu như: Kiểu dữ liệu cơ bản, kiểu mảng, danh sách liên kết đơn, cây nhị phân và cây tìm kiếm nhị phân. - Dùng phương pháp Quy hoạch động để giải một số bài toán tối ưu. Đây là nội dung chính trong đề tài bài tập tiểu luận của nhóm em: THIẾTKẾ VÀ PHÂN TÍCH THUẬT TOÁN Mặc dù đã rất cố gắng nhưng tiểu luận này không tránh khỏi n ...