概述

计算机科学（MSC 68）研究算法、计算模型与信息处理。其数学基础由图灵（1936 年图灵机模型）、丘奇（λ 演算）与哥德尔奠定，回答了”什么是可计算的”。在此之上，计算复杂度理论（Cook 1971 年提出 NP 完全性，Karp 1972 年扩展）刻画了问题求解的资源代价，P 与 NP 问题成为核心未解难题。

主要方向包括：算法设计与分析（分治、动态规划、随机化），数据结构，形式语言与自动机，以及计算几何与密码学的数学基础。它与数理逻辑（可判定性、证明论）、信息论（编码与通信）及数值分析（科学计算）深度交织。

计算机科学既是工程学科也是数学分支：其定理（如停机问题不可判定、信息论信道容量）具有严格的数学形态，而算法复杂度则指导着从数据库到人工智能的几乎所有计算实践。