AP Computer Science Principles (CSP) Study Guide / 备忘录

这是一个基于 AP CSP 五大核心概念 (Big Ideas) 的知识点总结与翻译。旨在帮助复习核心术语和逻辑。

提示：考试中所有的代码均为 Pseudocode (伪代码)，请特别注意列表索引是从 1 开始的，而不是 0。

目录 (Table of Contents)

1. Big Idea 1: Creative Development (创造性开发)
2. Big Idea 2: Data (数据)
3. Big Idea 3: Algorithms and Programming (算法与编程)
4. Big Idea 4: Computer Systems and Networks (计算机系统与网络)
5. Big Idea 5: Impact of Computing (计算的影响)

---

Big Idea 1: Creative Development

1. Collaboration (协作)

编程不仅仅是写代码，更是一个协作过程。

• Collaboration Styles: 可以在设计、编码、调试阶段进行。常见的有 Pair Programming (结对编程)（一人写代码，一人导航/检查）。
• Benefits: 减少错误、分享知识、产生更多样的解决方案、解决偏见 (Bias)。

2. Program Function vs. Purpose (功能与目的)

• Purpose: 为什么这个程序存在？它解决了什么问题？(The "Why")
• Function: 程序具体做了什么？它是如何运行的？(The "What" and "How")
• Input/Output: 程序接收的数据 (Input) 和产生的数据 (Output)。

3. Errors (错误类型) - 考试重点

在开发过程中，你会遇到三种主要错误：

错误类型	英文名称	定义	例子
语法错误	Syntax Error	违反了编程语言的规则（标点、拼写）。程序通常无法启动。	漏写分号、变量名拼写错误 (Displey vs Display)。
运行时错误	Runtime Error	程序可以启动，但在运行过程中崩溃。	Dividing by zero (除以0)、索引越界 (Index out of bounds)。
逻辑错误	Logic Error	程序可以运行且不崩溃，但产生错误的结果。	数学公式写错 (Area = 2 * r 而不是 r * r)、循环条件错误。
溢出错误	Overflow Error	数字太大，超出了计算机能存储的范围。	计算结果超出了整数类型的最大值。

---

Big Idea 2: Data

1. Binary Numbers (二进制)

计算机底层使用二进制 (Binary) 存储所有数据。

• Bit (比特): 最小的单位，只有 0 或 1。
• Byte (字节): 8 bits = 1 Byte。
• Abstraction (抽象): 数字、文字、颜色、声音最终都抽象为二进制。

2. Number Conversion (进制转换)

• Binary to Decimal: 记住位置权值 ($2^0=1, 2^1=2, 2^2=4, 2^3=8...$).
  • Example: 1101 = $18 + 14 + 02 + 11 = 13$.
• Decimal to Binary: 找到小于该数字的最大2的幂次方进行相减。

3. Data Representation (数据表示)

• Digital Images: 由 Pixels (像素) 组成。
• Metadata (元数据): "Data about data"（关于数据的数据）。例如：图片的长宽、拍摄时间、GPS位置。没有 Metadata，计算机不知道如何解析二进制流。
• Sampling (采样): 将 Analog (模拟信号，连续的) 转换为 Digital (数字信号，离散的) 的过程。
  • 采样率越高，还原度越高，文件越大。

4. Data Compression (数据压缩)

压缩类型	英文名称	特点	适用场景
无损压缩	Lossless Compression	数据被压缩后可以完美还原，不丢失任何信息。	文本文件、可执行程序、重要数据。
有损压缩	Lossy Compression	为了追求更小的文件体积，永久丢弃部分细节，无法还原到原始状态。	图片 (JPEG)、音频 (MP3)、视频。人眼/人耳通常难以察觉丢失的部分。

---

Big Idea 3: Algorithms and Programming

1. Variables & Assignments (变量与赋值)

• Assignment Operator (<-): 赋值符号。a <- 5 意味着把 5 存入 a。
• Data Types:
  • String: 文本，用引号包裹 "Hello".
  • Boolean: 只有 true 或 false.
  • List (Array): 列表。注意：AP CSP 伪代码中，List 的索引 (Index) 从 1 开始！ (Index starts at 1)。

2. Algorithm Control Structures (控制结构)

所有算法都由这三种基本结构组成：

1. Sequence (顺序): 代码按顺序一行行执行。
2. Selection (选择/条件): IF, IF-ELSE。根据 Boolean Condition 决定执行哪部分。
3. Iteration (迭代/循环): REPEAT n TIMES, REPEAT UNTIL, FOR EACH.

3. Lists and Traversal (列表与遍历)

• Traversing: 使用循环访问列表中的每一个元素。
• Common Algorithms:
  • 查找最大/最小值 (Linear search for max/min).
  • 计算平均值 (Sum / Length).
  • 过滤数据 (创建一个新列表，只存符合条件的元素).

4. Searching Algorithms (搜索算法)

算法	英文名称	条件	效率
线性搜索	Linear Search	数据可以是无序的。	慢。从头查到尾。最差情况需要查 N 次。
二分搜索	Binary Search	数据必须是排序好 (Sorted) 的。	快。每次排除一半数据。("Divide and Conquer")。

5. Procedures (过程/函数)

• Procedure: 一段被命名的代码块，可以重复使用。
• Parameters (参数): 定义过程时使用的变量（占位符）。
• Arguments (实参): 调用过程时传入的实际数值。
• Procedural Abstraction: 你不需要知道函数内部怎么写的，只需要知道它做什么以及怎么调用它。

6. Algorithm Efficiency (算法效率)

• Efficiency: 这里的效率通常指运行时间随数据量增长的变化趋势。
• Polynomial Time (多项式时间): 运行时间是合理的 (Reasonable)。例如: $N, N^2, N^3$。
• Exponential Time (指数时间): 运行时间增长极快，被认为是不合理 (Unreasonable) 的。例如: $2^N, N!$。当输入数据变大时，现代计算机也算不出来。
• Heuristic (启发式算法): 当找不到完美解（或完美解太慢）时，使用一种“足够好”的近似解法。

7. Undecidable Problems (不可判定问题)

• Undecidable Problem: 没有任何算法能对所有可能的输入都给出正确的 Yes/No 回答。
• 经典例子：Halting Problem (停机问题)。

---

Big Idea 4: Computer Systems and Networks

1. The Internet (互联网)

• Internet: 网络的网络 (Network of networks)。硬件驱动。
• Protocol (协议): 一套大家都遵守的规则标准。
• Open Standard: 互联网协议是公开的，允许不同设备互联。

2. Data Transmission (数据传输)

• Packet Switching (分组交换): 数据被切分成小包 (Packets) 发送。包可能走不同的路径，到达后重新组装。
• Router (路由器): 决定数据包路径的设备。
• Path: 从发送者到接收者经过的一系列路由器。

3. Protocols (核心协议)

• IP (Internet Protocol): 给每个设备一个地址 (IP Address)。负责寻址。
  • IPv4 (32-bit, 旧), IPv6 (128-bit, 新，解决地址耗尽)。
• TCP (Transmission Control Protocol): 可靠传输。负责建立连接、检查丢包、重传、排序。
• UDP (User Datagram Protocol): 快速但不可靠。不检查丢包。用于视频直播、在线游戏。
• HTTP/HTTPS: 网页传输协议。
• DNS (Domain Name System): 将域名 (www.google.com) 翻译成 IP 地址。

4. System Properties (系统特性)

• Bandwidth (带宽): 单位时间内能传输的最大数据量 (bit/s)。
• Latency (延迟): 数据从源头到目的地所需的时间 (ms)。
• Scalability (可扩展性): 系统在工作量增加时，能否通过增加资源来维持性能。
• Fault Tolerance (容错性): 当部分系统（如某个路由器或线路）坏掉时，整个系统依然能工作。
  • 实现方式：Redundancy (冗余)，即拥有多条路径或备份。

5. Parallel & Distributed Computing (并行与分布式计算)

• Sequential Computing: 按顺序一个接一个做。
• Parallel Computing: 一个程序被分成小部分，在多个处理器上同时运行。
  • Speedup (加速比) = 顺序执行时间 / 并行执行时间。
  • 受限于那部分必须按顺序执行的代码。
• Distributed Computing: 利用多台计算机（联网）共同解决一个巨大问题。

---

Big Idea 5: Impact of Computing

1. Digital Divide (数字鸿沟)

• 不同人群（地域、年龄、收入）在接触和使用计算机技术上的差距。影响信息获取和教育机会。

2. Legal & Ethical Issues (法律与伦理)

• Intellectual Property (知识产权): 代码、图片等创作受版权保护。
• Creative Commons (CC 许可): 创作者允许他人免费使用、分享或修改其作品的一种公共版权许可（通常要求署名）。
• Open Source (开源): 源代码公开，允许任何人查看、修改和分发。
• Open Access (开放获取): 研究数据或论文免费对公众开放。

3. Privacy & PII (隐私)

• PII (Personally Identifiable Information): 能识别个人身份的信息（社保号、位置、邮箱、医疗记录）。
• Cookie: 网站存储在本地的小文件，用于跟踪用户行为。
• Data Mining (数据挖掘): 在大数据中发现模式，可能导致隐私泄露。

4. Security (安全) - 考试高频

• Phishing (网络钓鱼): 伪装成合法邮件/网站骗取密码。
• Keylogging (键盘记录): 恶意软件记录你的按键来窃取密码。
• Malware (恶意软件): 病毒、勒索软件等。
• DDoS (分布式拒绝服务攻击): 利用大量僵尸网络(Botnet)瞬间访问服务器，使其瘫痪。

5. Encryption (加密)

• Symmetric Encryption (对称加密): 加密和解密使用同一个密钥 (Key)。缺点是密钥传输不安全。
• Public Key Encryption (公开密钥加密/非对称加密):
  • Public Key: 公开，用于加密。
  • Private Key: 私有，用于解密。
  • 这是 HTTPS 和现代互联网安全的基石。

6. Crowdsourcing (众包)

• 利用互联网上大量用户的力量来收集数据、解决问题或筹集资金 (Kickstarter, Waze, Wikipedia)。
• Citizen Science: 普通人协助科学家收集数据。

7. Bias (偏见)

• Algorithmic Bias: 并非算法本身有偏见，而是训练数据 (Data) 或开发者的偏见导致算法对某些群体不公平（如面部识别对某些肤色识别率低）。