计算机科学速成课
计算机早期历史 Early Computing
公认最早的计算设备的算盘,注意不是中国的,而是美索不达米亚文明的,它没有计算的功能,只是用于记录数据。
最早使用计算机 computer 一词的文献是 1613 年的一本书,指的是一种职业,即负责计算的人,他们有时也会使用机器辅助计算,所以渐渐地“计算机”也代指机器。
步进计算器:由莱布尼兹发明,像汽车的里程表
加法:由多个齿轮组成,每当一个齿轮转过 9,它会转回 0,同时让旁边的齿轮前进一个齿
减法:反向旋转
乘除:本质上是加法或减法的叠加
所以它是第一台能做“加减乘除”的机器
计算表:预先算好,也就是早期的打表法,类似与字典之类的工具书,但不够灵活。
Charles Babbage 提出了“差分机”,能近似多项式,但最终没做出来,后来有人历史学家按照它的设计图做了出来,发现确实可以做到。
在做这台机器的过程中,这个人提出了一种“分析机”的概念,是“通用计算机”,和后来的冯诺依曼结构是一种东西,但实在是太超前了,当时仅存在于概念上。
此人被认为是“计算之父”
Ada Lovelace 给分析机写了假想的程序,被认为世 ...
MIT 18.06:线性代数
方程组的几何解释
二元一次方程组:
{2x−y=0−x+2y=3\begin{cases}
2x - y = 0 \\
-x + 2y = 3
\end{cases}
{2x−y=0−x+2y=3
可以写成矩阵形式:
[2−1−12][xy]=[03]\begin{bmatrix}
2 & -1 \\
-1 & 2
\end{bmatrix}
\begin{bmatrix}
x \\
y
\end{bmatrix}
=\begin{bmatrix}
0 \\
3
\end{bmatrix}
[2−1−12][xy]=[03]
更进一步抽象:
Ax=bAx = b
Ax=b
列的线性组合:
x[2−1]+y[−12]=[03]x \begin{bmatrix}
2 \\
-1
\end{bmatrix}
+y \begin{bmatrix}
-1 \\
2
\end{bmatrix}
=\begin{bmatrix}
0 \\
3
\end{bmat ...
MIT 18.01:单变量微积分
导数 derivatives
几何解释:切线斜率
物理解释:速率
极限 limits 连续性 continuity
limΔx→0ΔyΔy=dydx\lim_{Δx→0}\frac{Δy}{Δy} = \frac{\mathrm{d}y}{\mathrm{d}x}
Δx→0limΔyΔy=dxdy
若
limx→x0f(x)=f(x0)\lim_{x→x_0}f(x) = f(x_0)
x→x0limf(x)=f(x0)
则称 f(x)f(x)f(x) 在 x0x_0x0 处连续 continuous
可去间断点 removable discontinuity:若左极限 limx→x−f(x)=\lim_{x→x^{-}}f(x)=limx→x−f(x)= 右极限 limx→x+f(x)\lim_{x→x^{+}}f(x)limx→x+f(x),但是 f(x0)f(x_0)f(x0) 不相等或无定义
跳跃间断点 jump discontinuity:左、右极限均存在但不相等
两个三角的极限:
limθ→0sinθθ=1\lim_{θ→0}\frac{\s ...
MIT 6.042J & 18.062J:计算机科学中的数学
证明 Introduction and Proofs
广义上的证明 Proof:确定事实的方法
手段:
实验和观察
抽样找反例
法官-陪审团
上帝的话
老板
内心的信念
数学上的证明是通过一系列公理的逻辑推理来验证一个命题
定义:命题 Proposition 是要么为真要么为假的陈述
定义:谓词 Predicate 是一个真值依赖于变量值的命题
定义:如果 ppp 为假或 qqq 为真,则蕴含 implication p ⟹ qp \implies qp⟹q 为真
所以猪会飞 ⟹ \implies⟹ 我是国王是正确的
定义:公理 axiom 是一个假定为真的命题
例如:如果 a=ba = ba=b 且 b=cb = cb=c,则 a=ca = ca=c
欧几里得几何中的:给定一条直线 lll 和不在直线 lll 上的点 ppp,通过点 ppp 与直线 lll 的平行线有且只有一条
但在球面几何中该公理是错误的
公理必须是:
一致的 consistent :一个命题不能同时为真或为假
完整的 complete :所有命题必须为真或为假
很可惜,根据哥德尔不完备定理,不存 ...
Coursera Algorithms II:算法(第二部分)
无向图 Undirected graphs
图的介绍 Introduction to graph
图:一对对顶点 vertices 用边 edge 连接
路径 path:用边连接在一起的顶点序列
环 cycle:首尾相同的路
如果两个顶点间有路,则这两个顶点相连 connected
图 API Graph API
顶点表示:000 到 V−1V-1V−1 的整数(用符号表将名称与整数转换)
public class Graph { Graph(int V) Graph(In in) void addEdge(int v,int w) Iterable<Integer>adj(int v) int V() int E() String toString()}
一些关于度数的处理:
public static int degree(Graph G, int v) { int degree = 0; for (int w : G.adj(v)) degree++; return ...
Coursera Algorithms I:算法(第一部分)
并查集 union-find
动态连通性 dynamic connectivity
将对象命名为 000 到 N−1N-1N−1 ,使用整数作为数组索引(略去无关细节,是符号表的一个应用)
“连通”是一个等价关系:
反身性:ppp 连通 ppp
对称性:若 ppp 连通 qqq,则 qqq 连通 ppp
传递性:若 ppp 连通 qqq,qqq 连通 rrr,则 ppp 连通 rrr
连通分量 connected components:连接在一起的最大集合
快速查找 quick find
如果 id[p]==id[q],则 p 和 q 连通
public class QuickFindUF { private int[] id; public QuickFindUF(int N) { id = new int[N]; for (int i = 0; i < N; i++) id[i] = i; } public boolean connected(int p, int q) ...
UCB CS61B:数据结构与算法
介绍
先来个Helloword:
public class Helloworld { public static void main(String[] args) { System.out.println("Hello world"); }}
Java 的特点:
所有代码都必须在类里面
语句组用大括号,语句末用分号
变量使用前先声明
变量类型是确定的,且不可变(静态语言)
注意public,private等
函数参数需要声明类型,返回值也是
所有 Java 中的函数都是方法
确定变量类型的优点:
运行速度快
可读性强
减少类型错误
缺点:
代码复杂
类 class 的使用
假如有这样一个类:
public class Dog { public int weight; public Dog(int startingweight) { weight = startingweight; } public static void ...
Stanford CS106L:标准C++程序设计
流 Stream
stream 相当于缓冲区 buffer,在不同物件中传输数据
构造 stringstream
#include <iostream>#include <sstream>#include <string>int main() { std::istringstream iss("Initial"); std::ostringstream oss("Initial"); std::string s; iss >> s; oss << s; return 0;}
四个 bits:
Good:准备好读写
Fail:之前的操作失败了
EOF:之前的操作到达了 buffer 的末尾
Bad:外部错误
通常检查 EOF 和 Fail 位的状态
不要大量使用 std::endl,因为每次使用时都会清除一次 buffer,导致效率低下,改为 \n。
还有很多 manipulator 可供使用,例如控制格式的 endl,hex, ...
UCB CS61A:计算机程序的构造与解释
值 Values
在 Python 中0o20为八进制的16,0b1101为二进制13,0x为十六进制。
还有字符串 string,元组 tuple,范围 range,列表 list,字典 dictionary,集合 set
函数 Functions,表达式 Expressions,环境 Environments
定义函数:
def saxb(a, x, b): return a * x + b
写成 λ 表达式(能当作表达式的函数):
lambda a, x, b: a * x + b
Environment 是名称对值的映射
在环境中名称被绑定到值上
最外层环境叫 global environment frame
函数被称为第一类值 first-class values,可以作为某一函数的参数或返回值:
def add_func(f, g): def adder(x): return f(x) + g(x) return adder>>> from math import sin,cos,pi>>> h=ad ...
MIT 18.03:微分方程
一阶常微分方程
形如:
y′=f(x,y)y^{\prime}=f(x,y)
y′=f(x,y)
方向场(作图法)
在平面上取一些点,画短斜线(线素),斜率 = f(x,y)f(x,y)f(x,y),积分曲线(常微分方程的解)为穿过平面每一处与线素相切的曲线。
计算机实现方法
等距取一些点 (x,y)(x,y)(x,y)
计算各点斜率 f(x,y)f(x,y)f(x,y)
画出线素
人类做法
取某个固定的斜率 CCC
作出 f(x,y)=Cf(x,y) = Cf(x,y)=C 的等值线
画出等斜线上一些线素
存在性与唯一性定理
f(x,y)f(x,y)f(x,y) 必须是连续函数(存在性),其对 yyy 的偏导连续(唯一性)
欧拉法
初值问题:
{y′=f(x,y)y(x0)=y0\begin{cases}
y^{\prime}=f(x,y) \\
y(x_0)=y_0
\end{cases}
{y′=f(x,y)y(x0)=y0
公式如下:
{xn+1=xn+hyn+1=yn+hAn其中:An=f(xn,yn)h为取点间隔\begin{cases}
x_ ...