03/04/2008
1
CÁC PHƯƠNG PHÁP
GIẢI QUYẾT BÀI TOÁN
TRÊN MÁY TÍNH
Phạm Thế Bảo
Khoa Toán – Tin học
Trường Đại học Khoa học Tự nhiên Tp.HCM
Phân lọai
1
Ph
há
iế
1
.
Ph
ương p
há
ptrựct
iế
p
2. Phương pháp gián tiếphoặc tìm kiếmlờigiải
Phạm Thế Bảo
03/04/2008
2
Phương pháp trựctiếp
• Xác định trựctiếp đượclờigiải qua mộtthủ tục tính toán
(công thức, hệ thức, định luật, …) hoặc qua các bướccăn
bản để có đượclờigiải.
Việ
iải

h
c
hỉ
là
th
ao
tá
c
lậ
p
t
r
ì
n
h
hay là sự chuyển đổilờigiảitừ ngôn ngữ tự nhiên sang
ngôn ngữ máy tính Æ kỹ thuậtlập trình trên máy tính.
• Có ba loạicơ bản:
o Lọai thứ nhất, dùng để biểudiễn cho các bài toán đãcólờigiải
chính xác bằng một công thứctoánhọcnàođó.
ví dụ: tính tổngnsố nguyên dương.
ể
ễ
ầ
(1)
1 2
2
nn
n
+

Cấu
trúc
một
chương
trình
5
.
Cấu
trúc
một
chương
trình
Phạm Thế Bảo
03/04/2008
3
Chuyển đổi quá trình tính toán của bài toán
thành các cấutrúccủachương trình
• Nguyên lý 2 (Định lý Bohn-Jacopini): Mọi quá trình tính
toá
n
đềucóthể mô tả và thựchiệndựatrên
b
acấutrúcc
ơ
bản: tuầntự,rẽ nhánh và lặp.
1. Cấutrúctuầntự
2. Cấutrúcrẽ nhánh
1. Rẽ nhánh có điềukiện: if (condition)
• rẽ nhánh đơn: if ()
• rẽ nhánh đôi: if () else

phân
chia
thành
những
bài
toán
nhỏ
hơn
1. Thủ tụcvàhàm-phương pháp phân chia chương trình thành
những chương trình con.
2. Biếncụcbộ và biếntoàncục
3. Tham số -dữ liệu đầuvào/đầuracủahàm
Phạm Thế Bảo
03/04/2008
4
Biểudiễn tính toán không tường minh bằng đệ quy
• Nguyên lý 4: quá trình đệ quy trong máy tính không đơngiản
như
các
biểu
thức
quy
nạp
trong
toán
học
như
các
biểu
thức

có
không
phải
lúc
nào
cũng
có
Phạm Thế Bảo
03/04/2008
5
Phân lọai phương pháp gián tiếp
1. Phương pháp thử -sai
ố
1. Thử -saihệ th
ố
ng
2. Thử - sai phân lớp
3. Thử -saingẫu nhiên
2. Phương pháp Heuristic
3
Phương
pháp
trí
tuệ
nhân
tạo
3
.
Phương
pháp

vào
chiến
năng
tìm
lời
giải
đúng
(
hoặc
gần
đúng
)
sẽ
phụ
thuộc
vào
chiến
lượcchọnngẫu nhiên và mộtsốđiềukiệncụ thể.
Ví dụ:kiểmtrachấtlượng trong quá trình sảnxuấtcủamột đoàn kiểmtra.
Một lô hàng có 1000 thùng, chọnngẫu nhiên 10 thùng, mỗi thùng có
24 sảnphNm, chọnngẫu nhiên 5 sảnphNm,
Phạm Thế Bảo
03/04/2008
6
N guyên lý được phát triên thành phương pháp Monté-Carlos.
Càng ngày nguyên lý ngẫu nhiên càng phát triểnmạnh mẽ,
trong sốđócómộtphương pháp nổibậtlàphươn gpháp
Genetic
.
3. N guyên lý mê cung: nguyên lý này đượcápdụng khi chúng ta

"
c
ủ
a
lời
g
iải
,m
à
p
hải
x
â
y
dựng lờigiảidần qua từng bước, giống như tìm đượcrakhỏi
mê cung.
Phạm Thế Bảo
Thử sai - hệ thống
1. N guyên lý vét cạntoànbộ:muốn tìm cây kim trong đống
rơm, hãy lầnlượt rút từng cọng rơm đến khi rút đượccây
kim.
Thuậtgiải: gọi D là không gian bài toán (tậptấtcả khả năng
xảyra),D={(x
1
,x
2
, ,x
n
)/x
i

con
.
Hỏi
có
bao
nhiêu
gà
và
chó
?
Phạm Thế Bảo
03/04/2008
7
2. N guyên lý mắtlưới: lướibắtcáchỉ bắt đượcnhững con cá có
kích thướclớnhơnkíchthướcmắtlưới.
Ví dụ:
Tìm nghiệmphương trình trong một đoạn
Khử nhiễu trong ảnh
3. N guyên lý mê cung: Muốn thóat khỏimêcungthìphảibiết
quay lui và biết đánh dấunhững nơi đã đi qua.
Ví dụ:
Tìm đường đingắnnhất
Phạm Thế Bảo
Thử - sai phân lớp
1. N guyên lý chung về giảm độ phứctạpcủathử - sai: thu hẹp
tập
trường
hợp
trước
và

l i
[
1
]
1
hil ( [
i
]
0
)
d
s
á
n
h
?
v
iết
l
ạ
i
: a
[
n+
1
]
=-
1
;w
hil

thành
phần
x[
i
]
mà
không
phải
chóng
loại
bỏ
được
các
khả
năng
cho
thành
phần
x[
i
]
mà
không
phải
xây dựng toàn bộ n-i thành phầncònlạicủalờigiải.
Ví dụ:chosáusố tự nhiên A={1,7,2,9,3,5}. Tìm dãy con củaAsao
cho tổng các phầntử trong dãy con bằng 8.
4. N guyên lý đánh giá nhánh cận: nhánh có chứaquả phảinặng
hơntrọng lượng củaquả.
Ví dụ: bài toán ngườidulịch.

–
ví
dụ
:
ví
dụ
:

Mộtembébị lạc đường về nhà, em nhớ nhà mình cao
nhất trong khu vực, em sẽ tìm đến tòa nhà cao nhất
trong vùng em thấy, rồilạitiếptục ,
Giảiphương trình bậc2,đoán nghiệmtheoVi-ét
Phạm Thế Bảo
03/04/2008
9
Tìm kiếm theo chiều sâu và chiềurộng
• Là thử - sai theo nguyên lý mê cung hay
hí h
là
thử
i
kết
h
lầ
c
hí
n
h
là
thử

ớ
c
khả
n
ă
ng
"
suy
l
u
ậ
n
"
c
ủ
a
con người.
ví dụ: bài toán đong nước, có 3 bình A, B, và
C có dung tích 5, 8, và 13 lít. Làm sao đong
được
11
lít
nước
trong
bình
C?
Bình
C
ban
được