-
《普林斯顿计算机公开课》总结(一) 硬件部分
2019-05-23 23:49:43前几天读到一本非常好的书 ,《普林斯度计算机公开课》 【美】 布莱恩 W.克尼汉(Brian W. Kernighan)著 机械工业出版社 在此总结其中非常好的话语和知识。 前言 本书英文版网站 kernighan.com 第1章 阿达....前几天读到一本非常好的书 ,《普林斯度计算机公开课》 【美】 布莱恩 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中包含图灵的名字,这个缩写词代表{}
-
《普林斯顿计算机公开课》总结(二) 软件部分
2019-05-23 23:49:502000年,美国克雷数学研究所(Clay Mathematics Institute)以每个100万美元奖金悬赏求解7个公开难题。其中一个是P是否等价于NP?其中庞加莱猜想已被解决,俄罗斯数学家格里格里·佩雷尔曼2010年获得大奖但拒绝接受...第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文件。
-
《普林斯顿计算机公开课》总结(三) 通信部分
2019-05-23 23:49:36以太网(Ethernet),一种联网技术,可以在通过一根同轴电缆相连的计算机之间传送信号。每台以太网设备都有一个48位的数字标识符,这个标识符独一无二,叫做(以太网)地址。因此以太网最多可以连接2^48(约为2.8*10...引言:
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也提供了很好的教程信息。
-
飞龙的计算机公开课推荐
2018-02-23 07:36:07这里是我推荐的一些优秀公开课,我上过绝大部分。 编程 哈佛 CS50 MIT 6.001x UCB CS61a 主页 中文版教材 数据结构·算法 斯坦福 CS106b UCB cs61b 普林斯顿 Algs4 MIT 6.006 系统 nand2tetris CMU ...来源:https://it-ebooks.flygon.net/mooc/
这里是我推荐的一些优秀公开课。
编程
数据结构·算法
系统
- nand2tetris
- CMU 15-213
- MIT 6.828
- UCB CS61c
- MIT 6.824
- 斯坦福 CS144
- 斯坦福 CS145
- Gate Lectures OS
- Gate Lectures 计网
编译
理论
数据科学
- MIT 18.003
- MIT 18.06
- 斯坦福 CS109
- UCB Prob140
- UCB STAT150
- UCB STAT153
- UCB STAT155
- 斯坦福 博弈论
- 耶鲁 ECON159
- 斯坦福 CVX101
- UCB DATA8
- UCB DS100
- MIT 6.00.2x
机器学习
- UCB CS188
- MIT 6.034
- 斯坦福 CS229
- 斯坦福 CS231n
- 斯坦福 CS224d
- 斯坦福 CS20si
- 斯坦福 CS230 / DeepLearningAI
- MIT 6.S191
- UCB CS294
商业·理财
- 斯坦福 CS183
- 斯坦福 CS183b
- 斯坦福 CS183c
- 斯坦福 CS183f
- 斯坦福 CS007
高校课程资源汇总
以下是由广大网友整理的,某一高校的课程资源汇总。
- 浙江大学课程攻略共享计划
- 中国科学技术大学课程资源
- 北京大学 EECS 课程资源
- 上海交通大学软件学院课程资源
- 北京林业大学信息学院课程攻略
-
普林斯顿公开课 算法1-6:内存
2014-10-11 09:46:00在计算机中,内存是通过字节来表示的,一个字节表示8个位。1KB是2^10字节。 数据类型占用的内存 在32位系统中,一个指针占用4个字节。在64位系统中一个指针占用8个字节。本课程中使用64位机器,一... -
飞龙的计算机公开课推荐 2018.2.23
2018-02-22 23:37:42这里是我推荐的一些优秀公开课,我上过绝大部分。 编程 哈佛 CS50 MIT 6.001x UCB CS61a 主页 中文版教材 数据结构 斯坦福 CS106b UCB cs61b 算法 普林斯顿 Algs4 MIT 6.006 系统 nand2tetris CMU 15-213 ... -
普林斯顿大学算法公开课(1)----介绍
2013-06-16 19:21:00课程概况 这个课程是什么? (1)中级研究课程。 (2)编程解决问题。 (3)算法:解决问题的思路方法。 (4)数据结构:存储信息的方法。...(3)计算机。电路草图,文件系统,编译器。 (4)计... -
普林斯顿大学_算法公开课:Part_1_第一部分:并查集
2018-05-20 23:07:27首先,给大家推荐一个平台,Coursera (类比国内的mooc网),你可以在上面学习诸多国外一流大学的公开课视频,各个领域的都有,涉猎范围很广。想要出国留学的小伙伴儿不妨在上面事先感受一波国外授课的氛围与模式。... -
推荐一波知名学府的计算机/编程/AI免费公开课
2020-04-30 17:27:11导读:50+公开课分别来自哈佛、MIT、UCB、普林斯顿、CMU、斯坦福以及国内清华、北大、中科大、浙大、上交大、东南大学、南邮等知名学府,伴随公开课一并奉上的不仅有课程视频、课程笔记,还有中文版教材和攻略。... -
推荐IT入门书籍
2021-01-14 00:48:23《普林斯顿计算机公开课》 中文版(京东有售,不到50元) 《数据结构与算法 C 语言描述》机械工业出版社 《操作系统概念》第七版 高等教育出版社 《计算机网络》第五版 中文版 清华大学出版社 《数据库系统概念》 原... -
AI公开课:19.05.15施尧耘-达摩院量子实验室主任《量子计算:前景与挑战》课堂笔记以及个人感悟
2019-05-29 09:12:01AI公开课:19.05.15施尧耘-达摩院量子实验室主任《量子计算:前景与挑战》课堂笔记以及个人感悟 导读 施尧耘1997年本科毕业于北京大学,后在普林斯顿大学取得计算机科学博士学位,是密西根大学安娜堡分校终身教授... -
译者前言
2018-09-12 15:21:57这是一本关于比特币和区块链技术的专业著作,起源于业内所熟知的比特币和加密货币技术的普林斯顿网络公开课。以 普林斯顿大学计算机科学助理教授阿尔文德·纳拉亚南(Arvind Narayanan)为首的专家,与我们分享了... -
第1章 导论
2017-10-19 16:05:421、Robert Sedgewick普林斯顿大学公开课,课程链接见B站,带有中文字幕高大上 2、阅读课本:《算法:C语言实现第1-4部分》、《算法:C语言实现第5部分》连通性问题描述:假如一个整数对序列,其中整数代表某种类型... -
浅谈算法和数据结构: 一 栈和队列
2019-09-21 20:29:16最近晚上在家里看Algorithems,4th Edition,我买的英文版,...另外普林斯顿大学在Coursera上也有这本书同步的公开课,还有另外一门算法分析课,这门课程的作者也是这本书的作者,两门课都挺不错的。 计算机程序离... -
浅谈算法和数据结构:栈和队列
2016-07-15 10:22:44最近晚上在家里看Algorithems,4th Edition,我买的... 上也有这本书同步的公开课,还有另外一门算法分析课,这门课程的作者也是这本书的作者,两门课都挺不错的。 计算机程序离不开算法和数据结构,本文简单介绍栈(St