计算理论 主条目:计算理论 按照Peter J. Denning的说法,计算机科学的最根本问题是“什么能够被有效地自动化?”计算理论的研究就是专注于回答这个根本问题,关于什么能够被计算,去实施这些计算又需要用到多少资源。为了试图回答第一个问题,递归论检验在多种理论计算模型中哪个计算问题是可解的。而计算复杂性理论则被用于回答第二个问题,研究解决一个不同目的的计算问题的时间与空间消耗。
信息编码论 主条目:信息论和编码理论 信息论与信息量化相关,由Claude E. Shannon创建,用于寻找信号处理操作的根本极限,比如压缩数据和可靠的数据存储与通讯。编码理论是对编码以及它们适用的特定应用性质的研究。编码(code)被用于数据压缩,密码学,前向纠错,也被用于网络编码。研究编码的目的在于设计更高效、可靠的数据传输方法。