YOMEDIA
Phân tích và thiết kế giải thuật
Chia sẻ: Lan Lan
| Ngày:
| Loại File: PDF
| Số trang:349
180
lượt xem
47
download
Download
Vui lòng tải xuống để xem tài liệu đầy đủ
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.
AMBIENT/
Chủ đề:
Nội dung Text: Phân tích và thiết kế giải thuật
- 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
Thêm tài liệu vào bộ sưu tập có sẵn:
Báo xấu
LAVA
ERROR:connection to 10.20.1.100:9315 failed (errno=111, msg=Connection refused)
ERROR:connection to 10.20.1.100:9315 failed (errno=111, msg=Connection refused)
Đang xử lý...
Thêm vào BST
Báo xấu
