http://ebook.here.vn Ti min phí ð thi, eBook, Tài liu hc tp
CHƯƠNG I:
THU(T TOÁN
1.1. KHÁI NI-M THU(T TOÁN.
1.1.1. M/ ñ1u:
Có nhiu lp bài toán tng quát xut hin trong toán hc ri rc. Chng hn, cho
m t dãy các s% nguyên, tìm s% ln nht; cho m t t)p h*p, lit kê các t)p con c,a nó; cho
t)p h*p các s% nguyên, x.p chúng theo th1 t2 tăng d4n; cho m t mng, tìm ñưng ñi
ng7n nht gi8a hai ñ9nh c,a nó. Khi ñư*c giao cho m t bài toán như v)y thì vic ñ4u
tiên ph<i làm là xây d2ng m t mô hình d?ch bài toán ñó thành ng8 c<nh toán hc. Các
cu trúc ri rc ñư*c dùng trong các mô hình này là t)p h*p, dãy, hàm, hoán v?, quan h,
cùng vi các cu trúc khác như ñA th?, cây, mng B nh8ng khái nim sC ñư*c nghiên c1u
D các chương sau.
L)p ñư*c m t mô hình toán hc thích h*p ch9 là m t ph4n c,a quá trình gi<i. ðI
hoàn tt quá trình gi<i, còn c4n ph<i có m t phương pháp dùng mô hình ñI gi<i bài toán
tng quát. Nói m t cách lý tưDng, cái ñư*c ñòi hMi là m t th, tNc, ñó là dãy các bưc
dOn ti ñáp s% mong mu%n. M t dãy các bưc như v)y, ñư*c gi là m t thu)t toán.
Khi thi.t k. và cài ñQt m t ph4n mm tin hc cho m t vn ñ nào ñó, ta c4n ph<i
ñưa ra phương pháp gi<i quy.t mà th2c cht ñó là thu)t toán gi<i quy.t vn ñ này. Rõ
ràng rTng, n.u không tìm ñư*c m t phương pháp gi<i quy.t thì không thI l)p trình
ñư*c. Chính vì th., thu)t toán là khái nim nn t<ng c,a h4u h.t các lĩnh v2c c,a tin
hc.
1.1.2. ð3nh nghĩa:
Thu)t toán là m t b<ng lit kê các ch9 dOn (hay quy t7c) c4n th2c
hin theo tYng bưc xác ñ?nh nhTm gi<i m t bài toán ñã cho.
Thu)t ng8 “Algorithm” (thu)t toán) là xut phát tY tên nhà toán hc ] R)p AlB
Khowarizmi. Ban ñ4u, tY algorism ñư*c dùng ñI ch9 các quy t7c th2c hin các phép tính
s% hc trên các s% th)p phân. Sau ñó, algorism chuyIn thành algorithm vào th. kc 19.
Vi s2 quan tâm ngày càng tăng ñ%i vi các máy tính, khái nim thu)t toán ñã ñư*c cho
m t ý nghĩa chung hơn, bao hàm c< các th, tNc xác ñ?nh ñI gi<i các bài toán, ch1 không
ph<i ch9 là th, tNc ñI th2c hin các phép tính s% hc.
Có nhiu cách trình bày thu)t toán: dùng ngôn ng8 t2 nhiên, ngôn ng8 lưu ñA (sơ
ñA kh%i), ngôn ng8 l)p trình. Tuy nhiên, m t khi dùng ngôn ng8 l)p trình thì ch9 nh8ng
lnh ñư*c phép trong ngôn ng8 ñó mi có thI dùng ñư*c và ñiu này thưng làm cho s2
mô t< các thu)t toán trD nên r%i r7m và khó hiIu. Hơn n8a, vì nhiu ngôn ng8 l)p trình
ñu ñư*c dùng r ng rãi, nên chn m t ngôn ng8 ñQc bit nào ñó là ñiu ngưi ta không
mu%n. Vì v)y D ñây các thu)t toán ngoài vic ñư*c trình bày bTng ngôn ng8 t2 nhiên
cùng vi nh8ng ký hiu toán hc quen thu c còn dùng m t dng gi< mã ñI mô t< thu)t
http://ebook.here.vn Ti min phí ð thi, eBook, Tài liu hc tp
toán. Gi< mã to ra bưc trung gian gi8a s2 mô t< m t thu)t toán bTng ngôn ng8 thông
thưng và s2 th2c hin thu)t toán ñó trong ngôn ng8 l)p trình. Các bưc c,a thu)t toán
ñư*c ch9 rõ bTng cách dùng các lnh gi%ng như trong các ngôn ng8 l)p trình.
Thí d8 1: Mô t< thu)t toán tìm ph4n tj ln nht trong m t dãy h8u hn các s% nguyên.
a) Dùng ngôn ng t nhiên ñ mô t các bưc cn phi thc hin:
1. ðQt giá tr? c2c ñi tm thi bTng s% nguyên ñ4u tiên trong dãy. (C2c ñi tm
thi sC là s% nguyên ln nht ñã ñư*c kiIm tra D m t giai ñon nào ñó c,a th, tNc.)
2. So sánh s% nguyên ti.p sau vi giá tr? c2c ñi tm thi, n.u nó ln hơn giá tr?
c2c ñi tm thi thì ñQt c2c ñi tm thi bTng s% nguyên ñó.
3. LQp li bưc trưc n.u còn các s% nguyên trong dãy.
4. DYng khi không còn s% nguyên nào n8a trong dãy. C2c ñi tm thi D ñiIm
này chính là s% nguyên ln nht c,a dãy.
b) Dùng ñon gi mã:
procedure max (a
1
, a
2
, ..., a
n
: integers)
max:= a
1
for i:= 2 to n
if max <a
i
then max:= a
i
{max là ph4n tj ln nht}
Thu)t toán này trưc h.t gán s% hng ñ4u tiên a
1
c,a dãy cho bi.n max. Vòng lQp
“for” ñư*c dùng ñI kiIm tra l4n lư*t các s% hng c,a dãy. N.u m t s% hng ln hơn giá
tr? hin thi c,a max thì nó ñư*c gán làm giá tr? mi c,a max.
1.1.3. Các ñ<c trưng c>a thut toán:
BB ð1u vào (Input): M t thu)t toán có các giá tr? ñ4u vào tY m t t)p ñã ñư*c ch9 rõ.
?? ð1u ra (Output): TY mvi t)p các giá tr? ñ4u vào, thu)t toán sC to ra các giá tr? ñ4u ra.
Các giá tr? ñ4u ra chính là nghim c,a bài toán.
BB Tính d@ng: Sau m t s% h8u hn bưc thu)t toán ph<i dYng.
BB Tính xác ñ3nh: w mvi bưc, các bưc thao tác ph<i h.t s1c rõ ràng, không gây nên s2
nh)p nhTng. Nói rõ hơn, trong cùng m t ñiu kin hai b xj lý cùng th2c hin m t bưc
c,a thu)t toán ph<i cho nh8ng k.t qu< như nhau.
BB Tính hiu qu: Trưc h.t thu)t toán c4n ñúng ñ7n, nghĩa là sau khi ñưa d8 liu vào
thu)t toán hot ñ ng và ñưa ra k.t qu< như ý mu%n.
BB Tính phC d8ng: Thu)t toán có thI gi<i bt kỳ m t bài toán nào trong lp các bài toán.
CN thI là thu)t toán có thI có các ñ4u vào là các b d8 liu khác nhau trong m t min
xác ñ?nh.
1.2. THU(T TOÁN TÌM KIEM.
1.2.1. Bài toán tìm kiGm:
Bài toán xác ñ?nh v? trí c,a m t ph4n tj trong m t b<ng lit
kê s7p th1 t2 thưng gQp trong nhiu trưng h*p khác nhau. Chng hn chương trình
http://ebook.here.vn Ti min phí ð thi, eBook, Tài liu hc tp
kiIm tra chính t< c,a các tY, tìm ki.m các tY này trong m t cu%n tY ñiIn, mà tY ñiIn
chng qua cũng là m t b<ng lit kê s7p th1 t2 c,a các tY. Các bài toán thu c loi này
ñư*c gi là các bài toán tìm ki.m.
Bài toán tìm ki.m tng quát ñư*c mô t< như sau: xác ñ?nh v? trí c,a ph4n tj x
trong m t b<ng lit kê các ph4n tj phân bit a
1,
a
2
, ..., a
n
hoQc xác ñ?nh rTng nó không có
mQt trong b<ng lit kê ñó. Li gi<i c,a bài toán trên là v? trí c,a s% hng c,a b<ng lit kê
có giá tr? bTng x (t1c là i sC là nghim n.u x=a
i
và là 0 n.u x không có mQt trong b<ng
lit kê).
1.2.2. Thut toán tìm kiGm tuyGn tính:
Tìm ki.m tuy.n tính hay tìm ki.m tu4n t2 là
b7t ñ4u bTng vic so sánh x vi a
1
; khi x=a
1
, nghim là v? trí a
1
, t1c là 1; khi x≠a
1
, so
sánh x vi a
2
. N.u x=a
2
, nghim là v? trí c,a a
2
, t1c là 2. Khi x≠a
2
, so sánh x vi a
3
. Ti.p
tNc quá trình này bTng cách tu4n t2 so sánh x vi mvi s% hng c,a b<ng lit kê cho ti
khi tìm ñư*c s% hng bTng x, khi ñó nghim là v? trí c,a s% hng ñó. N.u toàn b<ng lit
kê ñã ñư*c kiIm tra mà không xác ñ?nh ñư*c v? trí c,a x, thì nghim là 0. Gi< mã ñ%i
vi thu)t toán tìm ki.m tuy.n tính ñư*c cho dưi ñây:
procedure tìm ki.m tuy.n tính (x: integer, a
1
,a
2
,...,an: integers phân bit)
i := 1
while (i ≤ n and x ≠ a
i
)
i := i + 1
if i ≤ n then location := i
else location := 0
{location là ch9 s% dưi c,a s% hng bTng x hoQc là 0 n.u không tìm ñư*c x}
1.2.3. Thut toán tìm kiGm nh3 phân:
Thu)t toán này có thI ñư*c dùng khi b<ng
lit kê có các s% hng ñư*c s7p theo th1 t2 tăng d4n. Chng hn, n.u các s% hng là các
s% thì chúng ñư*c s7p tY s% nhM nht ñ.n s% ln nht hoQc n.u chúng là các tY hay xâu
ký t2 thì chúng ñư*c s7p theo th1 t2 tY ñiIn. Thu)t toán th1 hai này gi là thu)t toán tìm
ki.m nh? phân. Nó ñư*c ti.n hành bTng cách so sánh ph4n tj c4n xác ñ?nh v? trí vi s%
hng D gi8a b<ng lit kê. Sau ñó b<ng này ñư*c tách làm hai b<ng kê con nhM hơn có
kích thưc như nhau, hoQc m t trong hai b<ng con ít hơn b<ng con kia m t s% hng. S2
tìm ki.m ti.p tNc bTng cách hn ch. tìm ki.m D m t b<ng kê con thích h*p d2a trên vic
so sánh ph4n tj c4n xác ñ?nh v? trí vi s% hng gi8a b<ng kê. Ta sC thy rTng thu)t toán
tìm ki.m nh? phân hiu qu< hơn nhiu so vi thu)t toán tìm ki.m tuy.n tính.
Thí d8 2. ðI tìm s% 19 trong b<ng lit kê 1,2,3,5,6,7,8,10,12,13,15,16,18,19,20,22 ta
tách b<ng lit kê gAm 16 s% hng này thành hai b<ng lit kê nhM hơn, mvi b<ng có 8 s%
hng, cN thI là: 1,2,3,5,6,7,8,10 và 12,13,15,16,18,19,20,22. Sau ñó ta so sánh 19 vi s%
hng cu%i cùng c,a b<ng con th1 nht. Vì 10<19, vic tìm ki.m 19 ch9 gii hn trong
b<ng lit kê con th1 2 tY s% hng th1 9 ñ.n 16 trong b<ng lit kê ban ñ4u. Ti.p theo, ta
http://ebook.here.vn Ti min phí ð thi, eBook, Tài liu hc tp
li tách b<ng lit kê con gAm 8 s% hng này làm hai b<ng con, mvi b<ng có 4 s% hng, cN
thI là 12,13,15,16 và 18,19,20,22. Vì 16<19, vic tìm ki.m li ñư*c gii hn ch9 trong
b<ng con th1 2, tY s% hng th1 13 ñ.n 16 c,a b<ng lit kê ban ñ4u. B<ng lit kê th1 2
này li ñư*c tách làm hai, cN thI là: 18,19 và 20,22. Vì 19 không ln hơn s% hng ln
nht c,a b<ng con th1 nht nên vic tìm ki.m gii hn ch9 D b<ng con th1 nht gAm các
s% 18,19, là s% hng th1 13 và 14 c,a b<ng ban ñ4u. Ti.p theo b<ng con ch1a hai s%
hng này li ñư*c tách làm hai, mvi b<ng có m t s% hng 18 và 19. Vì 18<19, s2 tìm
ki.m gii hn ch9 trong b<ng con th1 2, b<ng lit kê ch9 ch1a s% hng th1 14 c,a b<ng
lit kê ban ñ4u, s% hng ñó là s% 19. Bây gi s2 tìm ki.m ñã thu h€p v ch9 còn m t s%
hng, so sánh ti.p cho thy19 là s% hng th1 14 c,a b<ng lit kê ban ñ4u.
Bây gi ta có thI ch9 rõ các bưc trong thu)t toán tìm ki.m nh? phân.
ðI tìm s% nguyên x trong b<ng lit kê a
1
,a
2
,...,a
n
vi a
1
< a
2
< ... < a
n
, ta b7t ñ4u
bTng vic so sánh x vi s% hng a
m
D gi8a c,a dãy, vi m=[(n+1)/2]. N.u x > a
m
, vic
tìm ki.m x gii hn D nja th1 hai c,a dãy, gAm a
m+1
,a
m+2
,...,a
n
. N.u x không ln hơn a
m
,
thì s2 tìm ki.m gii hn trong nja ñ4u c,a dãy gAm a
1
,a
2
,...,a
m
.
Bây gi s2 tìm ki.m ch9 gii hn trong b<ng lit kê có không hơn [n/2] ph4n tj.
Dùng chính th, tNc này, so sánh x vi s% hng D gi8a c,a b<ng lit kê ñư*c hn ch.. Sau
ñó li hn ch. vic tìm ki.m D nja th1 nht hoQc nja th1 hai c,a b<ng lit kê. LQp li
quá trình này cho ti khi nh)n ñư*c m t b<ng lit kê ch9 có m t s% hng. Sau ñó, ch9 còn
xác ñ?nh s% hng này có ph<i là x hay không. Gi< mã cho thu)t toán tìm ki.m nh? phân
ñư*c cho dưi ñây:
procedure tìm ki.m nh? phân (x: integer, a
1
,a
2
,...,an: integers tăng d4n)
i := 1 {i là ñiIm mút trái c,a kho<ng tìm ki.m}
j := n {j là ñiIm mút ph<i c,a kho<ng tìm ki.m}
while i < j
begin
m:= [(i+j)/2]
if x>a
m
then i:=m+1
else j := m
end
if x = ai then location := i
else location := 0
{location là ch9 s% dưi c,a s% hng bTng x hoQc 0 n.u không tìm thy x}
1.3. ðL PHNC TOP CPA THU(T TOÁN.
Khái nim v ñR phSc tTp c>a mRt thut toán
Thưc ño hiu qu< c,a m t thu)t toán là thi gian mà máy tính sj dNng ñI gi<i
bài toán theo thu)t toán ñang xét, khi các giá tr? ñ4u vào có m t kích thưc xác ñ?nh.
http://ebook.here.vn Ti min phí ð thi, eBook, Tài liu hc tp
M t thưc ño th1 hai là dung lư*ng b nh ñòi hMi ñI th2c hin thu)t toán khi các giá
tr? ñ4u vào có kích thưc xác ñ?nh. Các vn ñ như th. liên quan ñ.n ñ ph1c tp tính
toán c,a m t thu)t toán. S2 phân tích thi gian c4n thi.t ñI gi<i m t bài toán có kích
thưc ñQc bit nào ñó liên quan ñ.n ñ ph1c tp thi gian c,a thu)t toán. S2 phân tích
b nh c4n thi.t c,a máy tính liên quan ñ.n ñ ph1c tp không gian c,a thu)t toán. Vc
xem xét ñ ph1c tp thi gian và không gian c,a m t thu)t toán là m t vn ñ rt thi.t
y.u khi các thu)t toán ñư*c th2c hin. Bi.t m t thu)t toán sC ñưa ra ñáp s% trong m t
micro giây, trong m t phút hoQc trong m t t9 năm, hiIn nhiên là h.t s1c quan trng.
Tương t2 như v)y, dung lư*ng b nh ñòi hMi ph<i là kh< dNng ñI gi<i m t bài toán,vì
v)y ñ ph1c tp không gian cũng c4n ph<i tính ñ.n.Vì vic xem xét ñ ph1c tp không
gian g7n lin vi các cu trúc d8 liu ñQc bit ñư*c dùng ñI th2c hin thu)t toán nên D
ñây ta sC t)p trung xem xét ñ ph1c tp thi gian.
ð ph1c tp thi gian c,a m t thu)t toán có thI ñư*c biIu di†n qua s% các phép
toán ñư*c dùng bDi thu)t toán ñó khi các giá tr? ñ4u vào có m t kích thưc xác ñ?nh. SD
dĩ ñ ph1c tp thi gian ñư*c mô t< thông qua s% các phép toán ñòi hMi thay vì thi gian
th2c c,a máy tính là bDi vì các máy tính khác nhau th2c hin các phép tính sơ cp trong
nh8ng kho<ng thi gian khác nhau. Hơn n8a, phân tích tt c< các phép toán thành các
phép tính bit sơ cp mà máy tính sj dNng là ñiu rt ph1c tp.
Thí d8 3: Xét thu)t toán tìm s% ln nht trong dãy n s% a
1
, a
2
, ..., a
n
. Có thI coi kích
thưc c,a d8 liu nh)p là s% lư*ng ph4n tj c,a dãy s%, t1c là n. N.u coi mvi l4n so sánh
hai s% c,a thu)t toán ñòi hMi m t ñơn v? thi gian (giây chng hn) thì thi gian th2c
hin thu)t toán trong trưng h*p xu nht là nB1 giây. Vi dãy 64 s%, thi gian th2c hin
thu)t toán nhiu l7m là 63 giây.
Thí d8 4:Thu)t toán v trò chơi “Tháp Hà N i”
Trò chơi “Tháp Hà N i” như sau: Có ba cc A, B, C và 64 cái ñĩa (có lv ñI ñQt
vào cc), các ñĩa có ñưng kính ñôi m t khác nhau. Nguyên t7c ñQt ñĩa vào cc là: mvi
ñĩa ch9 ñư*c chAng lên ñĩa ln hơn nó. Ban ñ4u, c< 64 ñĩa ñư*c ñQt chAng lên nhau D c t
A; hai c t B, C tr%ng. Vn ñ là ph<i chuyIn c< 64 ñĩa ñó sang c t B hay C, mvi l4n ch9
ñư*c di chuyIn m t ñĩa.
Xét trò chơi vi n ñĩa ban ñ4u D cc A (cc B và C tr%ng). Gi S
n
là s% l4n
chuyIn ñĩa ñI chơi xong trò chơi vi n ñĩa.
N.u n=1 thì rõ ràng là S
1
=1.
N.u n>1 thì trưc h.t ta chuyIn nB1 ñĩa bên trên sang cc B (gi8 yên ñĩa th1 n D
dưi cùng c,a cc A). S% l4n chuyIn nB1 ñĩa là S
nB1
. Sau ñó ta chuyIn ñĩa th1 n tY cc A
sang cc C. Cu%i cùng, ta chuyIn nB1 ñĩa tY cc B sang cc C (s% l4n chuyIn là S
nB1
).
Như v)y, s% l4n chuyIn n ñĩa tY A sang C là:
S
n
=S
nB1
+1+S
n
=2S
nB1
+1=2(2S
nB2
+1)+1=2
2
S
nB2
+2+1=.....=2
nB1
S
1
+2
nB2
+...+2+1=2
n
−1.
![Giáo trình Toán rời rạc Phần 2 Nguyễn Gia Định [PDF]](https://cdn.tailieu.vn/images/document/thumbnail/2023/20230706/chankora07/135x160/1808415098.jpg)
![Giáo trình Toán rời rạc Trường CĐ Cơ điện Hà Nội [Tải Miễn Phí]](https://cdn.tailieu.vn/images/document/thumbnail/2022/20221229/phuongthao0020/135x160/869229917.jpg)
![Bài tập Đại số tuyến tính [chuẩn nhất]](https://cdn.tailieu.vn/images/document/thumbnail/2025/20250930/dkieu2177@gmail.com/135x160/79831759288818.jpg)
