Mô phỏng thuật toán, tưởng dễ mà khó!

October 25, 2020 1 By Nam Vu

Bài viết trước mình có đề cập đến thuật toán, bạn đọc có thể đọc lại tại đây
# http://blog.ntechdevelopers.com/thuat-toan-lieu-co-ma-thuat-phuc-tap-va-bi-an-nhu-moi-nguoi-van-nghi/
Hôm nay mình sẽ nói về việc áp dụng mô phỏng thuật toán trong quá trình học tập hiệu quả hơn!

Bắt đầu thôi!

Cùng với sự phát triển của ngành công nghệ thông tin, việc đưa máy tính vào các trường học đã tạo ra bước ngoặt lớn trong việc dạy học. Sử dụng mô phỏng trên máy tính là phương pháp sư phạm tích cực phát huy cao độ tính độc lập, khả năng làm việc trí tuệ của sinh viên, tạo ra một nhịp độ phong cách trạng thái tâm lí mới làm thay đổi phương pháp và hình thức dạy và học. Chính vì vậy phương pháp mô phỏng trong giảng dạy các môn học nói chung và các môn học thuộc chuyên ngành công nghệ thông tin nói riêng được sử dụng rộng rãi ở các trường đại học trong và ngoài nước, dành cho mọi đối tượng đào tạo.

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.

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 và 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.

Các thuật toán giải các bài toán tin học điển hình

Giải thuật chia để trị
Giải thuật quay lui
Giải thuật nhánh cận
Giải thuật tham lam
Giải thuật Quy hoạch động
Các phương pháp biểu diễn đồ thị trên máy tính
Giải thuật tìm kiếm trên đồ thị
Giải thuật tìm chu trình trên đồ thị
Giải thuật tìm đường đi ngắn nhất, và cây khung nhỏ nhất

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

Bước 1: Phân tích thuật toán
Bước 2: Xây dựng mô hình mô phỏng dữ liệu vào và dữ liệu ra
Bước 3: Tách thuật toán thành nhiều bước nhỏ
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ỏ

Ví dụ nhé! Cách mình xây dựng chương trình mô phỏng sắp xếp QuickSort và Tìm kiếm nhị phân bằng phương pháp chia để trị như thế nào.

*** Giải thuật chia để trị ***

– Ý tưởng:
Kỹ thuật “Chia để trị” là kỹ thuật quan trọng và áp dụng rộng rãi nhất trong kỹ thuật thiết kế giải thuật. Nó phân rã bài toán kích thước n thành các bài toán con nhỏ hơn mà việc tìm lời giải của chúng là cùng một cách. Lời giải của bài toán đã cho được xây dựng từ lời giải của các bài toán con này. Ta có thể nói vắn tắt ý tưởng chính của phương pháp này là: chia dữ liệu thành từng miền đủ nhỏ, giải bài toán trên các miền đã chia rồi tổng hợp kết quả lại.

– Mô hình:
Nếu gọi D&C(R) – Với R là miền dữ liệu, là hàm thể hiện cách giải bài toán theo phương pháp chia để trị thì ta có thể viết:Thủ tục thuật toán chia để trị có thể cài đặt như sau (mô phỏng bằng mã giả trên C/C++):

Các minh họa kỹ thuật thiết kế “Chia để trị” được cụ thể hóa qua các bài toán tin học ứng dụng điển hình: bài toán tìm kiếm nhị phân (Binary Searching), bài toán MinMax, bài toán sắp xếp (thuật toán Quicksort)

– Tách thuật toán:
Dùng thuật toán QuickSort(QS) để sắp xếp các giá trị trong một mảng các số theo thứ tự, chẳng hạn tăng dần. Phương pháp QuickSort (hay còn gọi là phân đoạn) là một cải tiến của phương pháp sắp xếp đổi chỗ trực tiếp, do C.A.R Hoare đề xuất.

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

– Kiểm nghiệm giải thuật thông qua dữ liệu ra của từng bước nhỏ:
Cái này mình phải test cả tháng trời luôn đó!

Đến đây bạn thấy sự khó khăn của việc xây dựng chương trình mô phỏng thuật toán thế nào rồi chứ ạ.
Không những phải hiểu sâu về thuật toán mà còn phải diễn đạt làm sao cho người mới học hiểu.
Trước đây mình cũng trầy trật mới có thể release nổi chương trình này cho khoa Công Nghệ Thông tin của trường mình.
@@ Một mình làm đó nha 😄