Báo cáo giải pháp - Mô phỏng các thuật toán trong ngôn ngữ lập trình

Nội dung tóm tắt: Báo cáo giải pháp - Mô phỏng các thuật toán trong ngôn ngữ lập trình

1. CỘNG HÒA XÃ HỘI CHỦ NGHĨA VIỆT NAM Độc lập - Tự do - Hạnh phúc BÁO CÁO - Tên giải giải pháp: Mô phỏng các thuật toán trong ngôn ngữ lập trình - Yếu tố mới và sáng tạo của sáng kiến: Sáng kiến, kinh nghiệm hoàn toàn mới, được áp dụng lần đầu tiên tại đơn vị. Viết bằng C++, cho phép sinh viên có thể quan sát quá trình thực hiện thuật toán theo từng bước, có âm thanh và hình ảnh động minh họa. - Hiệu quả và phạm vi áp dụng của sáng kiến: Giải pháp giúp sinh viên và giáo viên dễ dàng hiểu các thuật toán thông qua các hình ảnh động, kích thích tính tự học, sáng tạo và say mê lập trình của sinh viên. Chất lượng môn học được nâng lên rõ rệt trong năm học KH1 năm học 2015- 2016. Cụ thể 100% sinh viên có kết quả điểm học phần đạt. Có thể áp dụng cho tất cả các chương trình đào tạo có giảng dạy các môn lập trình (từ tỉnh trở lên). Trang 1
2. GIẢI PHÁP KỸ THUẬT MÔ PHỎNG CÁC THUẬT TOÁN TRONG NGÔN NGỮ LẬP TRÌNH NỘI DUNG 1. Phần dẫn nhập 2. Những khó khăn 3. Những giải pháp khắc phục khó khăn 4. Kết quả thực hiện 5. Kết luận I- PHẦN DẪN NHẬP Hiện nay trong chương trình giảng dạy của các ngành kỹ thuật, đặt biệt là ngành Công nghệ thông tin có rất nhiều các môn lập trình được đưa vào giảng dạy. Tuy nhiên việc truyền tải các thuật toán cho sinh viên gặp rất nhiều khó khăn. Dẫn đến chất lượng tiết học, kết quả học tập còn nhiều hạn chế. Vậy thuật toán là gì và các nguyên nhân nào khiến cho sinh viên khó tiếp thu trong quá trình học tập? Khái niệm thuật toán: Thuật toán là một dãy hữu hạn các thao tác được sắp xếp theo một trình tự xác định sao cho sau khi thực hiện các thao tác ấy, từ Input của bài toán ta nhận được Output cần tìm. Cũng có thể xem thuật toán là một công cụ để giải quyết một bài toán cụ thể. Phát biểu bài toán sẽ chỉ định tổng quát mối quan hệ Input/Output cần thiết. Thuật toán mô tả một thủ tục tính toán cụ thể để đạt được mối quan hệ Input/Output đó. Các nguyên nhân: + Hầu hết sinh viên lần đầu tiếp xúc với ngôn ngữ lập trình. + Các thuật toán khó hình dung, việc hiểu và cài đặt tốt thuật toán đòi hỏi thời gian và công sức. + Việc tổ chức dữ liệu cho nó khá phức tạp, thời gian giảng dạy trên lớp có hạn. + Đây là các môn đòi tính kiên trì, có tư duy, tham khảo nhiều nguồn tài liệu, nhiều kênh học tập khác nhau trong quá trình học tập. + Cách dạy đơn điệu, sinh viên chỉ nhìn và tưởng tượng các bước thực hiện của thuật toán. + Chất lượng đầu vào của sinh viên các năm gần đây còn nhiều hạn chế. Xuất phát từ những nguyên nhân nêu trên là một giáo viện trực tiếp đứng lớp giảng dạy. Tôi luôn đặt ra câu hỏi vậy làm cách nào để giúp học sinh và giáo viên dễ dàng học các ngôn ngữ lập trình, cũng như kích thích tính tự học, say mê sáng tạo và say mê lập trình của sinh viên. Để thực hiện được điều đó, thì công việc đầu tiên là người giáo viên phải không ngừng đổi mới cả về nội dung lẫn phương pháp, phải theo chủ trương ứng dụng CNTT vào trong công tác giảng dạy. Trang 2
3. Để thực hiện được điều đó, trong quá trình giảng dạy tôi đã nghiên cứu để viết chương trình “Mô phỏng các thuật toán trong ngôn ngữ lập trình” cho các môn học về lập trình. Trong đó có môn Cấu trúc dữ liệu và giải thuật. Một trong số các chương trình giới thiệu trong đề tài sáng kiền này, đó là chương trình mô phỏng các thuật toán trên cấu trúc dữ liệu dạng cây (chương 4: Cấu trúc cây). Nhằm mục đích giúp sinh viên có thể dễ dàng nắm bắt tư tưởng cũng như từng bước hoạt động cụ thể của các thuật toán, làm cho bài giảng về các thuật toán này trở nên dễ hiểu, dễ tiếp thu hơn. II- NHỮNG KHÓ KHĂN: Chương trình mô phỏng các thuật toán trong các ngôn ngữ lập trình đã được nhiều tác giả thực hiện từ lâu với nhiều ngôn ngữ lập trình khác nhau như Visual C++, Visual Studio, C#, java v v. Ta chỉ cần vào Google gõ vào nội dung cần tìm về chương trình mô phỏng về một thuật toán nào đó, kết quả hiểu thị ra rất nhiều kết quả cần tìm (miễn phí hoặc trả phí). Tuy nhiên điều quan trọng là không phải thuật toán nào cũng có thể đem vào giảng dạy cho mọi cấp học, đối tượng và trình độ khác nhau. Vì vậy, chính giáo viên người trực tiếp đứng lớp sẽ là người am hiểu đối tượng mà mình giảng dạy, từ đó có thể tự thiết kế ra bài giảng cho riêng mình để áp dụng vào giảng dạy sao cho hiệu quả nhất. Để viết một chương trình mô phỏng phải cần rất nhiều yếu tố. Một trong các yếu tố đó là: + Mô phỏng đúng theo thuật toán. + Cho phép thực hiện theo từng bước. + Mô phỏng thuật toán phải có tính động. + Có thể thực thi với mọi dữ liệu đầu vào. + Có sự phân cấp người học. Ngoài các yếu tố trên, một điều quan trọng nữa là phải xây dựng đúng quy trình trình để mô phỏng thuật toán bao gồm các bước. + Nghiên cứu và phân tích dữ liệu. + Mô phỏng dữ liệu và kết quả đầu ra. + Chia thuật toán theo từng bước nhỏ rồi mô phỏng từng bước. + Ngôn ngữ để mô phỏng thuật toán. III- GIẢI PHÁP KHẮC PHỤC KHÓ KHĂN: Trong phạm vi sáng kiến này mang tính chất chuyên ngành, do đó tôi không đi sâu về giải thích các thuật toán (bao gồm các câu lệnh khô khan, khó hiểu). Tôi chỉ nêu đưa ra cách làm thế nào để các câu lệnh đó trở sinh động, dễ hiểu. Giúp cho việc dạy và học một ngôn ngữ lập trình nào đó trở nên sinh động, nhẹ nhàng và húng thú hơn cho sinh viên. Trang 3
4. Vì đây là các thuật toán mô phỏng áp dụng trên cây. Nên tôi giới thiệu sơ lược về cấu trúc câu (trên một phương diện nào đó nó tương tự như cây thư mục lưu trữ dữ liệu trên máy tính). 1. Định nghĩa cây: Cây là một tập hợp T các phần tử (gọi là nút của cây) trong đó có 1 nút đặc biệt được gọi là gốc, các nút còn lại được chia thành những tập rời nhau T1, T2 , , Tn theo quan hệ phân cấp trong đó Ti cũng là một cây. Mỗi nút ở cấp i sẽ quản lý một số nút ở cấp i+1. Quan hệ này người ta còn gọi là quan hệ cha-con. Tất cả các dữ liệu lưu trữ trên máy tính đều nhằm mục đích dùng để khai thác và xử lý. Trong quá trình khai thác và xử lý người ta thiết kế ra các thuật toán để thực hiện điều đó. Dữ liệu lưu trữ dưới dạng cây cũng không nằm trong ngoại lệ, sau đây là một vài các thuật toán thông dụng áp dụng trên cấu trúc cây (để dễ hiểu các thuật toán dưới đây được áp dụng cho cây lưu trữ số nguyên). 2. Các thuật toán áp dụng trên cây: a. Thuật toán tạo cây: Trang 4
5. b. Thuật toán tìm một phần tử trong cây: c. Thuật toán thêm một phần tử vào cây: Trang 5
6. d. Thuật toán xóa (hủy) một phần tử trong cây: 3. Mô phỏng các thuật toán trên cây: Tất các các thuật toán trên sẽ được mô phỏng bằng ngôn ngữ C++ thỏa mãn các yếu tố đã được nêu ở phần II đó là: • Mô phỏng đúng theo thuật toán. • Cho phép thực hiện theo từng bước. • Mô phỏng thuật toán phải có tính động. • Có thể thực thi với mọi dữ liệu đầu vào. • Có sự phân cấp người học. Dưới đây là một vài hình ảnh minh họa quá trình mô phỏng các thuật toán. Việc thực hiện trình tự đầy đủ các bước đã được mô phỏng cụ thể trong chương trình. Trang 6
7. a. Kết quả thực hiện thuật toán tạo cây: b. Tương tự cho kết quả thực hiện thuật toán tìm một phần tử trong cây: . Trang 7
8. c. Tương tự cho thuật toán thêm một phần tử vào cây: d. Tương tự cho thuật toán xóa (hủy) một phần tử trong cây: Trên đây là chương trình mô phỏng cho một số thuật toán tại chương 4 trong môn Cấu trúc dữ liệu và giải thuật. Một môn học tương đối khó mà tất cả những Trang 8
9. sinh viên khi học ngành Công nghệ thông tin bắt buộc phải trải qua, môn học làm tiền đề cho các môn lập trình khác. Tât cả các chương khác trong môn này tôi đều mô phỏng bằng chương trình động giúp cho bài sinh viên tiếp thu bài được dễ hơn, bài giảng sinh động hơn, thay vì chỉ là các con số, câu lệnh khô khan khó hiểu. IV- KẾT QUẢ THỰC HIỆN: Sau khi áp dụng cách làm trên cho cấu trúc cây tìm kiếm nhị phân và các cấu trúc dữ liệu khác của môn học. Kết quả đạt được là học sinh có hứng thú hơn về môn học từ đó kết quả môn học được nâng lên một cách rõ rệt trong kỳ thi học kỳ I năm học 2015-2016. Cụ thể như sau: Trang 9
10. V. KẾT LUẬN Để thực hiện được việc này, đòi hỏi phải tốn khá nhiều thời gian, công sức. Nhưng đổi lại là kết quả học tập của sinh viên, sẽ là niềm động viên, an ủi, là động lực cho mỗi chúng ta để không ngừng đổi mới cả về phương pháp, nội dung trong suốt quá trình giảng dạy. Qua đây, tôi rất mong nhận được nhiều ý kiến đóng góp từ các đồng nghiệp, từ hội đồng khoa học giúp cho công việc giảng dạy của bản thân nói riêng và nhà trường nói chung ngày một cải tiến và đạt hiệu quả cao hơn. Xin chân thành cảm ơn! Trang 10