统计与数据分析基础W2(2):概率论回顾Final

2020-09-24

变量变换求卷积P152

$Y=f(X)$ ， $f(X)$ 是一个严格单调递增， $X=h(Y)$ ,是其反函数。

设二元随机变量 $(X,Y)$ 联合密度函数为 $p(x,y)$ ，如果函数 $\begin{cases}u=g_1(x,y)\v=g_2(x,y)\end{cases}$ ，有连续偏导数，且存在唯一的反函数。 $\begin{cases}x=x(u,v)\y=y(u,v)\end{cases}$ ,其变换的雅可比行列式 $J$ 。

则 $(U,V)$ 的联合密度函数为： $p(u,v)=p(x(u,v),y(u,v))|J|$

多元雅可比行列式

$|J|_{n\times n}$

$J=|\frac{\part(h_1,h_2,…,h_n)}{\part(y_1,y_2,…,y_n)}|=|\frac{\part{h_i}}{\part{y_j}}|$ ，省去了转制

此时多元的密度相同，把反函数带进去再求雅可比行列式。

例子：书上例3.3.10

X和Y是i.i.d.

正态验证独立的另一种思路，先验证独立性再求边际要好求很多。

条件分布与条件期望

联合密度和边际密度的关系

定义

remarks

连续场合的全概率公式和贝叶斯公式

贝叶斯公式并不一定意味着贝叶斯学派。

即贝叶斯公式很counts.贝叶斯是利用已知信息对未知信息进行推断。

p(y|x)= $\frac{p(x,y)}{p(x)}$

全概率公式：利用某一个分割来求一个事件的概率(加权来算)

连续：加权求和->求积分

连续贝叶斯公式

联合正态，边际正态，条件正态

条件期望

核心： $E(Y|X=x)=\int y·p(y|x)dy$

remarks：

$E[Y|X=x]$ 是x的函数
$E(Y|X)$ 是一个变量X的函数，它一定是随机变量。它自己也有期望。

$E_X(E_Y(Y|X))=E(X)$ ，重期望定理。

平均成绩：w1✖️男生均分+w2✖️女生均分=全班均分

例题：经典例题：3.5.7

随机个随机变量的和也可以通过重期望公式去解(书上例题)。

冲期望的重要性质，书上习题：

$E(g(X)·Y|X)=g(X)·E(Y|X)$ ，在线性模型的推导比较有用。

P185-15

概率不等式

马尔可夫不等式(tailProb)
切比雪夫不等式(tailProb)

尾概率控制风险

柯西-施瓦滋不等式：二阶内积小于二阶平方

$(Cov(X,Y))^2\le Var(X)Var(Y)$

证明Cov是在[-1，1]区间的
琴生不等式f是凸函数

$f(E(X))\le E(f(X))$

凸函数:二阶导

证明EM算法的收敛性

三种收敛性

定义4.1.2

$X_1,X_2,…,X_n$ 是一系列的随机变量， $F_i(X)$

X一个r,v是 $F(X)$

弱收敛

应用：CLT的定义

依概率收敛

书上缺乏：下周统计推断公式有用：以概率1收敛

P(lim X_n=X)=1

三种收敛关系之间有强弱之分

以概率1收敛>依概率收敛>弱收敛(按分布收敛)(general)

有时，收依概率收敛于某一常数是有反向符号的

大数定律(LLN)和中心极限定理(CLT)

大数定律

大数定律：用频率，样本均值真的很好用!估计概率

IMG_3688.HEIC

CLT：独立同分布的CLT和独立不同分布的CLT。

和的某一倍数或线形组合，受到正态分布的控制。

收敛到真值且不会太远，LLN度量的误差是可以被控制的

期望存在，方差一定存在。反之不一定成立。

但如果方差不存在，还有中心极限定理嘛？

在现代，基于鞅Martingale的提出，对CLT的独立性也放宽到相关性。[left to do ]

重点

变量变换，条件，条件密度与重期望公式，LLN和CLT到底在说啥。

展开全文 >>

当代数据库管理系统W2:MongoDB的实现原理/数据库系统正确性是如何保证的

2020-09-23

W2:MongoDB的实现原理

前情回顾

memory hierarchy永远不会变的原因是什么？

当有一块（页）被掉入Dram时，会被缓存而不是立刻扔掉。

more >>

展开全文 >>

统计与数据分析基础W2:概率论回顾(2)

2020-09-22

概率论(2)

多项分布：一个骰子被投掷10次，6朝上次数的概率。

统计课讨论pdf

n元正态分布

2.n元正态分布

设 $X$ = $\begin{pmatrix}x_1\x_2\x_3\x_n\end{pmatrix}$ 为n维随机变量，其期望 $\vec\mu\begin{pmatrix}\mu_1\\mu_2\\mu_3\\mu_n\end{pmatrix}$

其方差-协方差矩阵 $\Sigma$ = { $\sigma_{ij}$ } $_{n\times n}$ =Cov{ $x_i,x_j$ }

记实向量 $X$ = $\begin{pmatrix}x_1\x_2\x_3\x_n\end{pmatrix}$ ，如果 $\vec{X}$ 的pdf为P(X=x)= $(2\pi)^{\frac{n}{2}}|\Sigma|^{\frac{-1}{2}}exp(\frac{-1}{2}(x-\mu)^T\Sigma^{-1}(x-\mu))$

那么，称 $X$ 服从n元正态分布，记 $X$ ～ $N_p(\vec{\mu},\Sigma)$

Special Case

当是二元向量时： $N(\mu_1,\mu_2,\sigma_1^2,\sigma_2^2)$

$\mu=(\mu_1,\mu_2)^{T}$ , $\Sigma=\begin{pmatrix}\sigma_1^2&&\rho\sigma_1\sigma_2\\rho\sigma_1\sigma_2&&\sigma_1^2\end{pmatrix}$

3.指数分布族

分布族理解，是一个分布的集合。

定义

设一个随机变量/向量X，其分布列/密度函数(pdf)

为 $p(x)=h(x)exp(\eta(\theta)^TT(x)-F(\theta))$ ，那么称这个随机变量来自于指数分布族。这里 $F(\theta)$ 是 $\theta$ 的函数变换。

这里都是向量。

参数 $\theta\in参数空间\in R^d$ ，参数向量
$\eta(\theta):参数空间->R^p$ 映射，做完变换，p维横向量，与后面的T(x)做内积。
$T(x)$ 是一个p维列向量。(使内积可以计算)，可理解为随机向量。

随机性概念的理解。

$F(\theta)$ 是一个一维/实值函数

向量的例子

验证是不是指数分布族

Exa.1

$p(x)=p^x(1-p)^{1-x}$ 为二点分布。

$p(x)=exp(ln(p^x(1-p)^{1-x}))=expexp(ln(p^x(1-p)^{-x})(1-p)^)=exp(ln(\frac{p}{1-p})^x(1-p))$

= $exp(xln(\frac{p}{1-p})+ln(1-p))$

$h(x)=1,T(x)=x,\theta=p,\eta(\theta)=ln(\frac{p}{1-p})$

Exa.2

验证正态分布也属于指数分布族。

将参数与指数分离，写成乘积的形式。

p(x)= $\frac{1}{\sqrt{2\pi}}(\sigma^2)^{-\frac{1}{2}} exp{-\frac{1}{2}\frac{(x-\mu)^2}{\sigma^2}}$

step1.先讲指数化出来

p(x)= $exp(-ln(\sqrt{2\pi \sigma^2}))exp{-\frac{1}{2}\frac{(x-\mu)^2}{\sigma^2}}$

= $exp(-ln(\sqrt{2\pi \sigma^2})+-\frac{1}{2}\frac{(x-\mu)^2}{\sigma^2})$

= $exp(-ln(\sqrt{2\pi \sigma^2})-\frac{1}{2\sigma^2}(x^2-2x\mu+\mu^2))$

= $exp(-\frac{1}{2\sigma^2}x^2+\frac{1}{\sigma^2}x\mu)+与x无关的参数$

所以，对照上面式子的标准形式

$h(x)=1,T(\vec{x})=(x^2,x)^T,\eta(\theta)^T=(\frac{1}{2\sigma^2},\frac{\mu}{\sigma^2})$

剩下的一堆是与x无关的参数。

$-F(\theta)=-ln(\sqrt{2\pi\sigma^2})-\frac{1}{2\sigma^2}\mu^2$

由上面的例子，离散和连续随机变量都可能来自于指数分布族，有益于对异构数据处理的统一表达。

4.独立性

A,B为随机事件：

A，B独立表示:P(AB)=P(A)P(B)
称 $(x_1,x_2,x_3,…,x_n)^T$ 是random vector,是相互独立的， $F_i(x)$ 是其cdf,则
1. $F(x_1,x_2,x_3,…,x_n)=\Pi F_i(x)=\Pi P(X_i\le x)$ 【这里用事件去推理去理解。联合cdf与边际cdf
离散：

联合分布列 $P(X_1=x_1,X_2=x_2,…,X_n=x_n)=\Pi P(X_i=x_i)$

连续：

$P(X_1,X_2,…,X_n)=\Pi P(X_i)$

重要的是学会去用

5.多元的期望和方差的性质

设(X,Y)是二元随机变量

E[X+Y]=E[X]+E[Y];无条件，基于积分的可加性求得。
若X与Y是独立的，则：
1. 有上面独立的联合概率的条件
  
  E[XY]=E[X]E[Y]
2. Var(X+-Y)=Var(X)+Var(Y)【无论那边是加号还是剪号，我的波动总是增加的！
Var(X+Y)=Var(X)+Var(Y)+2Cov(X,Y)

Var(X-Y)=Var(X)+Var(Y)-2Cov(X,Y)【比较有用

因为独立，协方差为0，上边加号是不变的。
Cov(X,Y)=E[XY]-E[X]E[Y]

独立时，协方差为0.

独立性条件强于协方差
Cov(X,Y)=0,表示线性无关。
当(X,Y)服从二元正态的时候，相关性和独立性等价。
$\rho=\frac{Cov(X,Y)}{\sqrt{Var(x)Var(y)}}$

所以正态分布算covariance远比直接推密度函数效率更高。

6.多元随机变量的函数

极值分布(最大值，最小值分布)

$x_1,x_2,x_3,…,x_n$ 是n个随机变量。

$x_{max}=max(x_1,x_2,x_3,…,x_n)$ ， $x_{max}$ 是一个多元随机变量的函数。

随机变量的函数一定是一个随机变量，我们一定要用分布去刻画。

$x_{min}=min(x_1,x_2,x_3,…,x_n)$

这个的最大应用，水位线的最大值，水坝的高度的建设相关。

例1

若 $X_1,X_2,..,X_n$ 是相互独立的随机变量

若 $Y=x_{max}=max(x_1,x_2,x_3,…,x_n)$ ，

$X_i～F_i(x)$

$F(y)=F(x_1,x_2,x_3,…,x_n\le y)=\Pi_{i=1}^n F(x_1\le y)$
$X_i$ 是同分布的

$F_Y(y)=(F(y))^n$
$X_i$ 是连续随机变量，且 $X_i$ 同分布， $p(x)$ 为 $X_i$ 的概率密度函数。

求Y的pdf

$P_Y(y)=\frac{dF_Y(y)}{dy}=\frac{d[(F(y))^n]}{dy}$

这里堪称一个复合函数求导。

= $nF(y)^{n-1}p(y)$

模型v.s.结论

$X_i$ ~Exp( $\lambda$ )

$p(X)$ = $\lambda exp(-\lambda x),x\ge0$ ;

$F(X)=1-exp(-\lambda x),x\ge0$

Y的密度函数， $P_Y(y)=n(1-exp(-\lambda y))\lambda exp(-\lambda y),y\ge0,0 ,otherwised$

例2

若 $X_1,X_2,..,X_n$ 是相互独立的随机变量

若 $Z=x_{min}=min(x_1,x_2,x_3,…,x_n)$ ，

$F_Z(z)=P(Z\le z)=1-P(Z>z)=1-\Pi P(X_1>z)=1-\Pi_{i=1}^n(1-F_i(z))$
$X_i$ 是同分布的：

$F_Z(z)=1-(1-F(z))^n$
求Z的概率密度函数：

$P_Z(z)=-n(1-F_Z(z))^{n-1}(-p_Z(z))$
$X_i$ ~Exp( $\lambda$ )

$p_Z(z)=n(1-1-exp(-\lambda z))^{n-1}\lambda exp(-\lambda z)$

= $n\lambda(-exp(-\lambda z))^{n-1+1}$ ， $z\ge 0$

注意这里，Z还是一个服从于 $n\lambda$ 的exp分布

pdf最重要的性质是非负性，要以此检查我的计算的正确性。

卷积公式

核心概念

X和Yiid(一般只要求独立，不要求同分布)，求X+Y的分布。

重要结论

$X_1$ ~~N( $\mu_1,\sigma_1^2$ ), $X_2$~~ N( $\mu_2,\sigma_2^2$ ),

$X_1+X_2～N(\mu_1+\mu_1,\sigma_1^2+\sigma_2^2)$

先确定分布，再由期望和方差的关系，不要走密度函数硬推。

n维随机变量独立同分布于正态分布，线性组合也是正态分布
$X_1$ ~~$\Gamma(\alpha_1,\lambda)$ , $X_2$~~ $\Gamma(\alpha_2,\lambda)$

X+Y～ $\Gamma(\alpha_1+\alpha_2,\lambda)$

指数分布 $\Gamma(1,\lambda)$ 相加不是指数分布

卡方分布， $\Gamma(\frac{n}{2},\frac{1}{2})$ ，卡方分布相加还是卡方分布。

展开全文 >>

数据库上机1:MongoDB的安装和使用

2020-09-21

Mac平台安装MongoDB

https://docs.mongodb.com/manual/tutorial/install-mongodb-on-os-x/

官方安装tutoral如上

more >>

展开全文 >>

信息检索W1

2020-09-21

布尔检索

利用AND,OR,NOT将词项连接起来进行查询。

例子：查brutus AND caesar

分别定位再求交集。

求交集的过程转换成数据结构中：求两个有序链表的交集。

【考试】

构建倒排索引的时候posting list要排序？

排序完以后，检索的时间复杂度的代价，O(Len1+Len2)，两个链表的长度之和。

布尔查询的效率瓶颈

每次从最小的开始合并(DF从小到大)

例子：查B AND C AND A

如何调整顺序能提高效率？

将posting lists少的放在最前面来做。

DF:docmuent frequency，这也是df的用处。

布尔检索的例子

2011年快女6进5比赛的新闻如何用布尔检索表达

缺点

构建复杂
没有充分利用词项的频率信息

如汉语中的“的”，“呢”Stop words。
不能对检索结果进行排序

本讲的内容

构建索引的过程(预处理)
如何对索引文档进行处理来得到词典
- 理解文档的概念
- 词条化，理解词条的概念
  
  词条化：将一个个字符流，转化成词条(token)，如何将数据流切成有意义的单元。
- 词项生成，理解词项(term),词项是最终支持搜索的最小单位
倒排记录表
- 更快的合并算法：跳表法(skip list)
- 短语查询的处理及位置信息的倒排索引

more >>

展开全文 >>

操作系统知识点复习总结(期末版)

2020-09-21

这是我在本学期开学的操作系统理论考试复习笔记，针对的更多是个人不会的地方。

教材配套是操作系统设计与实现这本书，也是我们专业课使用的教材。

长上面这个样子。

对照着也有王道408考研书的，虽然表述不同，但大都大同小异，针对的都是操作系统的核心。

操作系统速记

操作系统控制和管理系统内的各种资源，源程序资源不是操作系统应该管理的
系统调用只能通过用户程序间接使用，是操作系统给编程人员的借口，系统调用的目的是请求系统服务。
操作系统与用户的通信接口不包括缓存管理指令
操作系统开机后，被最终加载到RAM。
提高单CPU利用率：多道程序设计，批处理OS的主要缺点是无交互能力。
OS的基本类型：批处理OS分时OS实时OS
多道程序系统的系统开销大
实时系统：抢占式的优先级调度
分时系统：优先级+非抢占
时间片一定，用户数越多，响应时间越长
甘特图CPU运行时间，进程周转时间
中断处理是OS必须提供的功能，
地址映射：重定位需要硬件的支持；时钟管理,中断系统也需要。
中断和异常
用户态执行命令解释程序
系统调用，是OS给用户的借口，用户态，进程切换只可能在和心态。
中断处理程序，PSWR/PC
中断是完成时的提醒，所以”缺页中断”是异常，但是广义来说，缺页中断作为中断，一条指令在执行期间，可能产生多次缺页中断。
执行系统调用的过程，传递系统调用参数，执行中断指令，执行相应的服务程序返回用户态
定时器产生时钟中断后，由时钟中断，所有与时间相关的都更新了。
显然，微内核没有大内核高效和稳定，但系统更可靠。

每一个进程必须有一个唯一的标示：PCB
进程状态的改变：
1. 就绪，除了CPU都有了
2. 阻塞，等待事件发生，等I/O的完成，等待中断的结束，等待其他资源
3. 当I/O完成时，由阻塞进入就绪态。
4. 时间片结束进入就绪态
5. 就绪态不可能直接到阻塞态
6. 进程的阻塞是进程自身的一种主动行为，因此也只有running才可以到wait态。
7. 进程间通信(IPC)需要进程同步和互斥手段的辅助
进程通信机制：共享存储消息传递管道PV原语
进程是拥有资源的基本单位，县城作为调度的基本单位
为啥要有线程？线程开销比进程开销小啊
有新进程进入就绪态不是引起操作系统选择新进程的直接原因
堆栈指针属于PCB但是全局变量不属于PCB
进程创建完成时会进入就绪序列
当就绪队列非空时，操作系统总是繁忙
对进程的管理和控制使用原语
设备分配由I/O系统完成，一种数据结构用来记录不会导致新进程的创建
属于同一个进程的线程也有属于自己的战指针
降低进程优先级的合理时机时进程时间片用完。
操作系统空闲，就绪队列为0，CPU处于空闲状态；当系统中所有进程处于阻塞状态时可能是死锁。
现代OS中，不能进行进程调度与切换的情况：
1. 处理中断
2. 进程在临界区
3. 完全屏蔽中断的原子操作过程
系统吞吐量时单位时间内CPU完成作业的数量，所以CPU完成的作业越多，CPU利用率高
FCFS不可剥夺算法，对长作业有利，长作业属于IO繁忙型，短作业属于CPU繁忙型(相对于SJF和高响应比)
SJF：导致饥饿，饥饿是由于策略调度产生的，死锁是循环等待，是由于系统资源互斥占有从而循环等待产生的。
优先级算法：剥夺式非剥夺式
优先级标准：IO >计算
高响应比优先调度：（等待+服务）/服务
时间片，适用于分时系统，为了多个用户可以及时干预系统，人机交互也应采用时间片轮转调度算法
时间片轮转调度算法是绝对可抢占的
进程处于临界区时可以进行处理机调度(28)
可以满足短作业优先且不会饥饿：高响应比优先
临界区是访问共享资源(临界资源)的那段代码！！！
可以用信号量机制来解决互斥与同步的问题,p/v操作
信号量实现同步：前V后P
信号量实现互斥：p(mutex)v(mutex)
一个进程只有通过管城内的过程才能进入管程访问共享数据
每次仅允许一个进程(任何时候)在管程内执行某个内部过程。管程可以实现进程的互斥和同步。管程是由编程语言支持的进程同步机制，管程中定义的变量只能被管程内的过程访问。
经典IPC问题：
1. 生产者消费者问题：
  
  信号量：标示资源，初始化为资源的数量
  
  p(资源)：要用什么p一下
  
  v(资源)：提供什么v一下
2. p(mutex) do sth on critical section v(mutex)
3. 读者写者问题的三种类型和不同的思路
4. 哲学家就餐问题
某个信号量的处置是n，当信号量n<0,|n|阻塞队列的进程个数。n>=0表示可用资源的个数
临界区是指并发进程访问共享变量段的代码程序。
p操作可能导致进程阻塞
管程定义了共享数据结构和各种进程在该数据结构上的全部操作。
用v操作唤醒，被唤醒进程变为就绪态。

阻塞态->就绪态。
可以被多个进程在任意时刻共享的代码必须是不允许任何修改的代码
如果有进程在等待进入临界区的话，mu tex一定<0
临界区是代码，
互斥使用的资源一定是1.
x.wait()阻塞该进程，并将之插入x的阻塞队列中。
对共享变量的操作需要互斥执行。
死锁
1. 死锁预防
  
  破坏死锁的四个条件
  - 互斥：任意时刻只允许一个进程使用资源【对所有资源进行spooling】
  - 环路等待：顺序资源分配，资源编号，资源有序分配
  - 破坏不剥夺：已占用的不会被强制剥夺
  - 请求并保持(占有并请求)：进程在请求剩余资源，不主动释放所占用的资源，运行前一次性申请完所需要的资源
2. 死锁检测：资源分配图
3. 死锁避免：银行家算法，检查系统的安全状态，防止系统进入不安全的状态
产生死锁的可能原因是独占资源分配不当，系统资源分配不足只会产生饥饿而不是死锁。
解除死锁通常不采用从非死锁进程抢夺资源
两级调度
忙等算法
两阶段加锁

虚拟存储器(virtual memory)：使进程在只有一部分主存的情况下也能运行。

虚拟存储是把内存与外存有机结合起来使用

虚拟存储器：在具有层次结构存储器的计算机系统中，自动实现部分装入和部分替换功能，能从逻辑上为用户提供一个比物理内存大得多，可寻址的内存。虚拟存储区的容量与物理内存(主存)大小无关，而受限于计算机的地址结构(最大容量取决于虚拟地址空间，即虚拟存储器的最大容量由计算机的地址结构决定)和可用磁盘容量。

48位虚拟地址空间，针对于64位计算机而言。

虚拟存储只能基于非连续分配技术。
虚拟内存技术的实现：

虚拟内存实现：分页存储/分段存储/请求段页式存储

不管哪种方式，都需要一定的硬件支持。
地址重定位：(将用户空间中使用的逻辑地址转变为物理地址的过程)
- 静态重定位：固定分区
- 动态重定位：作业执行过程
重定位与地址保护：一个既针对重定位又针对保护问题的解决方法是设置基址和界限寄存器
地址映射

逻辑地址变为物理地址：

虚拟地址是用户空间的逻辑地址
固定分区
动态分区（FF/BF/NF/WF）
软件模拟LRU算法(NFU )
非连续分配管理方式：(虚拟存储管理)

分页存储管理，没有外碎片，1/2内碎片；地址变换由硬件自动完成。

逻辑地址结构与页表项结构

多级页表：不浪费空间存储无用页表项在内存中，【不盲目顺序式查找页表项】地址映射需要非常迅速

多级页表的缺点是我们需要多次访问内存以查找页表。

分段存储管理：没有内碎片

分段/段表/地址变换机构

段页式管理方式：一个进程中，段表只有一个，页表可能有多个。段式：编程时程序的逻辑结构。段没有内碎片但有外碎片
页式存储管理的设计问题：
1. 工作集模型：
  1. 抖动：分配给进程的物理页数太小，无法包含其工作集，频繁的在内存和外存间换页。
  2. 预先调页
2. 分配策略
3. 页面大小：内碎片在最后一页
4. 虚拟存储接口
LRU算法耗费高的原因是需要对所有的页进行排序。
虚拟存储管理系统的基础是基于程序的局部性
使用覆盖，交换可以实现虚拟存储

I/O的各种控制方式：

程序控制
中断控制
DMA控制
通道控制

设备驱动程序

设备无关软件的设计目标

设备无关性

Spooling

磁盘

磁盘调度算法

时钟

终端设备

文件系统
字符设备文件/块设备文件
I-node ：

inode包含了文件的元信息，inode也会消耗磁盘空间，所以在磁盘格式化的时候，磁盘中也有inode区。

unix/linux系统内部不使用文件名，而是使用inode号来识别文件。

unix中目录也是一种文件，所以，打开目录就是打开文件，每个目录的目录项由两部分组成，包含文件的文件名与该文件名的inode号。

硬连接：文件名和inode号码之间是一一对应的关系，每个inode对应一个文件名。但是unix系统允许多个文件名指向同一个inode号码。

所以，可以用不同的文件名访问同样的内容。对文件内容的修改，会影响到所有文件名，但是删除一个文件名不会影响另一个文件名的访问。

即inode信息项中有一项叫做链接数，记录指向该inode的文件名总数，这时会增加1.

删除一个文件名，会使得inode节点中的“链接数”减1，当这个值减到0，表示没有文件名指向这个inode.

符号链接是一个包含文件名的小文件。硬链接比符号链接更有效。

所以删除原文件的时候，符号链接就失效啦，符号链接类比于快捷方式，但是符号链接可以跨系统

磁盘块结构
FOT
文件系统安装
磁盘空间管理
块高速缓存
文件系统的性能

生产者-消费者问题

生产者消费者共享一个初始为空，大小为n的缓冲区
缓冲区没满，生产者才能生产
缓冲区没空，消费者才能消费
缓冲区是临界资源，必须互斥访问。

semaphore mutex=1;
semaphore full=0;
semaphore empty=n;
producer(){
  while(1){
    p(empty)//消耗一个空的slot
    p(mutex)//p操作会导致进程阻塞，所以实现互斥的p操作一定要放在实现同步的p操作之后。
    produce()
    v(mutex)
    v(full)//增加一个满的
  }
}
consumer(){
  while(1){
    p(full)
    p(mutex)
    consume()
    v(mutex)
    v(empty)
  }
}

读者-写者问题(三种变体，课后题)

变体1

允许多个读者可以同时对文件进行读操作
写写互斥
读写互斥
读者优先

semaphore db=1//共享文件的互斥访问(写写)
int count =0;//引入count变量记录有多少读进程
semaphore mutex=1;//count变量的互斥访问
reader(){
  while(1){
    p(mutex);//读进程互斥访问count
    counter=counter+1;
    if(counter==1)
      p(db);//因为读优先，所以对db加锁
    v(mutex);//living critical sectioncount
    read();
    p(mutex);//各读进程互斥访问count
    counter=counter-1;
    if(counter==1)
      v(db);
   	v(mutex)  
  }
}
writer(){
  while(1){
    p(db);//可omit
    p(mutex);//写之前加锁
    writer;
    v(mutex);//写之后解锁
    v(db);//可omit
  }
}

变体2：公平竞争

设有一个数据库，存在多个读者和写者，读写互斥，写写互斥，写操作只需要等待它到来时处于活跃状态的读者结束，而不需要等待所有读者结束。

读完才能写；写完才能读；

读读不需要互斥。

semaphore rw=1;//读写对共享资源的互斥访问
int count=0;//有多少读进程
semaphore mutex=1;//对count共享变量互斥访问
semaphore w=1;//写资源优先，
writer(){
  while(1){
    p(w);//拿到写令牌，阻塞读
    p(rw);//拿到访问数据库令牌
    write;
    v(rw);
    v(w); 
  }
}
reader(){
  p(w);//拿到写令牌
  p(mutex);
  counter=counter+1;//都reader了，肯定counter计数要+1;
  if(counter==1)//如果是第一个读
    p(rw);//访问数据库的锁
  v(mutex);//counter咱不需要占着了嘛
  read();
  //读完以后呢
  p(mutex);
  counter=counter-1;
  if(counter==0)
    v(rw);//释放访问数据库的锁
  v(mutex);
}

变体3 写者优先

当有写者到来时阻塞读者线程的队列

读写互斥，写完后才能读。

没有写的时候，所有读都能读。

增加计数这是第几个写？

哲学家就餐问题

#define N 5
#define LEFT (i+N-1)%N
#define RIGHT (i+1)%N
#define THINKING 0
#define HUNGRY 1
#define EATING 2
semaphore mutex=1;//临界区互斥
semaphore s[N];//每个哲学家一个信号量
int state[N]//记录哲学家的状态

void philosopher(int i){
  while(1){
    think();
    take_forks(i);
    eat();
    put_forks(i);
  }
}
void take_forks(int i){
  p(mutex);
  state[i]=HUNGRY;
  test(i);//试图得到两把叉子
  v(mutex);
  p(s[i]);//得不到叉子就阻塞该哲学家
}
void put_forks(int i){
  p(mutex);
  state[i]=THINKING:
  test(LEFT);//看左能否进餐
  test(RIGHT);//看右能否进餐
  v(mutex)
}
void test(i){
  if(state[i]==HUNGRY &&state[LEFT]!=EATING &&state[RIGHT]!=EATING){
    state[i]=EATING;
    v(s[i]);//得到叉子后就唤醒
  }
}

操作系统名词解释

陷入

管程：管程是由过程、变量及数据结构组成的集合，组成一个特殊的模块或软件包，进程可在任何需要的时候调用管程中的过程

把共享变量，和对共享变量的操作都集中在一个模块中。

设备驱动程序：接受上方设备无关软件的请求，负责执行请求。

设备无关性：用软件屏蔽硬件上的差异

两阶段加锁法：【死锁预防的方案过于严格，死锁避免的方法需要无法得到信息】，【在很多数据库系统中，常常需要将若干记录上锁然后更新】

在第一阶段，进程时图将其所需的全部记录加锁，一次锁一个记录。若成功，则开始第二阶段。完成更新然后释放锁。如果有一些记录已经被上锁，则它将已上锁的记录解锁并重新开始第一阶段。

交换：把各个进程完整地掉入内存，运行一段时间，然后再放回磁盘

虚拟存储器: virtual memory，进程即使只有一部分内容在内存中也能运行。程序代码\，数据和栈的总大小可以超过实际可用的物理内存的大小。OS把当前需要的留在内存中，不需要的保留在磁盘上。

工作集模型：一个进程当前正在使用的页面的集合称为它的工作集。

字符设备文件：与输入/输出有关，用于处理各种串行I/O设备；

快设备，用于磁盘

文件系统的布局：

大多数磁盘可以分为若干个分区，每个分区上的FS是相互独立的，MBR(主引导技术)：

整个磁盘：

MBR(磁盘扇区0，用来启动计算机BIOS 读入执行MBR中的代码)+分区表

单独分区：

Boot block;Super block;空闲空间管理；I-nodes(索引节点)；根目录；文件和目录

Difference between file discriptor and i-nodes.

超级块用来管理文件系统

Inode-与打开文件表

magic number:

rwx（所有者)//同组(rwx)//其他
CPU核心态OS使用，执行机器所有指令
用户态用户，I/O操作和其他操作都不能执行
先将参数放入预先确定的寄存器或堆栈，然后执行一条特殊的陷入指令
虚拟机：全虚拟化技术(虚拟成多个大型机，并且和硬件接口完全一致)，半虚拟化技术
部分虚拟化：在硬件支持不完全的情况下，仍然能够提供虚拟化
基于容器的虚拟化技术：计算机系统上运行着唯一的操作系统实例，通过在这个系统上加装虚拟化平台，可以将系统划分成多个独立隔离的容器，每个容器是一个虚拟的操作系统，不虚拟任何硬件设备。
PCB 进程控制块：资源占用信息：虚拟地址空间现状,打开文件列表。
中断处理的步骤：
用户线程：不依赖于OS核心；所以也没有用户态与核心态的切换
内核线程：依赖于OS核心
可能的方法：
1. 关中断；
2. 锁变量(如果锁变量是普通类型，不是原子类型，仍会发生竞争条件)
3. 严格交替法：即使代码在非临界区中，也会阻塞其他进程
4. 忙等待形式互斥：Peterson互斥，TSL解法
许多系统调用是原语，但并非所有系统调用都是原语
条件变量：在管程内部，存在某种等待机制，管程内部可以说明和使用的一种特殊类型的变量（条件变量）,每个表示一种等待原因，相当于每个原因对应一个队列。
利用消息传递进行进程间通信，使用SEND/RECEIVE两条原语
分时系统：多个用户分享使用同一台计算机，多个程序分时共享硬件和软件资源(按时间片分配)
OS的有些部分也需要定时器，即所谓的看门狗时钟。每次向硬盘控制器发命令时，都要安排唤醒调用，以便当命令执行完全失败时的试图恢复。
程序控制I/O：I/O操作由程序发起，CPU等待操作完成,数据的读写通过CPU，每个控制器都有一些用来与CPU通信的寄存器与缓冲区。

设备数据缓冲区按内存地址空间进行统一编址。
中断驱动：I/O操作由程序发起，在读/写字符数据完成时，向CPU发出中断，通知CPU，读写通过CPU
DMA：程序DMA硬件中的完成I/O操作，CPU只需要干预I/P操作的开始和结束。
通道，通道比CPU完成更为复杂的I/O控制，一个通道对应多个外设，一次完成几批I/O操作。
spooling ：假脱机，创建一个特殊的守护进程与特殊的目录，称为spooling 目录，进程将文件方在spooling 目录下，打印机是独占设备。
RAM 盘：在内存中保留一部分存储区域，使其像普通磁盘一样使用。
寻道时间是找道找柱面(磁道)！旋转延迟则是由于扇区的定位带来的！
终端是用户与计算机交互的工具，包括键盘和显示器
TLB：页表的缓存，lookaside buffer,快表
反置页表：一个物理页框对应一个页表项
一台虚拟机由48位虚拟地址和32位物理地址，页面大小为8KB，请问在页表中需要多少个页表项，页表项只取决于虚拟地址空间，所以为35位
TLB的大小只有工程上的折衷。
旋转时间8msec,一道的容量为1MB，所以transfer其实也相当于是知道了。
磁盘计算：20题。

一个磁盘有4000个柱面，每个柱面有8个磁道，每个磁道有512个块，在寻道时每移过一个柱面需要1ms。

逻辑上相邻两个块的平均寻道时间为5ms，

逻辑上相邻两个块的平均寻道为100 $\mu s$

旋转延迟为10ms，传输时间时每块20 $\mu s$ .

读100个块：

旋转延迟10ms，所以平均旋转延迟是5ms。

（5+5+0.02）✖️100

（0.1+5+0.02）✖️100

4000柱面 10ms，块与块rotation0.005

OS关心磁盘存储，有效工作，管理安全一致性的问题

展开全文 >>

当代数据库管理系统W1:好的系统软件是好的模块

2020-09-18

数据库管理系统（DBMS）

本课程围绕着系统软件开展

Today:文档数据库

more >>

展开全文 >>

统计与数据分析基础W1:概率论复习

2020-09-15

概率论复习

一元随机变量||CDF 和PDF的性质|| $\Gamma$ 函数

一元随机变量

定义在样本空间上的实值函数 $x=x_n$ 称为随机变量。

【Attention】

相同样本空间却有不同的随机变量
统计学研究对象是数字/时数：所以统计学往往研究的是结构化的东西。

离散随机变量和连续随机变量怎么刻画？

离散随机变量：取值有限个。

CDF和PDF

分布函数的三个性质：(后续定理证明的一些基础)

单调性
连续性
有界性：F( $-\infin$ )=0;

Gamma函数

$\Gamma(x)=\int_0^{\infin}x^{\alpha-1}e^{-x}dx,\alpha>0$

Gamma分布

$f_X(x)=\frac{x^{\alpha-1}\lambda^{\alpha}e^{-\lambda x}}{\Gamma(\alpha)}$ ,其中x>=0；0，otherwised.

性质

$\Gamma(1)=1$
$\Gamma(\frac{1}{2})=\sqrt{\pi}$
$\Gamma(\alpha+1)=\alpha·\Gamma(\alpha)$ 【用的最多的性质，理解记忆可把该函数看成实数域上的阶乘，不太一样诶，那就分布积分法吧】

统计中重要的计算技巧，构成密度函数的积分，密度在定义域上积分为1 。

若一r.v.X 满足：[trick 待补充]
$p(x)=\begin{cases}\frac{\lambda^{\alpha}}x{\Gamma(\alpha)}\end{cases}$

特例

$\Gamma(1,\lambda)$ 是指数分布， $\alpha=1$
$\alpha=\frac{n}{2},\lambda=\frac{1}{2}$ 时，Gamma分布是自由度为n的卡方分布，记为 $\Chi^2(n)$

Beta分布

Beta函数

B(a,b)= $\int_0^1x^{a-1}(1-x)^{b-1}dx$ ，a>0,b>0,x $\in(0,1)$

$x^{a-1}(1-x)^{b-1}$ 是核，核确定即密度函数确定。

$\beta$ 函数与 $\Gamma$ 函数的关系

$B(a,b)=\frac{\Gamma(a)\Gamma(b)}{\Gamma(a+b)}$ ;

性质

B(a,b)=B(b,a)；将1-x换成y再积分。

$\beta$ 分布：

$p(x)=\frac{\Gamma(a+b)}{\Gamma(a)\Gamma(b)}x^{a-1}(1-x)^{b-1},0<x<1\0,otherwised;$

将 $X～Be(a,b)$ ，称X服从贝塔分布

期望

推导

$E(x)=\int_0^1x\frac{\Gamma(a+b)}{\Gamma(a)\Gamma(b)}x^{a-1}(1-x)^{b-1}dx$

= $\frac{\Gamma(a+1)\Gamma(a+b)}{\Gamma(a+1+b)\Gamma(a)}\int_0^1\frac{\Gamma(a+1+b)}{\Gamma(a+1)\Gamma(b)}x^{a+1-1}(1-x)^{b-1}dx$

= $\frac{a}{a+b}$ ,后面这个积分，是Y~ $\Beta(a+1,b)$

【看这里，很明显的一个概率密度函数被配凑出来了，就是概率密度函数的积分为1好算而已，没啥技巧性

= $\frac{a}{a+b}$ ;

其中 $x^{a+1-1}$ ，再去配那个系数，同时再用Gamma函数最重要的那个性质(阶乘递推性)；

方差

$Var(X)=E[x^2]-E^2[x]$

求 $x^2$ 的用法是类似的。

$Var(X)=\frac{ab}{(a+b+1)(a+b)^2}$

尽可能的凑成一个密度函数的形式去积分

特例

当a=1,b=1时， $\beta(X)=1,$ 即 $Beta(1,1)$ = $U（0，1）$ ,这里U表示均匀分布

正态分布

对正态分布掌握的多深，统计学的多好。

$f(x)=\frac{1}{\sqrt{2\pi\sigma}}exp{-\frac{1}{2}\frac{(x-\mu)^2}{\sigma^2}}$

= $\frac{1}{\sqrt{2\pi}}(\sigma^2)^{-\frac{1}{2}} exp{-\frac{1}{2}\frac{(x-\mu)^2}{\sigma^2}}$

这样写是为了单纯保证方差的形式?

$N(\mu,\sigma^2)$ , $N(0,1)$ 【标准正态分布】

均匀分布(区间等概率)

可定义在任何的ab区间

泊松分布

Possion( $\lambda$ )

刻画记数随机变量

指数分布

Exp( $\lambda$ )

除常见形式外的另外一个形式： $\theta=\lambda^{-1}$ ，以期望的形式刻画

$p(x)=\frac{1}{\theta}e^{-\frac{x}{\theta}},x>0$

用指数分布刻画寿命(非负),x $\ge0$

一元随机变量函数的分布

$X$ 是一元(连续)r.v. $g(X)$ 也是随机变量，已知 $F(X)$ ,求 $g(X)$ 这个随机变量的分布。

仅仅是因为离散比较好求

Case1： $g(X)$ 是严格单调函数

定理

设一个r.v.X 是连续r.v.其pdf是p(x)，随机变量Y=g(X)是一个r.v.

其反函数h(y)=x的导数存在且连续(存在连续的导函数)，那么我们说 $Y=g(X)$ 的pdf, $P_{Y}(y)$ (随机变量Y取值为y的时候的分布)

$P_Y(y)=\begin{cases}P_X[h(y)]|h’(y)|&&a<y<b\0&&otherwised\end{cases}$

若 $x\in(x_1,x_2),g(X)\in(g(x_1),g(x_2))$ 单增单减相同。

$x=h(y),P_Y(y)=P_X(h(y))｜h’(y)｜,y\in(a,b),(a,b)$ 是x的值域

注意这个地方有一个绝对值，因为密度函数是非负的。多元是Jaccobian行列式，行列式外还要求绝对值。

例子

若 $x$ ~~$\Gamma(\alpha,\lambda)$ ,对k>0, $kx$~~ $\Gamma(\alpha,\lambda/k)$

证明:

令g(x)=kx,g(x)是一个严格的单调增函数，其反函数x=h(y)=y/k.
那么存在x=h(y)存在连续导函数为h’(y)=1/k.
取值范围：x是gamma函数,所以x>=0.所以y $\in[0,+\infin)$
所以 $P_Y(y)=P_X(h(y))|h’(y)|$

= $P_X(y/k)|\frac{1}{k}|=\frac{\lambda^{\alpha}}{k\Gamma(\alpha)}(\frac{y}{k})^{\alpha-1}exp(-\lambda\frac{y}{k})$

这一结论是很有用的，譬如当 $X$ ～Ga(a, $\lambda$ ),则 $2\lambda X～Ga(a,1/2)=\Chi^2(2a)$

即，任意Gamma分布可以转化为卡方分布。

Case2:特例g(X)=F(X)的分布(对x做分布变换套娃)

设X的分布函数是F(X)，这里Y=G(X)=F(X),求随机变量Y的分布

定理

若随机变量X的分布函数F(X),F(X)作为分布函数本身的性质是单调增的，这里只需要将它限制在严格单增上，其反函数 $F^{-1}_X(y)$ (的导数连续且)存在，则Y=F(X)，随机变量Y的分布服从U(0,1)，即是[0,1]上的分布函数。

证明：对于任意y<0.分布函数是>0的，{Y<=y}是不可能事件，

对任意y>=1,{Y<=y}是必然事件。

0<=y<1:

$F_Y(y)=P(Y<=y)=P(F_X(X)<=y)$

因为 $F_X(X)$ 是严格单增的，所以 $P(F_X(X)<=y)=P(X<=F^{-1}_X(y))=F_X(F^{-1}_X(y))=y$

得证。

例子：求一个给定分布的随机数

X~Exp( $\lambda$ ),

在统计中做simulation.

指数分布族的分布函数 $F_X(x)=1-e^{-\lambda x}$

U= $F_X(X)=1-e^{-\lambda X}～U(0,1)$

从 $U(0,1)$ 抽一个 $U_1,U_2,U_3,….,U_n$ 是可以做到的。【假设现在的计算机可以做到，那我得到u,就可以得到x】

由U= $1-e^{-\lambda X}$ ，所以 $X_i=\frac{1}{-\lambda}ln(1-U_i)$

应用中的经典应用，求一个很复杂的分布族的采样。

Case3:x～N(0,1);求 $X^2$ 的分布? $X^2$ 服从一个卡方分布

卡方分布是3大抽样分布之一。

解： $Y=X^2$

$F_Y(y)=P(Y\le y)=P(X^2\le y)(y>0)=P(-\sqrt{y}\le X \le \sqrt{y})=2\Phi(\sqrt{y})-1$

P(y)=F’(y),复合函数求导，求导出来是一个Gamma分布

p(y)=2f_x( $\sqrt{y}$ ) $\frac{1}{-2\sqrt{y}}$ ,

p(y)= $\frac{1}{\sqrt{2\pi}}exp(-y/2)\frac{1}{-2\sqrt{y}}$

$\lambda=\frac{1}{2}$ ,与Gamma分布的表达式对比之后，Y~Ga( $\frac{1}{2},($ \frac{1}{2}$)

Q：标准正态分布的累积分布函数？不需要知道，这里也是导数，即 $\Phi(x)$ 的形式不需要知道。

1.2 多元随机变量

多项分布，r项分布(?)

多项分布是二项分布的推广

$X ～b(n,p)$

n个独立重复的实验
每次实验有r个结果{ $A_1,A_2,….,A_r$ }
$P(A_i)=p_i$

那么 $(X_1,X_2,…,X_r)$ 取值为 $(n_1,n_2,…,n_r)$ 的概率 $P(X_1=n_1,X_2=n_2,…,X_r=n_r)$ = $\frac{n!}{n_1!n_2!n_3!…n_r!}p_1^{n_1}p_2^{n_2}p_3^{n_3}….p_r^{n_r}$ ,

其中 $\sum_i^rn_i=n$

也由于这个限制，它是一个r-1维的随机变量。

理解： $X_i$ 表示在n次投掷中i出现的次数， $X_i$ 的取值就是n选r的那个r.

展开全文 >>

信息检索W0：Course Overview

2020-09-14

Moden information retrival
每双周一实验课，每四周一个实验。
学习目的：
了解IR(Information Research)的原理
考核标准
1. 上课问答表现
2. 实验课35%
3. 期末考试50%
4. 突出表现5%

【考试】

more >>

展开全文 >>

GitHub Large File Storage

2020-08-27

今天在把FTProject存档的时候，出现了.csv太大的问题，所以这次打算好好搞一下！

问题如下：

即出现了如下报错：

:warning: GH001: Large files detected. You may want to try Git Large File Storage - https://git-lfs.github.com.

打算follow GitHub官方搞一下。

more >>

展开全文 >>

变量变换求卷积P152

多元雅可比行列式

例子：书上例3.3.10

条件分布与条件期望

定义

remarks

连续场合的全概率公式和贝叶斯公式

p(y|x)=p(x,y)p(x)\frac{p(x,y)}{p(x)}

全概率公式：利用某一个分割来求一个事件的概率(加权来算)

连续贝叶斯公式

条件期望

例题：经典例题：3.5.7

冲期望的重要性质，书上习题：

概率不等式

三种收敛性

定义4.1.2

弱收敛

依概率收敛

书上缺乏：下周统计推断公式有用：以概率1收敛

三种收敛关系之间有强弱之分

大数定律(LLN)和中心极限定理(CLT)

大数定律

CLT：独立同分布的CLT和独立不同分布的CLT。

重点

W2:MongoDB的实现原理

概率论(2)

2.n元正态分布

Special Case

3.指数分布族

定义

向量的例子

Exa.1

Exa.2

4.独立性

5.多元的期望和方差的性质

6.多元随机变量的函数

极值分布(最大值，最小值分布)

例1

例2

卷积公式

核心概念

重要结论

Mac平台安装MongoDB

布尔检索

布尔查询的效率瓶颈

布尔检索的例子

缺点

本讲的内容

生产者-消费者问题

读者-写者问题(三种变体，课后题)

变体1

变体2：公平竞争

变体3 写者优先

哲学家就餐问题

操作系统名词解释

数据库管理系统（DBMS）

概率论复习

一元随机变量

CDF和PDF

Gamma函数

Gamma分布

性质

特例

Beta分布

Beta函数

β\beta函数与Γ\Gamma函数的关系

性质

β\beta分布：

期望

方差

特例

正态分布

均匀分布(区间等概率)

泊松分布

指数分布

一元随机变量函数的分布

Case1：g(X)g(X)是严格单调函数

定理

例子

Case2:特例g(X)=F(X)的分布(对x做分布变换套娃)

p(y|x)= $\frac{p(x,y)}{p(x)}$

$\beta$ 函数与 $\Gamma$ 函数的关系

$\beta$ 分布：

Case1： $g(X)$ 是严格单调函数

Case3:x～N(0,1);求 $X^2$ 的分布? $X^2$ 服从一个卡方分布