处理器

ALU used for

1. Load/Store: F = add
2. Branch: F = subtract
3. R-type: F depends on funct field

流水线

提高吞吐率，并未减少单一指令的执行时间（延迟latency）

吞吐率 TP：单位时间内流水线所完成的任务数量或输出结果的数量

$TP=n/T_k=n/[(n+k-1)*δt]$，n为任务数，$T_k$是处理完n个任务所用的时间

加速比 S：完成同样一批任务，顺序执行所用的时间与使用流水线所用的时间之比

$S=T_0/T_k$

效率 E：流水线上的设备利用率，即时空图上，N个任务占用的时空区与K个流水段占用的总时空区之比。由于流水线有建立时间和排空时间，各段并不总是满负荷工作的。

E=n个任务占用的时空区/k个流水段占用的时空区=n/(n-k+1)

在时空图上体现为执行所有指令需要的时间和实际用的时间，多余的时间由建立时间和排空时间造成

5个处理步骤：IF，ID，EX，MEM，WB

冒险

结构冒险

硬件占用：内存读写—IM，DM分开

数据冒险

拿错数据

1. 前推/旁路
2. 重新安排代码避免阻塞

C code for A = B + E; C = B + F

1
2
3
4
5
6
7

lw	$t1, 0($t0)
lw	$t2, 4($t0)
add	$t3, $t1, $t2
sw	$t3, 12($t0)
lw	$t4, 8($t0)
add	$t5, $t1, $t4
sw	$t5, 16($t0)

重新安排代码:

1
2
3
4
5
6
7

lw	$t1, 0($t0)
lw	$t2, 4($t0)
lw	$t4, 8($t0)
add	$t3, $t1, $t2
sw	$t3, 12($t0)
add	$t5, $t1, $t4
sw	$t5, 16($t0)

控制冒险

取错指令

1. 阻塞
2. 分支预测

静态预测

动态预测

当预测错误时，流水线控制必须确保被错误预测的分支后面的指令执行不会生效，并且在正确的分支地址处重新开始启动流水线。

流水线数据通路

流水线寄存器

IF/ID，ID/EX，EX/MEM，MEM/WB

最终的数据通路与控制

数据冒险：旁路与阻塞

冒险条件

前提：写操作(EX/MEM.RegWrite, MEM/WB.RegWrite有效)，写目的寄存器不能是$zero

1a. EX/MEM.RegisterRd = ID/EX.RegisterRs≠ 0 ForwardA = 10

1b. EX/MEM.RegisterRd = ID/EX.RegisterRt≠ 0 ForwardB = 10

2a. MEM/WB.RegisterRd = ID/EX.RegisterRs≠ 0 ForwardA = 01

2b. MEM/WB.RegisterRd = ID/EX.RegisterRt≠ 0 ForwardB = 01

1—Fwd from EX/MEM pipeline reg

2—Fwd from MEM/WB pipeline reg

ForwardA=0：第一个ALU操作数来自寄存器，ForwardB同理

旁路单元

01选通MEM/WB；10选通EX/MEM

==为什么有两个Rt啊？还有下面加的红色语句我也没有理解目的所在==

更复杂的潜在数据冒险：比如一个寄存器对多个数字进行求和运算，一系列连续的指令将会读写到同一寄存器：

1
2
3

add $1,$1,$2
add $1,$1,$3
add $1,$1,$4

第二条指令的EX/MEM数据才是最新的。因此，改变MEM冒险的控制策略：

MEM hazard

if (MEM/WB.RegWrite and (MEM/WB.RegisterRd ≠ 0)
​ and not (EX/MEM.RegWrite and (EX/MEM.RegisterRd ≠ 0)
​ and (EX/MEM.RegisterRd = ID/EX.RegisterRs))
​ and (MEM/WB.RegisterRd = ID/EX.RegisterRs))
ForwardA = 01

if (MEM/WB.RegWrite and (MEM/WB.RegisterRd ≠ 0)
​ and not (EX/MEM.RegWrite and (EX/MEM.RegisterRd ≠ 0)
​ and (EX/MEM.RegisterRd = ID/EX.RegisterRt))
​ and (MEM/WB.RegisterRd = ID/EX.RegisterRt))
ForwardB = 01

Load-Use冒险检测单元

工作在ID级，从而可以在装载指令与紧随其后需要它的结果的指令间插入阻塞

阻塞条件：ID/EX.MemRead and ((ID/EX.RegisterRt = IF/ID.RegisterRs) or (ID/EX.RegisterRt = IF/ID.RegisterRt))

插入空指令：把ID/EX流水线寄存器的EX、MEM、WB级的控制信号都置为0.仍向前传递，但控制信号为0不会进行Reg和MEM的写操作。（事实上只需将RegWrite和MenWrite置为0）

通路

冒险检测控制单元控制PC和IF/ID流水线寄存器的写入，以及在实际控制信号与全0中进行选择的多选器。若冒险条件为真，阻塞并清除所有控制字段。

控制冒险

增加寄存器比较电路，如果参与比较的两个寄存器，是两步之前的ALU结果，可以通过旁路解决冒险。如果参与比较的两个寄存器其中有一个，是前一步的ALU结果或是两步之前load的结果，需要一个阻塞。如果参与比较的两个寄存器其中有一个，是前一步的load的结果，需要两个阻塞。

动态分支预测

分支预测缓存Branch prediction buffer (aka branch history table)：一小块按照分支指令的低位地址索引的存储器区，其中包括一位或多位数据用以说明最近是否发生过分支。

2位预测位

依然需要花费一个时钟周期的开销，去计算分支目标地址。使用延迟分支或分支目标地址缓存

异常

（另一种形式的控制冒险，机制相同，不同的是由异常重置控制信号）

异常程序计数器EPC：保存出错指令的地址+4

协处理器CP0

Jump to handler at 8000 00180

记录引起异常的原因的两种方法

1. Cause寄存器：有一个字段记录引起异常的原因
2. 向量中断，控制权转移到由异常原因决定的地址处

多重中断，硬件对异常进行排序从而使得最先发生异常的指令被中断。优先级最高的异常处理完后，继续处理后面的异常。

非精确中断/非精确异常：在流水线中，将每一个异常与导致该异常的指令对应起来难度很大，EPC中放入相近的值，由操作系统确定精确位置。精确异常是为了支持虚拟存储器。

指令级并行

增加流水线的指令级并行程度：

1. 增加流水线的深度—-更多的重叠
2. 复制计算机内部部件的数量—每个流水既可以启动多条指令—-多发射multiple issue

多发射

CPI可能小于1，可使用IPC

静态多发射（在编译时）

动态多发射（在执行时）

发射槽 issue slot

Speculation 推测：编译器或处理器推测指令结果以消除其他指令对该结果的依赖。

推测错误时需要回卷。 指令重排、缓存结果

静态多发射处理器

使用编译器封装指令并处理冒险，若无可同时发射的，用nop代替

发射包 issue packet：在一个时空周期内发射的多条指令的集合。可有编译器静态生成或处理器动态生成。对一个周期内能发射的多条指令有所限制。

超长指令字VLIW

例：Two-issue packets

One ALU/branch instruction

One load/store instruction

数据通路

数据冒险：

EX数据：同一个包中，can’t use ALU result in load/store

load-use：会增加延迟

调度

Loop: lw \$t0,0(\$s1) # \$t0=array element
​ addu \$t0, \$t0,\$s2 # add scalar in \$s2
​ sw \$t0,0(\$s1) # store result
​ addi \$s1,\$s1,–4 # decrement pointer
​ bne \$s1,\$zero, Loop # branch $s1!=0

循环展开（循环体复制4份）：

寄存器重命名——引入临时寄存器，消除虚假的数据依赖（反相关）

动态多发射处理器

也叫超标量处理器

指令顺序发射，乱序执行，顺序提交。处理器决定每个周期几条指令，硬件保证正确性。

流水线被划分为：取指与发射单元、多个功能单元、一个提交单元（含重排序缓冲区）。每个功能单元有自己的缓冲区（保留站）用于保存操作数和操作。

寄存器重命名

保留站和重排序缓冲区提供寄存器重命名机制。发射指令时，它先被复制到合适的功能单元的保留站。如果操作数在寄存器堆中或重排序缓冲区中可用，那么立即数被复制到保留站中。否则该指令一直缓存在保留站中。若指令已发射，那么操作数对应的寄存器的值可以被覆盖。如果操作数不在寄存器堆中或重排序缓冲区中，那么他应该是某个功能单元的结果，硬件帮助定位该功能单元，计算出结果时直接从功能单元复制到保留站，跳过寄存器堆。

推测

Predict branch and continue issuing

Don’t commit until branch outcome determined

Load speculation

Avoid load and cache miss delay

1. Predict the effective address
2. Predict loaded value
3. Load before completing outstanding stores
4. Bypass stored values to load unit

Don’t commit load until speculation cleared

为什么需要动态调度？

1. 并不是所有的阻塞都可以预知。动态调度在一些指令阻塞时调度其他指令，以掩盖阻塞。
2. 对于分支指令，若采用动态推测而不是用动态调度，会极大限制指令级并行度。
3. 流水线延迟和发射宽度根据处理器的具体实现的不同有很大差别。

多发射的阻碍：窗口期有限、内存访问延迟、带宽受限

动态调度和推测消耗能源

指令集、数据通路和控制的设计之间相互影响

分支预测由处理器完成，以试图确定在条件跳转之后执行将继续的位置，以便它可以从存储器读取下一条指令。

推测执行更进一步，并确定执行下一条指令的结果。如果分支预测是正确的，则使用结果，否则将其丢弃。即使代码中没有实际的条件分支，也可以应用推测执行。处理器可以从通常将连续执行的若干指令确定结果，但是可以例如通过算术溢出中断来停止执行。

计算机的算术运算

乘法

高位HI，低位LO

Instructions

mult rs, rt / multu rs, rt 64-bit product in HI/LO

mfhi rd / mflo rd Move from HI/LO to rd，Can test HI value to see if product overflows 32 bits

mul rd, rs, rt Least-significant 32 bits of product –> rd

除法

浮点运算

数值表示

单精度规格化数：阶码取值范围在1~254之间；尾数可以取任何值。

对于float型，特殊的值：

移码

精度范围

高级语言中可以定义多种数据类型，因此需要存取不同长度操作数的数据传输指令。

对阶的时候，需要小阶向大阶看齐，因为大阶如果向小阶看齐，那么就要左移，不符号规格化的要求。

浮点数乘法运算结果规格化：不需要左移，最多需要一次右移；除法：不需要右移，最多需要一次左移。正常的运算过程下，若尾数为0，则结果的阶码也置为0.

浮点加法不满足结合律

查询过程

parse - convert（Parse Tree -> Logical Query Plan） - apply laws（Improving the L.Q.P） - estimate result sizes - consider physical plans - estimate costs - pick best - execute

选择和投影尽量早做

Parameters for Estimation

M: # of available main memory buffers (estimate)

Kept as statistics for each relation R:

–T(R) : # of tuples in R

–B(R): # of blocks to hold all tuples of R

–V(R, A): # of distinct values for attribute R.A

= SELECT COUNT (DISTINCT A) FROM R

•Physical operators

–to implement physical query plans

–selections, joins

–one-pass, two-pass, (multi-pass)

–based on scanning, sorting, hashing, existing indexes

Crash Recovery

Undo日志

从后向前恢复

例题

Consider a system that uses pure undo logging. After a system crash, we find the following log entries on disk:

\;<T1,A,5>;\, <T1,B,1>; \;<T2,B,11>,<T2,C,8>,\; \;<T3,A,10>;\; <T4,A,11>, <T3,C,7>;<T4,B,22>

The last four actions in the schedule were incrementing each object by 1(e.g.<T4,A,11> was updating A to 12). How many different combinations of values of values for A,B,and C could possibly exist on disk at the time of the system crash?

Redo日志

从前向后恢复

恢复速度极慢 -> 静态检查点

例题

Consider a system that uses pure redo logging. The initial database state was A=0,B=1,C=2. After a system crash, we find the following log entries on disk:

\,<T1,A,5>,\, <T1,B,1>, \,<T2,B,11>,<T2,C,8>,\, \,\,<T3,A,10>,\, <T4,A,11>, <T3,C,7>, <T4,B,22>

How many different combinations of values for A,B, and C could possibly exist on disk at the time of the system crash?

A: 5；B: 11；C: 8。有一种可能

Undo/redo日志

<Ti, X, Old-X-value, New-X-value>

恢复时，从前向后redo完成(有commit)的，从后向前undo未完成的

动态检查点

How to balance job responsibilities and personal interests

我觉得出题人没必要在这种词上面作妖，两种解释都有道理，而根据两外两个题：extracurriculer和leisure，此处应该是爱好的意思。

If this situation continues to worsen, their physical and mental status raises the alarm. Thus, it’s urgent to strike a good balance between working duties and personal hobbies. For one thing, too much work gives rise to immunity deterioration, which causes many health problems. For another, constructive pastime helps us live in a positive cycle.

Therefore, what we should do is to find enough time to develop our hobbies by finishing the task on time and arranging some beneficial activities off work. For example, regular exercise is a commendable way to get relaxed. By doing exercises your body can produce a hormone that makes you recover from exhaustion. What’s more you can transfer your focus from busy job by reading an interesting book or listening to a favorite song, thereby getting your intense nerves calm down.

Notes

workload n. (某一人或组织的)工作量，工作负担

immunity n. 免疫力;受保护;豁免;免除

deterioration n. 恶化，变坏；退化；堕落

commendable adj. 值得赞扬(或嘉许)的

hormone n. 激素;荷尔蒙

thereby adv. 因此;由此;从而

网络流

最大流问题

容量、源点、汇点、流；流f满足容量条件和守恒定理

在边上用剩余的容量向前推（前向边，c(e)-f(e)）， 并且在已经有流的边上向后推（后向边，f(e)，可撤销的容量）， 使它转向一个不同的方向。

剩余图: $G_f$= (V, $E_f$). 具有正的剩余容量的剩余边。$ E_f$= {e} ∪{$e^R$}.

令P是$G_f$中一条简单的s-t路径（增广路径）。bottleneck(P,f)是P上任何边关于流f的最小剩余容量。算法augment(f,P)在G中产生一 个新的流f’.不断调整Gf来获取更大的流量.

1
2
3
4
5
6

Augment(f, P) { 
    b ←bottleneck(P) 
    foreach e ∈P { //宽度优先或者广度优先搜索，代价为 O(m+n)=O(m); 
        if(e ∈E) f(e) ←f(e) + b 
        else f(eR) ←f(e) -b } 
    return f }

1
2
3
4
5
6
7
8
9

Ford-Fulkerson(G,s,t,c){
    foreach e ∈E f(e)←0
    Gf ← residual graph
    while(there exists augmenting path P){
        f ← Augment(f,c,P)
        update Gf
    }
    return f
}

Ford-Fulkerson算法可以在 O(mC)时间内实现

最大流与最小割

v(f)≤c(A,B)，每个流的值是以每个割的容量为上界的。证明：流f的值=A的出度-A的入度≤A的出度=割(A,B)的容量

最大流的值等于最小割

选择好的增广路径

选择了一条瓶颈容量很小的增广路径， 导致收敛很慢！— 选择具有大的瓶颈容量的路径，进展会更大些

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

Scaling-Max-Flow(G, s, t, c) { 
    foreach e ∈E  f(e) ←0 
    ∆←largest power of 2 <= Max of Ce out of s 
    Gf←residual graph
	while(∆≥1) { // 外层While循环的迭代次数至多是 1 + ⎡log2 C⎤ 
        Gf(∆)←∆-residual graph 
        while(there exists augmenting path P in Gf(∆)) { 
            //在∆缩放阶段，每次增广增加的流值至少是∆.
            //在一个缩放阶段增广次数至多是2m
            f ←augment(f, c, P) //一次增广用O(m)时间(包括建立图，找到合适路径)
            update Gf(∆) 
        } 
        ∆←∆/ 2 
    } 
    return f
}

二分匹配问题

构造最大流

构造图G’ = (L ∪R∪{s, t}, E’ ). 连接原图L到R的每条边, 每条边赋予单位容 量；增加一个源点s, 从s到L中的每个结点连接一 条边，每条边赋予单位容量；增加一个终点t, 从R中的每个结点到t连接一 条边，每条边赋予单位容量。

G中最大匹配的数目与所定义的G‘中最大流值相同.

令n=|L|=|R|,m是G的边数，一般假定初始问题中每个结点至少存在一条关联边， 因此m>=n/2.

时间复杂度：C=|L|=n,根据以前O(mC)的界——Ford-Fulkerson算法在 O(mn)时间内找到二部图中的一个最大匹配

NP与计算的难解性

多项式时间规约

如果对于问题Y：能用多项式个标准的计算步骤，加上多项式次调用解问题X的黑盒子来解问题Y，则：Y多项式时间可归约到X，或X至少想Y一样难（相对于多项式时间）

$Y≤_pX$ （有传递性）

如果X能在多项式时间内求解，则Y也能在多项式时间内求解；如果Y能在多项式时间内求解，则X也能在多项式时间内求解。

独立集问题

G=(V,E)，G包含大小至少为k的独立集吗？G包含大小至多为k的顶点覆盖吗？

S是一个独立集当且仅当它的补图V-S是一个顶点覆盖。

集合覆盖：比顶点覆盖更具一般性，顶点覆盖$≤_p$集合覆盖

使用零件归约

合取范式，可满足性问题SAT，3-SAT：三元可满足性

3-SAT$≤_p$独立集

构造：连接一个三角形的三个顶点（需要同时考虑三个三角形，从三个三角形中各取一个点），并把每个项与它的否定项连接起来。

3-SAT$≤_p$独立集$≤_p$顶点覆盖$≤_p$集合覆盖

寻找问题$≤_p$判别问题

有效证书和NP的定义

对于判定问题： A解问题X

存在多项式时间解法的问题的集合P

判断素性：用2到根号N来判断N是否能被这些数整除，算法的时间复杂度是指数级别的；AKS算法为多项式级别。

证书串t包含s是X的“yes”实例的证据。

存在t使得：|t|≤p(|s|)且B(s,t)=yes，则B是问题X的有效验证程序，t是证书。

NP是所有存在有效验证程序的问题的集合

例

独立集问题：

证书：至少有k个顶点的集合；验证程序B：核实这些顶点中的任何两两之间没有边连接。

NP完全问题

电路可满足性

NP问题要么是P，要么是NP完全问题

难问题的部分分类：

1. 包装问题：独立集、集合包装
2. 覆盖问题：顶点覆盖、集合覆盖
3. 划分问题：三维匹配、图着色
4. 排序问题：哈密顿图、哈密顿回路、巡回售货员问题
5. 数值问题：子集和，带开放时间和截止时间的调度问题
6. 约束满足问题：SAT，3SAT

优化模式设计

没有信息丢失、保持函数依赖、冗余量最小、（好的查询性能）

Closure of FD sets（函数依赖集合的闭包）

Closure of a Set of Attributes（传递闭包）

求码

已知R(A,B,C,D,E,…)，R的码是这样一组属性集合S，S的闭包含有R的所有属性，S的子集不能包含R的所有属性。

求码的启发式算法：不在任何函数依赖右边出现的属性必是码的一部分，从未在左边出现的不是码。

E/R图(Conceptual Model)、Relational Schema Design (or Logical Design)Relational Model

无损分解

经常会出现做自然连接后得到的表，比原来的表大的情况——lossy join

BCNF是无损分解

无损连接的chase检验

行数为分解后表的个数，列数为元素个数；对于每一行，已知元素填$a_i$，未知元素写$b_{ij}$，用函数依赖填表，如果出现一行全为a的元素，则为无损连接。

保持函数依赖

enforceable

拆表时，X->Y的X,Y不在一张表中，可能不保持函数依赖

范式

BCNF

所有函数依赖的左边都是superkey。除了平凡的函数依赖(AB->A)

若一个表只有两个属性，一定满足BCNF

分解成BCNF：

1. 找到违背BCNF的函数A->B
2. 求左边的闭包$A^+$，$A^+$拆成一张表，剩下的属性和A是一张表
3. 继续检查拆后的表
4. 将函数依赖的闭包分配给拆分后的表

这样可能会丢函数依赖，所以有了3NF。

3NF

对BCNF的修正

左边X不是superkey，右边A不是prime，则X->A不是3NF

保持函数依赖和无损连接的3NF模式分解

–求最小函数依赖集合和关系模式的候选码；

–按函数依赖左部相同原则进行分组，每个组的所有属性形成分解后的关系模式；

–如果某个关系模式被另一个关系模式所包含，删除该关系模式；

–判断候选码是否包含在某个关系模式中，如果包含则结束；如果不包含，将其中一个候选码作为关系模式加入到关系模式中。

多值依赖—>第四范式

X ->->Y

多个多值依赖在一张表中，则违背4NF

例题

Relation R(A，B，C) satisfies the multi-valued dependency A->->B, and has (possibly among others) the following tuples in its current instance: (0, 1, 2), (0, 3, 4), and (1, 5, 6).

Which of the following tuples is not necessarily in the current instance of R?

(a)(0; 1; 4) (b) (0; 3; 2) (c) (0; 5; 2) (d) None of the above.

The following three questions refer to a relation R(A, B, C, D, E) with functional dependencies A->B, BC->D, and E->C.

Question 1: The number of keys of R is:

​ (a) 1 (b) 2 (c) 8 (d) 11

Question 2: Which of the following functional dependency does not necessarily hold in R?

​ (a) AC -> D (b) AE -> C (c) BC -> B (d) CE -> D

Question 3: If we project R onto S(B, C, D, E), which of he following functional dependencies holds in S and also does not violate the BCNF condition for S?

​ (a) BC -> D (b) BE -> D (c) B -> E (d) E -> C

判断无损连接的算法

•已知R<U,F>，U={A,B,C,D,E}

•F={AB ->C, C ->D, D ->E}

•R的一个分解R1(A,B,C),R2(C,D),R3(D,E)

•已知R<U,F>，U={A,B,C,D,E}

•F={A->C,B->C, C ->D, DE ->C,CE ->A}

•R的一个分解R1(A,D),R2(A,B),R3(B,E),R4(C,D,E),R5(A,E)

最小函数依赖集

最小函数依赖集F：

F中的任意函数依赖右边只有一个属性，函数依赖缺一不可，左边的属性不能再少了

F的最小依赖集不一定是唯一的。

找的时候，去掉一个，看能不能由其它函数依赖推出它

2NF：码的一个子集决定了一个非主属性，则违背2NF

例题

•下列关系模式最高属于第几范式：

–R(ABCD), F={B→D,AB→C} 1NF

–R(ABCDE),F={AB→CE,E→AB,C→D} 2NF 码：(AB),E

–R(ABCD),F={B→D,D→B,AB→C} 3NF

–R(ABC),F={A→B,B→A,A→C} BCNF

–R(ABC),F={A→B,B→A,C→A} 2NF

–R(ABCD),F={A→C,D→B} 1NF

–R(ABCD),F={A→C,CD→B} 1NF

例：首先关系模式R满足原子性，所以是满足第一范式的。并且有函数依赖可以得到所有的非主属性都完全依赖于码，所以是第二范式。但是由于第二个依赖中SD不是码并且M不是键属性，所以不满足3NF的定义。

关系查询语句

$R:=R_1∩R_2，R:=R_1∪R_2，R:=R_1-R_2$

$R_3:=R_1×R_2\ (from\ R_1,R_2)，R_1:=\sigma_C(R_2)\ (where\ condition)，R_1:=π_L(R_2)\ (select\ L)$

投影操作(projection)会去掉重复的元组

$\theta$-连接：先做笛卡尔积$R_1×R_2$，再做选择$\sigma_C$，出来的结果列数等于R1和R2列数之和

自然连接：相同的列名合成一列

重命名：$R_1 := ρ_{R_1(A_1,…,A_n)}(R_2) $，简单记为：$R_1(A1,…,An) :=R_2$

对于set:S ∪ S = S ；对于bag:S ∪ S != S

$R÷S$：用于“for all”的查询

例题

\1. 查询数学系(MA)全体学生

\2. 查询学生的姓名和所在的系

\3. 查询年龄小于20岁的学生的学号和姓名

\4. 查询选修了‘C1’课的学生学号和姓名

\5. 查询至少选修了一门其直接先行课为’C1’课程的学生姓名

\6. 查询选修了全部课程的学生号码和姓名

\7. 将新开课<‘C6’,’Pascal’,’-’>插入到关系C中

\8. 将S1学生的‘C1’课成绩改为‘B’

思考题：

查询不学‘C2’课的学生姓名和年龄

•a) Consider relations R(A,B) and S(B,C) where T(R) = 5000, T(S) = 3000, and B is a primary key on S. The expected number of tuples in R 自然连接 S is less than or equal to 3000.FALSE

•b) Consider two relations R(A, B, C) and S(A, D, E), sharing a common attribute A. It is known that R.A is a foreign key referencing S.A, and that S.A is the primary key of relation S. Then the estimated size of R 自然连接 S is T(R).TRUE

theta连接(包括自然连接)运算满足交换律

假设有m层楼，n个鹰蛋，最高从哪层楼扔下时蛋不会碎？f(m, n)为m层楼，n个鹰蛋所需次数。在第i层试探时：1、鹰蛋摔破，下一步只有n-1个鹰蛋，总楼层数缩减为i-1；2、鹰蛋没有摔破，那么鹰蛋总数不变，还是n个，楼层数则缩减为m-i层。递归在以下3个状态结束：1）如果鹰蛋只剩1个，对所有的楼层进行穷举；2）如果楼层是0，则需要试探0次； 3）如果楼层是1，则需要只需要试探1次。

要保证能测出蛋恰好会碎的楼层, 并使此策略在最坏情况下所扔次数最少

动态规划的状态转移：F(m,n)= MIN{ MAX{ F(i-1, n-1) + 1, F(m-i, n)+1}} (0 < i < m)

递归的过程中会重复的解，通过array[M][N]来保存子问题的结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

const int nfloor = 100;
const int negg = 2;
 
#define MAX(a, b) (a) > (b) ? (a) : (b)
 
int arr[nfloor][negg];
 
int test_egg(int nfloors, int neggs)
{	
	if(neggs <= 1)
		return nfloors;
 
	if(nfloors == 0)
		return 0;
 
	if(nfloors == 1)
		return 1;
 
	int min = nfloor;
 
	if(arr[nfloors-1][neggs-1] != 0)
		return arr[nfloors-1][neggs-1];
 
	for(int i = 1; i < nfloors; i++)
	{
		int a = test_egg(i-1, neggs-1) + 1;	
		int b = test_egg(nfloors - i, neggs) + 1;
		int v = MAX(a, b); //有两种情况，要求最坏情况下的所需次数
 
		if(min >  v)
			min = v;//记录所有扔法中次数最少的
	}
 
	arr[nfloors-1][neggs-1] = min;
 
	return min;
 
}
 
int main(int argc, _TCHAR* argv[])
{
 
	memset(arr, 0, nfloor*negg*sizeof(int));
	int a = test_egg(nfloor,negg);
 
	return 0;
}

How to balance work and leisure

Along with the development of the society, more and more problems are brought to our attention; one of the most serious problems is how to balance between work and leisure. People have different attitudes towards the problem.

It is generally agreed that work has been playing an increasingly important role in our life, because we need to work to earn more money for life. But if people put too much time on work, their health condition will be damaged and suffer from kinds of diseases. The sub health among workers has attracted extensive attention of the society, which can be found in TV programs, newspapers, university classes and many aspects of our everyday life. Thus, when people have completed the work responsibility, they should spend some time on personal leisure. Then they could get some rest both physically and mentally, and have better conditions for tomorrow’s work. However, if people invest too much time on leisure, their career developments maybe affected and lost opportunities for a better life.

From what has been discussed above, we may safely draw the conclusion that people should ensure their leisure time after work.

how to balance academic study and extracurricular activities

It is generally agreed that academic study has been playing a crucial role in students’ life. Nevertheless, we should not neglect the equal importance of extracurricular activities which can help us to build confidence and enhance overall abilities.

A number of factors might account for participating in both academic study and extracurricular activities. With respect to academic study, one of the most common factors is to facilitate our academic competence. There’s no doubt that study is the priority to students, and the academic performance, to a large extent, determines whether we can enter a prestigious school and get a decent job. As for extracurricular activities, it is worth mentioning that it can supplement what we cannot learn from schools, such as the ability of critical thinking, problem-solving and addressing interpersonal relationship.

In view of how to balance academic study and extracurricular activities, effective measures should be taken into consideration. In my perspective, the most useful technique is to promote our efficiency. Only if we can manage our time well, we can have more time to do the both things. To be more specific, a to-do list is highly recommended so that we can draw a clear picture of what we are going to do and distribute time to academic study and extracurricular activities in a more effective and balanced way. With the efforts concerned, the imbalance will no longer be a problem.

Notes

个人感觉这篇范文写跑题了，重点在how，不应该花大量篇幅去写why.

With respect to 考虑到，关于

We must plan with respect to the future. 我们必须对未来有个打算。

facilitate 促进；促使；使便利

priority n. 优先事项;最重要的事;首要事情;优先;优先权;重点;(车辆的)优先通行权

to a large extent 在很大程度上

prestigious [preˈstɪdʒəs] adj. 有威望的;声誉高的

supplement n.补充(物)，(报纸的)增刊，附录 v. 增补;补充

动态规划

带权的区间调度

对区间j定义p(j)为使得区间i与j不相交的最大的标记i < j, i是最右边的与j不冲突的区间。
$$
OPT(j)=\begin{cases}
0,\quad if\ j=0 \\
max{v_j+OPT(p(j)),OPT(j-1)},\quad otherwise
\end{cases}
$$

递归的备忘录形式 自顶向下

用一个数组M[0…n]保存中间计算结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14

Input: n,  s1,...,sn,  f1,...,fn,   v1,...,vn
sort jobs by finish times so that f1 <= f2 <=...<= fn //O(nlogn)
compute p(1)，p(2),...,p(n) //如果已对开始时间排序，只需O(n)

for j-1 to n
	M[j]=empty
M[0]=0;

M-Compute_Opt(j){ //O(n) ，每次递归时，M[]被填充一个，至多有2n次递归调用
    if (M[j] is empty){
        M[j]=max(wj+M-Compute_Opt(p(j)),M-Compute_Opt(j-1))
    }
    return M[j]
}

输出最优解 O(n)

j属于一个区间集合{1,…,j} 的最优解当且仅当：$v_j+OPT(p(j)) > OPT(j-1)$

1
2
3
4
5
6
7
8
9

Find-Solution(j){
    if(j=0)
        output nothing
    else if(vj+M[p(j)] >M[j-1])
        print j
        Find-Solution(p(j))
    else
        Find-Solution(j-1)
}

迭代算法计算M[] 自底向上

Input: n, s1,…,sn, f1,…,fn , v1,…,vn

Sort jobs by finish times so that f1≤f2≤… ≤fn.

Computep(1), p(2), …, p(n)

Iterative-Compute-Opt { //O(n)

​ M[0] = 0 forj = 1 to n

​ M[j] = max(vj+ M[p(j)], M[j-1])

}

区别动态规划与分治策略：子问题是否独立

分段的最小二乘

罚分度量函数: E + c L 在所有直线上的平方误差之和E，直线的数目L

OPT(j) =对于点pi, pi+1, . . . , pj的最优解

e(i, j) = 关系到pi, pi+1, . . . , pj的任何直线的最小误差
$$
OPT(j)=\begin{cases}
0,\quad if\ j=0 \\
min_{1≤i≤j}{e(i,j)+c+OPT(i-1)},\quad otherwise
\end{cases}
$$

自底向上

INPUT: n, p1,…,pN,c

Segmented-Least-Squares() {

​ M[0] = 0

​ for j = 1 to n

​ for i = 1 to j

​ compute the least square error eij for the segment pi,…, pj //O(n)
​ for j = 1 to n

​ M[j] =$min_{1≤i≤j}{e(i,j)+c+OPT(i-1)}$ //O(n^2)

​ return M[n]
}

总的算法代价是O(n^3)；如果预先计算了统计信息e(i, j) ，那么代价就是 O(n^2)

通过数组M 向回寻找计算最优的划分

Find-Segments(j)

​ If j=0 then

​ 不用输出

​ Else

​ 找一个使得e(i,j)+c+M[i-1]最小的i

​ 输出这一段{pi,…,pj}作为直线段，以及输出递归函数Find-Segments(i-1)的结果

End if

背包问题

增加一个变量
$$
OPT(i,w)=\begin{cases}
0,\quad if\ i=0 \\
OPT(i-1,w),\quad if\ wi>w \\
max{OPT(i-1,w),vi+OPT(i-1,w-wi)},\quad otherwise
\end{cases}
$$
自底向上算法，填满一个n*W的二维数组

Input: n, w1,…,wN, v1,…,vN

for w = 0 to W

​ M[0, w] = 0

for i = 1 to n

​ for w = 1 to W

​ if(wi> w)

​ M[i, w] = M[i-1, w]

​ else

​ M[i, w] = $max{OPT(i-1,w),vi+OPT(i-1,w-wi)}$

return M[n, W]

Θ(nW)，伪多项式。在O(n)时间内找到最优集合。

RNA二级结构

没有尖的转弯：S中每个对的两端被至少四个插入的碱基所分割. 即如果(bi, bj) ∈S, 那么i < j -4.
$$
OPT(i,j)=\begin{cases}
0,\quad if\ i≥j-4 \\
max{OPT(i,j-1),1+max_t{OPT(i,t-1)+OPT(t+1,j)}},\quad otherwise
\end{cases}
$$
$max_t$遍取所有的t,使得bt与bj是一对被允许的碱基.

存在O(n^2)个子问题;每次求值用O(n)时间,总运行时间是O(n^3)

序列比对

空隙罚分δ; 不匹配罚分$α_{pq}$

一个比对M是一些有序配对xi-yj 的集合，每一项至多出现在一个配对中， 而且没有配对交叉.
$$
OPT(i,j)=\begin{cases}
jδ,\quad if\ i=0 \\
min\begin{cases}
α_{x_iy_j}+OPT(i-1,j-1)\quad\\
δ+OPT(i-1,j)\quad \\
δ+OPT(i,j-1)\quad
\end{cases}\quad otherwise\\
iδ,\quad if\ j=0
\end{cases}
$$

算法

Sequence-Alignment(m, n, x1x2…xm, y1y2…yn, δ, α) {

for i = 0 to m M[0, i] = iδ

for j = 0 to n M[j, 0] = jδ

for i = 1 to m

​ for j = 1 to n

​ M[i, j] = min(α[xi, yj] + M[i-1, j-1], δ+ M[i-1, j], δ+ M[i, j-1])

returnM[m, n]
}

时间和空间复杂度：Θ(mn)

线性空间的序列比对

Space-Efficient-Alignment(X,Y)

​ 数组B[0…m,0…1]

​ 初始化对每个i令B[i,0]=iδ

​ For j=1,…,n

​ B[0,1] =jδ

​ For i=1,…,m

​ B[i,1]= min(α[xi, yj] + B[i-1, 0], δ+ B[i-1, 1], δ+ B[i,0])

​ Endfor

​ 将B的第一列移到第0列来为下一次迭代留出空间

​ 对每个i修改B[i,0]=B[i,1]

​ Endfor

O(mn)的时间与O(m)的空间.

Divide-and-Conquer-Alignment(X,Y)

令m是X中的符号个数

令n是Y中的符合个数

If m<=1或N<=2, then

​ 使用Alignment(X,Y)计算最优比对

调用Space-Efficient-Alignment(X,Y[1:n/2])

调用Backward-Space-Efficient-Alignment(X,Y[n/2+1:n])

令q是使得f(q,n/2)+g(q,n/2)达到最小的指标

把(q,n/2)加到全局表P中

Divide-and-Conquer-Alignment(X[1:q],Y[1:n/2])

Divide-and-Conquer-Alignment(X[q:m],Y[n/2:n])

返回P

采用待定系数法式的归纳法可以证明算法Divide-and-Conquer在长度为m与n的串上运行时间是O(mn).

图中的最短路径

OPT(i, v) 表示至多使用i条边的v-t最短路径的最小费用。
$$
OPT(i,v)=\begin{cases}
0,\quad if\ i=0 \\
min{OPT(i-1,v),min_{(v,w)∈E}{OPT(i-1,w)+c_{vw}}},\quad otherwise
\end{cases}
$$

算法

Shortest-Path(G, t) {

foreach node v ∈V

​ M[0, v] ←∞

M[0, t] ←0
for i = 1 to n-1

​ foreach node v ∈V

​ M[i, v] ←M[i-1, v]

​ foreach edge (v, w) ∈E

​ M[i, v] ←min { M[i, v], M[i-1, w] + cvw}
}

表M有n^2项，每项O(n)时间计算，时间复杂度：O(n^3)，空间复杂度：O(n^2)

改进

对每个结点v更新一个值M[v]，即我们至今已经找到的从v到t的最短路径的长度。为了帮助复原这条最短路径，记录每个结点通向终点t的路径上它后面的第一个结点；只要距离M[v]更新，我们就更新 这个值(first[v]).

O(mn)时间

$M[v]=min(M[v],min_{w∈V}(M[w]+c_{vw}))$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

PUsh-Based-Shortest-Path(G,s,t){
    foreach node v∈V{
        M[v]←∞ 
        successor[v]←∅
    }
    M[t]=0
    for i=1 to n-1{
        foreach node w∈V{
            if(M[w]has been updated in previous iteration){
                foreach node v such that (v,w)∈E {
                    if(M[v]>M[w]+Cvw){
                        M[v]←M[w]+Cvw
                        successor[v]←w   
                    }
                }
            }
            if no M[w]value changed in iteration i, stop.
        }
    }
}

图中的负圈

增加一个终点t。如果G有n个结点且 OPT(n,v)!=OPT(n-1,v),那么一条从v到t 的费用OPT(n,v)的路径P包含一个圈C,并 且C有负费用。