Ứng dụng các thủ thuật sáng tạo trong các bài toán tin học

Ứng dụng các thủ thuật sáng tạo trong các bài toán tin học Trang 2 TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN CAO HỌC CÔNG NGHỆ THÔNG TIN QUA MẠNG PHƯƠNG PHÁP NGHIÊN CỨU KHOA HỌC TRONG TIN HỌC ỨNG DỤNG CÁC THỦ THUẬT SÁNG TẠO TRONG CÁC BÀI TOÁN TIN HỌC Giảng viên: GS.TSKH Hoàng Kiếm Học viên thực hiện: Huỳnh Tuấn Anh CH1101004 Tp.HCM, 04/2012 Ứng dụng các thủ thuật sáng tạo trong các bài toán tin học TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN CAO HỌC CÔNG NGHỆ THÔNG TIN QUA MẠNG PHƯƠNG PHÁP NGHIÊN CỨU KHOA HỌC TRONG TIN HỌC ỨNG DỤNG CÁC THỦ THUẬT SÁNG TẠO TRONG CÁC BÀI TOÁN TIN HỌC Giảng viên: GS.TSKH Hoàng Kiếm Sinh viên thực hiện: Huỳnh Tuấn Anh CH1101004 Tp.HCM, 04/2012 Ứng dụng các thủ thuật sáng tạo trong các bài toán tin học Lời cám ơn. Em xin chân thành cám ơn GS.TSKH Hoàng Kiếm đã tận tình hướng dẫn, chỉ bảo chúng em trong suốt thời gian học chuyên đề này. Xin chân thành cám ơn quý thầy cô trong Trường Đại Học Công Nghệ Thông Tin, Đại Học Quốc Gia Tp.HCM đã tận tình giảng dạy, trang bị cho em những kiến thức quý báu, tạo mọi điều kiện tốt cho chúng em học tập và nghiên cứu. Xin chân thành cám ơn gia đình và bạn bè đã ủng hộ, giúp đỡ và động viên em trong thời gian học tập và nghiên cứu. Mặc dù đã cố gắng hoàn thành bài luận nhưng chắc chắn không tránh khỏi thiếu sót. Em kính mong nhận được sự thông cảm và tận tình chỉ bảo của quý thầy cô. Học viên thực hiện Huỳnh Tuấn Anh TpHCM, 04/2012 Ứng dụng các thủ thuật sáng tạo trong các bài toán tin học Mục Lục Lời nói đầu. .............................................................................................................................. 1 I. Tổng quan về phương pháp luận sáng tạo khoa học. ......................................................... 2 1. Khoa học: ........................................................................................................................ 2 2. Nghiên cứu khoa học: ..................................................................................................... 3 3. Phương pháp luận sáng tạo khoa học: ............................................................................. 3 4. Ý nghĩa, ích lợi của các thủ thuật sáng tạo cơ bản: ......................................................... 4 II. Các nguyên tắc (thủ thuật) sáng tạo và ứng dụng trong các bài toán tin học. ................... 7 III. Những sáng tạo trong công nghệ máy tính của tương lai. ............................................... 24 1. Máy tính quang học: ...................................................................................................... 24 2. Máy tính ADN: .............................................................................................................. 24 3. Máy tính nano: .............................................................................................................. 24 4. Máy tính phân tử và chấm: ............................................................................................ 25 5. Máy tính lượng tử:......................................................................................................... 25 6. Máy tính tích hợp trí thông minh nhân tạo: .................................................................. 25 Kết Luận. ............................................................................................................................... 27 Tài liệu tham khảo. ................................................................................................................ 28 Ứng dụng các thủ thuật sáng tạo trong các bài toán tin học Trang 1 Lời nói đầu. Ấn tượng sâu sắc do những lợi ích Phương pháp luận sáng tạo và đổi mới đem lại cho cá nhân mình, cùng với sự khuyến khích của thầy GS. Altshuller, GS. Phan Dũng đã cho ra đời bộ sách “Sáng tạo và đổi mới”, trong đó quyển “Các thủ thuật (nguyên tắc) sáng tạo cơ bản, Phần 1” trình bày các lợi ích của 40 thủ thuật sáng tạo cơ bản nhìn dưới góc độ các kiến thức cơ sở của phương pháp luận sáng tạo và đổi mới. Các thủ thuật sáng tạo nói riêng, phương pháp luận sáng tạo và đổi mới nói chung là hệ thống các công cụ. Chúng có những ảnh hưởng ngược lại với người sử dụng chúng. Ví dụ, chúng giúp người sử dụng tăng óc quan sát, tò mò sáng tạo; khắc phục tính ì tâm lý, tăng tính nhạy của việc tiếp thu, xử lý và đánh giá giá trị của thông tin; phát triển trí tưởng tượng sáng tạo; giúp xây dựng tư duy biện chứng – hệ thống… Như chúng ta đã biết, về nguyên tắc, sáng tạo, và đổi mới có thể nảy sinh ở bất kỳ lĩnh vực nào. Trong bài luận này, em sẽ trình bày ứng dụng 40 nguyên tắc sáng tạo trong tư duy của con người để giải quyết các vấn đề - bài toán trong tin học, đồng thời nói đến những sáng tạo trong công nghệ máy tính của tương lai, em xin chân thành cám ơn GS.TSKH Hoàng Kiếm, giảng viên đã dạy môn học Phương pháp luận sáng tạo khoa học, đã cung cấp cho em kiến thức để em hoàn thành bài luận này. Ứng dụng các thủ thuật sáng tạo trong các bài toán tin học Trang 2 I. Tổng quan về phương pháp luận sáng tạo khoa học. 1. Khoa học: Lịch sử phát triển khoa học từ xưa đến nay đã có nhiều quan niệm khác nhau về khoa học: - Aristote cho rằng : “Chỉ có cái tổng quát mới đáng gọi là khoa học”. - Furie: “Khoa học phải hướng tới cái chân lí tổng quát hoặc hơn nữa là cái tất yếu về cùng một đối tượng”. - Cuvrie:”Khoa học là hệ thống những nhận thức và nghiên cứu có phương pháp nhằm mục đích khám phá ra những qui luật tổng quát về các hiện tượng”. - “Khoa học là một hệ thống tri thức về tự nhiên, xã hội và tư duy được tích luỹ trong quá trình nhận thức trên cơ sở thực tiễn, được thể hiện bằng những khái niệm, phán đoán, học thuyết” [7]. - “Khoa học là hệ thống tri thức về mọi loại qui luật của vật chất và sự vận động của vật chất, những qui luật của tự nhiên, xã hội, tư duy” (Pierre Auger : Tendences actuelles de la recherche scientifique, UNESCO, Paris, 1961, tr 17-19). - “Khoa học là một hệ thống tri thức về tự nhiên, xã hội và tư duy, về những qui luật phát triển khách quan của tự nhiên, xã hội và tư duy, hệ thống tri thức này hình thành trong lịch sử và không ngừng phát triển trên cơ sở thực tiễn xã hội” [4]. Từ những quan niệm trên về ‘khoa học’, có lẽ chúng ta sẽ thống nhất với hai quan niệm sau của các tác giả: - Nguyễn Sinh Huy - Trần Trọng Thuỷ: “Khoa học là toàn bộ hệ thống kiến thức mà nhân loại đã tích luỹ được về những qui luật trong sự phát triển của thiên nhiên, của xã hội và tư duy, về những biện pháp tác động có kế hoạch đến thế giới xung quanh đến sự nhận thức và làm biến đổi thế giới đó nhằm phục vụ lợi ích cho con người” [3]. - Từ điển tiếng Việt: “Khoa học là một hệ thống tri thức tích lũy trong quá trình lịch sử và được thực tiễn chứng minh, phản ánh quy luật khách quan của thế giới bên ngoài cũng như của hoạt động tinh thần của con người, giúp con người có khả năng cải tạo thế giới hiện thực” [8]. Trên cơ sở khái niệm về khoa học được trình bày, chúng ta cũng cùng thống nhất niệm về nội dung của khoa học: tác giả Phạm Viết Vượng trong quan nhiệm về nội dung của khoa học: - Những tài liệu về thế giới do quan sát, điều tra, thí nghiệm mà có. - Những nguyên lí được rút ra dựa trên những sự kiện đã được thực nghiệm chứng minh. Ứng dụng các thủ thuật sáng tạo trong các bài toán tin học Trang 3 - Những qui luật, những học thuyết được khái quát bằng tư duy lí luận. - Những phương pháp nhận thức sáng tạo khoa học. - Những qui trình vận dụng lí thuyết khoa học vào sản xuất và đời sống xã hội. 2. Nghiên cứu khoa học: Theo Phạm Viết Vượng: “Bản chất của nghiên cứu khoa học là hoạt động sáng tạo của các nhà khoa học nhằm nhận thức thế giới, tạo ra hệ thống tri thức có giá trị để sử dụng vào cải tạo thế giới” [5]. Theo Vũ Cao Đàm: “Nghiên cứu khoa học là một hoạt động xã hội, hướng vào việc tìm kiếm những điều mà khoa học chưa biết, hoặc là phát hiện bản chất sự vật, phát triển nhận thức khoa học về thế giới; hoặc là sáng tạo phương pháp mới và phương tiện kĩ thuật mới để cải tạo thế giới” [9]. Từ quan niệm về NCKH của Vũ Cao Đàm và quan niệm về nội dung khoa học của Phạm Viết Vượng đã nêu ở trên, cho thấy NCKH có phạm vi vô cùng rộng lớn trong nhận thức và cải tạo thế giới. Nhưng điều đó không phải chỉ dành cho những nhà NCKH "chính hiệu”. 3. Phương pháp luận sáng tạo khoa học: Bill Gates là người giàu nhất và có lẽ, quyền lực nhất trong làng công nghệ. Trong 3 thập kỷ qua, ông đã có rất nhiều diễn văn, bình luận về kinh doanh, y tế toàn cầu và sự tiến hóa của ngành công nghiệp máy tính... Có một câu nói đáng nhớ của "ông vua" đế chế Microsoft này. Đó là: “Tôi nghĩ sẽ không ngoa khi nói rằng máy tính cá nhân là công cụ mạnh nhất mà con người từng tạo ra. Chúng là công cụ thông tin liên lạc, là công cụ sáng tạo và có thể do người dùng mặc sức tùy biến”. (Phát biểu tại Đại học Illinois, tháng 2/2004). 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à Ơristic (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. Ứng dụng các thủ thuật sáng tạo trong các bài toán tin học Trang 4 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. 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. 4. Ý nghĩa, ích lợi của các thủ thuật sáng tạo cơ bản: Edison tìm cái kim trong đống rơm: cho đến nay Edison vẫn là người có nhiều sáng chế nhất: hơn 1000 sáng chế. Ông không làm việc một mình mà cả một tập thể lớn làm việc cho ông. Phương pháp tư duy sáng tạo của ông là phương pháp thử-sai (trial–and–error method), nghĩa là lựa chọn lần lượt các phương án giải một cách mò mẫn và dùng số lượng lớn các phép thử để bù khả năng định hướng. Để sáng tác ra ắc quy kiềm, Edison đã làm hơn 50000 thí nghiệm. Nhà sáng chế Nikolai Tesla, có thời gian làm việc chung với Edison đã viết: “Nếu như Edison cần tìm cái kim rớt trong đống rơm, ông ta sẽ không mất thời gian để suy nghĩ xem khả năng lớn nhất cái kim sẽ nằm ở đâu. Không chậm trễ, với sự siêng năng vội vã của con ong, ông ta sẽ xem xét từng cọng rơm một cho tới khi tìm thấy cây kim thì thôi. Cách làm việc của ông rất kém hiệu quả: ông có thể bỏ ra rất nhiều thời gian và sức lực mà không thu được kết quả gì”. Trong bất kỳ lĩnh vực nào, thông qua việc giải thành công nhiều bài toán, người ta đều có thể rút ra được các kinh nghiệm, “bí quyết”, “mẹo” giúp giải quyết các vần đề trong lĩnh vực đó nhanh hơn, hiệu quả hơn so với phương pháp thử và sai. Những kinh nghiệm, “bí quyết”, “mẹo” như vậy được gọi là các thủ thuật (thủ pháp) sáng tạo (Heuristic Technique), hay gọi tắt là các thủ thuật. Nói cách khác, các thủ thuật có thể được coi là các phương pháp nhỏ, đơn giản nhất. Trong quyển “Các thủ thuật sáng tạo cơ bản, Phần 1”, GS. Phan Dũng tập trung trình bày hệ thống các thủ thật sáng tạo cơ bản của G.S Altshuller. Đây là bộ sưu tập các thủ thuật được đánh giá rất cao trong lĩnh vực sáng tạo và đổi mới hiện nay, do đã khắc phục một cách đáng kể các hạn chế và có nhiều ưu việt hơn các bộ sưu tập khác. Từ năm 1946, GS. Altshuller bắt đầu sưu tập các thủ thuật nhằm mục đích giúp cá nhân mình làm các sáng chế với năng suất và hiệu quả cao hơn. Đến năm 1948, ông đặt mục đích rộng hơn: Xây dựng lý thuyết và hệ thống các phương pháp giải các bài toán sáng tạo sáng chế (TRIZ) cho đông đảo mọi người. Ngày từ thời kỳ đó, ông đã nhận ra rằng, sáng tạo sáng chế chính là Ứng dụng các thủ thuật sáng tạo trong các bài toán tin học Trang 5 giải quyết các mâu thuẫn kỹ thuật, tạo ra sự phát triển. Do vậy, tiêu chuẩn lựa chọn các thủ thuật được GS. Altshuller xác định là: Chúng phải có khả năng giải quyết các mâu thuẫn kỹ thuật có trong các bài toán sáng tạo sáng chế. Kể từ năm 1946, số lượng các thủ thuật được GS. Altshuller tìm ra tăng dần theo thời gian. Đến đầu những năm 1970, sau nhiều lần bổ sung, chỉnh sửa, hoàn thiện nội dung và lời phát biểu các thủ thuật, phương án được chọn dùng từ đó đến nay là hệ thống 40 thủ thuật sáng tạo cơ bản. Mỗi thủ thuật cung cấp cho người sử dụng một (hoặc vài) các xem xét đối tượng cho trước. Như vậy, 40 thủ thuật sáng tạo cung cấp cho bạn hệ thống các cách xem xét sự vật. Các xem xét này giúp bạn khắc phục tính ì tâm lý, tạo những đường suy nghĩ giúp tăng tính nhạy bén tư duy, giúp phát hiện và sử dụng các nguồn dự trữ có sẵn trong đối tượng (hệ thống). Các thủ thuật giúp người sử dụng phát các ý tưởng sáng tạo, đưa ra cái mới mà đối tượng tiền thân hiện tại chưa có. Ngoài ra, GS. Phan Dũng muốn nhấn mạnh loại ích lợi do các thủ thuật đem lại cho người sử dụng, nếu người sử dụng có ý thức coi chính mình cũng là đối tượng cần cải tiến, hoàn thiện, phát triển. Phương pháp luận sáng tạo và đổi mới nói chung không chỉ dùng để cải tiến những gì bên ngoài con người mà người sử dụng có thể và cần dùng chúng một cách có ý thức để cải tiến, hoàn thiện, phát triển chính bản thân mình. Sau đây là tập hợp một cách tóm tắt các lợi ích của các thủ thuật sáng tạo nói riêng, phương pháp luận sáng tạo và đổi mới nói chung: - Cung cấp hệ thống các cách xem xét sự vật. - Tăng óc quan sát, tò mò sáng tạo. - Phân tích, lý giải một cách logich những giải pháp sáng tạo đã có. - Tăng tính nhanh nhạy của việc tiếp thu và đánh giá giá trị của thông tin. - Thấy được sự tương tự, thống nhất giữa các hệ thống tưởng chừng rất khác xa nhau. - Khắc phục tính ì tâm lý. - Giúp phát hiện các nguồn dự trữ có sẵn trong hệ, đặc biệt các nguồn dự trữ trời cho không mất tiền sử dụng. - Đưa ra và lựa chọn các cách tiếp cận thích hợp để giải bài toán. - Giải quyết các mâu thuẫn có trong bài toán. - Phát các ý tưởng cải tiến hệ thống cho trước. - Dự báo khuynh hướng phát triển của hệ thống cho trước trong tương lai, xây dựng cơ chế định hướng trong dư duy sáng tạo. - Giúp phát hiện, đặt và lựa chọn bài toán cần giải. - Dùng để luyện tập phát triển trí tưởng tượng sáng tạo. Ứng dụng các thủ thuật sáng tạo trong các bài toán tin học Trang 6 - Dùng để cải tiến, hoàn thiện, phát triển chính bản thân, xây dựng tác phong, suy nghĩ và làm việc một cách khoa học, sáng tạo. - Góp phần xây dựng tư duy biện chứng – hệ thống. - Làm giảm thiểu số lượng các bài toán không đáng nảy sinh. Ứng dụng các thủ thuật sáng tạo trong các bài toán tin học Trang 7 II. Các nguyên tắc (thủ thuật) sáng tạo và ứng dụng trong các bài toán tin học. 1. Nguyên tắc phân nhỏ: Nội dung: - Chia các đối tượng thành các phần độc 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. Ứng dụng trong tin học: - Ứng dụng nguyên tắc trên (trong tin học) vào việc sắp xếp dãy (Quick Sort), hay tìm kiếm nhị phân, mỗi lần tìm kiếm ta chia đôi dãy phần tử, khi đó ta chỉ tìm trên nữa dãy. Nguyên tắc này sẽ cải thiện tốc độ tìm kiếm và độ phức tạp thuận toán sẽ được cải thiện đáng kể. - Ứng dụng quen thuộc nhất chính là chia chương trình thành nhiều chức năng nhỏ, còn được gọi là “hàm” hay “thủ tục”. - Đưa các hàm và thuộc tính tương tự về mặt chức năng vào một mô-đun độc lập. - Tăng độ mịn của các thành phần chương trình (code, data) cho đến khi đạt được ngưỡng nguyên tử. (Ngưỡng nguyên tử là đơn vị cấu trúc nhỏ nhất của một đối tượng hay thành phần, ví dụ: bit có thể xem là ngưỡng nguyên tử trong một sơ đồ mã hóa). 2. Nguyên tắc “tách khỏi”: Nội dung: - Tách phần gây “phiền phức” (tính chất “phiền phức”) hay ngược lại, tách phần duy nhất “cần thiết” (tính chất “cần thiết”) ra khỏi đối tượng. Ứng dụng trong tin học: - Hệ thống ERP cũng áp dụng nguyên tắc trên: Do hệ thống bao gồm nhiều Module (phân hệ), mỗi phân hệ có thể sử dụng riêng cho từng yêu cầu như : Phân hệ Kế toán có thể dùng riêng cho lãnh vực kế toán, phân hệ nguồn nhân lực, phân hệ sản xuất … Khi đó công ty có thể dùng toàn bộ hệ thống cho công việc của mình, nhưng cũng có thể dùng một hay một vài module nào đó cần thiết cho công việc của mình thôi để giảm bớt chi phí. - Trích văn bản trong hình ảnh. Giải thuật khi họat động không biết trước hướng, kích thước, phông chữ. Do đó cần phải lọai bỏ phần ảnh nền và phân lập vùng ảnh có chứa văn bản. - Phân tích cú pháp là quá trình trong đó dữ liệu vào được tách ra thành từng phần nhỏ, các phần nhỏ càng tách biệt càng dễ cho quá trình biên dịch. Ứng dụng các thủ thuật sáng tạo trong các bài toán tin học Trang 8 3. Nguyên tắc phẩm chất cục bộ: Nội dung: - Chuyển đối tượng (hay môi trường bên ngoài, tác động bên ngoài) có cấu trúc đồng nhất thành không đồng nhất. - Các phần khác nhau của đối tượng phải có những chức năng khác nhau. - Mỗi phần của đối tượng phải ở trong những điều kiện thích hợp nhất đối với công việc. Ứng dụng trong tin học: - Trong lập trình, trong một đoạn chương trình cần phân biệt phẩm chất cục bộ : ở đâu là phần lỏi của chương trình, phần khác là những thao tác phụ. Ví dụ : In tất cả các số chia hết cho 9 trong phạm vi [1..10000], với hình thức in ra: Mỗi hàng có 10 số, mỗi trang có 20 hàng, tạm dừng chờ nhấn phím liệt tiếp trang sau (nếu hơn trang). Như vậy nếu chương có lỗi thì lỗi thì lỗi của chương trình (phẩm chất cục bộ) là phần kiểm tra một số chia hết cho 9, chứ không phải là phần in ra. - Trong lập trình hướng đối tượng , chúng ta có các phương thức, mà mỗi phương thức có những tính năng khác nhau. - Phương pháp lấy mẫu không đồng nhất trong việc nhận dạng ký tự: Trong việc nhận dạng các mẫu, người ta lấy mẫu theo hướng vuông góc với hướng cho trước theo khỏang cách không đồng nhất để tránh nhận dạng sai 2 dòng gần nhau như là 1 dòng. - Trong việc truyền không dây, thông tin được phát sóng lên các kênh truyền thông đến các máy nhận sử dụng năng lượng hạn chế (pin..). Để tiết kiệm năng lượng, thông tin truyền đi phải được tổ chức sao cho các máy nhận có thể tự chọn lọc tiếp nhận trong một chu lỳ bất kỳ của quá trình phát. Hầu hết các kỹ thuật hiện nay dùng cách phát sóng đồng nhất. Tuy nhiên, thông thường một lượng nhỏ thông tin lại được rất nhiều máy thu tiếp nhận trong khi một lượng lớn còn lại rất ít được sử dụng. Do đó người ta sủ dụng giải pháp phát không đồng nhất tùy theo tính chất của hệ thống. 4. Nguyên tắc phản (bất) đối xứng: Nội dung: