Khóa luận Phương pháp sáng tạo trong khoa học kĩ thuật và ứng dụng trong tin học

g đượ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: - Tổng kết dữ liệu - Hợp nhất thông tin từ các nguồn nghiên cứu khác nhau. - Ghi chép tường minh - Ghi nhớ chi tiêt cấu trúc đối tượng hay sáng kiến mà chúng chứa các mối liên hệ phức tạp hay chằng chéo - Trình bày thông tin để chia ra của toàn bộ đối tượng. - Động não về một vấn đề phức tạp. - Khuyến khích làm giảm sự mô tả của mỗi ý,mỗi khái niệm thành mot từ (hay từ kép). - Toàn bộ ý của giản đồ có thể "nhìn thâý" và nhớ bởi trí nhớ hình ảnh. Loại trí nhớ gần như tuyệt hảo. - Sáng tạo các bài viết và các bài tường thuật. - Là phương tiện học tập hay tìm hiểu sự kiện. Với giản đồ ý người ta có thể tìm thấy gần như vô hạn số lượng các ý tưởng và cùng sắp xếp lại các ý đó và bên cạnh những ý có cùng liên hệ.Điều này biến phương pháp này thành công cụ mạnh để soạn các bài viết và tường thuật, khi mà những ý kiến cần phải được ghi nhanh. Sau dó tùy theo các ý chính thì các câu hay đoạn văn sẽ được triển khai rộng ra. Đặc điểm giản đồ ý. - Đặt ý chính ở trung tâm và được xác định rõ ràng. - Sự quan hệ tương hỗ được chỉ ra tường tận.Ý càng quan trọng thì càng nằm gần ý chính. -Sự liên hệ giữa các khái niệm then chốt sẽ được chấp nhận lập tức. -Ôn và nhớ sẽ có hiệu quả cao hơn. -Thêm thông tin dễ dàng hơn. -Mỗi giản đồ phân biệt nhau dễ dàng hơn cho việc gợi nhớ. Ví dụ minh họa: Ghi chú trên hình 1.CPU2.Bộ nhớ3.BUS4.Các bộ điều khiển I/O5.Bộ điều khiển video6.Cổng nối tiếp7.USB8.Ổ điã9. Ổ CD10.Màn hình11.NIC12.Cổng song song13.Bàn phím14.Chuột15.Máy in16.Mạng17.Máy quét hình18.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 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 đápCâ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.  Chúng đánh lừa não bạn vì não bạn có xu hướng suy nghĩ theo kiểu "mặc định": 2 người chơi cờ thì "mặc định" là họ chơi với nhau, cưa khúc gỗ làm đôi được 5 đôla thì cưa làm 4 (2x2) thì "mặc định" là được trả 5x2=10 đôla... Trong khi đề bài không hề có những dữ kiện như vậy. Tại sao bạn lại "mặc định" như thế? à?ó chính là sức ỳ tâm lý làm cho não bạn bị mắc lừa ở những câu đố đòi hỏi nghĩ sáng tạo.Nghĩ sáng tạo là nhìn một vấn đề, một câu hỏi... theo những cách khác với thông thường. Tức là nhìn mọi thứ từ các góc độ, tầm nhìn khác nhau, "nhìn" theo những cách không bị hạn chế bởi thói quen, bởi phong tục, bởi tiêu chuẩn... Câu 3: 2 con vịt đi trước 2 con vịt, 2 con vịt đi sau 2 con vịt, 2 con vịt đi giữa 2 con vịt. Hỏi có mấy con vịt? Trả Lời: 4. Câu 4: Có 1 anh chàng làm việc trong 1 tòa nhà 50 tầng, nhưng anh ta lại chỉ đi thang máy lên đến tầng 35 rồi đoạn còn lại anh ta đi thang bộ. Tại sao anh ta lại làm như vậy ? Trả Lời: Vì cái thang máy đó không lên được tới tầng 50. Câu 5: Bạn có thể kể ra ba ngày liên tiếp mà không có tên là thứ hai, thứ ba, thứ tư, thứ năm, thứ sáu, thứ bảy, chủ nhật? Trả Lời: Hôm qua, hôm nay và ngày mai. Câu 6: Có 1 con trâu. Đầu nó thì hướng về hướng mặt trời mọc, nó quay trái 2 vòng sau đó quay ngược lại sau đó lại quay phải hay vòng hỏi cái đuôi của nó chỉ hướng nào? Trả Lời: Chỉ xuống đất. Câu 7: Chứng minh: 4 = 5 TL: Ta có: -20 = -20 25 - 45 = 16 - 36 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 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 chiếc hộp (lần này có lẽ là bên ngoài cái vỏ trứng!), đã giải quyết được vấn đề. Ông được Nữ hoàng cung cấp tàu và tiền để bắt đầu chuyến phiêu lưu của mình.Thực ra, đây là một ví dụ rõ ràng về một con người không chấp nhận bị giới hạn bởi những suy nghĩ thông thường. Columbus lên tàu đi vòng quanh thế giới, trong khi tất cả mọi người lúc đó còn khẳng định là thế nào rồi ông cũng đi đến "rìa" thế giới và rơi tõm ra ngoài. 3. Ứng dụng của nghĩ sáng tạo Nếu sức ỳ tâm lý của bạn vẫn còn lớn, e rằng đến bây giờ bạn lại "mặc định" rằng vậy ra "nghĩ sáng tạo", nói vòng vo mãi, cuối cùng cũng chỉ để... giải các câu đố!!!Bạn hãy nghe câu chuyện này. Có 2 người làm bánh quế, với chất lượng và giá cả như nhau. Khi mọi người chán ăn bánh quế và không mua nữa, một người bán chẳng biết làm sao và bỏ nghề. Trong khi đó, người còn lại đã "thiết kế" bánh quế kiểu mới bằng cách cuộn tròn nó lại theo hình nón và tạo ra một sản phẩm mới hoàn toàn: ốc quế cho kem. Như vậy, người bán hàng thứ nhất đã không thể đi tiếp được, còn người thứ hai đã chuyển dịch ra ngoài giới hạn và những mặc định thông thường.Nếu không có sự "nghĩ sáng tạo" của người thứ hai, hẳn bây giờ chúng ta vẫn chỉ biết ăn kem que hoặc dùng thìa múc từ cốc (hoặc nếu không có ai nghĩ sáng tạo từ ban đầu thì có thể chúng ta thậm chí còn chẳng có kem mà ăn!).Khả năng nghĩ sáng tạo càng trở nên cực kỳ quan trọng trong thế giới kinh doanh thay đổi nhanh chóng như hiện nay. 4. Những phẩm chất của một người nghĩ sáng tạo - Độc lập.- Tự tin.- Chấp nhận rủi ro.- Nhiều năng lượng.- 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.E = Effective thinking (Nghĩ hiệu quả). Nghĩ hiệu quả tức là hướng suy nghĩ của bạn đến những mục đích cụ thể. Không có mục đích thì bạn sẽ làm rối hết mọi việc lên.D = Determination (Quyết tâm). Sự sáng tạo đòi hỏi có luyện tập. Bạn nên tạo thói quen tưởng tượng. Những ý tưởng ban đầu của bạn có vẻ hết sức buồn cười và không ai chấp nhận, nhưng đừng bỏ cuộc.I = Ink (viết). Khi bạn nhìn vào những thứ bạn viết ra, bạn sẽ có nhiều ý tưởng hơn là chỉ nghĩ đến nó. b. TILS: T = Think it: Suy nghĩ.I = Ink it: Viết ra.L = Link it: Nối, liên tưởng.S = Sync it: à? thồng nhất.6. Luyện tập Có những bài tập suy nghĩ sáng tạo mà bạn có thể thử:- Nếu bạn cần giao tiếp nhưng bạn không thể sử dụng từ ngữ, dù viết hay nói, thì bạn làm cách nào? Một người đã đưa ra những ý sau: ngôn ngữ cử chỉ, dùng trống, dùng đồ vật, dùng đèn nhấp nháy, vẽ...- Bạn hãy đặt ra những câu hỏi cho những đồ vật thường ngày, ví dụ: "nếu thang máy không chỉ đi lên và xuống mà còn từ đầu này sang đầu kia thì sẽ thế nào?", "nếu mỗi cơ quan yêu cầu mỗi ngày mỗi người phải cười ít nhất 30 phút thì sao?"...- Vấn đề của một công ty bán khoai tây chiên: khoai tây chiên thường rất dễ vỡ vụn khi đóng gói, vận chuyển..., vậy làm thế nào? Bạn có thể bắt đầu bằng việc nghĩ ra cách đóng gói và vận chuyển mà không làm khoai tây bị vỡ. Sau đó, suy luận: về bản chất thì cái gì giống miếng khoai tây chiên, chúng có dễ vỡ không?...- Một cuốn sổ tay thì bạn có thể sáng tạo theo cách nào? "Sức ỳ tâm lý" rất dễ làm cho đa số mọi người nghĩ rằng "sổ tay thì còn gì để sáng tạo nữa!". Nó rõ ràng đến phát bực mình! Nhưng vẫn có những ý tưởng của những người không chịu thua: Sổ tay đổi màu; Sổ biết đọc những thứ mình viết lên; 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à:. 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 đôiMụ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ườngVí 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 luận, ảo thuật, truyện vui, tạp kỹ…. Trong đó câu đố là một hình thức không thể thiếu được để rèn luyện trí óc của chúng ta. Nó bao gồm những tài liệu rèn luyện khả năng trực giác, khả năng quan sát, khả năng phân tích, khả năng suy luận, khả năng bền bỉ, khả năng sáng tạo của con người. 8. Kết Có một người cha giàu có với 3 người con trai. Ông muốn trao lại tài sản cho người con thông minh nhất. Thế là ông nghĩ ra một cách: đưa cho mỗi người một khoản tiền nhỏ và bảo những người con hãy mua thứ gì có thể làm đầy được nhà kho, càng đầy càng tốt.Ba người con cầm tiền và đi tìm thứ vừa rẻ vừa dễ làm đầy nhà kho. Người con cả nhìn thấy một cái cây rất to trên đường, và nghĩ rằng cành và lá cây rất cồng kềnh, sẽ tỏa ra được mọi ngóc ngách của phòng. Thế là anh ta mua hết cành cây và thuê người đem về nhà.Người con thứ hai thì mừng húm khi nhìn thấy đống cỏ khô. Cỏ vừa rẻ vừa nhẹ, lại nhỏ, dễ dàng làm đầy nhà kho. Thế là anh ta mua hết cỏ và thuê người đem về nhà.Người con út nghĩ đi nghĩ lại về cách làm đầy nhà kho sao cho vừa hiệu quả, vừa không tốn kém. Cuối cùng, anh ta chỉ mua một ngọn nến. Khi thắp ngọn nến lên, cả nhà kho đầy tràn ánh sáng. Người cha rất hài lòng và để lại tài sản cho người con út.Hàm ý của câu chuyện này là gì? à? Để thắp sáng được ngọn nến sáng tạo bên trong mỗi người, trước hết, đầu óc chúng ta phải đầy đã. CHƯƠNG IV: PHƯƠNG PHÁP SÁNG TẠO TRONG CÁC BÀI TOÁN TIN HỌC. 1.Thuật toán Thuật toán, còn gọi là giải thuật, là một tập hợp hữu hạn của các chỉ thị hay phương cách được định nghĩa rõ ràng cho việc hoàn tất một số sự việc từ một trạng thái ban đầu cho trước; khi các chỉ thị này được áp dụng triệt để thì sẽ dẫn đến kết quả sau cùng như đã dự đoán. 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: Nếu a = 0 b = c thì P(x) có nghiệm bất kì b ≠ c thì P(c) vô nghiệm Nếu a ≠ 0 P(x) có duy nhất một nghiệm x = (c - b)/a 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 bạch; các câu lệnh được sắp xếp theo thứ tự nhất định. Tính khách quan: Một thuật toán dù được viết bởi nhiều người trên nhiều máy tính vẫn phải cho kết quả như nhau. Tính phổ dụng: Thuật toán không chỉ áp dụng cho một bài toán nhất định mà có thể áp dụng cho một lớp các bài toán có đầu vào tương tự nhau. Tính kết thúc: Thuật toán phải gồm một số hữu hạn các bước tính toán. 2.Thuật toán Chia để Trị (Divide & Conquer) Có lẽ thuật toán được sử dụng nhiều nhất, quan trọng nhất là kỹ thuật ″Chia để Trị″. Kỹ thuật này sẽ chia bài toán hiện thời thành N bài toán nhỏ hơn, thực hiện lời giải cho từng bài toán nhỏ này và từ đó xây dựng thuật toán cho bài toán lớn tổng hợp. Ví dụ cho các thuật toán này là Sắp xếp Trộn(1) hoặc Tìm kiếm Nhị phân(2) mà các bạn đã đã được biết trong chương trình Tin học Cơ bản. Để minh họa rõ hơn cho kỹ thuật này chúng ta hãy xét một ví dụ quen thuộc đó là bài toán ″Tháp Hà Nội″. Giả sử có 3 cọc A, B, C. Ban đầu tại A đặt một số đĩa với thứ tự trên nhỏ dưới to. Yêu cầu của bài toán là chuyển toàn bộ số đĩa trên sang cọc B, trong quá trình chuyển được phép sử dụng đĩa C, mỗi lần chuyển đúng 01 đĩa và luôn bảo đảm nguyên tắc đĩa nhỏ nằm trên đĩa to trong suốt quá trình chuyển. Bài toán Tháp Hà Nội trên có thể giải với thuật toán ″thông minh″ sau: Giả sử ta đặt 3 cọc trên tại các đỉnh của một tam giác đều. Tại bước với số lượt là lẻ, ta chuyển đĩa nhỏ nhất sang cọc bên cạnh theo 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ớnXé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(n2)(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 = A2n/2 + B)Y = C | D (Y = C2n/2 + D)Khi đó tích XY sẽ có dạng:XY = AC2n + (AD+BC)2n/2 + BD (1)Dựa trên công thức (1) ta có thể suy luận đơn giản như sau cho việc tính tích XY: chúng ta sẽ tính 4 phép nhân với các số n/2-bit là AC, AD, BC và BD, sau đó thực hiện 3 phép cộng với các số 2n-bit, cuối cùng là 2 phép chuyển chữ số (2 phép nhân với lũy thừa của 2) Các phép cộng và phép chuyển chữ số đều được thực hiện với thời gian O(n), do đó ta thu được công thức tính độ phức tạp của phép toán trên T(n) là:T(1) = 1T(n) = 4T(n/2) + C.n (C-const) (2)Công thức (2) cho ta T(n) = O(n2) và như vậy ta chưa thu được kết quả gì mới so với phương pháp tính từ nhà trường phổ thông.Bây giờ ta biến đổi công thức (1) dưới dạng:XY = AC2n + ((A-B)(D-C) + AC + BD)2n/2 + BD (2)Công thức (2) mặc dù phức tạp hơn (1) nhưng chúng có thể được tính 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) = 1T(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 TennisGiả sử cần lập một lịch thi đấu Tennis cho n = 2k 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 cách cộng 4 vào mỗi phần tử tương ứng của ma trận. Để điền nốt các phần còn lại của ma trận chúng ta chỉ cần xác định lịch thi đấu giữa các VĐV với số thấp (≤n/2) với các VĐV với số cao (≥n/2). Để làm việc này chúng ta xếp các VĐV từ 1 đến n/2 đấu lần lượt với các VĐV số cao vào ngày 4. Các ngày còn lại thu được từ ngày 4 bằng cách hoán vị vòng quanh các VĐV với số thứ tự cao. Quá trình điền số được mô tả trong hình 2. Các bạn có thể tổng quát quá trình này cho trường hợp tổng quát n=2k bất kỳ. 3.Thuật toán Qui Hoạch Động (Dynamic Programming)Trong phần trên chúng ta đã thấy sức mạnh của kỹ thuật Chia để Trị bằng cách chia nhỏ bài toán cần làm. Tuy nhiên không phải bao giờ cũng có thể chia nhỏ bài toán thành các bài toán con và từ đó tìm ra lời giải của bài toán lớn. Trong các trường hợp như vậy, mặc dù chúng ta vẫn có thể chia nhỏ bài toán thành nhiều bài toán con, nhưng thời gian thu được sẽ tăng theo số mũ và thuật toán trở nên vô giá trị. Trên thực tế, việc chia thành các bài toán con thường chỉ chiếm thời gian là đa thức. Trong trường hợp này một bài toán con sẽ được lặp lại nhiều lần trong quá trình tìm kiếm lời giải. Để khỏi mất thời gian mỗi khi giải quyết các bài toán con, các bạn sẽ lưu trữ các lời giải này để tra cứu về sau mỗi khi cần đến. Công việc này sẽ đòi hỏi độ phức tạp thuật toán là đa thức.Có một cách làm còn đơn giản hơn cách đã nêu trên. Chúng ta sẽ lưu giữ tất cả các lời giải của các bài toán con lại không cần biết rằng chúng có được dùng lại nhiều lần về sau hay không, không quan tâm đến việc các lời giải này có cần thiết cho lời giải của bài toán chính của chúng ta hay không. Cách làm như vậy có tên gọi là Qui hoạch động. Bản thân từ qui hoạch động được lấy từ lý thuyết điều khiển. Cách cài đặt thực tế của thuật toán qui hoạch động không thống nhất như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 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(2n). 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 tạp được ký hiệu là big-omega: W). Để tính được giá trị này chúng ta sẽ tính số lần gọi hàm P khi thực hiện đệ qui cách tính P(i,j) theo công thức (4). Công thức (4) với i+j=n nếu xem xét kỹ sẽ gợi ý cho chúng ta về một đẳng thức tương tự của hệ số tổ hợp là (tổ hợp chập i từ n phần tử, số cách chọn ra i phần tử từ tập hợp ban đầu n phần tử).Với i=j=n/2 dễ thấy giá trị này sẽ bằng .Vậy ta vừa chứng minh được rằng cận dưới độ phức tạp tính toán P(i,j) là một giá trị rất lớn (tuy có nhỏ hơn 2n) và hầu như không thể áp dụng tính toán trên thực tế. Bảng hệ số P(i,j) được điền tuần tự như sau: Trước tiên để ý rằng hàng dưới c