【21-30】计算机科学速成课- Carrie Anne
21、压缩
目的：相同的文件，占据更少的存储空间
- 无损压缩：压缩时没有丢失任何数据，解压缩后和压缩前完全一样
【方式1】消除冗余——减少重复信息
【方式2】紧凑代码表示——霍夫曼树编码（字典压缩法）
第一步：统计所有块出现频率
第二步：每次选择频率最低的两个组成树，频率变更为节点之和，直到形成一个按照频率分层的树形结构
第三步：每个二叉编码为0或1，生成字典
第三步：编码
第四步：字典 + 编码后数据
- 有损压缩：对于有些文件（实时音频、视频等），即使丢失部分数据，不影响人类使用
【方式1】感知编码——删除人类无法感知数据，减少人类感知弱的数据
skype软件因为网络速度下降，压缩算法减少精度——声音逐渐失真
音频——mp3
图片——JPEG
视频——时间冗余（每一帧画面中存在大面积相同图案 + 只是少量像素位置变化）MPEG-4
22、命令行
人机交互概念：计算机和人类间信息交换 —— 输出：计算机→人类 & 输入：人类→计算机 *
- 早期：输入——齿轮、旋钮、开关、控制面板、可插拔电线等机械结构；输出—— 打印机
- 1950年代：输入——打孔纸卡和磁带；输出——打孔制表机 + 指示灯
- 1950年代末期（小型计算机价格变便宜 & 大型计算机支持多个程序和多个用户）：输入/输出——电传打字机
打字机目标：易读性和标准化
打字机速度提升：1880年代十指打字 和 盲打 普及
转移成本：当人们熟悉最早的QWER布局，适应其它布局键盘将额外费时费力
屏幕最早出现在1950年代，由于分辨率低和价格高，直到1970年代屏幕才代替电传打字机
1971年美国大约有7万台电传打字机和7万个终端。1970年代末，屏幕成本标配
- 文字终端用途
命令行交互
编程
早期交互式文字游戏：1977年Zork → 多人游戏MUD/多人地牢游戏 → MMOrpg大型多人在线角色扮演游戏
打开现代计算机终端 windows——cmd Mac——Terminal 尝试安装游玩Zork
23、屏幕和二维图形显示
- 显示设备
早期屏幕用途：追踪程序运行情况、显示临时变量、图形绘制
- 屏幕字符显示——基于字符集
早期计算机内存小，采用字符编码（ASCII→ IBM CP437，额外色彩编码……）配合字符生成器显示，更省存储
第一代显卡（字符生成器）：自带ROM存储符号点阵，从内存中屏幕缓冲区读取信息，转换为光栅图形显示
- 屏幕图形显示——基于矢量
- 字符图形显示——基于像素的位图显示
帧缓冲区（内存）→VRAM（显存）
8bit图像——256灰度等级
基于函数指令填充像素表示图形：直线、曲线、图形、文字等
位图显示更加灵活，代价高昂 持续了数年（1971年只有约1000台电脑有交互式图形界面）
24、冷战和消费主义
- 冷战——政府主导
二战中计算机发挥重要作用，美苏冷战时政府将大量资源投入科学和工程领域。早期计算机依赖政府投入快速发展
二战美国国家研究与开发办公室（负责战间资助和安排科学研究）负责人 Vannevar Bush，在1945年预测计算机影响
1945年 遐想计算机Memex：可以用这个设备存自己所有的书，其它资料，以及和别人沟通。而且数据是按照格式存储，所以可以快速查询，有很大灵活性。可以辅助我们记忆
新的百科全书形式（web的概念）：信息间相互链接
推动1950年国家科学基金成立首个商业成功计算机型号：Univac 1—成功预测1952年美国大选，使得计算机进入公众视野；首个批量生产型号
【晶体管普及】
晶体管收音机更小、更耐用、只需电池更便携
日本获取贝尔实验室晶体管授权，1955年索尼推出TR-55晶体管收音机，5年内占据一半美国便携收音机市场
【苏联】1950年第一个可编程电子计算机
【美苏太空争霸】
1957年苏联发射人类第一个卫星 Sputnik 1
1961年苏联将第一个太空宇航员 尤里* 加加林送进太空
美国阿波罗登月计划——阿波罗导航计算机（计算要快、体积小&重量轻、超高可靠性）——集成电路
洲际导弹和核弹等军事设施和超级计算机——推动集成电路大规模生产
- 消费主义——市场主导
早期美国半导体依赖政府高利润订单，1950-1960年代日本依靠模经济&自动化 降低成本占领半导体消费者市场
1970年代太空竞赛和冷战逐渐消退—政府订单减少：美国半导体公司竞争劣势(1974年Intel裁员1/3;
1979年仙童半导体濒临倒闭，被收购;外包生产降低成本;细分领域)
基于微处理器的其它电子产品：电视、手表、随身听、游戏机（1972年Pong、1976年打砖机）
1975年Altair 8800——第一批家用电脑 & 1977年Atari 2600——第一款家用游戏机
政府投入，推动计算机早期发展，维持计算机行业生命力和技术成熟到商用
公司和消费者让计算机成为主流
25、个人计算机革命
1970年代末，计算机各个组件成本下降，性能强大——个人计算机时代
微型计算机诞生→ 性能可观，价格个人/家庭能够承担
单芯片CPU——（强大、体积小、便宜）
集成电路/固态存储 ——低成本
主板——将计算机集成到一张电路板，降低成本
磁带&软盘——便宜可靠的存储介质
显示器——由电视改装，成本低- 首个个人计算机
【硬件】允许用户购买零件组装，推动内存、纸带读取器、电传接口等硬件出现
【编程】机器码→Altair BASIC：比尔*盖茨 & 保罗*艾伦推出首个依赖解释器的编程语言
【社区】大量计算机爱好者小组，例如 家酿计算机俱乐部
1976年Steve Wozniak免费分享展示自行设计的计算机原型机——电视呢显示、提供文本界面
- 面向消费者计算机
【硬件】
1977年市面上三种开箱即用计算机：自带basic解释器，方便编程
Apple-2（首个全配套个人计算机：良好设计和制造、简单色彩和声音输出）
TRS-80-1（价格更便宜）
Commodore PET 2001（一体化设计：集成计算机、显示器、键盘、磁带驱动器）
【软件】游戏和各种生产力工具——计算器、文字处理器、最早的电子表格（1979年VisiCalc）
- 开放式架构 VS 封闭架构
IBM忽视微型计算机市场：份额下降1970年60%→1980年30%；
推出采用开放式架构（IBM兼容）的个人计算机——IBM PC——良好文档、扩展槽、方便拓展其它硬件
微软将MS-DOS授权给其它计算机品牌——MS-DOS成为最受欢迎的PC操作系统
Apple从硬件到软件full-stack保持封闭架构——保证用户体验和较高可靠性
26、图形用户界面
二战期间作为驻菲律宾雷达操作员，阅读Vannevar Bush的Memex文章
1955年在UCB获取博士学位
1962年报告“增强人类智力”：除了自动化，应借助计算机辅助解决复杂知识性问题
1964年，和同事比尔*英格利希研发便于使用屏幕进行人机交互的鼠标
1968年在“秋季计算机联合会议”历史首个演示：位图图像、视频会议、文字处理、协多人作等计算机功能
包含现代图形用户界面原型：鼠标光标 + 多窗口；过于超前，商业失败
1997年获得图灵奖
- 首个带GUI计算机
1970年代政府资金减少，道格拉斯*恩格尔巴特团队成员进入施乐的“帕洛阿尔托研究中心Xerox PARC“
1973年Xerox PARC开发带GUI计算机：XEROX ALTO
特点1：引入计算机桌面、窗口、文件堆叠等
特点2：WIMP Interface：用窗口、图标、菜单和指针设计图形界面
特点3：提供可复用基本显示元素（按钮、勾选框、滑动条、标签页等）
1981年发布系统”施乐之星“，引入计算机文件夹和文件
施乐首先使用术语：剪切、复制、粘贴——编辑打字机文件 & 计算机显示和纸张打印相同（所见即所得）
过于领先，价格昂贵，销量不佳
- 乔布斯和 Apple Macintosh
1979年12月乔布斯去施乐参观，完全基于鼠标的图形界面直观操作——计算机产业的未来
新功能：菜单栏、垃圾桶
1983年首个GUI + 鼠标计算机——Apple Lisa（价格过于昂贵，失败）
1984年Apple Macintosh发布，有销量但缺少可使用软件
- Windows
价格更加低廉的原始图形用户界面计算机受到市场欢迎，影像apple营收
乔布斯和Apple新CEO关系紧张→被扫地出门
Windows 1.0 发布，基于非图形化的DOS系统开发
Windows 3.1后微软面向消费者开发的新的GUI操作系统Win95（多任务、受保护内存、开始菜单、任务栏、文件管理器）
27、三维图形显示
- 3D和2D本质区别
- 投射和简单3D图形——线框
- 复杂3D图形——线框
- 3D图像填充
线扫描：3D图形中单个三角形平面逐行扫描，填充像素
抗锯齿：正常填充多边形中的像素，对于多边形边缘的像素浅化颜色，减轻图形边缘锯齿感
遮挡：3D图形在某一时刻，只有部分被显示，另一部分被遮挡不显示
【问题1】：Z-fighting——两个多边形存在部分像素与摄像机距离相同
【问题2】多边形内存中位置变化导致访问顺序变化
【问题3】浮点计算误差
案例：背面剔除技术——实际只渲染多边形正面，不渲染反面，节省渲染时间。进入模型内部后部分平面消失
- 明暗处理——借助灯光实现3D场景中图形表面明暗变化
- 纹理——图形学中指外观
- 渲染加速方法
专用硬件，例如GPU & 将3D场景拆分成若干小部分，并行渲染
28、计算机网络-互联网
- 局域网LAN：计算机间近距离构成的小型网络。
1950-1960年代，第一种计算机网络，用途：公司或研究室内部信息交换
特点：比搬运纸卡或磁带更快速可靠 & 可共享物理资源
典型局域网：1970年代施乐“帕洛阿尔托研究中心Xerox PARC”开发的以太网
【简单网络】所有设备共享信道，借助MAC地址（媒体访问控制地址）局域网中定位
CSMA载波侦听多路访问协议：共享信道的若干设备信息交换方式——监听信道，仅检测到信道空闲时发送信息
带宽：网络中两个设备间数据传输的速度
指数退避：单次信息发送前，检测到信道占用延后发送。延后次数越多，延后时间指数增加，避免网络拥塞
冲突域：共享信道的若干设备和信道载体本身
【复杂网络】交换机：将一个冲突域划分为两个小的冲突域，仅在跨冲突域信息传输时占用整个信道
- 广域网Wlan：计算机间远距离网络
29、计算机网络-因特网
因特网：使用TCP/IP协议族控制数据传输的互联网
- 数据交换方式
TCP/IP（传输控制协议/网际协议）是指能够在多个不同网络间实现信息传输的协议簇
IP地址：计算机在因特网中位置
端口号：由计算机分配给网络程序的序号，表示程序在计算机中位置
数据传输方式1：TCP——两个互联网应用建立连接后，再传输数据
数据传输方式2：UDP——将数据划分为报文/分组，由中间节点存储转发，直到接收方，类似寄信。
IP数据报/分组：因特网中数据交换基本单位
【UDP】无连接，开销小，网络质量要求低，数据最大限度送达
【TCP】建立连接，开销大，网络质量要求高，所有数据全部送达
阻塞控制：平衡网状结构中不同节点上的负载，确保数据传输快速可靠
- 网络层次结构
应用层：能联网的互联网应用& 表示层：系统间信息交换格式及转换 & 会话层：连接建立与管理，有序数据传输
查看本机连接到百度服务器 网络路由(跳转)次数
windows命令行
Tracert www.baidu.com
linux/Mac 命令行
traceroute www.baidu.com- 域名系统：域名相比IP更适合人类记忆和使用
30、万维网
- 万维网World Wild Web：因特网中使用最多的网络服务，基于浏览器（客户端）-服务器架构
1990年Tim Berners-Lee建立第一个浏览器和服务器。1991年发布——万维网建立
web网页：万维网基本单位——单个页面，包含文字、图像、视频等 和链接到其它页面的超链接
HTML：超文本标记语言，用于内容组织和网络传输，可由浏览器渲染为web页面
URL：统一资源定位符号，唯一标识万维网中的网页。便于浏览器访问
HTTP：超文本传输协议，客户端和服务器端基于请求和响应交换数据
状态码：HTTP协议中，用于表示数据交换状态 ：200—正常 、404—请求资源不存在、500—服务器内部错误
- 开放标准
【互联网大繁荣】
开放标使得任何人可以开发新服务器和新浏览器
浏览器
1993年Mosaic浏览器——第一个文字和图像显示在一个页面的浏览器 & 书签功能等
其它浏览器：Netscape、Navigator、Internet Explorer、Opera、OmniWeb、Mozilla
服务器
Apache、微软互联网信息服务IIS
网站：
亚马逊、ebay
【搜索引擎】
万维网中网页众多，网址不易记忆和传播、粒度过大
web目录：Jerry and David‘s guide to the World Wild Web （雅虎前身）
1993年Jonathon Fletcher在斯特林大学创建第一个现代搜索引擎JumpStation
搜索引擎：【爬虫：不断将新链接加入自身列表】【索引：记录历史访问和单词】【搜索算法：查询索引方法】
搜索排名
早期依据网页中出现次数，无法避免恶意污染索引
Google： 前身1996年斯坦福大学BackRub项目，通过网页被链接数（而不是内容）判断可信度，避免信息污染
- 网络中立原则：平等的对待所有数据包，相同的优先级
【支持】
防止商业公司 特别是互联网服务供应商，提升自身数据包优先级，节流（降低优先级和带宽使用）其它数据包
防止垄断，影响小公司和创新
【反对】
对于实时性要求不同的应用，用户有合理差异性需求
依靠市场竞争防止不良网络不良行为
注意：本文大量使使用网络素材
文章被以下专栏收录
