tailieunhanh - Bài giảng Bài 9: Thiết kế thuật toán

Bài giảng Bài 9: Thiết kế thuật toán do Hoàng Thị Điệp biên soạn trình bày về các chiến lược thiết kế thuật toán, thuật toán tiêu biểu, số Fibonacci thứ n đệ quy, Fibonacci(n) quy hoạch động, cấu trúc chung của phương pháp quy hoạch động. | Bài 9: Thiết kế thuật toán Giảng viên: Hoàng Thị Điệp Khoa Công nghệ Thông tin – ĐH Công Nghệ Các chiến lược thiết kế thuật toán • Chia-để-trị (Divide-and-conquer) • – Thực hiện từng bước một. Tại mỗi bước, chọn phương án được xem là tốt lúc đó. – Không phải tất cả các thuật toán tham ăn đều cho kết quả tối ưu toàn cục – Chia bài toán thành các bài toán kích thước nhỏ có thể giải quyết độc lập. Sau đó kết hợp nghiệm các bài toán kích thước nhỏ thành nghiệm bài toán gốc – Thuật toán đệ quy • Quy hoạch động (Dynamic programming) Tham ăn (Greedy method) • – Giải bài toán lớn dựa vào kết quả bài toán con. Tránh lặp lại việc giải cùng một bài toán con bằng cách lưu nghiệm các bài toán con trong một bảng – Thuật toán lặp INT2203 Các chiến lược khác – Quay lui – Thuật toán ngẫu nhiên Thuật toán tiêu biểu – Tìm dãy con chung của hai dãy số (longest common subsequence) • Chia-để-trị – Tìm kiếm nhị phân (binary search) – Sắp xếp trộn (merge sort) – Sắp xếp nhanh (quick sort) • Tham ăn – Xây dựng mã Huffman (Huffman encoding) – Tìm cây bao trùm nhỏ nhất (minimum spanning tree) • Quy hoạch động – Tìm dãy con tăng dài nhất (longest increasing subsequence) – Bài toán ba lô (backpacker/knapsack) – Bài toán người bán hàng (traveling salesman) INT2203 Tìm số Fibonacci thứ n đệ quy • • Algorithm Fib(n) Input n Output số Fibonacci thứ n if n = 0 then return 0 else if n = 1 then return 1 else return Fib(n – 2) + Fib(n – 1) Fn= Fn-1+ Fn-2 F0 =0, F1 =1 – 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 • Thủ tục tính đệ quy trực tiếp thực hiện chậm do tính lặp nhiều lần. F(6) = 8 F(5) F(4) F(4) F(3) F(2) F(1) F(0) F(3) F(2) F(1) F(1) F(3) F(2) F(1) F(0) F(1) F(0) INT2203 F(2) F(1) F(0) F(2) F(1) F(1) F(0) Phân tích • Có bao nhiêu phép cộng? Fn +1 1+ 5 • Tỉ lệ vàng ≈φ = ≈ . 2 Fn • Suy ra Fn≈ • Cây đệ quy có các lá bằng 0 hoặc 1, do đó có tổng cộng khoảng phép cộng • Thời gian thực hiện là hàm .

• Kỹ thuật lập trình
• Thiết kế thuật toán
• Bài giảng Thiết kế thuật toán
• Chiến lược thiết kế thuật toán
• Thuật toán tiêu biểu
• Số Fibonacci thứ n đệ quy
• Fibonacci quy hoạch động
• Phân tích thiết kế thuật toán
• Phân tích thuật toán
• Bài giảng Phân tích thiết kế thuật toán
• Kỹ thuật thiết kế giải thuật
• Thiết kế giải thuật
• Phân tích thiết kế giải thuật
• Phương pháp thiết kế thuật toán
• Tối ưu thuật toán
• Đề thi Phân tích thiết kế thuật toán
• Câu hỏi Phân tích thiết kế thuật toán
• Ôn tập Phân tích thiết kế thuật toán
• Thuật toán tham lam
• Trình diễn thuật toán
• Đề thi học kỳ
• Đánh giá thuật toán
• Thiết kế và đánh giá thuật toán
• Đề thi Thiết kế và đánh giá thuật toán
• Bài tập Thiết kế và đánh giá thuật toán
• Kỹ thuật phân tích thuật toán
• Đánh giá một giải thuật
• Đề thi Đánh giá thuật toán
• Bài giảng đánh giá thuật toán
• Bài toán sắp xếp
• Sắp xếp chèn
• Năng lực sáng tạo kĩ thuật của sinh viên
• Bài toán thiết kế kĩ thuật
• Dạy học kĩ thuật
• Đặc điểm bài toán thiết kế kĩ thuật
• Nguyên tắc xây dựng bài toán thiết kế kĩ thuật
• Tự động hóa tính toán thiết kế tàu
• Thiết kế tàu thủy
• Kỹ thuật thiết kế tàu
• Tính toán thiết kế tàu
• Thiết kế tối ưu tàu thủy
• Thiết kế chân vịt tàu thủy
• Giải thuật sắp xếp
• Chương trình sắp xếp
• Cấu trúc dữ liệu
• Giải thuật lưu trữ ngoài
• Lập trình động
• Kỹ thuật thiết kế dưới lên
• Giáo trình Phương pháp thiết kế kỹ thuật
• Phương pháp thiết kế kỹ thuật
• Kỹ thuật xây dựng
• Bài toán thiết kế
• Xây dựng ý tưởng thiết kế
• Kế hoạch thiết kế kỹ thuật
• Bài giảng Phân tích thiết kế giải thuật
• Phương pháp thiết kế thuật giải
• Thuật toán chính xác
• Thuật toán gần đúng
• Bước thiết kế một thuật giải
• Phân tích đệ quy
• Thuật toán đệ quy
• Phân tích toán học
• Bài toán trả tiền thừa
• Chiến lược tham ăn
• Chia để trị
• Bài tập Chia để trị
• Đánh giá độ phức tạp thuật toán
• Phân tích thiết kế thuật toán
• Kỹ thuật phân tích thiết kế giải thuật
• Phương pháp phân tích thuật toán
• Vai trò của phân tích thuật toán
• Quá trình phân tích thuật toán
• Thuật toán sắp xếp
• Phân tích thuật toán sắp xếp
• Thuật toán tìm kiếm
• Phân tích thuật toán tìm kiếm
• Bài giảng Thiết kế và đánh giá thuật toán
• Kỹ thuật chia để trị
• Kỹ thuật tham lam
• Kỹ thuật quy hoạch động
• Kỹ thuật quay lui
• Khái niệm tiệm cận
• Ký hiệu tiệm cận