Đại số máy tính

Trong toán học tính toán, đại số máy tính, còn được gọi là tính toán bằng biểu tượng hoặc biểu số máy tính, là một lĩnh vực khoa học đề cập đến việc nghiên cứu và phát triển các thuật toán và phần mềm để điều khiển các biểu thức toán học và các đối tượng toán học khác. Mặc dù đại số máy tính có thể được coi là một trường con của điện toán khoa học, nhưng chúng thường được coi là các trường riêng biệt bởi vì điện toán khoa học thường dựa trên tính toán số với các số dấu phẩy động gần đúng, trong khi tính toán biểu tượng nhấn mạnh tính toán chính xác với các biểu thức chứa các biến không có giá trị nhất định và được thao tác như là các biểu tượng.

Các ứng dụng phần mềm thực hiện các phép tính tượng trưng được gọi là hệ thống đại số máy tính, với thuật ngữ hệ thống ám chỉ sự phức tạp của các ứng dụng chính bao gồm, ít nhất là một phương pháp biểu diễn dữ liệu toán học trong máy tính, ngôn ngữ lập trình người dùng (thường khác với ngôn ngữ được sử dụng để thực hiện), trình quản lý bộ nhớ chuyên dụng, giao diện người dùng cho đầu vào / đầu ra của các biểu thức toán học, một tập hợp lớn các thói quen để thực hiện các hoạt động thông thường, như đơn giản hóa các biểu thức, phân biệt bằng cách sử dụng quy tắc chuỗi, nhân tử đa thức, tích phân bất định, v.v..

Đại số máy tính được sử dụng rộng rãi để thử nghiệm trong toán học và thiết kế các công thức được sử dụng trong các chương trình số. Nó cũng được sử dụng cho các tính toán khoa học hoàn chỉnh, khi các phương pháp số hoàn toàn thất bại, như trong mật mã khóa công khai, hoặc cho một số vấn đề phi tuyến tính.

Thuật ngữ

Một số tác giả phân biệt đại số máy tính với tính toán biểu tượng bằng cách sử dụng tên sau để chỉ các loại tính toán tượng trưng khác với tính toán với các công thức toán học. Một số tác giả sử dụng tính toán tượng trưng cho khía cạnh khoa học máy tính và "đại số máy tính" cho khía cạnh toán học. Trong một số ngôn ngữ, tên của trường không phải là bản dịch trực tiếp tên tiếng Anh của nó. Thông thường, nó được gọi là calcul formel trong tiếng Pháp, có nghĩa là "tính toán chính thức". Tên này phản ánh ràng buộc lĩnh vực này với phương pháp hình thức.

Trước đây, tính toán tượng trưng cũng được gọi là thao tác biểu tượng, thao tác đại số, xử lý biểu tượng, toán học tượng trưng hoặc đại số tượng trưng, nhưng các thuật ngữ này, cũng đề cập đến thao tác phi tính toán, không còn được sử dụng trong đại số máy tính.

Cộng đồng khoa học

Hiện chưa có tổ chức khoa học nào được dành riêng cho đại số máy tính, nhưng chức năng này được đảm nhận bởi nhóm lợi ích đặc biệt của Hiệp hội Máy tính mang tên SIGSAM (Nhóm đặc biệt quan tâm về xử lý ký tự và đại số).^[1]

Có một số hội nghị thường niên về đại số máy tính, hàng đầu là ISSAC (Hội thảo quốc tế về tính toán tượng trưng và đại số), thường xuyên được SIGSAM tài trợ.^[2]${\displaystyle }$

Có một số tạp chí chuyên về đại số máy tính, trong đó tạp chí hàng đầu là Tạp chí tính toán tượng trưng được thành lập năm 1985 bởi Bruno Buchberger.^[3] Ngoài ra còn có một số tạp chí khác thường xuyên xuất bản các bài báo về đại số máy tính.^[4]

Lịch sử

Vào đầu đại số máy tính, khoảng năm 1970, khi các thuật toán được biết đến từ lâu lần đầu tiên được đưa vào máy tính, chúng hóa ra rất kém hiệu quả.^[5] Do đó, một phần lớn công việc của các nhà nghiên cứu trong lĩnh vực này bao gồm xem xét lại đại số cổ điển để làm cho nó hiệu quả và khám phá các thuật toán hiệu quả để thực hiện hiệu quả này. Một ví dụ điển hình của loại công việc này là tính toán của các ước số chung lớn nhất đa thức, được yêu cầu để đơn giản hóa các phân số. Đáng ngạc nhiên, thuật toán của Euclid cổ điển hóa ra không hiệu quả đối với đa thức trên các trường vô hạn, và do đó các thuật toán mới cần được phát triển. Điều tương tự cũng đúng với các thuật toán cổ điển từ đại số tuyến tính.

Về mặt khoa học máy tính

Biểu diễn dữ liệu

Bởi các phần mềm số có khả năng tính xấp xỉ giải tích số rất tốt nên trong đại số máy tính ta thường quan tâm nhất tới những cách tính toán chính xác biểu diễn của dữ liệu. Nếu có dữ liệu được biểu diễn chính xác, thì nó sẽ cho rằng kể cả khi kích cỡ của đầu ra nhỏ thì lượng dữ liệu trung gian được sinh ra vẫn có thể lớn tùy ý, không đoán được. Hành vi này được gọi là làm to biểu thức. Để giảm thiểu nó đi, nhiều phương pháp được dùng trong cách biểu diễn dữ liệu, cũng như trong các thuật toán xử lý chúng.

Các con số

Các hệ thống số thường được dùng trong giải tích số là số thực dấu phẩy động và các số nguyên với kích thước nhất định. Không có cái nào trong hai hệ thống này dễ dùng trong đại số máy tính do làm to biểu thức ^{[cần dẫn nguồn]}.

Thay vì đó, các con số căn bản được dùng trong đại số máy tính là các số nguyên của các nhà toán học, thường được biểu diễn bởi một dãy không giới hạn chữ số trong một số hệ cơ số, thường là cơ số lớn nhất cho bởi word. Các số nguyên này cho phép biểu diễn các số hữu tỉ hay phân số tối giản của hai số nguyên.

Lập trình để tính toán hiệu quả các phép tính toán số học là công việc rất khó, do đó hầu như mọi hệ thống đại số máy tính miễn phí và một số thương mại như phần mềm Mathematica và Maple đều dùng chung một tiêu chuẩn trong ngành: thư viện GMP.

Các biểu thức

Biểu diễn biểu thức (8-6)*(3+1) dưới dạng cây trong ngôn ngữ Lisp từ một bài luận năm 1985.^[6]

Trừ các con số và biến, mọi biểu thức toán học có thể được xem là ký tự của toán tử kèm theo sau đó là dãy là toán hạng. Trong phần mềm đại số máy tính, các biểu thức thường được biểu diễn theo cách này. Cách biểu diễn này rất linh hoạt và dù nhiều cái trông có vẻ không giống biểu diễn toán học khi mới thoạt nhìn, vẫn có thể được biểu diễn thành và xử lý như thường. Ví dụ như: phương trình thì là biểu thức có dấu “=” làm toán tử, một ma trận cũng có thể coi là biểu thức với từ "ma trận" làm toán tử và các hàng của nó làm các toán hạng.

Xem thêm

• Định lý tự động
• Bằng chứng hỗ trợ máy tính
• Hình học đại số tính toán
• Hệ thống đại số máy tính
• Kiểm tra bằng chứng
• Người kiểm tra mô hình
• Tính toán số-tượng trưng
• Mô phỏng tượng trưng

Tham khảo

1. Trang web chính thức của SIGSAM
2. Danh sách hội nghị SIGSAM
3. Cohen, Joel S. (2003). Computer Algebra and Symbolic Computation: Mathematical Methods. AK Peters, Ltd. tr. 14. ISBN 978-1-56881-159-8.
4. SIGSAM danh sách các tạp chí
5. Computer Algebra
6. Kevin G. Cassidy (tháng 12 năm 1985). The Feasibility of Automatic Storage Reclamation with Concurrent Program Execution in a LISP Environment (PDF) (Master's thesis). Naval Postgraduate School, Monterey/CA. Here: p.15

Đọc thêm

Đối với một định nghĩa chi tiết của chủ đề:

• Tính toán tượng trưng (Một biên tập), Bruno Buchberger, Tạp chí tính toán tượng trưng (1985) 1, trang.   1 Tiếng6.

Đối với sách giáo khoa dành cho chủ đề:

• Davenport, James H.; Siret, Yvon; Tournier, Èvelyne (1988). Computer algebra: systems and algorithms for algebraic computation. Translated from the French by A. Davenport and J.H. Davenport. Academic Press. ISBN 978-0-12-204230-0.
• von zur Gathen, Joachim; Gerhard, Jürgen (2003). Modern computer algebra . Cambridge University Press. ISBN 0-521-82646-2.
• Geddes, K. O.; Czapor, S. R.; Labahn, G. (1992). “Algorithms for Computer Algebra”. doi:10.1007/b102438. ISBN 978-0-7923-9259-0.
• Buchberger, Bruno; Collins, George Edwin; Loos, Rüdiger; Albrecht, Rudolf biên tập (1983). “Computer Algebra”. Computing Supplementa. 4. doi:10.1007/978-3-7091-7551-4. ISBN 978-3-211-81776-6.