Chương I Cấu trúc dữ liệu và giải thuật | Học viện Nông nghiệp Việt Nam

Tài liệu này cung cấp một cái nhìn tổng quan về cấu trúc dữ liệu và giải thuật, bao gồm các khái niệm cơ bản và mối quan hệ giữa chúng. Nó đi sâu vào định nghĩa của giải thuật, cấu trúc dữ liệu và sự tương tác của chúng, cung cấp thông tin về thiết kế và đánh giá của giải thuật. Tài liệu cũng khám phá các phương pháp khác nhau để diễn đạt giải thuật, chẳng hạn như liệt kê bước, sơ đồ luồng giải thuật và mã giả.

Trường:

Học viện Nông nghiệp Việt Nam 392 tài liệu

Thông tin:
42 trang 8 tháng trước

Bình luận

Vui lòng đăng nhập hoặc đăng ký để gửi bình luận.

Chương I Cấu trúc dữ liệu và giải thuật | Học viện Nông nghiệp Việt Nam

Tài liệu này cung cấp một cái nhìn tổng quan về cấu trúc dữ liệu và giải thuật, bao gồm các khái niệm cơ bản và mối quan hệ giữa chúng. Nó đi sâu vào định nghĩa của giải thuật, cấu trúc dữ liệu và sự tương tác của chúng, cung cấp thông tin về thiết kế và đánh giá của giải thuật. Tài liệu cũng khám phá các phương pháp khác nhau để diễn đạt giải thuật, chẳng hạn như liệt kê bước, sơ đồ luồng giải thuật và mã giả.

65 33 lượt tải Tải xuống
Bài ging Cu trúc d liu gii thut - Cơng 01
CHƯƠNG 1
CU TRÚC D LIU GII THUT
GV. Ngô Công Thng
B môn Công ngh phn mm Khoa
Công ngh thông tin
Website: dse.vnua.edu.vn/ncthang
1. Mi quan h gia cu trúc d liu và
gii thut
1.1.
Gii thut (thut toán, algorithms)
l Khái nim: Gii thut mt h thng các
thao c,c phép toán được thc hin
theo trình t nhất định trên mt s đi
ng d liệu nào đó, sao cho sau mt s
c hu hn ta có được kết qu mong
mun.
l Gii thut phn ánh c phép x , còn
đối ng x d liu.
Ngô Công Thng 1.2
1.1. Gii thut (thut toán, algorithms)
l Gii thut phi có các tính cht bn sau:
l Tính thc hin đưc:
l Tính kết thúc:
l Tính kết qu: Phi cho kết qu mong mun.
l Tính hiu qu:
l Tính duy nht:
l Tính tng quát: Phi áp dng cho mi bài toán cùng
loi.
l Tính hình thc (máy móc)
Ngô Công Thng Bài ging Cu trúc d liu gii thut - Cơng 01 1.3
1.2. Cu trúc d liu
l Khái nim d liu: D liu là các phn t biu
din các thông tin cn thiết choi toán.
l Mt i toán th c loi d liu: D liu
vào, d liu trung gian, d liu ra.
l D liu vào là d liu cần đưa vào để x lý, đây
chính là đầu vào ca i toán.
l D liu trung gian là d liu cha các kết qu trung
gian trong quá trình x lý.
l D liu ra là d liu cha kết qu mong mun ca
bài toán.
l Gii thut thc hin biến đổi t các d liu vào
thành các d liu ra.
Ngô Công Thng Bài ging Cu trúc d liu gii thut - Cơng 01 1.4
Bài ging Cu trúc d liu gii thut - Cơng 01
1.2.
Cu trúc d liu (tiếp)
l Ví d 1: Ta xéti toán tính hc bng cho
sinh viên theo chế độ hin hành.c d
liu ca bài toán bao gm:
l D liu vào: H tên, Đim c môn, S
trình các môn hc.
l D liu trung gian: Điểm trung bình
l D liu ra: Hc bng
Ngô Công Thng Bài ging Cu trúc d liu gii thut - Cơng 01 1.5
1.2. Cu trúc d liu (tiếp)
l Ví d 2: Xét bài toán giải phương trình bậc
hai
ax2 + bx + c = 0 . Các d liu ca bài
toán này như sau:
l D liu vào: a, b, c
l D liu trung gian: delta
l D liu ra: x1, x2
Ngô Công Thng 1.6
1.2. Cu trúc d liu (tiếp)
l D liu nguyên t là phn t d liệu cơ s
không th tách nh ra đưc,th mt ch
s, mt kí t, mt giá tr logic,... Trong mti
toán, d liu bao gm mt tp các d liu
nguyên t.
l T c d liu nguyên t ta th to thành các
cu trúc d liu bng các cách thc liên kết
khác. Chng hn liên kếtc kí t li vi nhau
to thành cu trúc d liu kiu xâu kí t, liên kết
các s li vi nhau theo kiu mt dãy s ta đưc
cu trúc d liu kiu mng mt chiu.
Ngô Công Thng Bài ging Cu trúc d liu gii thut - Cơng 01 1.7
1.2. Cu trúc d liu (tiếp)
l Tóm li, Cu trúc d liu tp hp các
phn t d liu liên kết vi nhau bng mt
cách nào đó. Nói ti cu trúc d liu là nói
ti cách t chc các phn t d liu như
thế nào.
Ngô Công Thng Bài ging Cu trúc d liu gii thut - Cơng 01 1.8
Bài ging Cu trúc d liu gii thut - Cơng 01
1.2. Cu trúc d liu (tiếp)
l Khái nim v Cu trúc lưu tr: Cách biu din
mt cu tc d liu trong b nh đưc gi là
cu trúc lưu trữ, đó chính là cách cài đt cu
trúc d liu trên máy vi tính.
l Có th có nhiu cấu trúc lưu tr khác nhau cho mt
cu trúc d liu. Chng hn mt cu trúc d liu kiu
mng ta có th lưu tr bng các ô nh kế tiếp nhau
trong b nh hoc có th lưu trữ bng các ô nh
không kế tiếp nhau trong b nh.
l Có th có nhiu cu trúc d liệu khác nhau được cài
đặt trong b nh bng mt cấu trúc lưu tr. Chng
hn cu trúc xâu kí t, cu trúc mảng đều có th cài
đặt trong b bng các ô kế tiếp nhau.
Ngô Công Thng Bài ging Cu trúc d liu gii thut - Cơng 01 1.9
1.2. Cu trúc d liu (tiếp)
l Mi mt ngôn ng lp trình đều có các
cu trúc d liu tiền định (định sn), bi
vy khi chn ngôn ng lp trình nào thì ta
phi chp nhn cu trúc d liu tiền định
ca nó, phi vn dng linh hot các cu
trúc d liu này vào bài toán cn gii
quyết.
Ngô Công Thng 1.10
1.3. Mi quan h gia cu trúc d liu
gii thut
l Xét ti gii thut thì phi xét gii thut đó tác
động trên cu trúc d liu nào.
l
Xét ti cu tc d liu thì phi hiu cu trúc d
liệu đó cần đưc tác động bng gii thut gì để
đưc kết qu mong mun.
l Cu trúc d liu o tgii thut đó. Khi cu
trúc d liệu thay đổi gii thuật cũng thay đổi
theo.
l Mi quan h gia cu trúc d liu gii thut
đưc Niklaus Wirth tng kết như sau:
Cu trúc d liu + Gii thut = Chương trình
Ngô Công Thng Bài ging Cu trúc d liu gii thut - Cơng 01 1.11
2. Các cách din đạt gii thut
2.1.
Litcác c bng li
l Trong cách din đạt này ta phi viết tng c
làm công việc gì: Bước 1, c 2….
Ngô Công Thng Bài ging Cu trúc d liu gii thut - Cơng 01 1.12
Bài ging Cu trúc d liu gii thut - Cơng 01
2.
Các cách din đạt gii thut
2.2.
Lưu đồ gii thut
l Lưu đồ gii thut mt đồ ng din
đạt các c thc hin ca gii thut.
l Lưu đồ gii thuật giúp người lp trình xem xét
s làm vic ca gii thut khá chi tiết c th.
l Lưu đồ gii thut bao gm các hình cơ bn ni
vi nhau bởi các đường có hưng.
Ngô Công Thng Bài ging Cu trúc d liu gii thut - Cơng 01 1.13
2.1. u đồ gii thut (tiếp)
l Các hình bản trong lưu đ gii thut
gm có:
l Hình elíp th hin s bt đầu kết thúc ca
gii thut.
Bt đầu Kết tc
l Hình ch nht ch các thaoc, công vic cn
thc hin.
Công vic
Ngô Công Thng 1.14
2.1. u đồ gii thut (tiếp)
l Các hình bản trong lưu đ gii thut
gm có:
l Hình thoi th hiện các điệu kin. Hình y có
một đường vào và hai đường ra ng vi hai
trường hp điu kin đúng hoặc điều kin sai.
Điu kin
Sai
Đúng
Ngô Công Thng Bài ging Cu trúc d liu gii thut - Cơng 01 1.15
Ví d: Lưu đồ gii thut tìm giá tr ln nht
trong mng s A có n phn t
Bt đu
max := A(1)
i := 2
S
i <= n
Đ
S
A(i) > max
Đ
max := A(i)
In giá tr max
Kết thúc
i := i + 1
Ngô Công Thng Bài ging Cu trúc d liu gii thut - Cơng 01 1.16
Bài ging Cu trúc d liu gii thut - Cơng 01
2.3. Gi
l Gi gi ngôn ng lp trình (ta ngôn
ng lp trình).
l Trong cách diễn đạt gii thut bng gi
mã, người ta s dng ngôn ng t nhiên
cùng vi các cu trúc chun ca mt ngôn
ng lp trình (Pascal) đ t gii thut.
Vì s dng c ngôn ng t nhiên nên có
th s dng các ký hiu toán hc để bn
mô t gii thut ngn gn, d hiểun.
Ngô Công Thng Bài ging Cu trúc d liu gii thut - Cơng 01 1.17
2.3.1. Quy định chung
l
Tên chương trình viết bng ch hoa,
th thêm du gạch ngang đt sau t
Program
l Li chú thích đặt gia hai du ngoc {.}.
Lời chú thích đưc quy ước dùng tiếng
Vit.
Ngô Công Thng 1.18
2.2.2.
Biu thc
l Các phép toán:
l S hc: +,
-, *, /, ^, DIV, MOD
l Quan h: < , = , > , , ,
l Logic: NOT, AND, OR, XOR
l Các giá tr Logic True, False
l Tên biến là mt dãy ch cái, ch s, du gch
ni ( _ ), bắt đầu bng ch cái, độ i không
gii hn.
l Biến ch s:
Tên[ch s] d :
a[i], b[i,j]
l Biu thc tương t như Pascal.
Ngô Công Thng Bài ging Cu trúc d liu gii thut - Cơng 01 1.19
2.2.3.
Câu lnh
l Các câu lnh th hin các thao tác, công vic
cn thc hin. Các câu lệnh được viết viết cách
nhau bi du ;
l Phép toán gán đưc hiu bi du := hoc
l Phép hoán đổi giá tr đưc hiu bi du :=:
hoc
l
Cu trúc tun t: Lit các công vic, các thao
tác theo th t. Để cho vic theo i đưc thun
tin có th đánh thêm th t 1), 2), 3) hoc a),
b), c)…
l Câu lnh ghép:
Begin s1; s2; ... ; sn; end
Trong đó si là câu lnh i
Ngô Công Thng Bài ging Cu trúc d liu gii thut - Cơng 01 1.20
Bài ging Cu trúc d liu gii thut - Cơng 01
2.2.3. Câu lnh
l
Câu lnh điu kin:
l
if B then S;
l if
B
then S1
else
S2;
trong đó B là biu thc
logic, S câu lnh.
Ngô Công Thng Bài ging Cu trúc d liu gii thut - Cơng 01
1.21
2.2.3. Câu lnh
l Câu lnh la chn:
CASE
B1: S1;
B2: S2;
. . .
Bn: Sn;
ELSE
Sn+1;
END CASE
Vi Bi (i=1, 2,…, n) các điu kin
Si (i=1, 2,…, n) các câu lnh
Ngô Công Thng
1.22
2.2.3. Câu lnh
l Câu lnh lp:
l Lp vi s ln lp biết trước:
FOR i:=m TO n
DO
S;
FOR i:= n
DOWNTO
m
DO
S;
Ngô Công Thng Bài ging Cu trúc d liu gii thut - Cơng 01
1.23
2.2.3. Câu lnh
Lp vi s ln lp không biết trước:
l
Kim tra điu kin trưc:
WHILE
B
DO S;
l
Kim tra điều kin sau:
REPEAT
S
UNTIL
B;
Ngô Công Thng Bài ging Cu trúc d liu gii thut - Cơng 01
1.24
Bài ging Cu trúc d liu gii thut - Cơng 01
2.2.3. Câu lnh
l Câu lnh chuyn:
GOTO n;
trong đó n là s hiu ca mt bước trong
gii thut.
l Câu lnh vào ra:
l READ(danh sách biến);
l WRITE(danh ch hng, biến, biu thc);
l Câu lnh kết thúc: END.
Ngô Công Thng Bài ging Cu trúc d liu gii thut - Cơng 01
1.25
Cu trúc gi chương trình
l Vào:
l Ra:
{Mô t}
Program TenCT;
1)
2)
….
End.
1.26
2.2.4.
Chương trình con
2.2.4.1.
Chương trình con dng hàm
- Vào:
- Ra:
{Mô t }
FUNCTION Tên_hàm(danh sách tham s)
S1; S2; . . .; Sn;
Tên_hàm:= biu thc; {Gtr tr v ca hàm}
RETURN
Ngô Công Thng Bài ging Cu trúc d liu gii thut - Cơng 01 1.27
2.2.4. Chương trình con
2.2.4.2.
Chương trình con dng th tc
- Vào:
- Ra: không
{Mô t}
PROCEDURE Tên_th_tc(danh sách tham s)
S1; S2; . . .; Sn;
RETURN
Ngô Công Thng Bài ging Cu trúc d liu gii thut - Cơng 01 1.28
Bài ging Cu trúc d liu gii thut - Cơng 01
2.2.4.3.
Li gi chương trình con
l Li gi chương trình con dng hàm
Tên_hàm( danh sách tham s thc s)
l Li gi chương trình con dng th tc
CALL Tên_th_tc( danh sách tham s thc s)
Ngô Công Thng Bài ging Cu trúc d liu gii thut - Cơng 01 1.29
Bài tp
l Tìm USCLN ca hai s nguyên dương a
và b.
l BTVN: Tính gần đúng e^x với độ c.xác
epsilon = 0.0001
Ngô Công Thng 1.30
Bài tp
l Viết gi cng hai ma trn kích
thước mxn. Y/c s dng c gi mã
chương trình gi chương trình con.
l Viết gi nhân hai ma trn. Y/c s dng
gi chương trình con.
l Viết gi m và đưa ra các s nguyên
t nh hơn số nguyên dương n cho trước.
Y/c s dng gi mã chương trình con.
Ngô Công Thng Bài ging Cu trúc d liu gii thut - Cơng 01 1.31
3.
Thiết kế đánh giá gii thut
3.1. Thiết kế thut gii
3.1.1. đun hóa vic gii quyết bài toán
l Khi thiết kế gii thut ta s dụng phương pháp mô
đun hoá. Nội dung của phương pháp mô đun hoá
coi bài toán lớn như mt mô đun chỉnh ri phân chia
thành c mô đun con, mỗi mô đun con lại được
phân chia tiếp, cho ti nhng mô đun ng vi các
phn việc cơ bn mà ta đã biết cách gii quyết.
l Với phương pháp mô đun hoá bài toán thì li gii ca
bài toán được t chc theo cu trúc cây (phân cp)
có dạng như sau:
Ngô Công Thng Bài ging Cu trúc d liu gii thut - Chương 01 1.2
Bài ging Cu trúc d liu gii thut - Chương 01
3.1.1. Mô đun hóa và vic gii quyết
bài toán
Ngô Công Thng Bài ging Cu trúc d liu gii thut - Chương 01 1.3
3.1.1. đun hóa vic gii quyết bài toán
(tiếp)
l Chiến thut gii quyết bài toán là chiến thuật “
chia để tr”, để th hin chiến thut đó người ta
dùng cách thiết kế “t đỉnh xuống” (Top -
Down).
l Cách thiết kế Top - Down hay thiết kế t khái
quát đến đến chi tiết th hiện như sau: Phân tích
tng quát toàn b vn đ xut phát t d liu
mc tiêu đ ra, đề cp đến vn đề ch yếu, ri
sau đó mới đi dần vào gii quyết các vn đề c
th mt cách chi tiết hơn.
Ngô Công Thng 1.4
3.1.1. đun hóa vic gii quyết bài toán
(tiếp)
l d: Bài toán đặt ra dùng máy vi tính đ
qun lương ca cán b trong nghip.
l Phân tích tng quát bài toán:
l D liu vào là mt tp h v lương, bao gồm các
bn ghi cha các thông tin v lương ca cán b. Bn
ghi gồm các trường: mã, h tên, đơn vị, h s
lương, phụ cp, n.
l Chương trình lập ra phải cho người s dng thc
hiện được các công vic chính sau:
1.
Tìm kiếm thông tin
2.
Cp nht thông tin
3.
In các bng tng hp lương
Ngô Công Thng Bài ging Cu trúc d liu gii thut - Chương 01 1.5
3.1.1. đun hóa vic gii quyết bài toán
(tiếp)
l Xut phát t phân tích tng quát trên ta
thy thut gii x phi gii quyết được 3
vấn đề sau:
1. Đọc tp: Đc thông tin t đĩa t vào b nh
2. X lý tp: X lý các thông tin để đưa ra kết
qu mong mun
3. Ghi tp: Lưu tr thông tin mi nht vào tp.
Trên s này ta đưa ra đồ gii thut
tổng quát n sau:
Ngô Công Thng Bài ging Cu trúc d liu gii thut - Chương 01 1.6
Bài ging Cu trúc d liu gii thut - Chương 01
đồ gii thut tng quát
Ngô Công Thng Bài ging Cu trúc d liu gii thut - Chương 01 1.7
d (tiếp)
l Các nhim v trên còn phc tp, cn phi
phân chia ra thànhc nhim v con.
Chng hn nhim v X TÊP” đưc
phân chia ra thành 3 nhim v con:
1. Tìm kiếm bn ghi
2. Cp nht bn ghi
3. In bn lương
Nhng nhim v con lại được chia ra
thành các nhim v nh n theo đồ
sau:
Ngô Công Thng 1.8
đồ gii thut chi tiết
Ngô Công Thng Bài ging Cu trúc d liu gii thut - Chương 01 1.9
3.1.1.
đun hóa vic gii quyết bài toán
(tiếp)
l Ưu đim ca cách thiết kế Top - Down:
l Gii quyết bài toán có địnhng, tránh sa đà vào
các chi tiết ph.
l Làm nn tng cho lp trình cu trúc.
l Bài toán do nhiều người cùng làm, phương pháp
đun hoá tách bài toán thành nhiu i toán con to
cho các nhóm làm việc độc lp, không ảnh ng
đến nhóm khác.
l Chương trình xây dng trên gii thut thiết kế theo
kiu Top - Down d dàng trong chnh sa.
Ngô Công Thng Bài ging Cu trúc d liu gii thut - Chương 01 1.10
Bài ging Cu trúc d liu gii thut - Chương 01
3.1.2.
Phương pháp tinh chnh dn
từng bước
l Phương pháp tinh chnh tng c là phương pháp
thiết kế gii thut gn lin vi lp trình, nó phn ánh tinh
thn của quá trình mô đun hóa bài toán và thiết kế kiu
Top - Down.
l Phương pháp này thể hiện n sau: Đầu tiên trình bày
gii thut bng ngôn ng t nhiên để phn ánh ý chính
ca công vic cần làm. Các bước tiếp theo s chi tiết
hoá dn dần, tương ứng vi các công vic nh n, gọi
là các bưc tinh chnh. Càng các bước sau thì công
việc được mô t ng ti các lnh ca gi mã.
Ngôn ng t nhiên Các c tinh chnh Gi
Trong quá trình này d liệu cũng được tinh chnh dn t
dng cấu trúc đến dạng cài đt c th.
Ngô Công Thng Bài ging Cu trúc d liu gii thut - Chương 01 1.11
Ví d 1: Sp xếp mt dãy n s
nguyên theo th t tăng dn
l Đầu tiên ta phác tho gii thut theo ngôn ng
t nhiên như sau:
l T dãy các s nguyên chưa đưc sp xếp ly ra s
nh nht.
l C lp li quá trình đó cho đến khi dãy chưa được
sp xếp tr thành rng.
l Các bước tinh chnh dùng gi nn ng Pascal
:
1. c tinh chnh đầu tiên:
For
i:=1 To n-1 Do Begin
-
Xét t a
i
đến a
n
để m s nh nht a
k
-
Đổi ch gia a
i
a
k
End
Ngô Công Thng 1.12
Ví d 1: Sp xếp mt dãy n s
nguyên theo th t tăng dn
l Các c tinh chnh ng gi ngôn ng
Pascal:
2. c tinh chnh 2.1: Tìm s nh nht
k:=i
For j:= i+1 To n
Do
If aj < ak
Then
k:=j
3. c tinh chnh 2.2: Đổi ch
x:=ai ; ai:=ak ; ak=x;
Ngô Công Thng i ging Cu trúc d liu gii thut - Chương 01 1.13
Ví d 1: Sp xếp mt dãy n s
nguyên theo th t tăng dn
l Sau khi chnh li ta có th tc sp xếp như sau:
Procedure SapXep(a,n)
1) For i :=1 To n-1 Do
Begin
2) k :=i
For j :=i+1 To n Do
If a[j] < a[k] Then
k :=j
3) x:=a[i]; a[i]:=a[k]; a[k]:=x;
End
Return
Ngô Công Thng Bài ging Cu trúc d liu gii thut - Chương 01 1.14
Bài ging Cu trúc d liu gii thut - Chương 01
Ví d 2: Cho ma trn cp mxn (m hàng, n ct). Tìm
phn t ln nht của các hàng và đổi ch nó cho
phn t đầu hàng.
l Phác ho thut gii:
1. Nhp m,n
2. Nhp các phn t ca ma trn
3. Tìm phn t ln nht của các hàng và đi
ch cho phn t đầu hàng.
4. In ra ma trn
Ngô Công Thng Bài ging Cu trúc d liu gii thut - Chương 01 1.15
Ví d 2: Cho ma trn cp mxn (m hàng, n ct). Tìm
phn t ln nht của các hàng và đổi ch nó cho
phn t đầu hàng.
l Din đạt bng gi ngôn ng Pascal:
1. Read(m,n)
2. For i:= 1 To m
Do
Đọc o các phn t hàng i
3. For i:= 1 To m Do
Begin
m a[i,k] phn t ln nht cho hàng i
Đổi ch gia a[i,k] và a[i,1]
End
4. For i:=1 To m Do
In ra các phn t hàng i
Ngô Công Thng 1.16
Ví d 2: Cho ma trn cp mxn (m hàng, n ct). Tìm
phn t ln nht của các hàng và đổi ch nó cho
phn t đầu hàng
l c c đưc tinh chnh như sau:
1. Readln(m,n)
2. For i:=1 To m Do
For j:= 1 To n Do
Read(a[i,j])
3. For i:=1 To m Do
Begin
End
4. For i:= 1 To m Do
Begin
k:=1
For j:=2 To n Do
If
a[i,j]> a[i,k] Then k:=j
a[i,k] <-> a[i,1]
Writeln;
For j:=1 To n Do
Write(a[i,j], ‘)
End
Ngô Công Thng Bài ging Cu trúc d liu gii thut - Chương 01 1.17
3.2. Phân tích, đánh giá gii thut
3.2.1. Đặt vn đ
l Phân tích tính đúng đắn: Chy th chương trình
trên b d liu, so sánh kết qu vi kết qu đã
biết.
l Các công c toán hc chng minh tính đúng
đắn ca gii thut.
l Tính đơn gin: D hiu, d lp trình, d chnh .
l Phân tích thi gian: Thi gian thc hin gii
thut là tiêu chun đánh giá hiu lc ca gii
thut.
Ngô Công Thng Bài ging Cu trúc d liu gii thut - Chương 01 1.18
3.2.2. Phân tích thi gian thc hin
gii thut
l Vi mt bài toán có nhiu gii thut, ta cn chn
gii thut dn đến kết qu nhanh nht.
l Thi gian thc hin ph thuc vào nhiu yếu t
như:
l Kích thước ca d liu vào. Nếu gọi n là kích thước ca
d liu vào thì thi gian thc hin T ca mt gii thut
phải được biu din như mt hàm ca n: T(n)
l Các kiu lnh, tốc độ x lý ca máy tính, ngôn ng viết
chương trình, chương trình dịch cũng ảnh hưởng đến tc
độ thc hin. Nhưng nhng yếu t này không đng đều
vi mi loi máy tính, vy không th đưa chúng vào
xác lp T(n). Điu đó cũng nghĩa T(n) không th
tính theo đơn v gy, phút…
Ngô Công Thng Bài ging Cu trúc d liu gii thut - Chương 01 1.19
3.2.3. Độ phc tp tính toán ca gii thut
l Cách đánh giá thi gian thc hin gii thut không ph
thuc vào máy tính và các yếu t liên quan mà ch ph thuc
vàoch thưc d liệu đầu vào được gi là đánh giá theo
“Đ phc tp tính toán ca gii thuật”.
l Nếu thi gian thc hin mt gii thut là T(n) = Cn
2
, trong đó
C là hng số, thì ta nói độ phc tp tính toán ca gii thut
y có cp n
2
, và đưc hiu là: T(n)= O(n
2
)
l Tng quát: Hàm f(n) đưc gọi là có độ phc tp tính toán
cp g(n), kí hiu f(n) = O(g(n)), nếu tn ti các hng s C
và n
0
sao cho:
f(n) Cg(n) vi n n
0
nghĩa là m f(n) b chn trên bi Cg(n), vi C là hng s
vi mi n t mt điểmo đó.
l d 1: f(n) = O(n
3
) nghĩa độ phc tp tính toán cp n
3
l d 2: f(n) = O(2
n
) nghĩa độ phc tp tính toán cp 2
n
Ngô Công Thng Bài ging Cu trúc d liu gii thut - Chương 01 1.20
3.2.3. Đ phc tp tính toán ca
gii thut (tiếp)
l Các m th hiện độ phc tp tính toán ca gii thut
các dng sau: n
n
, n!, 2
n
, n
3
, n
2
, nlog
2
n, n, log
2
n. Các
hàm này đã đưc sp theo g tr gim dn, nghĩa
vi cùng mt gtr ca n, hàm n
n
ln nht, log
2
n là
nh nht. Các hàm này có dng đồ th như sau:
Ngô Công Thng Bài ging Cu trúc d liu gii thut - Chương 01 1.21
3.2.3. Đ phc tp tính toán ca
gii thut (tiếp)
l Các hàm n
n
, n! , 2
n
gọi là c hàm mũ.
Mt gíi thuật có độ phc tp tính toán
cp m thì rt chm, do đó khó đưc
chp nhn.
l Các hàm n
3
, n
2
, nlog
2
n, n, log
2
n là các
hàm loi đa thc. Độ phc tp tính toán
ca gii thut có cấp đa thc thì chp
nhận được.
Ngô Công Thng Bài ging Cu trúc d liu gii thut - Chương 01 1.22
Bài ging Cu trúc d liu gii thut - Chương 01
3.2.4. Xác định độ phc tp tính toán
l Quy tc cng:
l Gi s T1(n) và T2(n) là thi gian thc hin 2
đoạn chương trình P1 và P2 mà T1(n)=
O(f(n)), T2(n)=O(g(n)), thì thi gian thc hin
P1 rồi đến P2 tiếp theo s là: T1(n) + T2(n) =
O(max(f(n),g(n)))
l
dụ: Chương trình có 3 c, mỗi c
độ phc tp nh toán lần lượt là O(n
3
), O(n),
O(nlog
2
n). Vy thi gian thc hin 3 c là:
T1(n) + T2(n) + T3(n) = O(max(n
3
, n, nlog
2
n)
= O(n
3
)
Ngô Công Thng Bài ging Cu trúc d liu gii thut - Chương 01 1.23
3.2.4. Xác định đ phc tp tính toán
(tiếp)
l Quy tc nhân:
l Nếu tương ứng với 2 bưc P1 và P2 là T1(n) =
O(f(n)),T2(n) = O(g(n)) thì thi gian thc hin P1 và
P2 lng nhau : T1(n).T2(n) = O(f(n).g(n))
l Ví d: Câu lnh x:=x+1 có thi gian thc hin bng
hng s C => T(n) =O(1)
Câu lnh: For i :=1
To
n
Do x :=x+1;
có thi gian thc hin là: T(n)=O(n.1)=O(n)
Câu lnh
For i :=1 To n Do
For j :=1
To n
Do x:=x+1;
thi gian thc hin đưc đánh giá là:
T(n)= O(n.n)
= O(n
2
)
Ngô Công Thng 1.24
3.2.4. Xác định đ phc tp tính toán
(tiếp)
l Quy tc b hng s
l O(c.f(n)) = O(f(n), trong đó c mt hng s.
l d: O(n
2
/3) =
O(n
2
)
l Chú ý 1: Khi đánh giá thời gian thc hin
gii thut ta ch cn chú ý tới các bưc
tương ng vi mt phép toán đưc gi là
phép toánch cc. Đó là phép toán
thi gian thc hiện nó không ít hơn thời
gian thc hin các phép toán khác.
Ngô Công Thng Bài ging Cu trúc d liu gii thut - Chương 01 1.25
3.2.4. Xác định đ phc tp tính toán
(tiếp)
l Các c c định O ca mt gii thut:
B1: Xác định phép toán tích cc trong gii thut.
B2: Đếm s ln thc hin phép toán tích cc, biu
din s đếm này thành mt hàm ph thuc vào
kích thước d liệu đầu vào n, f(n)
B3: Coi O(f(n)), s dng đnh nghĩa O các quy
tắc xác định O để tìm ra O cui cùng.
Ngô Công Thng Bài ging Cu trúc d liu gii thut - Chương 01 1.26
Bài ging Cu trúc d liu gii thut - Chương 01
3.2.4. Xác định đ phc tp tính toán
(tiếp)
l Ví d: e
x
= 1+ x/1! + x
2
/2! + . . .+ x
n
/n! vi xn
cho trước.
l Gii thut 1:
1) Read(x,n); s:=1;
2) For i :=1 To n Do
begin
p:=1;
For j :=1 To i Do p:=p*x/j ;
s:=s+p;
end;
Ngô Công Thng Bài ging Cu trúc d liu gii thut - Chương 01 1.27
3.2.4. Xác định đ phc tp tính toán
(tiếp)
l Trong gii thut 1 phép toán tích cc
đây là p:=p*x/j. Ta thy đưc thc hin
vi s ln là: 1+2+3+ . . . + n = n(n+1)/2
Vy thi gian thc hin gii thut là: T(n) =
O(n
2
)
Ngô Công Thng 1.28
3.2.4. Xác định đ phc tp tính toán
(tiếp)
l Gii thut 2:
1) Read(x,n); s:=1; p:=1;
2) For i :=1 To n Do
begin
p:=p*x/i;
s:=s+p;
end;
Thi gian thc hin gii thut 2 là: T(n) = O(n)
Ngô Công Thng Bài ging Cu trúc d liu gii thut - Chương 01 1.29
3.2.4. Xác định đ phc tp tính toán
(tiếp)
l Gii thut 3:
1) Read(x); s:=1; p:=1; i:=0;
2) Repeat
i:=i+1;
p:=p*x/i;
s:=s+p;
Until | p | < Epsilon;
end.
3) Write(s);
Ngô Công Thng Bài ging Cu trúc d liu gii thut - Chương 01 1.30
Bài ging Cu trúc d liu gii thut - Chương 01
3.2.4. Xác định đ phc tp tính toán
(tiếp)
l Chú ý 2: Có những trưng hp thi gian thc hin gii
thut không ch ph thuộc vàoch thưc ca d liu
vào mà còn ph thuc vào chính tình trng ca d liu
đó nữa.
l Khi phân tích thi gian thc hin gii thut ta phit
xem vi mi d liu vào có kích tc n thì T(n) trong
trường hp thun li nhất, trường hp trung bình và
trường hp xu nhất như thế nào?
l Việc xác định T(n) trong trưng hợp trung bình thường
khó phi dùng ti nhng công c toán đặc bit. Bi
vậy người ta thường đánh giá giải thut bng T(n) trong
trường hp xu nht.
Ngô Công Thng Bài ging Cu trúc d liu gii thut - Chương 01 1.31
3.2.4. Xác định đ phc tp tính toán
(tiếp)
l Ví d: Cho véc a n phn t a1, a2,..., an. Tìm trong a phn t
đầu tiên có g tr = x cho trước.
l Gii thut n sau:
Found := False;
i:=1;
While (i<=n) and Not Found Do
If a[i] =x then begin
Found:=True;
k:=i;
Write(k);
end
else i:=i+1;
End.
T(n) trong trường hp tt
T(n)=O(1)
T(n) trong trường hp xu
T(n)=O(n) . Vây suy ra T(n)=O(n)
Ngô Công Thng 1.32
4.
Gii thut đệ quy
4.1. Khái nim đệ quy
l Ta nói mt đối tượng là đệ quy nếu nó được đnh nghĩa
i dng chính nó.
l Ví d 1: Trên màn hình ca vô tuyến truyn hình li xut
hin hình nh ca chính cái màn hình vô tuyến đó.
l d 2: Trong toán hc hay gp đnh nghĩa đệ quy:
1. Định nghĩa s t nhiên
a)
x s t nhiên nếu x-1 s t nhiên
b)
1 s t nhiên
2. Hàm n!
a)
n! = n*(n-1)! nếu n>0
b)
n!=1 nếu
n=0
Ngô Công Thng Bài ging Cu trúc d liu gii thut - Chương 02 2.33
4.2. Gii thut đệ quy th tc đệ quy
l Nếu li gii ca một bài toán T được thc hin
bng li gii ca bài toán T’ có dng ging như
T thì đó là mt li gii đệ quy. Trong đó T’ tuy
giống T nhưng nó phải nh hơn T.
l Gii thut tươngng vi li giải đệ quy gi
gii thut đ quy.
l Th tc viết cho bài toán có li gii đệ quy gi là
th tục đệ quy.
Trong th tc đệ quy có li gi ti chính nó, mi
ln gọi thì kích thước bài toán thu nh n và
dn dn tiến tới trường hp đc biệt là trường
hp suy biến.
Ngô Công Thng Bài ging Cu trúc d liu gii thut - Chương 02 2.34
Bài ging Cu trúc d liu gii thut - Chương 02
Ví d: Bài toán tìm 1 t trong cun
t đin
l Gii thut đệ quy ca bài toán này như sau:
IF t đin là mt trang THEN tìm t trong
trang y
ELSE
BEGIN
M t đin vào trang giữa; Xác định xem
na nào cha t
IF t nm trong nửa trước THEN tìm trong
nửa trước
ELSE tìm trong na sau
END
Ngô Công Thng Bài ging Cu trúc d liu gii thut - Chương 02 2.35
Ví d: Bài toán tìm 1 t trong cun
t đin
l Trong gii thut này 2 đim cn cý:
l Đim 1: Sau mi ln t điển được tách đôi, một na
thích hp s đưc tìm kiếm theo chiến thuật đã dùng.
l Điểm 2: Có trưng hp đặc bit là sau khi tách đôi t
đin ch còn 1 trang, gii quyết trc tiếp bng cách
tìm t trong trang đó. Trường hợp đặc bit này gi
trường hp suy biến.
l Gii thut này gi là gii thut chia đôi: Bài toán
được tách đôi ra bài toán nh hơn, bài toán nhỏ
hơn lại dùng chiến thut chia đôi, cho ti khi gp
trường hp suy biến.
Ngô Công Thng 2.36
Ví d: Bài toán tìm 1 t trong cun
t đin
l Th tc đệ quy ca bài toán đưc viết như sau:
Procedure timkiem(Tudien, tu)
IF Tudien ch còn mt trang THEN tìm t trong trang y
ELSE BEGIN
M t đim vào trang gia
Xác định xem na nào cha t
IF T nm nửa trước
THEN CALL timkiem(Tudien1, tu)
ELSE CALL timkiem(Tudien2, tu)
END
RETURN
Ngô Công Thng Bài ging Cu trúc d liu gii thut - Chương 02 2.37
4.3. Thiết kế gii thut đệ quy
l Khi bài toán đang xét hoặc d liệu đang xử lý
được định nghĩa dưi dạng đệ quy thì vic thiết
kế các gii thut đ quy t ra rt thun li.
l Khi thiết kế gii thut đ quy cn tr lic câu
hi sau:
1. Có th định nghĩa bài toán dưi dng mt i toán
cùng loại nhưng có quy mô nhỏ hơn. Đây được gi là
đệ quy.
2. Có trường hợp đặc biệt (trường hp suy biến) mà
đó kết thúc đệ quy.
Ngô Công Thng Bài ging Cu trúc d liu gii thut - Chương 02 2.38
Bài ging Cu trúc d liu gii thut - Chương 02
Bài toán 1: Tính n!
l Kh đệ quy ca hàm tính giai tha:
Function FAC(n)
If
n=0
then
gt:=1;
Else begin
gt:=1;
For i:=1 to n do gt:=gt*i;
end;
FAC:=gt;
Return
Ngô Công Thng
2.40
Bài toán 1: Tính n!
l Đối chiếu vi 3 đặc đim ca th tc đệ
quy ta thy:
l Li gi ti chính đng sau Else
l Mi ln gọi đệ quy giá tr giảm đi:
FAC(4)FAC(3)FAC(2) FAC(1)
l Trưng hp suy biến FAC(0): FAC(0) = 1
Ngô Công Thng Bài ging Cu trúc d liu gii thut - Chương 02 2.41
Bài toán 2: Lp dãy s FIBONACCI
1 1 2 3 5 8 13...
l Định nghĩa F(n) như sau:
F(n) = 1 nếu n 2
F(n)=F(n-2)+F(n-1) nếu n>2
l Th tc đệ quy th hin gii thut tính F(n) như
sau:
Function F(n:integer)
If n<=2 then F:=1
Else F:=F(n-2)+F(n-1)
Return
Ngô Công Thng Bài ging Cu trúc d liu gii thut - Chương 02 2.42
Bài ging Cu trúc d liu gii thut - Chương 02
Bài toán 3: Bài toán “Tháp ni
l Nội dung: Có n đĩa kích thước nh dn, đĩa có l
gia. Có th xếp chng chúng lên nhau xun
qua mt cái cọc, to dưới nh trên để cui cùng
có mt chng đĩa dạng như hình tháp.
Ngô Công Thng Bài ging Cu trúc d liu gii thut - Chương 02 2.43
Bài toán 3: Bài toán “Tháp ni”
l Yêu cu đặt ra: Chuyn chng đĩa t cc
A sang cc C theo những điều kin sau:
l Mi ln ch đưc chuyn mt đĩa
l Không khi nào có tình hung đĩa to trên đĩa
nh i
l Đưc phép s dng 1 cc trung gian (cc B)
để đặt tm thi.
Ngô Công Thng 2.44
Bài toán 3: Bài toán “Tháp ni”
l Ta xét mt vài trường hp đơn gin:
l Trưng hp 1 đĩa:
l Chuyn t cc A sang cc C
l Trưng hp 2 đĩa:
l Chuyn đĩa th nht t cc A sang cc B
l Chuyn đĩa th hai t cc A sang cc C
l Chuyn đĩa th nht t cc B sang cc C
Ngô Công Thng Bài ging Cu trúc d liu gii thut - Chương 02 2.45
Bài toán 3: Bài toán “Tháp ni”
l Trưng hợp n đĩa (n>2): Ta coi n-1 đĩa ở trên như
đĩa th nht và x lý giống như trưng hp 2 đĩa:
l Chuyn n-1 đĩa t cc A sang cc B
l Chuyn đĩa th n t cc A sang cc C
l Chuyn n-1 đĩa t cc B sang cc C
l Chuyn n-1 đĩa t cc B sang cc C thut gii s
:
l Chuyn n-2 đĩa t cc B sang cc A
l Chuyn 1 đĩa t cc B sang cc C
l Chuyn n-2 đĩa t cc B sang cc C
l C làm n vậy cho đến khi trường hp suy biến
xy ra, đó là trường hp ng vi bài toán chuyn 1
đĩa.
Ngô Công Thng Bài ging Cu trúc d liu gii thut - Chương 02 2.46
Bài ging Cu trúc d liu gii thut - Cơng 02
Bài toán 3: Bài toán “Tháp ni”
l Th tc ca bài toán “Tháp Hà nội” như sau:
Procedure Hanoi(n,A,B,C)
If n=1 then chuyn đĩa t A sang C
Else Begin
Call Hanoi(n-1,A,C,B)
Call Hanoi(1,A,B,C)
Call Hanoi(n-1,B,A,C)
End;
Return
Ngô Công Thng Bài ging Cu trúc d liu gii thut - Chương 02 2.47
Bài tp
1. Thế nào gii thut đệ quy?
2. Ưu nhưc đim ca gii thut đệ quy?
3. Trong b nh ca máynh dùng vùng nh nào để dùng
cho gii thuật đệ quy.
4. Trường hp suy biến là trường hợp như thế nào trong
gii thuật đệ quy.
5. Thường hay dùng cu trúc lập trình nào để th hin gii
thuật đệ quy
6. Viết gii thuật đệ quy cho bài toán sau:
Acker(m,n)= n+1 nếu m=0
Acker(m,n)= Acker(m-1,1) nếu n=0
Acker(m,n)= Acker(m-1,Acker(m,n-1)) với các trưng
hp khác.
Ngô Công Thng 2.48
Th tc đệ quy Bài 6
Function Acker(m,n:integer)
If m=0 then Acker:=n+1
else if n=0 then Acker:=Acker(m-1,1)
else Acker:=Acker(m-1,Acker(m,n-1))
Return
Ngô Công Thng Bài ging Cu trúc d liu gii thut - Chương 02 2.49
Bài tp (tiếp)
7.Gii thut tính ước s chung ln nht ca
hai s nguyên dương ab (a>b) như
sau:
Gi r s ca phép chia a cho b.
- Nếu r=0 thì b ưc s chung ln nht
- r khác 0 thì gán a:=b; b:=r ri lp li.
Hãy xây dng gii thut đệ quy tính ước
s chung ln nht USCLN(a,b)
Ngô Công Thng Bài ging Cu trúc d liu gii thut - Chương 02 2.50
Bài ging Cu trúc d liu gii thut - Chương 02
Th tc đệ quy bài 7
Bài toán: Tìm USCLN ca 2 s nguyên dương a,b
Cách 1: Dùng đệ quy
Function USCLN(a,b)
If b=0 then begin USCLN := a; return; end;
If b # 0 then USCLN := USCLN(b,a mod b);
Return
Ngô Công Thng Bài ging Cu trúc d liu gii thut - Chương 02 2.51
Th tc đệ quy bài 7
Bài toán: Tìm USCLN ca 2 s nguyên dương a,b
Cách 2: Kh đệ quy
Function USCLN(a,b)
1) r := a mod b;
2) while r # 0 do begin
a:=b; b:=r; r:= a mod b
end;
3) USCLN:=b;
Return
Ngô Công Thng 2.52
Th tc đệ quy bài 8
Function C(n,k:integer)
If k=0 then C:=1
else if k=n then C:=1
else C:=C(n-1,k-1)+C(n-1,k);
Return
Ngô Công Thng Bài ging Cu trúc d liu gii thut - Chương 02
2.54
| 1/42

Preview text:

CHƯƠNG 1
CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT GV. Ngô Công Thắng
Bộ môn Công nghệ phần mềm Khoa Công nghệ thông tin
Website: dse.vnua.edu.vn/ncthang
1. Mối quan hệ giữa cấu trúc dữ liệu và giải thuật
1.1. Giải thuật (thuật toán, algorithms)
l Khái niệm: Giải thuật là một hệ thống các
thao tác, các phép toán được thực hiện
theo trình tự nhất định trên một số đối
tượng dữ liệu nào đó, sao cho sau một số
bước hữu hạn ta có được kết quả mong muốn.
l Giải thuật phản ánh các phép xử lý, còn
đối tượng xử lý là dữ liệu. Ngô Công Thắng
Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 01 1.2
1.1. Giải thuật (thuật toán, algorithms)
l Giải thuật phải có các tính chất cơ bản sau:
l Tính thực hiện được: l Tính kết thúc:
l Tính kết quả: Phải cho kết quả mong muốn. l Tính hiệu quả: l Tính duy nhất:
l Tính tổng quát: Phải áp dụng cho mọi bài toán cùng loại.
l Tính hình thức (máy móc) Ngô Công Thắng
Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 01 1.3 1.2. Cấu trúc dữ liệu
l Khái niệm dữ liệu: Dữ liệu là các phần tử biểu
diễn các thông tin cần thiết cho bài toán.
l Một bài toán có thể có các loại dữ liệu: Dữ liệu
vào, dữ liệu trung gian, dữ liệu ra.
l Dữ liệu vào là dữ liệu cần đưa vào để xử lý, đây
chính là đầu vào của bài toán.
l Dữ liệu trung gian là dữ liệu chứa các kết quả trung
gian trong quá trình xử lý.
l Dữ liệu ra là dữ liệu chứa kết quả mong muốn của bài toán.
l Giải thuật thực hiện biến đổi từ các dữ liệu vào thành các dữ liệu ra. Ngô Công Thắng
Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 01 1.4
1.2. Cấu trúc dữ liệu (tiếp)
l Ví dụ 1: Ta xét bài toán tính học bổng cho
sinh viên theo chế độ hiện hành. Các dữ
liệu của bài toán bao gồm:
l Dữ liệu vào: Họ và tên, Điểm các môn, Số trình các môn học.
l Dữ liệu trung gian: Điểm trung bình
l Dữ liệu ra: Học bổng Ngô Công Thắng
Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 01 1.5
1.2. Cấu trúc dữ liệu (tiếp)
l Ví dụ 2: Xét bài toán giải phương trình bậc
hai ax2 + bx + c = 0 . Các dữ liệu của bài toán này như sau: l Dữ liệu vào: a, b, c
l Dữ liệu trung gian: delta l Dữ liệu ra: x1, x2 Ngô Công Thắng
Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 01 1.6
1.2. Cấu trúc dữ liệu (tiếp)
l Dữ liệu nguyên tử là phần tử dữ liệu cơ sở
không thể tách nhỏ ra được, có thể là một chữ
số, một kí tự, một giá trị logic,... Trong một bài
toán, dữ liệu bao gồm một tập các dữ liệu nguyên tử.
l Từ các dữ liệu nguyên tử ta có thể tạo thành các
cấu trúc dữ liệu bằng các cách thức liên kết
khác. Chẳng hạn liên kết các kí tự lại với nhau
tạo thành cấu trúc dữ liệu kiểu xâu kí tự, liên kết
các số lại với nhau theo kiểu một dãy số ta được
cấu trúc dữ liệu kiểu mảng một chiều. Ngô Công Thắng
Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 01 1.7
1.2. Cấu trúc dữ liệu (tiếp)
l Tóm lại, Cấu trúc dữ liệu là tập hợp các
phần tử dữ liệu liên kết với nhau bằng một
cách nào đó. Nói tới cấu trúc dữ liệu là nói
tới cách tổ chức các phần tử dữ liệu như thế nào. Ngô Công Thắng
Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 01 1.8
1.2. Cấu trúc dữ liệu (tiếp)
l Khái niệm về Cấu trúc lưu trữ: Cách biểu diễn
một cấu trúc dữ liệu trong bộ nhớ được gọi là
cấu trúc lưu trữ, đó chính là cách cài đặt cấu
trúc dữ liệu trên máy vi tính.
l Có thể có nhiều cấu trúc lưu trữ khác nhau cho một
cấu trúc dữ liệu. Chẳng hạn một cấu trúc dữ liệu kiểu
mảng ta có thể lưu trữ bằng các ô nhớ kế tiếp nhau
trong bộ nhớ hoặc có thể lưu trữ bằng các ô nhớ
không kế tiếp nhau trong bộ nhớ.
l Có thể có nhiều cấu trúc dữ liệu khác nhau được cài
đặt trong bộ nhớ bằng một cấu trúc lưu trữ. Chẳng
hạn cấu trúc xâu kí tự, cấu trúc mảng đều có thể cài
đặt trong bộ bằng các ô kế tiếp nhau. Ngô Công Thắng
Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 01 1.9
1.2. Cấu trúc dữ liệu (tiếp)
l Mỗi một ngôn ngữ lập trình đều có các
cấu trúc dữ liệu tiền định (định sẵn), bởi
vậy khi chọn ngôn ngữ lập trình nào thì ta
phải chấp nhận cấu trúc dữ liệu tiền định
của nó, phải vận dụng linh hoạt các cấu
trúc dữ liệu này vào bài toán cần giải quyết. Ngô Công Thắng
Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 01 1.10
1.3. Mối quan hệ giữa cấu trúc dữ liệu và giải thuật
l Xét tới giải thuật thì phải xét giải thuật đó tác
động trên cấu trúc dữ liệu nào.
l Xét tới cấu trúc dữ liệu thì phải hiểu cấu trúc dữ
liệu đó cần được tác động bằng giải thuật gì để
được kết quả mong muốn.
l Cấu trúc dữ liệu nào thì giải thuật đó. Khi cấu
trúc dữ liệu thay đổi giải thuật cũng thay đổi theo.
l Mối quan hệ giữa cấu trúc dữ liệu và giải thuật
được Niklaus Wirth tổng kết như sau:
Cấu trúc dữ liệu + Giải thuật = Chương trình Ngô Công Thắng
Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 01 1.11
2. Các cách diễn đạt giải thuật
2.1. Liệt kê các bước bằng lời
l Trong cách diễn đạt này ta phải viết từng bước
làm công việc gì: Bước 1, Bước 2…. Ngô Công Thắng
Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 01 1.12
2. Các cách diễn đạt giải thuật
2.2. Lưu đồ giải thuật
l Lưu đồ giải thuật là một sơ đồ có hướng diễn
đạt các bước thực hiện của giải thuật.
l Lưu đồ giải thuật giúp người lập trình xem xét
sự làm việc của giải thuật khá chi tiết và cụ thể.
l Lưu đồ giải thuật bao gồm các hình cơ bản nối
với nhau bởi các đường có hướng. Ngô Công Thắng
Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 01 1.13
2.1. Lưu đồ giải thuật (tiếp)
l Các hình cơ bản trong lưu đồ giải thuật gồm có:
l Hình elíp thể hiện sự bắt đầu và kết thúc của giải thuật. Bắt đầu Kết thúc
l Hình chữ nhật chỉ các thao tác, công việc cần thực hiện. Công việc Ngô Công Thắng
Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 01 1.14
2.1. Lưu đồ giải thuật (tiếp)
l Các hình cơ bản trong lưu đồ giải thuật gồm có:
l Hình thoi thể hiện các điệu kiện. Hình này có
một đường vào và hai đường ra ứng với hai
trường hợp điều kiện đúng hoặc điều kiện sai. Sai Điều kiện Đúng Ngô Công Thắng
Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 01 1.15
Ví dụ: Lưu đồ giải thuật tìm giá trị lớn nhất
trong mảng số A có n phần tử Bắt đầu max := A(1) i := 2 S i <= n Đ S In giá trị max A(i) > max Đ Kết thúc max := A(i) i := i + 1 Ngô Công Thắng
Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 01 1.16 2.3. Giả mã
l Giả mã là giả ngôn ngữ lập trình (tựa ngôn ngữ lập trình).
l Trong cách diễn đạt giải thuật bằng giả
mã, người ta sử dụng ngôn ngữ tự nhiên
cùng với các cấu trúc chuẩn của một ngôn
ngữ lập trình (Pascal) để mô tả giải thuật.
Vì sử dụng cả ngôn ngữ tự nhiên nên có
thể sử dụng các ký hiệu toán học để bản
mô tả giải thuật ngắn gọn, dễ hiểu hơn. Ngô Công Thắng
Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 01 1.17 2.3.1. Quy định chung
l Tên chương trình viết bằng chữ hoa, có
thể thêm dấu gạch ngang và đặt sau từ Program
l Lời chú thích đặt giữa hai dấu ngoặc {….}.
Lời chú thích được quy ước dùng tiếng Việt. Ngô Công Thắng
Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 01 1.18 2.2.2. Biểu thức l Các phép toán:
l Số học: +, -, *, /, ^, DIV, MOD
l Quan hệ: < , = , > ,  , ,  l Logic: NOT, AND, OR, XOR
l Các giá trị Logic là True, False
l Tên biến là một dãy chữ cái, chữ số, dấu gạch
nối ( _ ), bắt đầu bằng chữ cái, độ dài không giới hạn.
l Biến chỉ số: Tên[chỉ số] Ví dụ : a[i], b[i,j]
l Biểu thức tương tự như Pascal. Ngô Công Thắng
Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 01 1.19 2.2.3. Câu lệnh
l Các câu lệnh thể hiện các thao tác, công việc
cần thực hiện. Các câu lệnh được viết viết cách nhau bởi dấu ;
l Phép toán gán được ký hiệu bởi dấu := hoặc 
l Phép hoán đổi giá trị được ký hiệu bởi dấu :=: hoặc 
l Cấu trúc tuần tự: Liệt kê các công việc, các thao
tác theo thứ tự. Để cho việc theo dõi được thuận
tiện có thể đánh thêm thứ tự 1), 2), 3)… hoặc a), b), c)… l Câu lệnh ghép: Begin s1; s2; ... ; sn; end
Trong đó si là câu lệnh i Ngô Công Thắng
Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 01 1.20 2.2.3. Câu lệnh l Câu lệnh điều kiện: l if B then S; l if B then S1 else S2; trong đó B là biể u thức logic, S là câu lệnh. Ngô Công Thắng
Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 01 1.21 2.2.3. Câu lệnh l Câu lệnh lựa chọn: CASE B1: S1; B2: S2; . . . Bn: Sn; ELSE Sn+1; END CASE
Với Bi (i=1, 2,…, n) là các điều kiện
Si (i=1, 2,…, n) là các câu lệnh Ngô Công Thắng
Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 01 1.22 2.2.3. Câu lệnh l Câu lệnh lặp:
l Lặp với số lần lặp biết trước: FOR i:=m TO n DO S; FOR i:= n DOWNTO m DO S; Ngô Công Thắng
Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 01 1.23 2.2.3. Câu lệnh
Lặp với số lần lặp không biết trước:
l Kiểm tra điều kiện trước: WHILE B DO S;
l Kiểm tra điều kiện sau: REPEAT S UNTIL B; Ngô Công Thắng
Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 01 1.24 2.2.3. Câu lệnh l Câu lệnh chuyển: GOTO n; trong đó n là số
hiệu của một bước trong giải thuật. l Câu lệnh vào ra: l READ(danh sách biến); l
WRITE(danh sách hằng, biến, biểu thức);
l Câu lệnh kết thúc: END. Ngô Công Thắng
Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 01 1.25
Cấu trúc giả mã chương trình l Vào: l Ra: {Mô tả} Program TenCT; 1) 2) …. End.
Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 01 1.26 2.2.4. Chương trình con
2.2.4.1. Chương trình con dạng hàm - Vào: - Ra: {Mô tả }
FUNCTION Tên_hàm(danh sách tham số) S1; S2; . . .; Sn;
Tên_hàm:= biểu thức; {Giá trị trả về của hàm} RETURN Ngô Công Thắng
Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 01 1.27 2.2.4. Chương trình con
2.2.4.2. Chương trình con dạng thủ tục - Vào: - Ra: không có {Mô tả}
PROCEDURE Tên_thủ_tục(danh sách tham số) S1; S2; . . .; Sn; RETURN Ngô Công Thắng
Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 01 1.28
2.2.4.3. Lời gọi chương trình con
l Lời gọi chương trình con dạng hàm
Tên_hàm( danh sách tham số thực sự)
l Lời gọi chương trình con dạng thủ tục
CALL Tên_thủ_tục( danh sách tham số thực sự) Ngô Công Thắng
Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 01 1.29 Bài tập
l Tìm USCLN của hai số nguyên dương a và b.
l BTVN: Tính gần đúng e^x với độ c.xác epsilon = 0.0001 Ngô Công Thắng
Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 01 1.30 Bài tập
l Viết giả mã cộng hai ma trận có kích
thước mxn. Y/c sử dụng cả giả mã
chương trình và giả mã chương trình con.
l Viết giả mã nhân hai ma trận. Y/c sử dụng
giả mã chương trình con.
l Viết giả mã tìm và đưa ra các số nguyên
tố nhỏ hơn số nguyên dương n cho trước.
Y/c sử dụng giả mã chương trình con. Ngô Công Thắng
Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 01 1.31
3. Thiết kế và đánh giá giải thuật
3.1. Thiết kế thuật giải
3.1.1. Mô đun hóa việc giải quyết bài toán
l Khi thiết kế giải thuật ta sử dụng phương pháp mô
đun hoá. Nội dung của phương pháp mô đun hoá là
coi bài toán lớn như một mô đun chỉnh rồi phân chia
nó thành các mô đun con, mỗi mô đun con lại được
phân chia tiếp, cho tới những mô đun ứng với các
phần việc cơ bản mà ta đã biết cách giải quyết.
l Với phương pháp mô đun hoá bài toán thì lời giải của
bài toán được tổ chức theo cấu trúc cây (phân cấp) có dạng như sau: Ngô Công Thắng
Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 01 1.2
3.1.1. Mô đun hóa và việc giải quyết bài toán Ngô Công Thắng
Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 01 1.3
3.1.1. Mô đun hóa việc giải quyết bài toán (tiếp)
l Chiến thuật giải quyết bài toán là chiến thuật “
chia để trị”, để thể hiện chiến thuật đó người ta
dùng cách thiết kế “từ đỉnh xuống” (Top - Down).
l Cách thiết kế Top - Down hay thiết kế từ khái
quát đến đến chi tiết thể hiện như sau: Phân tích
tổng quát toàn bộ vấn đề xuất phát từ dữ liệu và
mục tiêu đề ra, đề cập đến vấn đề chủ yếu, rồi
sau đó mới đi dần vào giải quyết các vấn đề cụ
thể một cách chi tiết hơn. Ngô Công Thắng
Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 01 1.4
3.1.1. Mô đun hóa việc giải quyết bài toán (tiếp)
l Ví dụ: Bài toán đặt ra là dùng máy vi tính để
quản lý lương của cán bộ trong xí nghiệp.
l Phân tích tổng quát bài toán:
l Dữ liệu vào là một tệp hồ sơ về lương, bao gồm các
bản ghi chứa các thông tin về lương của cán bộ. Bản
ghi gồm các trường: mã, họ và tên, đơn vị, hệ số lương, phụ cấp, nợ.
l Chương trình lập ra phải cho người sử dụng thực
hiện được các công việc chính sau: 1. Tìm kiếm thông tin 2. Cập nhật thông tin
3. In các bảng tổng hợp lương Ngô Công Thắng
Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 01 1.5
3.1.1. Mô đun hóa việc giải quyết bài toán (tiếp)
l Xuất phát từ phân tích tổng quát ở trên ta
thấy thuật giải xử lý phải giải quyết được 3 vấn đề sau:
1. Đọc tệp: Đọc thông tin từ đĩa từ vào bộ nhớ
2. Xử lý tệp: Xử lý các thông tin để đưa ra kết quả mong muốn
3. Ghi tệp: Lưu trữ thông tin mới nhất vào tệp.
Trên cơ sở này ta đưa ra sơ đồ giải thuật tổng quát như sau: Ngô Công Thắng
Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 01 1.6
Sơ đồ giải thuật tổng quát Ngô Công Thắng
Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 01 1.7 Ví dụ (tiếp)
l Các nhiệm vụ trên còn phức tạp, cần phải
phân chia ra thành các nhiệm vụ con.
Chẳng hạn nhiệm vụ “ XỬ LÝ TÊP” được
phân chia ra thành 3 nhiệm vụ con: 1. Tìm kiếm bản ghi 2. Cập nhật bản ghi 3. In bản lương
Những nhiệm vụ con lại được chia ra
thành các nhiệm vụ nhỏ hơn theo sơ đồ sau: Ngô Công Thắng
Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 01 1.8
Sơ đồ giải thuật chi tiết Ngô Công Thắng
Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 01 1.9
3.1.1. Mô đun hóa việc giải quyết bài toán (tiếp)
l Ưu điểm của cách thiết kế Top - Down:
l Giải quyết bài toán có định hướng, tránh sa đà vào các chi tiết phụ.
l Làm nền tảng cho lập trình có cấu trúc.
l Bài toán do nhiều người cùng làm, phương pháp mô
đun hoá tách bài toán thành nhiều bài toán con tạo
cho các nhóm làm việc độc lập, không ảnh hưởng đến nhóm khác.
l Chương trình xây dựng trên giải thuật thiết kế theo
kiểu Top - Down dễ dàng trong chỉnh sửa. Ngô Công Thắng
Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 01 1.10
3.1.2. Phương pháp tinh chỉnh dần từng bước l
Phương pháp tinh chỉnh từng bước là phương pháp
thiết kế giải thuật gắn liền với lập trình, nó phản ánh tinh
thần của quá trình mô đun hóa bài toán và thiết kế kiểu Top - Down. l
Phương pháp này thể hiện như sau: Đầu tiên trình bày
giải thuật bằng ngôn ngữ tự nhiên để phản ánh ý chính
của công việc cần làm. Các bước tiếp theo sẽ chi tiết
hoá dần dần, tương ứng với các công việc nhỏ hơn, gọi
là các bước tinh chỉnh. Càng ở các bước sau thì công
việc được mô tả hướng tới các lệnh của giả mã.
Ngôn ngữ tự nhiên  Các bước tinh chỉnh  Giả mã
Trong quá trình này dữ liệu cũng được tinh chỉnh dần từ
dạng cấu trúc đến dạng cài đặt cụ thể. Ngô Công Thắng
Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 01 1.11
Ví dụ 1: Sắp xếp một dãy n số
nguyên theo thứ tự tăng dần
l Đầu tiên ta phác thảo giải thuật theo ngôn ngữ tự nhiên như sau:
l Từ dãy các số nguyên chưa được sắp xếp lấy ra số nhỏ nhất.
l Cứ lặp lại quá trình đó cho đến khi dãy chưa được
sắp xếp trở thành rỗng.
l Các bước tinh chỉnh dùng giả ngôn ngữ Pascal là:
1. Bước tinh chỉnh đầu tiên: For i:=1 To n-1 Do Begin
- Xét từ ai đến an để tìm số nhỏ nhất ak
- Đổi chỗ giữa ai và ak End Ngô Công Thắng
Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 01 1.12
Ví dụ 1: Sắp xếp một dãy n số
nguyên theo thứ tự tăng dần
l Các bước tinh chỉnh dùng giả ngôn ngữ Pascal là:
2. Bước tinh chỉnh 2.1: Tìm số nhỏ nhất k:=i For j:= i+1 To n Do If aj < ak Then k:=j
3. Bước tinh chỉnh 2.2: Đổi chỗ x:=ai ; ai:=ak ; ak=x; Ngô Công Thắng
Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 01 1.13
Ví dụ 1: Sắp xếp một dãy n số
nguyên theo thứ tự tăng dần
l Sau khi chỉnh lại ta có thủ tục sắp xếp như sau: Procedure SapXep(a,n) 1) For i :=1 To n-1 Do Begin 2) k :=i For j :=i+1 To n Do If a[j] < a[k] Then k :=j 3) x:=a[i]; a[i]:=a[k]; a[k]:=x; End Return Ngô Công Thắng
Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 01 1.14
Ví dụ 2: Cho ma trận cấp mxn (m hàng, n cột). Tìm
phần tử lớn nhất của các hàng và đổi chỗ nó cho phần tử đầu hàng. l Phác hoạ thuật giải: 1. Nhập m,n
2. Nhập các phần tử của ma trận
3. Tìm phần tử lớn nhất của các hàng và đổi
chỗ cho phần tử đầu hàng. 4. In ra ma trận Ngô Công Thắng
Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 01 1.15
Ví dụ 2: Cho ma trận cấp mxn (m hàng, n cột). Tìm
phần tử lớn nhất của các hàng và đổi chỗ nó cho phần tử đầu hàng.
l Diễn đạt bằng giả ngôn ngữ Pascal: 1. Read(m,n) 2. For i:= 1 To m Do
Đọc vào các phần tử hàng i 3. For i:= 1 To m Do Begin
Tìm a[i,k] là phần tử lớn nhất cho hàng i
Đổi chỗ giữa a[i,k] và a[i,1] End 4. For i:=1 To m Do
In ra các phần tử hàng i Ngô Công Thắng
Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 01 1.16
Ví dụ 2: Cho ma trận cấp mxn (m hàng, n cột). Tìm
phần tử lớn nhất của các hàng và đổi chỗ nó cho phần tử đầu hàng l
Các bước được tinh chỉnh như sau: 1. Readln(m,n) 2. For i:=1 To m Do For j:= 1 To n Do Read(a[i,j]) 3. For i:=1 To m Do Begin k:=1 For j:=2 To n Do
If a[i,j]> a[i,k] Then k:=j a[i,k] <-> a[i,1] End 4. For i:= 1 To m Do Begin Writeln; For j:=1 To n Do Write(a[i,j], ‘ ‘) End Ngô Công Thắng
Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 01 1.17
3.2. Phân tích, đánh giá giải thuật 3.2.1. Đặt vấn đề
l Phân tích tính đúng đắn: Chạy thử chương trình
trên bộ dữ liệu, so sánh kết quả với kết quả đã biết.
l Các công cụ toán học chứng minh tính đúng đắn của giải thuật.
l Tính đơn giản: Dễ hiểu, dễ lập trình, dễ chỉnh lý.
l Phân tích thời gian: Thời gian thực hiện giải
thuật là tiêu chuẩn đánh giá hiệu lực của giải thuật. Ngô Công Thắng
Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 01 1.18
3.2.2. Phân tích thời gian thực hiện giải thuật
l Với một bài toán có nhiều giải thuật, ta cần chọn
giải thuật dẫn đến kết quả nhanh nhất.
l Thời gian thực hiện phụ thuộc vào nhiều yếu tố như:
l Kích thước của dữ liệu vào. Nếu gọi n là kích thước của
dữ liệu vào thì thời gian thực hiện T của một giải thuật
phải được biểu diễn như một hàm của n: T(n)
l Các kiểu lệnh, tốc độ xử lý của máy tính, ngôn ngữ viết
chương trình, chương trình dịch cũng ảnh hưởng đến tốc
độ thực hiện. Nhưng những yếu tố này không đồng đều
với mỗi loại máy tính, vì vậy không thể đưa chúng vào
xác lập T(n). Điều đó cũng có nghĩa là T(n) không thể
tính theo đơn vị giây, phút… Ngô Công Thắng
Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 01 1.19
3.2.3. Độ phức tạp tính toán của giải thuật l
Cách đánh giá thời gian thực hiện giải thuật không phụ
thuộc vào máy tính và các yếu tố liên quan mà chỉ phụ thuộc
vào kích thước dữ liệu đầu vào được gọi là đánh giá theo
“Độ phức tạp tính toán của giải thuật”. l
Nếu thời gian thực hiện một giải thuật là T(n) = Cn2, trong đó
C là hằng số, thì ta nói độ phức tạp tính toán của giải thuật
này có cấp n2, và được kí hiệu là: T(n)= O(n2) l
Tổng quát: Hàm f(n) được gọi là có độ phức tạp tính toán
cấp g(n), kí hiệu là f(n) = O(g(n)), nếu tồn tại các hằng số C và n0 sao cho: f(n) ≤ Cg(n) với n  n0
nghĩa là hàm f(n) bị chặn trên bởi Cg(n), với C là hằng số và
với mọi n từ một điểm nào đó. l
Ví dụ 1: f(n) = O(n3) có nghĩa độ phức tạp tính toán cấp n3 l
Ví dụ 2: f(n) = O(2n) có nghĩa độ phức tạp tính toán cấp 2n Ngô Công Thắng
Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 01 1.20
3.2.3. Độ phức tạp tính toán của
giải thuật (tiếp)
l Các hàm thể hiện độ phức tập tính toán của giải thuật
có các dạng sau: nn, n!, 2n, n3, n2, nlog n, n, log n. Các 2 2
hàm này đã được sắp theo giá trị giảm dần, có nghĩa là
với cùng một giá trị của n, hàm nn là lớn nhất, log2n là
nhỏ nhất. Các hàm này có dạng đồ thị như sau: Ngô Công Thắng
Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 01 1.21
3.2.3. Độ phức tạp tính toán của
giải thuật (tiếp)
l Các hàm nn , n! , 2n gọi là các hàm mũ.
Một gíải thuật có độ phức tạp tính toán
cấp hàm mũ thì rất chậm, do đó khó được chấp nhận.
l Các hàm n3, n2, nlog n, n, log n là các 2 2
hàm loại đa thức. Độ phức tạp tính toán
của giải thuật có cấp đa thức thì chấp nhận được. Ngô Công Thắng
Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 01 1.22
3.2.4. Xác định độ phức tạp tính toán l Quy tắc cộng:
l Giả sử T1(n) và T2(n) là thời gian thực hiện 2
đoạn chương trình P1 và P2 mà T1(n)=
O(f(n)), T2(n)=O(g(n)), thì thời gian thực hiện
P1 rồi đến P2 tiếp theo sẽ là: T1(n) + T2(n) = O(max(f(n),g(n)))
l Ví dụ: Chương trình có 3 bước, mỗi bước có
độ phức tạp tính toán lần lượt là O(n3), O(n),
O(nlog2n). Vậy thời gian thực hiện 3 bước là:
T1(n) + T2(n) + T3(n) = O(max(n3, n, nlog2n) = O(n3) Ngô Công Thắng
Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 01 1.23
3.2.4. Xác định độ phức tạp tính toán (tiếp) l Quy tắc nhân:
l Nếu tương ứng với 2 bước P1 và P2 là T1(n) =
O(f(n)),T2(n) = O(g(n)) thì thời gian thực hiện P1 và
P2 lồng nhau là : T1(n).T2(n) = O(f(n).g(n))
l Ví dụ: Câu lệnh x:=x+1 có thời gian thực hiện bằng
hằng số C => T(n) =O(1)
Câu lệnh: For i :=1 To n Do x :=x+1;
có thời gian thực hiện là: T(n)=O(n.1)=O(n) Câu lệnh For i :=1 To n Do For j :=1 To n Do x:=x+1;
có thời gian thực hiện được đánh giá là: T(n)= O(n.n) = O(n2) Ngô Công Thắng
Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 01 1.24
3.2.4. Xác định độ phức tạp tính toán (tiếp) l Quy tắc bỏ hằng số l
O(c.f(n)) = O(f(n), trong đó c là một hằng số. l Ví dụ: O(n2/3) = O(n2)
l Chú ý 1: Khi đánh giá thời gian thực hiện
giải thuật ta chỉ cần chú ý tới các bước
tương ứng với một phép toán được gọi là
phép toán tích cực. Đó là phép toán mà
thời gian thực hiện nó không ít hơn thời
gian thực hiện các phép toán khác. Ngô Công Thắng
Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 01 1.25
3.2.4. Xác định độ phức tạp tính toán (tiếp)
l Các bước xác định O của một giải thuật:
B1: Xác định phép toán tích cực trong giải thuật.
B2: Đếm số lần thực hiện phép toán tích cực, biểu
diễn số đếm này thành một hàm phụ thuộc vào
kích thước dữ liệu đầu vào n, f(n)
B3: Coi O(f(n)), sử dụng định nghĩa O và các quy
tắc xác định O để tìm ra O cuối cùng. Ngô Công Thắng
Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 01 1.26
3.2.4. Xác định độ phức tạp tính toán (tiếp)
l Ví dụ: ex = 1+ x/1! + x2/2! + . . .+ xn/n! với x và n cho trước. l Giải thuật 1: 1) Read(x,n); s:=1; 2) For i :=1 To n Do begin p:=1; For j :=1 To i Do p:=p*x/j ; s:=s+p; end; Ngô Công Thắng
Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 01 1.27
3.2.4. Xác định độ phức tạp tính toán (tiếp)
l Trong giải thuật 1 phép toán tích cực ở
đây là p:=p*x/j. Ta thấy nó được thực hiện
với số lần là: 1+2+3+ . . . + n = n(n+1)/2
Vậy thời gian thực hiện giải thuật là: T(n) = O(n2) Ngô Công Thắng
Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 01 1.28
3.2.4. Xác định độ phức tạp tính toán (tiếp) l Giải thuật 2: 1) Read(x,n); s:=1; p:=1; 2) For i :=1 To n Do begin p:=p*x/i; s:=s+p; end;
Thời gian thực hiện giải thuật 2 là: T(n) = O(n) Ngô Công Thắng
Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 01 1.29
3.2.4. Xác định độ phức tạp tính toán (tiếp) l Giải thuật 3: 1) Read(x); s:=1; p:=1; i:=0; 2) Repeat i:=i+1; p:=p*x/i; s:=s+p; Until | p | < Epsilon; end. 3) Write(s); Ngô Công Thắng
Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 01 1.30
3.2.4. Xác định độ phức tạp tính toán (tiếp) l
Chú ý 2: Có những trường hợp thời gian thực hiện giải
thuật không chỉ phụ thuộc vào kích thước của dữ liệu
vào mà còn phụ thuộc vào chính tình trạng của dữ liệu đó nữa. l
Khi phân tích thời gian thực hiện giải thuật ta phải xét
xem với mọi dữ liệu vào có kích thước n thì T(n) trong
trường hợp thuận lợi nhất, trường hợp trung bình và
trường hợp xấu nhất như thế nào? l
Việc xác định T(n) trong trường hợp trung bình thường
khó vì phải dùng tới những công cụ toán đặc biệt. Bởi
vậy người ta thường đánh giá giải thuật bằng T(n) trong trường hợp xấu nhất. Ngô Công Thắng
Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 01 1.31
3.2.4. Xác định độ phức tạp tính toán (tiếp) l
Ví dụ: Cho véc tơ a có n phần tử a1, a2,..., an. Tìm trong a phần tử
đầu tiên có giá trị = x cho trước. l Giải thuật như sau: Found := False; i:=1;
While (i<=n) and Not Found Do If a[i] =x then begin Found:=True; k:=i; Write(k); end else i:=i+1; End.
T(n) trong trường hợp tốt T(n)=O(1)
T(n) trong trường hợp xấu T(n)=O(n) . Vây suy ra T(n)=O(n) Ngô Công Thắng
Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 01 1.32 4. Giải thuật đệ quy 4.1. Khái niệm đệ quy l
Ta nói một đối tượng là đệ quy nếu nó được định nghĩa dưới dạng chính nó. l
Ví dụ 1: Trên màn hình của vô tuyến truyền hình lại xuất
hiện hình ảnh của chính cái màn hình vô tuyến đó. l
Ví dụ 2: Trong toán học hay gặp định nghĩa đệ quy:
1. Định nghĩa số tự nhiên
a) x là số tự nhiên nếu x-1 là số tự nhiên b) 1 là số tự nhiên 2. Hàm n! a) n! = n*(n-1)! nếu n>0 b) n!=1 nếu n=0 Ngô Công Thắng
Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 02 2.33
4.2. Giải thuật đệ quy và thủ tục đệ quy
l Nếu lời giải của một bài toán T được thực hiện
bằng lời giải của bài toán T’ có dạng giống như
T thì đó là một lời giải đệ quy. Trong đó T’ tuy
giống T nhưng nó phải nhỏ hơn T.
l Giải thuật tương ứng với lời giải đệ quy gọi là giải thuật đệ quy.
l Thủ tục viết cho bài toán có lời giải đệ quy gọi là thủ tục đệ quy.
Trong thủ tục đệ quy có lời gọi tới chính nó, mỗi
lần gọi thì kích thước bài toán thu nhỏ hơn và
dần dần tiến tới trường hợp đặc biệt là trường hợp suy biến. Ngô Công Thắng
Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 02 2.34
Ví dụ: Bài toán tìm 1 từ trong cuốn từ điển
l Giải thuật đệ quy của bài toán này như sau:
IF từ điển là một trang THEN tìm từ trong trang ấy ELSE BEGIN
Mở từ điển vào trang giữa; Xác định xem nửa nào chứa từ
IF từ nằm trong nửa trước THEN tìm trong nửa trước ELSE tìm trong nửa sau END Ngô Công Thắng
Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 02 2.35
Ví dụ: Bài toán tìm 1 từ trong cuốn từ điển
l Trong giải thuật này có 2 điểm cần chú ý:
l Điểm 1: Sau mỗi lần từ điển được tách đôi, một nửa
thích hợp sẽ được tìm kiếm theo chiến thuật đã dùng.
l Điểm 2: Có trường hợp đặc biệt là sau khi tách đôi từ
điển chỉ còn 1 trang, giải quyết trực tiếp bằng cách
tìm từ trong trang đó. Trường hợp đặc biệt này gọi là trường hợp suy biến.
l Giải thuật này gọi là giải thuật chia đôi: Bài toán
được tách đôi ra bài toán nhỏ hơn, bài toán nhỏ
hơn lại dùng chiến thuật chia đôi, cho tới khi gặp trường hợp suy biến. Ngô Công Thắng
Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 02 2.36
Ví dụ: Bài toán tìm 1 từ trong cuốn từ điển
l Thủ tục đệ quy của bài toán được viết như sau: Procedure timkiem(Tudien, tu)
IF Tudien chỉ còn một trang THEN tìm từ trong trang ấy ELSE BEGIN
Mở từ điểm vào trang giữa
Xác định xem nửa nào chứa từ
IF Từ nằm ở nửa trước
THEN CALL timkiem(Tudien1, tu)
ELSE CALL timkiem(Tudien2, tu) END RETURN Ngô Công Thắng
Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 02 2.37
4.3. Thiết kế giải thuật đệ quy
l Khi bài toán đang xét hoặc dữ liệu đang xử lý
được định nghĩa dưới dạng đệ quy thì việc thiết
kế các giải thuật đệ quy tỏ ra rất thuận lợi.
l Khi thiết kế giải thuật đệ quy cần trả lời các câu hỏi sau:
1. Có thể định nghĩa bài toán dưới dạng một bài toán
cùng loại nhưng có quy mô nhỏ hơn. Đây được gọi là đệ quy.
2. Có trường hợp đặc biệt (trường hợp suy biến) mà ở đó kết thúc đệ quy. Ngô Công Thắng
Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 02 2.38 Bài toán 1: Tính n!
l Định nghĩ đệ quy của hàm n! như sau: GiaiThua(n) = 1 nếu n=0
GiaiThua(n)=nGiaiThua(n-1) nếu n>0
Thuật giải đệ quy được viết dưới dạng hàm: Function GiaiThua(n)
If n=0 then begin GiaiThua :=1; return;end
Else GiaiThua := n * GiaiThua(n-1); Return Ngô Công Thắng
Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 02 2.39 Bài toán 1: Tính n!
l Khử đệ quy của hàm tính giai thừa: Function FAC(n) If n=0 then gt:=1; Else begin gt:=1; For i:=1 to n do gt:=gt*i; end; FAC:=gt; Return Ngô Công Thắng
Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 02 2.40 Bài toán 1: Tính n!
l Đối chiếu với 3 đặc điểm của thủ tục đệ quy ta thấy:
l Lời gọi tới chính nó đứng sau Else
l Mỗi lần gọi đệ quy giá trị giảm đi:
FAC(4)FAC(3)FAC(2) FAC(1)
l Trường hợp suy biến là FAC(0): FAC(0) = 1 Ngô Công Thắng
Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 02 2.41
Bài toán 2: Lập dãy số FIBONACCI 1 1 2 3 5 8 13...
l Định nghĩa F(n) như sau: F(n) = 1 nếu n  2
F(n)=F(n-2)+F(n-1) nếu n>2
l Thủ tục đệ quy thể hiện giải thuật tính F(n) như sau: Function F(n:integer) If n<=2 then F:=1 Else F:=F(n-2)+F(n-1) Return Ngô Công Thắng
Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 02 2.42
Bài toán 3: Bài toán “Tháp Hà nội”
l Nội dung: Có n đĩa kích thước nhỏ dần, đĩa có lỗ
ở giữa. Có thể xếp chồng chúng lên nhau xuyên
qua một cái cọc, to dưới nhỏ trên để cuối cùng
có một chồng đĩa dạng như hình tháp. Ngô Công Thắng
Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 02 2.43
Bài toán 3: Bài toán “Tháp Hà nội”
l Yêu cầu đặt ra: Chuyển chồng đĩa từ cọc
A sang cọc C theo những điều kiện sau:
l Mỗi lần chỉ được chuyển một đĩa
l Không khi nào có tình huống đĩa to ở trên đĩa nhỏ ở dưới
l Được phép sử dụng 1 cọc trung gian (cọc B) để đặt tạm thời. Ngô Công Thắng
Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 02 2.44
Bài toán 3: Bài toán “Tháp Hà nội”
l Ta xét một vài trường hợp đơn giản: l Trường hợp 1 đĩa:
l Chuyển từ cọc A sang cọc C l Trường hợp 2 đĩa:
l Chuyển đĩa thứ nhất từ cọc A sang cọc B
l Chuyển đĩa thứ hai từ cọc A sang cọc C
l Chuyển đĩa thứ nhất từ cọc B sang cọc C Ngô Công Thắng
Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 02 2.45
Bài toán 3: Bài toán “Tháp Hà nội”
l Trường hợp n đĩa (n>2): Ta coi n-1 đĩa ở trên như
đĩa thứ nhất và xử lý giống như trường hợp 2 đĩa:
l Chuyển n-1 đĩa từ cọc A sang cọc B
l Chuyển đĩa thứ n từ cọc A sang cọc C
l Chuyển n-1 đĩa từ cọc B sang cọc C
l Chuyển n-1 đĩa từ cọc B sang cọc C thuật giải sẽ là:
l Chuyển n-2 đĩa từ cọc B sang cọc A
l Chuyển 1 đĩa từ cọc B sang cọc C
l Chuyển n-2 đĩa từ cọc B sang cọc C
l Cứ làm như vậy cho đến khi trường hợp suy biến
xảy ra, đó là trường hợp ứng với bài toán chuyển 1 đĩa. Ngô Công Thắng
Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 02 2.46
Bài toán 3: Bài toán “Tháp Hà nội”
l Thủ tục của bài toán “Tháp Hà nội” như sau: Procedure Hanoi(n,A,B,C)
If n=1 then chuyển đĩa từ A sang C Else Begin Call Hanoi(n-1,A,C,B) Call Hanoi(1,A,B,C) Call Hanoi(n-1,B,A,C) End; Return Ngô Công Thắng
Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 02 2.47 Bài tập
1. Thế nào là giải thuật đệ quy?
2. Ưu nhược điểm của giải thuật đệ quy?
3. Trong bộ nhớ của máy tính dùng vùng nhớ nào để dùng cho giải thuật đệ quy.
4. Trường hợp suy biến là trường hợp như thế nào trong giải thuật đệ quy.
5. Thường hay dùng cấu trúc lập trình nào để thể hiện giải thuật đệ quy
6. Viết giải thuật đệ quy cho bài toán sau: Acker(m,n)= n+1 nếu m=0
Acker(m,n)= Acker(m-1,1) nếu n=0
Acker(m,n)= Acker(m-1,Acker(m,n-1)) với các trường hợp khác. Ngô Công Thắng
Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 02 2.48 Thủ tục đệ quy Bài 6 Function Acker(m,n:integer) If m=0 then Acker:=n+1
else if n=0 then Acker:=Acker(m-1,1)
else Acker:=Acker(m-1,Acker(m,n-1)) Return Ngô Công Thắng
Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 02 2.49 Bài tập (tiếp)
7.Giải thuật tính ước số chung lớn nhất của
hai số nguyên dương a và b (a>b) như
sau: Gọi r là số dư của phép chia a cho b.
- Nếu r=0 thì b là ước số chung lớn nhất
- r khác 0 thì gán a:=b; b:=r rồi lặp lại.
Hãy xây dựng giải thuật đệ quy tính ước
số chung lớn nhất USCLN(a,b) Ngô Công Thắng
Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 02 2.50 Thủ tục đệ quy bài 7
Bài toán: Tìm USCLN của 2 số nguyên dương a,b Cách 1: Dùng đệ quy Function USCLN(a,b)
If b=0 then begin USCLN := a; return; end;
If b # 0 then USCLN := USCLN(b,a mod b); Return Ngô Công Thắng
Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 02 2.51 Thủ tục đệ quy bài 7
Bài toán: Tìm USCLN của 2 số nguyên dương a,b Cách 2: Khử đệ quy Function USCLN(a,b) 1) r := a mod b; 2) while r # 0 do begin a:=b; b:=r; r:= a mod b end; 3) USCLN:=b; Return Ngô Công Thắng
Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 02 2.52 Bài tập (tiếp)
8. Hàm C(n,k) với n, k là các giá trị nguyên không
âm và k<=n, được định nghĩa như sau: C(n,n)=1 C(n,0)=1
C(n,k)=C(n-1,k-1)+C(n-1,k) nếu 0< kHãy xây dựng giải thuật đệ quy cho bài toán trên
9. Viết thủ tục đệ quy in ngược một dòng kí tự cho trước. Ngô Công Thắng
Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 02 2.53 Thủ tục đệ quy bài 8 Function C(n,k:integer) If k=0 then C:=1 else if k=n then C:=1 else C:=C(n-1,k-1)+C(n-1,k); Return Ngô Công Thắng
Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 02 2.54