VẤN ĐỀ NGHIÊN CỨU KHOA HỌC CỦA CÁ NHÂN
1. Giới thiệu
Bài luận này không có tham vọng trình bày lại tất cả các luận điểm của các thuật toán,
mà chỉ có mục đích khái quát lại các thuật toán, nguyên tắc, xen kẽ những lập luận, nhưng
ý kiển chủ quan của cá nhân về các nguyên tắc xuất hiện trong các thuật toán đồng thời
đưa ra các ví dụ cụ thể để làm sáng rõ các thuật toán này.
2. Các bước giải quyết một vấn đề bài toán và áp dụng nguyên
lý
Trong bất cứ hoạt động gì của cuộc sống, kể cả học tập, làm việc đến những hoạt động
hàng ngày chúng ta luôn phải đối mặt với các vấn đề. Bạn đang lo lắng làm sao để học kì
này đạt được một suất học bổng, bạn đang lo lắng ngày mai là sinh nhật người bạn thân,
phải mua gì đây? Làm sao xin được tiền của ba mẹ để đi tham quan cùng lớp… Như tôi
khi viết bài báo cáo này cũng rất đang lo lăng: làm sao viết được bài báo cáo thật rõ ràng,
đáp ứng yêu cầu đề ra, lượng kiến thức cũng như khả năng lập luận, khả năng viết bài
được nâng cao, làm sao truyền tải được hết ý của mình đến người đọc đặc biệt là người
thầy sẽ chấm điểm môn này :D
Kỹ năng giải quyết vấn đề là một điểm mấu chốt trong nghiên cứu khoa học, để đạt được
những kết quả tốt trong quá trình nghiên cứu và học tập của mình người làm khoa học cần
rèn luyện cho mình khả năng giải quyết công việc và vấn đề.
Khi đối mặt với các vấn đề, mỗi người trong chúng ta lại có cách giải quyết riêng của
mình, tùy vào đặc tính và khả năng cá nhân, nhưng nhìn chung cách giải quyết đểu được
đưa ra dưới dạng mô hình sau:

Cần xác định A, B, các thao tác để đi từ A đến B.
 A, B không rõ ràng?
 Các điều kiện của cách
giải không minh bạch?
Chúng đa đưa ra một tiến trình để giải quyết các vấn đề nói chung như sau:
Bước 1: Xác định vấn đề - bài toán.
Bước 2: Lựa chọn phương pháp giải.
Bước 3: Xây dựng thuật toán hoặc thuật giải.

học trên
Cài đặt cụ thể: code
b) Gần đúng
Các bài toán dạng này thường là các bài toán đã biết khoảng kết quả sẵn, chúng ta
dùng một thủ thuật nào đó để đi gần đến kết quả nhất có thể.
Bài toán tìm nghiệm của phương trình f(x) trong khoảng (a;b)
 Xác định vấn đề bài toán:
Lấy f(x) = 2x^2 +3 x -2
Tìm một giá trị của x làm cho f(x) = 0;
Bài toán không yêu cầu phải tìm đầy đủ 2 nghiệm của phương trình.
Vấn đề đầu tiên là, phương trình đã cho liệu có nghiệm không?
Rõ ràng ta thấy rằng tich a*c của phương trình trên <0, do đó phương trình trên có
nghiệm.
 Phương án giải
Phương trình có nghiệm ở đâu?
Mặt khác ta lại thấy f(-1)*f(-3)<0
=>nghiệm của phương trình nằm trong khoảng [-3;1]
Tìm bằng cách nào khi đã biết nghiệm ?
Ở đây chúng ta sẽ dùng một phương pháp ước lượng ngiệm gần đúng. Tức là
chúng ta sẽ thắt chặt nghiệm từ 2 đầu đã biết trước này.
 Thuật toán:
Thuật toán được đưa ra đó là phân đôi và xét f(x) tại giá trị ở giữ này. Cụ thể:
B1: xác định đoạn [a;b] chứa nghiệm
B2: xét f(c) với c=(a+b)/2
• F(c) = 0 => nghiệm là c; đến B3
• F( c ) >0 => nghiệm nằm trong [c;b]; gán a = c; quay lại B2
• F(c) <0 => nghiệm nằm trong [a;c]; gán b =c; quay lại B2
B3: nghiệm là c
Trường Đại Học Công Nghệ Thông Tin – Sinh Viên: Nguyễn Lâm Tú 06520525
Phương pháp luận sáng tạo khoa học Trang 4

duy nhất xuống cấp thấp. (ví dụ về hàm tính giai thừa phía trên)
 Đệ quy nhánh: là dạng đệ quy mà trong suốt quá trình thực hiện hàm đệ quy, lời gọi
đệ quy được thực hiện nhiều hơn một lần.
Một ví dụ điển hình là bài toán tháp Hà Nội:
Bài toán: Bài toán tháp Hà Nội (tiếng Anh gọi là Tower of Hanoi hay Towers of
Hanoi) xuất phát từ trò chơi đố Tháp Hà Nội.
Mục đích của bài toán là thực hiện được yêu cầu của trò chơi. Dạng bài toán thông
dụng nhất là: "Người chơi được cho ba cái cọc và một số đĩa có kích thước khác
nhau có thể cho vào các cọc này. Ban đầu sắp xếp các đĩa theo trật tự kích thước
vào một cọc sao cho đĩa nhỏ nhất nằm trên cùng, tức là tạo ra một dạng hình nón.
Người chơi phải di chuyển toàn bộ số đĩa sang một cọc khác, tuân theo các quy tắc
sau:
+ một lần chỉ được di chuyển một đĩa
+ một đĩa chỉ có thể được đặt lên một đĩa lớn hơn (không nhất thiết hai đĩa này phải
có kích thước liền kề, tức là đĩa nhỏ nhất có thể nằm trên đĩa lớn nhất)".
Trường Đại Học Công Nghệ Thông Tin – Sinh Viên: Nguyễn Lâm Tú 06520525
Phương pháp luận sáng tạo khoa học Trang 6
Phân tích phương án giải:
Với trường hợp 2 đĩa,giả sử 3 cột lần lượt là A,B,C;Với A là cột chứa các đĩa theo
thứ tự nhỏ đến lớn; ta chỉ cần chuyển: 1. đĩa trên cùng qua B, 2.dĩa còn lại qua C; 3.
Đĩa từ B qua C là đã thỏa mãn yêu cầu bài toán.
Trường hợp 3 đĩa:
1. AB
2. AC
3. BC
4. AB
5. CA
6. CB
7. AB
Trường hợp 4 đĩa:

đệ quy này là sự thay đổi vai trò của các cột: ở B1 cột A là nguồn, cột B là đích, C
là trung gian; ở B2 : B- là nguồn, C là đích, A là trung gian.
Trong bài toán này chúng ta dã sử dụng đệ quy trong 2 nhánh B1 và B3.
Cài đặt: code
 Đệ quy hỗ tương: là dạng đệ quy mà trong đó có sự gọi quay vòng như A gọi B, B
gọi C rồi C gọi lại A.
d)Quy hoạch động
Trong nghành Khoa học máy tính và toán học người ta sử dụng phương pháp
quy hoạch đông(dynamic programming) để giải quyết các vấn đề phức tạp bằng
cách chia nhỏ vấn đề phức tạp đó thành các vấn đề đơn giản hơn.
Chúng ta vừa tiếp cận một số phương pháp giải toán : tính trực tiếp chính xác, gần
đúng và đệ quy. Các phương pháp đó chỉ có thể giải quyết các bài toán mang tính
chất đơn giản, gần gũi với khả năng tính toán của con người. Để giải quyết các vấn
đề phức tạp hơn, có sự biến thiên các giá trị trong một vùng xác định người ta sử
dụng đến quy hoạch động.
Phương pháp quy hoạch động có thể được khái quát bởi hình ảnh sau:
Trường Đại Học Công Nghệ Thông Tin – Sinh Viên: Nguyễn Lâm Tú 06520525
BOTTOM-TOP
OVERLAPPING -SUBPROBLEMSTOP-DOWN
OPTIMAL SUBSTRUCTURE
Phương pháp luận sáng tạo khoa học Trang 8
Hướng tiếp cận của quy hoạch động có thể là bottm-top hoặc top-down,trong đó 2
tính chất của nó luôn được đảm bảo: tối ưu hóa các cấu trúc con thành
phần(optimal substructure) và giải quyết các vấn đề con theo hướng từng bước,
bước này dựa vào các bước trước đó(overlapping subproblems)
Chúng ta hãy xet bài toán về dãy Fibonaci quen thuộc.Bài toán này được giải bằng
đệ quy như sau:
int Fib(int n) {
if(n==1||n==0) {
return 1;

B4:trả về giá trị của số Fibonaci thứ n. Kết thúc.
 Tiếp cận bottom –top:
Cách này sự dụng cách tính trực tiếp, thuật toán như sau:
B1: nhận vào số fibonaci thứ n
B2: Gán f1=f2=1;
Lặp i 2n-1
newF =previousF+currenceF;
previousF=currenceF;
currenceF =newF;
B3.Trả về giá trị của số fibonaci thứ n currenceF
Cài đặt: code (xem file)
Cái nào là optiminal substructure cái nào là overlapping subproblems ?
Phân tích tính tối ưu về cấu trúc con(optimal substructure):
Trong 3 thuật toán để giải bài toán nêu trên chúng ta đều thấy vấn đề được chia nhỏ
dần thành các vấn đề nhỏ hơn, và giải quyết. Vấn đề nhỏ nhất được chia là khi n=1
và n=0.
Chúng ta hãy để ý đến cấu trúc chia nhỏ này, rõ ràng đối với quy hoạch động các
cấu trúc được tối ưu tốt nhất, tài nguyên được đảm bảo sử dụng ít nhất có thể.
Trường Đại Học Công Nghệ Thông Tin – Sinh Viên: Nguyễn Lâm Tú 06520525
Phương pháp luận sáng tạo khoa học Trang 10
Phân tích về giải quyết các vấn đề từng bước, bước hiện tại dựa vào các bước trước
(overlapping subproblems):
Rõ ràng từ các vấn đề cơ bản (f1=f0=1), chúng ta sử dụng để giải quyết các vấn đề
lớn hơn. Từ các vấn đề vừa giải quyết chúng ta lại sử dụng để giải quyết các vấn đề
tiếp theo.
3.2.Phương pháp thử sai
a) Vét cạn/duyệt toàn bộ
Vét cạn toàn bộ là một phương pháp được sử dụng cho những bài toán có không
gian tìm kiếm nhỏ. Chúng ta hãy xét một ví dụ sau:
Cho 100 con Trâu ăn 100 bó cỏ. Trâu đứng ăn 5, Trâu nằm ăn 3, Trâu già 3 con một

Gọi D(Domain) là không gian của vấn đề - bài toán (hay tập tất cả trường hợp, khả
năng có thể xảy ra của bài toán)
D = tập hợp tất cả các bộ (x1,x2,x3,…,xn)
Trong đó:
x1 thuộc D1
x2 thuộc D2
…
xn thuộc Dn
Và Di là các tập hợp hữu hạn có số phần tử là mi.
Gọi quy tắc xác định lời giải là một ánh xạ f:
f: D {True,False}
Để tìm kiếm lời giải của bài toán, ta liệt kê (theo một thứ tự nào đó) và lần lượt xét
tất cả các phần tử của tập D, nếu phần tử X = (x1,x2,..,xn) thỏa f(X) = True thì X là
một lời giải của bài toán.
Trường Đại Học Công Nghệ Thông Tin – Sinh Viên: Nguyễn Lâm Tú 06520525
Phương pháp luận sáng tạo khoa học Trang 12
Rõ ràng phương pháp vét cạn là một phương pháp “thuần túy”, và khá “thông
thường”.Có thể hiểu đơn giản là muốn tìm được lời giải ta sét từng trường hợp xảy
ra cho tới khi tìm được lời giải hoặc hết trường hợp. Làm như thế rõ ràng là khả
chắc chắn, nếu có lời giải nhất định ta sẽ tìm ra. Điều này đã lợi dụng được sức
mạnh tính toán của máy tính. Tuy nhiên, đối với không gian tìm kiếm quá lớn thì
phương pháp này khó có thể áp dụng.
Chúng ta sẽ xem xét một vài ví dụ có thể áp dụng được thuật toán này:
Ví dụ 1: Tìm một số có 3 chữ số sao nó bẳng tổng lập phương của từng chữ số.
Ví dụ 2: Có tờ 1 đồng, 2 đồng, 5 đồng. Hỏi cần bao nhiêu tờ 1 đồng, 2 đồng, 5 đồng
để có 200 đồng.
b) Nguyên lý mắt lưới
Chúng ta thấy được nhược điểm của vét cạn toàn bộ đó là không gian tìm kiếm.
Để giảm bớt yếu điểm này người ta đưa ra một nguyên lý: mắt lưới.
Dựa vào đặc điểm của vấn đề mà ta có thể loại bớt một số trường hợp và do đó loại