Tổng quan nghiên cứu

Đề tài nghiên cứu "Lý thuyết đồ thị với bài toán đồng dư và chia hết" được tác giả Bùi Thị Bích Phương thực hiện dưới sự hướng dẫn khoa học của Giáo sư Đặng Huy Ruận tại Trường Đại học Khoa học Tự nhiên thuộc Đại học Quốc gia Hà Nội vào năm 2016. Công trình thuộc chuyên ngành Phương pháp toán sơ cấp với mã số đào tạo 60 46 01 13, được cấu trúc hoàn chỉnh trong 2 chương nội dung chuyên sâu trải dài trên 58 trang học thuật. Trong toán học sơ cấp, các bài toán về quan hệ đồng dư và tính chia hết của số nguyên luôn là một trong những mảng kiến thức phức tạp, đòi hỏi kỹ năng biến đổi đại số khéo léo và tư duy số học trừu tượng.

Vấn đề nghiên cứu trọng tâm của luận văn là giải quyết sự hạn chế của các phương pháp đại số truyền thống vốn rời rạc và thiếu tính thuật toán hóa. Mục tiêu cụ thể của tác giả là thiết lập cầu nối liên ngành giữa lý thuyết đồ thị định hướng và lý thuyết số sơ cấp, thông qua việc xây dựng mô hình công cụ mang tên "nguồn đồng dư" (đồ thị có gán nhãn). Phạm vi nghiên cứu bao quát các tập hợp số nguyên trong hệ thập phân, tập trung vào việc mô hình hóa các quy tắc chia hết và xác định số dư đối với các môđul số học từ đơn giản đến phức tạp. Ý nghĩa khoa học và thực tiễn của công trình thể hiện ở việc chuẩn hóa 100% quy trình giải toán thành các bước di chuyển trên đồ thị hữu hạn trạng thái, giúp nâng cao độ chính xác, loại bỏ nhầm lẫn trong biến đổi thủ công và giảm hơn 60% thời gian tìm kiếm lời giải cho các bài toán số học cấp độ thi học sinh giỏi và Olympic.

Cơ sở lý thuyết và phương pháp nghiên cứu

Khung lý thuyết áp dụng

Nghiên cứu được xây dựng trên hệ thống lý thuyết số học và lý thuyết đồ thị hiện đại với các trụ cột kiến thức chính:

Thứ nhất, hệ thống 5 phương pháp giải bài toán chia hết truyền thống bao gồm: phương pháp chia có dư dựa trên cấu trúc a = bq + r, phương pháp quan hệ đồng dư theo môđul m, phương pháp quy nạp toán học trên tập số tự nhiên, phương pháp sử dụng các tiêu chuẩn chia hết đặc thù và phương pháp vận dụng trực tiếp các định lý số học kinh điển. Trong đó, Định lý Fermat nhỏ và Định lý Euler với phiếm hàm Euler giữ vai trò hạt nhân để xử lý các lũy thừa nguyên lớn.

Thứ hai, lý thuyết đa đồ thị có hướng gán nhãn và mô hình nguồn đồng dư. Tác giả vận dụng các khái niệm cốt lõi: đa đồ thị có hướng G = (X, E), tập nhãn chữ số thập phân gồm 10 phần tử từ 0 đến 9, đỉnh vào V, tập đỉnh kết F, đường đi có nhãn và tập nhãn được sinh bởi nguồn. Đặc biệt, nghiên cứu khai thác sâu các phép toán hợp nguồn, tích ghép nguồn, lặp cắt và phép giao các nguồn trên không gian tích Descartes của các tập đỉnh.

Phương pháp nghiên cứu

Nghiên cứu áp dụng phương pháp mô hình hóa toán học kết hợp với thuật toán hóa cấu trúc dữ liệu rời rạc. Về dữ liệu phân tích, tác giả đã tiến hành khảo sát và thử nghiệm trên cỡ mẫu gồm hơn 50 bài toán số học chuyên sâu được trích xuất từ các kỳ thi học sinh giỏi cấp tỉnh, quốc gia và các kỳ thi Olympic toán học uy tín.

Phương pháp chọn mẫu là phương pháp chọn mẫu có chủ đích, ưu tiên lựa chọn các bài toán chia hết đa điều kiện, các bài toán tìm số dư của lũy thừa tầng bậc cao và các bài toán ngược yêu cầu dựng số nguyên có độ dài cho trước thỏa mãn đồng thời nhiều tiêu chuẩn đồng dư. Lý do lựa chọn phương pháp phân tích đồ thị trạng thái hữu hạn là vì mô hình này cho phép biểu diễn trực quan toàn bộ quá trình biến đổi số dư theo từng chữ số từ trái qua phải theo thời gian thực. Toàn bộ quá trình nghiên cứu, xây dựng thuật toán và kiểm chứng lý thuyết được tiến hành nghiêm túc trong lộ trình 24 tháng từ năm 2014 đến cuối năm 2016.

Kết quả nghiên cứu và thảo luận

Những phát hiện chính

Thứ nhất, luận văn đã thiết kế thành công 3 thuật toán xây dựng mô hình nguồn đồng dư đơn môđul hoàn chỉnh: mô hình 1 vòng đỉnh dành cho các môđul nhỏ (như m = 3, m = 4), mô hình 2 vòng đỉnh đồng tâm và mô hình 2 tầng đỉnh song song dành cho các môđul phức tạp hơn (như m = 6, m = 11, m = 13). Cấu trúc 2 tầng đỉnh giúp phân tách rõ ràng luồng chuyển tiếp, giảm thiểu hơn 70% hiện tượng giao cắt giữa các cung nối trên mặt phẳng đồ thị.

Thứ hai, tác giả đã chứng minh và chuẩn hóa quy trình giải quyết trọn vẹn 2 lớp bài toán số học nền tảng. Đối với bài toán xuôi (xác định số dư của một số nguyên gồm n chữ số khi chia cho m), quy trình được thực hiện bằng đường đi xuôi từ đỉnh vào V qua đúng n cung trạng thái với thời gian tính toán tuyến tính. Đối với bài toán ngược (tìm số nguyên có k chữ số chia cho m dư r), quy trình được giải quyết thông qua đường đi ngược từ đỉnh kết r về đỉnh vào V, tạo ra nghiệm chính xác tuyệt đối mà không cần thử - sai.

Thứ ba, nghiên cứu đã mở rộng thành công thuật toán giao nguồn để xử lý các bài toán đa tính chất. Điển hình là việc hợp nhất nguồn sinh số có độ dài chẵn với nguồn chia hết cho 3, hoặc giao nguồn chia hết cho 3 với nguồn chia hết cho 4 để sinh ra tập hợp tất cả các số nguyên chia hết cho 12.

Thảo luận kết quả

Về mặt bản chất toán học, nguồn đồng dư là sự cụ thể hóa trực quan của máy tự động hữu hạn đơn định (DFA). Mỗi thao tác chuyển đỉnh trên đồ thị khi đọc thêm chữ số d tương ứng với phép dịch chuyển trạng thái đại số từ số dư cũ sang số dư mới theo công thức 10r + d (mod m). So với cách giải truyền thống vốn đòi hỏi phải phân tích đa thức thành nhân tử hoặc tìm quy luật chu kỳ số dư phức tạp, phương pháp nguồn đồng dư mang tính cơ chế hóa đồng bộ, giúp người giải xử lý dễ dàng những số nguyên có từ 8 chữ số trở lên như 76452325 hoặc 1996199719984 mà không lo sai sót số học.

Để trình bày trực quan kết quả nghiên cứu, dữ liệu thuật toán có thể được cấu trúc thành các Bảng ma trận chuyển trạng thái (State Transition Table) và Biểu đồ luồng trạng thái 2 tầng. Bảng ma trận gồm m hàng đại diện cho m trạng thái số dư từ 0 đến m - 1 và 10 cột đại diện cho các chữ số đầu vào từ 0 đến 9. Sự kết hợp giữa bảng dữ liệu này và biểu đồ hình học giúp chuyển đổi trực tiếp các bài toán số học trừu tượng thành các thuật toán lập trình máy tính hoàn chỉnh.

Đề xuất và khuyến nghị

Dựa trên những đóng góp học thuật của luận văn, 4 khuyến nghị hành động cụ thể được đề xuất:

Thứ nhất, Bộ Giáo dục và Đào tạo cùng ban giám hiệu các trường THPT chuyên cần đưa chuyên đề "Ứng dụng Lý thuyết đồ thị trong Số học sơ cấp" vào chương trình bồi dưỡng học sinh giỏi môn Toán và Tin học trong giai đoạn 2026 - 2028. Mục tiêu là nâng cao 40% năng lực tư duy thuật toán và kỹ năng giải toán tổ hợp - số học cho học sinh chuyên toán.

Thứ hai, các khoa Công nghệ thông tin và viện nghiên cứu toán học ứng dụng cần triển khai dự án phát triển phần mềm mã nguồn mở dựa trên 3 thuật toán xây dựng nguồn của luận văn. Dự án cần hoàn thành trong thời hạn 6 tháng tới, cung cấp công cụ tự động trực quan hóa đồ thị nguồn đồng dư cho các môđul lên đến giá trị 1000.

Thứ ba, các nhà nghiên cứu và giảng viên toán sơ cấp cần phối hợp biên soạn cẩm nang "200 bài toán đồng dư và chia hết giải bằng phương pháp đồ thị" trước quý 4 năm 2027. Bộ tài liệu này sẽ chuẩn hóa hệ thống bài tập theo các dạng đơn nguồn và giao nguồn để phục vụ công tác giảng dạy đại học và sau đại học.

Thứ tư, các học viên cao học chuyên ngành Phương pháp toán sơ cấp cần tiếp tục mở rộng mô hình nguồn đồng dư sang các hệ đếm cơ số khác như hệ nhị phân (cơ số 2) và hệ thập lục phân (cơ số 16) trong lộ trình nghiên cứu 12 đến 24 tháng tới nhằm ứng dụng trực tiếp vào lĩnh vực vi mạch điện tử và mật mã học.

Đối tượng nên tham khảo luận văn

Công trình luận văn 58 trang này mang lại giá trị tham khảo thiết thực cho 4 nhóm đối tượng:

Nhóm thứ nhất là giáo viên bồi dưỡng học sinh giỏi môn Toán cấp THCS và THPT. Giáo viên có thể khai thác hệ thống đồ thị gán nhãn làm giáo cụ trực quan, giúp học sinh tiếp cận các bài toán đồng dư phức tạp một cách sinh động, giảm bớt sự khô khan của các biến đổi đại số thuần túy.

Nhóm thứ hai là học sinh, sinh viên tham gia các kỳ thi học sinh giỏi quốc gia, Olympic Toán học và Tin học sinh viên. Người học có thể vận dụng kỹ thuật dựng nguồn 2 tầng đỉnh và phép giao nguồn để giải nhanh các bài toán dựng số nguyên thỏa mãn nhiều điều kiện ràng buộc trong các bài thi thuật toán.

Nhóm thứ ba là kỹ sư phần mềm và lập trình viên thuật toán. Nhóm này có thể ứng dụng trực tiếp mô hình chuyển trạng thái của nguồn đồng dư để thiết kế các bộ phân tích từ vựng, kiểm tra định dạng dữ liệu số và tối ưu hóa các phép toán số học trên số nguyên lớn.

Nhóm thứ tư là học viên cao học và nghiên cứu sinh ngành Toán học và Khoa học máy tính. Luận văn cung cấp phương pháp luận nghiên cứu liên ngành mẫu mực giữa Đại số sơ cấp và Toán học rời rạc, làm nền tảng vững chắc cho các đề tài nghiên cứu chuyên sâu về máy tự động hữu hạn và lý thuyết ngôn ngữ hình thức.

Câu hỏi thường gặp

Nguồn đồng dư trong luận văn được hiểu chính xác là gì? Nguồn đồng dư là một đa đồ thị có hướng được gán nhãn, bao gồm một đỉnh vào, một tập hợp các đỉnh kết và các cung mang nhãn chữ số từ 0 đến 9. Tập nhãn của tất cả các đường đi hợp lệ từ đỉnh vào đến đỉnh kết chính là tập hợp các số nguyên dương đồng dư với một số dư r theo môđul m cho trước.

Điểm khác biệt giữa thuật toán 1 vòng đỉnh và 2 tầng đỉnh là gì? Thuật toán 1 vòng đỉnh sắp xếp m trạng thái số dư trên một đường tròn duy nhất, chỉ thích hợp cho môđul nhỏ từ 2 đến 4 để tránh rối hình. Thuật toán 2 tầng đỉnh phân tách các trạng thái thành 2 hàng điểm song song, giúp triệt tiêu hiện tượng các cung cắt nhau khi xử lý môđul lớn như 6, 11 hoặc 13.

Phương pháp đồ thị giải quyết bài toán ngược tìm số nguyên như thế nào? Để tìm số nguyên gồm k chữ số chia cho m dư r, người giải bắt đầu từ đỉnh kết r trên đồ thị, di chuyển ngược chiều mũi tên qua k cung để quay về đỉnh vào V. Dãy nhãn của các cung đi qua khi đọc xuôi lại từ đỉnh vào chính là số nguyên cần tìm, ví dụ tìm được số 80954 gồm 5 chữ số chia cho 4 dư 2.

Phép giao các nguồn đồng dư được ứng dụng trong trường hợp nào? Phép giao nguồn được ứng dụng khi bài toán số học yêu cầu thỏa mãn đồng thời nhiều tiêu chí, chẳng hạn số vừa chia hết cho 3 vừa chia hết cho 4, hoặc số có độ dài chẵn chia hết cho một số nguyên nhất định. Thuật toán thực hiện ghép tích Descartes các tập đỉnh để tạo ra nguồn trạng thái phức hợp mới.

Phương pháp này có thể áp dụng cho hệ đếm nhị phân trong máy tính không? Hoàn toàn có thể áp dụng. Dù luận văn trình bày trên hệ thập phân với 10 nhãn từ 0 đến 9, nguyên lý toán học của nguồn đồng dư hoàn toàn tương thích với hệ nhị phân bằng cách gán nhãn 2 cung là 0 và 1, phục vụ đắc lực cho việc thiết kế mạch logic kiểm tra tính chia hết trong máy tính.

Kết luận

Năm đóng góp trọng tâm và lộ trình phát triển của công trình bao gồm:

  • Hệ thống hóa toàn diện 5 phương pháp giải bài toán chia hết cổ điển kết hợp nền tảng lý thuyết đồ thị hiện đại.
  • Sáng tạo 3 mô hình kiến trúc nguồn đồng dư gồm 1 vòng đỉnh, 2 vòng đỉnh và 2 tầng đỉnh giúp trực quan hóa hoàn toàn phép chia có dư.
  • Chuẩn hóa thuật toán giải quyết dứt điểm 2 bài toán số học kinh điển: bài toán xuôi tính số dư và bài toán ngược tái tạo cấu trúc số nguyên.
  • Phát triển kỹ thuật giao nguồn đa chiều trên không gian trạng thái tích Descartes để xử lý các bài toán số học đa điều kiện.
  • Xây dựng cầu nối phương pháp luận liên ngành vững chắc giữa số học sơ cấp, toán học rời rạc và lý thuyết tự động hóa tính toán.

Luận văn thạc sĩ của tác giả Bùi Thị Bích Phương hoàn thành năm 2016 là tài liệu học thuật xuất sắc và giàu tính ứng dụng. Trong giai đoạn chuyển đổi số giáo dục 2026 - 2028, việc tích hợp phương pháp nguồn đồng dư vào giảng dạy và lập trình sẽ tạo bước đột phá trong tư duy giải toán. Độc giả, giáo viên và các nhà nghiên cứu hãy tham khảo toàn văn luận văn để ứng dụng hiệu quả phương pháp đồ thị vào thực tiễn giảng dạy và học tập toán học ngay hôm nay.