Course: Crash Course Computer
中文字幕组：计算机科学速成课
Overview
Outline the history of computers and the design decisions that gave us modern computersDescribe the basic elements of programming and softwareIdentify the basic components of computer hardware and what they doDescribe how computers are used and how that has evolved over timeAppreciate how far computers have come and how far they might take us
计算机早期历史
算盘 → 步进计算器 → 差分机 → 分析机 → 打孔卡片制表机最早的计算设备是算盘Computer 最初用于指代职业步进计算器是第一个可以做加减乘除的机器炮弹为了精准，要计算弹道，二战是查表来做。但每次改设计了就需要做一张新表Charles Babbage 提出了 “差分机”, 在构造差分机期间，想出了分析机, 分析机是通用计算机Ada Lovelace 给分析机写了假想程序，因此成为了第一位程序员人口普查 10 年一次. Herman Hollerith 的打孔卡片制表机大大提升了效率
电子计算机
继电器 → 真空管 → 晶体管哈佛 Mark 1 号，由IBM 于1944 年制造继电器，继电器一秒最多 50 次开关继电器出 bug1904 年，热电子管出现，第一个真空管。改进后变成和继电器的功能一样“巨人1号” 计算机在英国 布莱切利园 首次大规模使用真空管。但编程麻烦，还要配置1946 年，宾夕法尼亚大学的 ENIAC 是第一个通用可编程计算机1947 年，贝尔实验室做出了晶体管，晶体管有诸多好处，IBM 很快全面转向晶体管硅谷的典故：很多晶体管和半导体的开发都是这里做的。而生产半导体最常见的材料是硅肖克利半导体 → 仙童半导体 → 英特尔
布尔逻辑和逻辑门
二进制, 布尔逻辑(真假), George Boole，Boolean Algebra3个基本操作：NOT，AND，ORXOR 异或
二进制
用十进制与二进制的原理，二进制加法存储单位 MB（Megabyte）GB（Gigabyte）TB（Terabyte）正数，负数，整数，浮点数美国信息交换标准代码 - ASCII, 用来表示字符UNICODE 1992 年诞生，16位，是字符编码标准，解决 ASCII 不够表达所有语言的问题
算数逻辑单元 - ALU
ALU（Arithmetic and Logic Unit），英特尔 74181ALU 有 2 个单元，1 个算术单元和 1 个逻辑单元算术单元
半加器 (处理1个 bit，2个输入)全加器 (处理1个 bit，3个输入)8 bit 加法 (1个半加器，7个全加器）溢出Overflow乘法除法 逻辑单元
检测数字是否为 0 的电路（一堆 OR 门最后加个 NOT 门） 8位ALU 抽象成一个 V 符号Flag 标志（是否相等，是否小于，是否溢出等）
寄存器和内存
Memory （存储 / 内存 两种含义）存 1 位 (Gated Latch - 锁存器）存 8 位 (Register - 寄存器)16x16 的矩阵存 256 位Opcode数据选择器/多路复用器 (Multiplexer) 解码 8 位地址，定位到单个锁存器4 位代表行， 4 位代表列组合 256 位内存 + 多路复用器Multiplexer可寻址的 256 字节 内存一条1980年代的内存，1M 大小8个模块，每个模块有32个小方块，每个小方块有 4 个小块，每个小块是 128 位 x 64 位
中央处理器（CPU)
Instruction Register、Instruction Address RegisterRAM + 寄存器 + 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多核 (Core)多个独立 CPU超级计算机，中国的"神威 太湖之光"
早期的编程方式
打孔纸卡 → 插线板 → 面板拨开关纺织业，给机器编程的需求远在计算机出现前就有了打孔纸卡 - Punched card插线板 - Plugboard冯诺依曼架构 - Von Neumann Architecture面板编程 - Panel programming第一款取得商业成功的家用计算机: Altair 8800编程依然很困难，人们需要更友好更简单的方式编程
编程语言发展史
编程：二进制 → 助记符mnemonic（汇编器assembler）→ A-0（编译器）→ FORTRAIN二进制写程序，先纸上写伪代码，手工转二进制，很快就烦了用 "助记符” 写代码（LOAD_A 14）为了把助记符转二进制，汇编器诞生 (Assembler)葛丽丝·霍普 (Grace Hopper) - 哈佛1号计算机首批程序员, 海军军官Grace 设计了编程语言 A-0Grace 1952 年做了第一个编译器 (Compiler)，实现 A-0变量 (Variables)FORTRAN（1957，IBM）COBOL（Common Business-Oriented Language）新语言
1960 年代：ALGOL，LISP，BASIC1970 年代：Pascal，C，Smalltalk1980 年代：C++，Objective-C，Perl1990 年代：Python，Ruby，JavaNew millennium: Swift，C#，Go
编程基础 - 语句和函数
变量, 赋值语句Grace Hopper 拍虫子游戏if 判断while 循环for 循环函数
算法入门
选择排序 - Selection sort O(n^2)大 O 表示法 - Big O notation (算法复杂度)归并排序 - Merge sort O(n log n)Dijkstra 算法（graph search algorithms） O(n log n +1)
数据结构
数组 - Array下标 - Index (Begins at 0)字符串 - String矩阵 - Matrix结构体 - Struct指针 - Pointer节点 - Node链表 - Linked List队列 - Queue ---- FIFO(First in first out)栈 - Stack ---- LIFO(Last in first out) ----push、pop树 - Tree ----root/ leaf nodes二叉树 - Binary Tree图 - Graph红黑树和堆, 不同数据结构适用不同场景
阿兰·图灵
计算机之父 Born in 1912可判定性问题 Entscheidungs problem阿隆佐·丘奇，Lambda 算子图灵机 Turing machine、Turing complete停机问题 （it‘s a paradox）Bombe破解德军英格玛加密机图灵测试图灵奖
软件工程
对象 Object面向对象编程 Object Oriented ProgrammingAPI Application Programming Interfacepublic, private集成开发环境, IDE - Integrated Development Environments调试 debugging文档和注释 - readme, comment版本控制 Version control质量控制 Quality Assurance testing，QABeta, Alpha
集成电路与摩尔定律
晶圆的制作流程：光刻分立元件 Discrete components数字暴政 Tyranny of Numbers - 是 1960 年代工程师碰到的问题（如果想加强电脑性能，就要更多部件，这导致更多线路，更复杂。所以很难做）光刻 Photolithography晶圆 Wafer光刻胶 Photoresist光掩膜 Photomask掺杂 Doping摩尔定律 Moore’s Law.英特尔 Intel晶体管数量大幅度增长, 1980年三万个，1990年一百万个，2000年三千万个，2010年十亿个进一步小型化会碰到 2 个问题
光的波长不足以制作更精细的设计量子隧穿效应
操作系统
操作系统 Operating systems批处理 Batch processing计算机变便宜变多，有不同配置，写程序处理不同硬件细节很痛苦，因此操作系统负责抽象硬件外部设备 Peripherals设备驱动程序 Device drivers多任务处理 Multitasking虚拟内存 Virtual Memory动态内存分配 Dynamic memory allocation内存保护 Memory Protection1970年代，计算机足够便宜，大学买了让学生用，多个学生用多个 “终端” 连接到主机多用户分时操作系统，MulticsUnixMS-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 文本文件：ASCIIWAV 音频文件：每秒上千次的音频采样数字BMP 图片文件：像素的红绿蓝 RGB 值文件系统：很早期时空间小，整个存储器就像一整个文件。后来随容量增长，多文件非常必要目录文件：用来解决多文件问题，存其他文件的信息，比如开头，结尾，创建时间等平面文件系统 - Flat File System：文件都在同一个层次，早期空间小，只有十几个文件，平面系统够用如果文件紧密的一个个前后排序会造成问题，所以文件系统会： 1. 把空间划分成一块块 2. 文件拆分存在多个块里文件的增删改查会不可避免的造成文件散落在各个块里，如果是磁带这样的存储介质就会造成问题，所以做碎片整理分层文件系统 - Hierarchical File System：有不同文件夹，文件夹可以层层嵌套
压缩
压缩的好处是能存更多文件，传输也更快游程编码 Run-Length Encoding无损压缩 Lossless compression霍夫曼树 Huffman Tree“消除冗余"和"用更紧凑的表示方法”，这两种方法通常会组合使用字典编码 Dictionary coders, 游程编码 和 字典编码 都是无损压缩感知编码 Perceptual coding有损压缩 jpeg 格式时间冗余 Temporal redundancyMPEG-4 视频编码
命令行界面
运行开始直到结束，中间没有人类进行操作，原因是计算机很贵，不能等人类慢慢输入，执行完结果打印到纸上到1950年代，计算机足够便宜+快，人类和计算机交互式操作变得可行为了让人类输入到计算机，改造之前就有的打字机，变成电传打字机到1970年代末，屏幕成本足够低，屏幕代替电传打字机，屏幕成为标配人机交互 Human-Computer Interaction早期输出数据是打印到纸上，而输入是用纸卡/纸带一次性把程序和数据都给进去QWERTY 打字机的发展，克里斯托弗·莱瑟姆·肖尔斯 发明于 1868 年电传打字机 Teletype machine命令行界面 Command line interfacels 命令早期文字游戏 Zork (1977年)cd 命令
屏幕与 2D 图形显示
PDP-1 计算机。键盘和显示器分开，屏幕显示临时值阴极射线管 Cathode Ray Tube (CRT)CRT 有两种绘图方式：
矢量扫描 Vector Scanning光栅扫描 Raster Scanning 液晶显示器 Liquid Crystal Displays (LCD)，像素 (Pixel)字符生成器 Character generator屏幕缓冲区 Screen buffer矢量命令画图Sketchpad, 光笔 (Light pen)函数画线，矩形
冷战和消费主义
范内瓦·布什 预见了计算机的潜力，提出假想机器 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 兼容” 下保持了足够市场份额
图形用户界面 (GUI)
图形界面先驱：道格拉斯·恩格尔巴特（Douglas Engelbart）1970年成立 帕洛阿尔托研究中心（Palo Alto Research Center）1973年完成 Xerox Alto(施乐奥托) 计算机举例：写一个简单的 GUI 程序1981年的 Xerox Star system(施乐之星系统)史蒂夫·乔布斯去施乐参观，所见即所得 WYSIWYG1983年推出 Apple Lisa1984年推出 Macintosh1985年推出 Windows 1.0，之后出到 3.11995年推出 Windows 95 提供图形界面1995年微软做失败的 Microsoft Bob
3D 图形
线框渲染 Wireframe Rendering正交投影 Orthographic Projection透视投射 Perspective Projection网格 Mesh三角形更常用因为能定义唯一的平面扫描线渲染 Scanline Rendering遮挡 Occlusion画家算法 Painter’s Algorithm深度缓冲 Z BufferingZ Fighting 错误背面剔除 Back Face Culling表面法线 Surface Normal平面着色 Flat Shading高洛德着色 Gouraud shading, 冯氏着色 Phong Shading纹理映射 Texture Mapping图形处理单元 GPU, Graphics Processing Unit
计算机网络
局域网 Local Area Networks - LAN媒体访问控制地址 Media Access Control address - MAC载波侦听多路访问 Carrier Sense Multiple Access - CSMA指数退避 Exponential Backoff冲突域 Collision Domain电路交换 Circuit Switching报文交换 Message Switching分组交换 Packet Switching
互联网
IP - 互联网协议 - Internet ProtocolUDP - 用户数据报协议 - User Datagram Protocol校验和 - ChecksumTCP - 传输控制协议 - Transmission Control ProtocolDNS - 域名系统 - Domain Name SystemOSI - 开放式系统互联通信参考模型 - Open System Interconnection
万维网
超链接 HyperlinksURL - 统一资源定位器 - Uniform Resource LocatorHTTP - 超文本传输协议 - HyperText Transfer ProtocolHTML - 超文本标记语言 - HyperText Markup Language写一个简单网页，用到了 《h1》《 a》《h2》《 ol》《 li》 标签第一个浏览器和服务器是 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 ControlBell LaPadula model 不能向上读取，不能向下写入隔离 Isolation, 沙盒 Sandbox
黑客与攻击
社会工程学 Social Engineering钓鱼 Phishing假托 Pretexting木马 Trojan HorsesNAND镜像 NAND Mirroring漏洞利用 Exploit缓冲区溢出 Buffer Overflow边界检查 Bounds Checking代码注入 Code Injection零日漏洞 Zero Day Vulnerability计算机蠕虫 Worms僵尸网络 Botnet拒绝服务攻击 DDoS
加密
多层防御 Defence in depth加密 - Encryption，解密 - Decryption凯撒加密 Caesar cipher替换加密 Substitution cipher移位加密 Permutation cipher列移位加密 Columnar transposition cipher德国 Enigma 加密机1977年"数据加密标准" - 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卷积 convolutionPrewitt 算子 Prewitt Operators维奥拉·琼斯 人脸检测 Viola-Jones Face Detection卷积神经网络 Convolutional Neural Networks识别出脸之后，可以进一步用其他算法定位面部标志，如眼睛和眉毛具体位置，从而判断心情等信息跟踪全身的标记点，如肩部，手臂等
自然语言处理
词性 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个象限，讨论自动化带来的影响机器人的存在时间可能长过人类，可以长时间探索宇宙
