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

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 TpHCM, 01-2010 PHỤ LỤC: CHƯƠNG I:GIỚI THIỆU. Khoa học sáng tạo Phương pháp luận Sáng tạo là gì? 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. Giới thiệu kỹ thuật tư duy 5W1H 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 Suy nghĩ trước khi nhìn giải đáp.: Nghĩ sáng tạo xa hơn Ứng dụng của nghĩ sáng tạo Những phẩm chất của một người nghĩ sáng tạo Bạn có thể học để nghĩ sáng tạo Luyện tập Nâng cao khả năng sáng tạo Kết  CHƯƠNG IV:PHƯƠNG PHÁP SÁNG TẠO TRONG CÁC BÀI TOÁN TIN HỌC. Thuật toán Thuật toán Chia để Trị (Divide & Conquer) Thuật toán Qui Hoạch Động (Dynamic Programming) Ứng dụng nguyên lý địa phương trong lập trình. Ứng dụng nguyên lý phân nhỏ trong lập trình. Ứng dụng nguyên lý an toàn trong lập trình. Ứng dụng nguyên lý BOTTOM-UP trong lập trình. Chương I: GIỚI THIỆU. 1. Khoa học sáng tạo Hoạt động sáng tạo gắn liền với lịch sử tồn tại và phát triển của xã hội loài người. Từ việc tìm ra lửa, chế tạo công cụ bằng đá thô sơ… đến việc sử dụng năng lượng nguyên tử, chinh phục vũ trụ…, hoạt động sáng tạo của loài người không ngừng được thúc đẩy. Sáng tạo không thể tách rời khỏi tư duy – hoạt động bộ não của con người. Chính quá trình tư duy sáng tạo với chủ thể là con người đã tạo các giá trị vật chất, tinh thần, các thành tựu vĩ đại về mọi mặt trong cuộc sống và tạo ra nền văn minh nhân loại. Ý định “khoa học hóa tư duy sáng tạo” có từ lâu. Nhà toán học Hy Lạp Pappos, sống vào thế kỷ III, gọi khoa học này là Ởistic (Heuristics). Theo quan niệm lúc bấy giờ, Ơristic là khoa học về các phương pháp và quy tắc làm sáng chế, phát minh trong mọi lĩnh vực khoa học, kỹ thuật, văn học, nghệ thuật, chính trị, triết học, toán, quân sự… Do cách tiếp cận quá chung và không có nhu cầu xã hội cấp bách, Ơristic bị quên lãng cho đến thời gian gần đây. 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 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á trình phát triển của loài người, sau nông nghiệp, công nghiệp và tin học. Làn sóng thứ tư ứng với Creatology (hay còn gọi là thời đại hậu tin học) chính là sự nhấn mạnh vai trò chủ thể tư duy sáng tạo của loài người trong thế kỷ XXI. “TRONG CON NGƯỜI VỐN CÓ NHỮNG NGUỒN SÁNG TẠO VÔ TẬN, NẾU KHÁC ĐI THÌ ĐÁ KHÔNG THÀNH NGƯỜI. CẦN PHẢI GIẢI PHÓNG VÀ KHƠI THÔNG CHÚNG”.  - A.N.TÔLXTÔI Tư duy sáng tạo là chủ đề của một lĩnh vực nghiên cứu còn mới. Nó nhằm tìm ra các phương án, biện pháp thích hợp để kích hoạt khả năng sáng tạo và để tăng cường khả năng tư duy của một cá nhân hay một tập thể cộng đồng làm việc chung về một vấn đề hay lĩnh vực. Ứng dụng chính của bộ môn này là giúp cá nhân hay tập thể thực hành nó tìm ra các phương án, các lời giải từ một phần đến toàn bộ cho các vấn đề nan giải. Các vấn đề này không chỉ giới hạn trong các ngành nghiên cứu về khoa học kỹ thuật mà nó có thể thuộc lĩnh vực khác như chính trị, kinh tế, xã hội, nghệ thuật... hoặc trong các phát minh, sáng chế. Một danh từ khác được giáo sư Edward De Bono (1933 -) sử dụng để chỉ ngành nghiên cứu này và được dùng rất phổ biến là tư duy định hướng. Một số phương pháp tư duy sáng tạo đã và đang được triển khai thành các lớp học, các hội nghị chuyên đề ở các cơ quan, tổ chức xã hội, chính trị, chính trị - xã hội nhằm nâng cao hiệu quả làm việc của cá nhân hay tập thể. Ở các trường trung học của các nước phát triển, một số phương pháp quan trọng như tập kích não, giản đồ ý cũng đã được áp dụng cho học sinh biết cách áp dụng dưới dạng thô sơ; đồng thời cũng đã có nhiều cơ sở giáo dục tư thục giảng dạy các chuyên đề về phương pháp tư duy sáng tạo cho học viên mọi lứa tuổi. 3.Một vài đặc điểm của tư duy sáng tạo Các bộ môn được xem là công cụ của ngành này bao gồm: Tâm lý học, giáo dục học, luận lý học (hay logic học), giải phẫu học, và các 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 án tư duy có định hướng thì một hệ quả tất yếu là người nghiên cứu sẽ chọn lựa một cách tối ưu những dữ liệu cần thiết, do đó tránh các cảm giác lúng túng, mơ hồ, hay lạc lõng trong rừng rậm của thông tin. Từ xa xưa, các phương pháp tư duy sáng tạo đã bắt nguồn khi loài người biết suy nghĩ. Một trong các phương pháp đầu tiên được dùng tới có lẽ là phương pháp tương tự hoá. Tiếp theo là các phương pháp tổng hợp, phân tích, trừu tượng và cụ thể hoá chắc chắn đã được các nhà triết học và toán học sử dụng trong thời La Mã cổ đại và thời Xuân Thu. Tuy nhiên, việc nghiên cứu có hệ thống và trình bày lại một cách đầy đủ cho từng phương pháp thì mãi đến đầu thế kỷ thứ 20 mới xuất hiện. Đặc biệt là sau việc chính thức phát minh ra phương pháp Tập kích não vào năm 1941 của Alex Osborn thì các phương pháp tư duy sáng tạo mới thực sự được các nhà nghiên cứu nhất là các nhà tâm lý học chú ý tới. Kể từ đó, rất nhiều phương pháp tư duy sáng tạo đã ra đời. Hiện nay, một số khuynh hướng chung là tìm ra các phương pháp để sử dụng kết hợp khả năng tư duy của các cá nhân vào trong một đề tài lớn cùng với sự hỗ trợ của ngành tin học. Trong tương lai, khi mà thành tựu của việc liên lạc trực tiếp các tín hiệu của các con chip điện tử với não người được hoàn thiện hơn thì chắc chắn nó sẽ tạo ra một cuộc cách mạng mới về các phương pháp tư duy sáng tạo. Lúc đó, việc khó khăn là làm sao cho bộ não của từng cá nhân điều khiển và tận dụng được mọi khả năng của các hệ thống máy tính, cũng như làm sao quản lý việc nối các hoạt động tư duy cá nhân thành một mạng tư duy khổng lồ với thời gian truy cập thông tin là thời gian thực. 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 Để bắt đầu nghiên cứu, học hỏi hoặc viết về một vấn đề nào đó, chúng ta 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, …? 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?- Bài thuyết trình này sẽ được trình bày trong nhóm hay trước lớp?... WHEN (Khi nào?)- Sự kiện này xảy ra khi nào?- Vấn đề này, trước đây đã có ai nghiên cứu chưa, khi nào?- Khái niệm này bắt đầu xuất hiện khi nào?- Khi nào thì cần ứng dụng ICT trong bài dạy?- Khi nào thì mình sẽ trình bày bài thuyết trình này?- Các bước nghiên cứu (đề tài tốt nghiệp, luận văn, tiểu luận, …) sẽ được thực hiện theo thời gian nào, hoặc phải kết thúc từng bước khi nào?...WHY (Tại sao?)- Tại sao phải nghiên cứu vấn đề này?- Tại sao tác giả cuốn sách lại lựa chọn cách sắp xếp như thế này?- Tại sao thí nghiệm này không diễn ra đúng như dự kiến? (Why not)- Tại sao giáo viên truy cập nhiều vào website giaovien.net? - Tại sao cuộc khởi nghĩa này nổ ra? Tại sao nó thất bại?- Tại sao hồi nhỏ mình học trong trường thuộc loại khá giỏi mà bây giờ vẫn luôn chật vật về kinh tế?...HOW (Như thế nào?)- Chiếc máy này hoạt động như thế nào?- Công việc này nên bắt đầu như thế nào?- Dự án này sẽ tiêu tốn bao nhiêu? (How much)- Các sự kiện và nhân vật trong cuốn tiểu thuyết này được kết nối như thế nào?- Sự kiện lịch sự này đã làm đối phương thiệt hại bao nhiêu quân trang, vũ khí và người? (How many)- Phong cách của bài báo sắp tới nên như thế nào?WHO (Ai?)- Ai đã nghiên cứu vấn đề này?- Ai đã nghiên cứu vấn đề này? - Ai phụ trách dự án này?- Bài trình bày sắp tới dành cho đối tượng nào?- Khi mình gặp khó khăn trong ứng dụng ICT, mình sẽ hỏi ai?- 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?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ễnTá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: Tại sao phải tư duy tích cực?HOW: Bài viết cần được thực hiện như thế nào? Muốn tư duy tích cực thì phải làm sao?- Vì đối tượng nhắm đến của bài viết là những người không biết hoặc biết nhưng chưa nắm cụ thể và rõ ràng nó là gì? Do đó, bài viết cần được thực hiện với một văn phong lôi cuốn nhưng dễ hiểu, đơn giản và rõ ràng. Đồng thời, các ví dụ đưa ra phải ít nhiều dính dáng đến giáo viên.- Để trả lời câu hỏi “Muốn tư duy tích cực thì phải làm sao?” thì cần đưa ra được các phương pháp thực hành, các lời khuyên để tham khảo. -> Sự ra đời của phần 3 của bài viết: Làm thế nào để tư duy tích cực?WHO: Đối tượng của bài viết là ai? Ai viết bài này? Ai kiểm tra và duyệt nội dung?- Đối tượng của bài viết là các Thầy Cô và các bạn muốn tìm hiểu về kỹ năng Tư duy tích cực. Có thể họ chưa biết hoặc có nghe qua cụm từ “Tư duy tích cực” nhưng không nắm hết các vấn đề, kỹ thuật liên quan.- Người viết bài: chính là …tui đây.- Ai duyệt bài? Ban quản trị của CENTEA.Bên trên là những phác thảo của tác giả T.T.H để thực hiện bài viết “Học cách Tư duy tích cực”. Chúng ta thấy rằng, việc sử dụng công cụ này thật đơn giản nhưng rất hiệu quả.Công cụ 5W1H còn có thể được sử dụng hiệu quả trong nhiều trường hợp khác như: thuyết trình, nghiên cứu khoa học, tóm tắt một cuốn sách, ghi nhớ một sự kiện,…5W1H cũng có thể sử dụng chung với Bản đồ tư duy để giải quyết nhiều vấn đề khác nhau trong giảng dạy, học tập, kinh doanh, đàm phán,…Một chút thông tin về nguồn gốc của 5W1HKhái niệm 5W1H được cho là có nguồn gốc từ bài thơ “The Elephant''s Child” của Rudyard Kipling. Bài thơ này như sau: I have six honest serving-men 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. 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: - 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ùng của bảng là toàn 0 và hàng đầu tiên bên phải sẽ là toàn 1. Xuất phát từ góc phải dưới chúng ta lần lượt điền số vào bảng theo hướng Tây-Bắc dọc theo đường chéo ngược với i+j không thay đổi. Thuật toán điền số P(i,j) vào bảng được mô tả như sau:Function Ođs(i,j: integer):real; (7) var s,k:integer;Beginfor s:=1 to i+j dobegin P[0,s]:=1; P[s,0]:=0;for k:=1 to s-1 doP[k,s-k]:=(P[k-1,s-k]+P[k,s-k-1])/2;end;Ođs:=(P[i,j]);End; {Ođs}Ta hãy thử phân tích thuật toán trên. Vòng lặp bên trong là O(s) thời gian, hai lệnh gán 0 và 1 chỉ là O(1) thời gian, như vậy tổng số thời 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à đó 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ácTa 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à V0, V1,.., Vn-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ử Vi,Vi-1 là hai đỉnh kề mà không được nối với bất cứ dây dung nào của phân hoạch tam giác. Khi đó vùng phân hoạch chứa cạnh ViVi+1 sẽ phải chứa thêm hai cạnh nữa làVi-1Vi và Vi+1Vi+2 và do đó vùng phân hoạch này không là tam giác.Bổ đề 2. Giả sử (Vi,Vj) là một dây cung của phân hoạch tam giác, khi đó phải tồn tại một đỉnh Vk sao cho (Vi,Vk) và (Vk,Vj) 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 (Vi,Vj) phải là cạnh của một tam giác của phân hoạch. Đỉnh thứ 3 chính là Vk 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 V0 và V1. Khi đó phải tồn tại đỉnh Vk sao cho V0Vk và V1Vk 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, tương ứng với 2 đa giác con xác định bởi dây cung vừa tìm được phân chia đa giác ban đầu thành 2 phần. Với ví dụ đa giác 7 cạnh đã nêu trên giả sử ta chọn đỉnh V3 với cung V0V3, khi đó sẽ đưa về 2 bài toán con ứng với hai đa giác. Tiếp theo chúng ta cần giải quyết bài toán phân hoạch tam giác cho hai trường hợp tương ứng với hình 5 trên. Ví dụ với Bài toán con 2, nếu chúng ta bắt đầu từ cung V3V5 thì sẽ chia thành 2 bài toán con nữa tương ứng với hai đa giác con là (V3,V4,V5) và (V0,V3,V5,V6). Cách tiếp cận như vậy sẽ có thời gian tăng số mũ với n. Chú thích của người viết.(1) Sắp xếp trộn. Thuật toán sắp xếp tách dãy ban đầu thành 2 dãy và sau đó tiến hành ″trộn″ hai dãy này lại với nhau theo hình thức xét lần lượt từng phần tử đầu của các dãy này.(2) Tìm kiếm nhị phân. Thuật toán tìm kiếm trên một dãy đã sắp thứ tự dựa trên ý tưởng luôn chia dãy đã cho thành 2 phần bằng nhau và đưa việc tìm trên dãy lớn về bài toán tìm kiếm trên các dãy con này.(3) Phương pháp tính nhân trong nhà trường phổ thông. Chia nhỏ việc nhân 2 số n-chữ số XY thành n bài toán con, mỗi bài toán con nhân X với một số có một chữ số. Với mỗi bài toán con như vậy việc nhân mất O(n) thời gian, do vậy tổng số độ phức tạp là O(n2).(4) Tới đây sẽ có bạn thắc mắc rằng thế thì tại sao không dạy cách nhân mới này cho học sinh ngay từ trên ghế nhà trường. Tuy nhiên thuật toán mô tả ở đây hoàn toàn không tốt hơn cách nhân thông thường ở trường phổ thông với n<5000. Mặt khác nó lại quá phức tạp và không sáng sủa như thuật toán học sinh đang sử dụng hiện nay.(5) Nguyên tác là cụm từ World Series Ođs, chúng tôi sửa lại cho thích hợp hơn với thực tế của Việt Nam.(6) Cách tính như sau: Với i=j=n/2 ta cần phải chứng minh: .Ta chứng minh bất đẳng thức này qui nạp theo n (n-chẵn). Với n=2, bất đẳng thức là hiển nhiên. Giả sử nó đã đúng với n, ta sẽ chứng minh nó cũng đúng với n+2....từ đó là suy ra đpcm. 4.Ứng dụng nguyên lý địa phương trong lập trình. Các biến địa phương trong hàm ,thủ tục hoặc chu trình cho dù có trùng tên với biến toàn cục thì khi xử lý biến đó trong hàm hoặc thủ tục vẫn không làm thay đổi giá trị của biến toàn cục. Tên của các biến trong đối của hàm hoặc thủ tục đều là hình thức. Mọi biến hình thức truyền theo trị cho hàm hoặc thủ tục đều là các biến địa phương. Các biến khai báo bên trong các chương trình con,hàm hoặc thủ tục đều là biến địa phương. Khi phải sử dụng biến phụ nên dùng biến địa phương và hạn chế tối đa việc sử dụng biến toàn cục để tránh xảy ra các hiệu ứng phụ. Ví dụ hoán đổi giá trị của hai số a và b sau đây sẽ minh họa rõ hơn về nguyên lý địa phương. Ví dụ 1.Hoán đổi giá trị của hai biến a và b. #include #include #include #include Int a,b;//khai báo a,b là 2 biến toàn cục Void Swap(void) { Int a,b,temp;//khai báo a,b là hai biến địa phương a=3,b=5;//gán giá trị cho a và b temp=a;a=b;b=temp;//đổi giá trị của a và b. printf(“\n Kết quả thực hiện trong thủ tục a=%5d b=%5d:”,a,b); } Void main(void) { a=1,b=8;//khởi đầu giá trị cho biến toàn cục a,b. Swap(); Printf(“\n Kết quả thực hiện sau khi thực hiện thủ tục a=%5d b=%5d”,a,b); Getch(); } Kết quả thực hiện chương trình: Kết quả thực hiện trong hàm thủ tục a=5 b=3 Kết quả sau khi thực hiện thủ tục a=1;b=8 Trong ví dụ trên a,b là hai biến toàn cục,hai biến a,b trong thủ tục Swap là hai biến cục bộ.Các thao tác trong thủ tục Swap gán cho a giá trị 3 và b giá trị 5 sau đó thực hiện đổi giá trị của a=5 và b=3 là công việc xử lý nội bộ của thủ tục mà không làm đổi giá trị của biến toàn cục của a,b sau khi thực hiện xong thủ tục Swap.Do vậy,kết quả sau khi hai biến toàn cục a và b.Tuy nhiên,trong ví dụ sau,thủ tục Swap lại làm thay đổi giá trị của biến toàn cục a và b vì nó thao tác trực tiếp trên biến toàn cục. Ví dụ 1.5.Đổi giá trị của hai biến a và b. #include #include #include #include Int a,b;//khai báo a,b là 2 biến toàn cục Void Swap(void) { Int a,b,temp;//khai báo a,b là hai biến địa phương a=3,b=5;//gán giá trị cho a và b temp=a;a=b;b=temp;//đổi giá trị của a và b. printf(“\n Kết quả thực hiện trong thủ tục a=%5d b=%5d:”,a,b); } Void main(void) { a=1,b=8;//khởi đầu giá trị cho biến toàn cục a,b. Swap(); Printf(“\n Kết quả thực hiện sau khi thực hiện thủ tục a=%5d b=%5d”,a,b); Getch(); } Kết quả thực hiện chương trình: Kết quả thực hiện trong hàm thủ tục a=8 b=1 Kết quả sau khi thực hiện thủ tục a=1;b=8 5.Ứng dụng nguyên lý phân nhỏ trong lập trình. Nội dung: Chia đối tượng thành các thành phần độ lập. Làm đối tượng trở nên tháo lắp được. Tăng mức độ phân nhỏ của đối tượng. Một bài toán thường có thể chia nhỏ các đối tượng để trở nên dễ tiếp cận lời giải hơn.Ví dụ trong phương pháp tìm kiếm nhị phân.Ta thực hiện các bước như sau: Bước 1:left=1,right=n;//tìm kiếm trên tất cả phần tử. Bước 2:mid=(left+right)/2;//lấy mốc so sánh. So sánh a[mid] với x,có ba khả năng: +a[mid]=x:Tìm thấy dừng. +a[mid]>x://tìm tiếp x trong dãy con aleft.....amid-1;right=midle-1; +a[mid]<x://tìm tiếp x trong dãy con amid+1…..aright. left=mid+1; Bước 3:Nếu left tìm tiếp . Lặp lại bước 2.ngược lại dừng.//đã xét hết phần tử. …. Cài đặt: Int binarySearch(int a[],int N,int x) { Int left=0;right=N-1; Int midle; Do { Mid=(left+right)/2; If(x=a[midle]) return midle; Else if(x<a[midle] right=midle-1; Else left =midle+1; }while(left<=right); Return -1;//tìm hết dãy mà không có x. } 6.Ứng dụng nguyên lý an toàn trong lập trình. Lỗi nặng nhất nằm ở mức cao nhất(mức ý đồ thiết kế) và ở mức thấp nhất thủ tục phải chịu tải lớn nhất. Mọi lỗi,dù nhỏ nhất cũng phải được phát hiện ở một bước nào đó của chương trình.Quá trình kiểm tra và phát hiện lỗi phải được thực hiện trước khi lỗi đó hoành hành. Các loại lỗi thường xảy ra trong khi viết chương trình có thể được tổng kết lại như sau: Lỗi được thông báo bởi từ khóa error(lỗi cú pháp): loại lỗi này thường xảy ra trong khi soạn thảo chương trình,chúng ta có thể viết sai các từ khóa ví dụ thay vì viết là int chúng ta soạn thảo thành Int(lỗi chữ in thường thành in hoa.) hoặc viết sai cú pháp các biểu thức như thiếu các dấu ngoặc đơn,ngoặc kép hoặc dấu chấm phẩy khi kết thúc một lệnh hoặc chưa khai báo nguyên mẫu cho hàm. Lỗi được thông báo bởi từ khóa Warning(lỗi cảnh báo):Lỗi này thường xảy ra khi ta khai báo biến trong chương trình nhưng lại không sử dụng tới chúng,hoặc lỗi trong các biểu thức kiểm tra khi biến kiểm tra không xác định được giá trị của nó, hoặc lỗi do thứ tự ưu tiên các phép toán trong biểu thức.Hai loại lỗi error và warning được thông báo ngay khi dịch chương trình thành file*.OBJ.Quá trình liên kết (linker) các file*.OBJ để tạo nên file chương tình mã máy *.EXE chỉ được tiếp tục khi chúng ta hiệu đính và khử bỏ mọi lỗi error. Lỗi xảy ra trong quá trình liên kết:Lỗi này thường xuất hiện khi ta sử dụng tới các lời gọi hàm,nhưng những hàm đó mới chỉ tồn tại dưới dạng nguyên mẫu(function prototype) mà chưa được mô tả chi tiết trong hàm,hoặc những lời gọi hàm chưa đúng với tên của nó.Lỗ này được khắc phục khi ta bổ sung đoạn chương trình con mô tả chi tiết cho hàm hoặc sửa đổi lại những lời gọi hàm tương ứng. Ta quan niêm,lỗi cú pháp(error),lỗi cảnh báo(warning) và lỗi liên kết (linker) là lỗi tầm thường vì những lỗi này đã được Compiler của các ngôn ngữ lập trình phát hiện được.Để khắc phục các lỗi này,chúng ta chỉ cần đọc hiểu được những thông báo lỗi thường được viết bằng tiếng Anh.Cũng cần phải lưu ý rằng,do mức độ phức tạp của chương trình dịch nên không phải lỗi nào cũng được chỉ ra một cách tường minh và chính xác hoàn toàn tại nơi xuất hiện lỗi. Loại lỗi cuối cùng mà các compiler không thể phát hiện nổi đó do chính lập trình viên gây nên trong khi viết các chương trình và xử lý dữ liệu.Những lỗi này không được compiler thông báo mà nó phải trá giá bằng quá trình tự test hoặc chứng minh được tính đúng đắn của chương trình.Lỗi có thể nằm ở chính ý đồ thiết kế,hoặc lỗi do không lường trước tính chất của mỗi loại thông tin vào.Ví dụ sau minh họa cho lỗi xảy ra thuộc loại này. Ví dụ :Tính tổng hai đa thức A bậc n,đa thức B bậc m. #include #include #includ e #define MAX 100 typedef float dathuc[MAX]; void In(dathuc A, int n, char c){ int i; printf("\n Da thuc %c:", c); for(i=0;i<n; i++) printf("%6.2f", A[i]); } void Init( dathuc A, int *n, dathuc B, int *m){ int i;float temp ; printf("\n Nhap n="); scanf("%d", n);*n=*n+1; printf("\n Nhap m="); scanf("%d",m); *m=*m+1; printf("\n Nhap he so da thuc A:"); for(i=0; i<*n;i++){ printf("\n A[%d]=", i); scanf("%f", &temp); A[i]=temp; } printf("\n Nhap he so da thuc B:"); for(i=0; i<*m;i++){ printf("\n B[%d]=",i); scanf("%f", &temp); B[i] = temp; } In(A,*n ,'A'); In(B,*m,'B'); } void Tong(dathuc A, int n, dathuc B, int m, dathuc C){ int i, k; if (n>= m ){ k =n; for(i=0; i<m; i++) C[i] = A[i]+B[i]; for (i=m; i<n; i++) C[i]=A[i]; In(C,k,'C'); } else { k = m; for(i=0; i<n; i++) C[i] = A[i]+B[i]; for (i=n; i<m; i++) C[i]=B[i]; In(C,k,'C'); } } void main(void){ dathuc A, B, C; int n, m; Init(A, &n, B, &m); Tong(A, n, B, m, C); } Trong ví dụ trên,chúng ta sử dụng định nghĩa MAX =100 để giải quyết bài toán .MAX được hiểu là bậc của đa thức lớn nhất mà chúng ta cần xử lý.Như vậy,bản thân việc định nghĩa MAX đã hạn chế tới phạm vi bài toán,hạn chế đó cũng có thể xuất phát từ ý đồ thiết kế.Do vậy,nếu người sử dụng nhập n>MAX thì chương trình sẽ gặp lỗi.Nếu chúng ta khắc phục bằng cách định nghĩa B A,C đủ lớn thì trong trường hợp xử lý các đa thức có bậc nhỏ sẽ gây nên hiện tượng lãng phí bộ nhớ,và trong nhiều trường hợp không đủ bộ nhớ để định nghĩa đa thức.Giải pháp khắc phục các lỗi loại này thường là chúng ta sử dụng con trỏ thay cho các hằng. 7.Ứng dụng nguyên lý BOTTOM-UP trong lập trình. Đi từ cái riêng tới cái chung,từ các đối tượng thành phần ở mức cao tới các đối tượng thành phần ở mức thấp,từ mức đơn vị chương trình tới mức tổng thể,từ những đơn vị đã thiết lắp đặt những thành những đơn vị mới. Nếu như phương pháp TOP-DOWN là phương pháp phân rã vấn đề một cách có hệ thống từ trên xuống,được ứng dụng chủ yếu cho quá trình phân tích và thiết kế hệ thống,thì phương pháp Bottom-Up thương được sử dụng cho quá trình cài đặt hệ thống.Trong ví dụ trên,chúng ta sẽ không thể xây dựng được chương trình một cách hoàn chỉnh nếu như ta chưa xây dựng được các hàm Binary(a),Addition(a,b),Subtraction(a,b),Multial(a,b),Division(a,b),Modulation(a,b),USCLN(a,b).Chương trình sau thể hiện quá trình cài đặt theo nguyên lý Botton-Up: #include #include #include #includ e #include #include void Init(int *a, int *b){ printf("\n Nhap a=");scanf("%d", a); printf("\n Nhap b=");scanf("%d", b); } void Binary(int a){ int i, k=1; for(i=15 ; i>=0; i--){ if ( a & (k<<i)) printf("%2d",1); else printf("%2d",0); } printf("\n");delay(500); } int bit(int a, int k){ int j=1; if (a & (j<<k)) return(1); return(0); } int Addition(int a, int b){ int du, d, s, j, c=0; du=0; for ( j=0; j<=15; j++){ d =( bit(a,j) + bit(b, j) +du)/2; s = bit(a,j)+bit(b,j)+ du - 2*d; c = c | (s <<j); du = d; } return(c); } int Mu ltial(int a, int b) { int c,j, p=0; for(j=0; j<=15; j++){ c = bit(b, j); if (c==1) { c = a<<j; p= Addition(p, c); } else c=0; } return(p); } int Subtraction(int a, int b){ int c; b=-b; c=Addition(a,b);return(c); } int Modu l(int a, int b){ while(a>=b) a = Subtraction(a,b); return(a); } int Division(int a, int b){ int d=0; while(a>=b) { a= Subtraction(a,b); d++; } return(d); } int USCLN(int a, int b){ while(a!=b){ if(a>b) a = Subtraction(a,b); else b = Subtraction(b,a); } return(a); } void main(void){ int a, b, key, control=0; do { clrscr(); printf("\n Tap thao tac voi so nguyen"); printf("\n 1- Nhap hai so a,b"); printf("\n 2- So nhi phan cua a, b"); printf("\n 3- Tong hai so a,b"); printf("\n 4- Hieu hai so a,b"); printf("\n 5- Tich hai so a,b"); printf("\n 6- Thuong hai so a,b"); printf("\n 7- Phan du hai so a,b"); printf("\n 8- USCLN hai so a,b"); printf("\n 0- Tro ve"); key=getch(); switch(key){ case '1': Init(&a, &b); control=1; break; case '2': if (control){ Binary(a); Binary(b); } break; case '3': if (control) printf("\n Tong a+b = %d", Addition(a, b)); break; case '4': if (control) printf("\n Hieu a-b =%d", Subtraction(a, b)); break; case '5': if(control) printf("\n Tich a*b =%d", Multial(a,b)); break; case '6': if(control) printf("\n Chia nguyen a div b=%d",Division(a,b)); break; case '7': if(control) printf("\n Phan du a mod b =%d", Modul(a,b)); break; case '8': if(control) printf("\n Uoc so chung lon nhat:%d",USCLN(a,b)); break; } delay(1000); } while(key!='0'); } Phương pháp sáng tạo trong khoa học kĩ thuật nói chung và trong tin học nói riêng còn nhiều.Trên đây đã trình bày các phương pháp sáng tạo cơ bản.Để tìm hiểu sâu hơn chúng ta tìm đọc bộ sách. TÀI LIỆU THAM KHẢO. [1] Phan Dũng. Các thủ thuật(Nguyên tắc) sáng tạo cơ bản . Ủy ban khoa học và kỹ thuật TP.HCM, 1990 [2] Nguyễn Chân,Dương Xuân Thảo,Phan Dũng.Alorit sáng chế. NXB Ủy ban khoa học và kỹ thuật TP.HCM, 1990. [3] Phan Dũng . Làm thế nào để sáng tạo.Khoa học sáng tạo tự giới thiệu. . NXB Khoa H c K Thu t, 2003 [4] Phan Dũng .Phương pháp luận sáng tạo khoa học-kỹ thuật. Ủy ban khoa học và kỹ thuật TP.HCM, 1991. [5] Mark Allen Weiss. Data Structures and Algorithm Analysis In C. Prentice Hall,1996.