Ứng dụng các phương pháp, nguyên tắc sáng tạo để giải quyết các vấn đề - Bài toán trong tin học

TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN CHƯƠNG TRÌNH ĐÀO TẠO THẠC SĨ CNTT QUA MẠNG BÀI THU HOẠCH PHƯƠNG PHÁP NGHIÊN CỨU KHOA HỌC TRONG TIN HỌC  ỨNG DỤNG CÁC PHƯƠNG PHÁP, NGUYÊN TẮC SÁNG TẠO ĐỂ GIẢI QUYẾT CÁC VẤN ĐỀ - BÀI TOÁN TRONG TIN HỌC Học viên thực hiện: Giảng viên : GS.TSKH. HOÀNG KIẾM Học viên : TRỊNH QUỐC HÙNG Mã học viên : CH1101088 Mục lục LỜI MỞ ĐẦU ............................................................................................................................................. 4 CHƯƠNG 1: KHÁI NIỆM CƠ BẢN VỀ KHOA HỌC VÀ NGHIÊN CỨU KHOA HỌC ......................................... 5 I. KHOA HỌC LÀ GÌ? ............................................................................................................................... 5 1.2 Tiêu chí nhận biết một bộ môn khoa học ..................................................................................... 5 1.3 Phân loại khoa học ...................................................................................................................... 6 II. KỸ THUẬT VÀ CÔNG NGHỆ LÀ GÌ? ..................................................................................................... 8 2.1 Công nghệ .................................................................................................................................. 8 2.2 Kỹ thuật ...................................................................................................................................... 8 2.3 Phân biệt khoa học, kỹ thuật và công nghệ .................................................................................. 8 III. NGHIÊN CỨU KHOA HỌC LÀ GÌ ....................................................................................................... 9 3.1 Chức năng cơ bản của nghiên cứu khoa học ................................................................................ 9 3.2 Các đặc điểm của nghiên cứu khoa học ....................................................................................... 9 3.3 Các loại hình nghiên cứu khoa học .............................................................................................. 9 3.4 Các bước nghiên cứu................................................................................................................. 10 CHƯƠNG 2: VẤN ĐỀ KHOA HỌC & CÁC PHƯƠNG PHÁP GIẢI QUYẾT .................................................... 12 I. VẤN ĐỀ KHOA HỌC ......................................................................................................................... 12 1.1 Khái niệm ................................................................................................................................. 12 1.2 Phân loại ................................................................................................................................... 12 1.3 Các tình huống vấn đề ............................................................................................................... 12 1.4 Các phương pháp phát triển vấn đề khoa học ............................................................................. 12 II. PHƯƠNG PHÁP GIẢI QUYẾT VẤN ĐỀ-BÀI TOÁN PHÁT MINH, SÁNG CHẾ ........................................ 13 2.1 Năm phương pháp ..................................................................................................................... 15 2.2 Bốn mươi thủ thuật ................................................................................................................... 15 III. PHƯƠNG PHÁP GIẢI QUYẾT VẤN ĐỀ- BÀI TOÁN TỔNG QUÁT .................................................... 16 3.1 Mô hình thông tin ban đầu ........................................................................................................ 16 3.2 Các phương pháp phân tích vấn đề ............................................................................................ 17 Ví dụ về xử lý hình ảnh ............................................................................................................................ 17 3.3 Các phương pháp tổng hợp vấn đề............................................................................................. 19 IV. PHƯƠNG PHÁP GIẢI QUYẾT VẤN ĐỀ-BÀI TOÁN TIN HỌC .......................................................... 21 4.1 Phương pháp trực tiếp: .............................................................................................................. 21 4.2 Phương pháp gián tiếp:.............................................................................................................. 22 Một số ví dụ áp dụng các phương pháp giải quyết vấn đề trong lĩnh vực tin học: ............................... 25 Tài liệu thao khảo: ................................................................................................................................... 45 LỜI MỞ ĐẦU Nghiên cứu khoa học (NCKH) là một hoạt động then chốt hàng đầu trong những ngành khoa học. Kết quả từ NCKH là những phát hiện mới về kiến thức, về bản chất sự vật, phát triển nhận thức khoa học về thế giới, sáng tạo phương pháp và phương tiện kỹ thuật mới có giá trị cao. Ngày nay khi mà với sự tiến bộ của khoa học kỹ thuật làm thế giới trở nên bình đẳng hơn, các biên giới quốc gia chỉ còn giá trị về địa lý thì cơ hội thành công là rất rõ rệt với tất cả mọi người. Do đó việc nắm vững phương pháp, nguyên lý sáng tạo có thể coi như là chìa khoá để mở cánh cửa thành công. Chỉ cẩn giải quyết được một vấn đề nào đó cũng có thể làm nên cuộc cách mạng công nghệ mới. Em xin chân thành cám ơn GS. TSKH thầy Hoàng Kiếm, đã cho em một kiến thức thật bổ ích qua môn học này, đã làm thay đổi, mở mang tư duy của em trong mọi vấn đề. Không chỉ là những vấn đề trong tin học mà còn tất cả những vấn đề trong mọi lĩnh vực, đời sống hằng ngày. CHƯƠNG 1: KHÁI NIỆM CƠ BẢN VỀ KHOA HỌC VÀ NGHIÊN CỨU KHOA HỌC I. KHOA HỌC LÀ GÌ? 1.1 Khoa học - 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 và tư duy (Pierre Auger –Tendences actuelles de la recherche scientifique, UNESCO, Paris, 1961). - Khoa học là quá trình nghiên cứu nhằm khám phá ra những kiến thức mới, học thiết mới…về tự nhiên và xã hội. Những kiến thức hay học thiết mới này tốt hơn, có thể thay thế cái củ không còn phù hợp. - 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. Phân biệt ra hai hệ thống tri thức: tri thức kinh nghiệm và tri thức khoa học.  Tri thức kinh nghiệm: là những hiểu biết được tích lũy qua hoạt động sống hang ngày trong mới quan hệ giữa con người với con người và giữa con người với thiên nhiên. Quá trình này giúp con người hiểu biết về sự vật, về cách quản lý thiên nhiên và hình thành mối quan hệ giữa những con người trong xã hội. Tri thức kinh nghiệm được con người không ngừng sử dụng và phát triển trong hoạt động thực tế. Tuy nhiên, tri thức kinh nghiệm chưa thật sự đi sâu vào bản chất, chưa thấy được hết các thuộc tính của sự vật và mối quan hệ bên trong giữa sự vật và con người. Vì vậy, tri thức kinh nghiệm chỉ phát triển đến một hiểu biết giới hạn nhất định, nhưng tri thức kinh nghiệm là cơ sở cho sự hình thành tri thức khoa học.  Tri thức khoa học: là những hiểu biết được tích lũy một cách có hê thống nhờ hoạt động nghiên cứu khoa học, các hoạt động này có mục tiêu xác định và sử dụng phương pháp khoa học. Không giống như tri thức kinh nghiệm, tri thức khoa học dựa trên kết quả khảo sát thu thập được qua những thí nghiệm và qua các sự kiện xảy ra ngẫu nhiên trong hoạt động xã hội, trong tự nhiên. Tri thức khoa học được tổ chức trong khuôn khổ các ngành và bộ môn khoa học (discipline) như: triết học, sử học, kinh tế học… 1.2 Tiêu chí nhận biết một bộ môn khoa học Các tiêu chí nhận biết một bộ môn khoa học - Có đối tượng để nghiên cứu? - Có hệ thống lý thuyết? - Có hệ thống phương pháp luận hay không? - Có mục đích sử dụng hay không? 1.3 Phân loại khoa học Sự phân loại các khoa học dựa trên: - Nguồn gốc (lý thuyết, thực nghiệm, thực chứng…) - Mục đích ứng dụng (mô tả, phân tích, tổng hợp, sáng tạo…) - Mức độ khái quát (cụ thể, trừu tượng, tổng quát…) - Tính tương liên (liên ngành, đa ngành…) - Cơ cấu hệ thống tri thức (cơ sở, cơ bản, chuyên ngành…) - Đối tượng nghiên cứu (tự nhiên, kỹ thuật, xã hội nhân văn, công nghệ, nông nghiệp, y học…) Phân loại ARISTOTE(384-322 trước công nguyên) Khoa học lý thuyết Khoa học sáng tạo Khoa học thực hành Mục đích Tìm hiểu thực tại Sáng tạo tác phẩm Hướng dẫn đời sống - Siêu hình học - vật lý học - Từ từ học - Thi pháp - Biện chứng pháp - Đạo đức học - Kinh tế học - Chính trị học Phân loại của COMTE (1798-1857) Toán học Thiên văn học Vật lý học Hóa học Sinh vật học Xã hội học Tính trừu tượng và phổ quát tăng dần Tính cụ thể và phức tạp tăng dần Phân loại Marx (1818 - 1883) Marx chia khoa học ra làm nhóm: - Khoa học tự nhiên có đối tượng là các dạng vật chất và hình thức vận động của các dạng vật chất đó được thể hhiện trong giới tự nhiên cũng như mối liên hệ và quy luật của chúng: cơ học, vật lý học, hóa học, sinh vật học, toán học,… - Khoa học xã hội hay khoa học về con người có đối tượng là những sinh họat của con người, những quan hệ xã hội… cùng các quy luật và những động lực của sự phát triển xã hội: sử học, kinh tế học, chính trị học đạo đức học, mỹ học,… bao trùm tất cả các khoa học vừa kể chính là chủ nghĩa duy vật lịch sử. II. KỸ THUẬT VÀ CÔNG NGHỆ LÀ GÌ? 2.1 Công nghệ Công nghệ: technoware + infoware + humanware + organware 2.2 Kỹ thuật Kiến thức kinh nghiệm, kỹ năng có tính chất hệ thống, Phương pháp trình tự tác nghiệp, phương tiện 2.3 Phân biệt khoa học, kỹ thuật và công nghệ TT KHOA HỌC CÔNG NGHỆ 1 Nghiên cứu khoa học mang tính xác suất Điều hành công nghệ mang tính xác định 2 Hoạt động khoa học luôn đổi mới, không lặp lại Hoạt động công nghệ được lặp lại theo chu kỳ 3 Sản phẩm khó được định hình trước Sản phẩm được định hình theo thiết kế 4 Sản phẩm mang đặc trưng thông tin Đặc trưng sản phẩm tùy thuộc đầu vào 5 Lao động linh họat và tính sáng tạo cao Lao động bị định khuôn theo qui định 6 Có thể mang mục đích tự thân Có thể không mang mục đích tự thân 7 Phát minh khoa học tồn tại mãi mãi với thời Sáng chế công nghệ tồn tại nhất thời và bị tiêu gian vong theo lịch sử tiến bộ kỹ thuật III. NGHIÊN CỨU KHOA HỌC LÀ GÌ Nghiên cứu khoa học là một họat động tìm kiếm, xem xét, điều tra, hoặc thử nghiệm. Dựa trên những số liệu, tài liệu, kiến thức…đạt được từ các thí nghiệm nghiên cứu khoa học để phát hiện ra những cái mới về bản chất sự vật, về thế giới tự nhiên và xã hội, và để sáng tạo phương pháp và phương tiện kỹ thuật mới cao hơn, giá trị hơn. 3.1 Chức năng cơ bản của nghiên cứu khoa học - Mô tả (định tính, định lượng) - Giải thích (thuộc tính, nguồn gốc, quan hệ…) - Dự đoán - Sáng tạo (các giải pháp cải tạo thế giới) 3.2 Các đặc điểm của nghiên cứu khoa học - Tính mới - Tính tin cậy - Tính thông tin - Tính khách quan - Tính rủi ro - Tính thừa kế - Tính cá nhân - Tính phi kinh tế 3.3 Các loại hình nghiên cứu khoa học - Nghiên cứu cơ bản (phát hiện bản chất, qui luật…) + Thuần túy (tự do) + Định hướng o Nền tảng: dịch tễ học, điều tra cơ bản… o Chuyên đề: plasma, Gen di truyền  Phát minh - Nghiên cứu ứng dụng Sự vận dụng các qui luật từ nghiên cứu cơ bản đến các nguyên lý về các giải pháp (công nghệ, vật liệu, tổ chức, quản lý…)  Sáng chế: giải pháp kỹ thuật có tính mới và áp dụng được - Nghiên cứu triển khai (R & D)  Các hình mẫu mang tính khả thi về kỹ thuật 3 mức độ triển khai (Labo, pilot,  ) 3.4 Các bước nghiên cứu - Xác lập vấn đề nghiên cứu: o Chọn và cụ thể hóa đề tài o Xác định cơ sở lý thuyết cho nghiên cứu o Nghiên cứu lịch sử vấn đề - Giai đọan chuẩn bị nghiên cứu: o Chuẩn bị điều kiện nghiên cứu o Thiết lập danh mục tư liệu - Lựa chọn và nghiên cứu thông tin: o Thu thập và xử lý thông tin o Nghiên cứu tư liệu o Thâm nhập thực tế o Tiếp xúc cá nhân Nghiên cứu cơ bản Nghiên cứu ứng dụng Triển khai Nghiên cứu cơ bản thuần túy Nghiên cứu cơ bản định hướng Triển khai trong phòng thí nghiệm Nghiên cứu nền tảng Nghiên cứu chuyên đề Triển khai bán đại trà Quan hệ giữa các loại hình nghiên cứu o Xử lý thông tin - Xây dựng giả thuyết, lựa chọn phương pháp và lập kế hoạch: o Xây dựng giả thuyết. o Xác định phương pháp luận nghiên cứu o Lập kế hoạch - Hoàn tất nghiên cứu: o Đề xuất và xử lý thông tin o Xây dựng kết luận và khuyến nghị - Viết báo cáo hòan tất công trình: o Sắp xếp tư liệu o Viết báo cáo - Giai đoạn kết thúc o Hoàn tất công tác o Áp dụng kết quả CHƯƠNG 2: VẤN ĐỀ KHOA HỌC & CÁC PHƯƠNG PHÁP GIẢI QUYẾT I. VẤN ĐỀ KHOA HỌC 1.1 Khái niệm Vấn đề khoa học (scientific problem) cũng được gọi là vấn đề nghiên cứu (research problem) hoặc câu hỏi nghiên cứu là câu hỏi được đặt ra khi người nghiên cứu đứng trước mâu thuẫn giữa tính hạn chế của tri thức khoa học hiện có với yêu cầu phát triển tri thức đó ở trình độ cao hơn. 1.2 Phân loại Nghiên cứu khoa học luôn tồn tại hai vấn đề: - Vấn đề về bản chất sự vật đang tìm kiếm - Vấn đề về phương pháp nghiên cứu để làm sáng tỏ về lý thuyết và thực tiễn những vấn đề thuộc lớp thứ nhất. 1.3 Các tình huống vấn đề Có ba tình huống: Có vấn đề, không có vấn đề, giả vấn đề được cho trong hình dưới đây: 1.4 Các phương pháp phát triển vấn đề khoa học Có sáu phương pháp: 1) Tìm những kẻ hở, phát hiện những vấn đề mới 2) Tìm những bất đồng 3) Nghĩ ngược lại quan niệm thông thường 4) Quan sát những vướng mắc trong thực tiễn Có vấn đề Có nghiên cứu Không có vấn đề Không có nghiên cứu Giả vấn đề Không có vấn đề Không có Nghiên cứu Nảy sinh vấn đề khác Nghiên cứu theo một hướng khác 5) Lắng nghe lời kêu ca phàn nàn 6) Cảm hứng : những câu hỏi bất chợt xuất hiện khi quan sát sự kiện nào đó. II. PHƯƠNG PHÁP GIẢI QUYẾT VẤN ĐỀ-BÀI TOÁN PHÁT MINH, SÁNG CHẾ Một tiếp cận không gian giải quyết vấn đề Ý tưởng  bài toán  mô hình  cách giải Bài toán P: Sau khi có ý tưởng, bài toán P được đặt ra nhằm giải quyết mục đích cuối cùng là gì. Điểm nhìn: nơi có vị trí, tầm nhìn khách quan nhất, bao quát vấn đề để khi giải quỵết không còn sai sót hoặc sai sót ít có thể chấp nhận được. Không gian vấn đề: Bài toán P đặt trong không gian vấn đề sao cho không quá phức tạp, nhưng cũng không thể đơn giản quá dẫn tới sai sót Vepol  “Bất cứ hệ thống kỹ thuật nào ít nhất cũng phải có hai thành phần vật chất tác động tương hổ và một loại trường hay năng lượng” Từ đó có một thuật ngữ về tam giác kỹ thuật gọi là tam giác Vepol. Vepol là mô hình hệ thống kỹ thuật. Vepol được quy ước đưa ra cốt chỉ để phản ánh một tính chất vật chất của hệ thống nhưng là chủ yếu nhất với bài toán đã cho. Bài toán P Điểm nhìn Không gian vấn đề Tuy nhiên, một hệ thống ban đầu chưa hẳn đã có một chuẩn Vepol đủ 3 yếu tố trên, hoặc đã đủ thì có thể phát triển gì thêm trên Vepol đó. 2.1 Năm phương pháp - Dựng Vepol đầy đủ - Chuyển sang Fepol - Phá vở Vepol - Xích Vepol - Liên trường 2.2 Bốn mươi thủ thuật 1. Nguyên lý phân nhỏ 2. Nguyên lý “tách riêng” 3. Nguyên lý phẩm chất cục bộ 4. Nguyên lý phản đối xứng 5. Nguyên lý kết hợp 6. Nguyên lý vạn năng 7. Nguyên lý chứa trong 8. Nguyên lý phản trọng lượng 9. Nguyên lý gây ứng suất sơ bộ 10. Nguyên lý thực hiện sơ bộ 11. Nguyên lý dự phòng 12. Nguyên lý đẳng thế 13. Nguyên lý đảo ngược 14. Nguyên lý cầu (tròn) hóa 15. Nguyên lý năng động 16. Nguyên lý tác động bộ phận và dư thừa 17. Nguyên lý chuyển sang chiều khác 18. Sự dao động cơ học 19. Nguyên lý tác động theo chu kỳ 20. Nguyên lý tác động liên tục hữu hiệu 21. Nguyên lý vượt nhanh 22. Nguyên lý chuyển bại thành thắng 23. Nguyên lý quan hệ phản hồi 24. Nguyên lý sử dụng trung gian 25. Nguyên lý tự phục vụ 26. Nguyên lý sao chép (copy) 27. Nguyên lý rẻ thay cho đắt 28. Nguyên lý thay thế sơ đồ cơ học 29. Nguyên lý sử dụng các kết cấu thủy và khí 30. Sử dụng vỏ dẻo và màng mỏng 31. Sử dụng vật liệu nhiều lỗ 32. Nguyên lý đổi màu 33. Nguyên lý đồng nhất 34. Nguyên lý loại bỏ và tái sinh từng phần 35. Đổi các thông số hóa lý của đối tượng 36. Sử dụng chuyển pha 37. Sử dụng nở nhiệt 38. Sử dụng các chất oxy hóa 39. Sử dụng môi trường trơ 40. Sử dụng vật liệu tổng hợp (composit) III. PHƯƠNG PHÁP GIẢI QUYẾT VẤN ĐỀ- BÀI TOÁN TỔNG QUÁT 3.1 Mô hình thông tin ban đầu Phân tích Phân chia Phân cp Phân tích Phân loi 3.2 Các phương pháp phân tích vấn đề a) Phân chia vấn đề: Ví dụ: tìm cặp điểm gần nhau nhất trong tập n điểm b) Phân loại vấn đề: Ci(P) = U Ci(P) Ci(P) : p P ,T(P) (class có thể phủ nhau) (class, classure) Ví dụ: nhận dạng chữ in Loại 2 chân : I Loại 3 chân : A, L, V, … c) Phân công vấn đề: Là một biến thể của nguyên lý phân nhỏ vấn đề Vấn đề A  { A1, A2,…, An} P  { P1, P2,…, Pn} d) Phân cấp bài toán: Bài toán P  cấu trúc lại bài toán P’ Mô tả thô  Mô tả tinh Ví dụ về xử lý hình ảnh Tìm xem một ảnh A nằm ở đâu trong ảnh B e) Phân tích: 3.3 Các phương pháp tổng hợp vấn đề Tổng hợp theo không gian và thời gian Để giải quyết vấn đề khoa học, ngược lại với phương pháp phân tích là phương tổng hợp. Tổng hợp ở đây bao gồm cả tổ hợp, kết hợp, đối hợp và tích hợp. Tùy thuộc vấn đề, yêu cầu của bài toán, ta có thể áp dụng việc tổ hợp hay kết hợp hay đối hợp hay tích hợp. Các thông tin thu nhận được sẽ được tổng hợp theo không gian hay thời gian hay kết hợp cả hai để được một thông tin mới gíup cho việc giải quyết các vấn đề của bài toán. IV. PHƯƠNG PHÁP GIẢI QUYẾT VẤN ĐỀ-BÀI TOÁN TIN HỌC 4.1 Phương pháp trực tiếp: Đặc điểm của cách giải quyết vấn đề này là đều xác định trực tiếp được lời giải qua một thủ tục tính toán (công thức, hệ thức, định luật,…) hoặc qua các bước căn bản để có được lời giải. Đối với phương pháp này, việc giải quyết vấn đề trên máy tính chỉ là thao tác lập trình hay là sự chuyển đổi lời giải từ ngôn ngữ bên ngoài sang các ngôn ngữ được sử dụng trong máy tính. Tìm hiểu về phương pháp này chính là tìm hiểu về kỹ thuật lập trình trên máy tính. Để thực hiện tốt phương pháp trực tiếp, chúng ta nên áp dụng các nguyên lý sau : - Nguyên lý 1 : Chuyển đổi dữ liệu bài toán thành dữ liệu của chương trình, có nghĩa là “Dữ liệu của bài toán sẽ được biểu diễn lại dưới dạng các biến của chương trình thông qua các quy tắc xác định của ngôn ngữ lập trình cụ thể “. - Nguyên lý 2 : Chuyển đổi quá trình tính toán của bài toán thành các cấu trúc của chương trình, có nghĩa là “Mọi quá trình tính toán đều có thể mô tả và thực hiện dựa trên ba cấu trúc cơ bản : Cấu trúc tuần tự, cấu trúc rẽ nhánh và cấu trúc lặp ”. - Nguyên lý 3 : Biểu diễn các tính toán chính xác, có nghĩa là “Chương trình tính toán theo các biểu thức chính xác không đồng nhất với quá trình tính toán chính xác về mặt hình thức ”. - Nguyên lý 4 : Biểu diễn các tính toán gần đúng bằng cấu trúc lặp, có nghĩa là “Mọi quá trình tính toán gần đúng đều dựa trên các cấu trúc lặp với tham số xác định ”. - Nguyên lý 5 : Phân chia bài toán ban đầu thành những bài toán nhỏ hơn, có nghĩa là “Mọi vấn đề - bài toán đều có thể giải quyết bằng cách phân chia thành những vấn đề - bài toán nhỏ hơn ”. - Nguyên lý 6 : Biểu diễn các tính toán không tường minh bằng đệ quy, có nghĩa là “Quá trình đệ quy trong máy tính không đơn giản như các biểu thức quy nạp trong toán học ”. 4.2 Phương pháp gián tiếp: Phương pháp này được sử dụng khi chưa tìm ra lời giải chính xác của vấn đề. Đây cũng chính là cách tiếp cận chủ yếu của loài ngư