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_ ...
多变量微积分(积分部分)
线积分
标量函数的线积分
ds=d2x+d2y\mathrm{d}s=\sqrt{\mathrm{d}^2x+\mathrm{d}^2y}
ds=d2x+d2y
方法一:若已知 y=f(x)y=f(x)y=f(x),用 f′(x)dxf^{\prime}(x)\mathrm{d}xf′(x)dx 替换 dy\mathrm{d}ydy,然后将 dx\mathrm{d}xdx 分解出来,积分的边界值将是曲线的最左边和最右边的 xxx 值,即
ds=1+f′2(x)dx\mathrm{d}s=\sqrt{1+f^{\prime 2}(x)}\mathrm{d}x
ds=1+f′2(x)dx
方法二:参数化
使用 xxx 和 yyy 作为 ttt 函数,取这两个函数的导数来获得以 dt\mathrm{d}tdt 表达的 dx\mathrm{d}xdx 和 dy\mathrm{d}ydy,即
ds=(dxdt)2+(dydt)2dt\mathrm{d}s=\sqrt{(\frac{\mathrm{d}x}{\mathrm{d}t})^2+(\frac{\mathrm{d}y}{\mathrm ...
多变量微积分(微分部分)
一个 多元函数 指的是输入或输出由多个数字组成。相反,如果一个函数的输入和输出都是单个数字,那么我们称之为 一元函数。
如果一个函数的输出是向量,我们称之为 向量值函数;而输出是一个单个数字的函数,它或者被称为 标量值 函数,或者被称为 实值 函数,这通常在理论数学中比较常见(实是实数的意思)
可视化
多维图形
我们可以在三维空间中绘制点来表示一个具有二维输入和一维输出的函数。
它最终看起来像一个三维的面, 这个面在 xy−xy-xy− 平面以上的高度表示每个点上的函数值。
例: 钟形曲线
函数:f(x,y)=e−(x2+y2)f(x,y)=e^{-(x^2+y^2)}f(x,y)=e−(x2+y2)
图:
等高线地图
选择一组输出值来描述函数,对这些输出值中的每一个,画出一条线,这条线包含且仅包含所有函数值 f(x,y)f(x,y)f(x,y)为输出值的输入值(x,y)(x,y)(x,y)。为了清楚地知道哪条线对应哪个值, 人们通常在每条线旁标注适当的数字.
例:抛物面
函数:f(x,y)=x2+y2f(x,y)=x^2+y^2f(x,y)=x2+y2
图:
参数曲线
具有一维输入和 ...