Phân tích và thiết kế giải thuật

Mộtchiến lược thiết kế giải thuật (Algorithm DesignStrategy) là một cách tiếp cận tổng quát để giảiquyết vấn đề bằng giải thuật mà có thể áp dụng chonhiều bài toán khác nhau trong nhiều lãnh vực khác nhau. Một kiểu dữ liệu trừu tượng là một mô hình toán học đi cùng với những tác vụ được định nghĩa trên mô hình này.
Nội dung trích xuất từ tài liệu:
Phân tích và thiết kế giải thuậtMôn h c: Phân tích và thi t k gi i thu tCh ng 1 CÁC KHÁI NI M C N B N 4N i dung1. Ki u d li u tr u t ng2. quy3. Phân tích gi i thu t 51.Ki u d li u tr u t ng• Mô t m t c u trúc d li u theo các tác v (operations) làm vi c trên c u trúc d li u thì ti n l i h n là di n t nó theo nh ng chi ti t thi công (implementation details).• Chúng ta nên tách nh ng khái ni m v c u trúc d li u ra kh i nh ng chi ti t thi công.• Khi m t c u trúc d li u c nh ngh a theo cách nh v y ta s có m t ki u d li u tr u t ng (abstract data type) hay ADT. M t ki u d li u tr u t ng là m t mô hình toán h c i cùng v i nh ng tác v c nh ngh a trên mô hình này. 6Vài thí d v Ki u d li u tr u t ng• M t t p (set) là m t t p h p g m zero hay nhi u ph n t . M t ph n t không c phép xu t hi n nhi u h n m t l n trong t p. M t t p g m n ph n t c ký hi u là {a1, a2,…,an}, nh ng v trí c a m t ph n t trong m t t p là không quan tr ng.• M t a t p (multiset) là m t t p mà trong ó m t ph n t c phép xu t hi n nhi u h n m t l n. Thí d , {5,7,5,2} là m t a t p. M t a t p có th có nh ng tác v sau: initialize (kh i t o) insert (thêm vào) is_empty (th a t p có r ng) delete (xoá) findmin (tìm ph n t bé nh t) 7Vài thí d v Ki u d li u tr u t ng (tt)• M t chu i (sequence) là m t t p h p có th t c a zero hay nhi u ph n t ; c ký hi u là . V trí c a m t ph n t trong m t chu i là có ý nghiã. M t chu i có th có nh ng tác v sau: initialize (kh i t o) length (chi u dài) head (ph n t u) tail (ph n uôi) concatenate (ghép k hai chu i) 8Gi i m t bài toán b ng ADT th y ích l i c a ki u d li u tr u t ng, th xét bài toánsau:Cho m t m ng (array) g m n s , A[1..n], hãy xác nh k ph nt l n nh t trong m ng, v i k n. Thí d , n u A là {5, 3, 1, 9,6}, và k = 3, thì k t qu là {5, 9, 6}.Không d xây d ng m t gi i thu t gi i bài toán trên.Ta th dùng ki u d li u tr u t ng a t p (multiset) v i cáctác v : initialize(M), insert(x, M), deleteMin(M), findMin(M) 9Suy ngh trên a t p M, ta có th vi t m t gi i thu t nhsau:Initialize(M);for i:= 1 to k do Insert(A[i], M);for i:= k + 1 to n do if A[i] > FindMin(M) then begin DeleteMin(M); Insert(A[i],M) end;Trong thí d trên, ta th y ki u d li u tr u t ng ã làm n gi n hóa vi c xây d ng gi i thu t b ng cách không b ntâm n nh ng chi ti t thi công hay hi n th c hóa. 10Thi công m t ki u d li u tr u t ngQuá trình dùng m t c u trúc d li u c th hi n th c hóa c g i là thi công ki u d li u tr u t ng. Trongm t ADTs thi công này, ph n d li u tr u t ng c hi n th c hóab ng m t c u trúc d li u c th và ph n các tác v tr ut ng c hi n th c hóa b ng các tác v c th h n. Abstract Data Data Structure Operations Concrete operations 11Thi công m t ki u d li u tr u t ng (tt.)Có th dùng m ng (array) hay danh sách liên k t (linked list) thi công t p h p (set).Có th dùng m ng (array) hay danh sách liên k t (linked list) thi công chu i.V i ki u d li u tr u t ng a t p nh trong thí d tr c, tacó th dùng hàng i có u tiên (priority queue) thicông. Và sau ó ta có th dùng c u trúc d li u heap thicông hàng i có u tiên. 122. quyH th c truy h iThí d 1: Hàm tính giai th aN! = N.(N-1)! v iN 1 0! = 1Nh ng nh ngh a hàm quy mà ch a nh ng i s nguyên c g i là nh ng h th c truy h i (recurrence relation).function factorial (N: integer): integer;begin if N = 0 then factorial: = 1 else factorial: = N*factorial (N-1);end; 13H th c truy h iThí d 2: S FibonacciH th c truy h i: FN = FN-1 + FN-2 for N 2 F0 = F1 = 1 1, 1, 2, 3, 5, 8, 13, 21, …function fibonacci (N: integer): integer;begin if N M t cách khác: Ta có th dùng m t m ng ch a nh ng tr s i tr c trong khi tính hàm fibonacci. Ta có m t gi i thu tkhông quy.procedure fibonacci;const max = 25;var i: integer;F: array [0..max] of integer;begin F[0]: = 1; F[1]: = 1; for i ...