Bài giảng "Phân tích thiết kế và giải thuật - Chương 2: Kỹ thuật thiết kế giải thuật" cung cấp cho người học các kiến thức: Giới thiệu, từ bài toán đến chương trình, các kỹ thuật thiết kế giải thuật. | Bài giảng Phân tích thiết kế và giải thuật - Chương 2 Kỹ thuật thiết kế giải thuật KỸ THUẬT THIẾT KẾ GIẢI THUẬT 1 Nội dung Giới thiệu Từ bài toán đến chương trình Các kỹ thuật thiết kế giải thuật Chia để trị Tham ăn gready Quay lui Quét cạn Cắt tỉa Alpha-Beta Nhánh cận 2 Giới thiệu Biết các kỹ thuật thiết kế giải thuật từ ý tưởng cho đến giải thuật chi tiết. Hiểu rõ nguyên lý của các kỹ thuật phân tích thiết kế giải thuật Vận dụng kỹ thuật phân tích thiết kế để giải các bài toán thực tế các bài toán dạng nào thì có thể áp dụng kỹ thuật này. 3 Mô hình từ bài toán đến chương trình Thiết kế Đánh giá Lập trình include Bài toán thực tế Giải thuật Chương trình Kỹ thuật thiết kế Kỹ thuật phân tích Ngôn ngữ lập trình giải thuật đánh giá giải thuật PASCAL C C - Chia để trị - Độ phức tạp của giải JAVA Ngôn ngữ lập - Tham ăn thuật trình - Quay lui - Cải tiến giải thuật PASCAL C C JAVA 4 Kỹ thuật chia để trị Yêu cầu Cần phải giải bài toán có kích thước n. Phương pháp Ta chia bài toán ban đầu thành một số bài toán con đồng dạng với bài toán ban đầu có kích thước nhỏ hơn n. Giải các bài toán con được các lời giải con Tổng hợp lời giải con ta có được lời giải của bài toán ban đầu. Chú ý Đối với từng bài toán con ta lại chia chúng thành các bài toán con nhỏ hơn nữa. Quá trình phân chia này sẽ dừng lại khi kích thước bài toán đủ nhỏ mà ta có thể dễ dàng giải gọi là bài toán cơ sở. 5 Kỹ thuật chia để trị Kỹ thuật chia để trị bao gồm hai quá trình Phân tích bài toán đã cho thành các bài toán cơ sở Tổng hợp kết quả từ bài toán cơ sở để có lời giải của bài toán ban đầu. Sơ đồ sau mô tả một kỹ thuật chia để trị mà trong đó chia bài toán thành hai bài toán nhỏ hơn. Đây là trường hợp phổ biến nhất của kỹ thuật này. 6 bài toán kích thước n bài toán con 2 bài toán con 1 kích thước n 2 kích thước n 2 lời giải cho lời giải cho bài toán con 1 bài toán con 2 lời giải cho bài toán ban đầu 7 Nhìn lại giải thuật QuickSort và MergeSort Giải thuật QuickSort Sắp xếp dãy n số theo thứ tự tăng dần Áp
