学习笔记

布尔函数和逻辑门 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 ...

页面排序 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) ...

向量 向量 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​>=a1​i^+a2​j^​+a3​k^ ∣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=a1​b1​+a2​b2​+a3​b3​ 几何上：A⃗⋅B⃗=∣A⃗∣ ...

概率模型与公理 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∪…) ...

比特 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 静态字典：多余的位用于编码一些常用的信息 ...

还原论 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:[] ...

…就这样开始了 …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 ...

复数与复平面 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 ...

计算机早期历史 Early Computing 公认最早的计算设备的算盘，注意不是中国的，而是美索不达米亚文明的，它没有计算的功能，只是用于记录数据。 最早使用计算机 computer 一词的文献是 1613 年的一本书，指的是一种职业，即负责计算的人，他们有时也会使用机器辅助计算，所以渐渐地“计算机”也代指机器。 步进计算器：由莱布尼兹发明，像汽车的里程表 加法：由多个齿轮组成，每当一个齿轮转过 9，它会转回 0，同时让旁边的齿轮前进一个齿 减法：反向旋转 乘除：本质上是加法或减法的叠加 所以它是第一台能做“加减乘除”的机器 计算表：预先算好，也就是早期的打表法，类似与字典之类的工具书，但不够灵活。 Charles Babbage 提出了“差分机”，能近似多项式，但最终没做出来，后来有人历史学家按照它的设计图做了出来，发现确实可以做到。 在做这台机器的过程中，这个人提出了一种“分析机”的概念，是“通用计算机”，和后来的冯诺依曼结构是一种东西，但实在是太超前了，当时仅存在于概念上。 此人被认为是“计算之父” Ada Lovelace 给分析机写了假想的程序，被认为世 ...

方程组的几何解释 二元一次方程组： {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 ...