ạ ươ
ọ
IT1110 Tin h c đ i c
ng
ầ
ả
ế
Ph n II Gi
i quy t bài toán
ễ
ọ
Nguy n Bá Ng c
1
ậ
ầ
ộ
Ôn t p n i dung ph n I
Ọ
Ả
ầ
Ph n I: TIN H C CĂN B N
ệ ề
ứ
ụ
Thông tin ữ ệ ễ ể Bi u di n d li u trong máy tính ạ Máy tính và m ng máy tính ệ ố H đi u hành và các h th ng ng d ng
ầ
ộ
N i dung ph n II
ằ
ươ
i quy t bài toán b ng máy tính
Ch
ằ
ả ng 1: Gi ề ệ ả
ế
i quy t bài toán b ng máy tính ế
ả
ằ
i quy t bài toán b ng máy tính
ng pháp gi
ế Khái ni m v bài toán Quá trình gi ươ Các ph ạ Phân lo i bài toán
Ch
ậ ậ
ễ
ụ
ậ
ươ ị ể ộ ố ậ ậ
ng 2: Thu t toán Đ nh nghĩa thu t toán ậ Bi u di n thu t toán M t s thu t toán thông d ng ệ Thu t toán đ quy ả i heuristic Thu t gi
3
ầ
ộ
N i dung ph n II
ằ
ươ
i quy t bài toán b ng máy tính
Ch
ằ
ả ng 1: Gi ề ệ ả
ế
i quy t bài toán b ng máy tính ế
ả
ằ
i quy t bài toán b ng máy tính
ng pháp gi
ế Khái ni m v bài toán Quá trình gi ươ Các ph ạ Phân lo i bài toán
Ch
ậ ậ
ễ
ụ
ậ
ươ ị ể ộ ố ậ ậ
ng 2: Thu t toán Đ nh nghĩa thu t toán ậ Bi u di n thu t toán M t s thu t toán thông d ng ệ Thu t toán đ quy ả i heuristic Thu t gi
4
ệ
ề
ề ấ 1.1. Khái ni m v v n đ và bài toán
ơ
ấ
ề ộ
ề
ẳ
ộ
c m t
ấ ượ ấ Theorema là v n đ c n đ ấ Problema là v n đ c n tìm gi ị
ụ
ữ
ệ
ị c kh ng đ nh đúngsai ể ạ ượ ả i pháp đ đ t đ ầ ề nh ng đi u ki n ban đ u.
ầ
m c tiêu xác đ nh t ạ ằ ễ Di n đ t b ng s đ : A B ế ả ầ thi A là gi ậ ạ ế B là k t lu n, m c tiêu c n đ t (cid:0) ậ
ầ
ị
V n đ r ng h n bài toán? Pitago chia v n đ ra: ề ầ ề ầ ừ ơ ồ ệ ề t, đi u ki n ban đ u ụ ả là suy lu n, gi
i pháp c n xác đ nh
5
(cid:0)
ướ ả ế ằ c gi i quy t bài toán b ng
1.2. Các b máy tính
ị ấ
ả i
B c 1: Xác đ nh v n đ bài toán ọ ự B c 2: L a ch n ph ng pháp gi ặ B c 3: Xây d ng thu t toán ho c thu t
ề ươ ậ ự ậ
gi
ặ ươ
B c 4: Cài đ t ch ệ B c 5: Hi u ch nh ch ự B c 6: Th c hi n ch
6
ỉ ệ ng trình ươ ươ ướ ướ ướ iả ướ ướ ướ ng trình ng trình
ả ng pháp gi ề ế ấ i quy t v n đ
ằ ươ 1.3. Các ph b ng máy tính
ế ấ
ề
ướ
ự
ế
ị
i quy t v n đ theo h
ng xác đ nh tr c ti p
ả i gi
ả i
ị
ủ ụ
Gi ờ l xác đ nh tr c ti p l
ủ i qua th t c tính toán ho c th
ạ ướ
ả ế ờ i gi ộ ố ữ ề
ơ ấ ờ
ế
Gi
ng tìm ki m l
i
ươ
ặ ự ụ ồ t c bao g m m t s h u h n các thao tác s c p. ả ả ế ấ i quy t v n đ theo h i gi ử nguyên lý "th và sai" ng pháp các ph ạ ệ t kê hay vét c n li ẫ ử th ng u nhiên quay lui chia đ trể ị
7
ạ
1.4. Phân lo i bài toán
Bài toán đa th cứ Bài toán không đa th cứ NP Problems
8
ầ
ộ
N i dung ph n II
ằ
ươ
i quy t bài toán b ng máy tính
Ch
ằ
ả ng 1: Gi ề ệ ả
ế
i quy t bài toán b ng máy tính ế
ả
ằ
i quy t bài toán b ng máy tính
ng pháp gi
ế Khái ni m v bài toán Quá trình gi ươ Các ph ạ Phân lo i bài toán
Ch
ậ ậ
ễ
ụ
ậ
ươ ị ể ộ ố ậ ậ
ng 2: Thu t toán Đ nh nghĩa thu t toán ậ Bi u di n thu t toán M t s thu t toán thông d ng ệ Thu t toán đ quy ả i heuristic Thu t gi
9
ậ
ị
2.1. Đ nh nghĩa thu t toán
Là m t khái ni m c s c a toán h c và tin
ơ ở ủ ệ ọ ộ
h c.ọ
ộ ồ ạ
ượ
ị ỉ ữ ệ Bao g m m t dãy h u h n các l nh/ch th ể ướ ng c đ h ạ ằ ự
ể ộ ề ụ ẫ ượ rõ ràng và có th thi hành đ ộ d n th c hi n m t hành đ ng nh m đ t đ
ự ể ệ ủ ộ ươ ng
Thu t toán là s th hi n c a m t ph ế
10
ể ả ộ ấ ệ c m c tiêu đ ra. ậ pháp đ gi ề i quy t m t v n đ .
ụ ầ ử ớ ậ ấ l n nh t
Các b
ủ ạ ố ộ Ví d 1: Thu t toán tìm ph n t ữ c a m t dãy h u h n các s nguyên
c:ướ ặ
ố
ờ
ầ
ấ ạ
ớ
ơ
ố
ế
ặ
ấ ạ ấ ạ
ớ ấ ạ
ờ ằ
ư
ế
ố
ị ớ 1. Đ t giá tr l n nh t t m th i là s nguyên đ u tiên. ị ớ ế ế ố 2. So sánh s nguyên k ti p trong dãy v i giá tr l n ị ớ ờ nh t t m th i, n u s nguyên này l n h n giá tr l n ố ị ớ ờ nh t t m th i thì đ t giá tr l n nh t t m th i b ng s nguyên này. i b
c 2 n u còn s nguyên trong dãy ch a
3. L p l ượ
đ
ế
ị ớ
ờ
ượ ị ớ
ấ
ặ ạ ướ c xét. ư ố ừ 4. D ng n u không còn s nguyên nào trong dãy ch a ấ ạ đ c xét. Giá tr l n nh t t m th i lúc này chính là giá ố tr l n nh t trong dãy s .
11
ụ ả ươ ậ ng trình b c
ậ i ph Ví d 2: Thu t toán gi hai: ax2 + bx + c = 0 (a(cid:0) 0)
ậ
ệ ố
ự
ệ
1. Nh p 3 h s a, b, c 2. Tính giá tr ị Δ = b2 4*a*c 3. Xét d u ấ Δ. N u ế Δ>0 thì th c hi n các thao tác
ứ
ả
ệ
sau đây: ệ 3.1. Tính các nghi m theo các công th c: x1 = (bsqrt(Δ))/(2*a) x2 = (b+sqrt(Δ))/(2*a) ấ ế 3.2. Xu t k t qu : ph
ng trình có hai nghi m x
1 và x2.
ươ ấ ế
ả
ươ
4. N u ế Δ là 0 thì xu t k t qu : ph
ng trình có
ệ
nghi m kép là b/(2*a) ấ ế
ả
ươ
5. N u ế Δ<0 thì xu t k t qu : ph
ng trình vô
nghi mệ ừ
ậ
6. D ng thu t toán
12
ủ
ư
ặ
ậ
Các đ c tr ng c a thu t toán
ậ
ị
ừ
ộ ậ
ấ
ợ
Nh p (input):
có các giá tr nh p t
m t t p h p nh t
ậ ị đ nh. ấ
ậ
ạ
ợ
t
Xu t (output): ấ
ị ủ ậ ấ ị
ợ
ị
ộ ị
ướ
ừ ỗ m i giá tr c a t p h p nh p, t o ra giá ộ ậ tr xu t thu c m t t p h p nh t đ nh. các b
Tính xác đ nh (definiteness):
c chính xác, rõ
ràng.
ộ ố ữ
ế
ả
ạ Tính h u h n (finiteness):
cho ra k t qu sau m t s h u
ạ h n b
c.
ữ ướ ệ
ượ
ự
ả Tính hi u qu (effectiveness):
đ
ộ ố
ẩ
ố ượ
c đánh giá d a trên ờ ng tính toán, không gian, th i
m t s tiêu chu n (kh i l ử ụ gian s d ng). ổ
ượ
Tính t ng quát (generaliness):
c cho t
ấ ả t c
ư
ạ
ụ áp d ng đ ố các bài toán có d ng nh mong mu n
13
ể
ậ
ễ 2.2. Bi u di n thu t toán
nhiên
ồ ơ ồ
ố
ữ ậ
14
ữ S d ng các ngôn ng : ữ ự ữ ư ữ ự ữ ậ ử ụ Ngôn ng t Ngôn ng l u đ (s đ kh i) ả Ngôn ng t a ngôn ng l p trình (mã gi ) Ngôn ng l p trình
ữ ư
ồ
Ngôn ng l u đ
Các thành ph n:ầ ượ
ễ
Nút gi
i h n: đ
ớ ạ ữ
ể ồ
ở c bi u di n b i hình ôvan có ố ầ ghi ch bên trong, g m có nút đ u và nút cu i:
Ắ
Ầ
Ế
B T Đ U
K T THÚC
ữ
ậ
Nút thao tác: là m t hình ch nh t có ghi các
ự
ệ
ầ
ộ ệ l nh c n th c hi n:
tăng k
ấ ữ ệ
ậ
Nút nh p/xu t d li u:
Đọc a và b
15
ồ
ữ ư Ngôn ng l u đ (2)
ệ
ệ
ề
Nút đi u ki n: là m t hình thoi có ghi đi u ki n
ộ ng có 1 cung đi vào và 2 cung đi
ườ ớ
ườ
ứ
ợ
ề ể ầ c n ki m tra, th ươ ng ng v i 2 tr ra (t
ng h p đúng/sai)
Đúng
Sai
a Cung: là đ 16 ụ ư ễ ậ ả i ắ ầ
B t đ u ậ Nh p a, b, c sai đúng a(cid:0) 0 Δ = b2 4ac ấ đúng sai ươ ậ Xu t: : Không
ph i ả
ng trình b c ph Δ>0 2 sai đúng Δ=0 x1 = (bsqrt(Δ))/(2*a)
x2 = (b+sqrt(Δ))/(2*a) x=b/(2a) ng ươ ấ
Xu t: ph ng trình ấ
Xu t: ph
có 2 nghi m xệ ươ
ệ
có nghi m kép x ng trình
1, x2 ấ
ươ
Xu tph
trình vô
nghi mệ 17 ế K t thúc ồ ể
ậ ươ Ví d : l u đ bi u di n thu t toán gi
ph ng trình b c 2 S d ng m nh đ có c u trúc chu n hóa và ệ ề ẩ v n dùng ngôn ng t ế ấ
nhiên.
ọ ữ ự
ệ
S d ng các ký hi u toán h c, các bi n,
ủ ụ ử ụ
ẫ
ử ụ
ấ ể
c u trúc ki u th t c. Ti n l 18 ộ
Hành đ ng gán:
i i+1
ệ ợ ả ễ ể ẫ ơ i, đ n gi n, v n d hi u. ộ
ộ ọ
ệ
ệ ộ ặ
ề ệ ộ
ề ệ ộ ộ ị ầ
ố
ị ị ầ ế
ế ộ ấ
if (đi u ki n) then (hành đ ng) end if
if (đi u ki n) then (hành đ ng 1)
else (hành đ ng 2)
end if
ấ
C u trúc l p
while (đi u ki n) do (hành đ ng) end while
repeat (hành đ ng) until (đi u ki n)
ố
ị
for (bi n)=(giá tr đ u) to (giá tr cu i) do (hành đ ng) end for
for (bi n)=(giá tr cu i) downto (giá tr đ u) do (hành đ ng) end for ấ
ả
C u trúc nh y
goto nhãn x; 19 ế ủ ươ ậ ng trình b c hai ụ ả ươ ậ ậ
Ví d : thu t toán gi i ph ng trình b c 2 ấ ả ươ ừ Xu t: Không ph i ph ậ
ng trình b c hai, D ng end if delta b*b4*a*c
if delta > 0 then
ừ ấ x1 (bsqrt(Δ))/(2*a)
x2 (b+sqrt(Δ))/(2*a)
Xu t: x1 và x2, D ng
ấ ệ ươ ệ ấ ng trình vô nghi m else if delta = 0 then x12 b/(2*a), Xu t: nghi m kép x12
else Xu t: ph
end if 20 ể ố ố Thu t toán ki m tra s nguyên t
ố
Thu t toán tìm USCLN, BSCNN c a 2 s ủ Thu t toán tìm ph n t ầ ử ớ ấ ộ ậ
ậ
nguyên
ậ l n nh t trong m t dãy ắ Thu t toán s p x p
Thu t toán tìm ki m 21 ế
ế ậ
ậ 22 Có m t s tr ừ Đ nh nghĩa giai th a ớ ố Đ nh nghĩa dãy s Fibonacci: 1, 1, 2, 3, 5, 8, 13,... 23 ị
0! = 1
n! = n*(n1)! v i n>0
ị
f1 = 1,
f2 = 1,
fn = fn1 + fn2 Thu t toán đ quy tính giai th a c a 1 s t ố ự ừ ủ ệ 24 ậ
nhiên:
ố ự
nhiên n
Input: s t
ằ
Output: F(n) b ng n!
ả
i:
Thu t gi
1. if n=0 then F 1
2. if n>0 then F F(n1)*n
3. Output F Thu t toán đ quy tính s h ng th n c a ố ạ ứ ủ ệ ậ ố
dãy s Fibonacci:
Input: s t
Output: F(n) b ng s h ng th n c a dãy
Thu t gi 25 Đ c đi m c a thu t toán đ quy:
ợ ậ
ơ ở ườ ệ
ng h p d ng ủ
ng h p c s /tr
ệ ể
ặ
ườ
Có 1 tr
ầ
Có ph n đ quy bên trong thu t toán (nó g i
đ n chính nó)
ự ế Có s bi n đ i ti n t 26 Vi ố ự ủ ậ t thu t toán tìm USCLN c a hai s t Vi ố ự ủ ậ t thu t toán tìm BSCNN c a hai s t Vi ầ ử ớ ậ t thu t toán tìm ph n t ấ
l n nh t trong ố ữ ạ m t dãy s h u h n ắ Vi
Vi 27 ế
nhiên
ế
nhiên
ế
ộ
ế
ế ế
ế ậ
ậ t thu t toán s p x p
t thu t toán tìm ki m Th ư ữ i gi ả ố
i t t (nh ng ch a ng tìm đ
ố ượ ờ
c l
ấ t nh t) D dàng và nhanh chóng h n so v i gi ơ ớ ả
i ườ
ắ
ch c đã t
ễ
thu t t i u Th hi n m t cách hành đ ng khá t ậ ố ư
ể ệ ộ ộ ộ ớ 28 ự
nhiên,
ủ
ầ
g n gũi v i suy nghĩ và hành đ ng c a con
ng i.ườ Các nguyên lý ế ế ặ ặ ệ ự ặ ể ạ
khi không gian tìm ki m l n => gi
ế
ki m ho c th c hi n dò tìm đ c bi
ủ
c a bài toán đ nhanh chóng tìm ra m c tiêu
ấ Nguyên lý vét c n thông minh: trong bài toán tìm ki m
ớ ạ
ớ
i h n không gian tìm
ệ ự
t d a vào đ c thù
ụ
ẩ ố ư
ụ Nguyên lý tham lam: l y tiêu chu n t
ọ ự ướ ẩ i u toàn c c làm
ộ ủ ừ
c ộ
i gi ả
i ứ ự ộ : th c hi n hành đ ng theo th t Nguyên lý th t h p ứ ự ợ
ạ ằ ộ ờ ụ
tiêu chu n ch n l a hành đ ng c c b c a t ng b
ờ
trong quá trình tìm ki m l
ệ
lý c a không gian kh o sát nh m nhanh chóng đ t
đ ủ
ượ
c m t l ế
ự
ả
t. ả ố
i t i gi 29 30ườ
ố ừ
ủ
ế
ng n i t
nút này đ n nút khác c a
ồ
l u đư
Mã giả
Mã gi
(2)ả
ườ
ặ
ng g p:
ấ
Các c u trúc th
C u trúc ch n:
ề
ề
Nh p:ậ các h s a, b, c
ệ ố
ệ
ề
ậ
Xu t:ấ k t lu n v nghi m c a ph
ậ
Thu t toán:
if a = 0 then
ộ ố
ụ
ậ
2.3. M t s thu t toán thông d ng
ầ ử ớ
ữ
ấ
ạ
ố
Tìm ph n t
ộ
l n nh t trong m t dãy h u h n s
ố
ị ớ
ấ
ố
Nh p:ậ dãy s a[1], a[2], a[3],… a[n]
Xu t:ấ max là giá tr l n nh t trong dãy s đã cho
ậ
Thu t toán:
max a[1]
for i = 2 to n do
if max < a[i] then
max a[i]
ấ
ố
end if
end for
ị ớ
ấ
Xu t: max là giá tr l n nh t trong dãy s
ệ
ậ
2.4. Thu t toán đ quy
ợ
ng h p, cách gi
ộ ố ườ
ấ ủ
ả
i có th vi ph m
ư
ạ
ơ
ạ
ể
i khá đ n
ậ
ậ
ượ
ả
các tính ch t c a thu t toán nh ng l
c ch p nh n.
gi n và đ
ấ
ể ượ
Bài toán có th đ
ả
i
c phân tích và đ a t
ạ
ư ớ ệ
i vi c gi
ơ
ộ ấ
ư
ấ
m t bài toán cùng lo i nh ng c p đ th p h n.
ộ
Ví d :ụ
ệ
ậ
Thu t toán đ quy (2)
ậ
ệ
ậ
Thu t toán đ quy (3)
ố ự
nhiên n
ằ
ố ạ
ủ
ứ
ậ
ả
i:
1. if n=1 or n=2 then F 1
2. if n>2 then F F(n1)+F(n2)
3. Output F
ệ
ậ
Thu t toán đ quy (4)
ừ
ợ
ậ
ọ
ế
ổ ế ớ ườ
ợ
ơ ở
ng h p c s .
i tr
Bài t pậ
ậ
ả
2.5. Thu t gi
i heuristic
ả
ậ
Thu t gi
i heuristic (2)
