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

Chia sẻ: Nguyen Bac A. Châu | Ngày: | Loại File: PDF | Số trang:0

Thêm vào BST

Báo xấu

200
lượt xem 71
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

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

Môn h c: Phân tích và thi t k gi i thu t Ch ng 1 CÁC KHÁI NI M C N B N 4
N i dung 1. Ki u d li u tr u t ng 2. quy 3. Phân tích gi i thu t 5
1.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. 6
Và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) 7
Và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) 8
Gi 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án sau: Cho m t m ng (array) g m n s , A[1..n], hãy xác nh k ph n t 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ác tác v : initialize(M), insert(x, M), deleteMin(M), findMin(M) 9
Suy ngh trên a t p M, ta có th vi t m t gi i thu t nh sau: 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 n tâm n nh ng chi ti t thi công hay hi n th c hóa. 10
Thi công m t ki u d li u tr u t ng Quá trình dùng m t c u trúc d li u c th hi n th c hóa m t ADT c g i là thi công ki u d li u tr u t ng. Trong s thi công này, ph n d li u tr u t ng c hi n th c hóa b ng m t c u trúc d li u c th và ph n các tác v tr u t 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 11
Thi 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, ta có th dùng hàng i có u tiên (priority queue) thi công. Và sau ó ta có th dùng c u trúc d li u heap thi công hàng i có u tiên. 12
2. quy H th c truy h i Thí d 1: Hàm tính giai th a N! = N.(N-1)! v iN 1 0! = 1 Nh 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; 13
H th c truy h i Thí d 2: S Fibonacci H 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 t khô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: = 2 to max do F[i]: = F[i-1] + F[i-2] end; 15
Chi n l c Chia- -tr Nhi u gi i thu t hay có c u trúc quy: gi i m t v n gi i thu t g i chính nó m t hay nhi u l n i phó v i nh ng v n con (subproblem) có quan h ch t ch v i nhau. Nh ng gi i thu t nh v y tuân theo cách ti p c n chia- -tr (divide and conquer): Gi i thu t phân rã v n thành nh ng v n con, gi i nh ng v n con này và k t h p nh ng l i gi i c a nh ng v n con thành l i gi i cho v n nguyên th y. Chi n l c này bao g m 3 b c sau ây m ic p quy: phân chia (divide) tr (conquer) k t h p (combine) 16
Thí d : Xét vi c v ch nh ng v ch cách nhau 1 inch trên 1 cây th c: có m t nét v ch t i i n ½ inch, nét v ch ng n h n nh ng o n ¼ inch, nét v ch ng n h n n a nh ng o n 1/8 inch, v.v... procedure rule(l, r, h: integer); /* l: left position of the ruler; r: right Gi s th t c position mark(x, h) v m t of the ruler */ v ch h n v t i v var m: integer; trí x. begin if h > 0 then begin m: = (1 + r) div 2; mark(m, h); rule(l, m, h-1); rule(m, r , h-1) end; end; 17
Kh quy V n : Gi i thu t không quy th ng làm vi c h u hi u và d ki m soát h n 1 gi i thu t quy. Làm cách nào chuy n i m t ch ng trình quy thành m t ch ng trình không- -quy t ng ng. Ph ng pháp: Cho m t th t c quy P, m i l n có m t l nh g i quy n P, giá tr hi n hành c a các tham s và các bi n c c b c c t vào các ng n x p (stack) x lý sau. M i l n có m t s quay v quy v P, giá tr c a các tham s và các bi n c c b s c khôi ph c l i t các ng n x p. 18
Kh quy (tt.) Vi c i phó v i a ch kh h i (return address) c th c hi n nh sau: Gi s th t c P ch a m t l nh g i quy t i b c l nh K, a ch kh h i K+1 s c l u t i m t ng n x p và s c dùng quay v m c th c thi th t c P hi n hành. procedure hanoi(n, beg, aux, end); begin if n = 1 then writeln(beg, end) Thí d : Th t c else hanoi là m t th begin t c quy gi i bài hanoi(n-1, beg, end, aux) ; toán Tháp Hà N i writeln(beg, end); hanoi(n-1, aux, beg, end); end end; 19
procedure hanoi(n, beg, aux, end: 3: writeln(beg, end); integer); top: = top + 1; /* second recursive call */ /* Stacks STN, STBEG, STAUX, STN[top]: = n; STEND, and STADD correspond, respectively, to variables N, BEG, AUX, STBEG[top]: = beg; END and ADD */ STAUX[top]: aux; STEND[top]: = end; label 1, 3, 5; var t: integer; STADD[top]: = 5; begin /* saving return address */ n: = n-1; t:= beg; beg: = aux; top: = 0; /* preparation for stacks */ 1: if n = 1 then aux: = t; goto 1; begin writeln(beg, end); goto 5 end; 5. /* translation of return point */ if top 0 then top: = top + 1; /* first recursive call */ STN[top]: = n; STBEG[top]: = beg; begin STAUX [top]:= aux; n: = STN[top]; beg: = STBEG [top]; STEND [top]: = end; STADD [top]: = 3; aux: = STAUX [top]; /* saving return address */ end: = STEND [top]; add: = STADD [top]; n: = n-1; t:= aux; aux: = end; end: = t; top: = top – 1; goto add goto 1; end end; 20
S duy t cây quy Cách n gi n nh t duy t các nút trong m t cây nh phân theo th t n i là nh m t th t c quy nh sau: // duy t th t n i (Inorder traversal) type link = node; node = record info: …….; l, r: link end; procedure traverse(t: link); begin if t z then /* z is dummy node */ begin traverse(t.l); visit(t); traverse(t.r) end end; 21
Th t c duy t cây ti n th t (Pre-order) procedure traverse (t: link) begin if t z then begin visit(t); traverse(t.1); traverse(t.r) end end; Tr c khi kh quy th t c này, ta có th lo i b l nh g i quy th hai d dàng vì không có mã ch ng trình i sau nó. L nh g i quy th hai có th c chuy n thành m t l nh goto nh sau: 22
Kh quy uôi procedure traverse (t: link); label 0,1; begin 0: if t = z then goto 1; visit(t); traverse(t. l); t: = t.r; goto 0; 1: end; K thu t này c g i là kh quy uôi (tail-recursion removal). 23