ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ NGUYỄN THỊ CHINH MÔ PHỎNG MỘT SỐ THUẬT TOÁN TRÊN ĐỒ THỊ
Trang 3
LUẬN VĂN THẠC SĨ Hà Nội - 2011
ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ NGUYỄN THỊ CHINH MÔ PHỎNG MỘT SỐ THUẬT TOÁN TRÊN ĐỒ THỊ
Ngành: Công nghệ thông tin
Chuyên ngành: Hệ thống thông tin
Mã số: 60 48 05
LUẬN VĂN THẠC SĨ
NGƯỜI HƯỚNG DẪN KHOA HỌC: TS. HỒ CẨM HÀ
Trang 4
Hà Nội - 2011
LỜI CAM ĐOAN
Tôi xin cam đoan, kết quả luận văn hoàn toàn là kết quả của tự bản thân
tôi tìm hiểu, nghiên cứu dưới sự hướng dẫn của TS. Hồ Cẩm Hà. Các tài liệu tham khảo được trích dẫn và chú thích đầy đủ.
Học viên
Trang 5
Nguyễn Thị Chinh
LỜI CẢM ƠN
Trước hết, tôi muốn gửi lời cảm đến các Thầy, Cô trong khoa Công nghệ thông tin- Trường Đại học Công nghệ - Đại học Quốc gia Hà nội đã truyền đạt các kiến thức quý báu cho tôi trong suốt thời gian học tập tại trường. Đặc biệt, tôi xin gửi lời cảm ơn sâu sắc tới cô giáo hướng dẫn TS Hồ Cẩm Hà, người đã tận tình chỉ bảo và hướng dẫn về mặt chuyên môn cho tôi trong suốt quá trình thực hiện luận văn này.
Cũng qua đây, tôi xin gửi lời cảm ơn đến Ban Giám hiệu trường THPT Chuyên Đại học Sư phạm Hà Nội, nơi tôi đang công tác đã tạo mọi điều kiện thuận lợi cho tôi trong thời gian học tập cũng như trong suốt quá trình thực hiện luận văn tốt nghiệp.
Cuối cùng, tôi xin cảm ơn gia đình, bạn bè, đồng nghiệp đã luôn ủng hộ, động viên tôi rất nhiều để tôi yên tâm nghiên cứu và hoàn thành luận văn. Trong suốt quá trình làm luận văn, bản thân tôi đã cố gắng tập trung tìm hiểu, nghiên cứu và tham khảo thêm nhiều tài liệu liên quan. Tuy nhiên, do thời gian hạn chế và bản thân còn chưa có nhiều kinh nghiệm trong nghiên cứu khoa học, chắc chắn bản luận văn vẫn còn nhiều thiếu sót. Tôi rất mong được nhận sự chỉ bảo của các Thầy Cô giáo và các góp ý của bạn bè, đồng nghiệp để luận văn được hoàn thiện hơn.
Hà Nội, ngày 12 tháng 06 năm 2011
Trang 6
Nguyễn Thị Chinh
MỤC LỤC
LỜI CẢM ƠN................................................................................................... 6
LỜI NÓI ĐẦU ................................................................................................. 10
Chương 1 MỘT SỐ KIẾN THỨC CƠ BẢN VỀ THUẬT TOÁN .................... 12
1. Khái niệm bài toán Tin học ....................................................................... 12
2. Khái niệm thuật toán ................................................................................. 12
3. Các tính chất của thuật toán ...................................................................... 13
4. Độ phức tạp và xác định độ phức tạp của thuật toán.................................. 14
5. Chi phí thực hiện thuật toán ...................................................................... 18
6. Ba bài toán trên mô hình đồ thị được đưa vào giảng dạy trong trường Trung
học Phổ thông Chuyên .................................................................................. 18
6.1. Một số khái niệm cơ bản về đồ thị ...................................................... 18
6.1.1. Khái niệm đồ thị (Graph).............................................................. 18
6.1.2. Các khái niệm cơ bản ................................................................... 19
6.2. Bài toán tìm kiếm trên đồ thị .............................................................. 21
6.2.1. Phát biểu bài toán ......................................................................... 21
6.2.2. Giới thiệu thuật toán tìm kiếm DFS và BFS ................................. 22
6.2.3. Độ phức tạp tính toán của thuật toán DFS và BFS ........................ 24
6.3. Bài toán tìm đường đi ngắn nhất trên đồ thị có trọng số...................... 24
6.3.1. Phát biểu bài toán ......................................................................... 24
6.3.2. Giới thiệu thuật toán Ford - Bellman ............................................ 25
6.2.3. Giới thiệu thuật toán thuật toán Dijkstra ....................................... 26
6.3.4. Độ phức tạp .................................................................................. 28
6.4. Các thuật toán tìm kiếm trên cây khung .............................................. 28
6.4.1. Bài toán cây khung ....................................................................... 28
6.4.2. Giới thiệu thuật toán Prim ............................................................ 29
6.4.3. Giới thiệu thuật toán Kruskal........................................................ 30
Trang 7
6.4.5. Độ phức tạp ................................................................................. 31
6.5. Bài toán tìm chu trình Hamilton qua tất cả các đỉnh của đồ thị ........... 32
6.5.1. Phát biểu bài toán ......................................................................... 32
6.5.2. Giới thiệu thuật toán tìm chu trình Hamilton: ............................... 33
Chương 2 MÔ PHỎNG THUẬT TOÁN.......................................................... 34
1. Khái niệm và chức năng của mô phỏng..................................................... 34
2. Lịch sử của mô phỏng thuật toán............................................................... 35
3. Hiệu quả của mô phỏng thuật toán trong giảng dạy................................... 37
4. Một số yêu cầu đối với mô phỏng thuật toán............................................. 41
4.1. Mô phỏng đúng theo thuật toán .......................................................... 41
4.2. Cho phép thực hiện theo từng bước .................................................... 41
4.3. Mô phỏng thuật toán phải có tính động............................................... 41
4.4. Có thể thực thi với mọi bộ dữ liệu đầu vào ......................................... 43
4.5. Có sự phân cấp người học................................................................... 43
5. Quy trình mô phỏng thuật toán.................................................................. 43
5.1. Nghiên cứu và phân tích giải thuật...................................................... 43
5.2. Mô phỏng dữ liệu vào và kết quả đầu ra ............................................. 44
5.3. Chia thuật toán thành nhiều bước nhỏ rồi mô phỏng theo từng bước .. 45
5.4. Tổng hợp mô phỏng theo các bước ..................................................... 47
5.5. Sơ đồ cấu trúc chung của hệ thống mô phỏng ..................................... 47
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 48
6.1. Một số hệ thống mô phỏng thuật toán chung ...................................... 49
6.2. Sử dụng công cụ mô phỏng thuật toán riêng biệt ................................ 52
6.3. Xây dựng hệ thống từ đầu................................................................... 53
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Ị....................................................................... 54
1. Mục đích................................................................................................... 54
2. Những yêu cầu thực tế .............................................................................. 54
3. Đề xuất cho hệ thống mới ......................................................................... 55
Trang 8
4. Thiết kế hệ thống mô phỏng một số thuật toán trên đồ thị......................... 56
4.1. Lựa chọn công cụ lập trình ................................................................. 57
4.2. Chức năng mô phỏng của các thuật toán được cài đặt ......................... 59
4.2.1 Mô phỏng thuật toán tìm kiếm....................................................... 59
4.2.2. Mô phỏng thuật toán Dijkstra ....................................................... 61
4.2.3. Mô phỏng thuật toán Ford – Bellman ........................................... 63
4.2.4. Mô phỏng thuật toán Prim ............................................................ 63
4.2.5. Mô phỏng thuật toán Kruskal ....................................................... 65
4.2.6. Thuật toán tìm chu trình Hamilton................................................ 66
5. Giới thiệu chương trình............................................................................. 66
5.1. Tổng quan về hệ thống........................................................................ 66
5.1.1. Các đối tượng xây dựng cấu trúc đồ thị ........................................ 67
5.1.2. Công cụ vẽ hình ảnh để mô phỏng................................................ 70
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 70
5.2. Giới thiệu các công cụ hỗ trợ mô phỏng do người dùng cài đặt .......... 71
Chương 4 KẾT LUẬN ..................................................................................... 80
1. Những kết quả đạt được ............................................................................ 80
2. Hướng phát triển ....................................................................................... 81
DANH MỤC TÀI LIỆU THAM KHẢO .......................................................... 82
Trang 9
PHỤ LỤC ........................................................................................................ 84
LỜI NÓI ĐẦU
Cách đây gần ba thập kỉ (khoảng những năm 80 của thế kỉ XX), ở nhiều
nước trên thế giới mô phỏng thuật toán đã được sử dụng trong việc giảng dạy
các môn Khoa học máy tính như một công cụ hữu hiệu để mô tả thuật toán một
cách trực quan, khoa học. Không những vậy nó còn cho người học biết chi tiết
từng bước hoạt động của thuật toán cùng với cấu trúc dữ liệu đi kèm thông qua
việc mô tả bằng đồ họa.
Những năm gần đây, ở Việt Nam môn Tin học đã được đưa vào chương
trình của học sinh trung học phổ thông như là một môn học chính thức. Tuy
nhiên trên thực tế, một số trường chuyên trên cả nước đã tuyển sinh học sinh
chuyên Tin từ cuối những năm 80 của thế kỉ XX. Những học sinh này cần nắm
chắc kiến thức cơ bản về Tin học như: các cấu trúc dữ liệu trừu tượng: stack,
queue, cây, cây nhị phân, cây nhị phân tìm kiếm, các chiến lược thiết kế thuật
toán: tham lam, quay lui, quy hoạch động… Trong đó, lý thuyết về đồ thị và
thuật toán trên đồ thị là một lĩnh vực rộng và phức tạp. Việc hiểu và cài đặt tốt
các thuật toán đó đòi hỏi thời gian và công sức rất lớn. Hiện nay, việc truyền đạt
các thuật toán trên đồ thị cho học sinh chuyên Tin gặp rất nhiều khó khăn. Có
nhiều rất nhiều lý do: Các thuật toán đó khó hình dung, việc tổ chức dữ liệu cho
nó cũng phức tạp, thời gian giảng dạy trên lớp có hạn, tài liệu tham khảo có thể
tự đọc, tự học vẫn còn ít….
Trong khuôn khổ đề tài này, chúng tôi xây dựng một chương trình nhằm
mô phỏng hoạt động của ba thuật toán giải ba bài toán cơ bản trên đồ thị theo
phân phối chương trình của Bộ Giáo dục với hai mục đích: để học sinh 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,
để giáo viên có thể 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.
Trang 10
Nội dung luận văn được chia thành 3 chương:
Chương I. Những kiến thức cơ bản về thuật toán.
Ở chương này, chúng tôi trích nêu khái niệm về bài toán và thuật toán.
Các tính chất của thuật toán, xác định độ phức tạp của thuật toán…Cuối cùng,
chúng tôi giới thiệu ba thuật toán quan trọng trên đồ thị mà học sinh THPT sẽ
được học.
Chương II. Mô phỏng thuật toán.
Chương này chúng tôi trình bày khái niệm mô phỏng, các chức năng của
mô phỏng và các vấn đề liên quan như: lịch sử mô phỏng, nghiên cứu về hiệu
quả của nó trong giảng dạy và một số yêu cầu đối với việc mô phỏng thuật toán
nói chung.
Chương III. Phân tích thiết kế hệ thống mô phỏng một số thuật toán trên
đồ thị.
Ở chương 3, chúng tôi trình bày về quá trình phân tích, thiết kế và xây
dựng hệ thống mô phỏng trên ba thuật toán: thuật toán tìm kiếm (tìm kiếm theo
chiều sâu và tìm kiếm theo chiều rộng), thuật toán tìm đường đi ngắn nhất (thuật
toán Dijsktra) và thuật toán tìm cây khung cực tiểu trên đồ thị vô hướng có trọng
Trang 11
số (thuật toán Prim)…
Chương 1 MỘT SỐ KIẾN THỨC CƠ BẢN VỀ THUẬT TOÁN
1. Khái niệm bài toán Tin học
Trong phạm vi tin học, người ta quan niệm bài toán là một công việc nào
đó mà con người muốn máy tính thực hiện. [xem 1]
Khi dùng máy tính để giải bài toán, ta cần quan tâm tới 2 vấn đề: Dữ liệu
cần được đưa vào máy tính (Input) là gì và cần lấy ra (Output) thông tin gì? Nói
một cách khác, cho một bài toán là việc mô tả rõ Input và Output của bài toán.
Vấn đề còn lại là: Làm thế nào để từ Input ta có được Output?
2. Khái niệm thuật toán
Khác với Toán học (các yêu cầu của bài toán thường là chứng minh sự tồn
tại đáp án chứ không yêu cầu tìm một cách chi tiết để tìm ra đáp án đó), giải một
bài toán Tin học là việc đi tìm một lời giải cụ thể, tường minh để đưa ra Output
của bài toán dựa trên Input đã cho. Việc chỉ ra một cách tìm Output của bài toán
được gọi là một thuật toán. Có nhiều cách phát biểu khái niệm về thuật toán.
Dưới đây là cách phát biểu được chọn để đưa vào sách giáo khoa Tin học phổ
thông:
Khái niệm về 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ự nhất định để sau khi thực hiện dãy các thao
tác đó, từ input ta có output cần tìm [xem 1].
Trong lĩnh vực máy tính, cụm từ “thuật toán” đôi khi người ta dùng bằng
một từ khác: “giải thuật”.
Ví dụ về một thuật toán: Nhập vào một số nguyên dương N, kiểm tra số
đó có là số nguyên tố hay không?
Lời giải:
Input: Số nguyên dương N.
Trang 12
Output: Có/không tương ứng với N có là nguyên tố hay không?
Ý tưởng: Một số nguyên gọi là nguyên tố khi nó chỉ có ước là 1 và chính
nó. Từ định nghĩa suy ra:
- Nếu N = 1 thì thông báo là N không nguyên tố rồi kết thúc;
]
- Nếu 1< N < 4 thì thông báo N là số nguyên tố rồi kết thúc;
[ N thì N là nguyên
- Nếu N 4 và không có ước trong khoảng từ 2 đến
tố.
Thuật toán: Có nhiều cách mô phỏng khác nhau. Dưới đây là cách
mô phỏng thuật toán dạng liệt kê các bước:
Bước 1. Nhập số nguyên dương N;
Bước 2. Nếu N = 1 thì thông báo là N không nguyên tố rồi kết thúc;
Bước 3. Nếu N < 4 thì thông báo N là số nguyên tố rồi kết thúc;
i
[ N
(*)]
Bước 4. i 2;
Bước 5. Nếu thì thông báo N là nguyên tố rồi kết thúc;
Bước 6. Nếu N chia hết cho i thì thông báo N không nguyên tố rồi kết
thúc;
Bước 7. i i + 1 rồi quay lại bước 5;
3. Các tính chất của thuật toán
Dựa trên khái niệm về thuật toán và ví dụ ở trên ta thấy các thao tác trong
thuật toán phải được mô tả đủ chi tiết để một đối tượng cứ tiến hành thực hiện
theo đúng thứ tự các thao tác đó là có thể cho ra output dựa trên input tương
ứng. Một thuật toán phải đảm bảo được các tính chất sau:
Tính xác định: Sau khi thực hiện một thao tác thì hoặc là thuật toán kết
Trang 13
thúc hoặc là có đúng một thao tác xác định để thực hiện tiếp theo.
Tính đúng đắn: Sau khi thực hiện thuật toán ta phải nhận được đúng
Output cần tìm.
Tính dừng: Thuật toán phải kết thúc sau một số hữu hạn lần thực hiện.
Tính tổng quát: Thuật toán là đúng đắn với mọi bộ dữ liệu đầu vào của
bài toán.
Tính hiệu quả:
- Hiệu quả về thời gian: Ta quan tâm tới thời gian cần thiết để thực
hiện xong thuật toán đó. Thời gian đó phải nằm trong giới hạn cho phép.
- Hiệu quả về không gian: Dung lượng bộ nhớ cần thiết để lưu trữ
các đối tượng như bộ Input, bộ Output, kết quả trung gian và chương trình
được dùng để thực hiện thuật toán.
- Dễ cài đặt: thuật toán đó liệu có chuyển được thành chương trình
bằng một ngôn ngữ lập trình nào đó hay không.
Trước khi xây dựng thuật toán cho một bài toán nào đó, trước tiên phải
xác định được Input và Output là gì, thử trên một số ví dụ cụ thể để định hướng
cho việc xây dựng thuật toán. [xem 1]
4. Độ phức tạp và xác định độ phức tạp của thuật toán
Một thuật toán chỉ có thể giải một bài toán, nhưng một bài toán có thể giải
bằng nhiều thuật toán khác nhau. Làm thế nào để lựa chọn một thuật toán tốt để
giải một bài toán đã cho? Tất nhiên, người lập trình thường chọn thuật toán dễ
hiểu, dễ cài đặt. Theo đó, chương trình viết ra ít có khả năng có lỗi, việc nâng
cấp chương trình dễ dàng và nhiều người có thể thực hiện được. Nhưng nếu hiệu
quả của thuật toán (về mặt thời gian và không gian nhớ) là yêu cầu quan trọng
thì cần chọn một thuật toán chạy nhanh và sử dụng tài nguyên có sẵn một cách
hiệu quả. Như vậy dựa vào đâu để có thể kết luận thuật toán này “nhanh” hơn
Trang 14
thuật toán kia?
Có một cách để biết được thuật toán nào nhanh hơn bằng cách viết các
chương trình bằng cùng một ngôn ngữ lập trình cho các thuật toán rồi so sánh
trên các bộ Input giống nhau trên cùng một hệ thống để kết luận thuật toán nào
nhanh, thuật toán nào chậm. Tuy nhiên cách này không chính xác và tốn nhiều
thời gian.
Một cách khác để đánh giá thuật toán là dựa vào tiêu chí mỗi câu lệnh của
chương trình nguồn sẽ thực hiện bao nhiêu lần trên một tập dữ liệu vào. Việc
đánh giá đó không chỉ đánh giá, so sánh trong việc lựa chọn thuật toán mà còn
có thể hiệu chỉnh, cải tiến thuật toán đã có tốt hơn. Khi đánh giá thời gian thực
hiện thuật toán ta chú ý đặc biệt đến các phép toán mà số lần thực hiện không ít
hơn các phép toán khác – ta gọi là phép toán tích cực của thuật toán.
Cách đánh giá thời gian thực hiện thuật toán độc lập với hệ thống máy
tính dẫn đến khái niệm về Độ phức tạp của thuật toán. Thời gian thực hiện một
thuật toán bằng chương trình máy tính phụ thuộc vào rất nhiều yếu tố. Một yếu
tố cần chú ý nhất đó là kích thước của dữ liệu đầu vào. Dữ liệu càng lớn thì thời
gian xử lý càng chậm. Nếu gọi n là kích thước dữ liệu đưa vào thì thời gian thực
hiện của một thuật toán có thể biểu diễn một cách tương đối như một hàm của n:
T(n). Thực tế, T(n) không những chỉ phụ thuộc vào kích thước n mà còn phụ
thuộc vào đặc tính, tình trạng thực tế của bộ dữ liệu đầu vào.
Ví dụ, với thuật toán sắp xếp dãy số đã cho thành dãy tăng dần thì thời
gian sắp xếp còn phụ thuộc vào dãy đầu vào đã là dãy tăng dần, dãy được sinh
ngẫu nhiên hay được sắp xếp theo thứ tự ngược lại. Vì thế cần phải xem xét các
trường hợp tốt nhất, trung bình và xấu nhất. [Xem 2]
Việc xác định độ phức tạp của một thuật toán bất kỳ có thể rất phức tạp.
Tuy nhiên, trong thực tế, đối với một số thuật toán ta có thể phân tích bằng một
số quy tắc đơn giản:
Trang 15
4.1. Quy tắc max
Nếu thuật toán T có thời gian thực hiện T(n) =O(f(n)+g(n)) thì có thể coi
T có độ phức tạp là O(max(f(n), g(n)))
4.2. Quy tắc tổng
Nếu thuật toán T gồm hai đoạn thuật toán liên tiếp T1 và T2 và nếu T1 có
thời gian thực hiện T1(n) = O(f(n)), T2 có thời gian thực hiện là T2(n) = O(g(n))
thì thời gian thực hiện T sẽ là:
T(n) = T1(n) + T2(n) = O(f(n)+ g(n))
4.3. Quy tắc nhân
Nếu đoạn chương trình T có thời gian thực hiện là T(n) = O(f(n)). Khi đó,
nếu thực hiện k(n) lần đoạn chương trình T với k(n) = O(g(n)) thì độ phức tạp sẽ
là O(g(n).f(n))
4.4. Một số tính chất
Theo định nghĩa về độ phức tạp tính toán ta có một số tính chất:
a) Nếu một thuật toán có độ phức tạp là hằng số, tức là thời gian thực hiện
không phụ thuộc vào kích thước dữ liệu vào thì ta ký hiệu độ phức tạp tính toán
của thuật toán đó là O(1).
b) Với một thuật toán có độ phức tạp cấp logarit của f(n), người ta ký hiệu
là O(logf(n)) mà không cần ghi cơ số của logarit.
c) Với P(n) là một đa thức bậc k thì O(P(n)) = O(nk). Vì thế, một thuật
toán có độ phức tạp cấp đa thức, người ta thường ký hiệu là O(nk)
d) Một thuật toán có cấp là các hàm như 2n, n!, nn được gọi là một thuật
toán có độ phức tạp hàm mũ. Những thuật toán như vậy trên thực tế thường có
tốc độ rất chậm. Các thuật toán có cấp là các hàm đa thức hoặc nhỏ hơn hàm đa
thức thì thường nhanh hơn các thuật toán hàm mũ. Tuy nhiên, khi chọn một
thuật toán để giải một bài toán thực tế phải có một sự mềm dẻo nhất định dựa
Trang 16
vào những điều kiện thực tế cho phép.
Dưới đây là một số hàm số hay dùng để ký hiệu độ phức tạp tính toán và
bảng giá trị của chúng để tiện theo dõi sự tăng của hàm theo đối số n.
Hàm logN NlogN N2 N3 2n
N
0 0 1 1 2 1
1 2 4 8 4 2
2 8 16 64 16 4
3 24 64 512 256 8
4 64 256 409 65536 16
5 160 1024 32768 4292967296 32
Ví dụ: Tính giá trị của đa thức P(x)=anxn+an-1xn-1+ ... +a1x+a0 với a0, a1, ..., an,
x nhập từ bàn phím.
Thuật toán 1:
1.Input n, a0, a1,a2,…an, x;
2. S:=a0;
3.for i := 1 to n do begin
3.1 p:=1;
3.2 for j := 1 to i do p:= p*x;
3.3 S:= S+ai*p;
End;
4. Output s;
)1
Với mỗi giá trị i của vòng lặp 3, vòng lặp 3.2 thực hiện i vòng lặp nên khi
( nn 2
n = i nó thực hiện đủ n vòng lặp. Vậy vòng lặp 3 thực hiện lần câu lệnh
sau do nên thời gian tính toán tỉ lệ thuận với n2.
Vậy độ phức tạp tính toán của thuật toán trên là O(n2).
=x * xn-1
nên có thể tận dụng kết quả của lần tính trước cho
Thuật toán 2: Vì xn
Trang 17
lần tính sau:
1. Input n, a0, a1,a2,…an, x;
2. S := a0;P:=1;
3. for i := 1 to n do begin
3.1 P:=p*x;
3.1 S:= S+p;
End;
4. Output S;
Hai lệnh 2 và 4 đều có độ phức tạp tính toán là O(1). Vòng lặp 3 cần thực
hiện n lần hai thao tác tính S và p.Vậy số lần thực hiện lệnh 3 là 2n. Do vậy, độ
phức tạp tính toán của thuật toán trên là O(n).
5. Chi phí thực hiện thuật toán
Khái niệm độ phức tạp tính toán đặt ra là để đánh giá chi phí thực hiện
một thuật toán về mặt thời gian. Nhưng chi phí thực hiện thuật toán còn có rất
nhiều yếu tố khác nữa: không gian bộ nhớ phải sử dụng là một ví dụ. Tuy nhiên,
trên phương diện phân tích lý thuyết, ta chỉ có thể xét tới vấn đề thời gian bởi
việc xác định các chi phí khác nhiều khi rất mơ hồ và phức tạp. Đối với người
lập trình thì khác, một thuật toán với độ phức tạp dù rất thấp cũng sẽ là vô dụng
nếu như không thể cài đặt được trên máy tính, chính vì vậy khi bắt tay cài đặt
một thuật toán, ta phải biết cách tổ chức dữ liệu một cách khoa học, tránh lãng
phí bộ nhớ không cần thiết. Có một quy luật tương đối khi tổ chức dữ liệu: Tiết
kiệm được bộ nhớ thì thời gian thực hiện thường sẽ chậm hơn và ngược lại. Biết
cân đối, dung hoà hai yếu tố đó là một kỹ năng cần thiết của người lập trình.
[Xem 2]
6. Ba bài toán trên mô hình đồ thị được đưa vào giảng dạy trong trường Trung học Phổ thông Chuyên
6.1. Một số khái niệm cơ bản về đồ thị
6.1.1. Khái niệm đồ thị (Graph)
Là một cấu trúc rời rạc gồm các đỉnh và các cạnh nối các đỉnh đó. Được
Trang 18
mô tả hình thức: G = (V, E). Trong đó:
V gọi là tập các đỉnh (Vertices) và E gọi là tập các cạnh (Edges). Có thể
coi E là tập các cặp (u, v) với u và v là hai đỉnh của V.
Một số hình ảnh của đồ thị:
Đồ thị vô hướng Đồ thị có hướng
6.1.2. Các khái niệm cơ bản
Có thể phân loại đồ thị theo đặc tính và số lượng của tập các cạnh E: Cho
đồ thị G = (V, E). Ta có một số khái niệm sau [xem 3- tập 1]:
Đơn đồ thị: G được gọi là đơn đồ thị nếu giữa hai đỉnh u, v của V có nhiều nhất
là 1 cạnh trong E nối từ u tới v.
Đa đồ thị: G được gọi là đa đồ thị nếu giữa hai đỉnh u, v của V có thể có nhiều
hơn 1 cạnh trong E nối từ u tới v.
Đồ thị vô hướng: G được gọi là đồ thị vô hướng nếu các cạnh trong E là không
định hướng, tức là cạnh nối hai đỉnh u, v bất kỳ cũng là cạnh nối hai đỉnh v, u.
Hay nói cách khác, tập E gồm các cặp (u, v) không tính thứ tự (u, v) (v, u)
Đồ thị có hướng: G được gọi là đồ thị có hướng nếu các cạnh trong E là có định
hướng, có thể có cạnh nối từ đỉnh u tới đỉnh v nhưng chưa chắc đã có cạnh nối
từ đỉnh v tới đỉnh u. Hay nói cách khác, tập E gồm các cặp (u, v) có tính thứ tự:
Trang 19
(u, v) (v, u). Trong đồ thị có hướng, các cạnh được gọi là các cung. Đồ thị vô
hướng cũng có thể coi là đồ thị có hướng nếu như ta coi cạnh nối hai đỉnh u, v
bất kỳ tương đương với hai cung (u, v) và (v, u).
3
1
2
5
4
Ví dụ:
Vô hướng Có hướng Vô hướng Có hướng
Đơn đồ thị Đa đồ thị
Cạnh liên thuộc, đỉnh kề, bậc
Đối với đồ thị vô hướng G = (V, E). Xét một cạnh e E, nếu e = (u, v) thì
ta nói hai đỉnh u và v là kề nhau (adjacent) và cạnh e này liên thuộc (incident)
với đỉnh u và đỉnh v.
Với một đỉnh v trong đồ thị, ta định nghĩa bậc (degree) của v, ký hiệu
deg(v) là số cạnh liên thuộc với v. Dễ thấy rằng trên đơn đồ thị thì số cạnh liên
thuộc với v cũng là số đỉnh kề với v.
Đối với đồ thị có hướng G = (V, E). Xét một cung e E, nếu e = (u, v) thì
ta nói u nối tới v và v nối từ u, cung e là đi ra khỏi đỉnh u và đi vào đỉnh v.
Đỉnh u khi đó được gọi là đỉnh đầu, đỉnh v được gọi là đỉnh cuối của cung e.
Với mỗi đỉnh v trong đồ thị có hướng, ta định nghĩa: Bán bậc ra của v ký hiệu deg+(v) là số cung đi ra khỏi nó; bán bậc vào ký hiệu deg-(v) là số cung đi
Trang 20
vào đỉnh đó
Đường đi: Một đường đi độ dài k từ đỉnh u đến đỉnh v là dãy (u = x0, x1,
..., xk = v) thoả mãn (xi, xi+1) E (là 1 cạnh của đồ thị) với i: (0 i k). Đỉnh
u gọi là đỉnh xuất phát, v gọi là đỉnh kết thúc của đường đi. Đường đi không có
cạnh nào đi qua hơn 1 lần gọi là đường đi đơn.
Chu trình: Đường đi có đỉnh xuất phát trùng với đỉnh kết thúc gọi là chu
trình. tương tự ta có khái niệm chu trình đơn.
6.2. Bài toán tìm kiếm trên đồ thị
6.2.1. Phát biểu bài toán
Cho đồ thị G = (V, E) và s và t là hai đỉnh của đồ thị.
Yêu cầu: Hãy chỉ ra một đường đi từ s đến t (nếu có).
Ví dụ: Xét một đồ thị vô hướng và một đồ thị có hướng dưới đây:
Trên cả hai đồ thị, (1, 2, 3, 4) là đường đi đơn độ dài 3 từ đỉnh 1 tới đỉnh
4. Bởi (1, 2) (2, 3) và (3, 4) đều là các cạnh (hay cung.
Làm sao để duyệt tất cả các đỉnh có thể đến được từ một đỉnh xuất phát
nào đó? Vấn đề này đưa về một bài toán liệt kê mà yêu cầu của nó là không
được bỏ sót hay lặp lại bất kỳ đỉnh nào. Vì vậy, cần phải xây dựng những thuật
toán cho phép duyệt một cách hệ thống các đỉnh, những thuật toán như vậy gọi
Trang 21
là những thuật toán tìm kiếm trên đồ thị. Trong lý thuyết đồ thị, người ta quan
tâm đến hai thuật toán cơ bản nhất: thuật toán tìm kiếm theo chiều sâu và thuật
toán tìm kiếm theo chiều rộng.
6.2.2. Giới thiệu thuật toán tìm kiếm DFS và BFS
a. Thuật toán tìm kiếm theo chiều sâu DFS (Depth – First – Search)
Tư tưởng của thuật toán có thể trình bày như sau: Bắt đầu từ s, mọi đỉnh u
kề với s tất nhiên sẽ đến được từ s. Với mỗi đỉnh u đó, những đỉnh v kề với u
cũng đến được từ s... Ý tưởng đó gợi ý cho ta viết một thủ tục đệ quy DFS(u)
mô tả việc duyệt từ đỉnh u bằng cách thông báo thăm đỉnh u và tiếp tục quá trình
duyệt DFS(v) với v là một đỉnh chưa thăm kề với u. Để quá trình duyệt không
lặp lại bất kì đỉnh nào, ta dùng kỹ thuật đánh dấu, khi thăm một đỉnh, ta sẽ đánh
dấu đỉnh đó lại để các bước duyệt đệ quy kế tiếp không thăm lại đỉnh đó nữa.
Vấn đề còn lại: Để in ra được đường đi từ đỉnh xuất phát s, trong quá trình
duyệt DFS(u), trước khi gọi đệ quy DFS(v) với v là một đỉnh kề với u mà chưa
đánh dấu, ta lưu lại “vết” đường đi từ u tới v bằng cách đặt trace[v] := u, tức là
trace[v] là đỉnh liền trước v trong đường đi từ s tới v. Khi quá trình tìm kiếm
theo chiều sâu kết thúc, đường đi từ S tới F sẽ là:
t Trace[t] …. Trace[u1] ... Trace[s] s.
Truy ngược đường đi này sẽ cho ta hành trình đi từ s đến t. Có thể mô tả
thủ tục DFS dạng giả mã như sau:
Procedure DFS(uV);
Begin
< 1. Thông báo tới được u >;
< 2. Đánh dấu u là đã thăm>;
< 3. Xét mọi đỉnh v kề với u mà chưa thăm, với mỗi đỉnh v đó >;
Begin
Trace[v] := u;
{Truy vết đường đi}
DFS(v);
{Gọi đệ quy duyệt bắt đầu với v}
Trang 22
End;
End;
Begin
DFS(s);
- Nếu t chưa bị đánh dấu thì kết luận: Không có đường từ s->t>; - Nếu t đã bị đánh dấu thì dựa vào Trace tìm đường đi từ s->t>; >; b. Thuật toán tìm kiếm theo chiều rộng BFS (Breadth – First – Search) Ý tưởng của phương pháp cài đặt này là "lập lịch" duyệt các đỉnh. Khi thăm một đỉnh ta sẽ lên lịch thăm tất cả các đỉnh kề nó sao cho thứ tự duyệt là ưu tiên chiều rộng (đỉnh nào gần s hơn sẽ được duyệt trước). Ví dụ: Bắt đầu, ta thăm đỉnh s. Quá trình thăm S sẽ lên lịch duyệt những đỉnh (u1, u2, ..., up) kề với s (những đỉnh gần s nhất). Tiếp theo sẽ thăm đỉnh u1, khi thăm u1 sẽ lại lên lịch duyệt những đỉnh (v1, v2 ..., vq) kề với u1. Nhưng rõ ràng các đỉnh này "xa" s hơn những đỉnh u nên chúng chỉ được duyệt đến khi tất cả những đỉnh u đã duyệt xong. Tức là thứ tự duyệt đỉnh sau khi đã thăm u1 sẽ là: (u2, u3..., up, v1, v2, ..., vq). Do việc lập lịch như mô tả ở trên nên cần phải xếp hàng cho các đỉnh đã lên lịch theo đúng thứ tự. Khi thêm đỉnh nào đó ta sẽ thêm vào cuối hàng (vì đỉnh lên lịch sau chắc chắn xa hơn các đỉnh đã lên lịch (vào hàng) rồi. Chính vì nguyên tắc đó nên danh sách chứa những đỉnh đang chờ sẽ được tổ chức dưới dạng hàng đợi (Queue). Bước 1: Khởi tạo: free[s] = true; free[v] = false v V\{s} First:=1; Last:=1; Queue[Last]:=s;//Queue chỉ chứa s Trang 23 Ta sẽ dựng giải thuật như sau: Bước 2: Lặp cho tới khi Queue rỗng: u := pop;//lấy u khỏi hàng đợi free[u]:= false; Xét v V: nếu v chưa được thăm: Free[v] = false;//đánh dấu đã thăm Trace[v] = u; Push(v);//đẩy v vào hàng đợi, chờ được thăm Bước 3: Truy vết tìm đường đi hoặc thông báo không thấy đường. 6.2.3. Độ phức tạp tính toán của thuật toán DFS và BFS Quá trình 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ị [xem 3 – tập 1] có ảnh hưởng lớn tới chi phí về thời gian thực hiện giải thuật: Trong trường hợp ta 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(n + m) = 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). Nếu ta biểu diễn đồ thị bằng danh sách cạnh, thao tác duyệt những đỉnh kề với đỉnh u sẽ dẫn tới việc phải duyệt qua toàn bộ danh sách cạnh, đây là cài đặt tồi nhất, nó có độ phức tạp tính toán là O(n.m). 6.3.1. Phát biểu bài toán Khái niệm đồ thị có trọng số: Đồ thị có trọng số là một bộ ba G = (V, E, Ew
: R e ew
)( w) trong đó, G = (V, E) là đồ thị, w là hàm được định nghĩa: Bài toán đó phát biểu dưới dạng tổng quát như sau: Cho đồ thị có trọng số Trang 24 G = (V, E,w) là đồ thị không có chu trình âm. Yêu cầu: Hãy tìm một đường đi ngắn nhất (tổng trọng số qua các đỉnh trên đường đi) từ đỉnh xuất phát s V đến đỉnh đích t V. Nếu như đồ thị có chu trình âm (chu trình với độ dài âm) thì khoảng cách giữa một số cặp đỉnh nào đó có thể không xác định, bởi vì bằng cách đi vòng theo chu trình này một số lần đủ lớn, ta có thể chỉ ra đường đi giữa hai đỉnh nào đó trong chu trình này nhỏ hơn bất kỳ một số cho trước nào. Trong trường hợp như vậy, có thể đặt vấn đề tìm đường đi cơ bản (đường đi không có đỉnh lặp lại) ngắn nhất. Vấn đề đó là một vấn đề hết sức phức tạp mà ta sẽ không bàn tới ở đây. Dưới đây, chúng tôi giới thiệu hai thuật toán giải bài toán này là thuật toán Ford – Bellman và thuật toán Dijkstra. 6.3.2. Giới thiệu thuật toán Ford - Bellman Thuật toán Ford-Bellman có thể phát biểu rất đơn giản: Với đỉnh xuất phát S. Gọi d(v) là khoảng cách từ S tới v. Ban đầu d(S) được khởi gán bằng 0 còn các d(v) với v S được khởi gán bằng +. Sau đó ta tối ưu hoá dần các d(v) như sau: Xét mọi cặp đỉnh u, v của đồ thị, nếu có một cặp đỉnh u, v mà d(v) > d(u) + c(u, v) thì ta đặt lại d(v) := d(u) + c(u, v). Tức là nếu độ dài đường đi từ S tới v lại lớn hơn tổng độ dài đường đi từ S tới u cộng với chi phí đi từ u tới v thì ta sẽ huỷ bỏ đường đi từ S tới v đang có và coi đường đi từ S tới v chính là đường đi từ S tới u sau đó đi tiếp từ u tới v. Chú ý rằng ta đặt c[u, v] = + nếu (u, v) không là cung. Thuật toán sẽ kết thúc khi không thể tối ưu thêm bất kỳ một nhãn d[v] nào nữa. Tính dừng của thuật toán: Tại bước lặp 0: Bước khởi tạo d(S) = 0; d(v) := + với v S: thì dãy d(v) Trang 25 chính là độ dài đường đi ngắn nhất từ S tới v đi qua không quá 0 cạnh Giả sử tại bước lặp thứ i, d(v) bằng độ dài đường đi ngắn nhất từ S tới v qua không quá i cạnh, thì do tính chất: đường đi từ S tới v qua không quá i + 1 cạnh sẽ phải thành lập bằng cách: lấy một đường đi từ S tới một đỉnh u nào đó qua không quá i cạnh, rồi đi tiếp tới v bằng cung (u, v). Nên độ dài đường đi ngắn nhất từ S tới v qua không quá i + 1 cạnh sẽ được tính bằng giá trị nhỏ nhất trong các giá trị: (Nguyên lý tối ưu Bellman) Độ dài đường đi ngắn nhất từ S tới v qua không quá i cạnh Độ dài đường đi ngắn nhất từ S tới u qua không quá i cạnh cộng với trọng số cạnh (u, v) (u) i, d(u)bước i+ c(u, v)) thì các d(v) sẽ bằng độ dài đường đi ngắn nhất từ S tới v qua Nên sau bước lặp tối ưu các d(v) bằng công thức d(v)bước i+1 = min(d(v)bước không quá i + 1 cạnh. Sau bước lặp tối ưu thứ n - 1, ta có d(v) = độ dài đường đi ngắn nhất từ S tới v qua không quá n - 1 cạnh. Vì đồ thị không có chu trình âm nên sẽ có một đường đi ngắn nhất từ S tới v là đường đi cơ bản (qua không quá n - 1 cạnh). Tức là d(v) sẽ là độ dài đường đi ngắn nhất từ S tới v. Vậy thì số bước lặp tối ưu hoá sẽ không quá n - 1 bước. Nếu mỗi bước for u := 1 to n do for v := 1 to n do d(v) := min(d(v), d(u) + c(u, v)); ta mô tả dưới dạng: Thì do sự tối ưu bắc cầu (dùng d(u) tối ưu d(v) rồi lại có thể dùng d(v) tối ưu d(w) nữa...) nên chỉ làm tốc độ tối ưu nhãn d(v) tăng nhanh lên chứ không thể giảm đi được. 6.2.3. Giới thiệu thuật toán thuật toán Dijkstra Trang 26 Thuật toán Dijkstra (E.Dijkstra - 1959) có thể mô tả như sau: Bước 1: Khởi tạo Với đỉnh v V, gọi nhãn d[v] là độ dài đường đi ngắn nhất từ s tới v. Ta sẽ tính các d[v]. Ban đầu d[v] được khởi gán bằng w[s, v]. Nhãn của mỗi đỉnh có hai trạng thái tự do hay cố định, nhãn tự do có nghĩa là có thể còn tối ưu hơn được nữa và nhãn cố định tức là d[v] đã bằng độ dài đường đi ngắn nhất từ s tới v nên không thể tối ưu thêm. Để làm điều này ta có thể sử dụng kỹ thuật đánh dấu: Free[v] = TRUE hay FALSE tuỳ theo d[v] tự do hay cố định. Ban đầu các nhãn đều tự do. Bước 2: Lặp Cố định nhãn: Chọn trong các đỉnh có nhãn tự do, lấy ra đỉnh u là đỉnh có d[u] nhỏ nhất, và cố định nhãn đỉnh u. Sửa nhãn: Dùng đỉnh u, xét tất cả những đỉnh v và sửa lại các d[v] theo công thức: d[v] := min(d[v], d[u] + c[u, v]) Bước lặp sẽ kết thúc khi mà đỉnh đích t được cố định nhãn (tìm được đường đi ngắn nhất từ s đến t); hoặc tại thao tác cố định nhãn, tất cả các đỉnh tự do đều có nhãn là + (không tồn tại đường đi). Có thể đặt câu hỏi, ở thao tác 1, tại sao đỉnh u như vậy được cố định nhãn, giả sử d[u] còn có thể tối ưu thêm được nữa thì tất phải có một đỉnh t mang nhãn tự do sao cho d[u] > d[t] + c[t, u]. Do trọng số c[t, u] không âm nên d[u] > d[t], trái với cách chọn d[u] là nhỏ nhất. Tất nhiên trong lần lặp đầu tiên thì S là đỉnh được cố định nhãn do d[s] = 0. Bước 3: Kết hợp với việc lưu vết đường đi trên từng bước sửa nhãn, thông báo đường đi ngắn nhất tìm được hoặc cho biết không tồn tại đường đi (d[t] = Bước 1: d[s] = 0 ; d[v] = + (v V\{s}); u = s; Trang 27 +). Có thể mô tả ngắn gọn thuật toán bằng giả mã như sau: Bước 2: Lặp nếu u t (với u S) 2.1. Nếu d[v] > d[u] + c[u,v] thì d[v] = min{d[v], d[u] + c[u, v]} trace[v]=u (với v S - tập các đỉnh đã tối ưu) 2.2 Chọn v có d[v] nhỏ nhất //v=0 không có đường 2.3 Nếu v 0 thì thêm v vào S; u = v Bước 3: In ra đường đi tối ưu từ s đến t hoặc thông báo vô nghiệm. 6.3.4. Độ phức tạp Nếu đồ thị có nhiều đỉnh, ít cạnh, ta có thể sử dụng danh sách kề kèm trọng số để biểu diễn đồ thị, tuy nhiên tốc độ của thuật toán Dijkstra vẫn khá chậm vì trong trường hợp xấu nhất, nó cần n lần cố định nhãn và mỗi lần tìm đỉnh để cố định nhãn sẽ mất một đoạn chương trình với độ phức tạp O(n). Vậy
độ phức tạp của thuật toán Dijkstra là O(n2). Để tăng tốc độ, người ta thường sử dụng cấu trúc dữ liệu Heap để lưu các đỉnh chưa cố định nhãn. Heap ở đây là một cây nhị phân hoàn chỉnh thoả mãn: Nếu u là đỉnh lưu ở nút cha và v là đỉnh lưu ở nút con thì d[u] d[v] (Đỉnh r lưu ở gốc Heap là đỉnh có d[r] nhỏ nhất). 6.4.1. Bài toán cây khung Khái niệm cây khung: Cho đồ thị G = (V, E) vô hướng, liên thông và T = (V,E’) là một đồ thị con của G (E’ E). Khi đó, T được gọi là cây khung (cây bao trùm) nếu T liên thông và không có chu trình đơn Cho G = (V, E, w) là đồ thị vô hướng liên thông có trọng số, với một cây khung T của G, ta gọi trọng số của cây T là tổng trọng số các cạnh trong T. Yêu cầu: Trong số các cây khung của G, chỉ ra cây khung có trọng số nhỏ Trang 28 nhất. Cây khung như vậy được gọi là cây khung nhỏ nhất của đồ thị, và bài toán đó gọi là bài toán xây dựng cây khung nhỏ nhất. Dưới đây ta sẽ xét một trong hai thuật toán thông dụng để giải bài toán cây khung nhỏ nhất của đơn đồ thị vô hướng có trọng số. 6.4.2. Giới thiệu thuật toán Prim Một trong hai thuật toán quan trọng để giải bài toán tìm cây khung nhỏ nhất là thuật toán Prim. Thuật toán đó có thể phát biểu hình thức như sau: Đơn đồ thị vô hướng G = (V, E,w). Xét cây T trong G và một đỉnh v, gọi khoảng cách từ v tới T là trọng số nhỏ nhất trong số các cạnh nối v với một đỉnh nào đó trong T: d[v] = min{w[u, v] uT} Ban đầu khởi tạo cây T chỉ gồm có mỗi đỉnh {1}. Sau đó cứ chọn trong số các đỉnh ngoài T ra một đỉnh gần T nhất, kết nạp đỉnh đó vào T đồng thời kết nạp luôn cả cạnh tạo ra khoảng cách gần nhất đó. Cứ làm như vậy cho tới khi: Hoặc đã kết nạp được tất cả n đỉnh thì ta có T là cây khung nhỏ nhất Hoặc chưa kết nạp được hết n đỉnh nhưng mọi đỉnh ngoài T đều có khoảng cách tới T là +. Khi đó đồ thị đã cho không liên thông, ta thông báo việc tìm cây khung thất bại. Về mặt kỹ thuật cài đặt, ta có thể làm như sau: Sử dụng mảng đánh dấu Free. Free[v] = TRUE nếu như đỉnh v chưa bị kết nạp vào T. Gọi d[v] là khoảng cách từ v tới T. Ban đầu khởi tạo d[1] = 0 còn d[2] = d[3] = ... = d[n] = +. Tại mỗi bước chọn đỉnh đưa vào T, ta sẽ chọn đỉnh u nào ngoài T và có d[u] nhỏ nhất. Khi kết nạp u vào T rồi thì rõ ràng các nhãn d[v] sẽ thay đổi: d[v]mới := min(d[v]cũ, v[u, v]). Vấn đề chỉ có vậy (chương trình rất Trang 29 giống thuật toán Dijkstra, chỉ khác ở công thức tối ưu nhãn). Bước 1: Khởi tạo: T = {s} d[s] = 0, u = s (s - đỉnh xuất phát) d[v]=+∞(v ∉ T) Bước 2: Lặp N-1 lần (N số đỉnh của đồ thị): 2.1 Cập nhật các đỉnh kề với u ở ngoài T Nếu d[v] > w[u,v] trace[v] = u, d[v] = w[u,v] 2.2 Chọn v (v ∉ T) mà d[v] nhỏ nhất Nếu d[v] = +∞ đến bước 3 2.3 Kết nạp v vào T, u = v Bước 3: In ra cây khung hoặc thông báo vô nghiệm. Có thể mô tả thuật toán Prim bằng đoạn giả mã sau: 6.4.3. Giới thiệu thuật toán Kruskal Thuật toán Kruskal dựa trên mô hình xây dựng cây khung bằng thuật toán hợp nhất [xxx], chỉ có điều thuật toán không phải xét các cạnh với thứ tự tuỳ ý mà xét các cạnh theo thứ tự đã sắp xếp: Với đồ thị vô hướng G = (V, E) có n đỉnh. Khởi tạo cây T ban đầu không có cạnh nào. Xét tất cả các cạnh của đồ thị từ cạnh có trọng số nhỏ đến cạnh có trọng số lớn, nếu việc thêm cạnh đó vào T không tạo thành chu trình đơn trong T thì kết nạp thêm cạnh đó vào T. Cứ làm như vậy cho tới khi: Hoặc đã kết nạp được n - 1 cạnh vào trong T thì ta được T là cây khung nhỏ nhất Hoặc chưa kết nạp đủ n - 1 cạnh nhưng hễ cứ kết nạp thêm một cạnh bất kỳ trong số các cạnh còn lại thì sẽ tạo thành chu trình đơn. Trong trường hợp này đồ thị G là không liên thông, việc tìm kiếm cây khung thất bại. Như vậy có hai vấn đề quan trọng khi cài đặt thuật toán Kruskal: Thứ nhất, làm thế nào để xét được các cạnh từ cạnh có trọng số nhỏ tới cạnh có trọng số lớn. Ta có thể thực hiện bằng cách sắp xếp danh sách cạnh theo Trang 30 thứ tự không giảm của trọng số, sau đó duyệt từ đầu tới cuối danh sách cạnh. Nên sử dụng các thuật toán sắp xếp hiệu quả để đạt được tốc độ nhanh trong trường hợp số cạnh lớn. Trong trường hợp tổng quát, thuật toán HeapSort là hiệu quả nhất bởi nó cho phép chọn lần lượt các cạnh từ cạnh trọng nhỏ nhất tới cạnh trọng số lớn nhất ra khỏi Heap và có thể xử lý (bỏ qua hay thêm vào cây) luôn. Thứ hai, làm thế nào kiểm tra xem việc thêm một cạnh có tạo thành chu trình đơn trong T hay không. Để ý rằng các cạnh trong T ở các bước sẽ tạo thành một rừng (đồ thị không có chu trình đơn). Muốn thêm một cạnh (u, v) vào T mà không tạo thành chu trình đơn thì (u, v) phải nối hai cây khác nhau của rừng T, bởi nếu u, v thuộc cùng một cây thì sẽ tạo thành chu trình đơn trong cây đó. Ban đầu, ta khởi tạo rừng T gồm n cây, mỗi cây chỉ gồm đúng một đỉnh, sau đó, mỗi khi xét đến cạnh nối hai cây khác nhau của rừng T thì ta kết nạp cạnh đó vào T, đồng thời hợp nhất hai cây đó lại thành một cây. 6.4.5. Độ phức tạp Xét về độ phức tạp tính toán, thuật toán Prim có độ phức tạp là O(n2). Tương tự thuật toán Dijkstra, nếu kết hợp thuật toán Prim với cấu trúc Heap sẽ được một thuật toán với độ phức tạp O((m+n)logn). Đối với thuật toán Kruskal, ta có thể chứng minh được rằng thao tác GetRoot có độ phức tạp là O(log2n), còn thao tác Union là O(1). Giả sử ta đã có danh sách cạnh đã sắp xếp rồi thì xét vòng lặp dựng cây khung, nó duyệt qua danh sách cạnh và với mỗi cạnh nó gọi 2 lần thao tác GetRoot, vậy thì độ phức tạp là O(mlog2n), nếu đồ thị có cây khung thì m n-1 nên ta thấy chi phí thời gian chủ yếu sẽ nằm ở thao tác sắp xếp danh sách cạnh bởi độ phức tạp của HeapSort là O(mlog2m). Vậy độ phức tạp tính toán của thuật toán là O(mlog2m) trong trường hợp xấu nhất. Tuy nhiên, phải lưu ý rằng để xây dựng cây khung thì ít khi thuật toán phải duyệt toàn bộ danh sách cạnh mà chỉ một Trang 31 phần của danh sách cạnh mà thôi. 6.5.1. Phát biểu bài toán Khái niệm chu trình Hamilton: Cho đồ thị G = (V, E) có n đỉnh Chu trình (x1, x2, ..., xn, x1) được gọi là chu trình Hamilton nếu xi xj với 1 i < j n Đường đi (x1, x2, ..., xn) được gọi là đường đi Hamilton nếu xi xj với 1 i < j n Có thể phát biểu một cách hình thức: Chu trình Hamilton là chu trình xuất phát từ 1 đỉnh, đi thăm tất cả những đỉnh còn lại mỗi đỉnh đúng 1 lần, cuối cùng quay trở lại đỉnh xuất phát. Đường đi Hamilton là đường đi qua tất cả các đỉnh của đồ thị, mỗi đỉnh đúng 1 lần. Bài toán tìm chu trình Hamilton: Cho đồ thị G = (V, E) có n đỉnh, m cạnh. Yêu cầu: Hãy chỉ ra một chu trình Hamilton của đồ thị đã cho. Để tìm chu trình Hamilton, ta quan tâm đến các định lý sau: Định lý 1: Đồ thị vô hướng G, trong đó tồn tại k đỉnh sao cho nếu xoá đi k đỉnh này cùng với những cạnh liên thuộc của chúng thì đồ thị nhận được sẽ có nhiều hơn k thành phần liên thông. Thì khẳng định là G không có chu trình Hamilton. Mệnh đề phản đảo của định lý này cho ta điều kiện cần để một đồ thị có chu trình Hamilton Định lý 2 (Định lý Dirac (1952)): Đồ thị vô hướng G có n đỉnh (n 3). Khi đó nếu mọi đỉnh v của G đều có deg(v) n/2 thì G có chu trình Hamilton. Đây là một điều kiện đủ để một đồ thị có chu trình Hamilton deg v
)( deg v
)( Định lý 3: Đồ thị có hướng G liên thông mạnh và có n đỉnh. Nếu n
2 n
2 Trang 32 và với mọi đỉnh v thì G có chu trình Hamilton 6.5.2. Giới thiệu thuật toán tìm chu trình Hamilton: Dưới đây ta sẽ cài đặt một chương trình liệt kê tất cả các chu trình Hamilton xuất phát từ đỉnh 1, các chu trình Hamilton khác có thể có được bằng cách hoán vị vòng quanh. Lưu ý rằng cho tới nay, người ta vẫn chưa tìm ra một phương pháp nào thực sự hiệu quả hơn phương pháp quay lui để tìm dù chỉ một chu trình Hamilton cũng như đường đi Hamilton trong trường hợp đồ thị tổng Bước 1. Khởi tạo: free[u] = true với u thuộc G Bước 2. Visit(i): Thăm đỉnh ở bước thứ i 2.1 u = đỉnh vừa thăm xong Xét các đỉnh v kề u và free[v] = true 2.2 Ghi nhận đỉnh ở bước thứ i 2.3 Nếu (i =n) và (u kề với 1) đến Bước 3 2.4 Đánh dấu thăm v và Vitsit(i+1); Bước 3. Truy vết tìm đường đi (nếu có) Trang 33 quát. 1. Khái niệm và chức năng của mô phỏng Mô phỏng thuật toán là quá trình mô tả cấu trúc dữ liệu, các thao tác của một chương trình bằng đồ hoạ [Stasko 1990]. Mô phỏng thuật toán được thiết kế nhằm giúp người dùng hiểu thuật toán, đánh giá thuật toán và gỡ lỗi khi cài đặt chương trình [xem 12] Một chương trình lập trình trên máy tính sẽ chứa các cấu trúc dữ liệu của thuật toán mà nó sẽ thực hiện. Trong khi thực hiện chương trình đó, giá trị thực của cấu trúc dữ liệu thay đổi dựa trên từng bước hoạt động của thuật toán. Mô phỏng thuật toán sử dụng đồ hoạ để biểu diễn sự thay đổi trạng thái của cấu trúc dữ liệu cho từng bước hoạt động của nó một cách trực quan, khoa học. Trong suốt quá trình biểu diễn, người dùng có thể quan sát việc thực thi thuật toán theo từng bước để có thể biết chi tiết về thuật toán cũng như hiểu một cách tường tận về thuật toán đó. Ví dụ: Một chương trình mô phỏng thuật toán phân tích LR phân tích trên 1 chuỗi kí tự. Chương trình chứa ba cấu trúc: bảng chuyển, một ngăn xếp (stack) và 1 xâu kí tự. Khi thực hiện, chương trình minh hoạ bằng việc đối sánh các trạng thái trong bảng chuyển và và thực hiện từng thao tác trên ngăn xếp để tách xâu kí tự. Các chỉ dẫn, kí hiệu trên xâu vào và các phần tử trong ngăn xếp ở mỗi trạng thái sẽ lần lượt thay đổi trong khi thực hiện thuật toán. Đây là một công việc khá khó khăn để nắm bắt nếu một học sinh chỉ sử dụng hình vẽ và các xâu kí tự. Mô phỏng thuật toán có thể chỉ ra tất cả các thông tin và sự thay đổi đồng Trang 34 thời ở từng bước bằng đồ hoạ. Ta có thể quan sát bằng hình vẽ dưới đây: Bên cạnh việc giúp người dùng hiểu rõ thuật toán, mô phỏng thuật toán cũng có thể dùng để gỡ lỗi chương trình một cách dễ dàng hơn. Để sử dụng mô phỏng thuật toán trong việc gỡ lỗi, người dùng ghi chú các trạng thái thực trên chương trình của họ để đưa ra các lệnh mô phỏng đầu ra và những bước làm cho thuật toán không cho ra kết quả như mong muốn. 2. Lịch sử của mô phỏng thuật toán Năm 1981 Ronald Baecker tại đại học Toronto đã thiết kế đoạn video “Sorting Out Sorting”. Đây là mốc đánh dấu sự phát triển của lĩnh vực mô phỏng. Từ đó, các giảng viên đã sử dụng hệ thống mô phỏng để giảng dạy các môn thuật toán. Từ những năm 1980 đến đầu những năm 90 của thế kỉ XX, có 2 hệ thống được phát triển đã gây ảnh hưởng đến tất cả những hệ thống về sau đó là BALSA-I (Brown ALgorithm Simulator and Animator) [Brown 1984] và TANGO (Transition-based Animation GeneratiOn) [Stasko 1990]. BALSA – I là hệ thống mô phỏng thuật toán nổi tiếng được biết đến đầu tiên, được viết bởi giáo sư Marc Brown và Robert Sedgewick (Đại học Brown – Trang 35 Mỹ). BALSA – I là chương trình mô phỏng thuật toán tương tác. Nó đưa ra nhiều khung nhìn về cấu trúc dữ liệu và có thể thực hiện nhiều thuật toán một cách đồng thời. Sự phát triển của nó là động lực thúc đẩy các nghiên cứu khác trong lĩnh vực này. Một hệ thống khác, TANGO, do John Stasko (Đại học Brown – Mỹ) viết vào đầu những năm 90. Điểm nổi bật của hệ thống này là giới thiệu mô hình chuyển cho thiết kế mô phỏng và framework cho hệ thống mô phỏng thuật toán. Nó giới thiệu một khái niệm mới về framework (sau này có rất nhiều hệ thống sử dụng nó như một cấu trúc cơ bản) Từ khi hai hệ thống này được công bố, các hệ thống con của nó cũng được phát triển. BALSA – II (1988). TANGO có rất nhiều phiên bản. Một trong số đó là XTANGO và POLKA. POLKA được thiết kế cho các thuật toán chạy song song. Nó là hệ thống mô phỏng thuật toán 2D hướng đối tượng và mở rộng trong 3D, POLKA 3D. POLKA 3D cung cấp cách nhìn 3D và các cơ sở như góc, hình cầu, hình khối…. Người dùng không yêu cầu phải biết kiến thức về đồ họa 3D để sử dụng POLKA 3D. SAMBA là hệ thống mô phỏng tương tác thông dịch, nó đọc các lệnh ASCII và thực hiện các thao tác mô phỏng tương ứng. Phiên bản của SAMBA cài bằng Java và có thể xem chi tiết tại trang web http://www.cc.gatech.due/gvu/softviz/parviz/samba.html. Một số hệ thống mô phỏng nổi tiếng khác là Zeus, Leonardo, CATAI, Mocha. Zeus (Brown 1991) được phát triển tại đại học Brown cùng với hệ thống BALSA và BALSA – II. Nó được coi là phần mềm tương tác trực quan hóa. Nó hỗ trợ việc đồng bộ các khung nhìn và cho phép người dung chỉnh sửa các khung nhìn này và thay đổi biểu diễn của dữ liệu. Zeus được thực thi trong môi trường đa xử lý và đa tuyến, nó cũng cho phép thực thi các thuật toán song song. Leonardo là hệ thống mô phỏng các chương trình C. Nó tích hợp phát triển với mô phỏng của các chương trình C vào cùng một môi trường. CATAI mô phỏng các chương trình C++. Nó dựa trên kĩ thuật đối tượng phân phối và cho phép Trang 36 nhiều người dùng chia sẻ cùng một mô phỏng thông qua “lớp” ảo. Việc giao tiếp và đồng bộ giữa các trạm và thuật toán được mô phỏng được đảm bảo bởi server có sử dụng kĩ thuật CORBA. Mocha là mô hình phân phối với kiến trúc client – server, nó phân đoạn một cách tối ưu các thành phần của hệ thống mô phỏng thông thường. Nó vượt qua các tồn tại của X - window và mô hình Java. Trong mô hình Mocha chỉ có mã giao diện được xuất tới máy của người dùng. Khi thuật toán chay trên server thì đoạn mã giao diện lại chạy trên máy người dùng. Hiện tại, một số lượng lớn các chương trình mô phỏng đã được viết ra. Hầu hết trong số chúng rất phổ biến và sử dụng phức tạp. Các phần mềm này được thiết kế nhằm mục đích giáo dục hoặc các nghiên cứu. Một vài chương trình có cấu trúc phức tạp và yêu cầu hỗ trợ kĩ thuật cao. Rõ ràng, điều này ít thực tế, chúng ta mong muốn một phần mềm nhỏ gọn và linh hoạt, có cấu trúc đơn giản. 3. Hiệu quả của mô phỏng thuật toán trong giảng dạy dạy học ngành khoa học máy tính. Đã có một số lượng các sinh viên được đào tạo bằng các chương trình mô phỏng để thấy được hiệu quả của nó trong giảng dạy nhưng kết quả rất khác nhau. Có thể đưa ra một vài ví dụ như sau: Giáo sư Brown (Đại học Brown) năm 1984 đã sử dụng phần mềm BALSA – I để dạy môn học lập trình và môn cấu trúc dữ liệu và giải thuật. Hệ thống này sử dụng để trực quan hóa chương trình dạy học. Ông viết trong bản báo cáo rằng việc sử dụng các đoạn mô phỏng kèm vào các bài giảng là một chứng minh cho việc “tốc độ hiểu bài của học sinh tăng lên” so với cách giảng dạy truyền thống. Stasko (Đại học Brown) năm 1997 sử dụng SAMBA – chương trình mô phỏng của hệ thống XTANGO để dạy môn thuật toán. Ông yêu cầu các sinh viên sử dụng hệ thống để thêm vào các mô phỏng của chính bài tập của mình. Trang 37 Kết quả chỉ ra rằng sinh viên rất có hứng thú với các chương trình mô phỏng và chính chương trình mô phỏng đã khuyến khích sự sáng tạo của học sinh. Rõ ràng, nhờ có chương trình mô phỏng mà các sinh viên hiểu các thuật toán nhanh hơn, nhớ được lâu hơn. Tuy nhiên, việc sử dụng chương trình mô phỏng trong dạy học không phải lúc nào cũng đem lại kết quả tốt. Stasko (1993) đã thử nghiệm dạy 2 nhóm sinh viên với cùng một nội dung bài học về HEAP – một dạng cấu trúc dữ liệu trừu tượng. Một nhóm học thuật toán dựa trên mô tả một cách khái niệm. Nhóm còn lại học bài dựa trên chương trình mô phỏng tương tác. Mặc dù kết quả cho thấy nhóm được học có mô phỏng điểm cao hơn nhóm còn lại nhưng sự chênh lệch không đủ để thấy được lợi ích của việc mô phỏng. Tương tự, Byrne (1996) cũng làm 2 thí nghiệm tương tự và kết quả thu được cũng không chỉ rõ được lợi ích của việc mô phỏng. Mặc dầu vậy, những kết quả đó không làm cho việc mô phỏng thuật toán mất đi những điểm mạnh của nó mà nó hướng người dùng đến một cách nhìn khác về thuật toán mô phỏng. Kết quả chỉ ra rằng để đạt được hiệu quả tối ưu khi dùng thuật toán mô phỏng là dùng nó như một cầu nối với các nhân tố khác. Lawrence đã sử dụng hệ thống XTANGO và POLKA để giảng dạy về thuật toán Kruskal. Tất cả sinh viên của nhóm học có mô phỏng có tác động rõ rệt. Thực nghiệm cũng cho thấy rằng để người học tiếp thu nhanh hơn thì nên để cho họ tự học và tự tạo cho mình tập dữ liệu hơn là các dữ liệu do giáo viên tự chuẩn bị từ trước. Hơn nữa, năm 1999 nghiên cứu của giáo sư Kehoe chỉ ra tính hiệu quả của việc sử dụng mô phỏng trong giảng dạy thuật toán bằng cách chia học viên thành các nhóm để dạy về thuật toán BINOMIAL HEAP – một dạng cấu trúc đặc biệt của HEAP. Một nhóm tự học thuật toán bằng cách dùng phần mềm mô phỏng, một nhóm học bằng cách đọc sách có các hình vẽ mô tả. Kết quả chỉ ra Trang 38 rằng nhóm học qua phần mềm có khả năng cài đặt thuật toán tốt hơn nhóm còn lại (nhưng không phải là tất cả các thành viên đều như vậy) và họ nói rằng nhờ có mô phỏng mà họ có thể hiểu thuật toán nhanh hơn. Báo cáo của Kehoe chứng minh rằng cách hiệu quả để sử dụng thuật toán mô phỏng trong việc dạy học có thể đạt được kết quả cao hơn đó là sử dụng nó như là một hệ thống “mở” và hướng tự học (như là giao bài tập về nhà chẳng hạn). Như vậy, việc mô phỏng thuật toán hiệu quả ở chỗ coi nó là một tài liệu học được sử dụng cùng với các tài liệu khác cùng với các hướng dẫn về cách thức hoạt động của chương trình tương ứng với các thao tác của thuật toán. Bài báo cũng chỉ ra rằng mô phỏng thuật toán là một cách thuận lợi cho việc học cách thức hoạt động của thuật toán. Nếu như mô phỏng không phải lúc nào cũng tạo điều kiện thuận lợi cho việc học tập tốt thì ít nhất nó có thể chỉ ra rằng một thuật toán cần học có thể dễ tiếp cận hơn. Giáo sư Stasko cũng chỉ ra rằng cần có một vài điều kiện để thuật toán mô phỏng có hiệu quả hơn trong giảng dạy. Một trong những điều kiện đó là kết hợp mô phỏng thuật toán với các trích dẫn giải thích cho dễ hiểu (chú thích), việc mô phỏng sẽ hiển thị cùng với các mô tả một cách hình thức về các thao tác đó. Một điều kiện nữa là hệ thống mô phỏng thuật toán nên có khả năng chạy lại (replay) cho phép người dùng quan sát các thao tác quan trọng. Một vài chương trình có thể chỉ ra trạng thái trước, trạng thái sau. Thêm vào đó, các phản hồi từ phía người học cũng rất cần thiết để cải tiến chương trình mô phỏng cho tốt hơn. Mặc dù kết quả thực nghiệm chỉ ra rằng không phải lúc nào mô phỏng cũng mang lại lợi ích tốt nhưng nó cũng không chỉ ra rằng mô phỏng không mang lại hiệu quả trong giảng dạy. Trên thực tế, có những nghiên cứu chỉ ra tính không hiệu quả của một chương trình mô phỏng nhưng điều đó không làm cho việc mô phỏng mất đi tính ưu việt mà là một cách để ta phải xem lại chương Trang 39 trình đó, cải tiến chương trình đó cho nó hiệu quả hơn với người học. Tóm lại, để một chương trình mô phỏng có hiệu quả và mang lại lợi ích cho người học thì việc thiết kế và phát huy tính động trong chương trình là một yếu tố rất quan trọng. Các tính chất sau đây cũng là cần thiết: Truy cập mở: Người học có thể tự do truy cập vào các hệ thống mô phỏng. Đó là, bên cạnh việc có truy cập vào các hệ thống ở trường học, họ có thể truy cập vào hệ thống từ nhà hoặc bất cứ nơi nào khác khi họ cần đến. Chủ động điều khiển mô phỏng: Người học sẽ có thể tạo ra bộ dữ liệu của riêng mình khi sử dụng hệ thống. Trong khi tự định nghĩa bộ dữ liệu vào cũng có thể giúp đỡ học sinh xây dựng sự hiểu biết ban đầu, hệ thống nên có cả hai lựa chọn: tự xây dựng dữ liệu hoặc dùng bộ dữ liệu vào mặc định của hệ thống. Khả năng tương tác giữa người học và hệ thống: Hệ thống mô phỏng phải có khả năng tương tác với người học, nghĩa là cho phép người học xem được kết quả, cho phép dừng thuật toán ở bất cứ thời điểm nào để quan sát, xem lại dữ liệu ban đầu và chạy tiếp, chạy từng bước, huỷ, quay lại, chạy nhanh, chạy chậm để thuật toán cho ra kết quả mong muốn. Tương ứng với câu lệnh giả mã mô tả thuật toán sẽ là bước mô phỏng trên đồ thị do người học tự mô tả. Đón nhận thông tin phản hồi: Hệ thống ghi nhận lại những góp ý từ người học để dần dần cải tiến hệ thống cho hiệu quả hơn. Các hệ thống mô phỏng thuật toán có nền tảng phụ thuộc nhau. Với sự tiến bộ của công nghệ mới, sự phổ dụng của WWW và sự phát triển của ngôn ngữ Java, các nhà lập trình chuyển sang lĩnh vực mô phỏng thuật toán trực tuyến trên mạng. Một vài lập trình viên kết hợp cả đa phương tiện vào chương trình của họ. Việc sử dụng hệ thống mô phỏng thuật toán đã giải quyết triệt để các Trang 40 yếu điểm của cách dạy học truyền thống và có thể đào tạo từ xa. 4. Một số yêu cầu đối với mô phỏng thuật toán Để mô phỏng một thuật toán nào đó, các bước thực hiện chỉ dẫn trên đồ họa phải phản ánh đúng theo nội dung của thuật toán đã đưa ra để đảm bảo rằng người học học đúng thuật toán mình yêu cầu. Thông thường, khi học một thuật toán phải dùng đến chương trình mô phỏng để minh họa trong lúc học tập hoặc nghiên cứu thì thuật toán đó thường không phải là thuật toán đơn giản. Vì vậy, việc để cho người dùng có thể hiểu được thuật toán thông qua chương trình mô phỏng thì chương trình đó phải hết sức “mềm dẻo”: ngoài việc cho phép người dùng đưa dữ liệu vào đúng theo chuẩn bị của họ thì nó còn có thể cho phép chạy thuật toán theo từng bước để họ có thể tiện theo dõi quá trình thay đổi dữ liệu cũng như kết quả của thuật toán sau mỗi bước thực hiện. Ngoài ra, chương trình càng hiệu quả hơn nếu nó cho phép quan sát lại các bước đã thực hiện. Vì công việc của mô phỏng là mô tả sự thay đổi về cấu trúc dữ liệu sau mỗi bước thực hiện của thuật toán nên hình ảnh mô phỏng cấu trúc đó cũng phải thay đổi theo từng bước để người học nắm bắt được ý tưởng của thuật toán. Ví dụ: với việc mô phỏng thuật toán tìm kiếm theo chiều rộng, cứ mỗi bước thực hiện xong thuật toán thì hình ảnh mô phỏng cũng phải thay đổi theo. Trong quá trình thực hiện thì đỉnh nào được chọn để xử lý sẽ có thông báo tại đỉnh đó để người dùng quan sát cho dễ. Dưới đây là hình ảnh trước và sau khi Trang 41 một bước thuật toán được thực hiện Một hình ảnh mô phỏng một bước thực hiện của thuật toán Hình ảnh mô phỏng đồ thị sau 1 bước thực hiện (1 thay đổi so với hình ảnh ở Trang 42 trên) Thường các thuật toán để dạy 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…. 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 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 Trang 43 đượ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ố 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 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 Trang 44 giải thuật. 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?.....) Việc chia thuật toán thành nhiều bước nhỏ rất có ý nghĩa trong việc lập Trang 45 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. 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. 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 Sau đây là giải thuật: Trang 46 Và ta sẽ mô phỏng theo từng bước của thuật toán như sau: Thuật
toán (giả
mã) Đồ họa mô
phỏng hoạt
động của
thuật toán Hình vẽ: Một bước mô phỏng của thuật toán Dijsktra 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. 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: Kênh mô
phỏng Các hàm
mô phỏng Màn hình
trình diễn
mô phỏng File kịch
bản Trang 47 Hình: Sơ đồ cấu trúc của một hệ thống mô phỏng - 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ô Trang 48 phỏng thuật toán để xây dựng hệ thống mô phỏng phù hợp. 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. 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 http://www.cc.gatech.edu/gvu/softviz/algoanim/samba. 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. Trang 49 Ưu điểm 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 (http://www.cs.duke.edu/~rodger/tools), 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. Trang 50 Ưu điểm 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 (http://www.cs.wm.edu/~noonan/jay/index.html) đượ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. Trang 51 Ưu điểm 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í”. 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”. Trang 52 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ụ: http://www.cs.auckland.ac.nz/ software/ AlgAnim/alg_anim.html) nhưng cũng có thể chỉ là một bài tập cá nhân (http://forum.khmt3-k2.net/t242-demo-chng-trnh-m-phng-thut-ton-heapsort-c-c- 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 đó. 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 Trang 53 mới dựa trên mô tả thực của người dùng. 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 Trang 54 những nhược điểm có thể chỉ ra như sau: 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. (http://www .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 Trang 55 những thay đổi trên đoạn giả mã và trên dữ liệu mẫu. 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à 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ỏ 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 – Trang 56 chương 3 của luận văn này. - Mô phỏng theo
từng bước 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 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. Mô hình bài toán mô phỏng thuật toán 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ể. Trang 57 Hướng đối tượng 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ẽ Trang 58 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 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.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 Trang 59 một đồ thị mới, tạo một đồ thị đã chuẩn bị từ trước: Công cụ để tạo đồ thị
cho mô phỏng Khung mô
phỏng bằng
hình ảnh đồ thị Khung
giả mã Khung trạng
thái 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 Trang 60 toán theo từng bước giã mã ở trên theo cách: 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: Trang 61 Khung chương trình mô phỏng thuật toán: Khung mô
phỏng trên đồ
thị Khung giả
mã của
thuật toán Khung trạng
thái của thuật
toán 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 Trang 62 kết quả một cách trực quan. 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 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 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. Trang 63 Khung chương trình để người dùng nhập dữ liệu đầu vào: Khung mô phỏng
bằng hình ảnh đồ
họa Khung giả
mã Khung trạng
thái 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 Trang 64 đỉ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.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: Trang 65 Khung chương trình mô phỏng: Khung mô phỏng
bằng hình ảnh đồ
họa Khung giả
mã Khung trạng
thái 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 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ô Trang 66 phỏng và mô phỏng theo kịch bản đã được “dựng” sẵn. 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) public class Entity
{
public virtual string Key { get; set; }
public virtual int Value { get; set; } public static bool IsDirection {get; set;} + IsDirection: đánh dấu đồ thị ban đầu là có hướng hay vô hướng. Đối tượng Graph: gồm các thuộc tính: + Tập các đỉnh Vertexs public class Graph
{
public Graph()
{
Vertexs = new HashSet Trang 67 + Tập các cạnh. public HashSet 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. public class Vertex : Entity
{
private Dictionary Trang 68 RemoveEdge: Loại bỏ 1 cạnh (cung) có 1 đầu mút là đỉnh đang xét. 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 } 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á Trang 69 trị này để đánh dấu có cạnh nối giữa 2 đỉnh hay không). 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 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 Trang 70 Vẽ một cạnh Vẽ đỉnh public void AddEdgeDrawing(string
fromVertex, string toVertex, int
value)
private void
RemoveVertexDrawing(VertexDrawing
vertexDrawing){}
public bool IsInShortestPath { get;
set; } public bool IsInSpanningTree { get;
set; } public bool IsInFindingPath { 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
Chứa đựng thông tin về các cạnh thuộc
cây khung của thuật toán Prim
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
Chế độ đồ họa trong khi xây dựng dữ liệu
đầu vào Chế độ đồ họa trong khi thực hiện mô
phỏng trên đồ thị đã cho 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. private void
DrawAtDesignMode(DrawingContext
drawingContext)
private void
DrawAtRunMode(DrawingContext
drawingContext)
public void
AddEdgeDrawing(EdgeDrawing e)
{}
public void
RemoveEdgeDrawing(EdgeDrawing e)
{}
public void ReRender(){}
public void
RemoveAllEdgeDrawings(){} 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: Trang 71 Chương trình con: 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 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 Kiến trúc: 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 Các công cụ trong chương trình: 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 private void GetResult() public BagStep GetBagStep() private void DfsAlgorithms(Vertex u) private void Initialize() Thực thi thuật toán.
Lấy kết quả và lưu trữ vào các bước cho vào
túi.
Lấy túi đã đựng các bước để chuyển qua mô
phỏng.
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ó.
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. Trang 72 Thực hiện công việc truy vết. private void UpdateTrace(string
after, string before) private void UpdateInfoAtStepEnd() public class StepStartDFS() public class StepEndDFS : Step 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.
Step kế thừa của lớp Step, khởi tạo đỉnh xuất
phát
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. 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 public class DfsStep1 : Step
public class DfsStep21 : Step
public class DfsStep22 : Step
public class DfsStep23 : Step
public class DfsStep3 : 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 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 Kiến trúc: 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 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 private Dictionary Trang 73 Các công cụ sử dụng trong chương trình: private BagStep _steps = new BagStep(); Các chương trình con và chức năng của chúng: public void Execute() private void GetResult() public BagStep GetBagStep() private void BfsAlgorithms(Vertex
u) private void Initialize() Thực thi thuật toán.
Lấy kết quả và lưu trữ vào các bước cho vào
túi.
Lấy túi đã đựng các bước để chuyển qua mô
phỏng.
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ó.
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. Thực hiện công việc truy vết. private void UpdateTrace(string
after, string before) private void
UpdateInfoAtStepEnd() Public class StepStart1() Public class StepEnd1 : Step 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.
Step kế thừa của lớp Step, khởi tạo đỉnh xuất
phát
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. Các bước được làm mịn trong quá trình mô
phỏng thuật toán BFS. Public class BfsStep1 : Step
Public class BfsStep21 : Step
Public class BfsStep22 : Step
Public class BfsStep23 : Step
Public class BfsStep3 : Step 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. Trang 74 Kiến trúc: 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 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 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 private HashSet Công cụ sử dụng trong module: Các chương trình con và chức năng của chúng: public void Execute() Thực hiện thuật toán Dijkstra Khởi tạo các thông số cần thiết cho public void Initialize(); thuật toán Sửa nhãn cho tất cả các đỉnh chưa private void UpdateEdgeGo(Vertex u) được chọn khi mới cố định đỉnh u Trang 75 Thủ tục Chức năng Cập nhật vết cho đường đi trong khi thực hiện thuật toán private void UpdateTrace(string after, string
before) Ghi lại các thông số cuối cùng để private void UpdateInfoAtStepEnd() dựng kịch bản cho mô phỏng Kết nạp thêm một đỉnh vào tập S private void AddVertextToVertexGone(Vertex
gone) (các đỉnh đã cố định nhãn) Ghi nhận bước đi đầu tiên của thuật private void AddStepStart() toán Dijkstra trên đồ thị vừa chọn. Cập nhật các bước để lên kịch bản mô phỏng 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. 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
đó…. 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()
public class StepStart : Step
{
public string VertexStart { get; set; }
private Dictionary Trang 76 Bước 1: Sửa nhãn cho tất cả các
đỉnh Bước 2: Chọn một đỉnh có nhãn nhỏ
nhất để cố định. 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. string key = keyEnd;
while (key != keyStart && key !=
string.Empty)
{
_edgesInShotestPath.Add(trace[key] + ">" +
key);
key = trace[key];
}
if (key == string.Empty)
_edgesInShotestPath = new
List Trang 77 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 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 Kiến trúc: 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 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 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 Trang 78 Thủ tục Chức năng thuật toán Sửa nhãn cho tất cả các đỉnh chưa private void UpdateEdgeGo(Vertex u) được chọn khi mới cố định đỉnh u 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 private void UpdateTrace(string after, string
before) toán Ghi lại các thông số cuối cùng để private void UpdateInfoAtStepEnd() dựng kịch bản cho mô phỏng Kết nạp thêm một đỉnh vào cây private void AddVertextToVertexGone(Vertex
gone) khung Ghi nhận bước đi đầu tiên của thuật private void AddStepStartPrim() toán Prim trên đồ thị vừa chọn. Cập nhật các bước để lên kịch bản mô phỏng 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() Trang 79 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. Trang 80 - Thuật toán tìm chu trình Hamilton qua tất cả các đỉnh của đồ thị. 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 Trang 81 toán nâng cao trên đồ thị: luồng, cặp ghép trên đồ thị…. 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: Trang 82 12. http://www.cs.hope.edu/algamin/cc
13. http://www.cs.edu/~zeil/algae.html
14. http://www.cc.gatech.edu/gvu/softviz/algoanim/xtango.html Trang 83 15. http://www.csse.monash.edu.au/
16. http://www.csharp-station.com/Tutorial.aspx
17. http://msdn.microsoft.com/en-us/library/aa288436(v=vs.71).aspx System.out.println(“begin”);
String[] a1 = {“4”, “453434”, "HELLO WORLD!", "01010 10101"}; System.out.println(“array a1 50 50 4 4 453434 “+”\"HELLO //ANNOTATIONS String[] a2 = {"THIS", "IS", "AN", "ARRAY"};
System.out.println(“array a2 150 100 4 “+”\"THIS\" ”+”\"IS\" void arrayExample ()
{
WORLD!\" ”+”\"01010 10101\" “+”horz black transparent”);
“+”\"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)+”] System.out.println(“changeParam System.out.println(“changeParam a1[“+String.valueOf(i)+”] System.out.println(“changeParam 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”); bkgrd transparent”);
a1[“+String.valueOf(i+1)+”] bkgrd red”);
bkgrd transparent”);
a2[“+String.valueOf(i+1)+”] bkgrd red”);
} Đầ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 để begin
array a1 50 50 4 4 453434 "HELLO WORLD!" "01010 10101"
horz black transparent Trang 84 mô phỏng: 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ô Trang 85 phỏng theo đúng file kịch bản được mô tả ở trên: [xem chi tiết tại 15] Bước 1 Bước 2 Bước 3 Bước 4 Bước 5 Bước 6 Trang 86End.
6.3. Bài toán tìm đường đi ngắn nhất trên đồ thị có trọng số
6.4. Các thuật toán tìm kiếm trên cây khung
6.5.Bài toán tìm chu trình Hamilton qua tất cả các đỉnh của đồ thị
Chương 2 MÔ PHỎNG THUẬT TOÁN
Hình. 1 Mô phỏng một bước hoạt động của thuật toán
Trên thế giới, hệ thống mô phỏng đã được sử dụng rộng rãi trong việc
4.1. Mô phỏng đúng theo thuật toán
4.2. Cho phép thực hiện theo từng bước
4.3. Mô phỏng thuật toán phải có tính động
4.4. Có thể thực thi với mọi bộ dữ liệu đầu vào
4.5. Có sự phân cấp người học
5.1.Nghiên cứu và phân tích giải thuật
5.2.Mô phỏng dữ liệu vào và kết quả đầu ra
5.3.Chia thuật toán thành nhiều bước nhỏ rồi mô phỏng theo từng bước
5.4. Tổng hợp mô phỏng theo các bước
5.5.Sơ đồ cấu trúc chung của hệ thống mô phỏng
6.1. Một số hệ thống mô phỏng thuật toán chung
6.2. Sử dụng công cụ mô phỏng thuật toán riêng biệt
Chỉ trong 0.07s có
tới 2.820.000 kết
quả
6.3. Xây dựng hệ thống từ đầu
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Ị
- 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
(http://www.unf.edu/~wkloster/foundations/DijkstraApplet/DijkstraAp
Input
Thuật toán
Output
4.1. Lựa chọn công cụ lập trình
4.2. Chức năng mô phỏng của các thuật toán được cài đặt
5.1.Tổng quan về hệ thống
Thủ tục
Chức nă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
DFS thực thi
thuật toán:
GraphTool.Mo
del.DFS
DFS mô phỏng:
Module:
GraphTool.Sear
ching.DFSForm
private Dictionary
Công cụ thuật toán:các thuật toán trợ giúp cho thuật toán chính:
Chức năng
Thủ tục
public void Execute()
BFS thực thi
thuật toán:
GraphTool.Mo
del.BFS
BFS mô phỏng:
Module:
GraphTool.Sear
ching.BFSForm
Chức năng
Thủ tục
Dijkstra thực
thi thuật toán:
GraphTool.Mo
del.Dijkstra
Dijkstra mô
phỏng:
Module:
GraphTool.Dijk
tra.DijktraFor
m
Prim thực thi
thuật toán:
GraphTool.Mo
del.Prim
Prim mô
phỏng:
Module:
GraphTool.Pri
m.PrimForm
Chương 4 KẾT LUẬN
DANH MỤC TÀI LIỆU THAM KHẢO
Tài liệu Tiếng Việt
PHỤ LỤC
Công đoạn chuẩn bị cho file kịch bản.
