Tin học lý thuyết

Tin học lý thuyết là tập hợp các chủ đề của khoa học máy tính tập trung vào các khía cạnh toán học trừu tượng của tính toán, chẳng hạn như lý thuyết tính toán (theory of computation), phân tích thuật toán (analysis of algorithms) và ngữ nghĩa của ngôn ngữ lập trình. Tuy bản thân tin học lý thuyết không phải là một chủ đề đơn nhưng các nhà nghiên cứu ngành này lập thành một nhóm con giữa các nhà nghiên cứu khoa học máy tính.

Phạm vi

Khó có thể khoanh vùng các lĩnh vực lý thuyết một cách chính xác; Nhóm nghiên cứu đặc biệt về thuật toán và lý thuyết tính toán của tổ chức ACM nói rằng:

"Lĩnh vực tin học lý thuyết được hiểu theo nghĩa rộng để bao hàm các thuật toán, cấu trúc dữ liệu, lý thuyết độ phức tạp tính toán, tính toán phân tán, tính toán song song, VLSI, học máy, sinh học tính toán (computational biology), địa lý tính toán (computational geometry, lý thuyết thông tin (information theory), mật mã học, tính toán lượng tử (quantum computation), đại số và lý thuyết số tính toán, kiểm định và ngữ nghĩa chương trình, lý thuyết ô-tô-mát (automata theory), và nghiên cứu về tính ngẫu nhiên (study of randomness). Các công trình trong lĩnh vực này thường được phân biệt với các lĩnh vực khác bởi nhấn mạnh vào kỹ thuật và tính chặt chẽ toán học."

Các tổ chức

• EATCS, the European Association for Theoretical Computer Science - Hội Tin học Lý thuyết châu Âu
• SIGACT
• Dutch Association for Theoretical Computer Science [1] - Hội Tin học Lý thuyết Hà Lan

Tạp chí

• Information and Computation
• Theory of Computing (open access journal)
• Formal Aspects of Computing
• Journal of the ACM
• SIAM Journal on Computing
• SIGACT News
• Theoretical Computer Science
• Theory of Computings Sytems^{[liên kết hỏng]}
• Chicago Journal of Theoretical Computer Science

Hội thảo

• Annual ACM Symposium on the Theory of Computing (STOC)
• IEEE Symposium on Foundations of Computer Science (FOCS)
• Symposium on Discrete Algorithms (SODA)
• International Colloquium on Automata, Languages and Programming (ICALP)
• Symposium on Theoretical Aspects of Computer Science (STACS)
• European Symposium on Algorithms (ESA)
• Algebraic Methodology And Software Technology (AMAST)
• IEEE Symposium on Logic in Computer Science (LICS)
• International Symposium on Algorithms and Computation(ISAAC)
• (APPROX/RANDOM)
• Computational Complexity Conference (CCC)
• Symposium on Parallelism in Algorithms and Architectures (SPAA)
• Computability in Europe (CiE)

Xem thêm

• Khoa học hình thức (Formal science)

Tham khảo

• SIGACT home page
• Challenges for Theoretical Computer Science, draft of 2000 Lưu trữ 2009-02-22 tại Wayback Machine

Liên kết ngoài

• SIGACT directory of additional theory links
• Usenet comp.theory