UCB Data100:数据科学原理与技术
课程概述 Course Overview
在数据科学中有很多工具,但它们不会思考
The purpose of computing is insight, not numbers.
计算的目的是洞察,而不是数字
——Hamming
数据采样和概率 Data Sampling and Probability
偏差:
选择偏差:可能不包括或有利于特定的群体
回应偏差:人们不会真实回答
不回应偏差:人们不一定回答
有替换的随机取样:避免一个人被选到两次
简单随机取样:一个人可能被选到两次
在样本总量很大时,两者表现相似
二项式/多项式概率
Pandas
引入:
import pandas as pd
生成的是 DataFrame 类(类似于一张表):
elections = pd.read_csv("elections.csv")
这个类有丰富的API,这里只介绍其中的一部分
索引
elections.head(5):获取前五行;.tail 同理
loc 通过标签 label 选择物品,有行标签和列标签
loc 的参数可以是:
列表:elections.l ...
CMU 15-213:计算机系统导论
比特,字节和整数 Bits, Bytes, and Integers
布尔代数
位移操作:
左移 x << y:丢弃左边多余的位,右边补 0
右移 x >> y:
逻辑右移:左边补 0
算术右移:左边重复最高位
c 语言默认为算术右移,Java 用 >>> 区分出逻辑右移
当位移长度 < 0 或 > 字长时,为定义
数字范围:
无符号:UMin = 0=000…00 = 000…00=000…0,UMax = 2w−1=111...12^w - 1 = 111...12w−1=111...1
补码:TMin = −2w−1=100...0-2^{w-1} = 100...0−2w−1=100...0,TMax = 2w−1−1=011...12^{w-1}-1 = 011...12w−1−1=011...1
其它值:−1=111...1-1 = 111...1−1=111...1
编码整数:
无符号:B2U(X)=∑i=0w−1xi2iB2U(X) = \sum_{i=0}^{w-1} x_i 2^iB2U ...
Coursera Nand2Tetris:依据基本原理构建现代计算机:从与非门到俄罗斯方块
布尔函数和逻辑门 Boolean Functions and Gate Logic
布尔逻辑 Boolean Logic
与或非
布尔函数合成 Boolean Functions Synthesis
不同的布尔函数能表达相同的意思
所有布尔函数都可以用“与或非”表示
进一步,都可以用“与非”表示 (x OR y) = NOT(NOT(x) AND NOT(y))
更进一步,可以用 NAND (AND 的否定)表示(NOR 也可以):
NOT(x) = (x NAND x)
(x AND y) = NOT(x NAND y)
故可以仅使用 NAND 构造整个逻辑
逻辑门 Logic Gates
基本逻辑门,复合逻辑门
将复合逻辑门看作黑盒,关心接口,不关心实现
硬件描述语言 Hardware Description Language
// 接口CHIP Xor { IN a, b; OUT out; PARTS: // 实现 Not(in=a, out=nota); Not(in=b, out=notb); And(a=a, b=n ...
UCB CS126:概率论
页面排序 PageRank
模型
网页间的链接构成一副图
如果有高名次的页面指向一个页面,则该页面有较高的名次,即
π(i)=∑j∈Xπ(j)P(j,i),i∈Xπ(i) = \sum_{j ∈ X} π(j) P(j, i), i ∈ X
π(i)=j∈X∑π(j)P(j,i),i∈X
注意其中 P(j,i)P(j, i)P(j,i) 为指向 iii 的链接,单位化后的结果
写成矩阵:
π=πPπ = π P
π=πP
还有一重单位化的约束:
∑i∈Xπ(i)=1\sum_{i ∈ X} π(i) = 1
i∈X∑π(i)=1
马尔科夫链
可以用公式定义马尔科夫链:
P[X(n+1)=j∣X(n)=i,X(m),m<n]=P(i,j),∀i,j∈X,n≥0P[X(n+1) = j | X(n) = i, X(m), m < n] = P(i, j), ∀ i, j ∈ X, n ≥ 0
P[X(n+1)=j∣X(n)=i,X(m),m<n]=P(i,j),∀i,j∈X,n≥0
其中 X(n)X(n)X(n) 表示时间 nnn 时的状态,X(0)X(0)X(0) ...
MIT 18.02:多变量微积分
向量
向量 vectors:有方向 A⃗\vec{A}A 和长度 ∣A⃗∣|\vec{A}|∣A∣,表示有向线段
用分量形式表示:
A⃗=<a1,a2,a3>=a1i^+a2j^+a3k^\vec{A} = <a_1, a_2, a_3> = a_1 \hat{i} + a_2 \hat{j} + a_3 \hat{k}
A=<a1,a2,a3>=a1i^+a2j^+a3k^
∣A⃗∣=a12+a22+a32|\vec{A}| = \sqrt{a_1^2 + a_2^2 + a_3^2}
∣A∣=a12+a22+a32
向量加法:首尾相连,平行四边形法则,对角线是 A⃗+B⃗\vec{A} + \vec{B}A+B 和 B⃗−A⃗\vec{B} - \vec{A}B−A,加法对分量形式也有效
点乘 dot product:
A⃗⋅B⃗=a1b1+a2b2+a3b3\vec{A} ⋅ \vec{B} = a_1b_1 + a_2b_2 + a_3b_3
A⋅B=a1b1+a2b2+a3b3
几何上:A⃗⋅B⃗=∣A⃗∣ ...
MIT 6.041 & 6.431:概率系统分析与应用概率
概率模型与公理 Probability Models and Axioms
样本空间 sample space:
离散,如抛骰子
连续,如在面积中取某个子区域
事件 event 是样本空间的一个子集
公理:
非负:P(A)≥0P(A) ≥ 0P(A)≥0
标准化:P(Ω)=1P(Ω) = 1P(Ω)=1
加法:如果 A∩B=∅A ∩ B = \emptysetA∩B=∅,则 P(A∪B)=P(A)+P(B)P(A ∪ B) = P(A) + P(B)P(A∪B)=P(A)+P(B)
离散一致律 Discrete uniform law:若所有结果等可能,则
P(A)=A 中的元素数量样本空间的总元素数量P(A) = \frac{\text{A 中的元素数量}}{\text{样本空间的总元素数量}}
P(A)=样本空间的总元素数量A 中的元素数量
计算概率 = 计数
连续一致律 Continuous uniform law:落在面积中半部分的概率
可数加法公理:如果 A1,A2,…A_1, A_2, …A1,A2,… 是互斥 disjoint 事件,则
P(A1∪A2∪…) ...
MIT 6.050J & 2.110J:信息与熵
比特 Bits
布尔位:与、或、非、抑或等运算
电路位:
有回路的电路位可能更复杂,叫时序逻辑电路 sequential logic
控制位:例如 (if (and (< x 0) (> y 0)) (define z 0)),特点在于有短路效应
物理位:若一个位可以被储存或转移,则其必定有物理形式
量子位:
可逆性 reversibility:量子数学中的函数是可逆的
叠加性 superposition:27% yes 73% no
纠缠 entanglement:量子纠缠
经典位:0V-0.2V 为逻辑假,0.8V-1V 为逻辑真
编码 Codes
符号空间大小:1、2、2 的幂次方、有限、无限可数、无限不可数
二进制编码十进制 BCD
基因编码
电话地址编码
IP 地址
ASCII
00000000 表示 NUL,被忽略
11111111 表示删除
固定长度和可变长度编码
摩尔斯编码
压缩 Compression
分成两类:有损(可逆)和无损(不可逆)
可变长度编码
运行长度编码:把 abbbbb 编码为 a1b5
静态字典:多余的位用于编码一些常用的信息 ...
Haskell MOOC Part 2
还原论 Reductionism
懒惰和纯净
懒惰 lazy 是一个值如果不需要,则不会计算,如
f x = f x -- 会陷入无限循环g x y = xg 2 (f 1) ==> 2 -- 不会陷入无限循环,因为 (f 1) 没有求值
等价推理
对于相同的输入总是返回相同的值
无限列表
Prelude> repeat 1 -- 会陷入死循环[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1^CPrelude> take 10 $ repeat 1 -- 不会陷入死循环[1,1,1,1,1,1,1,1,1,1]Prelude> repeat 1 !! 133371
运行原理
C 等语言从内向外求值
Haskell 从外向内求值
这是 Haskell 执行 length 的过程
length (map not (True:False:[])) ==> length (not True : map not (False:[])) ==> 1 + length (map not (False:[] ...
Haskell MOOC Part 1
…就这样开始了 …And so It Begins
Haskell
函数式 Functional:程序完全由函数构成,函数可以以函数为参数或返回函数,循环结构是递归
纯净 Pure:函数没有副作用
懒惰 Lazy:只有需要时才会计算值
强类型 Strongly typed:每个值和表达式都有类型,在编译时检查类型错误
类型推断 Type inferred:编译器可以推断类型
垃圾收集 Garbage-collected:不需要手动管理内存
编译 Compiled: Haskell 是编译型语言
GHCi
命令行界面运行 stack ghci 进入交互模式
ghci> 1+12ghci> "asdf""asdf"ghci> reverse "asdf""fdsa"ghci> :type "asdf""asdf" :: Stringghci> tail "asdf""sdf"ghci> :ty ...
MIT 18.04:复变函数
复数与复平面 Complex algebra and the complex plane
复数的定义及基本术语
−1=±i\sqrt{-1} = ± i
−1=±i
数学中用 iii,工程中常用 jjj,称作虚数 imaginary number
算术基本定理:nnn 阶的多项式有 nnn 个复数根(包括重根)
复数可表示为:
z=x+yiz = x + yi
z=x+yi
其中 x,yx,yx,y 都是实数 real number
xxx 称为实部 real part
yyy 称为虚部 imaginary part,虚部不包括 iii
复数的集合用 CCC 表示
复数的加法、减法、乘法、除法
共轭复数 complex conjugation:
x+iy‾=x−iy\overline{x + iy} = x - iy
x+iy=x−iy
有用的性质:若 z=x+iyz = x + iyz=x+iy,则
zz‾=(x+iy)(x−iy)=x2+y2z\overline{z} = (x + iy)(x - iy) = x^2 + y^2
zz=(x+iy)(x−iy)=x2+y2
...