Phân tích và thiết kế giải thuật - Chương 1

Bài Giảng điện tử Phân tích và thiết kế giải thuật. Tiến sĩ Dương Tuấn Anh. Chương 1: Các khái niệm cơ bản. Mô tả cấu trúc dữ liệu theo các tác vụ 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.
Nội dung trích xuất từ tài liệu:
Phân tích và thiết kế giải thuật - Chương 1Mô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óam t ADT c g i là thi công ki u d li u tr u t ng. Trongs 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; fo ...