BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC SƯ PHẠM TP. HỒ CHÍ MINH

Cao Thị Hải Yến

BƯỚC CHUYỂN TỪ LỜI GIẢI TOÁN
HỌC SANG LỜI GIẢI TIN HỌC CỦA
MỘT BÀI TOÁN

LUẬN VĂN THẠC SĨ GIÁO DỤC HỌC

NGƯỜI HƯỚNG DẪN KHOA HỌC:
PGS. TS. NGUYỄN CHÍ THÀNH

Thành phố Hồ Chí Minh - 2013


BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC SƯ PHẠM TP. HỒ CHÍ MINH

Cao Thị Hải Yến

BƯỚC CHUYỂN TỪ LỜI GIẢI TOÁN
HỌC SANG LỜI GIẢI TIN HỌC CỦA
MỘT BÀI TOÁN

Chuyên ngành: Lí luận và phương pháp dạy học bộ mơn Toán
Mã số: 60 14 01 11

LUẬN VĂN THẠC SĨ GIÁO DỤC HỌC

NGƯỜI HƯỚNG DẪN KHOA HỌC:
PGS. TS. NGUYỄN CHÍ THÀNH

Thành phố Hồ Chí Minh – 2013


LỜI CẢM ƠN

Trước tiên, tơi xin bày tỏ lịng biết ơn sâu sắc đến PGS. TS. Nguyễn Chí Thành, người
đã nhiệt tình hướng dẫn và giúp đỡ tơi hồn thành luận văn này.
Tôi xin chân thành cảm ơn đến quý thầy, cơ: PGS. TS. Lê Thị Hồi Châu, PGS.TS. Lê
Văn Tiến, TS. Trần Lương Công Khanh, TS. Lê Thái Bảo Thiên Trung, TS. Vũ Như Thư
Hương, TS. Nguyễn Thị Nga về những bài giảng Didactic Toán sinh động và đầy ý nghĩa.
Tơi xin chân thành cảm ơn Phịng Sau Đại học, Khoa Toán - Tin trường Đại học Sư
phạm Thành phố Hồ Chí Minh đã tạo những điều kiện học tập tốt nhất cho chúng tôi.
Tôi cũng xin chân thành cảm ơn:
Ban Giám hiệu cùng các thầy, cô trong tổ Tin học TrườngTHPT Trần Phú đã tạo điều
kiện, giúp đỡ tôi tiến hành thực nghiệm.
Tôi cũng xin gửi lời cảm ơn đến các bạn lớp didactic Tốn khóa 22 vì những sẻ chia,
giúp đỡ trong thời gian học tập.
Cuối cùng, tơi hết lịng cảm ơn gia đình đã quan tâm và động viên suốt q trình học
tập của tơi.

Cao Thị Hải Yến

1


MỤC LỤC
LỜI CẢM ƠN .............................................................................................................. 1

MỤC LỤC .................................................................................................................... 2
DANH MỤC CÁC TỪ VIẾT TẮT ............................................................................ 4
MỞ ĐẦU....................................................................................................................... 5
1. Ghi nhận ban đầu và câu hỏi xuất phát ........................................................................5
2. Mục đích và phạm vi nghiên cứu ..................................................................................8
3. Khung lý thuyết tham chiếu và phương pháp nghiên cứu..........................................9
4. Tổ chức luận văn ...........................................................................................................10

CHƯƠNG 1: THUẬT TOÁN – MỘT NGHIÊN CỨU TRI THỨC LUẬN ........ 11
1.1. Thế nào là vấn đề - bài toán ......................................................................................11
1.2. Thuật toán và các phương pháp biễu diễn thuật toán ...........................................13
1.3. Biến và lệnh gán .........................................................................................................18
1.4. Cấu trúc cơ bản của thuật toán ................................................................................20
1.5. Một số phương pháp giải quyết vấn đề - bài tốn...................................................24
1.6. Vai trị của cơng cụ tính tốn ....................................................................................28

CHƯƠNG 2: MỐI QUAN HỆ THỂ CHẾ ĐỐI VỚI THUẬT TỐN TRONG
DẠY HỌC TỐN PHỔ THƠNG GIAI ĐOẠN 1990 – 2000 ................................ 30
2.1. Khái niệm thuật toán .................................................................................................31
2.1.1 Phần lý thuyết .........................................................................................................31
2.1.2. Phần bài tập ...........................................................................................................35
2.2. Ngơn ngữ biểu diễn thuật tốn .................................................................................38
2.2.1 Phần lý thuyết .........................................................................................................38
2.2.2 Phần bài tập ............................................................................................................42

CHƯƠNG 3: MỐI QUAN HỆ THỂ CHẾ ĐỐI VỚI THUẬT TOÁN TRONG
DẠY HỌC TIN HỌC GIAI ĐOẠN 2006 ĐẾN NAY ............................................. 46
3.1. Bài toán và thuật toán trong [M] .............................................................................47
3.1.1. Khái niệm bài toán ................................................................................................48
3.1.2. Khái niệm thuật tốn .............................................................................................49

3.1.3. Một số ví dụ về thuật toán .....................................................................................53
3.1.4 Các tổ chức tin học ................................................................................................61

CHƯƠNG 4: THỰC NGHIỆM ............................................................................... 66
4.1. Mục đích và giả thuyết nghiên cứu ..........................................................................66
4.2. Giới thiệu thực nghiệm ..............................................................................................66
2


4.2.1. Hình thức thực nghiệm: .........................................................................................66
4.2.2. Bài tốn thực nghiệm ............................................................................................66
4.2.3. Dàn dựng kịch bản ................................................................................................67
4.3. Phân tích tiên nghiệm ................................................................................................69
4.3.1. Biến tình huống và biến didactic ...........................................................................69
4.3.2. Các chiến lược có thể ............................................................................................70
4.3.3. Phân tích kịch bản .................................................................................................72
4.4 Phân tích hậu nghiệm .................................................................................................75

KẾT LUẬN ................................................................................................................ 88
TÀI LIỆU THAM KHẢO ........................................................................................ 90
PHỤ LỤC ................................................................................................................... 91

3


DANH MỤC CÁC TỪ VIẾT TẮT

SGK:

Sách giáo khoa


SGV:

Sách giáo viên

GV:

Giáo viên

HS:

Học sinh

UCLN:

Ước chung lớn nhất

MT:

Máy tính

MTCT:

Máy tính cầm tay

4


MỞ ĐẦU
1. Ghi nhận ban đầu và câu hỏi xuất phát

Toán học và Tin học là hai ngành khoa học có liên quan chặt chẽ mật thiết với nhau.
Trong tốn học, để giải một bài toán chúng ta cần nghiên cứu giả thiết đã cho, tìm ra những
phương pháp có thể có để giải, lựa chọn phương pháp thích hợp nhất (có thể là phương pháp
ngắn gọn nhất, cũng có thể là dễ hiểu nhất đối với người làm) và tiến hành giải bài tốn đó.
Trước đây, con người tự mình giải quyết tất cả những bài tốn mà họ bắt gặp. Cùng với sự
phát triển của xã hội, con người tìm cách sáng tạo ra các cơng cụ giúp họ giải quyết những
vấn đề trong cuộc sống, và máy tính điện tử ra đời. Ban đầu máy tính điện tử chỉ giúp con
người tính tốn những phép tính đơn giản như cộng trừ nhân chia các số, đặc biệt là giữa
những con số có giá trị lớn. Dần dần, cùng với sự phát triển của các loại ngôn ngữ lập trình,
con người cải tiến chiếc máy tính điện tử sao cho nó có khả năng giải quyết những bài tốn
phức tạp hơn như kiểm tra một số ngun có phải là số ngun tố khơng, tìm số lớn nhất
trong dãy các số nguyên, và không những trên lĩnh vực tính tốn mà trên nhiều lĩnh vực
khác nhau, nhiều loại dữ liệu khác nhau: các số liệu, hình ảnh, âm thanh, … Trong các lĩnh
vực đó, chúng tơi quan tâm đến việc lập trình giải các bài tốn tốn học.
Máy tính dưới sự điều khiển của con người (thơng qua các chương trình, phần mềm
được con người lập trình sẵn trong máy tính) có thể giải quyết rất nhiều bài tốn phức tạp
trong thời gian ngắn, khơng hề biết mệt mỏi hay ảnh hưởng bởi sự tác động của các yếu tố
khách quan, trong khi đó, con người khơng thể làm được, hoặc làm được trong khoảng thời
gian lớn và tốn nhiều cơng sức. Nhưng con người lại có khả năng phản ứng linh hoạt với
những tình huống bất ngờ, và xét cho đến cùng con người là nhân tố quyết định khả năng
giải quyết các vấn đề, bài toán của MT. Vì vậy trong nghiên cứu này, chúng tơi quan tâm
đến quá trình mà con người “ra lệnh” cho MT giải quyết các vấn đề, bài toán.
Với những ứng dụng đa dạng và phong phú trong nhiều lĩnh vực, Tin học bắt đầu
được đưa vào giảng dạy ở chương trình phổ thơng ở hầu hết các nước. Theo Nguyễn Chí
Thành (2005), tại Pháp và Việt Nam, Tin học được đưa vào trường phổ thơng theo hai hình
thức:
-

Đưa các yếu tố Tin học vào môn Tin học với tư cách là môn học độc lập;


-

Đưa các yếu tố Tin học vào mơn Tốn học;

5


Ở Việt Nam, khác với Tốn học là mơn học xun suốt trong chương trình phổ
thơng, mơn Tin học mới được đưa vào giảng dạy ở trường phổ thông từ những năm 1990.
Trong chương trình cải cách giáo dục năm 1990 (từ 1990 đến trước 2000) Tin học được đưa
vào dạy lồng ghép với mơn tốn, trong chương IV: Khái niệm sơ đẳng về tin học và thuật
toán - đại số lớp 10 (Trần Văn Hạo, Nxb Giáo dục - 1990). Đến chương trình cải cách giáo
dục 2006, Tin học xuất hiện trong chương trình phổ thơng với tư cách là mơn học độc lập và
là mơn học chính khóa.
Cũng theo Báo cáo của uỷ ban nghiên cứu Dacunha-Castelle, 1989:
Chúng tôi không nghĩ rằng Tin học phải được giảng dạy như một mơn (lí thuyết) riêng biệt ở
cấp bậc phổ thơng. Thật vậy, Tin học dạy ở trình độ này sẽ chưa các nguy cơ liên quan đến
sự hình thức hố và nó sẽ cịn nghiêm trọng hơn cả những cái có thể có bên Tốn học. Lập
luận cho rằng một số học sinh yếu kém trong mơn Tốn học có thể sẽ khá hơn khi học Tin
.học khơng có nhiều cơ sở lí thuyết. Ngược lại, việc dẫn nhập các phương tiện Tin học có
thể « cứu vãn » các học sinh có khó khăn và khuyến khích các em khác khi học tốn.
[11, tr 254]

Từ đó dẫn chúng tôi đến câu hỏi: Việc đưa tin học vào giảng dạy trong chương trình
phổ thơng với tư cách là một môn học độc lập ảnh hưởng như thế nào đến việc học tập mơn
Tốn và mơn Tin học của học sinh ở bậc phổ thơng? Học sinh có nhận thấy mối liên hệ mật
thiết giữa hai môn học này hay khơng?
Như đã nói ở trên, việc giải một bài tốn trong tốn học thì chỉ cần đưa ra một
phương pháp hay thuật toán giải và tiến hành giải theo thuật tốn để tìm đáp án là bài tốn
đã được giải xong. Tuy nhiên, để MT giải được bài tốn đó, từ lời giải toán học được đưa ra,

con người cần phải viết một chương trình hồn chỉnh theo một ngơn ngữ lập trình nào đó rồi
biên dịch thành ngơn ngữ máy và cài đặt vào MT, khi đó MT mới hiểu và giải quyết được
bài toán.
Vậy thế nào là lời giải toán học, thế nào là lời giải tin học? Chúng tơi đã cố gắng tìm
hiểu các nguồn tài liệu để trả lời cho câu hỏi trên. Tuy nhiên, qua những tài liệu mà chúng
tơi có được, chúng tơi khơng tìm được định nghĩa “lời giải tốn học” và “lời giải tin học”.
Vì vậy, chúng tơi xin đưa ra định nghĩa lời giải toán học và lời giải tin học như sau:
-

Lời giải toán học là lời giải của một bài toán dựa trên các kiến thức toán học sao
cho tìm được kết quả cho bài tốn sau khi kết thúc lời giải mà con người có thể
hiểu được.
6


-

Lời giải tin học là lời giải của một bài tốn được biễu diễn bằng một thuật tốn
hoặc chương trình sao cho có thể cài đặt được trên MT và cho kết quả bài toán.

Xét bài toán: Với a là số nguyên lớn hơn 2 cho trước, tính tổng:

S=

1
1
1
1
+
+

+ ... +
a a +1 a + 2
a + 50

Có nhiều cách để tính tổng trên, một lời giải tốn học được đưa ra để tính tổng trên là
quy đồng mẫu số tất cả các số hạng rồi cộng các phân số cùng mẫu, hoặc ta có thể tính tổng
S bằng cách thực hiện phép cộng dồn từ trái sang phải đến số hạng cuối cùng thì ta có tổng
cần tính (vẫn dùng quy đồng mẫu số các phân số):
S=

1
1
1
1
1
1
1
1
+
+
+ ... +
= +
+
+ ... +
a
a +1 a + 2
a + 50 
a
a +1 a + 2
a + 50


2 a +1
a ( a +1)

2 a +1
a ( a +1)



Tuy nhiên, nếu lập trình để MT giải quyết bài toán này theo lời giải tốn học trên thì MT sẽ
khơng hiểu được “quy đồng” là gì? Lời giải tin học của bài tốn này dựa trên việc xây dựng
vịng lặp để tính tổng như sau:
Phát biểu lại bài tốn:
Tính tổng S =

1
1
1
1
+
+
+ ... +
với N = 1;50
a a +1 a + 2
a+N

Để tính tổng này ta sẽ không thực hiện gán giá trị S cho biểu thức

1
1

1
1
+
+
+ ... +
nữa mà sẽ thực hiện cộng dồn từng giá trị của các số hạng vào
a a +1 a + 2
a+N
tổng S bằng cách sử dụng vòng lặp. Việc tính tổng kết thúc khi N > 50 .
Và thuật toán để giải bài toán trên như sau:
Bước 1: Khởi tạo S và N;
S ← 1 ; N ←0
a

Bước 2: N ← N + 1 ;
Bước 3: Nếu N > 50 thì chuyển đến bước 5;
Bước 4: S ← S + 1 ( a + N ) rồi quay lại bước 2;
Bước 5: In ra S và kết thúc.
Sau đó thuật tốn này sẽ được viết thành chương trình trong một ngơn ngữ nào đó để
máy tính thực hiện việc tính tổng.
7


Nếu như khơng có MT, khi các số hạng của tổng được tăng lên đến 100, 1000, … số
hạng hay khi giá trị của a lớn thì con người sẽ mất rất nhiều thời gian và cơng sức để có thể
tính được tổng trên, và đơi khi có thể khơng tính được giá trị của tổng. Tuy nhiên, với sự hỗ
trợ của cơng cụ tính tốn là MT, thơng qua việc xây dựng chương trình tính tổng xuất phát
từ thuật tốn trên, ta có thể tính tổng S với số lượng số hạng bất kỳ giá trị a nguyên bất kỳ
chỉ trong khoảng thời gian rất ngắn.
Từ một bài toán cụ thể thì chưa thể kết luận được điều gì. Tuy nhiên chúng tôi nhận

thấy rằng dường như từ lời giải tốn học sang thuật tốn trong ngơn ngữ lập trình (lời giải
tin học) có một bước chuyển. Bước chuyển đó là khơng dễ dàng đối với những người làm
cơng việc lập trình, đặc biệt là đối với học sinh phổ thông - đối tượng mới được làm quen
với tin học và lập trình trong tin học.
Vì vậy, câu hỏi chúng tôi đặt ra ở đây là: Học sinh phổ thông sẽ làm như thế nào để
chuyển từ lời giải toán học của bài toán trên sang lời giải tin học khi mà Toán học và Tin
học được tách thành hai mơn học chính khóa?
Tất cả những điều trên dẫn chúng tôi đến việc nghiên cứu “Bước chuyển từ lời giải Toán
học sang lời giải Tin học của một bài tốn”.
Từ những ghi nhận trên, chúng tơi phát biểu lại các câu hỏi ban đầu như sau:
-

Giữa lời giải toán học và lời giải tin học của một bài toán có gì giống và khác nhau?

-

Liệu rằng học sinh có nhận thấy sự cần thiết hay điều gì dẫn học sinh tới việc sử

dụng tin học để giải quyết các bài tốn tốn học?
-

Học sinh gặp phải khó khăn, chướng ngại và sai lầm gì khi chuyển từ lời giải Toán

học sang lời giải Tin học của một bài toán? Trong quá trình giảng dạy tin học giáo viên
quan tâm như thế nào đến việc hình thành bước chuyển đó?
-

Bước chuyển từ lời giải Toán học sang lời giải Tin học của một bài tốn tin học có

tác động như thế nào đến việc hình thành tri thức về thuật tốn, tri thức tin học ở học sinh?

-

Vai trị của ngơn ngữ thuật tốn?

2. Mục đích và phạm vi nghiên cứu
Việc nghiên cứu bước chuyển từ lời giải toán học sang lời giải tin học có thể xem xét
ở nhiều phạm vi khác nhau: trong chương trình và SGK, trong thực hành giảng dạy của GV,
trong thực hành giải toán của HS. Trong phạm vi của luận văn này, chúng tôi tập trung vào

8


việc nghiên cứu bước chuyển từ lời giải toán học sang lời giải tin học của một bài toán trong
chương trình và SGK Tin học PT hiện hành.
Cụ thể, chúng tơi sẽ:
-

Làm rõ bước chuyển từ lời giải Tốn học sang lời giải Tin học của một bài toán ở bậc

trung học phổ thơng (nếu có) và ảnh hưởng của nó đến việc hình thành tri thức về thuật tốn
và tin học ở học sinh.
-

Phân tích sự lựa chọn của chương trình và SGK Tốn học và Tin học để biết sự lựa

chọn này có ảnh hưởng như thế nào đến việc hình thành bước chuyển đó. Những khó khăn,
chướng ngại và sai lầm của học sinh khi chuyển từ lời giải Toán học sang lời giải Tin học
của một bài toán.
-


Những bài toán được giải quyết trong tin học có tồn tại trong tốn học và u cầu của

hai thể chế đối với bài tốn đó.

3. Khung lý thuyết tham chiếu và phương pháp nghiên cứu
3.1. Khung lý thuyết tham chiếu
Nội dung đề tài liên quan đến cả hai lĩnh vực Tốn học và Tin học. Vì vậy việc chọn
một khung lý thuyết phù hợp để tham chiếu cho việc nghiên cứu là rất quan trọng. Ở đây,
chúng tôi muốn ứng dụng lý thuyết Didactic toán, cụ thể: lý thuyết nhân chủng học, chướng
ngại và sai lầm, lý thuyết tình huống, hợp đồng didactic trong việc nghiên cứu dạy học Tin
học.
Dựa trên khung lý thuyết tham chiếu đã chọn, chúng tôi phát biểu lại câu hỏi nghiên
cứu như sau:
Q1: Ở cấp độ tri thức luận, thuật tốn và ngơn ngữ thuật tốn có những đặc trưng cơ
bản nào?
Q2: Mối quan hệ thể chế (thể chế dạy học toán học PT giai đoạn 1990 – 2000 và thể
chế dạy học tin học PT hiện nay) đối với thuật tốn có những đặc trưng cơ bản nào? Bước
chuyển từ lời giải toán học sang lời giải tin học của một bài tốn được thực hiện hay khơng,
nếu có thì được thực hiện như thế nào? Bước chuyển đó tác động như thế nào đến việc hình
thành tri thức về thuật tốn, tri thức tin học ở học sinh?
Q3: Trong thể chế dạy học tốn học trung học phổ thơng hiện nay, tồn tại hay không
những kiểu nhiệ m vụ liên quan đến thuật tốn? Có những bài tốn tốn học nào được viết
dưới dạng thuật toán để chuyển sang bài toán tin học? Và ngược lại, những bài toán được
9


giải quyết trong tin học có tồn tại trong thể chế dạy học tốn học khơng? Nếu tồn tại ở cả
hai thể chế thì những mong đợi thể chế của hai mơn học đối với bài tốn đó có gì giống và
khác nhau?
Q4: Học sinh gặp phải khó khăn, chướng ngại và sai lầm gì khi chuyển từ lời giải Toán

học sang lời giải Tin học của một bài toán?
3.2 Phương pháp nghiên cứu
• Tiến hành nghiên cứu lý thuyết thuật toán và các phương pháp giải quyết vấn đề - bài
tốn trên máy tính được đề cập trong tài liệu: Hồng Kiếm, Giải một bài tốn tin học như
thế nào?,tập 1, Nxb Giáo dục. Tìm hiểu mối quan hệ giữa thuật tốn và cơng cụ tính tốn
qua cơng trình nghiên cứu của Nguyễn Chí Thành (2005) để trả lời cho câu hỏi Q1.
• Tiến hành phân tích làm rõ đặc trưng mối quan hệ thể chế đối với thuật tốn để trả lời
cho câu hỏi Q2. Chúng tơi tiến hành phân tích hai thể chế:
-

Thể chế dạy học Tốn học phổ thông giai đoạn 1990 – 2000.

-

Thể chế dạy học Tin học phổ thơng giai đoạn hiện hành.

• Phân tích giáo khoa Tốn hiện hành để tìm hiểu những bài tốn trong chương trình
tốn phổ thơng được viết dưới dạng ngơn ngữ thuật tốn và sự tồn tại của các bài toán được
đề cập trong tin học trong chương trình tốn phổ thơng, những mong đợi của hai thể chế đối
với bài tốn đó (nếu có) để trả lời cho câu hỏi Q3.
• Để trả lời cho câu hỏi Q4: Tiến hành thực nghiệm trên học sinh để biết được những
khó khăn và chướng ngại, sai lầm mà học sinh gặp phải khi thực hiện bước chuyển từ lời
giải theo ngơn ngữ tốn học sang thuật tốn trong tin học thông qua phần mềm Algobox.

4. Tổ chức luận văn
Phần mở đầu
Chương 1: Thuật tốn trong giáo trình bậc đại học.
Chương 2: Mối quan hệ thể chế đối vối thuật toán trong dạy học toán học lớp 10 giai
đoạn 1999 – 2000.
Chương 3: Mối quan hệ thể chế đối với thuật toán trong dạy học toán học và tin học lớp

10 giai đoạn 2006 đến nay.
Chương 4: Thực nghiệm.
Kết luận
Tài liệu tham khảo
10


CHƯƠNG 1: THUẬT TOÁN – MỘT NGHIÊN CỨU TRI THỨC
LUẬN
Mục tiêu của chương
Trong chương này chúng tôi sẽ đi làm rõ những vấn đề liên quan đến thuật toán trong
tin học và các phương pháp giải quyết vấn đề - bài tốn được trình bày trong giáo trình
“Giải một bài tốn trên máy tính như thế nào?”, tập 1của tác giả Hồng Kiếm, Nxb Giáo
dục. Qua đó làm cơ sở tham chiếu cho các phân tích ở chương 2 và chương 3.

1.1. Thế nào là vấn đề - bài toán
Theo Hồng Kiếm, Giải một bài tốn trên máy tính như thế nào?, Nxb Giáo dục,
hiểu một cách đơn giản vấn đề là “những vướng mắc, khó khăn trong cuộc sống mà chúng
ta cần giải quyết” và dưới góc nhìn khoa học thì “vấn đề thường được thể hiện dưới dạng
một bài tốn” cịn “bài tốn là một loại vấn đề mà để giải quyết nó, chúng ta phải ít nhiều
cần đến tính tốn như các bài tốn trong vật lý, hóa học, xây dựng, kinh tế, …”
Trong một thời kỳ dài, các nhà khoa học đều cho rằng “mọi vấn đề đều có thể biểu
diễn dưới dạng một bài tốn”. Hơn thế nữa, khi đại số đang ở đỉnh cao của sự phát triển,
Descartes phát biểu rằng: “tất cả mọi bài tốn đều có thể quy về bài tốn đại số, từ đó, việc
giải tốn chỉ là vấn đề của giải phương trình”. Và vì vậy, ở thời kỳ này các nhà khoa học
trong tất cả các lĩnh vực đều cố gắng biểu diễn các bài toán trong lĩnh vực của mình dưới
dạng các phương trình tốn học. Tuy nhiên cùng với sự phát triển của khoa học kỹ thuật, các
nhà khoa học cũng dần nhận thức được rằng Toán học không phải là công cụ vạn năng để
giải quyết mọi vấn đề.
Về sau, Pythagore chia những vấn đề mà con người cần giải quyết ra làm hai loại:

Theorem và Problem. Trong đó:
- Theorem là vấn đề cần được khẳng định tính đúng sai.
- Problem là vấn đề cần tìm giải pháp để đạt được một mục tiêu xác định từ những
điều kiện ban đầu nào đó.
Sau đó các nhà nghiên cứu lại cho rằng, hai loại vấn đề mà Pythagore đưa ra đều có
thể được diễn đạt bằng sơ đồ sau:

11


Trong đó:
A là giả thuyết hoặc điều kiện ban đầu
B là kết luận hoặc mục tiêu cần đạt
“ ⇒ ” là suy luận, giải pháp cần xác định.
Tuy nhiên trên thực tế, không phải lúc nào ta cũng gặp những vấn đề mà A và B
được xác định rõ ràng, chính xác. Vì vậy, nếu xét theo tính rõ ràng của vấn đề thì người ta
chia vấn đề thành 4 loại: Loại 1 là các vấn đề - bài toán với thông tin về A và B rất rõ ràng,
loại 2 có mục tiêu khơng rõ ràng, loại 3 có giả thiết không rõ ràng và cuối cùng là loại 4 với
cả giả thiết và mục tiêu đều không rõ ràng.
Việc giải quyết các vấn đề - bài toán nhanh hay chậm, đơn giản hay phức tạp là phụ
thuộc nhiều yếu tố khác nhau. Có những vấn đề được giải quyết thơng qua nhiều q trình
phức tạp và cũng có những vấn đề tưởng chừng như rất đơn giản nhưng để giải quyết nó đơi
khi con người phải lặp đi lặp lại các thao tác giống nhau dẫn đến sự nhàm chán. Vì vậy sự ra
đời của MT đã giúp cho con người giải quyết các vấn đề - bài tốn một cách đơn giản hơn.
Bởi vì so với con người, MT có thể tính tốn một khối lượng phép tính rất lớn với tốc độ
cực nhanh, chính xác mà không hề biết “mệt mỏi” hay nhàm chán.
Tuy nhiên, như đã nói trong phần mở đầu, khơng phải là MT tự bản thân nó có khả
năng thực hiện những tính tốn đó, mà con người chính là nhân tố quyết định cho quá trình
giải quyết các vấn đề - bài tốn của máy tính. MT chỉ thực hiện các q trình tính tốn theo
các u cầu của con người được cài đặt sẵn trong chương trình của máy. Nhưng MT lại

không hiểu được ngôn ngữ của con người, mà chỉ hiểu những yêu cầu dưới dạng những con
số nhị phân 0 và 1.
Ban đầu (trong các thế hệ MT đầu tiên) để hướng dẫn cho MT thực hiện các yêu cầu
của mình con người phải “ra lệnh” cho MT bằng ngôn ngữ máy, tuy nhiên việc này tốn quá
nhiều công sức. Sau này con người sáng tạo ra một loại ngôn ngữ “dễ chịu” hơn mà ta
thường gọi là ngôn ngữ bậc cao. Ngôn ngữ bậc cao gần giống với tiếng Anh nên việc ra lệnh
bằng ngôn ngữ này dễ dàng hơn so với ngơn ngữ máy. Có nhiều loại ngơn ngữ bậc cao khác
nhau, trong đó phải kể đến ngôn ngữ Basic, Pascal và C.
Với sự ra đời của ngôn ngữ bậc cao, việc ra lệnh cho MT không cịn phức tạp như
trước nữa. Lúc này, việc q trình giải quyết một vấn đề - bài tốn nào đó bắt đầu từ việc
xác định bài toán, nghĩa là xác định dữ liệu vào, ra và các yêu cầu đối với thuật toán rồi lựa
chọn cấu trúc dữ liệu phù hợp với dữ liệu vào ra của bài toán. Tiếp đó là xây dựng thuật
12


tốn, lập trình, kiểm thử và cuối cùng là tối ưu chương trình. Sau khi xây dựng được một
chương trình hồn thiện, chương trình sẽ được biên dịch thành ngơn ngữ máy và cài đặt vào
MT. Chúng tôi sẽ không đi sâu vào chi tiết tất cả các quá trình trên mà tập trung nghiên cứu
thuật toán và việc xây dựng thuật toán.

1.2. Thuật toán và các phương pháp biễu diễn thuật toán
Từ “thuật toán” (Algorithm) xuất phát từ tên một nhà toán học người Trung Á là Abu
Abd - Allah ibn Musa al’Khwarizmi. Ông là tác giả một cuốn sách về số học, trong đó ơng
đã dùng phương pháp mô tả rất rõ ràng, mạch lạc cách giải những bài tốn. Sau này, phương
pháp mơ tả cách giải của ông đã được xem là một chuẩn mực và được nhiều nhà toán học
khác tuân theo. Từ Algorithm ra đời dựa theo cách phiên âm tên của ông.
Trong từ điển bách khoa toàn thư, Hebeinstrait đưa ra định nghĩa sau đây cho “thuật
toán”:
Thuật toán là một dãy hữu hạn các quy tắc cần áp dụng trong một thứ tự nhất định cho một số
hữu hạn các dữ liệu, để sau một số bước hữu hạn có thể đi đến một kết quả, và điều đó khơng

phụ thuộc vào các dữ liệu.
[11, tr 258]

Cịn trong khoa học về máy tính, “thuật toán được định nghĩa là một dãy hữu hạn các
bước khơng mập mờ và có thể thực thi được, q trình hành động theo các bước này phải
dừng và cho kết quả như mong muốn”, [8, tr 50].
 Các tính chất cơ bản của thuật tốn:
Thuật tốn có ba tính chất cơ bản là tính xác định, hữu hạn, tính đúng. Trong đó, số
bước hữu hạn của thuật tốn và tính chất dừng của nó được gọi chung là tính hữu hạn. Số
bước hữu hạn của thuật toán là một tính chất khá hiển nhiên. Tính “khơng mập mờ” và “có
thể thực thi được” gọi chung là tính xác định.
Ngồi những đặc trưng trên, thuật tốn cịn có những đặc trưng khác như sau:
Thứ nhất, đầu vào và đầu ra. Mọi thuật toán cho dù đơn giản hay phức tạp đến đâu
cũng phải nhận dữ liệu đầu vào, xử lý nó và cho ra kết quả cuối cùng.
Thứ hai, tính hiệu quả. Tính hiệu quả được đánh giá dựa trên một số tiêu chuẩn như
khối lượng tính tốn, khơng gian và thời gian khi thuật toán được thi hành. Đây là yếu tố
quyết định để đánh giá, chọn lựa cách giải quyết vấn đề - bài toán trên thực tế. Phương pháp
phổ biến nhất để đánh giá thuật toán là độ phức tạp của thuật toán.
13


Khi viết thuật toán để giải quyết một bài toán nào đó thì thơng thường thuật tốn phải
áp dụng được cho mọi trường hợp chứ không phải chỉ một vài trường hợp riêng lẻ của bài
tốn. Đó chính là tính tổng quát của thuật toán. Chẳng hạn thuật toán giải phương trình bậc
hai bằng Delta ln áp dụng được cho mọi số thực a, b, c. Tuy nhiên, trong thực tế không
phải lúc nào người ta cũng xây dựng được các thuật tốn tổng qt, mà đơi khi chỉ xây dựng
được thuật toán áp dụng cho một số trường hợp hay cho một dạng đặc trưng của bài tốn mà
thơi.
 Các phương pháp biểu diễn thuật toán
Thuật toán là phương pháp biểu diễn lời giải của bài toán dưới một góc độ nào đó, vì

vậy cũng cần phải tn theo một số quy tắc nào đó. Để biểu diễn thuật tốn, người ta thường
dùng 3 phương pháp sau:
-

Dùng ngơn ngữ tự nhiên.

-

Dùng lưu đồ - sơ đồ khối (flowchart).

-

Dùng mã giải (ngơn ngữ giả lập trình).

• Ngơn ngữ tự nhiên
Đó là cách biểu diễn thuật tốn bằng ngơn ngữ thường ngày, liệt kê các bước của
thuật toán. Phương pháp này khơng u cầu người viết thuật tốn cũng như người đọc phải
nắm các quy tắc nào cả. Tuy nhiên cách biểu diễn này thường dài dịng, khơng thể hiện rõ
cấu trúc thuật tốn, đơi lúc gây hiểu lầm và khó hiểu cho người đọc. Vì vậy để dễ đọc,
người ta thường viết các bước con lùi vào bên phải và đánh số bước theo quy tắc phân cấp
như 1, 1.1, 1.1.1.
Chẳng hạn thuật tốn Euclide tìm UCLN của hai số nguyên được biễu diễn như sau:

14


[8, tr 58]
• Lưu đồ - sơ đồ khối
Đây là một công cụ trực quan để diễn đạt các thuật toán. Việc biểu diễn bằng sơ đồ
khối sẽ giúp người đọc theo dõi được sự phân cấp các trường hợp và q trình xử lý của

thuật tốn, thường sử dụng trong những thuật tốn rắc rối phức tạp và khó theo dõi được q
trình xử lý.
Việc biểu diễn thuật tốn bằng sơ đồ khối yêu cầu người viết cần phân biệt hai loại
thao tác, đó là thao tác lựa chọn dựa theo một điều kiện nào đó và thao tác hành động (hay
thao tác xử lý).
• Thao tác chọn lựa được biểu diễn bằng một hình thoi, bên trong chứa biểu
thức điều kiện.

∆>0

a=b

• Thao tác xử lý được biểu diễn bằng một hình chữ nhật, bên trong chứa nội
dung xử lý, chẳng hạn:
Tăng i lên 1

Chọn một hộp bất kỳ

• Đường đi.
Khi biểu diễn thuật tốn bằng ngơn ngữ tự nhiên ta mặc định hiểu rằng quá trình thực
hiện diễn ra theo trình tự từ bước trước sang bước sau và chỉ nhảy tới bước nào đó khi có
yêu cầu. Đối với việc biểu diễn bằng sơ đồ khối, các bước được thể hiện bằng hình vẽ và có
thể đặt các hình vẽ này ở vị trí bất kỳ nên cần phải có phương pháp để thể hiện trình tự thực
hiện các thao tác.
Theo đó hai bước kế tiếp nhau được nối bằng một cung, trên cung có mũi tên chỉ
hướng thực hiện. Như vậy việc thực hiện các thao tác trên sơ đồ khối tuân theo chỉ dẫn của
đường mũi tên.
Từ thao tác lựa chọn có thể có đến hai hướng đi, một hướng ứng với điều kiện thỏa
và hướng cịn lại ứng với điều kiện khơng thõa. Do vậy ta dùng hai cung xuất phát từ các
đỉnh hình thoi, trên mỗi cung có ký hiệu Đ/S hoặc Yes/No để chỉ hướng đi ứng với hai

trường hợp thõa điều kiện và không thõa điều kiện đặt ra.

15


Ví dụ: thuật tốn giải phương trình bậc hai được biểu diễn bằng sơ đồ khối.

[8,
tr 62]

• Điểm cuối
Điểm cuối là điểm khởi đầu và kết thúc của thuật toán được biểu diễn bằng hình ơvan
bên trong có ghi chữ “Bắt đầu” (Begin) hoặc “Kết thúc” (End). Điểm cuối chỉ có cung đi ra
(điểm khởi đầu) hoặc chỉ có cung đi vào (điểm kết thúc).
Ngoài ra, việc biểu diễn thuật toán bằng sơ đồ khối là khá cồng kềnh nên trong mơt
số thuật tốn phức tạp, trên sơ đồ khối thường được chia thành nhiều phần khác nhau, và
các phần đó được nối với nhau bằng các điểm nối (connector). Khi sơ đồ biểu diễn thuật
tốn q lớn, phải trình bày trên nhiều trang giấy, người ta phải dùng các điểm nối phần sơ
đồ từ trang này sang trang khác, đó gọi là điểm nối sang trang (off – page – connector). Bên
trong các điểm nối đặt một ký hiệu để biết được sự liên hệ giữa các điểm nối hay các điểm
nối sang trang.

16


Điểm nối giữa các phần khác nhau của sơ đồ.

Điểm nối sang trang (off - page - connector)

[8, tr 63]

• Ngơn ngữ giả lập trình (mã giả)
Một nhược điểm của việc biểu diễn thuật toán bằng sơ đồ khối là sự cồng kềnh, dù
chỉ để mơ tả một thuật tốn nhỏ ta cũng phải cần đến một không gian rất lớn. Hơn thế nữa
sơ đồ khối chỉ phân biệt hai loại thao tác là thao tác lựa chọn và thao tác rẽ nhánh trong quá
trình xử lý, nhưng trong thực tế cịn có thêm các thao tác lặp. Vì vậy ta sử dụng một phương
pháp biểu diễn thuật toán khác, đó chính là dùng ngơn ngữ giả lập trình (mã giả).
Khi sử dụng thuật tốn bằng ngơn ngữ giả lập trình, ta sẽ vay mượn các cú pháp của
một ngơn ngữ lập trình nào đó và dùng một phần ngơn ngữ tự nhiên để thể hiện thuật toán.
Tất nhiên, mọi ngơn ngữ lập trình đều có những thao tác cơ bản là xử lý, rẽ nhánh và lặp. Từ
17


thuật tốn người ta cần phải viết thành chương trình trong một ngơn ngữ lập trình cụ thể và
biên dịch thành ngơn ngữ máy. Vì vậy, việc dùng ngơn ngữ giả lập trình vừa tận dụng được
các khái niệm trong ngơn ngữ lập trình, vừa giúp người cài đặt dễ dàng nắm bắt nội dung
thuật toán. Và một khi đã vay mượn cú pháp và khái niệm của ngôn ngữ lập trình nào đó thì
chắc chắn rằng ngơn ngữ giả lập trình sẽ bị phụ thuộc vào ngơn ngữ lập trình (NNLT) đó.
Sau đây là một ví dụ về biểu diễn thuật tốn bằng ngơn ngữ giả lập trình:

[8, tr 64 ]

1.3. Biến và lệnh gán
Để biễu diễn thuật toán ngắn gọn hơn, người ta sử dụng các biến - nơi lưu trữ giá trị.
Trong tin học, mỗi biến bất kì đều có ba thuộc tính cơ bản: tên, kiểu biến và giá trị hiện tại
mà biến đang lưu giữ. Giá trị của biến có thể thay đổi trong quá trình thực hiện chương
trình, tuy nhiên kiểu biến và tên biến không thay đổi. Chẳng hạn, nếu biến A lưu trữ giá trị
số ngun thì nó khơng thể lưu trữ giá trị số thực hay chuỗi kí tự.
Mỗi biến đều có tên riêng để phân biệt với các biến khác. Trong các chương trình,
tùy vào từng ngơn ngữ lập trình khác nhau mà có những yêu cầu đối với việc đặt tên biến
nhưng đều tuân thủ một nguyên tắc chung là ngắn gọn và dễ nhớ.

Biến có thể thay đổi giá trị trong quá trình thực hiện chương trình. Để thay đổi giá trị
của biến, ta sử dụng lệnh gán với cú pháp như sau:
Biến:=<biểu thức>
Lệnh gán không phải là phép so sánh giữa hai biểu thức mà là thao tác tính giá trị
biểu thức bên phải lệnh gán và đặt kết quả này vào biến ở bên trái lệnh gán. Lệnh gán làm
thay đổi giá trị hiện tại của biến và không thể nào lấy lại giá trị này của biến. Chẳng hạn, xét

18


bài toán: “Cho hai biến A và B. Hãy thực hiện lệnh gán sao cho giá trị của hai biến A và B
hoán đổi cho nhau”.
Nếu thực hiện hoán đổi bằng hai lệnh gán: A:=B; B:=A thì sau lệnh gán thứ nhất giá
trị ban đầu của A đã mất, thay vào đó là giá trị của B, sau lệnh gán thứ hai B vẫn có giá trị là
B. Như vậy việc hốn đổi khơng thành cơng.
Để thực hiện việc hốn đổi này, ta xem xét bài toán hoán đổi nước trong hai ly A và
B. Việc hoán đổi sẽ được thực hiện cùng với một ly TẠM có dung tích bằng hai ly A và B
như sau:

Quay trở lại với bài toán hoán đổi giá trị hai biến A và B, việc hốn đổi sẽ được thực
hiện thơng qua 3 lệnh gán:
Tam:=A;

A:=B;

B:=Tam;

Ngồi ra, có thể thực hiện việc hốn đổi bằng ba câu lệnh gán sau:
A:= A+B;


B:=A-B;

A:=A-B;

Tuy nhiên, trên thực tế người ta không bao giờ dùng cách này mà dùng cách hoán đổi giá trị
hai biến bằng biến trung gian Tam.
Như vậy, có phép gán được sử dụng để gán giá trị cho biểu thức, biến hay hoán đổi
giá trị hai biến cho nhau.

19


1.4. Cấu trúc cơ bản của thuật toán
Một vấn đề nữa mà chúng tôi muốn đề cập đến trong chương này, đó là cấu trúc cơ
bản của thuật tốn.
Dù biễu diễn thuật tốn bằng ngơn ngữ tự nhiên, sơ đồ khối hay dùng ngơn ngữ giả
lập trình thì việc xây dựng thuật toán đều dựa trên ba cấu trúc cơ bản: cấu trúc tuần tự, cấu
trúc rẽ nhánh và cấu trúc lặp. Đây cũng là cấu trúc cơ bản của một chương trình.
• Cấu trúc tuần tự
Đây được xem như là cấu trúc được mặc định trong MT, các thao tác được thực hiện
tuần tự từ thao tác đầu tiên đến thao tác cuối cùng. Nếu thuật tốn có n bước thì việc thực
hiện sẽ được tiến hành từ bước đầu tiên đến bước thứ n.
• Cấu trúc rẽ nhánh
Cấu trúc rẽ nhánh có hai dạng cơ bản là rẽ nhánh có điều kiện và rẽ nhánh khơng có
điều kiện.
o Cấu trúc rẽ nhánh có điều kiện bao gồm hai dạng:
Dạng 1, rẽ nhánh đơn (hay còn gọi là rẽ nhánh dạng khuyết). Nghĩa là chỉ thực hiện
rẽ nhánh khi biểu thức logic đúng. Nếu biểu thức logic sai thì thực hiện bước kế tiếp của
thuật toán.


[8, tr 148]
Dạng 2, rẽ nhánh đơi (hay cịn gọi là rẽ nhánh dạng đủ). Nghĩa là nếu biểu thức
logic đúng hay sai thì đều thực hiện công việc đối với trường hợp đúng hoặc sai tương ứng.

20


[8, tr 148]
Trong thực tế có nhiều lúc ta cịn gặp những dạng rẽ nhánh không chỉ là xét một biểu
thức logic với hai trường hợp tương ứng là đúng, sai mà còn dựa vào giá trị một biểu thức
số học, ứng với mỗi giá trị của biểu thức ta lại có một xử lý riêng.
Nó được phát biểu như sau:

[8, tr 157]
Và biễu diễn dưới dạng sơ đồ khối như sau:

21


[8, tr 157]
o Cấu trúc rẽ nhánh khơng có điều kiện
Khác với rẽ nhánh có điều kiện, rẽ nhánh khơng có điều kiện khơng dựa trên một
biểu thức điều kiện nào mà chỉ đơn thuần thay đổi thứ tự thực hiện tuần tự của chương trình.
• Cấu trúc lặp
Đối với máy tính, cấu trúc lặp là một trong ba cấu trúc cơ bản của máy tính. Đặc biệt
đối với các tính tốn gần đúng vì chỉ cần một phép tốn cộng và phép lặp, MT đã có thể
thực hiện mọi phép toán khác từ nhân, chia cho đến lũy thừa, rút căn, sin, cos, … Máy tính
phân biệt hai cấu trúc lặp, đó là lặp xác định và lặp khơng xác định.
o


Cấu trúc lặp xác định được sử dụng khi ta “biết trước” số lần lặp trước khi

thục hiện. “Biết trước” ở đây phải hiểu theo kiểu số lần lặp có thể tính được theo tham số
nào đó của bài tốn. Chẳng hạn như việc tính tổng S với hằng số n cho trước:
n
1 1
1
1
S =1 + + + ... + =∑ hay việc tính e x , x là số thực cho trước với độ chính xác nhỏ
n i =1 i
2 3

hơn hằng số

ε

x x2
xn
cho trước bằng công thức: e =1 + +
+ ... + . Trong trường hợp này
n!
1! 2!
x

ta chỉ biết q trình tính tốn sẽ dừng lại khi tính đến số hạng thứ n nào đó và số hạng này
có giá trị tuyệt đối nhỏ hơn hằng số

ε

xn

<ε
:
n!

Đối với NNLT Pascal, lặp với số lần biết trước bắt đầu với từ khóa for. Có hai kiểu
vịng lặp for, một kiểu là for “tăng” nghĩa là biến đếm bắt đầu tại một giá trị bắt đầu “start”,
sau đó tăng dần từng đơn vị cho đến khi lớn hơn giá trị kết thúc “stop”. Một kiểu là for
“giảm”, nghĩa là biến đếm bắt đầu tại một giá trị bắt đầu và giảm dần cho đến khi nhỏ hơn
giá trị kết thúc. Hai dạng vòng lặp for được thể hiện bằng sơ đồ khối như sau:

22


[7, tr 172]
o Cấu trúc lặp không xác định, nghĩa là số lần
lặp không thể xác định bằng công thức tính tốn nào trước
khi bước vào vịng lặp. Trong NNLT Pascal có hai loại cấu
trúc lặp khơng xác định là While và Repeat … Until được
biễu diễn bằng sơ đồ khối như sau:

Trong đó, vịng lặp “While … do” thực hiện <lệnh> cho đến khi “điều kiện thi hành” không
thõa.
Sau đây

là

một

đoạn


chương

trình

trong

NNLT

Pascal
23