计算机科学速成课程的授课老师是英国树莓派基金会教育部长Carrie Anne，她以入门级大学教材和 AP 计算机科学原理指南为基础，在短短40节课中概述了计算机的历史、设计决策、编程和软件的基本要素、硬件的基本组件及其作用，对新手小白可以说是非常友好了。以下为我在学习过程中所做的笔记，可供参考。

一、计算机的早期历史和电子计算机

最早的计算设备是算盘，其次是步进计算器，差分机，分析机，打孔卡片制表机。步进计算器是第一个可以做加减乘除的机器，Charles Babbage 提出了“差分机”，在构造差分机期间，想出了分析机, 分析机是通用计算机。

Ada Lovelace 给分析机写了假想程序，因此成为了第一位程序员，后来 Herman Hollerith 的打孔卡片制表机又大大提升了人口普查效率。

电子计算机组成核心最初由继电器组成。继电器一秒最多 50 次开关，bug 原指继电器上的虫子。

IBM 于 1944 年制造哈佛 Mark I。1904 年，热电子管出现成为第一个真空管。改进后和继电器的功能一样，”巨人 1 号” 计算机在英国布莱切利园首次大规模使用真空管，但编程麻烦，还要配置。1946 年，宾夕法尼亚大学的 ENIAC 是第一个通用可编程计算机。1947 年，贝尔实验室做出了晶体管，晶体管有诸多好处，IBM 很快全面转向晶体管。

当时，很多晶体管和半导体的开发都是硅谷做的。而生产半导体最常见的材料是硅，著名的有肖克利半导体、仙童半导体和英特尔。

二、布尔逻辑、逻辑门和二进制

George Boole 提出布尔逻辑（真假），也称 Boolean Algebra。基本操作有：NOT，AND，OR，以及异或 XOR。

存储单位有 MB（Megabyte），GB（Gigabyte），TB（Terabyte），树型单位有正数、负数、整数、浮点数。

美国信息交换标准代码 ASCII：用来表示字符。1992 年诞生 UNICODE，16 位，是字符编码标准，解决 ASCII 不够表达所有语言的问题。

三、算数逻辑单元（ALU）

ALU（Arithmetic and Logic Unit）有 2 个单元，1 个算术单元和 1 个逻辑单元。

算术单元分为半加器 （处理 1 个 bit，2 个输入）和全加器（处理 1 个 bit，3 个输入），8 bit 加法就包括（1 个半加器，7 个全加器），溢出为 Overflow。

逻辑单元是检测数字是否为 0 的电路（一堆 OR 门最后加个 NOT 门）。

8 位 ALU 抽象成一个 V 符号。

Flag 标志判断是否相等，是否小于，是否溢出等。

最早的处理器为英特尔 74181。

四、寄存器和内存

Memory 有存储、内存两种含义：Gated Latch（锁存器）存 1 位字节，Register（寄存器）存 8 位，16x16 的矩阵存 256 位，Opcode 操作码。

数据选择器/多路复用器 （Multiplexer）用来解码 8 位地址（4 位代表行，4 位代表列），定位到单个锁存器，组合 256 位内存 + 多路复用器 Multiplexer。

可寻址的 256 字节内存：8 个模块，每个模块有 32 个小方块，每个小方块有 4 个小块，每个小块是 128 位 x 64 位。

一条 1980 年代的内存有 1M 大小。

五、中央处理器（CPU）以及指令和程序

Instruction Register、Instruction Address Register。

RAM + 寄存器 + ALU = CPU。

取指令 → 解释 → 执行循环。

时钟 clock：时钟速度和赫兹，超频提升性能, 降频省电。

”指令集”，LOAD_A，LOAD_B，SUB，JUMP，ADD，HALT 等指令，带条件跳转：JUMP NEGATIVE 是负数才跳转，还有其他类型的 JUMP。

真正现代 CPU 用更多指令集。位数更长，1971 年的英特尔 4004 处理器，有 46 个指令，如今英特尔酷睿 i7, 有上千条指令。CPU 发展早期是加快晶体管切换速度，来提升 CPU 速度，现在给 CPU 专门的除法电路 + 其他电路来做复杂操作，比如游戏，视频解码，或是给 CPU 加缓存，提高数据存取速度，更快喂给 CPU。

专有名词：脏位（Dirty bit）、流水线设计（pipeline）、并行处理（parallelize）、乱序执行（out-of-order execution）、推测执行（speculative execution）、分支预测（branch prediction）。

多个 ALU 组成多核放大为多个独立 CPU 放大为超级计算机（中国的神威太湖之光）。

六、编程语言发展史

早期的编程发展从纺织业开始，给机器编程的需求远在计算机出现前就有了，于是有了打孔纸卡（Punched card）和插线板（Plugboard）。

冯诺依曼架构（Von Neumann Architecture）是编程的鼻祖，在这之上演变出面板编程（Panel programming）。第一款取得商业成功的家用计算机是 Altair 8800。

二进制写程序，先纸上写伪代码，手工转二进制，很快就烦了，于是用助记符（mnemonic）写代码（LOAD_A 14），为了把助记符转二进制，汇编器（Assembler）诞生。

Grace Hopper 设计了编程语言 A-0，并在 1952 年做了第一个编译器（Compiler），实现 A-0。IBM 在 1957 年开发出 FORTRAN，随后 COBOL（Common Business-Oriented Language）诞生。

1960 年代：ALGOL，LISP，BASIC。

1970 年代：Pascal，C，Smalltalk。

1980 年代：C++，Objective-C，Perl。

1990 年代：Python，Ruby，Java。

New millennium：Swift，C#，Go。

七、函数、算法和数据结构

最经典的是 Grace Hopper 拍虫子游戏。

专有名词：变量、赋值语句、if 判断、while 循环、for 循环、函数。

最简单的算法有：选择排序（Selection sort O(n^2)）、归并排序（Merge sort O(n log n)）、Dijkstra 算法（（graph search algorithms） O(n log n +1)）。

大 O 表示法（Big O notation）用来表示算法复杂度。

数据结构要点：数组（Array）、下标（Index）、字符串（String）、矩阵（Matrix）、结构体（Struct）、指针（Pointer）、节点（Node）、链表（Linked List）。

队列（Queue）(First in first out)，栈（Stack）(Last in first out) push、pop。

不同数据结构适用不同场景：树（Tree）root/ leaf nodes，二叉树（Binary Tree），图（Graph），红黑树和堆。

八、阿兰·图灵

阿兰·图灵生于 1912，是计算机之父，他首先提出可判定性问题（Entscheidungs problem）和停机问题，阿隆佐·丘奇研究 Lambda 算子。图灵机是计算机的蓝本而 Bombe 则破解了德军英格玛加密机。

图灵测试和图灵奖。

九、软件工程

对象（Object）以及面向对象编程（Object Oriented Programming）。

API（Application Programming Interface）和集成开发环境 IDE（Integrated Development Environments）。

其他专有名词：调试（debugging），文档和注释（readme, comment）版本控制（Version control）质量控制（Quality Assurance testing，QA）。

十、集成电路与摩尔定律

晶圆的制作：光刻（Photolithography）、晶圆（Wafer）、光刻胶（Photoresist）、光掩膜（Photomask）、掺杂（Doping）、分立元件（Discrete components）。

数字暴政（Tyranny of Numbers）是 1960 年代工程师碰到的问题（如果想加强电脑性能，就要更多部件，这导致更多线路，更复杂。所以很难做）。

摩尔定律 Moore’s Law。晶体管数量大幅度增长, 1980 年三万个，1990 年一百万个，2000 年三千万个，2010 年十亿个，进一步小型化会碰到 2 个问题：1、光的波长不足以制作更精细的设计，2、量子隧穿效应。

十一、操作系统

操作系统（Operating systems）：计算机变便宜变多，有不同配置，写程序处理不同硬件细节很痛苦，因此操作系统负责抽象硬件。

专有名词：批处理（Batch processing）、外部设备（Peripherals）、设备驱动程序（Device drivers）、多任务处理（Multitasking）、虚拟内存（Virtual Memory）、动态内存分配（Dynamic memory allocation）、内存保护（Memory Protection）。

1970 年代，计算机足够便宜，大学买了让学生用，多个学生用多个 “终端” 连接到主机。

多用户分时操作系统，Multics、Unix、MS-DOS。

十二、内存和文件

存储技术的发展，首先是纸卡（Paper punch cards），随后发展为延迟线存储器（Delay Line Memory）、磁芯（Magnetic Core Memory）、磁带（Magnetic Tape）、磁鼓（Magnetic Drum Memory）。

硬盘（Hard Disk Drives）有内存层次结构（Memory Hierarchy）。

软盘（Floppy Disk）、光盘（Compact Disk）、固态硬盘（Solid State Drives）。

文件格式：可以随便存文件数据，但按格式存会更方便。

• TXT 文本文件：ASCII。
• WAV 音频文件：每秒上千次的音频采样数字。
• BMP 图片文件：像素的红绿蓝 RGB 值。

文件系统：很早期时空间小，整个存储器就像一整个文件。后来随容量增长，多文件非常必要。

目录文件：用来解决多文件问题，存其他文件的信息，比如开头，结尾，创建时间等。

平面文件系统（Flat File System）：文件都在同一个层次，早期空间小，只有十几个文件，平面系统够用，如果文件紧密的一个个前后排序会造成问题，所以文件系统会： 1. 把空间划分成一块块 2. 文件拆分存在多个块里，文件的增删改查会不可避免的造成文件散落在各个块里，如果是磁带这样的存储介质就会造成问题，所以做碎片整理。

分层文件系统（Hierarchical File System）：有不同文件夹，文件夹可以层层嵌套。

压缩的好处是能存更多文件，传输也更快。

无损压缩（Lossless compression）：游程编码（Run-Length Encoding）和字典编码（Dictionary coders）。

霍夫曼树 Huffman Tree、消除冗余和用更紧凑的表示方法，这些方法通常会组合使用。

感知编码（Perceptual coding）、有损压缩，如 jpeg 格式、时间冗余（Temporal redundancy）、MPEG-4 视频编码。

十三、命令行界面与 图形用户界面（GUI）

最早计算机程序从运行开始直到结束，中间没有人类进行操作，原因是计算机很贵，不能等人类慢慢输入，执行完结果打印到纸上，到 1950 年代，计算机足够便宜+快，人类和计算机交互式操作变得可行，为了让人类输入到计算机，改造之前就有的打字机，变成电传打字机，到 1970 年代末，屏幕成本足够低，屏幕代替电传打字机，屏幕成为标配。

人机交互（Human-Computer Interaction）：早期输出数据是打印到纸上，而输入是用纸卡/纸带一次性把程序和数据都给进去。

克里斯托弗·莱瑟姆·肖尔斯于 1868 年发明 QWERTY 打字机，随后诞生电传打字机（Teletype machine），输入指令打印在纸上，电脑会将返回指令打印在纸上完成交互。

命令行界面（Command line interface）：ls 命令、cd 命令、早期文字游戏 Zork（1977 年）。

图形界面先驱：道格拉斯·恩格尔巴特（Douglas Engelbart），施乐公司则在 1970 年成立 帕洛阿尔托研究中心（Palo Alto Research Center），1973 年完成 Xerox Alto 计算机。

1981 年的 Xerox Star system，史蒂夫·乔布斯去施乐参观，所见即所得 WYSIWYG，1983 年推出 Apple Lisa，1984 年推出 Macintosh。

微软则在 1985 年推出 Windows 1.0，之后出到 3.1，1995 年推出 Windows 95 提供图形界面，1995 年微软失败的 Microsoft Bob。

十四、冷战、消费主义和个人计算机发展

范内瓦·布什预见了计算机的潜力，提出假想机器 Memex，帮助建立国家科学基金会，给科学研究提供资金。

1950 年代消费者开始买晶体管设备，收音机大卖，日本取得晶体管授权后，索尼做了晶体管收音机，为日本半导体行业崛起埋下种子。

苏联 1961 年把宇航员加加林送上太空，导致美国提出登月，NASA 预算大大增加，用集成电路来制作登月计算机，集成电路的发展实际上是由军事应用大大推进的，阿波罗登月毕竟只有 17 次，美国造超级计算机进一步推进集成电路。

美国半导体行业一开始靠政府高利润合同活着，忽略消费者市场，1970 年代冷战渐消，行业开始衰败，很多公司倒闭，英特尔转型处理器，政府和消费者推动了计算机的发展，早期靠政府资金，让技术发展到足够商用，然后消费者购买商用产品继续推动产品发展。

1970 年代初成本下降，个人计算机变得可行，Altair 8800 大卖。比尔·盖茨和保罗·艾伦写了 BASIC 解释器，乔布斯提议卖组装好的计算机，Apple-I 诞生。1977 年出现 3 款开箱即用计算机：Apple-II、TRS-80 Model I、Commodore PET 2001。

IBM 意识到个人计算机市场，IBM PC 发布，采用开放架构，兼容的机器都叫 IBM Compatible（IBM 兼容），生态系统产生雪球效应：因为用户多，软硬件开发人员更愿意花精力在这个平台，因为软硬件多，用户也更乐意买 “IBM 兼容” 的计算机。苹果选封闭架构，一切都自己来，只有苹果在非 “IBM 兼容” 下保持了足够市场份额。

十五、2D 图形和3D 图形显示

屏幕对于临时值的表现比纸张打印好太多，所以人们把键盘和显示器分开，屏幕显示临时值。（PDP-1 计算机）。

阴极射线管（Cathode Ray Tube(CRT)），有两种绘图方式：1、矢量扫描（Vector Scanning），2、光栅扫描（Raster Scanning）。

其他显示有关：液晶显示器（Liquid Crystal Displays (LCD)）、像素（Pixel））、字符生成器（Character generator）、屏幕缓冲区（Screen buffer）、矢量命令画图、Sketchpad、光笔（Light pen）、函数画线、矩形。

3D 投影包括：线框渲染（Wireframe Rendering）、正交投影（Orthographic Projection）、透视投射（Perspective Projection）。

相对于网格（Mesh），三角形更常用因为能定义唯一的平面，扫描线渲染（Scanline Rendering）。

为了处理遮挡（Occlusion），使用画家算法（Painter’s Algorithm）、深度缓冲 Z Buffering、Z Fighting 错误出现穿模。

其他处理：背面剔除（Back Face Culling）、表面法线（Surface Normal）、平面着色（Flat Shading）、高洛德着色（Gouraud shading）, 冯氏着色（Phong Shading）、纹理映射（Texture Mapping）。

图形处理单元 GPU（Graphics Processing Unit）。

十六、计算机网络和互联网

局域网 LAN（Local Area Networks），最著名的是 1970 年代的以太网，需要每个电脑（网卡）有独立的媒体访问控制地址 MAC（Media Access Control address），载波侦听多路访问 CSMA（Carrier Sense Multiple Access）是多电脑共享的传输媒介，传输速度用带宽（bandwidth）表示。

多线路的冲突使用指数退避（Exponential Backoff），同时分组、引入交换机减少冲突域（Collision Domain）的范围。

电路交换（Circuit Switching）、报文交换（Message Switching）、分组交换（Packet Switching）、阻塞控制、ICMP、BGP。

IP 互联网协议（Internet Protocol），负责把数据包送到正确的计算机。UDP 用户数据报协议（User Datagram Protocol）在数据包中跟在 IP 之后，负责把数据包送到正确的程序。UDP 头部包含校验数（Checksum）。

但是要保证所有数据必须到达，则要使用 TCP 传输控制协议（Transmission Control Protocol），含有序号，发送确认码，调整传输率。

IP 地址复杂难记，DNS 域名系统（Domain Name System），分为 TLD、二级域名、子域名。

OSI 开放式系统互联通信参考模型（Open System Interconnection）从下至上：物理层、数据链路层、网络层、传输层、会话层、表示层、应用程序层。

超链接（Hyperlinks）形成巨大的网络：万维网。

URL 统一资源定位器（Uniform Resource Locator）、HTTP 超文本传输协议（HyperText Transfer Protocol）定位服务器中的内容。

HTML 超文本标记语言（HyperText Markup Language）。

第一个浏览器和服务器是 Tim Berners-Lee 花了 2 个月在 CERN 写的，1991 年正式发布，万维网就此诞生。

Jerry 和 David 的万维网指南 后来改名成 Yahoo，其他搜索引擎：JumpStation、Google。

网络中立性：平等对待所有数据包。

十七、计算机安全与黑客攻击

计算机安全三大要素：保密性, 完整性, 可用性（Secrecy, Integrity, Availability）。

使用威胁模型（Threat Model）模拟黑客攻击。

身份验证（Authentication）的三种方式：What you know、What you have、What you are。

访问控制（Access Control）：公开、机密/只读、可写、完全控制，例如美国国防部的 Bell LaPadula model 不能向上读取，不能向下写入。

安全内核、隔离（Isolation）：沙盒（Sandbox）建立在虚拟机上。

社会工程学（Social Engineering）：钓鱼（Phishing）、假托（Pretexting）、木马（Trojan Horses）。

NAND 镜像（NAND Mirroring）：物理连接复制内存，覆盖错误。

漏洞利用（Exploit）在远程端：利用缓冲区溢出（Buffer Overflow），通过边界检查（Bounds Checking）可以避免。

代码注入（Code Injection）植入 bug。

零日漏洞（Zero Day Vulnerability）是发现后立即被恶意利用的安全漏洞。

计算机蠕虫（Worms）、僵尸网络（Botnet）、拒绝服务攻击（DDoS）。

十八、加密

多层防御（Defence in depth）：加密（Encryption）、解密（Decryption）。

替换加密（Substitution cipher）、移位加密（Permutation cipher）：如凯撒加密（Caesar cipher）：字母向前移位 3 位。

列移位加密（Columnar transposition cipher）：读取方向和列表大小。

德国 Enigma 加密机，利用转子替换加密。

IBM 和 NSA1977 年制定数据加密标准（Data Encryption Standard (DES)）。

2001 年出现高级加密标准（Advanced Encryption Standard (AES)）。

密钥交换（Key exchange）：单向函数和密钥加密、迪菲-赫尔曼密钥交换（Diffie-Hellman Key Exchange）属于对称加密。

非对称加密（Asymmetric encryption）只能加密不能解密或只能解密不能加密、非对称加密算法（RSA）。

十九、机器学习与人工智能

分类（Classification）：使用分类器（Classifier）辨别特征（Feature），再标记数据（Labeled data）记录。

数据分析会出现决策边界（Decision boundaries）、混淆矩阵（Confusion matrix）、未标签数据（Unlabeled data）。

决策树（Decision tree）是机器学习算法的一种。还有支持向量机（Support Vector Machines）都源于统计学。

人工神经网络（Artificial Neural Network）和深度学习（Deep learning）。

弱 AI/窄 AI（Weak AI/Narrow AI）复杂但只能做一件事，强 AI（Strong AI）接近人类智能。强化学习（Reinforcement Learning）：和人类学习方式类似。

二十、计算机视觉

计算机视觉算法：检验颜色/垂直边缘。

核/过滤器（kernel or filter）包含做像素乘法的数字、卷积（convolution）。

Prewitt 算子（Prewitt Operators）、维奥拉·琼斯人脸检测（Viola-Jones Face Detection）、卷积神经网络（Convolutional Neural Networks）。

情感识别算法在识别出脸之后，可以进一步用其他算法定位面部标志，如眼睛和眉毛具体位置，从而判断心情等信息，也可用其他算法跟踪全身的标记点，如肩部，手臂等。

二十一、自然语言处理（NLP）

• 把句子分块，区分出词性（Parts of speech）、短语结构规则（Phrase structure rules）。
• 分析树（Parse tree）、知识图谱。
• 语音识别（Speech recognition）：谱图（Spectrogram）、快速傅立叶变换（Fast Fourier Transform）。
• 音素（Phonemes）识别、语音合成（Speech Synthesis）。

二十二、机器人和计算机心理学

机器人早期雏形：法国吃饭鸭（Digesting Duck, Canard Digerateur）、土耳其行棋傀儡下国际象棋。

第一台计算机控制的机器出现在 1940 年代晚期，叫数控机器（Computer Numerical Control(CNC)）。

1960 年 Unimate 是第一个商业贩卖的可编程工业机器人。

简单控制回路（simple control loop）、负反馈回路（negative feedback loop）。

比例-积分-微分控制器（Proportional–Integral–Derivative controller）即 PID 控制器。

机器人三定律（Three Laws of Robotics）。

我们需要了解人类心理学，做出更好的计算机。

易用度（Usability）：颜色强度排序比颜色排序好，分组更好记，电话号码 317-555-3897 比 3175553897 好记。

直观功能（Affordances）：认出 vs 回想（Recognition vs Recall）、Facebook 研究正面情绪影响。

用软件修正注视位置，让视频通话时看起来像盯着对方，而不是盯着下方。

让机器有一定情商，把机器人做的像人，恐怖谷理论。

计算机心理学有很多开放式的问题，心理学帮助我们明白不同选择可能带来的影响。

二十三、教育科技和计算机的未来

大型开放式在线课程（Massive Open Online Courses (MOOC)）。

智能辅导系统（Intelligent Tutoring Systems）：判断规则（Production rule）、域模型（Domain Model）、贝叶斯知识追踪（Bayesian knowledge tracing）：学生已经学会的概率、瞎猜的概率、失误的概率、做题过程中学会的概率、教育数据挖掘（Educational Data Mining）。

普适计算（Ubiquitous Computing）的愿景。

奇点（Singularity）：冯诺依曼提出，计算机发展爆炸性增长。

把工作分为 4 个象限，讨论自动化带来的影响。

机器人的存在时间可能长过人类，可以长时间探索宇宙。

Bezhuang