Tạp chí Thông tin toán học - Tập 6 Số 2 Tháng 8 Năm 2002

 2T(k) + 1 
 = .)( 121122 1 −=+− +kk 
Nh− vậy dự đoán là đúng cho mọi n. 
 Thế là độ phức tạp tính toán của thuật 
toán đệ quy giải bài toán là hàm mũ và cho 
đến hiện nay ch−a có thuật toán nào tốt 
hơn. Vì vậy bài toán Tháp Hà Nội hiện là 
một bài toán bất trị. Để minh hoạ tính “ 
bất trị “ của bài toán, ta hãy xét chẳng hạn 
n = 64. Ta hãy nhớ lại bài toán cổ về phần 
th−ởng giành cho ng−ời phát minh ra cờ 
t−ớng: tục truyền rằng để th−ởng công cho 
ng−ời phát minh ra cờ t−ớng, nhà vua cho 
phép nhà phát minh tự chọn lấy phần 
th−ởng cho mình. Nhà phát minh khiêm 
tốn đề nghị: xin đặt 1 hạt lúa vào ô thứ 
nhất của bàn cờ, ô thứ hai đặt gấp đôi lên 
tức là 2 hạt, rồi ô thứ ba lại gấp đôi lên, tức 
là 4 hạt, v... v... cho đến ô thứ 64 thì dừng. 
Tổng số thóc có trên bàn cờ chính là phần 
th−ởng nhà phát minh muốn nhận. Nhà 
vua vui vẻ đồng ý, nh−ng đến lúc thực hiện 
mới vỡ lẽ ra là tất cả các kho thóc của nhà 
vua cộng lại vẫn không đủ. Tính ra, số 
thóc này bằng: 
12 222 1 646321 −=++++= ......S 
hạt. Nếu đem trải đều số thóc này lên mặt 
đất, ta sẽ đ−ợc một lớp thóc bao phủ toàn 
bộ bề mặt trái đất và dầy đến hàng th−ớc! 
Vậy mà số lần chuyển đĩa trong bài toán 
Tháp Hà Nội với 64 đĩa lại bằng chính số 
thóc này! 
Bây giờ giả sử mỗi lần chuyển 1 đĩa từ cọc 
này sang cọc kia mất 1 giây. Khi đó thời 
gian thực hiện bài toán Tháp Hà Nội với n 
= 64 sẽ bằng: 
50 12 164 6464 ≈−=ì= gygyTt )()( 
tỷ năm. Nếu dùng một máy tính có tốc độ 
1 triệu phép toán/giây, thì thời gian chạy 
máy sẽ bằng : 
năm000.50 
 )12( 
10
1)64( 
61064
6
'
64
≈
−=ì= − gygyTt
Thật đúng là “đồ bất trị“! 
Trở lại với thuật toán đệ quy, ta thấy t− 
duy đệ quy rất ngắn gọn, hiệu quả. Nh−ng 
vấn đề khó là tạo ra đ−ợc các phần mềm 
tin học “hiểu” và “thực thi“ đ−ợc các thuật 
toán đệ quy. Chỉ có các ngôn ngữ lập trình 
cận đại từ Pascal và C trở lên mới có khả 
năng này. Sau đây là một ch−ơng trình đệ 
quy giải bài toán tháp Hà nội, viết bằng 
ngôn ngữ Pascal: 
PROGRAM TOWER_HANOI 
Var 
 n: integer; 
PROCEDURE HANOI (n, c1, c2, c3: 
integer); 
 BEGIN 
 12
 IF n = 1 THEN WRITE LN(c1, ‘ → 
‘, c2) 
 ELSE 
 BEGIN 
 HANOI (n-1, c1, c3, c2); 
 HANOI (1, c1, c2, c3); 
 HANOI (n-1, c3, c2, c1); 
 END; 
 END; 
 ------------------------------------------------ 
 BEGIN 
 WRITE (‘n = ‘); READ LN (n); 
 CALL HANOI (n, 1, 2, 3); 
 END. 
Ch−ơng trình thật đơn giản, trong sáng 
và ngắn gọn đến bất ngờ ! 
Bạn hãy chạy ch−ơng trình, chẳng hạn với 
n = 4, sau T(4) = 15124 =− b−ớc sẽ cho 
ra kết quả sau đây: 
1 → 3 2 → 3 2 → 1 
 1 → 2 1 → 3 3 → 2 
 3 → 2 1 → 2 1 → 3 
1 → 3 3 → 2 1 → 2 
 2 → 1 3 → 1 3 → 2 
 Bài toán tháp Hà Nội thực là một bài 
toán hóc búa! Nguyễn Xuân Tấn* đã viết 
nh− vậy ở cuối bài viết của mình. Nh−ng 
cũng chính xuất phát từ một loạt các bài 
toán hóc búa nh− vậy, trong đó có bài toán 
Tháp Hà Nội, một lý thuyết mới đã nẩy 
sinh và phát triển ở biên giới của toán học 
và tin học, đó là lý thuyết Độ phức tạp tính 
toán. Ng−ợc lại, từ những thành tựu của lý 
thuyết Độ phức tạp tính toán nhìn lại bài 
toán Tháp Hà Nội, ta cảm thấy yên tâm vì 
đã lý giải đ−ợc bản chất "tính hóc búa " 
của bài toán là nằm ở tính đệ quy và tính 
bất trị của bài toán. 
---------------------------- 
* Nguyễn Xuân Tấn, Bài toán Tháp Hà Nội, 
một bài toán đố hóc búa hơn một trăm năm 
nay, TT Toán học, Tập 6, số 1(2002) 2-4. 
 T nhanh T chậm 
(ε, c là các hằng số, với 0 < ε < 1 < c) 
(Hình 2) 
Bảng 3 
lg2n n nlg2n n
2 n3 2n 
0 1 0 1 1 2 
1 2 2 4 8 4 
2 4 8 16 64 16 
3 8 24 64 512 256 
4 16 64 256 4096 65536 
5 32 160 1024 32768 2147483648
nccnnncnncnnnnc loglogloglog ε
 13
Danh sách các nghiên cứu sinh 
 bảo vệ trong n−ớc đến tháng 8/2001 
 Đã đ−ợc cấp bằng tiến sĩ 
vào tháng 9 và tháng 12/2001 
Tt Họ và tên NCS 
Cơ quan công tác 
Ngày bảo vệ 
Cơ sở đào tạo 
Tên đề tài luận án 
Chuyên ngành 
Ng−ời h−ớng 
dẫn khoa học 
1 
Nguyễn Ngọc Anh 
ĐHSP HN 2 
20/12/2000 
Viện KHGD 
ứng dụng phép tính vi phân 
(phần đạo hàm) để giải các 
bài tập cực trị có nội dung 
liên môn và thực tế trong 
dạy toán lớp 12 trung học 
phổ thông. 
5.07.02 - Ph−ơng pháp giảng 
dạy toán 
PGS. TS. Ngô 
Hữu Dũng và 
PGS. TS. Trần 
Kiều 
2 
Đinh Thanh Đức 
ĐHSP Quy Nhơn 
30/11/2000 
Viện Toán học 
Một số vấn đề của lí thuyết 
biến đổi tích phân. 
1.01.07 - Toán học tính toán 
PGS. TSKH. Vũ 
Kim Tuấn 
3 
Nguyễn Lan 
Ph−ơng 
CĐSP Phú Thọ 
28/12/2000 
Viện KHGD 
Cải tiến ph−ơng pháp dạy 
học toán với yêu cầu tích cực 
hoá hoạt động học tập theo 
h−ớng giúp học sinh phát 
hiện và giải quyết vấn đề 
(qua phần giảng dạy "Quan 
hệ vuông góc trong không 
gian" lớp 11 trung học phổ 
thông). 
5.07.02 - Ph−ơng pháp giảng 
dạy toán, 
PGS. TS. Trần 
Kiều 
3 
Phạm Hữu Anh 
Ngọc 
ĐHSP - Đại học 
Huế 
28/02/2001 
Viện Toán học 
Một số bài toán về tính ổn 
định vững của các hệ động 
lực. 
1.01.01 - Toán giải tích 
GS. TSKH. 
Nguyễn Khoa 
Sơn và 
TS. Tr−ơng 
Xuân Đức Hà 
4 
Nguyễn Văn Toản 
ĐH Khoa học - Đại 
học Huế 
15/03/2001 
Viện Toán học 
Về dáng điệu tiệm cận của 
−ớc l−ợng Boostrap với cỡ 
mẫu ngẫu nhiên. 
1.01.04 - Lí thuyết xác suất 
và thống kê toán học 
GS. TS. Tràn 
Mạnh Tuấn và 
TS. Trần Hùng 
Thao 
 14
5 
Trần Tín Kiệt 
ĐHSP Quy Nhơn 
19/01/2001 
Viện Toán học 
Một số tính chất định tính 
các hệ động lực vô hạn 
chiều. 
1.01.01 - Toán giải tích 
PGS. TSKH. Vũ 
Ngọc Phát, và 
PGS. TS. Phan 
Huy Khải 
6 
Phạm Quang Trung 
Viện Kiểm sát nhân 
dân tối cao 
27/02/2001 
Đại học Bách 
khoa Hà Nội 
Thiết kế và cài đặt hệ cơ sở 
dữ liệu trên cơ sở phân tích 
và chuẩn hoá. 
1.01.10 - Đảm bảo toán học 
cho máy tính và hệ thống 
tính toán. 
PGS. TS. 
Nguyễn Xuân 
Huy và 
PGS. TS. Đỗ 
Xuân Lôi 
7 
Mai Quý Năm 
ĐHSP Quy Nhơn 
23/02/2001 
ĐHSPHN 
Về CS-mô đun và một số 
ứng dụng vào khảo sát cấu 
trúc vành. 
1.01.03 - Đại số và lí thuyết 
số 
GS. TSKH. Đinh 
Văn Huỳnh và 
TS. Nguyễn 
Tiến Quang 
8 
Nguyễn Ngọc Hải 
ĐHSP - Đại học 
Huế 
24/04/2001 
Viện Toán học 
Một số tính chất của hàm γ-
lồi và γ-d−ới vi phân. 
1.01.01 - Toán giải tích 
GS. TS. Hoàng 
Xuân Phú 
9 
Trần Tuấn Nam 
Tr−ờng Dự bị đại 
học dân tộc TW 
Nha Trang 
05/04/2001 
Viện Toán học 
Về đồng điều địa ph−ơng 
của compăc tuyến tính. 
1.01.03 - Đại số và lí thuyết 
số 
PGS. TSKH. 
Nguyễn Tự 
C−ờng 
10 
Phan Nhật Tĩnh 
ĐH Khoa học - Đại 
học Huế 
10/04/2001 
Viện Toán học 
Hàm vectơ lồi và một số ứng 
dụng. 
1.01.09 - Vận trù học 
PGS. TSKH. 
Nguyễn Xuân 
Tấn, và 
PGS. TSKH. 
Đinh Thế Lục 
11 
Lê Thị Thanh Nhàn 
ĐHSP - Đại học 
Thái Nguyên 
22/05/2001 
Viện Toán học 
Về cấu trúc một số lớp 
môđun compắc tuyến tính 
trên vành giao hoán. 
1.01.03 - Đại số và lí thuyết 
số 
PGS. TSKH. 
Nguyễn Tự 
C−ờng 
12 
Phạm Ngọc Bội 
ĐHSP Vinh 
28/04/2001 
ĐHSP Vinh 
Về sự tiệm cận của nghiệm 
ph−ơng trình vi phân tuyến 
tính và ph−ơng trình sai phân 
tuyến tính trong không gian 
Banach. 
1.01.01 - Toán giải tích 
PGS. TS. 
Nguyễn Thế 
Hoàn và 
 GS. TSKH. 
Trần Văn 
Nhung 
13 
Nguyễn Đình Bình 
ĐH Bách khoa HN 
23/04/2001 
ĐH Bách khoa 
HN 
Một số bài toán biên tự do 
ẩn đối với ph−ơng trình 
truyền nhiệt. 
1.01.02 - Ph−ơng trình vi 
GS. TS. Nguyễn 
Đình Trí và 
TS. Phan Hữu 
Sắn 
 15
phân và tích phân 
14 
Nguyễn Thị Bạch 
Kim 
Viện Khoa học thuỷ 
lợi 
10/05/2001 
Viện Toán học 
Ph−ơng pháp nón pháp tuyến 
và bài toán quy hoạch tuyến 
tính đa mục tiêu. 
1.01.09 - Vận trù học 
PGS. TSKH. 
Đinh Thế Lục 
và PGS. TSKH. 
Lê Dũng M−u 
15 
Trần Thị Lan Anh 
Viện Toán học 
08/05/2001 
Viện Toán học 
Điểm bất động chung của 
các ánh xạ và ứng dụng. 
1.01.07 - Toán học tính toán 
GS. TSKH. 
Nguyễn Minh 
Ch−ơng 
16 
Trần Việt H−ng 
Cty Điện toán và 
truyền số liệu B−u 
điện 
04/06/2001 
ĐH Bách khoa 
Hà Nội 
Nghiên cứu đánh giá độ tin 
cậy mạng và thể nghiệm trên 
mạng truyền số liệu quốc 
gia. 
1.01.07 - Toán học tính toán 
PGS. TS. 
Nguyễn Thúc 
Hải 
17 
Phùng Văn ổn 
ĐH Hàng hải 
18/05/2001 
ĐH Khoa học tự 
nhiên - 
ĐHQGHN 
Nghiên cứu một số lớp siêu 
ngôn ngữ. 
1.01.10 - Đảm bảo toán học 
cho máy tính và hệ thống 
tính toán 
PGS. TS. Đặng 
Huy Ruận 
18 
Tạ Thị Hoài An 
ĐHSP Vinh 
19/6/2001 
ĐHSP Vinh 
Về tập xác định duy nhất và 
đa thức duy nhất cho các 
hàm phân hình. 
1.01.03 - Đại số và lí thuyết 
số 
GS. TSKH. Hà 
Huy Khoái 
19 
Nguyễn Tấn Hoà 
CĐSP Gia Lai 
02/07/2001 
ĐHKH tự nhiên 
-ĐHQG Hà Nội 
Một số vấn đề về đặc tr−ng 
hoá các ph−ơng trình tích 
phân kì dị. 
1.01.01 - Toán giải tích 
GS. TSKH. 
Nguyễn Văn 
Mậu 
20 
Nguyễn Thị Hồng 
Minh 
ĐHKH tự nhiên - 
ĐHQG Hà Nội 
29/8/2001 
ĐHKH tự nhiên 
- ĐHQG Hà Nội
Một số thuật toán giải số hệ 
ph−ơng trình vi phân trên 
siêu máy tính. 
1.01.10 - Đảm báo toán học 
cho máy tính và hệ thống 
tính toán 
PGS. TSKH. 
Nguyễn Hữu 
Công 
 16
Thông báo hội nghị 
INTERNATIONAL CONFERENCE ON HIGH PERFORMANCE 
 SCIENTIFIC COMPUTING 
Modelling, Simulation and Optimization of Complex 
Processes 
March 10-14, 2003, Institute of Mathematics, NCST, Hanoi 
TOPICS: 
• mathematical modelling 
• numerical simulation 
• methods for optimization and control 
• parallel computing: architectures, algorithms, 
 tools, environment 
• symbolic computing 
• software development 
• applications of scientific computing in: 
 - physics, mechanics, chemistry, and biology 
 - environmental and hydrology problems 
 - transport, logistics and site location 
 - communication networks, production 
 scheduling 
 - industrial and commercial problems 
The conference is organized jointly by: 
• Institute of Mathematics, Vietnam NCST 
• SFB 359 "Reactive Flows, Transport and 
 Diffusion", Heidelberg 
• Ho Chi Minh City University of Technology 
• Interdisciplinary Center for Scientific 
 Computing