TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
KHOA MẠNG MÁY TÍNH & TRUYỀN THÔNG


BÁO CÁO ĐỀ TÀI
Bộ môn: PP luận sáng tạo khoa học và công nghệ

Đề tài : PHƯƠNG PHÁP SÁNG TẠO TRONG KHOA HỌC KĨ
THUẬT VÀ ỨNG DỤNG TRONG TIN HỌC
Sinh viên thực hiện: PHAN XUÂN HÙNG.
MSSV : 06520191
Lớp : MMT01
GVHD: GS-TSKH : HOÀNG VĂN KIẾM
1

TpHCM, 01-2010
PHỤ LỤC:
CHƯƠNG I:GIỚI THIỆU.
1. Khoa học sáng tạo
2. Phương pháp luận Sáng tạo là gì?
3. Một vài đặc điểm của tư duy sáng tạo
CHƯƠNG II:CÁC PHƯƠNG PHÁP SÁNG TẠO CƠ BẢN.
1. Giới thiệu kỹ thuật tư duy 5W1H
2. Phương pháp giản đồ.
CHƯƠNG III: PHƯƠNG PHÁP RÈN LUYỆN TƯ DUY QUA CÁC
BÀI TOÁN
1. Suy nghĩ trước khi nhìn giải đáp.:
2. Nghĩ sáng tạo xa hơn
3. Ứng dụng của nghĩ sáng tạo
4. Những phẩm chất của một người nghĩ sáng tạo
5. Bạn có thể học để nghĩ sáng tạo

Cùng với cuộc cách mạng KHKT, số lượng bài toán phức tạp mà loài người
cần giải quyết tăng nhanh, đồng thời yêu cầu thời gian phải giải được chúng
rút ngắn lại. Trong khi đó không thể tăng mãi phương tiện và số lượng người
tham gia giải bài toán. Thêm nữa, cho đến nay và trong tương lai khá xa sẽ
không có công cụ nào thay thế được bộ óc tư duy sáng tạo. Ngưòi ta đã nhớ
lại Ơristic và phát triển tiếp để tìm ra cách tổ chức hợp lý, nâng cao năng
suất, hiệu quả quá trình tư duy sáng tạo – quá trình suy nghĩ giải quyết vấn
đề và ra quyết định trong mọi lĩnh vực không riêng gì khoa học kỹ thuật.
Trên con đường phát triển và hoàn thiện, KHOA HỌC SÁNG TẠO
(Heuristics, Creatology) tách ra thành một khoa học riêng, trong mối tương
tác hữu cơ với các khoa học khác (có đối tượng nghiên cứu, hệ thống các
khái niệm kiến thức riêng, cách tiếp cận và phương pháp nghiên cứu
riêng…)

Một số nước tiên tiến trên thế giới đã bắt đầu đào tạo cử nhân, thạc sỹ về
chuyên ngành sáng tạo và đổi mới (BA, BS, MA, MS in Creativity and
3
Innovation). Ví dụ Trung tâm nghiên cứu sáng tạo (Center for Studies in
Creativity) thuộc Đại học Buffalo bang New York (Mỹ) đến cuối năm 1994
đã đào tạo được 100 thạc sỹ.
2. Phương pháp luận Sáng tạo là gì?
Nói một cách ngắn gọn, “PHƯƠNG PHÁP LUẬN SÁNG TẠO” (Creativity
Methodologies) là bộ môn khoa học có mục đích xây dựng và trang bị cho
mọi người hệ thống các phương pháp, các kỹ năng thực hành tiên tiến về suy
nghĩ để giải quyết vấn đề và ra quyết định một cách sáng tạo, về lâu dài, tiến
tới điều khiển được tư duy.
“PHƯƠNG PHÁP LUẬN SÁNG TẠO” là phần ứng dụng của khoa học
rộng lớn hơn, mới hình thành và phát triển trong thời gian gần đây : KHOA
HỌC SÁNG TẠO (Creatology).
Theo các nhà nghiên cứu, khoa học này ứng với “làn sóng thứ tư” trong quá

tiến bộ về y học trong lĩnh vực nghiên cứu não.
• Không có khuôn mẫu tuyệt đối: Cho đến nay vẫn không có phương
pháp vạn năng nào để khơi dậy khả năng tư duy và các tiềm năng
khổng lồ ẩn chứa trong mỗi con người. Tùy theo đặc tính của đối
tượng làm việc và môi trường tại chỗ mà mỗi cá nhân hay tập thể có
thể tìm thấy các phương pháp riêng thích hợp.
• Không cần đến các trang bị đắt tiền: Cho đến nay, các phương pháp tư
duy sáng tạo chủ yếu vẫn là các cách thức tổ chức lề lối suy nghĩ có
hướng và các dụng cụ sử dụng rất đơn giản chủ yếu là giấy, bút, phấn,
bảng, lời nói, đôi khi là màu sắc, máy chiếu hình, từ điển Một số
phần mềm đã xuất hiện trên thị trường để giúp đẩy nhanh hơn quá
trình hoạt động sáng tạo và làm việc tập thể có tổ chức và hiệu quả
hơn. Song, tại một số trường học vẫn có thể tiến hành giảng dạy bộ
môn này bằng những cuộc thảo luận chuyên đề hỗ trợ không tốn kém.
Cuối cùng, khoa này cũng không giới hạn tầm nghiên cứu của nó cho
việc ứng dụng thành tựu mới của y học về não bộ và tin học và điều
đó vẫn còn bỏ ngỏ cho các nhà nghiên cứu.
• Không phức tạp trong thực nghiệm: Thực nghiệm của hầu hết các
phưong pháp tư duy sáng tạo hiện nay rất đơn giản. Nếu cần quá trình
đào tạo cấp tốc có thể từ 1 buổi cho tới dưới 1 tuần cho người học. Đa
số các phương pháp đã đưọc ghi sẵn ra từng bước như là những thuật
toán. Điều kiện cho người thực hiện chỉ là sự hiểu biết và có khả năng
tư duy cũng như đôi khi cần đến sự hỗ trợ của các kho dữ liệu về kiến
thức chuyên môn mà vấn đề đặt ra có liên quan hay đề cập tới.
• Hiệu quả cao: Các phương pháp tư duy sáng tạo, nếu sử dụng đúng
chỗ đúng lúc đều mang lại lợi ích rất cao, nhiều giải pháp được đưa ra
chỉ nhờ vào phương pháp tập kích não. Các phương pháp khác cũng
đã hỗ trợ rất nhiều cho các nhà phát minh, nhất là trong lĩnh vực kỹ
thuật hay công nghệ.
• Giảm thiểu được áp lực quá tải của lượng thông tin: bằng các phưong

thường lúng túng vì không biết phải bắt đầu như thế nào, tiến hành ra làm
sao, tại sao chúng ta phải làm điều này, nó có ích lợi gì hay không, …?
6

5W1H viết tắt từ các từ sau:
What? (Cái gì?)
Where? (Ở đâu?)
When? (Khi nào?)
Why? (Tại sao?)
How? (Như thế nào?)
Who? (Ai?)
Để trình bày một ý tưởng, tóm tắt một sự kiện, một cuốn sách hoặc bắt đầu
nghiên cứu một vấn đề, chúng ta hãy tự đặt cho mình những câu hỏi sau:
WHAT? (Cái gì?)
- Cái đó là gì?
- Nó đề cập đến vấn đề gì?
- Kế tiếp sự kiện này, thì cái gì khác xảy ra? (What else)
- Cuốn sách này trình bày vấn đề gì?
- Bài học này trình bày vấn đề gì?
- E-learning là gì?
- Những câu hỏi phụ của vấn đề này là gì?
WHERE (Ở đâu?)
- Vấn đề trình bày nằm trong lĩnh vực nào?
- Sự kiện lịch sử này xảy ra ở địa điểm nào?
- Vấn đề này còn liên quan đến các lĩnh vực nào khác?
- Loại thảo dược này thường được trồng ở đâu?
- Bài báo này đăng trên tạp chí nào?
- Tìm hiểu kiến thức về việc ứng dụng ICT trong dạy học ở đâu?
7
- Bài thuyết trình này sẽ được trình bày trong nhóm hay trước lớp?

- Ai sẽ hưởng lợi khi dự án này được tiến hành? Còn ai khác không? (Who
else)
- Ai là tác giả của cuốn sách đang làm dư luận xôn xao?
- Chính sách này của nhà nước hướng đến đối tượng nào?
8
Công cụ 5W1H thoạt nhìn rất đơn giản nhưng lại tỏ ra rất hiệu quả nếu
chúng ta sử dụng nó đúng đắn, khéo léo và thông minh.
Ví dụ về việc sử dụng công cụ 5W1H trong thực tiễn
Tác giả T.T.H – một người làm việc cho CENTEA – cho biết đã sử dụng
công cụ 5W1H để thực hiện bài viết thú vị “Học cách Tư duy tích cực”.
Sau đây là các phân tích của anh ta với công cụ 5W1H để thực hiện bài viết
thú vị và hữu ích trên:
WHAT: Bài viết sẽ đề cập đến vấn đề gì?
- Bài viết đề cập đến kỹ năng tư duy tích cực, nêu lên được một phác thảo sơ
lược: Tư duy tích cực là gì?
-> Sự ra đời của phần 1 của bài viết: Tư duy tích cực là gì?
WHERE: Bài viết sẽ được đăng tải ở đâu? Tài liệu tìm từ đâu?
- Bài viết sẽ được đăng tải trên website giaovien.net. Tài liệu được tìm kiếm
trên mạng thông tin Internet (phần Nguồn tham khảo ở cuối bài viết)
WHEN: Khi nào bài viết được đăng?
- Sau khi bài viết đã được kiểm tra các lỗi chính tả bởi CENTEA và duyệt
toàn bộ nội dung bài.
WHY: Tại sao phải thực hiện bài viết này? Tại sao phải tư duy tích cực?
- Vì mong muốn cung cấp đến cộng đồng giáo viên những kiến thức về các
kỹ năng sống, mà tư duy tích cực là một trong những kỹ năng có vai trò
quan trọng trong việc phòng tránh và giảm stress, cân bằng công việc và
cuộc sống, phát triển sức mạnh tinh thần.
- Để trả lời câu hỏi “Tại sao phải tư duy tích cực?”, bài viết cần đưa ra các
yếu tố thuyết phục người đọc về lợi ích của tư duy tích cực để thuyết phục
họ về tầm quan trọng của kỹ năng này. -> Sự ra đời của phần 2 của bài viết:

They taught me all I knew
Their names are What and Where and When
And How and Why and Who.
Tạm dịch:
Tôi có 6 người đầy tớ trai trung thực
Họ đã dạy cho tôi biết mọi thứ
Tên của họ là What và Where và When
Và How và Why và Who.
10
2.Phương pháp giản đồ.
Phương pháp tư duy sáng tạo Giản đồ là phương cách rất hữu hiệu để ghi
nhớ một sự kiện hay hệ thống phức tạp.Đây là một phương tiện mạnh để tận
dụng khả năng ghi nhận hình ảnh của bộ não. Nó có thể dùng như một cách
để ghi nhớ chi tiết, để tổng hợp hay để phân tích một vấn đề thành một dạng
của lược đồ phân nhánh. Phương pháp này củng cố thêm khả năng liên lạc,
liên hệ các dữ kiện với nhau cũng như nâng cao khả năng nhớ theo chuỗi dữ
kiện xảy ra theo thời gian. Bằng cách dùng giản đồ ý, tổng thể của vấn đề
được chỉ ra dưới dạng một hình trong đó các đối tượng được liên hệ với
nhau bằng các đường nối. Với cách thức đó, các dữ liệu được ghi nhớ và
nhìn nhận dễ dàng và nhanh chóng hơn.Phương pháp này nâng cao cách ghi
chép. Bằng cách dùng giả đồ ý, tổng thể các vấn đề được chỉ ra dưới dạng
một hình trong đó các đôi tượng được liên he với nhau bằng các đường
nối.Với cách thức đó, các dữ liệu được ghi nhận và nhìn nhận dễ dàng và
nhanh chóng hơn.Thay vì dùng chữ viết để mô tả (một chiều) giản đồ ý sẽ
phơi bày câú trúc một đối tượng bằng hình ảnh hai chiều. Nó chỉ ra "dạng
thức" của đôí tượng, sự quan hệ tương hỗ giữa các khái niệm liên
quan và cách liên he giữa chúng với nhau bên trong của một vấn đề lớn.
Gỉan đồ ý đơn giản hóa cho việc nhớ các dạng câu hỏi: Ai?; cái gì?; thế
nào?; tại sao?; ở dâu?; khi nào?, … Khi xây dựng một giản đồ ý cần tuân
theo các bước sau:

3.BUS
4.Các bộ điều khiển I/O
12
5.Bộ điều khiển video
6.Cổng nối tiếp
7.USB
8.Ổ điã
9. Ổ CD
10.Màn hình
11.NIC
12.Cổng song song
13.Bàn phím
14.Chuột
15.Máy in
16.Mạng
17.Máy quét hình
18.Máy chụp hình số
19.Máy phóng hình
CHƯƠNG III:
PHƯƠNG PHÁP RÈN LUYỆN TƯ DUY QUA CÁC BÀI TOÁN
1. Suy nghĩ trước khi nhìn giải đáp.:

Câu 1: Jack được trả 5 đôla cho một lần cưa khúc gỗ ra làm đôi. Vậy
Jack được trả bao nhiêu tiền để cưa khúc gỗ ra làm bốn?".
Câu 2:Có 2 người ngồi trước cửa siêu thị và chơi cờ tướng. Họ chơi 5
ván. Mỗi người đều thắng 3 ván. Sao lại thế?".
Đây là giải đáp
Câu 1: 15 đôla, vì để cưa khúc gỗ ra làm đôi thì chỉ cần một lần cưa,
nhưng để cưa một khúc gỗ ra làm 4 thì cần 3 lần.
Câu 2: Bởi vì 2 người này chơi với 2 người khác nhau.

5^2 - 2.5.9/ 2 = 4^2 - 2.4.9/2
Cộng cả 2 vế với (9/2)^2 để xuất hiện hằng đẳng thức :
5^2 - 2.5.9/2 + (9/2)^2 = 4^2 - 2.4.9/2 + (9/2)^2
(5 - 9/2)^2 = (4 - 9/2 )^2
5 - 9/2 = 4 - 9/2
5 = 4
Câu 8: Hai người đào trong hai giờ thì được một cái hố. Vậy hỏi một
người đào trong một giờ thì được mấy cái hố?
Trả Lời: 1 cái hố (nhỏ hơn).
Câu 9: Bên trái đường có một căn nhà xanh, bên phải đường có một
căn nhà đỏ. Vậy, nhà trắng ở đâu ?
Trả Lời: Ở Mỹ.
Câu 10: Có một cây cầu có trọng tải là 10 tấn, có nghĩa là nếu vượt
quá trọng tải trên 10 tấn thì cây cầu sẽ sập. Có một chiếc xe tải chở
hàng, tổng trọng tải của xe 8 tấn + hàng 4 tấn = 12 tấn. Vậy đố các
14
bạn làm sao bác tài qua được cây cầu này (Không được bớt hàng ra
khỏi xe)?
Trả Lời: Bác tài cứ đi qua thôi, còn xe thì ở lại. 4
2. Nghĩ sáng tạo xa hơn
Những câu chuyện về nghĩ sáng tạo không phải chờ đến thời kỹ thuật hiện
đại. Từ những năm 1400, Nữ hoàng Isabella của Tây Ban Nha có lần yêu
cầu mọi người tìm cách để quả trứng đứng thẳng trên một đầu của nó, mà
không được dùng cái đế gì kê ở dưới.
Tất cả các vị quan trong triều đình đều vò đầu bứt tóc chịu thua. Nhưng rồi
một thuỷ thủ trẻ bước đến, đập vỡ một đầu của quả trứng và dựng nó lên
bằng đầu đó. Tất nhiên, ruột trứng chảy hết ra và các quan thì vô cùng tức
giận. Nhưng Nữ hoàng thì không. Nữ hoàng chưa bao giờ nói rằng không
được đập vỡ trứng, còn các quan đã nghĩ "mặc định" là như thế.
Và Christopher Columbus - một thuỷ thủ - bằng cách nghĩ ra bên ngoài

- Nồng nhiệt.
- Không gò bó.
- Thích phiêu lưu.
- Tò mò, hiếu kỳ.
- Nhiều sở thích.
- Hài hước.
- Trẻ con, hiếu động.
- Biết nghi ngờ.
Thực tế cuộc sống không phải là một cái hộp, nên bạn đừng tự tạo ra rồi chui
vào đó!
5. Bạn có thể học để nghĩ sáng tạo
Ai trong chúng ta cũng có sự sáng tạo, và tin tốt là nếu bạn thấy mình "chưa"
(chứ không phải là "không") sáng tạo, bạn có thể học. Công việc càng khó
thì não bạn hoạt động càng tích cực. Theo nghiên cứu thì đến thiên tài cũng
mới sử dụng có 15% hiệu suất não của mình! Cho nên, học nghĩ sáng tạo để
não bạn đi xa hơn là hoàn toàn có thể. Thậm chí, có rất nhiều gợi ý cho cách
học nghĩ sáng tạo.
a. Phương pháp SAEDI - "SAEDI" không phải là từ gì quái dị, nó là từ
"IDEAS" viết lộn ngược. à?ôi khi, nghĩ sáng tạo chỉ cần bạn nhìn mọi thứ
theo chiều khác đi.
S = State of mind (cách suy nghĩ): Tự nói rằng "Tôi chẳng sáng tạo chút
nào" hoặc "Tôi chẳng bao giờ có ý tưởng gì hay ho đâu" sẽ huỷ hoại sức
sáng tạo của bạn. Nghĩ sáng tạo đòi hỏi nghĩ tích cực.
A = Atmosphere (không khí). Có những người thích ở nơi đông người mới
nghĩ ra nhiều thứ. Có những người lại phải ngồi một mình yên tĩnh mới sáng
suốt được. Bạn hãy tạo cho căn phòng mình có không khí tuỳ theo sở thích.
Nếu bạn có nhiều ý tưởng khi đang đi, hãy chăm đi dạo ở công viên, bờ
hồ Trang trí phòng bạn bằng những bức ảnh, ánh sáng mà bạn thích.
16
E = Effective thinking (Nghĩ hiệu quả). Nghĩ hiệu quả tức là hướng suy nghĩ

Sổ sửa lỗi chính tả; Sổ hình tròn; Sổ có thể dán giấy lên mà không cần hồ
dán; Sổ có thể dịch từ tiếng Việt sang tiếng Anh
7.Nâng cao khả năng sáng tạo:
Để nâng cao khả năng sáng tạo, cần có phương pháp rèn luyện. Đó là:
17
. Phương pháp đặt vấn đề:
Trước tiên, các bạn liệt kê toàn bộ những chi tiết có vấn đề thành một bảng
kê. Sau đó lần lượt suy nghĩ từng vấn đề. Làm như vậy chúng ta sẽ tránh
được kiểu xem xét sự vật phiến diện hoặc bỏ sót cá chi tiết quan trọng. Tuy
vậy, cũng không nên quá lệ thuộc vào phương pháp nạy vì quá lệ thuộc vào
nó sẽ làm hạn chế tính sáng tạo.
. Phương pháp liên tưởng đôi
Mục đích rèn luyện của phương pháp này cũng giống như phương pháp đặt
vấn đề, giúp ta vượt qua các liên tưởng thông thường
Ví dụ: Cần sáng chế một sản phẩm mới về âm thanh nổi. Trước tiên, người
ta liên tưởng tới một sản phẩm hoàn toàn không liên quan dến nó – máy bay.
Sau đó ta xem xét đặc tính, công dụng, trang bị của máy bay.
Căn cứ vào những yếu tố đó ta lại lần lượt xét các yếu tố đó với sản phẩm về
âm thanh nổi.
Phương pháp này không những giúp ta nghiên cứu sáng chế sản phẩm mới
mà còn rèn luyện tính sáng tạo trong cuộc sống hàng ngày của chúng ta.
. Phương pháp phân tích hình thái:
Ví dụ: Muón làm một cái ly để đông dung dịch chúng ta cần xem xét hình
dáng, kích thước, nguyên liệu của ly. Người ta lập một biểu đồ khối lập
phương để lựa chọn điều kiện tối ưu. Có 48 trường hợp để lựa chọn, giúp
chúng ta có những dữ liệu để sáng chế một sản phẩm mới đạt tiêu chuẩn cao.
Ba phương pháp trên nhằm hạn chế sự lão hoá của bộ não nhưng đối với
việc rèn luyện tư duy lại không có hiệu quả bao nhiêu.
Theo kinh nghiệm những người có sức sáng tạo phong phú thường là những
người rất thích thú với các trò chơi về bộ não như: câu đố, tiểu thuyết suy

Nói cách khác, thuật toán là một bộ các qui tắc hay qui trình cụ thể nhằm
giải quyết một vấn đề trong một số bước hữu hạn, hoặc nhằm cung cấp một
kết quả từ một tập hợp của các dữ kiện đưa vào.
Ví dụ: thuật toán để giải phương trình bậc nhất P(x): ax + b = c, (a, b, c là
các số thực), trong tập hợp các số thực có thể là một bộ các bước sau đây:
1. Nếu a = 0
o b = c thì P(x) có nghiệm bất kì
o b ≠ c thì P(c) vô nghiệm
2. Nếu a ≠ 0
o P(x) có duy nhất một nghiệm x = (c - b)/a
19
Khi một thuật toán đã hình thành thì ta không xét đến việc chứng minh thuật
toán đó mà chỉ chú trọng đến việc áp dụng các bước theo sự hướng dẫn sẽ có
kết quả đúng. Việc chứng minh tính đầy đủ và tính đúng của các thuật toán
phải được tiến hành xong trước khi có thuật toán. Nói rõ hơn, thuật toán có
thể chỉ là việc áp dụng các công thức hay qui tắc, qui trình đã được công
nhận là đúng hay đã được chứng minh về mặt toán học.
"Thuật toán" hiện nay thường được dùng để chỉ thuật toán giải quyết các vấn
đề tin học. Hầu hết các thuật toán tin học đều có thể viết thành các chương
trình máy tính mặc dù chúng thường có một vài hạn chế (vì khả năng của
máy tính và khả năng của người lập trình). Trong nhiều trường hợp, một
chương trình khi thiết kế bị thất bại là do lỗi ở các thuật toán mà người lập
trình đưa vào là không chính xác, không đầy đủ, hay không ước định được
trọn vẹn lời giải của vấn đề. Tuy nhiên cũng có một số bài toán mà hiện nay
người ta chưa tìm được lời giải triệt để, những bài toán ấy gọi là những bài
toán NP-không đầy đủ.
Một thuật toán có các tính chất sau:
• Tính chính xác: để đảm bảo kết quả tính toán hay các thao tác mà máy
tính thực hiện được là chính xác.
• Tính rõ ràng: Thuật toán phải được thể hiện bằng các câu lệnh minh

chiều kim đồng hồ, tại bước đi với số lượt là chẵn, ta thực hiện một
thao tác bất kỳ nhưng không đụng đến cái đĩa nhỏ nhất. Các bạn dễ
dàng kiểm tra rằng đó là một thuật toán đúng, tuy nhiên nó rất khó
hiểu, khó tổng quát sang các trường hợp khác.
Ta hãy thử vận dụng tư duy của thuật toán ″Chia để Trị″ đối với bài
toán Tháp Hà Nội này. Bài toán chuyển N đĩa từ A sang B có thể chia
thành 2 bài toán nhỏ hơn với kích thước N-1 như sau: (a) Chuyển N-1
đĩa đầu tiên từ A sang C (giữ nguyên trạng thái của đĩa thứ N tại A).
(b) Chuyển đĩa thứ N từ A sang B và chuyển N-1 đĩa từ C sang B.
Chú ý rằng khi thực hiện bài toán (b) phần chuyển N-1 đĩa từ C sang
B ta có thể dùng lại hoàn toàn thuật toán của bài (a) nhưng với vị trí
thay đổi giữa A và C và tất nhiên bỏ qua sự có mặt của đĩa thứ N
trong A hay B. Với cách tư duy như vậy, việc mô phỏng thuật toán sẽ
tương đối khó do nó phải gọi đệ qui đến chính nó nhưng cách làm trên
thật là dễ hiểu và cho phép chúng ta áp dụng cho nhiều lớp bài toán
khác. Chúng ta hãy xét một vài ví dụ.
Ví dụ 1: Bài toán nhân các số tự nhiên lớn
Xét bài toán nhân 2 số tự nhiên n-bit X và Y. Bài toán nhân 2 số tự
nhiên n-bit (n chữ số) đã được dạy trong nhà trường phổ thông với độ
phức tạp O(n
2
)
(3)
. Bây giờ chúng ta sẽ xét lại bài toán này với kỹ thuật
Chia để Trị. Ta phân tách mỗi số X, Y thành 2 phần, mỗi phần n/2 bit.
Để cho đơn giản ta sẽ luôn xét n là lũy thừa của 2. X, Y sẽ được phân
tích thành 2 phần n/2-bit như sau:
X = A | B (X = A2
n/2
+ B)

bởi:
- 3 phép nhân n/2-bit: AC, BD và (A-B)(D-C).
- 6 phép +, - các số n/2-bit.
- 2 phép chuyển chữ số (nhân với lũy thừa của 2).
Do vậy với cách tính trên ta có công thức sau tính độ phức tạp của
thuật toán này:
T(1) = 1
T(n) = 3T(n/2) + C.n (C-const) (3)
Công thức (3) cho ta
Như vậy ta đã thu được một kết quả mới cho việc thực hiện phép nhân
2 số tự nhiên n-bit với thuật toán mạnh hơn phép nhân bình thường đã
học trong nhà trường (
4
).
Ví dụ 2: Bài toán tạo lịch thi đấu Tennis
Giả sử cần lập một lịch thi đấu Tennis cho n = 2
k
vận động viên
(VĐV). Mỗi vận động viên phải thi đấu với lần lượt n-1 vận động
viên khác, mỗi ngày thi đấu 1 trận. Như vậy n-1 là số ngày thi đấu tối
thiểu phải có. Chúng ta cần lập lịch thi đấu bằng cách thiết lập ma trận
có n hàng, n-1 cột. Giá trị số tại vị trí (i,j) (hàng i, cột j) chỉ ra vận
động viên cần thi đấu với vận động viên i trong ngày thứ j.
Sử dụng kỹ thuật Chia để Trị, chúng ta hãy lập lịch thi đấu cho nửa
(n/2) số vận động viên đầu tiên. Bằng việc sử dụng lời gọi đệ qui
chúng ta đưa bài toán về trường hợp chỉ có 2 VĐV.
Chúng ta minh họa bằng trường hợp n=8. Lịch thi đấu cho 4 người
đầu tiên của danh sách chiếm nửa trái trên của ma trận (4 hàng, 3 cột).
Phần nửa trái dưới (4 hàng, 3 cột) của ma trận là lịch thi đấu của 4
VĐV còn lại (từ 5 đến 8). Phần này thu được từ nửa trái trên bằng

điều chung nhất ở chúng là có một cái bảng và chúng ta cần lần lượt điền các
thông số vào cái bảng này. Để minh họa chúng ta hãy xét một vài ví dụ.
Ví dụ 3: Trò chơi Tán thủ
(5)
Giả sử có hai tán thủ A, B cần đấu trực diện với nhau, qui định chung là
người thắng trước n ván sẽ là người thắng cuộc. Trên thực tế thường giá trị n
= 4. Giả sử hai tán thủ A, B là mạnh ngang nhau và do đó sác xuất thắng,
thua trong mỗi ván là 50/50. Giả sử P(i,j) là sác xuất sao cho A cần thắng
thêm i ván nữa , B cần thắng thêm j ván nữa thì A sẽ chắc chắn thắng chung
cuộc. Chúng ta cần tính những giá trị P(i,j) này với i, j bất kỳ.
Nếu i=0, j>0, tức là A đã thắng rồi và do đó P(0,j)=1. Nếu i>0, j=0, tức là B
đã thắng và A đã thua rồi, do đó P(i,0)=0. Với i, j > 0 ta có nhận xét sau: sác
xuất để A thắng chung cuộc dựa vào ván tiếp theo A thắng hay thua. Nếu
ván tiếp theo A thắng, khi đó sác xuất để A thắng sẽ là P(i-1,j), còn nếu A
23
thua ở ván tiếp theo thì sác xuất để A vẫn thắng chung cuộc sẽ là P(i,j-1). Vì
ván tiếp theo khả năng A thắng thua là 50/50 nên ta có công thức P(i,j) =
(P(i-1,j)+P(i,j-1))/2. Tóm lại ta có công thức truy hồi sau để tính P(i,j)
• Từ công thức (4) với i+j=n ta dễ dàng tính được công thức truy hồi
của độ phức tạp tính toán T(n) như sau:
T(1) = C (C-const)
T(n) = 2T(n-1) + D (D-const) (5)
Ta tính được T(n) = O(2
n
). Như vậy việc tính toán các hệ số P(i,j) sẽ
có độ phức tạp tăng theo số mũ của n nếu tính toán bằng kỹ thuật đệ
qui và đây là một kết quả rất lớn. Tuy nhiên công thức trên chỉ cho ta
giới hạn trên của tính toán, để hiểu rõ hơn sự″tồi tệ″ thực sự của việc
sử dụng đệ qui tính toán theo công thức(4) chúng ta sẽ thử tính toán
giới hạn dưới của công việc tính toán này. (Giới hạn dưới của độ phức

gian tính từ vòng lặp ngoài sẽ là n=i+j. Chắc các bạn đã thấy sự kỳ
diệu của phương pháp điền bảng số so sánh với việc gọi đệ qui, và đó
24
là tư tưởng của thuật toán qui hoạch động.
Ví dụ 4: Bài toán Phân hoạch Tam giác
Ta sẽ xét thêm một ví dụ nữa minh họa cho kỹ thuật qui hoạch động,
đó là bài toán tam giác hóa đa giác. Giả sử có một đa giác trên mặt
phẳng với các đỉnh cho trước. Yêu cầu nối các ″cung″ nối giữa hai
đỉnh bất kỳ của đa giác để chia đa giác thành các tam giác nhỏ hơn
(phân hoạch tam giác) sao cho tổng các dây cung nối là nhỏ nhất. Một
cách chọn dây cung như vậy được gọi là một Phân hoạch tam giác tối
thiểu.
• Hình 4 mô tả một đa giác 7 cạnh với một phân hoạch tam giác. Từ dữ
liệu trên hình vẽ ta tính được tổng chiều dài của phân hoạch này .
tuy nhiên phân hoạch này không là tối ưu.
Bây giờ chúng ta sẽ dùng kỹ thuật qui hoạch động để giải bài toán
phân hoạch tam giác này. Để tiện cho việc theo rõi, chúng ta sẽ ký
hiệu các đỉnh của đa giác là V
0
, V
1
, , V
n-1
theo chiều kim đồng hồ.
Tổng chiều dài các dây cung của một phân hoạch sẽ được gọi là Giá
trị của phân hoạch này. Trước tiên chúng ta có một số nhận xét sau
đây:
Bổ đề 1. Trong mọi phân hoạch tam giác, hai đỉnh kề nhau bất kỳ của
đa giác bao giờ cũng có tối thiểu một đỉnh được nối với một dây cung.
Giả sử V

) và (V
k
,V
j
) sẽ là cạnh của
đa giác hoặc dây cung của phân hoạch.
Thật vậy, cạnh (V
i
,V
j
) phải là cạnh của một tam giác của phân hoạch.
Đỉnh thứ 3 chính là V
k
cần tìm.
Để bắt đầu tìm kiếm phân hoạch tam giác tối ưu, chúng ta chọn 2 đỉnh
kề bất kỳ, chẳng hạn V
0
và V
1
. Khi đó phải tồn tại đỉnh Vk sao cho
V
0
V
k
và V
1
V
k
là cạnh hoặc dây cung của phân hoạch. Với mỗi cách
chọn k như vậy ta đưa bài toán tìm phân hoạch về 2 bài toán con,