Phân tích và thiết kế và giải thuật - Chương 1 Các khái niệm cơ bản

Chia sẻ: Ba Xoáy | Ngày: | Loại File: PDF | Số trang:0

Thêm vào BST

Báo xấu

86
lượt xem 9
download

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

Tài liệu tham khảo về bài giảng phân tích và thiết kế giải thuật.

Chủ đề:

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

Lưu

Nội dung Text: Phân tích và thiết kế và giải thuật - Chương 1 Các khái niệm cơ bản

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 c g i là thi công ki u d li u tr u t ng. Trong m t ADT 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 vn 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
3: writeln(beg, end); procedure hanoi(n, beg, aux, end: top: = top + 1; /* second integer); recursive call */ /* Stacks STN, STBEG, STAUX, STN[top]: = n; STEND, and STADD correspond, STBEG[top]: = beg; respectively, to variables N, BEG, AUX, STAUX[top]: aux; END and ADD */ STEND[top]: = end; label 1, 3, 5; STADD[top]: = 5; var t: integer; /* saving return address */ begin n: = n-1; t:= beg; beg: = aux; top: = 0; /* preparation for stacks */ aux: = t; goto 1; 1: if n = 1 then 5. /* translation of return point */ begin writeln(beg, end); goto 5 end; if top 0 then top: = top + 1; /* first recursive call */ begin STN[top]: = n; STBEG[top]: = beg; n: = STN[top]; STAUX [top]:= aux; beg: = STBEG [top]; STEND [top]: = end; aux: = STAUX [top]; STADD [top]: = 3; end: = STEND [top]; /* saving return address */ add: = STADD [top]; n: = n-1; t:= aux; aux: = end; top: = top – 1; goto add end: = t; end goto 1; 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; c g i là kh quy uôi (tail-recursion K thu t này removal). 23