BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƢỜNG ĐẠI HỌC SƢ PHẠM HÀ NỘI

NGUYỄN CHÍ TRUNG
PHÁT TRIỂN TƢ DUY THUẬT TOÁN CHO HỌC SINH
THÔNG QUA DẠY HỌC THUẬT TOÁN
Ở TRƢỜNG TRUNG HỌC PHỔ THÔNG
LUẬN ÁN TIẾN SĨ KHOA HỌC GIÁO DỤC HÀ NỘI - 2015

BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƢỜNG ĐẠI HỌC SƢ PHẠM HÀ NỘI

NGUYỄN CHÍ TRUNG
PHÁT TRIỂN TƢ DUY THUẬT TOÁN CHO HỌC SINH
THÔNG QUA DẠY HỌC THUẬT TOÁN Ở TRƢỜNG
TRUNG HỌC PHỔ THÔNG
LUẬN ÁN TIẾN SĨ KHOA HỌC GIÁO DỤC
Chuyên ngành: Lý luận và phƣơng pháp dạy học bộ môn
toán
Mã số: 62 14 01 11


cô trong Hội đồng bộ môn đã giúp chọn tên luận án phù hợp, phản ánh đúng nội
dung nghiên cứu. Tôi chân thành cảm ơn PGS.TS Vũ Quốc Chung đã hƣớng dẫn tôi
trong giai đoạn hoàn thiện luận án để luận án có chất lƣợng tốt hơn.
Trân trọng cảm ơn Quý phòng ban và Quý trƣờng Đại học Sƣ phạm Hà nội đã hỗ
trợ toàn bộ kinh phí đào tạo cũng nhƣ tạo nhiều điều kiện thuận lợi cho Tôi trong
thời gian học tập và hoàn thành chƣơng trình tiến sỹ.
Chân thành cảm ơn các thầy cô của bộ môn Lý luận và Phƣơng pháp dạy học,
Ban chủ nhiệm khoa Công nghệ thông tin đã cho phép và tạo điều kiện thuận lợi
cho tôi đƣợc học chƣơng trình tiến sỹ. Chân thành cảm ơn các thầy cô trong khoa,
các bạn bè đồng nghiệp và các em sinh viên đã chia sẻ và động viên cho tôi trong
thời gian học tập.
Đặc biệt nhất, trong luận án này tôi xin dành sự biết ơn đến gia đình nhất là vợ và
các con đã sát cánh chia sẻ trong suốt thời gian nghiên cứu luận án.

- iii -

BẢNG CÁC CỤM TỪ VIẾT TẮT
Từ viết tắt
Viết đầy đủ
CNTT
Công nghệ thông tin
ĐC
Đối chứng
GV
Giáo viên
HS
Học sinh
NT
Nông thôn
PPDH

Xếp loại mức độ phân tích, tổng hợp
XLVD
Xếp loại mức độ vận dụng

- iv -

MỤC LỤC
MỞ ĐẦU 1
1. Lý do chọn đề tài 1
2. Mục tiêu nghiên cứu 2
3. Nhiệm vụ nghiên cứu 2
3.1. Nghiên cứu lý luận 2
3.2. Nghiên cứu thực tiễn 2
3.3. Đề xuất giải pháp 3
3.4. Thực nghiệm sƣ phạm 3
4. Đối tƣợng nghiên cứu 3
5. Phạm vi nghiên cứu 3
6. Phƣơng pháp nghiên cứu 4
6.1. Nghiên cứu lý luận 4
6.2. Khảo sát điều tra thực tiễn 4
6.3. Nghiên cứu trƣờng hợp 4
6.4. Thực nghiệm sƣ phạm 4
6.5. Thống kê Toán học 4
7. Giả thuyết khoa học 4
8. Các luận điểm bảo vệ và đóng góp của luận án 5
8.1. Về mặt lý luận 5
8.2. Về mặt thực tiễn 5

TƢ DUY THUẬT TOÁN 35
2.1. KHÁI NIỆM TƢ DUY THUẬT TOÁN 35
2.1.1. Những căn cứ để đề xuất khái niệm tƣ duy thuật toán 35
2.1.2. Khái niệm tác nhân và khái niệm tƣ duy thuật toán 36
2.2. CÁC BIỂU HIỆN CỦA SỰ PHÁT TRIỂN TƢ DUY THUẬT TOÁN
TRONG GIẢI BÀI TẬP TOÁN THEO THUẬT TOÁN 37
Bài toán về các chất dinh dƣỡng 38
2.2.1. Hiểu bài toán 38
2.2.2. Hiểu hƣớng giải quyết giải bài toán 40
2.2.3. Hiểu thuật toán giải bài toán 41
2.2.4. Thực hiện đƣợc thuật toán giải bài toán 43
2.2.5. Xây dựng đƣợc thuật toán tƣơng đƣơng 44
2.2.6. Đánh giá đƣợc thuật toán 45
2.2.7. Cải tiến thuật toán hoặc xây dựng đƣợc thuật toán mới 46
2.3. CÁC BIỂU HIỆN CỦA TƢ DUY THUẬT TOÁN TRONG GIẢI BÀI
TOÁN DỰA VÀO CÁC CÔNG CỤ TÍNH TOÁN TỰ ĐỘNG 46
2.3.1. Xác định bài toán 47
2.3.2. Hiểu ý tƣởng thuật toán 48
2.3.3. Hiểu thuật toán 50
2.3.4. Thực hiện đƣợc thuật toán 54
2.3.5. Xây dựng đƣợc thuật toán tƣơng đƣơng 56
2.3.6. Đánh giá đƣợc thuật toán 57
- vi -

2.3.7. Cải tiến đƣợc thuật toán hoặc thiết kế đƣợc thuật toán mới 58
2.4. CÁC CẤP ĐỘ CỦA SỰ PHÁT TRIỂN TƢ DUY THUẬT TOÁN 58
2.4.1. Ý nghĩa của việc xác định các cấp độ tƣ duy thuật toán 58
2.4.2. Các cấp độ tƣ duy thuật toán 59
2.4.3. Những biểu hiện của các cấp độ tƣ duy thuật toán 60
2.4.4. Ví dụ minh họa về các cấp độ tƣ duy thuật toán 61

- vii -

4.1. MỤC ĐÍCH, PHƢƠNG PHÁP ĐÁNH GIÁ VÀ QUI TRÌNH THỰC
NGHIỆM 119
4.1.1. Mục đích, mục tiêu và nhiệm vụ của thực nghiệm sƣ phạm 119
4.1.2. Phƣơng pháp đánh giá trong thực nghiệm sƣ phạm 119
4.2. QUI TẮC MÃ HÓA VÀ QUI ĐỔI ĐIỂM 121
4.2.1. Qui đổi và mã hóa điểm bài kiểm tra - đánh giá tổng kết 121
4.2.2. Qui đổi và mã hóa điểm bài tập nhóm - Đánh giá ngang hàng và tự đánh
giá 122
4.2.3. Qui đổi và mã hóa điểm từ phiếu khảo sát 123
4.3. THỰC NGHIỆM 1 124
4.3.1. Giới thiệu thực nghiệm 124
4.3.2. Kết quả đánh giá bài tập nhóm 125
4.3.3. Kết quả làm bài kiểm tra 128
4.3.4. Kết quả đánh giá về phƣơng pháp dạy học của GV 130
4.3.5. Kết luận thực nghiệm 1 133
4.4. THỰC NGHIỆM 2 134
4.4.1. Giới thiệu thực nghiệm 2 134
4.4.2. Kết quả đánh giá bài tập nhóm và bài kiểm tra 134
4.4.3. Kết quả đánh giá về phƣơng pháp dạy học của giáo viên 140
4.5. ĐỀ XUẤT VÀ KIẾN NGHỊ 142
4.5.1. Về việc dạy học thuật toán ở trƣờng trung học phổ thông 142
4.5.2. Về điều chỉnh một số nội dung của học phần PPDH chuyên ngành môn Tin
học 142
KẾT LUẬN CHƢƠNG 4 143
KẾT LUẬN 144
CÁC CÔNG TRÌNH CỦA TÁC GIẢ 147
TÀI LIỆU THAM KHẢO 148


Ví dụ 3. 5. Tìm phƣơng trình đƣờng thẳng – Bài toán 2 (Hình học lớp 10) 86
Ví dụ 3. 6. Làm mịn từ ngoài vào một lần 93
Ví dụ 3. 7. Tinh chế theo từng bƣớc của quá trình xây dựng thuật toán 105
Ví dụ 3. 8. Tinh chế nâng cấp 112
Ví dụ 3. 9. Về cách ƣớc lƣợng, đánh giá hiệu quả thuật toán 113
- ix -

DANH MỤC CÁC BẢNG
Bảng 1. 1. Bảng thống kê tổng hợp 29
Bảng 1. 2. Thống kê mô tả (Descriptive Statistics) 30
Bảng 1. 3. Mô tả tần suất (Frequency table) 30
Bảng 1. 4. Giá trị các thang đo theo từng đối tƣợng học sinh 31
Bảng 1. 5. Báo cáo các giá trị trung bình của các thang đo nhận thức 31
Bảng 4. 1. Qui tắc qui đổi điểm của một bài tập trong đề kiểm tra 122
Bảng 4. 2. Bảng qui tắc qui đổi điểm của bài tập nhóm 123
Bảng 4. 3. Bảng qui đổi điểm sang các thang đo khảo sát 124
Bảng 4. 4. Thống kê kết quả bài tập nhóm của các lớp thực nghiệm 125
Bảng 4. 5. Thống kê kết quả bài tập nhóm của các lớp đối chứng 126
Bảng 4. 6. Bảng tổng hợp: So sánh kết quả làm bài tập nhóm giữa các lớp thực
nghiệm và các lớp đối chứng 127
Bảng 4. 7. Thống kê kết quả làm bài kiểm tra của các lớp thực nghiệm 128
Bảng 4. 8. Thống kê kết quả làm bài kiểm tra của các lớp đối chứng 129
Bảng 4. 9. Bảng tổng hợp: So sánh kết quả làm bài kiểm tra giữa các lớp thực
nghiệm và các lớp đối chứng 130
Bảng 4. 10. Điểm trung bình đánh giá PPDH của GV 131
Bảng 4. 11. Kiểm định giả thuyết thống kê 132
Bảng 4. 12. Thống kê kết quả bài tập nhóm của các lớp thực nghiệm 135

cấp độ tƣ duy thuật toán đối với bài tập nhóm. 126
Biều đồ 4. 3. So sánh chuẩn tƣ duy thuật toán giữa nhóm lớp thực nghiệm và
nhóm lớp đối chứng. 128
Biều đồ 4. 4. Biểu đồ biểu diễn số lƣợng và tỉ lệ HS các lớp thực nghiệm đạt các
cấp độ tƣ duy thuật toán đối với bài kiểm tra. 128
Biều đồ 4. 5. Biểu đồ biểu diễn số lƣợng và tỉ lệ HS các lớp đối chứng đạt các
cấp độ tƣ duy thuật toán đối với bài kiểm tra. 129
Biều đồ 4. 6. Biểu đồ biểu diễn số lƣợng và tỉ lệ HS nhóm lớp thực nghiệm đạt
các cấp độ tƣ duy thuật toán đối với bài tập nhóm. 135
Biều đồ 4. 7. Biểu đồ biểu diễn số lƣợng và tỉ lệ HS các lớp thực nghiệm đạt các
cấp độ tƣ duy thuật toán đối với bài kiểm tra. 136
Biều đồ 4. 8. Biểu đồ biểu diễn số lƣợng và tỉ lệ HS nhóm lớp đối chứng đạt các
cấp độ tƣ duy thuật toán đối với bài tập nhóm. 137
Biều đồ 4. 9. Biểu đồ biểu diễn số lƣợng và tỉ lệ HS nhóm lớp đối chứng đạt các
cấp độ tƣ duy thuật toán đối với bài kiểm tra. 138
Biều đồ 4. 10. So sánh chuẩn tƣ duy thuật toán giữa nhóm lớp thực nghiệm và
nhóm lớp đối chứng. 140

1

MỞ ĐẦU
1. Lý do chọn đề tài
Bàn về tƣ duy, Pascal cho rằng “Tư duy tạo nên sự cao cả của con người”;
Descartes nói “Tôi tư duy tức là tôi tồn tại”; Emerson nói “Tư duy là hạt giống của
hành động”; H.Poincaré dùng hình ảnh “Tư duy là một tia sáng giữa đêm tối.
Nhưng chính tia sáng ấy là tất cả”. Bàn về dạy học, rèn luyện tƣ duy, nguyên thủ
tƣớng Phạm Văn Đồng nói “Điều chủ yếu không phải là nhồi nhét một mớ kiến thức
hỗn độn mà là phương pháp suy nghĩ, phương pháp nghiên cứu, phương pháp học
tập, phương pháp giải quyết vấn đề”. Theo ngạn ngữ cổ Hy lạp thì “Dạy học không
phải là rót kiến thức vào một chiếc thùng rỗng mà là thắp sáng lên những ngọn

Trong những năm gần đây, dạy học theo định hướng phát triển năng lực đã trở
thành xu hƣớng chính đối với nhiều nƣớc trên thế giới, đặc biệt là các nƣớc phát
triển thuộc OECD (Organisation for Economic Co-operation and Development-Tổ
chức hợp tác và phát triển kinh tế). Dạy học thuật toán có thể xem nhƣ góp vai trò
đáng kể trong dạy học định hƣớng phát triển năng lực giải quyết vấn đề. Bởi lẽ, dạy
học thuật toán hƣởng ứng mục tiêu đào tạo hình mẫu con ngƣời có năng lực tự
quyết và có khả năng ứng xử và giải quyết các vấn đề trong khoa học và thực tiễn.
Với sự đảm bảo của Toán học, thuật toán trong lĩnh vực Khoa học máy tính bồi
dƣỡng cho HS phƣơng pháp tƣ duy hiệu quả trong học tập những môn học khác ở
trƣờng phổ thông, nhất là trong những kiến thức tích hợp và liên môn với Toán và
Tin học.
Với những lý do trên, chúng tôi chọn đề tài “Phát triển tư duy thuật toán cho HS
thông qua dạy học thuật toán ở trường trung học phổ thông” để nghiên cứu
2. Mục tiêu nghiên cứu
Mục tiêu của luận án là đề xuất đƣợc một số cách tiếp cận trong dạy học thuật
toán nhằm phát triển tƣ duy thuật toán cho HS trong dạy học môn Toán và môn Tin
học. Một cách cụ thể, luận án đƣa ra một số cách tiếp cận mới trong dạy học giải
bài tập toán theo thuật toán ở một số nội dung của môn Toán và dạy học các thuật
toán giải các bài toán dựa vào máy tính thuộc lĩnh vực của môn Tin học. Những
cách tiếp cận này nhằm thúc đẩy và hƣớng dẫn HS tƣ duy đúng đắn và hiệu quả
trong giải quyết vấn đề, tức là nhằm phát triển tƣ duy thuật toán cho HS.
3. Nhiệm vụ nghiên cứu
3.1. Nghiên cứu lý luận
Nghiên cứu các vấn đề sau đây:
- Khái niệm thuật toán ở góc độ Toán học và Khoa học máy tính.
- Khái niệm thuật toán đƣợc dạy ở môn Tin học trong trƣờng phổ thông.
- Các tính chất và đánh giá hiệu quả thuật toán.
- Những xu hƣớng dạy học thuật toán hiện nay ở trong nƣớc và trên thế giới.
3.2. Nghiên cứu thực tiễn
3

Về phạm vi lý thuyết, luận án tập trung nghiên cứu về lý luận và phƣơng pháp
dạy học thuật toán ở trƣờng phổ thông.
Về phạm vi đối tượng, luận án hƣớng đến lớp đối tƣợng HS đại trà lớp 10 và lớp
11 THPT, trong đó có một số nội liên quan đến đối tƣợng HS khá.
4

Về phạm vi nội dung, luận án nghiên cứu những bài toán của môn Toán có thể
giải tổng quát theo thuật toán và những bài toán của môn Tin học đƣợc xây dựng
thuật toán thuận lợi cho lập trình để giải quyết trên máy tính.
6. Phƣơng pháp nghiên cứu
6.1. Nghiên cứu lý luận
Nghiên cứu lý luận bao gồm nghiên cứu những bài báo, tạp chí và sách về cách
tiếp cận dạy học thuật toán, và các tài liệu liên quan nhƣ tâm lý học, giáo dục học,
sách giáo khoa và sách giáo viên.
Phân tích tài liệu lý luận trên đây để hoàn thành nhiệm vụ của đề tài.
So sách quốc tế dựa trên cơ sở đánh giá, so sánh tài liệu, cách tiếp cận dạy học
thuật toán ở trong nƣớc và trên thế giới.
Phân tích tiên nghiệm trong nghiên cứu lý luận dựa vào lịch sử hình thành khái
niệm thuật toán và các cách tiếp cận dạy học thuật toán khác nhau để dự kiến những
hiện tƣợng có thể có của HS khi học thuật toán. Từ đó kiểm nghiệm hiện tƣợng đó
trong thực nghiệm sƣ phạm về cách tiếp cận dạy học thuật toán đƣợc đề xuất.
6.2. Khảo sát điều tra thực tiễn
Khảo sát - điều tra thực tiễn dạy học thuật toán hiện nay ở chƣơng trình Tin học
lớp 10 và lớp 11, THPT, để phát hiện những thuật lợi và khó khăn trong việc dạy
học thuật toán, giúp thu thập thông tin sinh động cho nghiên cứu.
6.3. Nghiên cứu trƣờng hợp
Dạy học một số nội dung về thuật toán. Trao đổi với GV, theo dõi, ghi chép
những trƣờng hợp này để xây dựng những tiêu chuẩn đánh giá, đo lƣờng các kết
quả điều tra cụ thể. Trên cơ sở đó phân tích, đánh giá dựa trên phần mềm.
6.4. Thực nghiệm sƣ phạm

quan như mô đun thuật toán, thủ tục và hàm.
- Phương pháp làm mịn dần trong dạy học thuật toán.
- Phương pháp tinh chế trong dạy học thuật toán và các khái niệm liên quan
như nguyên tắc tinh chế dựa trên ngôn ngữ, độ phức tạp của biểu diễn thuật
toán.
8.2. Về mặt thực tiễn
Luận án có những đóng góp sau đây về mặt thực tiễn:
- Đề xuất một hƣớng tiếp cận mới trong dạy học thuật toán ở trƣờng THPT,
góp phần rèn luyện cho HS tƣ duy giải quyết các vấn đề trong dạy học môn
Toán và môn Tin học.
- Đóng góp một xu hƣớng mới trong đào tạo sinh viên sƣ phạm Tin học nói
riêng, lĩnh vực Toán - Tin nói chung trong trƣờng Đại học Sƣ phạm Hà Nội.
9. Cấu trúc và tóm tắt nội dung của luận án
Ngoài một số phần nhƣ mở đầu, kết luận, và tài liệu tham khảo, luận án gồm 4
chƣơng sau đây:
Chƣơng 1: Cơ sở lý luận về thực tiễn
- Về cơ sở lý luận: Trình bày nguồn gốc của từ thuật toán, khái niệm thuật toán
trong quá trình hình thành thuật toán trong Toán học và trong Khoa học máy
6

tính, các tính chất của thuật toán. Lịch sử vấn đề nghiên cứu cũng đƣợc giới
thiệu chi tiết, bao gồm các xu hƣớng dạy học thuật toán hiện nay ở trong nƣớc
và trên thế giới.
- Về cơ sở thực tiễn: Trình bày kết quả khảo sát, điều tra tình hình học tập thuật
toán hiện nay ở một số trƣờng THPT.
Chƣơng 2: Các biểu hiện và các cấp độ của sự phát triển tƣ duy thuật toán
- Đề xuất các khái niệm cơ sở nhƣ tác nhân, tƣ duy thuật toán,
- Trình bày các biểu hiện của sự phát triển tƣ duy thuật toán theo hai mức mô tả
thuật toán: mức độ thủ công (giải bài toán theo thuật toán) và mức độ điều
khiển (giải bài toán dựa vào máy tính).

Turkmen, và Uzbek. Tuy nhiên Donald E. Knuth (1980) cho rằng phần tên gọi al-
Khwârizmî lại không chứng minh đƣợc ông sinh ra ở Khwarizm. Vì công việc
nghiên cứu của ông diễn ra ở Baghdad, ở nơi mà một số nhà khoa học vẫn gọi là
“Ngôi nhà thông thái” (“House of Wisdom”) của Caliph al-Ma’mun - nhà tài trợ nổi
tiếng cho các nhà nghiên cứu khoa học, đã từng mời nhiều ngƣời đến khóa học của
ông để tuyển chọn và mở rộng những tài năng trên thế giới. Nhà sử học al-Tabari đã
thêm từ "al-Qutrubbulli" vào tên của al-Khwârizmî, là có ý đề cập đến huyện
Qutrubbulli gần Baghdad. Do đó, Knuth nghĩ rằng al-Khwârizmî đƣợc sinh ra ở
Khwarizm và sống phần lớn cuộc đời ở Qutrubbull sau đƣợc triệu tập tới Baghdad
của Caliph, nhƣng sự thật có thể sẽ không bao giờ đƣợc biết đến.
1.1.2. Sự hình thành khái niệm thuật toán trong Toán học
Theo Dimitris Samaras (2009), thuật toán có vai trò quan trọng trong Toán học.
Các tài liệu Toán học cổ điển đã bao gồm các mô tả về các thuật toán giải quyết các
nhiệm vụ khác nhau nhƣ: tìm số nguyên tố, tìm ước số chung lớn nhất của hai số
nguyên. Khái niệm thuật toán không đƣợc định nghĩa chính xác cho đến tận thế kỉ
20. Trƣớc thế kỉ 20, các nhà Toán học chỉ có một khái niệm trực giác (intuitive
notation) về cái gọi là thuật toán. Khái niệm trực giác về thuật toán không đủ để có
một cái nhìn sâu hơn về việc hiểu thuật toán. Năm 1900, tại hội nghị Toán học quốc
tế ở Paris, nhà Toán học David Hilbert đã đƣa ra 23 bài toán nổi tiếng, mà theo ông
8

đây là những hƣớng nghiên cứu Toán học lý thú cho các nhà Toán học thế giới ở
thế kỷ 20. Trong đó, yêu cầu của bài toán thứ 10 là “hãy tìm một qui trình bao gồm
một số hữu hạn bƣớc thực hiện mà nó cho phép xác định một phƣơng trình
Diophante có nghiệm nguyên hay không”
1
. Tại thời điểm này, Hilbert đã không sử
dụng thuật ngữ “thuật toán” mà sử dụng cụm từ “qui trình với một số hữu hạn các
bƣớc thực hiện” (cụm từ này thể hiện khái niệm trực giác về thuật toán). Trong phát
biểu của mình, Hilbert đã giả định rằng “thuật toán” để kiểm tra là đã tồn tại, ta chỉ

unknown quantities and with rational integral numerical coefficients: To devise a process according to which
it can be determined in a finite number of operations whether the equation is solvable in rational integers.”
(Xem Barry Mazur (2010), “Hilbert’s Tenth Problem and Elliptuc Curves”, in Expository Articles - Notes for
Basic Notations talk, Department of Mathematics, University of Harvard).
2
Máy Turing là một mô hình về thiết bị xử lý các ký tự, tuy đơn giản, nhƣng có thể thực hiện đƣợc tất cả
các thuật toán máy tính. Máy Turing đƣợc xây dựng không dành cho việc trực tiếp chế tạo ra máy tính, mà là
dành cho các thí nghiệm tƣởng tƣợng để tìm hiểu về các giới hạn của việc tính toán trên máy móc. Các máy
Turing đã đƣợc Alan Turing trình bày vào năm 1936.
9

Yiannis N. Moschovakis (2001) đã cho rằng: Khi các thuật toán đƣợc định nghĩa
một cách chính xác (rigorously) thì chúng đƣợc nhận ra bởi một máy trừu tượng, là
mô hình Toán học của máy tính, đôi khi đƣợc lí tƣởng hóa bằng cách thêm vào một
“bộ nhớ không giới hạn”. Yiannis đã trình bày định nghĩa thuật toán theo cách đệ
qui (recursive definitions) để giao cho mô hình máy thực hiện sự cài đặt
(implementations), mô hình này cũng đƣợc xem là một kiểu của thuật toán
1
. Tuy
nhiên, định nghĩa thuật toán của Yiamis, cũng nhƣ của nhiều nhà Toán học thuần
túy, vẫn là một định nghĩa hết sức Toán học, khó hiểu và có một khoảng cách xa so
với một định nghĩa thuật toán mà sự mô tả nó tiệm cận với sự cài đặt trên các máy
tính để thực hiện.
Andreas R. Blass & Yuri Gurevichz (2003) đã mô tả về quá trình “truy tìm” để
hiểu và định nghĩa khái niệm thuật toán, bắt đầu với luận đề Church – Turing, rồi
giới thiệu một số các cách tiếp cận tƣơng phản với Church và Turing và cuối cùng
là một số khám phá mới nhƣ hình thức hóa các khái niệm thuật toán tuần tự
(sequential algorithms), thuật toán song song (parallel algorithms) và thuật toán
phân tán (distributed algorithms). Andreas và Yuri cho biết có những bằng chứng
thực nghiệm không ủng hộ luận đề Church-Turing và các tác giả cho rằng luận đề

Với quan điểm trên, Kolmogorov đã đề xuất một mô hình tính toán mới và cùng
với Vladimir A. Uspensky, mô hình này đƣợc phát triển thành một mô hình tổng
quát hơn cho máy Turing và khắc phục những hạn chế của máy Turing nguyên gốc.
Kết luận 1
- Thuật toán là một khái niệm có nguồn gốc từ Toán học và đƣợc hình thành từ
định nghĩa trực giác đến định nghĩa hình thức một cách chính xác.
- Máy Turing đƣợc xem là một định nghĩa hình thức cho khái niệm thuật toán,
có thể đƣợc trình bày dƣới dạng trực quan hoặc Toán học hình thức, nhƣng
khá dài dòng và phức tạp.
- Hầu hết các định nghĩa hình thức và chính xác hiện nay về khái niệm thuật
toán đều tƣơng đƣơng với nhau và cùng xuất phát từ luận đề Church – Turing
hoặc mô hình máy Kolmogorov.
1.1.3. Khái niệm thuật toán trong Khoa học máy tính
Robert Sedgewick (1946) đã gián tiếp đề cập đến khái niệm thuật toán ở góc độ
lập trình nhƣ sau: "Khi viết một chƣơng trình máy tính, ta thƣờng cài đặt một
phƣơng pháp đã đƣợc nghĩ ra trƣớc đó để giải quyết một vấn đề. Phƣơng pháp này
thƣờng độc lập với một máy tính cụ thể sẽ đƣợc dùng, nó hầu nhƣ thích hợp nhƣ
nhau cho nhiều máy tính". Từ "thuật toán" được dùng trong Khoa học máy tính để
mô tả một phương pháp giải bài toán thích hợp cho việc cài đặt như là các chương
trình máy tính
1
. Thuật toán là "chất liệu" ("stuff") của Khoa học máy tính: chúng là
đối tượng nghiên cứu trung tâm trong nhiều, nếu không nói là hầu hết, các lĩnh vực
của Tin học". Quan điểm về thuật toán của Robert không đi ngƣợc lại các định
nghĩa hình thức đúng đắn về thuật toán nhƣ đã đề cập trên đây, và cũng giống nhƣ
các nhà Khoa học máy tính khác, Robert lƣợc bỏ các thuật ngữ phức tạp của Toán
học, để lột tả một cách dễ hiểu rằng một thuật toán một khi nó đƣợc mô tả bởi một
ngƣời làm về Khoa học máy tính thì nó phải đủ gần gũi tựa nhƣ giả mã (pseudo
code), cũng nhƣ đủ độ dễ chuyển đổi sang một mã nguồn (source code) nào đó
không phụ thuộc vào phần cứng máy tính.

quan và hƣớng đến đối tƣợng “hiểu đƣợc”, đồng thời có khả năng “thực hiện đƣợc”
thuật toán. Steven C. Althoen & Robert J. Bumcrot (1988) đã đƣa ra một định nghĩa
khá đơn giản: "Một thuật toán là một danh sách các bước chỉ dẫn để giải quyết một
bài toán cụ thể‖
2
. Ví dụ, công thức làm bánh bao từ bột yến mạch là một thuật toán
đơn sơ, là bản đồ chỉ đƣờng". Ngƣợc lại, Leonard Soicher & Franco Vivaldi (2004)
đã đƣa ra định nghĩa một cách thận trọng nhƣ sau: “Một cách không chính thức, một
thuật toán là một dãy xác định các chỉ dẫn rõ ràng để thực hiện một nhiệm vụ cụ
thể”
3
. Karlheinz Essl (2007), ngƣời sáng tạo phƣơng pháp “Soạn nhạc theo thuật
toán” (“Algorithmic Compositon”), đã định nghĩa thuật toán nhƣ sau: “Một thuật
toán có thể được định nghĩa như là một tập xác định trước các chỉ dẫn để giải quyết 1
Nguyên bản: An algorithm is a precisely-defined sequence of rules telling how to produce specified
output information from given input information in a finite number of steps.
2
Nguyên bản: An algorithm is a step-by-step list of instructions for solving a particular problem.
3
Nguyên bản: Informally, an algorithm is a finite sequence of unambiguous instructions to perform a
specific task.
12

một vấn đề cụ thể trong một số giới hạn các bước. Thuật toán có thể thay đổi từ một
dãy các phép toán số học đơn giản đến sự kết hợp các thủ tục phức tạp hơn, sử
dụng nhiều chỉ dẫn hơn từ Khoa học máy tính như dựa trên nguyên tắc ngữ pháp,
đệ quy và suy luận xác suất.”

và ngôn ngữ lập trình. 1
Nguyên bản: An algorithm can be defined as a predetermined set of instructions for solving a specific
problem in a limited number of steps. Algorithms can range from a mere succession of simple arithmetical
operations to more complex combinations of procedures, utilising more involved constructions from
computer science such as rule-based grammars, recursion and probabilistic inference.
2
Nguyên bản: In mathematic and computer science, algorithm mean finite, ordered sequence of clearly
defined actions, needed to perform some task.
3
Nguyên bản: An algorithm is a sequence of well-defined instructions for completing a task or solving a problem. It
can be described in a natural language, pseudocode, a flowchart, or even a programming language.
4
Nguyên bản: When we say that mathematics is algorithmic in nature, we do not mean that we have an algorithm to
do mathematics. Instead, we want to say that the principles and techniques that have been developed to formulate and
solve algorithmic problems can be used to solve many mathematical problems.
5
Nguyên bản: An algorithm is a finite sequence of instructions that can be systematically executed in the solution of
a given problem.
13

- Một thuật toán không đƣợc xem là một lời bài toán bao gồm cả việc chứng
minh tính đúng đắn của lời giải. Nói cách khác, có thể xem thuật toán là một
lời giải tóm tắt cho một bài toán, lƣợc bỏ đi rất nhiều các giải thích chi tiết.
1.1.4. Khái niệm thuật toán đƣợc dạy ở trƣờng phổ thông
Luận án cho rằng khái niệm thuật toán đƣợc phát biểu trong Tin học lớp 10 -
SGK (2006) đảm bảo đƣợc sự chính xác tuyệt đối. Định nghĩa thuật toán đƣợc dựa
trên khái niệm bài toán trong Tin học, cụ thể nhƣ sau:

thao tác được sắp xếp theo một trình tự nhất định sao cho khi thực hiện dãy thao
tác ấy, từ Input (là dữ liệu vào của bài toán), ta nhận được output (là dữ liệu ra của
bài toán) cần tìm".
Định nghĩa trên đây nhấn mạnh dãy “thao tác” phải đảm bảo hai tính chất: (1)
tính hữu hạn để đảm bảo thuật toán phải dừng lại sau một số bƣớc thực hiện, và (2)
tính có qui tắc để đảm bảo các chỉ dẫn (các thao tác) trong thuật toán đƣợc viết theo
một qui định nhất quán về cách mô tả, biểu diễn chúng.
Định nghĩa về thuật toán đƣợc nêu trên đây hàm ý nhấn mạnh việc chỉ ra một qui
trình rõ ràng và chính xác để tìm ra kết quả (output) từ dữ liệu vào (input) của bài
toán. Định nghĩa này còn ngụ ý thuật toán không bị đòi hỏi phải giải quyết các yêu
cầu định tính của các bài toán trong Toán học (ví dụ nhƣ chứng minh sự tồn tại hay