计算机科学原理

基础、算法、系统、数据与负责任的工程实践

计算机科学研究信息、计算、抽象以及支撑计算应用的工程系统。它不只是编程技巧，而是连接数学推理、算法设计、计算机体系结构、操作系统、网络、数据管理和社会影响的综合学科。

本文强调具有长期价值的原则，而不是某一种语言或厂商平台。每个主题围绕问题、模型、权衡和验证方法展开，适合作为学习和工程讨论的参考资料。

图1：上层应用依赖底层表示和机制，层次化抽象有助于管理复杂度。

概念	核心问题	典型表示	重要性
信息	什么可以被编码？	比特、符号、数据类型	让存储和通信更加精确。
计算	输入如何经过步骤变成输出？	算法、程序、机器	定义可重复的问题求解。
抽象	哪些细节可以隐藏？	接口、层次、模块	控制复杂度并支持复用。
证据	如何信任一个结果？	证明、测试、不变量	区分可靠结果与猜测。

表1：连接计算机科学各领域的四个核心思想。

1. 计算机科学研究什么

计算机科学研究处理信息的过程。过程可以由人、物理电路、顺序程序、分布式服务或它们的组合来执行。共同点是对状态、允许的操作以及结果何时算作正确建立清晰模型。

问题描述输入与输出应满足的关系；实现则选择算法、数据表示、编程语言和执行环境。分离这些层次，可以在不改变目标行为的情况下替换实现。

1.1 模型、表示与抽象

• 表示把现实对象或概念映射为机器可以存储和处理的符号。
• 抽象暴露必要行为，同时隐藏调用者不需要了解的实现细节。
• 规格说明描述必须满足什么；实现说明如何实现。
• 不变量是每个合法计算步骤都会保持的性质。

抽象可以减少同时需要考虑的细节，但隐藏的假设可能在接口处失效。因此，良好工程需要用明确契约、测试和可观测性来配合抽象。

1.2 把正确性作为工程纪律

数学证明可以说明普遍性质，测试可以验证代表性行为，测量可以量化资源，监控可以发现生产环境中的假设是否仍然成立。这些证据相互补充，不能互相完全替代。

证据类型	适用对象	示例	局限
证明	普遍性质	用循环不变量证明排序	需要精确模型。
测试	具体行为	边界和随机测试	不能覆盖所有输入。
测量	性能	延迟和内存	依赖工作负载。
监控	运行状态	错误率和饱和度	通常部署后发现症状。

表2：建立系统可信度时需要结合的证据类型。

2. 算法与复杂度

算法是把输入转换为输出的有限、有效过程。设计算法从精确定义开始，选择表示和策略，最后分析正确性与资源。对于同一个任务，许多算法都可能正确，但输入规模增加后表现差异很大。

图2：输入规模增加时，复杂度类别可能主导实际性能。

2.1 分解与算法设计范式

分治法求解相互独立的子问题并合并结果；动态规划保存重叠子问题；只有当证明连接局部选择与全局最优时才能安全使用贪心法；随机化算法利用概率改善平均性能或规避对抗性输入。

范式	主要思想	优势	风险
蛮力法	枚举可能性	简单、适合作为基线	可能产生指数级开销。
分治法	拆分、求解、合并	常得到高效递推	可能重复计算。
贪心法	选择局部最优	速度快、实现紧凑	可能错过全局最优。
动态规划	复用重叠子问题	避免重复计算	状态设计较难。
随机化算法	使用受控随机性	平均性能好	需要概率性保证。

表3：常见算法范式，以及安全使用它们所需的推理。

2.2 复杂度不只是大O标签

渐进记号描述规模增长趋势，但常数、局部性、并行性、输入分布、缓存和输入输出也会影响实际性能。严谨分析应说明模型假设、测量资源和评估工作负载。

• 最坏情况分析支持需要可预测性的服务。
• 当输入分布明确时，平均情况分析可能有用。
• 摊还分析解释一系列操作中偶发的昂贵操作。
• 在现代机器上，空间和数据搬运有时比算术次数更关键。

3. 数据结构与信息组织

数据结构决定搜索、插入、删除、遍历和更新的效率。选择表示方式就是算法设计：它会让某些操作便宜，让另一些操作昂贵。

图3：树强调层次关系，图可以表示一般关系。

3.1 基本数据结构

• 数组支持索引访问并具有良好局部性，但中间插入可能需要移动元素。
• 链表便于局部插入，但指针跳转可能降低局部性。
• 栈和队列表达访问顺序，常用于解析、调度、搜索和事件处理。
• 哈希表在适当假设下提供期望常数时间查找，但冲突处理和扩容需要谨慎。
• 树和图表达层次、依赖、可达性、路由以及网络关系。

3.2 数据建模与不变量

有效数据结构需要不变量。例如，搜索树不变量描述左右子树键的顺序；队列不变量保持先进先出。不变量能够指导实现、测试和部分失败后的恢复。

结构	典型操作	期望代价	设计注意事项
数组	按索引访问	O(1)	局部性好，扩容可能复制。
哈希表	按键查找	期望 O(1)	依赖哈希函数和负载因子。
平衡树	有序查找	O(log n)	更新时维护平衡。
堆	最小/最大值	查看 O(1)，更新 O(log n)	适合优先级调度。
图	可达性	取决于表示和算法	明确方向和权重。

表4：代表性数据结构及其性能假设。

4. 计算机组成与体系结构

计算机体系结构解释指令、数据和控制信号如何在机器中移动。布尔运算和状态构成逻辑基础；流水线、缓存、分支预测、向量单元和多核执行提高吞吐量，同时引入时序和一致性问题。

图4：表示、分解、计算、验证和沟通构成完整计算工作流。

4.1 存储程序模型

存储程序思想把指令视为可以存储、取出、译码和执行的数据。处理器不断更新寄存器、内存和控制状态。现代实现通过缓存、投机执行、并行执行和专用加速器优化这一过程。

4.2 性能与存储层次

算术运算不一定是瓶颈。处理器可能等待数据从内存、存储设备或另一台机器传来。存储层次把频繁使用的数据放在靠近执行单元的位置，从而降低有效延迟。时间局部性和空间局部性是性能工程的重要原则。

层次	职责	机制	权衡
逻辑	表示并变换数值	布尔代数、数字电路	表达能力与成本。
体系结构	执行指令并搬运数据	CPU、缓存、内存	延迟与吞吐量。
操作系统	管理资源并提供隔离	进程、文件、虚拟内存	便利性与开销。
网络	在端点间传递信息	协议、路由	可靠性与速度。
应用	解决领域问题	服务与界面	功能与维护成本。

表5：系统层次提供不同抽象，也带来不同性能权衡。

• 延迟是完成一次操作的时间；吞吐量是单位时间完成的工作量。
• 只有在依赖、同步和数据搬运受控时，并行性才能提升吞吐量。
• 能耗、散热和可靠性都是性能工程的一部分。

5. 操作系统、网络与分布式系统

操作系统围绕硬件资源提供抽象和保护。进程与线程组织执行；虚拟内存提供隔离和方便的地址空间；文件和设备支持持久化及外部交互。操作系统需要平衡公平性、性能、故障隔离和兼容性。

网络把问题扩展到多台机器。通信会受到延迟、丢失、乱序、重复、拥塞和部分故障影响。分布式系统还面临不存在单一瞬时全局状态视图的困难。

5.1 分布式系统原则

• 面向故障设计，假设机器、链路、进程和依赖可能独立故障。
• 显式管理所有权、复制、一致性和恢复流程。
• 区分安全性（坏事不会发生）和活性（好事最终会发生）。
• 使用幂等操作和稳定标识，使重试更加安全。
• 通过链路追踪、指标、日志和用户可见结果度量系统。

机制	目的	典型保证	局限
进程隔离	防止任务互相破坏	独立地址空间和权限	切换与通信开销。
虚拟内存	提供受保护内存	隔离和按需分页	转换和缺页开销。
复制	提升可用性或吞吐量	多个状态副本	一致性协调复杂。
事务	组织相关更新	原子性和恢复	锁、日志或协调开销。

表6：把不可靠资源转化为可用抽象的典型机制。

6. 编程语言、数据与智能系统

编程语言提供符号、抽象和规则，把人的意图转换成可执行行为。类型系统可以在执行前阻止一类错误；内存模型控制生命周期；并发原语协调独立活动；模块为协作提供边界。

图5：输入、处理状态和输出的简化模型强调数据流与契约。

6.1 数据作为计算资源

数据质量不仅取决于准确性，还取决于来源、覆盖范围、时效性、表示方式和访问控制。数据库提供维护一致性和查询信息的结构化方法。机器学习系统从样本中推断模式，因此必须在分布变化、不确定性和目标变化下进行评估。

6.2 可复现性与可维护性

当其他工程师能够复现、检查和扩展一个结果时，该结果价值更高。可复现性需要版本化代码和数据、声明依赖、记录随机性、清晰评估协议和充分上下文。可维护性依赖易读接口、小范围变更、自动化测试和主动移除过时复杂度。

实践	回答的问题	有用产物
版本控制	改了什么，为什么？	历史和评审记录
自动化测试	预期行为仍成立吗？	单元、集成和性质测试
基准测试	性能如何变化？	可重复工作负载和报告
文档	应该怎样使用？	规格说明和示例
可观测性	生产中发生什么？	日志、指标、追踪和告警

表7：把一次性程序发展为工程系统的实践。

7. 安全、伦理与社会环境

计算机科学应用于机构和社会，因此技术质量不仅是功能正确，还包括系统之外的影响。系统可能速度快、准确率高，却仍会泄露隐私、放大不公平、消耗过多资源或形成不安全激励。

问题	技术表现	工程响应	评估问题
隐私	收集或推断个人数据	减少数据并控制访问	能否用更少数据？
安全	对抗输入或未授权行为	威胁建模与纵深防御	假设失效怎么办？
公平	错误或机会不均	比较不同条件下的结果	谁承担错误成本？
可持续性	能源与硬件消耗	优化生命周期效率	收益是否值得投入？

表8：技术设计选择及其更广泛后果需要一起评估。

7.1 威胁建模与纵深防御

安全工作从识别资产、行为者、信任边界、攻击面和故障模式开始。纵深防御结合最小权限、安全默认值、输入校验、隔离、加密、补丁、监控、恢复和用户教育。不应假设某一个控制措施永远完美。

7.2 负责任的问题求解

• 明确目标用户、受影响但不直接使用系统的人群以及系统边界。
• 在相关条件下比较错误和收益，不只报告总体平均值。
• 对影响重大的决策设计申诉、纠正、回滚和人工监督。
• 考虑采购、能源、维护、退役和处置等全生命周期影响。

8. 学习与工程实践清单

面对新问题时，应先提出精确问题并建立小模型。定义输入、输出、约束和成功标准；选择突出关键操作的表示；在优化前设计基线；通过证明或测试验证基本性质；测量资源并记录假设。最后检查当输入、依赖或用户不同于原始计划时系统如何表现。

步骤	行动	产物
1	澄清问题和约束	规格说明与假设
2	选择表示和接口	数据模型与接口契约
3	设计基线算法	正确参考实现
4	分析复杂度和风险	资源模型与威胁模型
5	用证明、测试和测量验证	证据报告
6	部署、观测并改进	运行反馈闭环

表9：把问题陈述转化为可信计算解决方案的可重复工作流。