Luận văn Mô phỏng một số thuật toán trên đồ thị

học cho học sinh Chuyên Tin đều là những thuật toán “tốt” và có ứng dụng để giải quyết một lớp bài toán trong tin học. Vì vậy, chương trình mô phỏng thuật toán cần đảm bảo chạy “tốt” đối với mọi bộ dữ liệu đầu vào: trường hợp tốt, trường hợp xấu, trường hợp ngẫu nhiên…. 4.5. Có sự phân cấp người học Thông thường, mức độ tiếp thu trong một giờ học của học sinh không giống nhau, có những học sinh hiểu bài nhanh nhưng cũng có những học sinh nắm bắt bài chậm hơn. Vì vậy, thuật toán mô phỏng cũng cần phải có những chức năng “mềm dẻo” với các đối tượng học. Ví dụ, có thể có chức năng lựa chọn độ trễ cho mỗi thao tác để phù hợp với mức độ quan sát của từng đối tượng học khác nhau hoặc cho phép chạy đi chạy lại một thuật toán trên một bộ dữ liệu vào… 5. Quy trình mô phỏng thuật toán 5.1.Nghiên cứu và phân tích giải thuật Bước đầu tiên trong quá trình giải một bài toán Tin học là xác định bài toán. Ở bước này, dựa trên phát biểu của bài toán ta phải xác định rõ Input (dữ liệu đầu vào) và Output (kết quả) của bài toán là gì và mối quan hệ giữa chúng. Thông tin đó cần được nghiên cứu một cách cẩn thận để có thể lựa chọn thuật toán, cách thể hiện các đại lượng đã cho, các đại lượng phát sinh trong quá trình giải toán và lựa chọn ngôn ngữ lập trình thích hợp. Tiêu chí để thiết kế hoặc lựa chon thuật toán thường dựa trên hai yếu tố là thời gian và không gian cần thiết để thực hiện thuật toán, trong đó yếu tố thời gian là đặc biệt quan trọng. Ngoài ra, trên thực tế khi lựa chọn thuật toán người ta còn quan tâm sao cho việc cài đặt thuật toán đó bằng một ngôn ngữ lập trình được dễ dàng, ít tốn công sức của người lập trình. Đối với những bài toán nhỏ số Trang 44 lần cần giải bài toán không nhiều nên tiêu chí sau cùng thường được ưa chuộng để lựa chọn thuật toán. Sau khi chứng minh được tính đúng đắn của giải thuật (có thể bằng suy luận Toán học hoặc chứng minh trên bộ dữ liệu mẫu phủ kín các trường hợp có thể xảy ra với bài toán) ta tiến hành cài đặt thuật toán trên một ngôn ngữ lập trình cụ thể. Để việc cài đặt thuật toán nhanh, thường người ta diễn tả lại thuật toán đủ chi tiết 5.2.Mô phỏng dữ liệu vào và kết quả đầu ra Mô phỏng dữ liệu vào là cách chọn hình thức hiển thị cho cấu trúc dữ liệu tương ứng với giải thuật. Việc lựa chọn mô hình mô phỏng cho dữ liệu vào quyết định tính hiệu quả của chương trình mô phỏng. Hình thức hiển thị này phải dễ hiểu, dễ gây hứng thú cho người học muốn tìm hiểu thuật toán. 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à 1 hình tròn màu xanh có tên nút ở giữa. Cạnh nối sẽ nối hai nút của đồ thị bằng một đường thẳng (nếu có trọng số thì 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. Trang 45 Hình vẽ: Dữ liệu đầu vào: một đồ thị có hướng gồm 6 đỉnh, 7 cạnh Việc đưa dữ liệu vào (như đã phân tích trong phần 4 – chương 2) 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 ý - Sinh 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ăc 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 dừng hay không?.....) 5.3.Chia thuật toán thành nhiều bước nhỏ rồi mô phỏng theo từng bước Việc chia thuật toán thành nhiều bước nhỏ rất có ý nghĩa trong việc lập trình. Nó làm cho thuật toán ban đầu trở nên đơn giản, rõ ràng và dễ hiểu hơn. Trang 46 Ví dụ: thuật toán tìm đường đi ngắn nhất trên đồ thị có trọng số - thuật toán Dijsktra: Cho đồ thị G = (V, E) - V tập các đỉnh và E là tập các cạnh Thuật toán Dijkstra tìm đường đi ngắn nhất từ đỉnh s tới đỉnh t. Gọi S là tập các đỉnh đã xác định được đường đi ngắn nhất từ s tới các đỉnh này và d[u] là độ dài đường đi ngắn nhất từ s tới u. Sau đây là giải thuật: Bước 1) Khởi tạo S = {s}, d[s] = 0, d[u] = + với u S Bước 2)Chọn u = s Lặp nếu u t Xét các đỉnh v (với v  S) 2.1 Cập nhật d[v] = min{d[v], d[u] + c[u, v]} và trace[v] = u nếu d[v] > d[u] + c[u,v] 2.2 Chọn v có d[v] là nhỏ nhất 2.3 Thêm v vào S, u = v Bước 3) In ra d[t] và đường đi từ s đến t Và ta sẽ mô phỏng theo từng bước của thuật toán như sau: Trang 47 Hình vẽ: Một bước mô phỏng của thuật toán Dijsktra 5.4. Tổng hợp mô phỏng theo các bước Cuối cùng, 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: thao tác đưa 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. 5.5.Sơ đồ cấu trúc chung của hệ thống mô phỏng Có một số hệ thống mô phỏng thuật toán được viết bằng ngôn ngữ lập trình Java với cùng một kiến trúc như sau: Hình: Sơ đồ cấu trúc của một hệ thống mô phỏng Thuật toán (giả mã) Đồ họa mô phỏng hoạt động của thuật toán File kịch bản Kênh mô phỏng Các hàm mô phỏng Màn hình trình diễn mô phỏng Trang 48 - Kênh mô phỏng: Đóng vai trò như một kênh truyền giữa hệ thống mô phỏng và người dùng cuối. Nó đọc một file kịch bản do người dùng chuẩn bị từ trước chuyển sang cho các hàm mô phỏng mô phỏng thuật toán và đưa kết quả lên màn hình bằng đồ họa. - Các hàm mô phỏng: chứa chức năng vẽ các đối tượng được mô phỏng lên màn hình trình diễn mô phỏng. - Màn hình trình diễn mô phỏng: cung cấp môi trường đồ họa để hiển thị kết quả cho người dùng cuối quan sát. Một ví dụ về chuẩn bị file kịch bản và hình ảnh các bước mô phỏng được mô tả ở phần phụ lục của luận văn này. Hình ảnh thể hiện kết quả cuối cùng của thuật toán Dijsktra 6. Đề xuất lựa chọn công cụ để phát triển chương trình mô phỏng thuật toán Trong mục này, chúng ta sẽ phân tích các cách tiếp cận để xây dựng hệ thống mô phỏng và tính khả thi của chúng. Ta sẽ xem xét một vài công cụ mô phỏng thuật toán để xây dựng hệ thống mô phỏng phù hợp. Trang 49 Có ba cách tiếp cận có thể để xây dựng hệ thống mô phỏng thuật toán. Cách tiếp cận thứ nhất là lựa chọn hệ thống mô phỏng thuật toán cung cấp các công cụ chung để xây dựng các thành phần tương tác cho hệ thống mô phỏng (sử dụng lại tài nguyên sẵn có). Cách tiếp cận thứ hai là lựa chọn một chương trình mô phỏng một thuật toán đã có (dạng open source), sửa đổi, nâng cấp thành hệ thống mới. Cách tiếp cận cuối cùng là phân tích thiết kế hệ thống từ đầu. 6.1. Một số hệ thống mô phỏng thuật toán chung Có một số chương trình mô phỏng thuật toán theo ý người dùng. Hay nói cách khác là đưa thuật toán, đưa cấu trúc dữ liệu, đưa dữ liệu vào trên một file kịch bản theo quy định chung của chương trình mô phỏng. Nếu file kịch bản đưa vào phù hợp với ngữ cảnh của chương trình đó (nghĩa là có thể mô tả cấu trúc dữ liệu bằng đồ họa của chương trình) thì nó sẽ mô phỏng các bước của thuật toán theo đúng sự chuẩn bị của người dùng. Các hệ thống này thường được viết bằng ngôn ngữ Java có cùng kiến trúc như đã đề cập trong phần 5 – chương 2 của luận văn này. Ta sẽ phân tích từng hệ thống để thấy được những ưu và nhược điểm của từng hệ thống. JSAMBA JSAMBA (xem html) là một phiên bản viết bằng Java của hệ thống mô phỏng POLKA (như đã giới thiệu trong phần lịch sử phát triển thuật toán mô phỏng). JSAMBA cung cấp các đối tượng như: đoạn văn bản (text), đoạn thẳng (lines), hình chữ nhật (rectangle), tam giác (triangle), hình tròn (circles) và đa giác (polygon). Nó có thể vẽ các đối tượng được mô phỏng bằng một tốc độ khá nhanh. Hình ảnh ít bị “giật giật” hình khi chạy mô phỏng. Nó cho phép người dùng thay đổi kích thước của các đối tượng được mô phỏng. Ưu điểm Trang 50 Có thể sử dụng cho các chương trình được viết bằng bất kì một ngôn ngữ nào. Nó sử dụng các thư viện có sẵn của Java để mô phỏng và tận dụng được mọi ưu điểm của Java, dễ tiếp cận qua các trình duyệt web hiện nay. Hạn chế Phải chuẩn bị trước một file kịch bản theo đúng yêu cầu của chương trình. Điều này là một hạn chế lớn đối với học sinh trong việc tự học (vì nếu chúng biết chuẩn bị file kịch bản cho mô phỏng theo đúng quy cách của chương trình thì đã không cần phải học lập trình nữa!) Đối với giáo viên, một hạn chế nổi bật của Jsamba là không hỗ trợ bất kì một cấu trúc dữ liệu có sẵn nào. Điều này làm cho chương trình trở nên gọn và đóng kín nhưng mặt khác nó cũng gây nên một hạn chế là việc chuẩn bị file kịch bản là rất phức tạp vì phải mô hình hóa các cấu trúc dữ liệu đi kèm. JAWAA (Java and Web – based Algorithm Animation) JAWAA ( hoạt động tương tự như Jsamba. Nó là một ngôn nhữ gồm các lệnh đơn giản để tạo ra những mô phỏng cấu trúc dữ liệu vào hiển thị chúng trên trình duyệt web. Các lệnh được sinh trong file kịch bản và chạy bởi Jawaa Applet. JAWAA cung cấp các lệnh cho phép tạo và di chuyển một số đối tượng cơ bản: hình tròn, đoạn thẳng, đoạn văn bản và khối hình chữ nhật và một số cấu trúc dữ liệu cơ bản: mảng, stack, queue, danh sách, cây và đồ thị. Tốc độ vẽ và mô phỏng nhanh. Các đối tượng mô phỏng được vẽ lại trên màn hình nhờ việc sử dụng kĩ thuật bộ nhớ đệm đôi trong đó bao gồm hai hình ảnh: một được vẽ lên màn hình, một được lưu trữ trong bộ nhớ. Một đặc điểm nữa của Jawwa là nó cung cấp một số điều khiển cho người dùng: các nút lệnh bắt đầu, dừng, chạy từng bước và lựa chọn tốc độ thể hiện mỗi bước của thuật toán trên màn hình. Ưu điểm Trang 51 Cũng giống như Jsamba, Jawaa cũng là một phần mềm mô phỏng được viết bằng Java nên nó có mọi ưu điểm của ngôn ngữ Java. Ngoài ra, Jawaa còn cung cấp các cấu trúc dữ liệu cơ bản: stack, queue, list, tree….. nên người dùng có thể mô hình những cấu trúc dữ liệu này dễ dàng hơn JSAMBA. Các lệnh trong file kịch bản có thể được thực hiện riêng biệt hoặc trong một khối lệnh. Một ưu điểm nữa là Jawaa cho phép dùng miễn phí. Nhược điểm JAWAA không cho phép người dùng xem lại các bước đã mô phỏng nên việc muốn xem lại một thao tác nào đó đồng nghĩa với việc quan sát lại toàn bộ mô phỏng của một thuật toán. Hơn nữa, vì có cùng mô hình với JSAMBA nên JAWAA cũng yêu cầu một file kịch bản riêng. Đây là một hạn chế lớn đối với trình độ của học sinh trung học phổ thông. JANIME JANIME ( được viết bởi Noonan (trường đại học William và Mary). Đây cũng là một hệ thống mô phỏng trên nền web với mục đích phục vụ giảng dạy và được viết bằng java. JANIME rất giống với JAWWA, nó cũng cung cấp một số cấu trúc dữ liệu (mảng, stack và queue) và các hình vẽ cơ bản như: đoạn văn bản, hình chữ nhật, hình tròn, đoạn thẳng và đa giác. Mặc dù, JANIME chứa ít cấu trúc dữ liệu hơn JAWWA nhưng nó chứa sẵn nhiều lệnh kịch bản hơn và nhiều công cụ điều khiển hơn trong khi mô phỏng. Ưu điểm Trang 52 Tương tự như JAWWA nên nó có hầu hết các ưu điểm giống như JAWWA và một ưu điểm của JANIME là cho phép quan sát lại các bước đã thực hiện. Nhược điểm Mặc dù có nhiều ưu điểm hơn cả Jawwa nhưng nói chung các phần mềm mô phỏng có cùng một mô hình thường có nhược điểm giống nhau. Đều khó cho việc tự học của học sinh cũng như thời gian chuẩn bị các file kịch bản của giáo viên khi giảng dạy. Một nhược điểm nữa của Janime là không được dùng “miễn phí”. 6.2. Sử dụng công cụ mô phỏng thuật toán riêng biệt Có một số chương trình mô phỏng cụ thể về một thuật toán nào đó được viết rất nhiều và miễn phí trên mạng. Hình vẽ dưới đây hiển thị các kết quả khi tìm kiếm bằng google với khóa là “Algorithm Animation”. Chỉ trong 0.07s có tới 2.820.000 kết quả Trang 53 Sử dụng các chương trình này có một lợi ích là chỉ việc học cách sử dụng mà không mất thời gian xây dựng. Hình ảnh mô phỏng khá đa dạng và phong phú. Các thuật toán được mô phỏng tương đối nhiều. Tuy nhiên, các chương trình này được xây dựng một cách riêng rẽ (của các tác giả khác nhau), không có một hệ thống quy chuẩn nhất định. Có thể là của một trường đại học nổi tiếng (ví dụ: software/ AlgAnim/alg_anim.html) nhưng cũng có thể chỉ là một bài tập cá nhân ( code.html). Những chương trình này không có một hệ thống kiểm định tính đúng sai. Nếu học sinh “tự học” một mô hình mô tả sai cách thức hoạt động (có thể vì tự tìm được một mô hình mô phỏng của thuật toán) thì thật là “nguy hiểm” nếu người học tiếp thu theo đúng mô hình đó. 6.3. Xây dựng hệ thống từ đầu Khi hệ thống hiện tại không phù hợp với người dùng (có thể vì: không được đầu tư ngân sách, không hợp ngữ cảnh…) dẫn đến phát sinh yêu cầu một hệ thống mới. Hệ thống này sẽ bắt đầu được xây dựng từ nền tảng hoàn toàn mới dựa trên mô tả thực của người dùng. Trang 54 Chương 3 PHÂN TÍCH THIẾT KẾ HỆ THỐNG MÔ PHỎNG MỘT SỐ THUẬT TOÁN TRÊN ĐỒ THỊ 1.Mục đích Hệ thống được xây dựng nhằm giúp giáo viên có thể sử dụng như một công cụ giảng dạy các thuật toán trên đồ thị. Nó cũng có thể giúp học sinh chuyên Tin tự tìm hiểu thuật toán khi học các thuật toán trên đồ thị với cách thức hoạt động theo mô tả của thuật toán và những thay đổi trực quan bằng đồ họa. 2.Những yêu cầu thực tế Năm 2009, Bộ Giáo dục và Đào tạo cho xuất bản bộ Tài liệu giáo khoa chuyên Tin (3 tập - Hồ Sĩ Đàm chủ biên). Đây là tài liệu giới thiệu các thuật toán cơ bản, thường dùng. Bộ sách này có thể dùng cho giáo viên và học sinh Trung học phổng thông, Trung học cơ sở có thể làm tài liệu tham khảo. Tuy nhiên, để giúp học sinh có thể tự chuẩn bị trước các thuật toán ở nhà và giúp giáo viên làm rõ những thắc mắc của học sinh về thuật toán cơ bản và các cải tiến có thể làm giảm độ phức tạp của các thuật toán đó cần phải có thêm những công cụ giúp làm hiệu quả hơn cho công việc chuẩn bị của học sinh cũng như dẫn giải của giáo viên trong khi giảng bài. Chương trình mô phỏng của chúng tôi hướng tới mục tiêu đó. Mô phỏng một cách có hệ thống các thuật toán cơ bản mà học sinh chuyên sẽ học (theo phân phối chương trình chuyên). Đó là các thuật toán: bài toán tìm kiếm trên đồ thị, bài toán tìm đường đi ngắn nhất và bài toán tìm cây khung cực tiểu trên đồ thị vô hướng. Như đã phân tích trong mục 7 chương 2 về một số phần mềm mô phỏng, đã có nhiều trang web giới thiệu chương trình mô phỏng về các thuật toán miễn phí ở trên mạng Internet. Nhưng tổng hợp lại, các chương trình đó đều có chứa những nhược điểm có thể chỉ ra như sau: Trang 55 - Hầu hết các chương trình này đều là một dạng bài tập. Hay nói cách khác, người viết chỉ hoàn thiện một thuật toán riêng lẻ, các thuật toán được giới thiệu một cách rời rạc. ( .cs.auckland.ac.nz /~jmor159/PLDS210/alg_anim.html) - Hầu hết các chương trình chỉ giới thiệu về thuật toán sau đó cho phép người dùng chạy thử trên một mẫu dữ liệu có sẵn ( plet.htm). Hay nói cách khác các chương trình mô phỏng chỉ làm một việc là trình chiếu cho người sử dụng nhìn thấy các bước hoạt động của thuật toán đó. Việc theo dõi kịp các bước đó để hiểu đã thuật toán đã là một thử thách. Việc đó còn khó hơn đối với người bắt đầu học một thuật toán cụ thể nào đó chưa kể đến là các thuật toán đó đều trừu tượng. - Cũng đã có trang web giới thiệu 2 thuật toán Kruskal và Dijsktra cùng với việc cho phép người dùng quan sát mã nguồn của thuật toán (ở ngôn ngữ Java) nhưng việc giới thiệu này đòi hỏi người dùng muốn hiểu thuật toán phải biết một chút về Java. Vì vậy, hệ thống cũng khó phổ biển ở Việt Nam được vì ngôn ngữ lập trình mà học sinh Việt Nam được học là ngôn ngữ lập trình Free Pascal và Turbo Pascal và C. - Chưa cho phép người dùng đưa dữ liệu của mình vào để thử nghiệm thuật toán. 3. Đề xuất cho hệ thống mới Hệ thống mới cho phép người dùng quan sát hoạt động của thuật toán đồng thời trên dữ liệu mẫu và trên đoạn giả mã của thuật toán đó. Hệ thống còn cho phép chạy toàn thuật toán, chạy từng bước, lùi một bước để tiện quan sát những thay đổi trên đoạn giả mã và trên dữ liệu mẫu. Trang 56 Hệ thống cũng cho phép người học đưa dữ liệu vào (là đồ thị có hướng, vô hướng, có trọng số hoặc không trọng số tùy theo thuật toán mà người học lựa chọn). 4. Thiết kế hệ thống mô phỏng một số thuật toán trên đồ thị Mô hình được áp dụng cho chương trình mô phỏng trong luận văn này là mô hình thác nước. Các bước phân tích thiết kế gồm: Sơ đồ quy trình phân tích và thiết kế các nhiệm vụ khi thuật toán mô phỏng. Chi tiết về các bước của quá trình này đã được giới thiệu trong phần 5 – chương 3 của luận văn này. Nghiên cứu và phân tích giải thuật Xây dựng mô hình mô phỏng dữ liệu vào và dữ liệu ra Tách giải thuật mô phỏng thành nhiều bước nhỏ Tổng hợp các bước mô phỏng thành giải thuật hoàn chỉnh Kiểm nghiệm giải thuật bằng cách quan sát dữ liệu ra của từng bước nhỏ Trang 57 4.1. Lựa chọn công cụ lập trình Trong luận văn này, chúng tôi không xem xét ngôn ngữ C# một cách tách biệt, nó luôn đồng hành với "Bộ khung .NET". C# là một trình biên dịch hướng .NET, nghĩa là tất cả các mã của C# luôn luôn chạy trên trên môi trường .NET Framework. Điều đó dẫn đến 2 hệ quả sau: Cấu trúc và các lập luận C# được phản ánh các phương pháp luận của .NET ngầm bên dưới. Trong nhiều trường hợp, các đặc trưng của C# thậm chí được quyết định dựa vào các đặc trưng của .NET, hoặc thư viện lớp cơ sở của .NET. Trong Microsoft Intermediate Language (thường được viết tắt là "Intermediate Language", hay "IL") tương tự như ý tưởng về mã Java byte, nó là một ngôn ngữ cấp thấp với những cú pháp đơn giản (dựa trên cơ sở mã số hơn là text), chính điều này sẽ làm cho quá trình dịch sang mã máy nhanh hơn. Hiểu kĩ các cú pháp này sẽ mang lại những lợi ích đáng kể. Hướng đối tượng Dữ liệu mẫu đưa vào chương trình được mô phỏng bằng đồ họa: - Dữ liệu mẫu - Dữ liệu trực tiếp - Mô phỏng theo từng bước - Mô phỏng tự động toàn bộ thuật toán - Đồ thị đã được mô phỏng bằng đồ họa: những thay đổi trên hình vẽ qua các bước thực thi thuật toán. Input Thuật toán Output Mô hình bài toán mô phỏng thuật toán Trang 58 Như mọi ngôn ngữ lập trình hướng đối tượng khác, C# có các tính năng đóng kín, kế thừa và đa hình. Mỗi lớp của C# bao gồm các trường và phương thức tương ứng. Trong đó: Trường: là dữ liệu chỉ trạng thái của đối tượng. Phương thức: là các khả năng của đối tượng trả lời các tác động đến nó. Độc lập nền Trước tiên, độc lập nền có nghĩa là các file chứa mã lệnh có thể chạy trên bất kì nền nào, vào thời gian chạy trình biên dịch cuối sẽ hoạt động và mã có thể chạy trên một nền cụ thể. Nói cách khác việc dịch mã nguồn sang Intermediate Language cho phép độc lập nền trong .NET, nó giống như cách dịch mã nguồn sang Java byte code cung cấp sự độc lập nền trong Java. Sự cải tiến trong thực thi Mặc dù chúng ta đã so sánh với Java, IL thật sự có một chút khả quan hơn Java. IL luôn là trình biên dịch mạnh, ngược lại Java byte code thì thường là thông dịch. Một trong những bất lợi của Java là vào lúc thực thi quá trình dịch từ java byte code sang mã máy tốn nhiều tài nguyên. Thay vì phải dịch toàn bộ ứng dụng một lần, trình biên dịch JIT sẽ biên dịch từng phần mã khi nó được gọi. Khi mã được dịch rồi, mã kết quả sẽ được giữ lại cho tới khi thoát khỏi ứng dụng, chính vì thế nó không phải biên dịch lại trong lần chạy kế tiếp. Microsoft quả quyết rằng cách xử lí này có hiệu lực cao hơn là dịch toàn bộ ứng dụng, bởi vì có trường hợp một khối lượng lớn mã của ứng dụng không bao giờ được sử dụng trong thời gian chạy. Khi sử dụng trình biên dịch JIT, các đoạn mã này sẽ không bao giờ được dịch. Chính vì thế nhà cung cấp hi vọng rằng mã IL sẽ thực thi nhanh như là mã máy. Lời lí giải là, lần dịch cuối cùng trong thời gian chạy, trình biên dịch JIT sẽ biết chính xác loại vi xử lí mà chương trình sẽ chạy. Có nghĩa là nó có thể tối ưu Trang 59 mã thi hành cuối cùng bằng cách tham chiếu đến các đặc trưng của từng các bộ lệnh ứng với các loại vi xử lí đó. Trình biên dịch JIT có thể thực hiện tối ưu giống như Visual Studio 6, ngoài ra nó còn có thể tối ưu cho các loại vi xử lí cụ thể mà mã chương trình sẽ chạy. Tương hoạt giữa các ngôn ngữ Chúng ta đã biết cách thức IL cho phép độc lập nền, trình biên dịch JIT có thể cải thiện quá trình thực thi. Tuy nhiên, IL cũng làm cho tương hoạt giữa các ngôn ngữ trở nên dễ dàng hơn. Bạn có thể biên dịch IL từ một ngôn, và mã này sau đó có thể tương hoạt với IL được biên dịch bởi một ngôn ngữ khác. Bảo mật và hiệu quả cao C# là một thành phần của bộ Visual Studio .NET dành cho lập trình môi trường mạng nên nó có khả năng bảo mật cao. Cấu trúc câu lệnh khá đơn giản, khả chuyển, giao diện đồ họa, dễ sử dụng. Làm được tất cả những gì Java có thể làm được. 4.2. Chức năng mô phỏng của các thuật toán được cài đặt 4.2.1 Mô phỏng thuật toán tìm kiếm Khung chương trình cho phép người dùng nhập đồ thị để mô phỏng: tạo một đồ thị mới, tạo một đồ thị đã chuẩn bị từ trước: Trang 60 Màn hình mô phỏng được chia thành 3 phần. Phần giả mã, phần trạng thái của các đối tượng trong quá trình thực hiện thuật toán và phần hình ảnh đồ thị. Người dùng có thể lựa chọn thực hiện thuật toán trên đồ thị có hướng hoặc vô hướng. Chương trình mô phỏng cố gắng làm rõ cách thức hoạt động của thuật toán theo từng bước giã mã ở trên theo cách: Công cụ để tạo đồ thị cho mô phỏng Khung giả mã Khung mô phỏng bằng hình ảnh đồ thị Khung trạng thái Trang 61 Tại khung giả mã: Chứa đoạn giả mã của thuật toán tìm kiếm tương ứng với lựa chọn của người dùng. Thuật toán thực hiện đến bước nào thì bước đó đổi màu cho người dùng tiện quan sát. Tại khung trạng thái: Ghi nhận và hiển thị những thay đổi của tập các đỉnh đã được thăm, đỉnh đang được xét…. Tại khung đồ thị: Hình ảnh đồ thị sẽ thay đổi theo mỗi bước thuật toán thực hiện qua. Các đỉnh đã được thăm qua sẽ được tô màu vàng. Các cạnh trên đường đi tìm thấy sẽ được tô màu đỏ để người học quan sát kết quả một cách trực quan. 4.2.2. Mô phỏng thuật toán Dijkstra Khung chương trình cho phép người dùng nhập đồ thị để mô phỏng: Khung chương trình mô phỏng thuật toán: Trang 62 Việc mô phỏng thuật toán Dijkstra trong chương trình cho phép người dùng có thể lựa chọn trên 2 loại đồ thị: Đồ thị vô hướng có trọng số hoặc đồ thị có hướng có trọng số. Cũng giống như việc mô phỏng cho bài toán tìm kiếm, màn hình mô phỏng được chia thành ba phần: - Khung giả mã: Mô tả thuật toán Dijkstra bằng giả mã dạng liệt kê. Thuật toán thực hiện đến bước nào thì bước đó đổi màu cho người dùng tiện quan sát. - Khung trạng thái: Ghi nhận và hiển thị những thay đổi của tập các đỉnh đã được thăm, đỉnh đang được sửa nhãn, đỉnh mới kết nạp vào tập các đỉnh đã được tối ưu nhãn…. - Khung đồ thị: Hình ảnh đồ thị sẽ thay đổi theo mỗi bước thuật toán thực hiện qua. Các đỉnh đã được thăm qua sẽ được tô màu vàng, các giá trị đã tối ưu thể hiện chi phí ngắn nhất từ đỉnh xuất phát đến các đỉnh trung gian được tô màu đỏ. Các cạnh trên đường đi tìm thấy sẽ được tô màu đỏ hoặc một thông báo không tìm thấy đường đi từ đỉnh xuất phát đến đỉnh đích để người học quan sát kết quả một cách trực quan. Khung giả mã của thuật toán Khung mô phỏng trên đồ thị Khung trạng thái của thuật toán Trang 63 4.2.3. Mô phỏng thuật toán Ford – Bellman Vì thuật toán Ford – Bellman cũng là thuật toán tìm đường đi ngắn nhất giữa hai cặp đỉnh của đồ thị có trọng số giống như Dijkstra nên dưới đây, chúng tôi chỉ xin giới thiệu về màn hình là việc của chương trình (còn ý nghĩa các khung làm việc giống hệt thuật toán Dijkstra. 4.2.4. Mô phỏng thuật toán Prim Do thuật toán Prim tìm cây khung nhỏ nhất chỉ được thực hiện trên đồ thị vô hướng có trọng số nên trong chương trình mô phỏng người dùng không có các lựa chọn như các thuật toán trên, chỉ có thể nhập cho đồ thị vô hướng có trọng số. Khung chương trình mô phỏng cũng tương tự như các thuật toán đã mô tả ở trên. Khung chương trình để người dùng nhập dữ liệu đầu vào: Khung giả mã của thuật toán Khung mô phỏng trên đồ thị Khung trạng thái của thuật toán Trang 64 Khung chương trình mô phỏng: Tại khung giả mã: Chứa đoạn giả mã của thuật toán Prim tương ứng với lựa chọn của người dùng. Thuật toán thực hiện đến bước nào thì bước đó đổi màu cho người dùng tiện quan sát. Tại khung trạng thái: Ghi nhận và hiển thị những thay đổi của tập các đỉnh đã được thăm, đỉnh đang được xét…. Khung giả mã Khung mô phỏng bằng hình ảnh đồ họa Khung trạng thái Trang 65 Tại khung đồ thị: Hình ảnh đồ thị sẽ thay đổi theo mỗi bước thuật toán thực hiện qua. Các đỉnh đã được thăm qua sẽ được tô màu vàng. Các đỉnh đã được kết nạp vào cây và các cạnh thuộc sẽ được tô màu đỏ để người học quan sát kết quả một cách trực quan. 4.2.5. Mô phỏng thuật toán Kruskal Do thuật toán Kruskal tìm cây khung nhỏ nhất chỉ được thực hiện trên đồ thị vô hướng có trọng số nên trong chương trình mô phỏng người dùng không có các lựa chọn như các thuật toán trên, chỉ có thể nhập cho đồ thị vô hướng có trọng số. Khung chương trình mô phỏng cũng tương tự như các thuật toán đã mô tả ở trên. Khung chương trình để người dùng nhập dữ liệu đầu vào: Khung chương trình mô phỏng: Trang 66 Tại khung giả mã: Chứa đoạn giả mã của thuật toán Kruskal tương ứng với lựa chọn của người dùng. Thuật toán thực hiện đến bước nào thì bước đó đổi màu cho người dùng tiện quan sát. Tại khung trạng thái: Ghi nhận và hiển thị những thay đổi của tập các đỉnh đã được thăm, đỉnh đang được xét…. Tại khung đồ thị: Hình ảnh đồ thị sẽ thay đổi theo mỗi bước thuật toán thực hiện qua. Các đỉnh đã được thăm qua sẽ được tô màu vàng. Các đỉnh đã được kết nạp vào cây và các cạnh thuộc sẽ được tô màu đỏ để người học quan sát kết quả một cách trực quan. 4.2.6. Thuật toán tìm chu trình Hamilton 5. Giới thiệu chương trình 5.1.Tổng quan về hệ thống Hệ thống mô phỏng được chia thành các module nhỏ. Mỗi module thực hiện một chức năng riêng biệt. Có 2 module chính: Module GraphTool: Thực hiện công việc thiết kế giao diện dành cho quá trình mô phỏng. Từ việc nhập đồ thị mới, người dùng lựa chọn thuật toán mô phỏng và mô phỏng theo kịch bản đã được “dựng” sẵn. Khung giả mã Khung mô phỏng bằng hình ảnh đồ họa Khung trạng thái Trang 67 Module Model: Thực hiện cài đặt các mô hình thuật toán, lưu trữ các thông tin cần thiết và lên kịch bản cho quá trình mô phỏng. Giữa hai module này luôn có mối quan hệ khăng khít với nhau. Một module thực thi thuật toán do người dùng lựa chọn sau đó lên kịch bản để mô phỏng. Module còn lại tiếp nhận kịch bản từ module kia và mô phỏng theo kịch bản đã được dựng sẵn theo đúng mô hình thuật toán đã được thực thi để trình chiếu tới người học. Để việc mô phỏng có thể áp dụng được với nhiều thuật toán khác nhau, tại mỗi module, việc cài đặt các công cụ hỗ trợ cho quá trình mô phỏng và dựng kịch bản mô phỏng chúng tôi luôn dựng ở dạng tổng quát. Thêm vào đó là một số công cụ riêng rẽ, thể hiện đặc trưng của mỗi thuật toán. Dưới đây là một số đối tượng dùng chung cho quá trình mô phỏng: 5.1.1. Các đối tượng xây dựng cấu trúc đồ thị  Entity: chứa 3 thuộc tính: + Key: tên của đỉnh trong đồ thị + Value: Trọng số của cạnh (trong trường hợp đồ thị là vô hướng thì trọng số = 1 nghĩa là 2 đỉnh có cạnh nối, = 0 nghĩa là không có cạnh nối) + IsDirection: đánh dấu đồ thị ban đầu là có hướng hay vô hướng. public class Entity { public virtual string Key { get; set; } public virtual int Value { get; set; } public static bool IsDirection {get; set;}  Đối tượng Graph: gồm các thuộc tính: + Tập các đỉnh Vertexs + Tập các cạnh. public class Graph { public Graph() { Vertexs = new HashSet(); } Trang 68 public HashSet Vertexs { get; set; } public int GetEdgeValue(string fromKey, string toKey) { Vertex from = GetVertex(fromKey); if (from.ConnectTo(toKey)) { return from.GetEdge(fromKey, toKey).Value; } return int.MaxValue; } public Vertex GetVertex(string key) { foreach (Vertex v in Vertexs) { if (v.Key == key) return v; } throw new Exception("Key is not exist."); } }  Vertex: Chứa các thuộc tính về đỉnh + Kế thừa các thuộc tính của lớp Entity + Phương thức: ConnectTo: xác định đỉnh kề với đỉnh đang xét NextToVertex: Xác định tập các đỉnh kề với đỉnh đang xét. AddEdge: Thêm 1 cạnh (cung) có 1 đầu mút là đỉnh đang xét. RemoveEdge: Loại bỏ 1 cạnh (cung) có 1 đầu mút là đỉnh đang xét. public class Vertex : Entity { private Dictionary _edges = new Dictionary<string, Edge>(); private IList _nextToVertexs = new List(); public bool ConnectTo(string keyTo) { string edgeKey = this.Key + ">" + keyTo; if (_edges.ContainsKey(edgeKey)) return true; if (Entity.IsDirection == false) { edgeKey = keyTo + ">" + this.Key; if (_edges.ContainsKey(edgeKey)) return true; } return false; } Trang 69 public void AddEdge(Edge edge) { _edges.Add(edge.Key, edge); if (edge.FromVertexKey != Key) { _nextToVertexs.Add(edge.FromVertexKey); } else if (edge.ToVertexKey != Key) { _nextToVertexs.Add(edge.ToVertexKey); } } public void RemoveEdge(Edge edge) { _edges.Remove(edge.Key); if (edge.FromVertexKey != Key) { _nextToVertexs.Remove(edge.FromVertexKey); } else if (edge.ToVertexKey != Key) { _nextToVertexs.Remove(edge.ToVertexKey); } } public void RemoveAllEdges() { _edges.Clear(); } public Edge GetEdge(string fromKey, string toKey) { if (string.IsNullOrEmpty(fromKey) || string.IsNullOrEmpty(toKey)) throw new ArgumentNullException("Key is not alowed null."); string edgeKey = fromKey + ">" + toKey; if (_edges.ContainsKey(edgeKey)) return _edges[edgeKey]; else if (Entity.IsDirection == false) { edgeKey = toKey + ">" + fromKey; return _edges[edgeKey]; } throw new Exception("Not found edge"); } public IList GetNextToVertexs() { return _nextToVertexs; }  Edge: chứa các thuộc tính về đỉnh thừa kế từ lớp Entity bao gồm 2 thông số: + Cạnh được nối từ FromVertexKey đến ToVertexKey. + Trọng số của cạnh (trong trường hợp đồ thị không trọng số thì ta dùng giá trị này để đánh dấu có cạnh nối giữa 2 đỉnh hay không). Trang 70 public class Edge : Entity { public override string Key { get { return FromVertexKey + ">" + ToVertexKey; } set { base.Key = value; } } public string FromVertexKey { get; set; } public string ToVertexKey { get; set; } }  Một cái “túi” để “đựng” các bước thực hiện theo thuật toán để mô phỏng. public class BagStep { private IList _steps = new List(); public void AddStep(Step step) { _steps.Add(step); } public IList Steps { get { return _steps; } } } 5.1.2. Công cụ vẽ hình ảnh để mô phỏng  CanvasDrawing: Xây dựng toàn bộ đồ thị nền trước, trong và sau khi mô phỏng.  EdgeDrawing: vẽ cạnh trước, trong và sau khi thực hiện thuật toán mô phỏng.  EntityDrawing: Chuyển đổi 2 chế độ: chế độ cho phép người dùng nhập một đồ thị đầu vào và chế độ mô phỏng.  VertexDrawing: vẽ đỉnh trước, trong và sau khi thực hiện thuật toán mô phỏng, những thay đổi giá trị trên các đỉnh cũng được thể hiện trên hình vẽ. 5.1.3. Chức năng chi tiết của các công cụ hỗ trợ cho quá trình mô phỏng Thủ tục Chức năng Trang 71 public void AddEdgeDrawing(string fromVertex, string toVertex, int value) Vẽ một cạnh private void RemoveVertexDrawing(VertexDrawing vertexDrawing){} Vẽ đỉnh public bool IsInShortestPath { get; set; } Chứa đựng thông tin về các cạnh trên đường đi ngắn nhất của thuật toán Dijkstra public bool IsInSpanningTree { get; set; } Chứa đựng thông tin về các cạnh thuộc cây khung của thuật toán Prim public bool IsInFindingPath { get; set; } Chứa đựng thông tin về các cạnh trên đường đi từ đỉnh xuất phát đến đỉnh kết thúc của thuật toán tìm kiếm DFS và BFS private void DrawAtDesignMode(DrawingContext drawingContext) Chế độ đồ họa trong khi xây dựng dữ liệu đầu vào private void DrawAtRunMode(DrawingContext drawingContext) Chế độ đồ họa trong khi thực hiện mô phỏng trên đồ thị đã cho public void AddEdgeDrawing(EdgeDrawing e) {} public void RemoveEdgeDrawing(EdgeDrawing e) {} public void ReRender(){} public void RemoveAllEdgeDrawings(){} Các công cụ hỗ trợ quá trình thiết kế dữ liệu đầu vào bằng hình vẽ và quá trình mô phỏng. 5.2. Giới thiệu các công cụ hỗ trợ mô phỏng do người dùng cài đặt Như đã nói ở trên, chúng tôi dùng C# là ngôn ngữ cài đặt chương trình mô phỏng là để tận dụng các ưu điểm của nó. Việc mô phỏng trong chương trình được chia thành các module, các chức năng hỗ trợ việc mô phỏng lại được chia thành các module nhỏ hơn, đóng kín với các module khác. Các lớp độc lập nhau có thể coi như một kiểu dữ liệu để khai báo trong chương trình khi cần sử dụng. 7.3.1 Tìm kiếm: Tìm kiếm theo mô hình DFS: Chương trình con: Trang 72  DFS mô phỏng: Module: GraphTool.Searching.DFSForm  DFS thực thi thuật toán và “lên” kịch bản: GraphTool.Model.DFS Kiến trúc: Chức năng: các công cụ và chức năng của chúng trong mô hình cài đặt  Các công cụ trong chương trình: private Dictionary _trace =new Dictionary<string, string>(); private Dictionary _free = new Dictionary(); public Graph Graph { get; set; } public string VertexKeyStart {get; set;} public string VertexKeyEnd {get; set;} private BagStep _steps = new BagStep();  Công cụ thuật toán:các thuật toán trợ giúp cho thuật toán chính: Thủ tục Chức năng public void Execute() Thực thi thuật toán. private void GetResult() Lấy kết quả và lưu trữ vào các bước cho vào túi. public BagStep GetBagStep() Lấy túi đã đựng các bước để chuyển qua mô phỏng. private void DfsAlgorithms(Vertex u) Chương trình đệ quy thực hiện việc thăm theo mô hình DFS từ một đỉnh u tới các đỉnh kề với nó. private void Initialize() Khởi tạo các thông số đồ thị dựa trên mô hình đồ thị mà người dùng đưa vào trước khi thực hiện thuật toán. Trả lại các bước thuật toán đã thực hiện trên bộ dữ liệu đầu vào để chương trình mô phỏng bắt đầu làm việc DFS mô phỏng: Module: GraphTool.Sear ching.DFSForm DFS thực thi thuật toán: GraphTool.Mo del.DFS Chuyển mô hình đồ thị mà người dùng đã chuẩn bị cho Module Model.DFS thực hiện thuật toán Trang 73 private void UpdateTrace(string after, string before) Thực hiện công việc truy vết. private void UpdateInfoAtStepEnd() Hoàn thiện thuật toán. Ghi nhận các cạnh đã đi qua theo mô hình DFS. Các bước sẽ được lưu trữ trong túi. public class StepStartDFS() Step kế thừa của lớp Step, khởi tạo đỉnh xuất phát public class StepEndDFS : Step Ghi nhận những cạnh đã thăm trong quá trình thực hiện theo thuật toán DFS và truy vết. public class DfsStep1 : Step public class DfsStep21 : Step public class DfsStep22 : Step public class DfsStep23 : Step public class DfsStep3 : Step Các bước được làm mịn trong quá trình mô phỏng thuật toán DFS. Thừa kế từ lớp Step Tìm kiếm theo mô hình BFS: Chương trình con:  BFS mô phỏng: Module: GraphTool.Searching.BFSForm  BFS thực thi thuật toán: GraphTool.Model.BFS Kiến trúc: Chức năng: các công cụ và chức năng của chúng trong mô hình cài đặt  Các công cụ sử dụng trong chương trình: private Dictionary _trace = new Dictionary(); private Dictionary _free = new Dictionary(); public Graph Graph { get; set; } private Queue _Q = new Queue(); public string VertexKeyStart { get; set; } public string VertexKeyEnd { get; set; } Trả lại các bước thuật toán đã thực hiện trên bộ dữ liệu đầu vào để chương trình mô phỏng bắt đầu làm việc BFS mô phỏng: Module: GraphTool.Sear ching.BFSForm BFS thực thi thuật toán: GraphTool.Mo del.BFS Chuyển mô hình đồ thị mà người dùng đã chuẩn bị cho Module Model.BFS thực hiện thuật toán Trang 74 private BagStep _steps = new BagStep();  Các chương trình con và chức năng của chúng: Thủ tục Chức năng public void Execute() Thực thi thuật toán. private void GetResult() Lấy kết quả và lưu trữ vào các bước cho vào túi. public BagStep GetBagStep() Lấy túi đã đựng các bước để chuyển qua mô phỏng. private void BfsAlgorithms(Vertex u) Chương trình đệ quy thực hiện việc thăm theo mô hình BFS từ một đỉnh u tới các đỉnh kề với nó. private void Initialize() Khởi tạo các thông số đồ thị dựa trên mô hình đồ thị mà người dùng đưa vào trước khi thực hiện thuật toán. private void UpdateTrace(string after, string before) Thực hiện công việc truy vết. private void UpdateInfoAtStepEnd() Hoàn thiện thuật toán. Ghi nhận các cạnh đã đi qua theo mô hình BFS. Các bước sẽ được lưu trữ trong túi. Public class StepStart1() Step kế thừa của lớp Step, khởi tạo đỉnh xuất phát Public class StepEnd1 : Step Ghi nhận những cạnh đã thăm trong quá trình thực hiện theo thuật toán BFS và truy vết. Public class BfsStep1 : Step Public class BfsStep21 : Step Public class BfsStep22 : Step Public class BfsStep23 : Step Public class BfsStep3 : Step Các bước được làm mịn trong quá trình mô phỏng thuật toán BFS. 7.3.2 Dijsktra Chương trình con  Dijsktra mô phỏng: Module: GraphTool.Searching.dijkstraForm  Dijkstra thực thi thuật toán: GraphTool.Model.dijkstra: thực thi theo đúng thuật toán và lưu lại các bước đã thực hiện vào trong một cái túi (BagStep) dùng trong mô phỏng. Kiến trúc: Trang 75 Chức năng: các công cụ và chức năng của chúng trong mô hình cài đặt  Công cụ sử dụng trong module: private HashSet _vertexGone = new HashSet(); private HashSet _vertexGo = new HashSet(); private Dictionary _trace = new Dictionary<string, string>(); private Dictionary _distance = new Dictionary(); private BagStep _steps = new BagStep(); public Graph Graph { get; set; } public string VertexKeyStart { get; set; } public string VertexKeyEnd { get; set; } public BagStep GetBagStep()  Các chương trình con và chức năng của chúng: Thủ tục Chức năng public void Execute() Thực hiện thuật toán Dijkstra public void Initialize(); Khởi tạo các thông số cần thiết cho thuật toán private void UpdateEdgeGo(Vertex u) Sửa nhãn cho tất cả các đỉnh chưa được chọn khi mới cố định đỉnh u Trả lại các bước thuật toán đã thực hiện trên bộ dữ liệu đầu vào để chương trình mô phỏng bắt đầu làm việc Dijkstra mô phỏng: Module: GraphTool.Dijk tra.DijktraFor m Dijkstra thực thi thuật toán: GraphTool.Mo del.Dijkstra Chuyển mô hình đồ thị mà người dùng đã chuẩn bị cho Module Model.Dijkstra thực hiện thuật toán Trang 76 private void UpdateTrace(string after, string before) Cập nhật vết cho đường đi trong khi thực hiện thuật toán private void UpdateInfoAtStepEnd() Ghi lại các thông số cuối cùng để dựng kịch bản cho mô phỏng private void AddVertextToVertexGone(Vertex gone) Kết nạp thêm một đỉnh vào tập S (các đỉnh đã cố định nhãn) private void AddStepStart() Ghi nhận bước đi đầu tiên của thuật toán Dijkstra trên đồ thị vừa chọn. private void AddStepStart12(string key) private void AddStepUpdateVertexValue() private void AddStepUpdateVertexValueStep11() private void AddStepUpdateVertexValueStep12() private void AddStepChooseVertexMin(string key) private void AddStepAddVertex() private void AddStepEnd() Cập nhật các bước để lên kịch bản mô phỏng public class StepStart : Step { public string VertexStart { get; set; } private Dictionary _d = new Dictionary(); public void UpdateVertexValue(Dictionary d) { foreach (string key in d.Keys) { _d.Add(key, d[key]); } } public Dictionary GetDistanceInfomation() { return _d; } Kịch bản cho mô phỏng: Bước khởi đầu: Xây dựng các thông số ban đầu từ đồ thị do người dùng chuyển vào thành Input cho thuật toán. public class StepEnd : Step { private IList _edgesInShotestPath = new List(); public void UpdateEdgeInfosInShotestPath(Dictionary<string , string> trace, string keyEnd, string keyStart) { Bước cuối cùng: sau khi thực hiện thuật toán Dijkstra, lớp StepEnd lưu giữ lại toàn bộ thông số cần thiết để mô phỏng: các cạnh thuộc đường đi ngắn nhất, các đỉnh thuộc đường đi đó…. Trang 77 string key = keyEnd; while (key != keyStart && key != string.Empty) { _edgesInShotestPath.Add(trace[key] + ">" + key); key = trace[key]; } if (key == string.Empty) _edgesInShotestPath = new List(); } public IList EdgesInShotestPath() { return _edgesInShotestPath; } } //step 1 public class StepUpdateVertexValue : Step { private Dictionary _d = new Dictionary(); public void UpdateVertexValue(Dictionary d) {foreach (string key in d.Keys) { _d.Add(key, d[key]); } } public Dictionary GetDistanceInfomation() { return _d; } } Bước 1: Sửa nhãn cho tất cả các đỉnh //step 2 public class StepChooseVertexMin : Step { public string Min { get; set; } } Bước 2: Chọn một đỉnh có nhãn nhỏ nhất để cố định. //step3 public class StepAddVertex : Step { private IList _gones = new List(); public IList GetAddedVertex() { return _gones; } } Bước 3: thêm đỉnh vừa chọn ở bước 2 vào tập các đỉnh đã được cố định nhãn. Trang 78 7.3.3 Prim Với thuật toán Prim – thuật toán tìm cây khung nhỏ nhất, đồ thị được lựa chọn chỉ là một: đồ thị vô hướng có trọng số và người dùng cũng chỉ cần lựa chọn đỉnh xuất phát. Từ đỉnh xuất phát đó, chương trình mô phỏng sẽ thực hiện đúng trình tự của thuật toán Prim để kết nạp dần các đỉnh vào cây khung. Thuật toán dừng khi hoặc đã dựng thành cây khung hoặc đồ thị đã cho không liên thông (không có nghiệm). Cũng giống như Dijkstra, chương trình mô phỏng thực hiện Chương trình con:  Prim mô phỏng: Module: GraphTool.Prim.PrimForm  Prim thực thi thuật toán: GraphTool.Model.Prim Kiến trúc: Chức năng: các công cụ và chức năng của chúng trong mô hình cài đặt Thủ tục Chức năng public void Execute() Thực hiện thuật toán Prim public void Initialize(); Khởi tạo các thông số cần thiết cho Trả lại các bước thuật toán đã thực hiện trên bộ dữ liệu đầu vào để chương trình mô phỏng bắt đầu làm việc Prim mô phỏng: Module: GraphTool.Pri m.PrimForm Prim thực thi thuật toán: GraphTool.Mo del.Prim Chuyển mô hình đồ thị mà người dùng đã chuẩn bị cho Module Model.Prim thực hiện thuật toán Trang 79 thuật toán private void UpdateEdgeGo(Vertex u) Sửa nhãn cho tất cả các đỉnh chưa được chọn khi mới cố định đỉnh u private void UpdateTrace(string after, string before) Cập nhật các đỉnh và các cạnh thuộc cây khung trong khi thực hiện thuật toán private void UpdateInfoAtStepEnd() Ghi lại các thông số cuối cùng để dựng kịch bản cho mô phỏng private void AddVertextToVertexGone(Vertex gone) Kết nạp thêm một đỉnh vào cây khung private void AddStepStartPrim() Ghi nhận bước đi đầu tiên của thuật toán Prim trên đồ thị vừa chọn. private void AddStepStartPrim(string key) private void AddStepUpdateVertexValuePrim() private void AddStepUpdateVertexValueStep11Prim() private void AddStepUpdateVertexValueStep12Prim() private void AddStepChooseVertexMinPrim(string key) private void AddStepAddVertexPrim() private void AddStepEndPrim() Cập nhật các bước để lên kịch bản mô phỏng Trang 80 Chương 4 KẾT LUẬN 1. Những kết quả đạt được Trải qua quá trình làm việc nghiêm túc, bước đầu chúng tôi đã thu được một số kết quả sau: - Những kiến thức tổng quan, những tính chất cơ bản của thuật toán, lịch sử phát triển của hệ thống mô phỏng; một số ưu điểm và tồn tại của các hệ thống mô phỏng hiện tại; - Đề xuất giải pháp xây dựng một mô hình mô phỏng mới, có hệ thống trên các thuật toán khá phức tạp. Đây là chương trình rất phù hợp với công việc giảng dạy của giáo viên cũng như việc tự học, tự tìm hiểu kiến thức mới của học sinh. - Xây dựng chương trình mô phỏng cụ thể một số thuật toán trên đồ thị gồm: - Thuật toán tìm kiếm theo chiều sâu DFS. - Thuật toán tìm kiếm theo chiều rộng BFS. - Thuật toán tìm đường đi ngắn nhất – thuật toán Ford - Bellman. - Thuật toán tìm đường đi ngắn nhất – thuật toán Dijkstra. - Thuật toán tìm cây khung nhỏ nhất trên đồ thị vô hướng có trọng số - thuật toán Prim. - Thuật toán tìm cây khung nhỏ nhất trên đồ thị vô hướng có trọng số - thuật toán Kruskal. - Thuật toán tìm chu trình Hamilton qua tất cả các đỉnh của đồ thị. Trang 81 2.Hướng phát triển - Triển khai chương trình tới học sinh để ghi nhận những tiến bộ về mặt hiểu bản chất và cách thức hoạt động của các thuật toán. - Có thể sử dụng những module đã cài đặt để tiếp tục mô phỏng các thuật toán nâng cao trên đồ thị: luồng, cặp ghép trên đồ thị…. Trang 82 DANH MỤC TÀI LIỆU THAM KHẢO Tài liệu Tiếng Việt 1. Hồ Sĩ Đàm (chủ biên) – Sách giáo khoa Tin học 10, NXB Giáo dục, trang… 2. Lê Minh Hoàng - Bài giảng chuyên đề 3. Hồ Sĩ Đàm (chủ biên) – Tài liệu giáo khoa chuyên Tin (bộ 2 tập) 4. Thomas H. Cormen Charles E. Leiserson Ronald Rivest – Giáo trình thuật toán - Nhà xuất bản thống kê. 5. TS. Nguyễn Xuân My(chủ biên) – Một số vấn đề chọn lọc trong Tin học (T1+T2) - Nhà xuất bản giáo dục Tài liệu Tiếng Anh 6. Kehoe C., Stasko J., Taylor A., Rethinking the evaluation of algorithm nimations as learning aids: an observational study, Technical Report GIT-GVU-99-10, March, 1999. 7. Stasko, 1990, Tango: A Framework and System for Algorithm Animation. IEEE Computer, 23(9): pp27-39. 8. Brown, 1988 Algorithm Animation. The MIT Press, Cambridge, MA, 1988. 9. [Brown, 1992] Brown, M. Zeus: A system for algorithm animation and multi-view editing (Research Report No.75). DEC Systems Research Center, Palo Alto, CA. 10. Brown, 1993 The 1992 SRC Algorithm Animation Festival. In Proceedings of the 1993 IEEE Symposium on Visual Languages: 116- 123, 1993. 11. Byrne, M. D, Catrambone, R. and Stasko, J. T.(1996). Do algorithm animations aid learning? Graphics, Visualization, and Usability Center, Georgia Institute of Technology, Atlanta, GA, Technical Report GITGVU -96-18, August 1996. Trang web: 12. 13. 14. Trang 83 15. 16. 17. Trang 84 PHỤ LỤC Công đoạn chuẩn bị cho file kịch bản. void arrayExample () { System.out.println(“begin”); String[] a1 = {“4”, “453434”, "HELLO WORLD!", "01010 10101"}; System.out.println(“array a1 50 50 4 4 453434 “+”\"HELLO WORLD!\" ”+”\"01010 10101\" “+”horz black transparent”); //ANNOTATIONS String[] a2 = {"THIS", "IS", "AN", "ARRAY"}; System.out.println(“array a2 150 100 4 “+”\"THIS\" ”+”\"IS\" “+”\"AN\" “”\"ARRAY\" “+ ”vert black transparent”); System.out.println(“end”); //ANNOTATIONS //ANNOTATIONS for multiple commands System.out.println(“begin”); System.out.println(“changeParam a1[0] bkgrd red”); System.out.println(“changeParam a2[0] bkgrd red”); System.out.println(“end”); for ( int i =0; i<4; i++ ) { //ANNOTATIONS for multiple commands System.out.println(“begin”); System.out.println(“changeParam a1[“+String.valueOf(i)+”] bkgrd transparent”); System.out.println(“changeParam a1[“+String.valueOf(i+1)+”] bkgrd red”); System.out.println(“changeParam a1[“+String.valueOf(i)+”] bkgrd transparent”); System.out.println(“changeParam a2[“+String.valueOf(i+1)+”] bkgrd red”); System.out.println(“end”); } //ANNOTATIONS for multiple commands System.out.println(“begin”); System.out.println(“changeParam a1[3] bkgrd transparent”); System.out.println(“changeParam a2[3] bkgrd transparent”); System.out.println(“end”); } Đầu ra của đoạn mã trên là file kịch bản bao gồm các lệnh sẽ dùng để mô phỏng: begin array a1 50 50 4 4 453434 "HELLO WORLD!" "01010 10101" horz black transparent Trang 85 array a2 150 100 4 "THIS" "IS" "AN" "ARRAY" vert black transparent end begin changeParam a1[0] bkgrd red changeParam a2[0] bkgrd red end begin changeParam a1[0] bkgrd transparent changeParam a1[1] bkgrd red changeParam a2[0] bkgrd transparent changeParam a2[1] bkgrd red end begin changeParam a1[1] bkgrd transparent changeParam a1[2] bkgrd red changeParam a2[1] bkgrd transparent changeParam a2[2] bkgrd red end begin changeParam a1[2] bkgrd transparent changeParam a1[3] bkgrd red changeParam a2[2] bkgrd transparent changeParam a2[3] bkgrd red end begin changeParam a1[3] bkgrd transparent changeParam a2[3] bkgrd transparent end Kết quả mô phỏng: File kịch bản này sẽ được thông dịch bởi kênh mô phỏng và các hàm mô phỏng sinh ra các đối tượng cho mô phỏng rồi hiển thị lên màn hình để người dùng quan sát kết quả. Hình vẽ dưới đây là hình ảnh mô phỏng theo đúng file kịch bản được mô tả ở trên: [xem chi tiết tại 15] Trang 86 Bước 1 Bước 2 Bước 3 Bước 4 Bước 5 Bước 6