Các bước dùng để kiểm tra thuật toán năm 2024

Mô phỏng thuật toán minh họa trực quan từng bước của thuật toán giúp người học có thể nhận thức được quá trình diễn biến và thay đổi của dữ liệu dẫn đến kết quả cuối cùng. Là cơ sở hỗ trợ đắc lực cho việc nắm và hiểu được bản chất của thuật toán.

Tìm hiểu về mô phỏng thuật toán và xây dựng demo mô phỏng thuật toán sắp xếp cơ bản là nội dung chính của bài báo. Trên cơ sở đó để làm tài liệu tham khảo cho học phần Cấu trúc dữ liệu và giải thuật giúp người học có thể hình dung rõ hơn về quá trình sắp xếp, nguyên lý hoạt động của thuật toán, đồng thời vận dụng việc mô phỏng với nhiều thuật toán khác của phần đồ thị.

1. Giới thiệu

Mô phỏng thuật toán là quá trình mô tả cấu trúc dữ liệu, thao tác của một chương trình bằng đồ họa. Mô phỏng thuật toán được sử dụng như một công cụ trợ giúp cho việc giảng dạy, nó có thể cung cấp các mô phỏng động bằng đồ họa của một thuật toán và các thay đổi trong cấu trúc dữ liệu trong suốt quá trình thực thi. Như một phần của quá trình học thuật toán, những sinh viên ngành công nghệ thông tin sẽ học về cấu trúc của một trình biên dịch trong một ngôn ngữ lập trình cho quá trình đó.

Khi cài đặt thuật toán bằng một ngôn ngữ lập trình cụ thể, máy tính chuyển chương trình nguồn thành chương trình dịch, và từ chương trình dịch thành chương trình đích (ngôn ngữ máy). Nhưng quá trình diễn biến của chương trình như thế nào, các lệnh ở các bước được xử lí ra sao thì người dùng không thấy được và dẫn đến việc xử lí lỗi khó khăn. Thông qua mô phỏng thuật toán có thể nắm bắt từng bước chi tiết, chính xác để tìm và khắc phục lỗi của chương trình. Đồng thời giúp người học đưa ra những bộ test chương trình hợp lí, khoa học để có thể kiểm tra hết các trường hợp có thể xảy ra của thuật toán cũng như tính đúng đắn của thuật toán.

Minh họa thuật toán là một yêu cầu cơ bản của học phần Cấu trúc dữ liệu và giải thuật. Nhưng không nắm được nguyên lý hoạt động của thuật toán thì quá trình minh họa sẽ gặp khó khăn. Xuất phát từ thực tế môn học, nhiều bạn sinh viên lúng túng khi minh họa thuật toán, đặc biệt các bạn sinh viên Lào, việc mô phỏng thuật toán đã hỗ trợ rất tích cực cho môn học.

Bên cạnh đó, hiện nay hình thức đào tạo E-learning và học theo tín chỉ phổ biến, vấn đề tự học và nghiên cứu tài liệu là yêu cầu tất yếu. Bài giảng kèm theo các đoạn mô phỏng đã hỗ trợ rất nhiều cho người học, tăng hứng thú cho người học, kích thích sự sáng tạo, đem lại hiệu quả cao trong giáo dục đào tạo.

2. Quy trình mô phỏng thuật toán

Mô phỏng thuật toán gồm các bước cơ bản sau:

Bước 1: Phân tích thuật toán

Để thực hiện quá trình mô phỏng thì việc đầu tiên là phải phân tích kỹ thuật toán đó. Một thuật toán cần dùng đến chương trình mô phỏng thì thường thuật toán không đơn giản. Xác định dữ liệu vào và dữ liệu ra của thuật toán, tức là xác định thuật toán xây dựng trên cấu trúc dữ liệu nào, xác định các trường hợp cần xét của dữ liệu, giá trị biến để thoát khỏi vòng lặp…

Chẳng hạn, cho dãy số nguyên, yêu cầu tìm phần tử lớn nhất. Với bài toán này, xác định dữ liệu vào là mảng một chiều, với dữ liệu kiểu mảng xác định cách nhập mảng… hay bài toán danh sách cán bộ với hai thao tác thường xuyên thực hiện là bổ sung và loại bỏ thì dùng cấu trúc dữ liệu mảng không còn phù hợp mà nên dùng kiểu danh sách nối đơn, từ đó xác định thuật toán tác động trên danh sách móc nối.

Bước 2: Xây dựng mô hình mô phỏng dữ liệu vào và dữ liệu ra

Mô phỏng dữ liệu vào là cách chọn hình thức hiện thị cho cấu trúc dữ liệu tương ứng với giải thuật. Việc lựa chọn hình thức 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.

Ví dụ: Mô phỏng thuật toán sắp xếp dãy số, dữ liệu vào là một dãy số. Dãy số này sẽ được thể hiện là các nút hình tròn kèm với giá trị số. Dãy nút chưa sắp xếp và đã sắp xếp sẽ có màu sắc khác nhau để phân biệt.

Hình 1. Giao diện chương trình trong quá trình sắp xếp giải thuật Bubble sort

Bước 3: Tách thuật toán thành nhiều bước nhỏ

Việc tách thuật toán thành nhiều bước nhỏ tương tự như phân tích bài toán theo hướng modul hóa, giúp quá trình mô phỏng dễ dàng và chi tiết hơn.

Bước 4: Tổng hợp các các bước mô phỏng thành thuật toán hoàn chỉnh

Bước 5: Kiểm nghiệm giải thuật thông qua dữ liệu ra của từng bước nhỏ

Hình 2. Sơ đồ các bước mô phỏng thuật toán

Khi mô phỏng thuật toán cần lưu ý các bước mô tả bằng hình ảnh phải phản ánh đúng thuật toán, việc mô phỏng cho phép thực hiện theo từng bước để dễ dàng quan sát sự thay đổi dữ liệu, có nhiều cách để đưa dữ liệu vào và có độ trễ của các tháo tác để phù hợp với nhiều trình độ sinh viên.

3. Demo chương trình

Chương trình mô phỏng các thuật toán sắp xếp được xây dựng trên ngôn ngữ C#. Các chức năng chính của chương trình:

Nhập dữ liệu: Có các lựa chọn:

- Tạo mảng với số phần tử tùy ý từ 8 đến 15 phần tử do người dùng định trước. Giá trị của các phần tử được mặc định gán bằng 0.

- Lấy giá trị ngẫu nhiên: Tự động gán giá trị ngẫu nhiên cho các phần tử của mảng đã được tạo.

- Nhập từ bàn phím: Gán hoặc thay đổi giá trị cho các phần tử của mảng đã được tạo từ bàn phím.

- Nhập từ file (Nhập từ file TEST.TXT lưu cùng thư mục với file .EXE)

Phần điều khiển: Có các chức năng:

- Sắp xếp: Bắt đầu thực hiện quá trình sắp xếp.

- Tạm dừng: dừng lại Tùy thích khi chương trình đang chạy sắp xếp.

- Tốc độ sắp xếp: thay đổi tốc độ sắp xếp ngay cả khi khi chương trình đang sắp xếp.

- Từng bước: chạy từng bước của giải thuật để tiện theo dõi các bước sắp xếp.

Hình 3. Giao diện chương trình

Phần Code C/C++: Hiển thị minh họa code C/C++ giúp dễ hình dung quá trình hoạt động của các giải thuật theo từng bước

4. Kết luận

Nghiên cứu về mô phỏng thuật toán, nhận thấy vai trò của mô phỏng thuật toán trong giáo dục. Trên cơ sở đó, vận dụng thiết kế chương trình mô phỏng thuật toán sắp xếp. Các thuật toán sắp xếp được sử dụng rất nhiều trong các bài toán Tin học, nhưng để nhớ và nắm bản chất của các thuật toán sắp xếp chưa phải sinh viên nào cũng làm được. Chương trình này hỗ trợ, làm tài liệu tham khảo cho học phần Cấu trúc dữ liệu và giải thuật. Ngoài ra có thể vận dụng để minh họa cho các thuật toán với đồ thị.

Tài liệu tham khảo

[1] Đỗ Xuân Lôi (2006), Cấu trúc dữ liệu và giải thuật, NXB Đại học Quốc gia Hà Nội.

[2] Hoàng Hữu Việt (2015), Lập trình C# cho ứng dụng cơ sở dữ liệu, NXB Trường Đại học Vinh.

[3] Nguyễn Thị Chinh (2011), Luận văn thạc sĩ: Mô phỏng một số thuật toán trên đồ thị, Đại học Quốc gia Hà Nội, Trường Đại học Công nghệ.