Tài liệu ứng dụng trực quan trong dạy lập trình cho học sinh phổ thông

1 ĐẠI HỌC ĐÀ NẴNG TRƯỜNG ĐẠI HỌC BÁCH KHOA TRẦN THỊ HOA LÀI ỨNG DỤNG TRỰC QUAN TRONG DẠY LẬP TRÌNH CHO HỌC SINH PHỔ THÔNG Chuyên ngành: Khoa học máy tính Mã số: 8480101 TÓM TẮT LUẬN VĂN THẠC SĨ KỸ THUẬT Đà Nẵng, Năm 2018 Công trình được hoàn thành tại TRƯỜNG ĐẠI HỌC BÁCH KHOA Người hướng dẫn khoa học: PGS.TS. Võ Trung Hùng Phản biện 1 : PGS.TS. Nguyễn Thanh Bình Phản biện 2 : TS. Trần Thế Vũ Luận văn được bảo vệ trước Hội đồng chấm Luận văn tốt nghiệp thạc sĩ họp tại Trường Đại học Bách khoa Đà Nẵng vào ngày 05 tháng 01 năm 2019 * Có thể tìm hiểu luận văn tại: - Trung tâm Học liệu và truyền thông, Đại học Đà Nẵng tại Trường Đại học Bách khoa. - Thư viện Khoa Công nghệ thông tin, Trường Đại học Bách khoa – Đại học Đà Nẵng 1 MỞ ĐẦU 1. Tính cấp thiết của đề tài Trong thực tế, việc dạy môn lập trình cũng như dạy bồi dưỡng học sinh giỏi môn Tin học cho học sinh phổ thông gặp rất nhiều khó khăn. Học sinh xem đây là một môn phụ, không thi tốt nghiệp, không thuộc khối nào khi thi vào các trường đại học. Môn lập trình lại là môn học tương đối khó, đòi hỏi phải có ý tưởng về thuật toán, tư duy về toán học…, nên động lực để thúc đẩy học sinh học tập môn này bị hạn chế. Nhiều em có năng lực và tư duy thuật toán, có tư duy lập trình nhưng chưa phát huy hết khả năng đó. Do đó, một phương pháp dạy học sinh động để tạo niềm đam mê và gây hứng thú cho học sinh là rất quan trọng. Phương pháp dạy học trực quan là một trong những phương pháp mà giáo viên khi dạy lập trình cần quan tâm hơn để phát huy tính tích cực, khả năng hình thành tư duy tốt và huy động sự tham gia của nhiều giác quan. Qua đó, tạo điều kiện dễ hiểu, dễ nhớ và nhớ lâu, làm phát triển năng lực tư duy, năng lực chú ý, năng lực quan sát, khả năng tò mò của học sinh. Đặc biệt việc ứng dụng kỹ thuật trực quan các thuật toán trong dạy lập trình là rất cần thiết, tạo thêm động lực, hứng thú và niềm đam mê cho học sinh khi học môn lập trình. Phương pháp dạy học trực quan ngày càng trở nên hữu ích và trở thành một giáo cụ trực quan rất quan trọng, nó như một tài liệu hướng dẫn trong việc dạy các thuật toán bằng máy tính, giúp học sinh hiểu cấu trúc dữ liệu và thuật toán nhanh hơn. Để tìm hiểu kỹ hơn về một số thuật toán và ứng dụng kỹ thuật trực quan trong quá trình dạy các thuật toán đó, tôi đã chọn đề tài “Ứng dụng trực quan trong dạy lập trình cho học sinh phổ thông làm đề tài luận văn tốt nghiệp. Hy vọng với nghiên cứu này sẽ là tài liệu tham khảo thiết thực trong ứng dụng dạy học lập trình và bồi dưỡng học sinh giỏi cho học sinh phổ thông. 2. Mục tiêu và nhiệm vụ nghiên cứu a. Mục tiêu Mục tiêu của đề tài là nâng cao chất lượng dạy học một số thuật toán trên đồ thị bằng cách trực quan, đồng thời hỗ trợ cho học sinh trong quá trình tự học một số thuật toán trên đồ thị với các thay đổi trực quan bằng đồ họa. Áp dụng kết quả nghiên cứu 2 để tạo động lực và niềm đam mê cho học sinh khi học lập trình. b. Nhiệm vụ Để đạt được mục tiêu trên, nhiệm vụ đặt ra là: * Cơ sở lý thuyết: - Nghiên cứu phương pháp dạy học trực quan. - Đồ họa máy tính. - Mô phỏng thuật toán và quy trình mô phỏng thuật toán. - Các thuật toán: Tìm đường đi ngắn nhất trên đồ thị bằng thuật toán Dijsktra, thuật toán tìm kiếm theo chiều rộng và chiều sâu. * Ứng dụng: - Cài đặt, thử nghiệm trực quan thuật toán tìm đường đi ngắn nhất, tìm kiếm theo chiều rộng và chiều sâu. - Đánh giá chất lượng của học sinh trước và sau khi áp dụng các phương pháp mà đề tài đã trình bày. 3. Đối tượng và phạm vi nghiên cứu a. Đối tượng nghiên cứu - Cơ sở lý thuyết về phương pháp dạy học trực quan, về đồ họa máy tính, về cách mô phỏng thuật toán và quy tình mô phỏng thuật toán. - Thuật toán tìm đường đi ngắn nhất trên đồ thị, thuật toán tìm kiếm theo chiều sâu và tìm kiếm theo chiều rộng. b. Phạm vi nghiên cứu Trong khuôn khổ của một luận văn cao học, tôi ch áp dụng cho thuật toán tìm đường đi ngắn nhất trên đồ thị bằng thuật toán Dijsktra và thuật toán tìm kiếm theo chiều sâu và chiều rộng. 4. Phương pháp nghiên cứu Sử dụng hai phương pháp chính là nghiên cứu lý thuyết và nghiên cứu thực nghiệm. a. Nghiên cứu thu t - Các tài liệu về cơ sở lý thuyết: Lý thuyết về thuật toán, về phương pháp dạy học trực quan, lý thuyết về đồ họa máy tính, lý thuyết mô phỏng thuật toán. - Các tài liệu liên quan đến ngôn ngữ lập trình Java. b. Nghiên cứu th c nghiệm 3 Xây dựng các chương trình thực nghiệm tính hiệu quả của các giải thuật nghiên cứu. 5. Bố cục của luận văn Luận văn được tổ chức thành 3 chương chính: Chương 1: Nghiên cứu tổng quan Giới thiệu về phương pháp dạy học trực quan, về ĐHMT, về đồ thị và trình bày 3 thuật toán thông thường trên đồ thị: Thuật toán Dijsktra tìm đường đi ngắn nhất, thuật toán tìm kiếm theo chiều rộng và thuật toán tìm kiếm theo chiều sâu. Chương 2: Mô phỏng thuật toán Giới thiệu về phương pháp mô phỏng thuật toán và áp dụng để mô phỏng cho 3 thuật toán ở chương 1 Chương 3: Cài đặt thử nghiệm Trình bày về việc thực hiện cài đặt mô phỏng trực quan các thuật toán ở chương 1 và chương 2. 4 CHƯƠNG 1. NGHIÊN CỨU TỔNG QUAN Chương 1sẽ giới thiệu tổng quan về phương pháp dạy học trực quan, về đồ họa máy tính, về đồ thị và trình bày 3 thuật toán thông thường trên đồ thị: Thuật toán Dijsktra tìm đường đi ngắn nhất, thuật toán tìm kiếm theo chiều rộng và thuật toán tìm kiếm theo chiều sâu. 1.1. Phương pháp dạy học trực quan Dạy học trực quan là PPDH sử dụng những phương tiện trực quan, phương tiện kĩ thuật dạy học trước, trong và sau khi nắm tài liệu mới, khi ôn tập, khi củng cố, hệ thống hóa và kiểm t ra tri thức, kĩ năng, kĩ xảo. PPDH trực quan được thể hiện dưới hình thức là trình bày trực quan và quan sát [11]. 1.1.1. Phương pháp trình bà tr c quan 1.1.2. Phương pháp quan sát 1.2. Đồ họa máy tính 1.2.1. Khái niệm 1.2.2. Các kỹ thuật đồ họa + Kỹ thuật đồ họa điểm + Kỹ thuật đồ họa vector 1.2.3. Màn hình đồ họa và một số ứng dụng của đồ họa 1.3. Đồ thị và một số thuật toán trên đồ thị 1.3.1. Đồ thị 1.3.2. Một số thuật toán trên đồ thị a. Tìm kiếm trên đồ thị b. Một số thuật toán trên đồ thị * Thuật toán tìm đường đi ngắn nhất (Dijsktra) Đ nh xuất phát là 2 Kết quả thứ tự các đ nh tìm kiếm theo chiều sâu là: 2->3->1>5->6->7->4 Độ phức tạp: Tìm kiếm trên đồ thị bắt đầu từ một đ nh có thể thăm tất cả các đ nh còn lại, khi đó cách biểu diễn đồ thị có ảnh hưởng lớn tới chi phí về thời gian thực hiện giải thuật. 5 Nếu biểu diễn đồ thị bằng danh sách kề, cả hai thuật toán BFS và DFS đều có độ phức tạp tính toán là O(m+n) = O(max(n,m)), đây là cách cài đặt tốt nhất. Nếu ta biểu diễn đồ thị bằng ma trận kề thì độ phức tạp tính toán trong trường hợp này là O(n + n2) = O(n2). [6] 1.4. Tổng kết chương 1 Chương 1 đã giới thiệu tổng quan về phương pháp dạy học trực quan, ưu điểm và hạn chế của phương pháp này, những yêu cầu cơ bản đối với phương pháp dạy học trực quan. Ngoài ra, trình bày về các kỹ thuật và ứng dụng của đồ họa máy tính. Các kiến thức liên quan đến đồ thị và 3 thuật toán thông thường trên đồ thị, đó là: thuật toán tìm đường đi ngắn nhất, thuật toán tìm kiếm theo chiều rộng và tìm kiếm theo chiều sâu, độ phức tạp của các thuật toán đó. 6 CHƯƠNG 2. MÔ PHỎNG THUẬT TOÁN Chương 2 trình bày về phương pháp mô phỏng thuật toán, tác dụng của việc mô phỏng thuật toán trong dạy học và các yêu cầu đối với việc mô phỏng thuật toán. Đồng thời trình bày cụ thể về quy trình mô phỏng thuật toán và áp dụng mô phỏng 3 thuật toán: Dijsktra, BFS, DFS. 2.1. Phương pháp mô phỏng thuật toán 2.1.1. Khái niệm 2.1.2. Tác dụng của mô phỏng thuật toán trong dạ học MPTT được sử dụng rộng rãi như công cụ hỗ trợ giảng dạy trong ngành giáo dục. Một số nghiên cứu thực nghiệm đã ước lượng hiệu quả của chúng trong giáo dục và kết quả nhận được có thay đổi, tác dụng của việc áp dụng mô phỏng thuật toán trong dạy học được ghi nhận lại như sau: Các hoạt cảnh MPTT gây hứng thú cho người học, làm tăng tính sáng tạo của người học. Sử dụng mô phỏng kết hợp với phương pháp thuyết trình truyền thống làm tăng tốc độ hiểu biết cho người học. Ngoài ra, mô phỏng giúp cho người học dễ hiểu thuật toán hơn thông qua các bước mô phỏng trực quan kết hợp với mã nguồn chương trình [16]. 2.1.3. Các êu cầu đối với mô phỏng thuật toán - Cần phản ánh đúng nội dung thuật toán: Thuật toán được đưa ra mô phỏng phải chính xác, các bước thực hiện thuật toán phải trực quan và phản ánh đúng theo nội dung thuật toán đã đưa ra để đảm bảo tính đúng đắn của thuật toán. - Mô phỏng phải được thực hiện theo từng bước: thuật toán thường là trừu tượng, nếu để chương trình chạy tự động thì người dùng sẽ khó hiểu. Vì vậy, cần phải có chế độ thực hiện mô phỏng thuật toán theo từng bước, để người học có thể quan sát, theo dõi sự thay đổi giá trị của từng biến, nhờ đó, sẽ giúp cho người học hiểu thuật toán rõ hơn và nhanh hơn. - Mô tả thuật toán phải có tính động: để mô tả trực quan hóa quá trình thực hiện của thuật toán ta nên đưa vào hình ảnh động (có thể có âm thanh) để thể hiện sự thay đổi của dữ liệu trong quá trình thực thi. 7 2.2. Quy trình mô phỏng thuật toán 2.2.1. Thi t k hệ thống mô phỏng thuật toán - Các bước phân tích thiết kế gồm: Nghiên cứu và phân tích giải thuật Mô phỏng dữ liệu vào và dữ liệu ra Chính xác hóa giải thuật (bằng cách quan sát dữ liệu ra của từng bước nhỏ) Tách giải thuật thành nhiều bước nhỏ Tổng hợp các bước thành giải thuật hoàn ch nh Hình 2.2 - Sơ đồ các bước thi t k hệ thống mô phỏng thuật toán Chi tiết về các bước của quá trình này đã được giới thiệu trong phần 2.2.2 của luận văn này. - Mô hình bài toán mô phỏng: Hình 1.3 - Mô hình bài toán mô phỏng Input Dữ liệu đưa vào chương trình được mô phỏng bằng đồ họa bằng 2 cách: + Tạo dữ liệu trực tiếp + Dữ liệu theo mẫu Thuật toán + Mô phỏng theo từng bước của thuật toán + Mô phỏng toàn bộ thuật toán Output Kết quả: đồ thị đã được mô phỏng bằng đồ họa thể hiện qua những thay đổi trên hình vẽ trong mỗi bước thực hiện thuật toán. 8 2.2.2. Qu trình thi t k mô phỏng thuật toán a. Nghiên cứu và phân tích giải thuật b. Mô phỏng dữ liệu vào và kết quả đầu ra Ví dụ: với chương trình mô phỏng các thuật toán trên đồ thị, dữ liệu vào sẽ là một đồ thị bao gồm tập các nút và các cạnh nối các nút với nhau. Ta sẽ thể hiện các nút là một hình tròn có tên nút được đánh số theo thứ tự và nằm giữa hình tròn. Cạnh sẽ nối hai nút của đồ thị bằng một đường thẳng (khi nối thì sẽ xuất hiện hộp thoại để nhập trọng số và trọng số sẽ nằm giữa vị trí giữa của hai nút). Như vậy, đồ thị được xây dựng rất trực quan và người học có thể quan sát dễ dàng những thay đổi trên đồ thị khi thực hiện các bước của giải thuật. Hình 2-4 - Dữ liệu đầu vào: một đồ thị vô hướng gồm 5 đỉnh, 6 cạnh Việc đưa dữ liệu vào là một yếu tố quan trọng quyết định tính hiệu quả của mô phỏng thuật toán. Nên chương trình mô phỏng cần phải có nhiều cơ chế đưa dữ liệu vào, ví dụ như: - Đề xuất một số dữ liệu mẫu: Chương trình sẽ chuẩn bị một số dữ liệu mẫu từ trước để người học có thể học thuật toán ngay mà không phải chuẩn bị dữ liệu đầu vào. - Sinh ngẫu nhiên: để cho chương trình tự sinh một đồ thị tùy ý. 9 - Nhập dữ liệu thủ công: người học dùng công cụ của chương trình cung cấp để tự tạo đồ thị theo cách của mình. Đây là cách để giải quyết các băn khoăn của người học về thuật toán (với trường hợp này thì kết quả sẽ là thế nào? Với đồ thị đặc biệt này thì thuật toán có chạy không?, …). c. Chia thuật toán thành nhiều bước nhỏ rồi mô phỏng theo từng bước d. Tổng hợp mô phỏng theo các bước Sau khi mô phỏng được từng bước của thuật toán ta tiến hành ghép các bước mô phỏng lại để được mô hình mô phỏng hoàn ch nh. e. Chính xác hóa giải thuật Từ dữ liệu vào, tiến hành chạy theo từng bước, quan sát những thay đổi của cấu trúc dữ liệu sau mỗi bước và quan sát kết quả cuối cùng khi thuật toán đã chạy xong. 2.3. Áp dụng mô phỏng một số thuật toán trên đồ thị 2.3.1. Thuật toán tìm đường đi ngắn nhất (Thuật toán Dijsktra) Áp dụng quy trình mô phỏng thuật toán ở mục 2.2 để thực hiện các bước cho quá trình mô phỏng: Các bước thiết kế hệ thống mô phỏng: 5 bước a. Nghiên cứu và phân tích giải thuật b. Mô phỏng dữ liệu vào và kết quả đầu ra Để mô phỏng dữ liệu vào cho bài toán này, tôi đã chọn 2 phương pháp để tạo dữ liệu vào: 10 - Cách thứ nhất: Tạo đồ thị bằng cách thủ công là vẽ các đ nh và cạnh - Cách này thì tôi tạo chế độ cho người dùng tự tạo đồ thị với số đ nh và số cạnh theo yêu cầu bài toán. Cách thứ hai: Chọn đồ thị theo mẫu sẵn c. Chia thuật toán thành nhiều bước nhỏ rồi mô phỏng theo từng bước: Thuật toán của bài toán tìm đường đi ngắn nhất có thể chia thành các bước như ở mục 1.3.2.b. Kết hợp với các kỹ năng về đồ họa và các lệnh trong ngôn ngữ lập trình Java, có thể mô phỏng các bước của thuật toán thông qua đoạn trích code (xem phụ lục 1). d. Tổng hợp mô phỏng theo các bước: e. Chính xác hóa giải thuật: Mô hình bài toán mô phỏng 2.3.2. Thuật toán tìm ki m theo chiều rộng (BFS) Các bước thiết kế hệ thống mô phỏng: a. Nghiên cứu và phân tích giải thuật b. Mô phỏng dữ liệu vào và kết quả đầu ra Kết hợp với kiến thức về đồ họa để mô phỏng dữ liệu vào trực quan (xem Phụ lục 2) như sau: 11 Hình 2-9 – Minh họa dữ liệu vào của thuật toán BFS Dữ liệu vào là số đ nh của đồ thị, các đ nh đầu đ nh cuối để tạo các cạnh của đồ thị và đ nh bắt đầu để duyệt đồ thị. Dữ liệu ra là các đ nh đã được duyệt trên đồ thị c. Chia thuật toán thành nhiều bước nhỏ (đã được trình bày ở mục 1.3.2b) và được thể hiện trong các chương trình con và chức năng của nó. d. Tổng hợp mô phỏng theo các bước: Mô hình mô phỏng hoàn ch nh trên đồ thị gồm 5 đ nh 7 cạnh như sau: 12 Hình 2-10 – K t quả mô phỏng thuật toán BFS e. Chính xác hóa giải thuật: Tạo 1 đồ thị đơn giản để mô phỏng nhằm chính xác hóa lại giải thuật thông qua các phương thức lựa chọn trên chương trình mô phỏng và duyệt để quan sát kết quả cuối cùng khi thuật toán đã chạy xong để kiểm tra tính chính xác của giải thuật. Mô hình bài toán mô phỏng: 2.3.3. Thuật toán tìm kiếm theo chiều sâu (DFS) Các bước thi t k hệ thống mô phỏng: a. Nghiên cứu và phân tích giải thuật b. Mô phỏng dữ liệu vào và kết quả đầu ra Kết hợp với kiến thức về đồ họa để mô phỏng dữ liệu vào trực quan (xem phục lục 3) như sau: 13 Hình 2-12 – Minh họa dữ liệu vào cho thuật toán DFS Dữ liệu vào là số đ nh của đồ thị, các đ nh đầu đ nh cuối để tạo các cạnh của đồ thị và đ nh bắt đầu để duyệt đồ thị. Dữ liệu ra là các đ nh đã được duyệt theo chiều sâu. Hình 2-13 – K t quả minh họa thuật toán DFS 14 c. Chia thuật toán thành nhiều bước nhỏ: Được trình bày tại mục 1.3.2b và thể hiện trong các chương trình con và chức năng của nó. d. Tổng hợp mô phỏng theo các bước: Chương trình sau khi duyệt toàn bộ áp dụng cho đồ thị gồm 5 đ nh 7 cạnh đã cho kết quả trên hình 20. e. Chính xác hóa giải thuật: Tạo 1 đồ thị đơn giản để mô phỏng nhằm chính xác hóa lại giải thuật thông qua các phương thức lựa chọn trên chương trình mô phỏng và duyệt để quan sát kết quả cuối cùng khi thuật toán đã chạy xong để kiểm tra tính chính xác của giải thuật. Mô hình bài toán mô phỏng: 2.4. Tổng kết chương Nội dung chương 2 trình bày về phương pháp mô phỏng thuật toán; tác dụng của việc mô phỏng và các yêu cầu đối với việc mô phỏng thuật toán; quy trình mô phỏng thuật toán và áp dụng mô phỏng 3 thuật toán trên đồ thị: thuật toán tìm đường đi ngắn nhất, thuật toán tìm kiếm theo chiều rộng và tìm kiếm theo chiều sâu. 15 CHƯƠNG 3. CÀI ĐẶT THỬ NGHIỆM Chương 3 trình bày về lựa chọn ngôn ngữ lập trình để cài đặt thử nghiệm; thực hiện cài đặt 3 thuật toán: Dijkstra, BFS, DFS và so sánh kết quả tiếp thu của người học sau khi dạy học 3 thuật toán này bằng cách sử dụng phương pháp thông thường và sử dụng phương pháp mô phỏng trực quan. 3.1. Lựa chọn ngôn ngữ lập trình Việc mô phỏng thuật toán nhằm giúp cho người học dễ hiểu thuật toán, đồng thời khuyến khích người thiết kế và người học tìm thấy những biến đổi mới của giải thuật qua từng bước. Để mô phỏng trực quan một số thuật toán trên đồ thị thì trong luận văn này, tôi đã sử dụng ngôn ngữ Java để cài đặt chương trình mô phỏng bởi Java có nhiều đặc tính dưới đây [7], [8]: Ngôn ngữ Java là ngôn ngữ lập trình hướng đối tượng nên nó cũng có các đặc điểm chung của các ngôn ngữ hướng đối tượng: - Tính trừu tượng (Abstraction): là tiến trình xác định và nhóm các thuộc tính, các hành động liên quan đến một thực thể đặc thù, xét trong mối tương quan với ứng dụng đang phát triển. - Tính đa hình (Polymorphism): cho phép một phương thức có các tác động khác nhau trên nhiều loại đối tượng khác nhau, với tính đa hình, nếu cùng một phương thức ứng dụng cho các đối tượng thuộc các lớp khác nhau thì nó đưa đến những kết quả khác nhau, bản chất của sự việc chính là phương thức này bao gồm cùng một số lượng các tham số. - Tính kế thừa (Inheritance): Điều này cho phép các đối tượng chia sẻ hay mở rộng các đặc tính sẵn có mà không phải tiến hành định nghĩa lại. - Tính đóng gói (Encapsulation): là tiến trình che giấu việc thực thi những chi tiết của một đối tượng đối với người sử dụng đối tượng ấy. 16 - Độc lập nền (Write Once, Run Anywhere): Không giống như nhiều ngôn ngữ lập trình khác như C và C ++, khi Java được biên dịch, nó không được biên dịch sang mã máy cụ thể, mà thay vào đó là mã byte code chạy trên máy ảo Java (JVM). Điều này đồng nghĩa với việc bất cứ thiết bị nào có cài đặt JVM sẽ có thể thực thi được các chương trình Java. - Tính đơn giản: ngôn ngữ java đơn giản hơn so với C/C++ do đã loại bỏ tính đa kế thừa và phép toán con trỏ từ C/C++. - Tính bảo mật: java hỗ trợ bảo mật rất tốt bởi các thuật toán mã hóa như mã hóa một chiều (one way hashing) hoặc mã hóa công cộng (public key), ... - Tính đa luồng: với tính năng đa luồng, java có thể viết chương trình có thể thực thi nhiều task cùng một lúc. Tính năng này thường được sử dụng rất nhiều trong lập trình game. - Hiệu suất cao nhờ vào trình thu gom rác (garbage collection), giải phóng bộ nhớ đối với các đối tượng không được dùng đến. - Linh hoạt: ngôn ngữ java được xem là linh hoạt hơn C/C ++ vì nó được thiết kế để thích ứng với nhiều môi trường phát triển. Để lập trình Java, chúng ta cần đến: - JDK (Java Development KIT): bao gồm JRE (Java Runtime Enviroment) và thư viện để phát triển. Development Environment): là ứng dụng giúp lập trình viên phát triển dễ dàng và nhanh chóng hơn, có thể sử dụng Netbeans, Eclipse để phát triển. 3.2. Các chương trình ứng dụng Sau khi sử dụng các công cụ đồ họa kết hợp với ngôn ngữ lập trình Java để mô phỏng 3 thuật toán ở chương 2, tôi đã tạo các chương trình mô phỏng sau đây: 3.2.1. Chương trình mô phỏng thuật toán tìm đường đi ngắn nhất a. Sử dụng chương trình: - IDE (Integrated 17 b. Minh họa Tiến hành minh họa với đồ thị sau: 1 3 0 1 2 4 45 1 0 4 5 2 0 3 5 1 0 - Phương pháp duyệt từng bước: Tạo đồ thị: 18 Kết quả duyệt từng bước như sau: - Phương pháp duyệt toàn bộ: Kết quả là: đường đi ngắn nhất từ 1 đến 5 là: 1->5, có độ dài là 45 Cả 2 phương pháp đều có cùng 1 kết quả. 3.2.2. Chương trình mô phỏng thuật toán tìm ki m theo chiều rộng a. Sử dụng chương trình: