Bài giảng Cơ sở dữ liệu giải thuật: Bài 11 - Thiết kế thuật toán

Bài giảng Cơ sở dữ liệu giải thuật: Bài 11 - Thiết kế thuật toán làm rõ các chiến lược thiết kế thuật toán, thuật toán tiêu biểu, quy hoạch động, cấu trúc chung của phương pháp quy hoạch động, bài toán ba lô.
Nội dung trích xuất từ tài liệu:
Bài giảng Cơ sở dữ liệu giải thuật: Bài 11 - Thiết kế thuật toánBài 11: Thi t k thu t toánGi ng viên: Hoàng Th i pKhoa Công ngh Thông tin –i h c Công NghCác chi n lư c thi t k thu t toán•Chia--tr (Divide-and-conquer)•– Chia bài toán thành các bài toánkích thư c nh có th gi i quy tc l p. Sau ó k t h p nghi mcác bài toán kích thư c nh thànhnghi m bài toán g c– Thu t toánquy•Quy ho ch ng (Dynamicprogramming)– Gi i bài toán l n d a vào k t qubài toán con. Tránh l p l i vi cgi i cùng m t bài toán con b ngcách lưu nghi m các bài toán controng m t b ng– Thu t toán l pdiepht@vnuTham ăn (Greedy method)– Th c hi n t ng bư c m t. T i m ibư c, ch n phương án ư c xemlà t t lúc ó.– Không ph i t t c các thu t toántham ăn u cho k t qu t i ưutoàn c c•Các chi n lư c khác– Quay lui– Thu t toán ng u nhiên2Thu t toán tiêu bi u• Chia--tr– Tìm ki m nh phân (binarysearch)– S p x p tr n (merge sort)– S p x p nhanh (quick sort)• Quy ho chng– Tìm dãy con tăng dài nh t(longest increasingsubsequence)– Bài toán ba lô(backpacker/knapsack)– Bài toán ngư i bán hàng(traveling salesman)diepht@vnu– Tìm dãy con chung c a haidãy s (longest commonsubsequence)• Tham ăn– Xây d ng mã Huffman(Huffman encoding)– Tìm cây bao trùm nh nh t(minimum spanning tree)31. Fibonacci(n)diepht@vnu4Tìm s Fibonacci th n••Algorithm Fib(n)Input nOutput s Fibonacci th nif n = 0 then return 0else if n = 1 then return 1elsereturn Fib(n – 2) + Fib(n – 1)Fn= Fn-1+ Fn-2F0 =0, F1 =1– 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 …•quyTh t c tínhquy tr c ti pth c hi n ch m do tính l pnhi u l n.F(6) = 8F(5)F(4)F(4)F(3)F(2)F(1)diepht@vnuF(3)F(2)F(1) F(1)F(3)F(2) F(1)F(0) F(1)F(0)F(2)F(1)F(2)F(1) F(1)F(0)F(0)F(0)5