ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH
CHƯƠNG TRÌNH ĐẠO TẠO THẠC SĨ CNTT QUA MẠNG
BÀI THU HOẠCH MÔN HỌC
PHƯƠNG PHÁP NGHIÊN CỨU KHOA HỌC TRONG TIN HỌC ĐỀ TÀI
ỨNG DỤNG MỘT SỐ NGUYÊN TẮC SÁNG TẠO ĐỂ GIẢI QUYẾT
VẤN ĐỀ BÀI TOÁN TRONG TIN HỌC VÀ ỨNG DỤNG GIẢI BÀI
TOÁN 8 SỐ TRÊN MÁY TÍNH

GVHD: GS.TSKH. Hoàng Văn Kiếm
Học viên thực hiện: Huỳnh Thị Mỹ Hồng
Mã số học viên: CH1101086 TP.HCM, năm 2012


3.1.3. Xác định trạng thái đích 29
3.2. Thuật toán tìm đáp án 30
3.2.1. Giới thiệu về A* 30
3.2.2. Chi tiết thuật toán A* 32
3.3. Cài đặt giải thuật 38
3.3.1. Cài đặt giải thuật 38
3.3.2. Hướng dẩn sử dụng 38
TÀI LIỆU THAM KHẢO 39
1

MỞ ĐẦU
Tất cả chúng ta công nhận rằng một nước muốn giàu có hùng mạnh
không những chúng ta có nhiều tài nguyên khoáng sản, có nhiều ruộng đất,
tiền của… mà điều quan trọng là để đất nước ta phát triển ta phải có nhiều
người tài giỏi để phát hiện ra cái hay cái mới nâng cao dần sự hoàn thiện để
sự giàu có của con người và sự phồn vinh của xã hội. Như ta đã biết Việt Nam
đang gia nhập với các nước trên thế giới. Nếu con ngưởi Việt Nam chỉ có cần
cù mà không thông minh và nếu chúng ta đi theo lối mòn kế thừa những cái
có sẵn thì chúng ta rất dễ bị lạc hậu.
Tôi xin kể một câu chuyện như sau:
Ngày xưa, có một anh thanh niên khỏe mạnh ít học nhưng có sức khỏe
rất cường tráng. Một ngày nọ anh đi tìm việc làm và được một ông chủ khai
thác gỗ nhận vào làm công việc khai thác gỗ. Anh thanh niên rất mừng rỡ.
Anh được ông chủ phát cho một cái rìu.
Hôm làm việc đầu tiên, anh thanh niên hăng hái vào rừng khai thác gỗ.
Anh khai thác được 14 góc gỗ. Ông chủ rất hài lòng và khen anh ta. Anh
thanh niên rất vui mừng và nghỉ thầm ngày mai sẽ cố gắng hơn nữa.
Ngày làm việc thứ hai, anh thanh niên thức sớm hơn ngày đầu và làm
việc rất vất vả đến chiều. Anh khai thác được 12 góc gỗ. Để động viên được
tinh thần làm việc của anh ta ông chủ vẫn khen anh ta. Anh thanh niên thấy

Ngày nay, nghiên cứu khoa học là một việc làm hết sức cần thiết đối với
mỗi chúng ta và nó trở thành một hoạt động sôi nổi trên thế giới. Tham gia
nghiên cứu khoa học được xem là cống hiến lớn của nhân loại cho khoa học
và xã hội vì tất cả các cơ quan nhà nước luôn luôn đãi ngộ đối với những
người đã cống hiến chất xám mình vào nghiên cứu khoa học. Để nghiên cứu
3

khoa học được thành con người phải có một tri thức nhất định và nhiều tâm
quyến để cần nghiên cứu sáng tạo. Hiện nay, công nghệ thông tin là một
ngành mũi nhọn, nó là chìa khóa để mở cửa cho tư duy và sáng tạo của con
người.
Qua bài thu hoạch này, em sẽ trình bày các suy nghĩ chủ quan của mình
về các thủ thuật, nguyên tắc về phát minh sáng tạo trong nghiên cứu khoa học
em cảm thấy ấn tượng nhất để có thể áp dụng vào trong đời sống hằng ngày
và trong ngành môn tin học của mình và cách giải bài toán trên máy tính. Qua
đây, em cũng xin được gửi lời cảm ơn sâu sắc đến GS.TSKH. Hoàng Văn
Kiếm, người đã tận tâm truyền đạt những kiến thức nền tảng cơ bản cho
chúng em về môn học “Phương pháp nhiên cứu khoa học trong tin học”. Bên
cạnh đó cũng không thể không nhắc đến công lao trợ giúp không mệt mỏi của
các chuyên gia cố vấn qua mạng thuộc Trung tâm phát triển CNTT – ĐH
Quốc gia TP.HCM và toàn thể các bạn bè học viên trong lớp.
4

CHƯƠNG 1
VẤN ĐỀ KHOA HỌC VÀ CÁC PHƯƠNG PHÁP GIẢI QUYẾT

1.1. Vấn đề khoa học
1.1.1. Khái niệm
Vấn đề khoa học (scientific problem) cũng được gọi là vấn đề nghiên
cứu (research problem) hoặc câu hỏi nghiên cứu là câu hỏi được đặt ra khi

Các phương pháp phát hiện vấn đề khoa học. Có 6 phương pháp:
1) Tìm những kẻ hở, phát hiện những vấn đề mới
2) Tìm những bất đồng
3) Nghĩ ngược lại quan niệm thông thường
4) Quan sát những vướng mắc trong thực tiễn
5) Lắng nghe lời kêu ca phàn nàn
6) Cảm hứng: những câu hỏi bất chợt xuất hiện khi quan sát sự kiện nào
đó.
Một tiếp cận không gian giải quyết vấn đề.
Ý tưởng  Bài toán  Mô hình  Cách giải Bài toán P: Sau khi có ý tưởng, bài toán P được đặt ra nhằm giải quyết
mục đích cuối cùng là gì? Trong cùng điểm nhìn, cùng một không gian, nếu ta
PBài toán P
Điểm nhìn
Không gian, vấn đề
6

thay đổi bài toán thì vấn đề cũng thay đổi nhưng chỉ thay đổi theo mục đích
yêu cầu của bài toán.
Ví dụ: Khi lập trình giải bài toán phương trình bậc 1 nếu cần chuyển
sang giải phương trình bậc 2 thì bài toán lúc này có khác ta chỉ thay đổi mục
đích yêu cầu từ bậc 1 sang bậc 2.
Điểm nhìn: nơi có vị trí, tầm nhìn khách quan nhất, bao quát vấn đề để
khi giải quỵết không còn sai sót hoặc sai sót ít có thể chấp nhận được. Nếu
cùng một bài toán cùng một không gian nhưng điểm nhìn khác nhau thì vấn

phân tích Vepol. Mô hình Vepol gồm 3 yếu tố: một Trường T và trong T có
hai vật chất V1, V2.
V1
T
V2

Tuy nhiên, một hệ thống ban đầu chưa hẳn đã có một chuẩn Vepol đủ 3
yếu tố trên, hoặc đã đủ thì có thể phát triển gì thêm trên Vepol đó.
Có 5 phương pháp:
- Dựng Vepol đầy đủ
- Chuyển sang Fepol
- Phá vỡ Vepol
- Xích Vepol
- Liên trường
8

1.2.2. Phương pháp giải quyết vấn đề theo khoa học về phát minh, sáng chế
Có 40 nguyên lý:
1. Nguyên lý phân nhỏ
2. Nguyên lý “tách riêng”
3. Nguyên lý phẩm chất cục bộ
4. Nguyên lý phản đối xứng
5. Nguyên lý kết hợp
6. Nguyên lý vạn năng
7. Nguyên lý chứa trong
8. Nguyên lý phản trọng lượng
9. Nguyên lý gây ứng xuất sơ bộ
10. Nguyên lý thực hiện sơ bộ
11. Nguyên lý dự phòng
12. Nguyên lý đẳng thế

Đưa một bài toán vào máy tính
1.2.3. Một số thủ thuật, nguyên tắc về phát minh, sáng tạo
1.2.3.1. Nguyên tắc phân nhỏ
Nội dung:
- Chia các đối tượng thành các phần độc lập.
- Làm đối tượng thành các thành phần tháo ráp.
P

MT
Algorithm

Program
10

- Tăng mức độ phân nhỏ của đối tượng.
Nhận xét:
- Nguyên tắc phân nhỏ thường dùng các nguyên tắc “2_tách khỏi”,
“3_phẩm chất cục bộ”, “5_kết hợp”, “6_vạn năng”…
- Ứng dụng quen thuộc nhất chính là chia chương trình thành nhiều chức
năng nhỏ, còn được gọi là “hàm” hay “thủ tục”.
Ứng dụng nguyên tắc trên trong tin học:
Trong lập trình nếu gặp những bài toán dài phức tạp người ta thường
chia những chương trình nhỏ gọi là chương trình con. Chương trình con được
dùng rộng rãi khi xây dựng các chương trình lớn nhằm làm cho chương trình

end;
{Than chuong trinh chinh}
Begin
Writeln(‘Nhap 3 he so: a,b,c(Moi so cach nhau mot dau cach)’);
readln(a,b,c);
PTB2;
if Delta < 0 then write(‘Phuong trinh vo nghiem’)
else
If Delta = 0 then Write(‘Phuong trinh co 1 nghiem: ‘, x1:10:2)
else writeln(‘Phuong trinh co 2 nghiem: x1 = ‘, x1:10:2 ,’***** x2 = ‘,
x2:10:2);
readln;
end.
Trong môn Cấu trúc dữ liệu và giải thuật sắp xếp trộn (merge sort)
Ý tưởng:
Sắp xếp trộn (merge sort) cùng với sắp xếp nhanh là hai thuật toán sắp
xếp dựa vào tư tưởng “chia để trị” (divide and conquer). Thủ tục cơ bản là
việc trộn hai danh sách đã được sắp xếp vào một danh sách mới theo thứ tự.
12

Nó có thể bắt đầu trộn bằng cách so sánh hai phần tử một (chẳng hạn phần tử
thứ nhất với phần tử thứ hai, sau đó thứ ba với thứ tư ) và sau khi kết thúc
bước 1 nó chuyển sang bước 2. Ở bước 2 nó trộn các danh sách hai phần tử
thành các danh sách bốn phần tử. Cứ như vậy cho đến khi hai danh sách cuối
cùng được trộn thành một.
Ví dụ: Ta có 12 13 45 32 100 34 65 10
Ta có ở trên là 8 phần tử cần được sắp xếp:
Ý tưởng của merge sort là thay vì sắp xếp 8 phần tử (khó sắp) thì ta chia
đôi dãy đó ra làm đôi (số phần tử nhỏ hơn > sắp dễ hơn ) và sắp xếp các dãy
con rồi ghép 2 dãy con lại (gọi là merge 2 dãy con).

- Thử bằng nhiệt (phun lửa): chất không phải vàng sẽ nóng chảy và lộ ra
trước tiên.
- Dùng hóa chất để trích vàng trong hỗn hợp vàng-bạc. Dùng phép điện
giải để mạ các đối tượng.
Ứng dụng nguyên tắc trên trong tin học:
Trong môn cơ sở dữ liệu ta tìm phủ tối thiểu của một phụ thuộc hàm:
Ý tưởng: Từ một tập phụ thuộc hàm ban đầu ta loại bỏ các phụ thuộc
hàm dư thừa để tìm phủ tối thiểu.
Ví dụ: Cho lược đồ quan hệ Q(A,B,C,D) và tập pth F={ABCD,
BC,CD}. Tìm phủ tối thiểu?
1. Tách các phụ thuộc hàm sao cho vế phải chỉ còn một thuộc tính.
+ Ta có: F={ABC,ABD,BC,CD}.
2. Bỏ các thuộc tính dư thừa ở vế trái.
+ BC, CD không xét vì vế trái chỉ có một thuộc tính.
+ Xét ABC: Nếu bỏ A thì B+=BCD không chứa A nên không thể bỏ
A. Nếu bỏ B thì A+=A. Không bỏ được thuộc tính nào.
14

+ Xét ABD: Nếu bỏ A thì B+=BCD không chứa A nên không thể bỏ
A. Nếu bỏ B thì A+=A. Không bỏ được thuộc tính nào.
3. Loại khỏi F các thuộc tính hàm dư thừa:
+ Xét ABC: tính AB+=ABCD=Q nên loại bỏ ABC.
+ Xét ABD: tính AB+=ABCD=Q nên loại bỏ ABD.
+ BC: tính B+=B không thể bỏ.
+ CD: tính C+=C không thể bỏ.
Phủ tối thiểu là Ftt={BC,CD}.
1.2.3.3. Nguyên tắc phẩm chất cục bộ
Nội dung:
- Chuyển đối tượng (hay môi trường bên ngoài, tác động bên ngoài) có
cấu trúc đồng nhất thành không đồng nhất.

Chuyển đối tượng có hình dạng đối xứng thành không đối xứng (nói
chung, làm giảm bậc đối xứng).
Nhận xét:
- Giảm bậc đối xứng, ví dụ chuyển từ hình tròn sang hình Oval, hình
vuông sang hình chữ nhật,
- Thủ thuật này rất có tác dụng trong việc khắc phục tính ì tâm lý, cho
rằng các đối tượng phải có tính đối xứng.
- Khi đối tượng chuyển sang dạng ít đối xứng hơn, có thể làm xuất hiện
những tính chất mới lớn hơn. Ví dụ tận dụng hơn về nguồn tài nguyên, không
gian,…
- Nguyên tắc đối xứng, có thể nói là trường hợp riêng của 3 nguyên tắc
phẩm chất cục bộ.
Ứng dụng trong tin học:
16

Ví dụ: Kiểu biến số nguyên (byte, word, unsigned int) chỉ bao gồm các
số nguyên dương, không có tính đối xứng (có cả âm lẫn dương, như dùng
kiểu integer hay longint), nhưng trong thực tế rất nhiều lúc ta chỉ làm việc
trên những số dương, rõ ràng khai báo kiểu này ta đã tiết kiệm được bộ nhớ
và làm cho chương trình trong sáng và linh động hơn.
1.2.3.5. Nguyên tắc kết hợp
Nội dung:
- Kết hợp các đối tượng đồng nhất hoặc các đối tượng dành cho các đối
tượng kế cận.
- Kết hợp về mặt thời gian các hoạt động đồng nhất hoặc kế cận.
Nhận xét:
- “Kế cận“ở đây không nên chỉ hiểu là gần nhau về mặt vị trí hay chức
năng, mà nên hiểu là có quan hệ với nhau, bổ sung cho nhau,… Do vậy có thể
kết hợp các đối tượng “ngược nhau” (ví dụ: bút chì kết hợp với tẩy).
- Đối tượng mới được tạo nên do sự kết hợp, thường có những tính chất,

- Một phần mềm quản lý trong một Trường Đại học được đánh giá là tốt,
nhất định phần mềm phải đáp ứng chức năng của người sử dụng như:
+ Quản lý hồ sơ sinh viên
+ Quản lý điểm sinh viên
+ Quản lý lịch dạy của giảng viên
+ Quản lý thu học phí
Đến một thời điểm nào đó người sử dụng cần thêm chức năng gì thì yêu
cầu phần mềm nâng cấp để đáp ứng nhu cầu của người tiêu dùng.
Thời xưa một sinh viên muốn học anh văn và muốn đánh máy phải sử
dụng cả hai thiết bị là máy đánh chữ, và máy nghe nhạc. Ngày nay, một sinh
18

viên sử dụng máy vi tính có thể làm nhiều công việc như: đánh máy, học anh
văn, lập trình, chơi game giải trí,…
- Trong lập trình chúng ta cảm thấy loại ngôn ngữ nào hỗ trợ nhiều thì
chắc chắn rằng loại ngôn ngữ đó nhiều người dùng.
Trong tin học con người lúc nào cũng áp dụng nguyên tắc này vì công
nghệ phát triển theo từng ngày, nguyên tắc vạn năng là nguyên tắc con người
càng hướng tới.
1.2.3.7. Nguyên lý rẻ thay cho đắt
Nhận xét:
Có nhiều nguyên nhân để ta phải thay thế đối tượng đắt tiền bởi đối
tượng rẻ tiền. Bác Hồ có dạy rằng “Cần, kiệm, liêm, chính” là đức tính của
mỗi con người chúng ta. Vì vậy mỗi người chúng ta cần tiết kiệm cả thời
gian, tiền bạc,… Trong cuộc sống người ta cố gắng nghĩ ra những loại máy có
công suất sản xuất cao như vậy trong một khoảng thời gian ngắn mà ta sản
xuất ra nhiều sản phẩm.
Ứng dụng nguyên tắc trong tin học:
Về tiền bạc:
- Hiện nay trên Internet có nhiều phần mềm mã nguồn mở hoặc

cos(a) + y
i
sin(a)
y’
i
:=x
i
sin(a) + y
i
cos(a)
20

End
Ta dễ dàng nhận thấy rằng đoạn chương trình trên thực hiện tính sin(a)
2000 lần và tính cos(a) 2000 lần. Một chi phí quá cao.
Chúng ta có thể giảm đáng kể chi phí này bằng cách dùng hai biến phụ
sina=sin(a) và cosa=cos(a). Khi đó rõ ràng là một lần tính sin và 1 lần tính
cos.
Đoạn chương trình được viết lại như sau:
sina:=sin(a);
cosa:=cos(a);
For i:=1 to 1000 do
Begin
x’
i
:=x
i
cosa + y
i
sina

người viết yêu cầu và ra lệnh máy tính thực thi các yêu cầu của mình.
2.2. Các phương pháp thường dùng để giải quyết vấn đề bài toán trên
máy tính
2.2.1. Phương pháp trực tiếp
Đặc điểm cách giải quyết vấn đề này là:
- Xác định trực tiếp được lời giải qua một thủ tục tính toán (công thức,
hệ thức, định luật,…) hoặc qua các bước căn bản để có được lời giải.
- Việc giải quyết vấn đề trên máy tính chỉ là thao tác lập trình hay là sự
chuyển đổi lời giải từ ngôn ngữ bên ngoài sang các ngôn ngữ được sử dụng
trong máy tính.
22

- Đi sâu tìm hiểu các phương pháp trực tiếp chính là đi sâu tìm hiểu các
ngôn ngữ lập trình trong máy tính.
Về cơ bản phương pháp lập trình có 3 loại:
Loại 1: Được dùng để biểu diễn cho các bài toán có lời giải chính bằng
một công thức toán học nào đó.
Ví dụ cách giải bài toán phương trình bậc hai trên máy tính. Ngoài việc
biết cách dùng ngôn ngữ lập trình ta phải có kiến thức giải phương trình bậc
hai như thế nào? Biểu diễn lại cách tính giá trị của delta, nghiệm kép, nghiệm
phân biệt,…
Loại 2: Biểu diễn các công thức toán học có lời giải gần đúng (như các
công thức gần đúng sin, cos, e, giải các phương trình siêu việt,…).
Loại 3: Biểu diễn các lời giải tường minh bằng kỹ thuật đệ qui nghĩa là
phân chia các bài toán ban đầu thành những bài toán nhỏ hơn.
Ví dụ: Tính giai thừa của số n, tính trị thứ n của dãy Fibonacci.
Các nguyên lý áp dụng trong phương pháp trực tiếp:
- Nguyên lý 1: Chuyển đổi dữ liệu bài toán thành dữ liệu của chương
trình, có nghĩa là “Dữ liệu của bài toán sẽ được biểu diễn lại dưới dạng các
biến của chương trình thông qua các quy tắc xác định của ngôn ngữ lập trình