ĐẠ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
-----------------
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 ĐGII QUYT
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 hin: Huỳnh Thị Mỹ Hồng
Mã s học viên: CH1101086
TP.HCM, năm 2012
MỤC LỤC
Trang
M ĐẦU ....................................................................................................... 1
CHƯƠNG 1: VẤN Đ KHOA HỌC VÀ CÁC PHƯƠNG PHÁP GII
QUYẾT .......................................................................................................... 4
1.1. Vấn đ khoa hc ...................................................................................... 4
1.1.1. Khái nim ............................................................................................. 4
1.1.2. Phân loi ............................................................................................... 4
1.1.3. Các tình hung vấn đề .......................................................................... 5
1.2. Phương pháp giải quyết vấn đtheo khoa học về phát minh, sáng chế .... 7
1.2.1. Vepol .................................................................................................... 7
1.2.2. Phương pháp giải quyết vấn đề theo khoa học về phát minh, sáng chế . 8
1.2.3. Mt s thủ thuật, nguyên tắc v phát minh, sáng tạo ............................. 9
CHƯƠNG 2: CÁC PHƯƠNG PHÁP NGHIÊN CỨU, GII QUYT VN
Đ BÀI TOÁN TRONG TIN HC ............................................................. 21
2.1. Mục đích nghiên cứu gii quyết bài toán trong tin hc .......................... 21
2.2. Các phương pháp thường ng đ gii quyết vấn đ bài toán trên máy
tính ............................................................................................................... 21
2.2.1. Phương pháp trực tiếp......................................................................... 21
2.2.2. Phương pháp gián tiếp hoc tìm kiếm li gii ..................................... 24
2.2.3. Các phương pháp Heuristic................................................................. 25
2.2.4. Các phương pháp trí tuệ nhân to ....................................................... 25
CHƯƠNG 3: LÝ THIẾT TRÒ CHƠI 8 S .................................................. 26
3.1. Tìm hiểu trò chơi 8 s ............................................................................ 26
3.1.1. Mục đích giải quyết bài toán 8 s trên máy tính .................................. 26
3.1.2. Mô t .................................................................................................. 28
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 vA* ................................................................................. 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
I LIU 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 nhiều tài nguyên khoáng sản, nhiều ruộng đất,
tiền của điều quan trọng để đất nước ta phát trin ta phải có nhiều
người tài giỏi để phát hiện ra cái hay cái mới ng cao dần sự hoàn thiện để
sự giàu có của con người và sự phn 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 Vit Nam ch cn
không thông minh nếu chúng ta đi theo lối mòn kế thừa những cái
sẵn thì chúng ta rất d bị lạc hậu.
Tôi xin k mt câu chuyện như sau:
Ngày xưa, có mt anh thanh niên khe mnh ít hc nhưng sức khe
rất cường tráng. Mt ngày n anh đi tìm việc m đưc mt ông ch khai
thác g nhn vào làm công vic khai thác g. Anh thanh niên rt mng r.
Anh được ông ch phát cho mt cái rìu.
Hôm làm việc đầu tiên, anh thanh niên ng hái vào rừng khai thác g.
Anh khai thác đưc 14 góc g. Ông ch rt hài lòng khen anh ta. Anh
thanh niên rt vui mngngh thm ngày mai s c gng hơn nữa.
Ngày làm vic th hai, anh thanh niên thc sớm hơn ngày đu làm
vic rt vt v đến chiều. Anh khai thác được 12 góc g. Đ động viên được
tinh thn làm vic ca anh ta ông ch vn khen anh ta. Anh thanh niên thy
đưc ng tt ca ông ch nguyn vi lòng ngày mai s c gắng hơn ngày
m trước:
Ngày làm vic th ba, anh thanh niên thc sớm hơn ngày làm việc th
hai làm vic c ngày và không h ngh trưa. Kết qu hôm m vic th ba
anh đã c gng làm việc hơn hai ngày đầu nhưng kết qu ch đưc 11 góc g.
Anh thanh niên rt bun và nói vi ông ch rng:
2
Thưa ông i rt c gng hết sức nhưng kết qu ngày càng không ng
có xu ng gim.
Ông ch tr li: anh một người rất chăm chỉ làm vic nhưng anh
không biết ng cp dng c lao động. Ví d i rìu anh ngày đu rt bén
nên anh khai thác được nhiu g nhưng đến một ngày nào đó không còn
n nữa, đó nói đến thi gian gn, nếu nói đến mt thời điểm xa hơn nó
không còn php na phi thay bng mt dng c khác. Ông ch nói
tiếp, ngoài vic ng cp dng c lao động anh n phi biết sáng to trong
lao động, anh phi suy nghĩ làm thế nào để tn ít sức lao động công vic
đạt được nhiu hiu qu hơn.
T câu chuyn của anh thanh niên ta t ra được bài hc nghiên cu
sáng to ra cái mi là rt cn thiết cho mi con ngưi chúng ta nói riêng và s
phát trin ca xã hi nói chung.
Theo Gaudin, chúng ta không thbằng lòng với vốn kiến thức qhạn
hẹp thu nhận được trong những năm ngồi trên ghế nhà trường, mà phải học
suốt đời, phải có đủ vốn kiến thức về phương pháp để tự mình hc tập, nghiên
cứu suốt đời. người đưa ra định nghĩa về cuộc đời như sau: Cuộc đời
chuỗi đcần gii quyết chui quyết định cần phải ra”. Thật vậy mỗi ngày
chúng ta phải đối mặt biết bao vấn đ cần giải quyết. Câu hỏi đặt ra rằng
chúng ta phải giải quyết như thế nào để hiệu quả nhất. Mt con người khôn
ngoan sống c nào họ cũng muốn tiến dần đến sự hoàn thiện vậy họ luôn
đầu tư, tìm tòi ra cái hay, cái mới.
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 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 cống hiến lớn của nhân loại cho khoa học
hội tất cả các quan n nước luôn ln đãi ngộ đối với những
người đã cống hiến chất xám nh vào nghiên cứu khoa học. Đnghiên cứu