前几天读到一本非常好的书 ，《普林斯度计算机公开课》  【美】 布莱恩 W.克尼汉（Brian W. Kernighan）著 机械工业出版社
 
在此总结其中非常好的话语和知识。
 
前言
 
本书英文版网站 kernighan.com
 
第1章
 
阿达.洛夫莱斯被认为是世界上第一个程序员，Ada语言以其名字命名。
 
第一个由电器组成的计算机是ENIAC
 
{}
 
第一个真正将程序和数据存储在一起的计算机EDSAC
 
{}
 
集成电路（Integrated circuit）IC，也称为芯片或微芯片
 
第2章
 
“如果以2为底，则所得到的单位可以称为二进制数位，或者采用J.W.Tukey建议的一个词‘位’作为简称。” ——克劳德.香农《信息的数学理论》1948年
 
模拟（Analog） 类似（Analogous）
 
模数转换
 
{}
 
像素（Pixel）
 
对于音乐，典型的压缩技术是MP3和AAC（高级音频压缩），大约能把音频文件的体积压缩到原来的1/10
 
{}
 
对于图片，最常用的压缩技术是JPEG，是制定该标准的联合图像专家组（Joint Photographic Expert Group）的缩写，它的压缩率也能达到10倍或更高
 
{}
 
对于电影，老电影每秒通常只有十几帧，看的时候有明显的闪烁（flicks），衍生出美国著名的收费视频网站Netflix。电影常用MPEG（Moving Picture Experts Group ，动画专家组）的标准电影格式。
 
{}
 
ASCII码（American Standard Code for Infomation Interchange，美国信息交换标准代码）
 
Unicode码包含的字符集，访问unicode.org，此站点内容及其丰富
 
一个著名的笑话，“世界上只有10种人，理解二进制的和不理解二进制的。”
 
2的幂和10的幂的转换关系
 
{}
 
 
 
二进制的加减乘除法
 
{}
 
每个十六进制（hexadecimal）的数字代表4个位
 
 
 
第3章  深入CPU
 
“{}”——1946
 
网站 top500.org每6个月就重新公布一次全世界最快的500台计算机。
 
GPU（Graphics Processing Unit图像处理单元）是与通用CPU相比在处理特定图像时运算速度更快的一种专业化处理器。
 
阿兰·图灵在战时的工作被拍成电影，包括1996年的《破译密码》（Breaking the Code）和2014年的《模仿游戏》（Imitation Game）
 
1950年图灵发表名为《{}》的论文，其中提出一个测试，图灵测试。
 
缩写词CAPTCHA中包含图灵的名字，这个缩写词代表{}
 
 
 
 
 
 
 
 
 
 
 
 
 
 

引言：
 
1876年 贝尔 电话{}
 
通过因特网提供的电话服务（VoIP，即Voice over IP）
 
 
 
 
 
第8章 网络
 
带宽，网络的基本特性，描述了系统传输数据的速度。
 
等待或延迟衡量了特定信息块通过系统所需要的时间，高延迟不一定意味着低带宽：用卡车满载硬盘穿越整个国家，带宽显然是巨大的，但延迟也极高。
 
抖动，即延迟的可变性，对某些通信系统，特别是语音和视频通信来说，同样很重要。
 
信程指的是某种技术能够在多大地理范围内实现联网。
 
 
 
在信号上施加信息传送模式叫调制，反之，将该模式还原为原来的形式，叫解调。
 
电缆
 
DSL（DIgital Subscriber Loop，数字用户环路，有时也叫ADSL，强调“asymmetric”即“非对称”）{}
 
 
 
以太网（Ethernet），一种联网技术，可以在通过一根同轴电缆相连的计算机之间传送信号。每台以太网设备都有一个48位的数字标识符，这个标识符独一无二，叫做（以太网）地址。因此以太网最多可以连接2^48（约为2.8*10^14）台设备。
 
在Windows中通过ipconfig，在Mac上ifconfig可以显示这些地址。以太网地址都是以十六进制数字表示的，两位数字表示一个字节，因此总共是12位十六进制数字。比如，{}（字节间的冒可有可无）
 
一个名叫Wireshark的免费程序可以体验“嗅探”行为，可以显示以太网（包括无线网）流量的各种信息。
 
以太网数据包格式{}
 
无线 
 
无线系统利用电磁波传送信号。
 
调幅（AM）通过改变载波的振幅或强度来传达信息，而调频（FM）的原理则是围绕一个中心值来改变载波的频率。
 
频段在美国通常由FCC（{}）等政府机构负责分配，联合国下辖的ITU（{}国际电信联盟）负责制定国际协议。
 
 
 
今天计算机网络使用的无线标准是IEEE 802.11b/g/n/ac{}，民间流行称呼Wi-Fi。Wi-Fi是Wi-Fi联盟这个行业组织的商标。
 
IEEE （Institute of Electrical and Electronics Engineers，美国电气与电子工程师协会）
 
 
 
三种最广泛的无线联网技术
 
蓝牙（Bluetooth）{}
 
RFID（radio-frequency identification，无线射频识别）{}
 
GPS（Global Positioning System，全球定位系统）
 
 
 
手机
 
每台手机都有一个唯一的15位识别码，叫做IMEI（International Mobile Equipment Iddentity，国际移动设备标志），这相当于以太网的地址。{}
 
手机通信技术
 
GSM{}
 
CDMA{}
 
 
 
手机的流量在面对有目标的攻击时很脆弱，这种攻击来自一种称为黄貂鱼（stingray）的设备，这个设备的名字来自于叫做“StingRay”的商业产品。{}
 
带宽{}
 
压缩{}
 
错误检测与纠错{}
 
WEP（Wired Equivalent Privacy,有线等效保密）
 
WPA（Wi-Fi Protected Access，受保护的Wi-Fi接入）
 
 
 
 
 
第9章  因特网
 
ARPANET{}
 
因特网服务提供商（Internet  Service Provider,ISP）
 
在因特网上，输送数据的包叫做IP（Internet Protocol，因特网协议）数据包。{}
 
IPv4地址通常用4字节的值表示，其中每个字节对应一个十进制数，数与数之间用句点分割。叫做点分十进制表示法。
 
IPv6地址通常写做16个用十六进制值表示的字节，字节之间用冒号分割，比如2620:0:1003:100c:9227:e4ff:fee0:05ec
 
DNS（Domain Name System，域名系统）用于名字和IP地址之间的转换。{}
 
路由{}
 
使用Windows系统的tracert探测路由信息，Unix和Mac用traceroute
 
协议{}
 
TCP（Transmission Control Protocol，传输控制协议）
 
IP（Internet Protocol，因特网协议），IP数据包中有个TTL（Time to LIve，生存时间）
 
动态更改IP地址是通过DHCP协议（Dynamic Host Configuration Protocol，动态主机配置协议）
 
 
 
因特网的大部分核心技术是由IETF（Internet Engineering Task Force，因特网工程任务组）开发的。{}
 
RFC（Request for Comment，征求修正意见书）。www.ietf.org
 
管理因特网其他事务的是一个叫ICANN（Internet Corporation for Assigned Names and Numbers，因特网名称与数字地址分配机构），网站www.icann.org{}
 
根服务器，负责顶级域的转换工作。{}
 
可以用nslookup等工具亲自体验DNS查询，试试运行：
 
nslookup a.root-servers.net
 
注册自己的域名{}
 
 
 
Tel与SSH——远程登录
 
SSH（Secure Shell，安全外壳协议）{}
 
SMTP（{}，简单邮件传输协议），端对端协议{}
 
IMAP{}
 
文件共享与点对点协议{}
 
因特网上的版权{}
 
物联网{}
 
IoT（Internet of Things）
 
 
 
 
 
第10章 万维网
 
world wide web ，简称Web
 
万维网使用因特网建立连接和传送消息，并为获取其他基于因特网的服务提供页面。
 
万维网主要由四个组成要素：
 
URL（Uniform Resource Locator，统一资源定位符），形如http://www.amazon.com，指定要访问信息的名字
 
HTTP（HyperText Transfer Protocol，超文本传输协议），在客户机请求某个URL时，让服务器能够返回客户端想要的信息
 
HTML（HyperText Markup Language，超文本标记语言），描述服务器返回信息的格式（或表现形式）
 
浏览器，通过URL和HTTP向服务器发送请求，然后读取并显示服务器返回的HTML
 
 
 
第一个浏览器{}
 
万维网技术由万维网联盟（World Wide Web Consortium，简称W3C，网站为w3.org）这个非营利机构控制着，至少是引导着。
 
万维网工作原理{}
 
HTML{}
 
CSS（Cascading Style Sheets，层叠样式表）。通过CSS语言可以定义标题格式之类的样式，并将该样式实施于所有对象。
 
CGI（Common Gateway Interface，公共网关接口）机制{}
 
cookie{}
 
网页上的动态内容{}
 
 
 
病毒、蠕虫和特洛伊木马{}
 
 
 
 
 
网络安全{}
 
 
 
第11章  数据与信息
 
“当你看因特网够久时，因特网也会回看向你”。——改编自弗里德里希·尼采的名言 原文出自1886年发表的《善恶的彼岸》
 
搜索{}
 
跟踪{}
 
社交网络{}
 
数据挖掘与聚合{}
 
云计算{}
 
 
 
 
 
第12章  隐私与安全
 
加密{}
 
密钥加密{}
 
公钥加密{}
 
Tor与Tor浏览器{}
 
比特币{}
 
比特币的所有交易使用公共的分期账簿，这个账簿叫做区块链，不过交易的双方都是匿名的，通过作为加密公钥的地址进行识别。
 
想尝试比特币，可以从bitcoin.org开始，同时coindesk.com也提供了很好的教程信息。
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

第4章 算法
 
线性算法
 
二分查找，每次检查或者比较都会把数据项一分为二。
 
排序，比如选择排序，不断从未经排序的名字中选择下一个名字，复杂度近似为N^2，这个增长率叫二次增长；
 
           快速排序，首先遍历一次所有名字，把介于A和M之间的名字放在一组里，把介于N和Z之间的名字放到另一组里，这样就把所有名字分成了两个组。然后继续迭代分组，排序N个名字的工作量是N
 
复杂性分析： 
 
一端是logN，可见于二分搜索。常见的是线性增长，或者说简单的N。快速排序的NlogN，比N要糟糕。还有N^2。还有指数级复杂性，也就是2^N，是另一个极端。
 
“容易”的问题，都具有“多项式”（Polynimial）级复杂性。也就是解决这些问题耳朵时间可以用N^2这样的多项式来表示其中指数可以大于2，但都是可以被将解决的。计算机科学家称此类问题为P问题。
 
现实中大量问题需要指数级算法来解决，也就是说还不知道这类问题有没有多项式算法。这类问题称为“NP”（非确定性多项式）问题。比如“旅行推销员问题”,一个推销员必须从他居住的城市出发，到其他几个城市去推销，然后再回家。目标是每个城市只到一次不能重复，且走过的总距离最短。其原理可以应用于设计电路板上孔洞的位置。
 
1970年，史蒂芬·库克证明了所有这些问题其实都是等价的，只要能找到一个多项式时间算法（复杂性类似于N^2）解出其中一个问题，据此就能找到所有问题的多项式时间算法。库克因此获得了1982年的图灵奖。
 
 
 
2000年，美国克雷数学研究所（Clay Mathematics Institute）以每个100万美元奖金悬赏求解7个公开难题。其中一个是P是否等价于NP？其中庞加莱猜想已被解决，俄罗斯数学家格里格里·佩雷尔曼2010年获得大奖但拒绝接受奖金。
 
第5章 编程与编程语言
 
汇编语言{} 
 
高级语言{}
 
Fortran源自“Formula Translation（公式转换）”
 
COBOL
 
BASIC     Microsoft Visual Basic是其一个主要分支
 
C、C++{}
 
Java、
 
JavaScript（衍生自C语言，与Java没有任何关系），但与C差别很大
 
软件开发{}
 
API（Application Programming Interface，应用编程接口）
 
SDK（Software Development Kit，软件开发工具包）
 
Bug的由来{}
 
最终用户许可协议（End User License Agreement,EULA）
 
标准{}
 
开源{}
 
GNU，gnu.org。
 
GNU通用公共许可（GNU General Public License，GPL）
 
Red Hat公司
 
 
 
第6章 软件系统
 
操作系统{}
 
操作系统工作原理{}
 
文件系统{}
 
磁盘文件系统{}
 
清楚文件{}
 
其他文件系统{}
 
软件的层次{}
 
第7章 学习编程
 
代码学院（Codecademy）  可汗学院（Khan Academy）
 
HTML（HyperText Markup Language，超文本标记语言）
 
不要使用Word等文字处理程序来生成HTML文件，而应该使用记事本或TextEdit这样的文本编辑器以确保文件保存为纯文本文件，也就是即使文件的扩展名是.html也没有任何格式信息的ASCII文件。
 
 
 
 
 
 
 
 
 
 

第一章 Union-Find
 
01 Dynamic connectivity (动态连接性问题即 the model of union find 并查集模型)
 
问题：
 
a set of N objects (use the numbers zero through N-1 to model our objects). and we then have the idea of a connection between two objects. And, we'll, postulate that there's going to be a command that says, connect two objects. Given two objects, provide a connection between them. And then key part of the problem is find query or the connected query, which just asks, is there a path connecting the two objects. so for example
 
有N个对象（用数字0到N-1去标记这N个对象） 两个对象是可以连通的。我们假设有一个命令可以连接两个对象，将两个对象传入该命令将创造两者之间的连接，现在问题的关键是连通性的查询，即查询两个对象之间是否有联通的路径存在。举例：
 
in this set of ten objects, a bunch of union commands, connecting 4 and 3, 3 and 8, 6 and 5, 9 and 4, 2 and 1. And now we might have a connected query that says, is zero connected to seven? in this case, there is no connection, so we say no. But if we ask is eight connected to nine? We are going to say yes, even no we don't have a direct connection between eight and nine. There is a path from eight to three to four to nine. So, that's our problem, to be able to officially support these two commands for given set of objects.
 

 
 
So that's our problem, intermix union, commands and connected queries and we need to be able to officially support
 those commands for a large number of objects.
 
 
更大一点的问题举例
 

 
 
Applications involve manipulating objects of all types.
 
 
 
we'll just name the objects with a number, integers from zero to N-1. That's a very convenient initial starting point for our programs because we can use integers as an index into an array then, and then quickly access information relevant to each object. And it also just supresses a lot of details that are not relevant to union find. In fact, to make this mapping from an object name to the integer zero through N - one is to find application of a symbol table or a searching algorithm. (用0到N-1标记这N个对象的好处)
 
 
关于连接的性质假定
 
自连接性：p is connected to p
 
对称性：if p is connected to q, then q is connected to p.
 
传递性: if p is connected to q and q is connected to r, then p is connected to r.
 
When we have an equivalence relation a set of objects and connections divide into subsets called connected components. A connected component is a maximal set of objects that's mutually connected. For example 
 
 

 
 
未完待续...