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. | TRƢỜNG ĐẠI HỌC KHOA HỌC HUẾ KHOA CÔNG NGHỆ THÔNG TIN BÀI TẬP - TIỂU LUẬN THIẾT KẾ VÀ PHÂN TÍCH THUẬT TOÁN LỚ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ỤC LỜI NÓI ĐẦU . 1 PHẦN I NỘI DUNG . 2 I ĐỘ 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 . 3 II. 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 gt 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 . 13 III. 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 . 30 TÀ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ệc khô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ột bà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 .
