Luận án tiến sĩ về đại số khoảng otomat và các ứng dụng thực tiễn

• Tác giả: Bùi Vũ Anh
• Người hướng dẫn: TS. Phan Trung Huy
• Trường học: Đại học Quốc gia Hà Nội
• Chuyên ngành: Bảo đảm Toán học cho máy tính và hệ thống tính toán
• Đề tài: Đại Số Khoảng, Otomat Khoảng Và Một Số Ứng Dụng
• Loại tài liệu: luận án tiến sĩ
• Năm xuất bản: 2015
• Địa điểm: Hà Nội

• LỜI CAM ĐOAN
• LỜI CẢM ƠN
• 1. MỤC LỤC
• 1.1. Lời cam đoan
• 1.2. Danh mục từ viết tắt
• 1.3. Danh sách hình vẽ
• 1.4. Các cách tiếp cận theo hướng otomat
• 1.5. Các cách tiếp cận theo hướng đại số
• 1.6. Mục tiêu của luận án
• 1.7. Các kết quả chính của luận án
• 1.8. Cấu trúc của luận án
• 1.9. Một số khái niệm cơ sở
• 1.10. Quan hệ hai ngôi
• 1.11. Nửa nhóm, vị nhóm
• 1.12. Từ và ngôn ngữ
• 1.13. Otomat hữu hạn
• 1.14. Otomat hữu hạn đơn định
• 1.15. Mối quan hệ giữa otomat đơn định và đa định
• 1.16. Bài toán xác định ngôn ngữ
• 1.17. Otomat tối tiểu
• 1.18. Cấu trúc đại số khoảng
• 1.19. Đại số khoảng
• 1.20. Quan hệ thứ tự trên khoảng
• 1.21. Giao thức chứng thực Zero-Knowledge
• 1.22. Ví dụ về giao thức Zero-Knowledge
• 1.23. Hệ thống Zero-Knowledge dùng tích khoảng
• 1.24. Giao thức Zero-Knowledge kiểm chứng một phía
• 1.25. Ngôn ngữ và otomat khoảng
• 1.26. Ngôn ngữ khoảng
• 1.27. Các phép toán trên d-ngôn ngữ
• 1.28. Otomat khoảng đơn định và đa định
• 1.29. Bài toán đơn định hoá otomat khoảng
• 1.30. Otomat khoảng tối tiểu
• 1.31. Một số ứng dụng
• 1.32. Bài toán tìm d-đường đi nhanh nhất
• 1.33. Mô hình mạng ưu tiên (Priority Network - PN)
• 1.34. Mô hình mạng ưu tiên bằng otomat khoảng
• 1.35. Bài toán đạt được
• 1.36. Ví dụ về PN trong thực tiễn
• 1.37. Mô hình hệ thống máy tính ghép cụm
• 1.38. Lập lịch công việc
• 1.39. Thuật toán lập lịch tổng quát
• 1.40. Các công trình đã công bố
• 1.41. Tài liệu tham khảo

I. Giới thiệu về đại số khoảng và otomat

Nghiên cứu về đại số khoảng và otomat là một lĩnh vực quan trọng trong toán học và khoa học máy tính. Đại số khoảng cung cấp một khung lý thuyết để mô hình hóa và phân tích các hệ thống phức tạp. Otomat là công cụ hữu hiệu để mô hình hóa các hệ thống hoạt động dưới dạng chuyển trạng thái. Việc kết hợp giữa đại số khoảng và otomat mở ra nhiều hướng nghiên cứu mới, giúp giải quyết các bài toán trong thực tiễn. Theo nghiên cứu của Bùi Vũ Anh, việc áp dụng đại số khoảng vào otomat không chỉ giúp tăng cường khả năng biểu diễn mà còn mở rộng khả năng tính toán trên các nhãn của otomat.

1.1. Khái niệm cơ bản về đại số khoảng

Khái niệm đại số khoảng được định nghĩa dựa trên các khoảng số thực, cho phép thực hiện các phép toán như cộng, trừ, nhân, chia trên các khoảng. Điều này giúp mô hình hóa các hệ thống có tính chất không chắc chắn và biến đổi. Đại số khoảng không chỉ đơn thuần là một công cụ lý thuyết mà còn có ứng dụng thực tiễn trong các lĩnh vực như khoa học máy tính, lý thuyết thông tin và an toàn thông tin. Việc xây dựng các cấu trúc đại số trên khoảng giúp giải quyết các bài toán phức tạp hơn, từ đó nâng cao hiệu quả của các thuật toán trong thực tiễn.

1.2. Các loại otomat và ứng dụng của chúng

Có nhiều loại otomat khác nhau, bao gồm otomat hữu hạn, otomat thời gian, và otomat khoảng. Mỗi loại có những đặc điểm riêng và ứng dụng trong các lĩnh vực khác nhau. Otomat hữu hạn thường được sử dụng trong lý thuyết ngôn ngữ, trong khi otomat thời gian được áp dụng trong các hệ thống thời gian thực. Otomat khoảng là một mô hình mới, cho phép mô hình hóa các hệ thống phức tạp hơn với các ràng buộc khoảng. Việc nghiên cứu và phát triển các loại otomat này không chỉ giúp hiểu rõ hơn về lý thuyết mà còn có ứng dụng thực tiễn trong việc thiết kế và kiểm chứng các hệ thống phần mềm.

II. Phương pháp nghiên cứu và kết quả chính

Luận án của Bùi Vũ Anh đã áp dụng các phương pháp nghiên cứu hiện đại để phát triển lý thuyết về đại số khoảng và otomat. Các kết quả chính bao gồm việc xây dựng một cấu trúc đại số trên các khoảng, từ đó phát triển các thuật toán mới cho các bài toán trong lĩnh vực này. Đặc biệt, việc áp dụng đại số khoảng vào otomat đã mở ra hướng nghiên cứu mới trong việc mô hình hóa các hệ thống thời gian thực. Các thuật toán được đề xuất không chỉ có tính lý thuyết mà còn có thể áp dụng trong thực tiễn, như trong việc xây dựng giao thức bảo mật Zero-Knowledge.

2.1. Cấu trúc đại số và các phép toán

Cấu trúc đại số được xây dựng trên các khoảng cho phép thực hiện các phép toán phức tạp hơn so với các mô hình truyền thống. Các phép toán này bao gồm phép cộng, trừ, và các phép toán logic, giúp tăng cường khả năng tính toán trên các nhãn của otomat. Việc định nghĩa các quan hệ thứ tự trên khoảng cũng là một điểm nổi bật trong nghiên cứu này, giúp mở rộng khả năng ứng dụng của đại số khoảng trong các lĩnh vực khác nhau.

2.2. Ứng dụng trong thực tiễn

Các ứng dụng của đại số khoảng và otomat trong thực tiễn rất đa dạng. Một trong những ứng dụng quan trọng là trong việc xây dựng các giao thức bảo mật như Zero-Knowledge. Giao thức này đảm bảo tính riêng tư và bí mật của thông tin trong quá trình trao đổi. Ngoài ra, việc sử dụng otomat khoảng trong các bài toán tìm đường nhanh nhất và mô hình mạng ưu tiên cũng cho thấy tính ứng dụng cao của nghiên cứu này trong các hệ thống thực tế.