Xinhecuican's Blog

基础关系模型是人们为了描述关系而建立的一种二维表，这个二维表叫做关系。 关系模型中的一些术语： 属性： 列名，例如图中title、year、length等 模式： 关系名和属性集合叫做这个关系的模式。例如Movies(title, year, length, genre).模式中的属性其实是集合 元组： 除了首行外的其他行叫元组。每个元组中的各个分量都对应各个属性。 域： 其实也就是数据类型，如果上面的域分别是string、 Integer、 integer、 string。因此也可以加上域来描写模式Movies(title: string, year: integer, length: integer, genre: string) 键： 键是区分该行和其他行的唯一标识。例如title和year构成了一个键。也就是说没有两部电影的制作年份和名字都相同（当然这种键并不好，可能会有冲突）。也可以只使用一列构成一个键，例如我们的身份证号。它的模式可以表示为： Movies(title, year, length, genre) 在SQL中定义关系SQL中有三种关系： 表、视图、临时表. ...

引例啤酒与尿布 在一家超市里，有一个有趣的现象：尿布和啤酒赫然摆在一起出售。但是这个奇怪的举措却使尿布和啤酒的销量双双增加了。这不是一个笑话，而是发生在美国沃尔玛连锁店超市的真实案例，并一直为商家所津津乐道。沃尔玛拥有世界上最大的数据仓库系统，为了能够准确了解顾客在其门店的购买习惯，沃尔玛对其顾客的购物行为进行购物篮分析，想知道顾客经常一起购买的商品有哪些。沃尔玛数据仓库里集中了其各门店的详细原始交易数据。在这些原始交易数据的基础上，沃尔玛利用数据挖掘方法对这些数据进行分析和挖掘。 一个意外的发现是：”跟尿布一起购买最多的商品竟是啤酒！经过大量实际调查和分析，揭示了一个隐藏在”尿布与啤酒”背后的美国人的一种行为模式：在美国，一些年轻的父亲下班后经常要到超市去买婴儿尿布，而他们中有30%～40%的人同时也为自己买一些啤酒。产生这一现象的原因是：美国的太太们常叮嘱她们的丈夫下班后为小孩买尿布，而丈夫们在买尿布后又随手带回了他们喜欢的啤酒。按常规思维，尿布与啤酒风马牛不相及，若不是借助数据挖掘技术对海量交易数据进行挖掘和分析，沃尔玛是不可能发现数据内在这一有价值的规律的。 概念从上例可以看出 ...

基础上下文无关文法(CFG)是一些固定的语法知识，例如 S ->NP, VP 句子可以由动词词组和名词词组构成NP->Det, Noun Det和Noun可以构成一个名词词组VP->Verb, NP 动词词组可以由动词+名词词组构成NP->eyes eyes是名词词组 通过这些规则我们可以找到一个句子的句法分析树。但是我们可能会找到非常多的句法分析树，并且没有办法判断到底使用哪一种。因此想到给每一个语法分配一个概率值。也就是概率上下文无关文法 S->NP VP 1.0PP->P NP 1.0VP->V NP 0.7P->With 1.0... 一些符号定义 G： 语法 L： 由语法生成的语言 t： 句法分析树 {$N^1 … N^n$}: 非终结符号集合，也就是NP，P等参数 {$w^1 … w^n$}: 终结符号集合，也就是实实在在的单词 $w_1 … w_m$: 句子序列 $N^j_{pq}: 覆盖$w_p 到 w_q$的非终结符$N^j$ 例如一个句子: astronomers saw stars with eyes,它的句法树 ...

下界Ω 上界O 紧界Θ这几个界都是由极限得来的。 上界： 对于 任意正常量c>0,都存在No>=n,使得 0<=f(n)<= cg(n).则可用 f(n) = O(g(n))表示。 g(n)一般使用简单的式子如 n nlogn, $n^2$,… 这个式子其实就是极限的表达形式，所以我们也可以用极限的形式表达： \lim_{n \to \infty}\frac{f(n)}{g(n)} = 0下界： f(n)>=cg(n) \lim_{n \to \infty}\frac{f(n)}{g(n)} = +\infty紧界： f(n)= cg(n) 分析递归式的复杂度之所以递归式要单独拿出来分析是因为递归式很难从直观上去判断。例如 f(n) = f(n-1)+f(n-2).这个递归式如果要分析的话可以写成 f(n) = f(n-1) + f(n-2) + 1，最后一个1表示每一层需要进行的运算，因为这里只有一个加法运算，所以是加1. 代入法求递归式代入法就是首先猜测复杂度，然后用归纳法证明。例如： T(n) = 4T(n/2) + n ...

基础分治法是将大问题分解成若干个小问题，通过解决小问题解决大问题的方法。它和递归关系密切。 大致流程if(|P| <= n0) adhoc(p);divide p into small k part;for(int i=0; i<k; i++){ yi = divide-and-conquer(pi); //递归解决各个子问题}return merge(y1,y2,...yk); 合并子问题的解 例题找伪币假如有十六个硬币，有一个是伪币，伪币比较轻，试用一个天平找出伪币 假如两两比较，最坏情况需要8次 如果使用分治法，需要四次。首先8个8个比较，然后在轻的一堆中比较。 计算a^n如果使用 a a a…。那么复杂度是O(n).使用分治法， a^n = a^(n/2) * a^(n/2) n%2 == 0 a^n = a^(n/2) a^(n/2) a n%2 == 1 所以 T(n) = T(n/2) + 0(1) 其中T(n/2)是计算a^(n/2)所需要的时间， O(1)是两个数相乘需要的时间。由主定理可得，复杂度是 O(logn)。 ...

无后效性无后效性是一个问题可以用动态规划求解的标志之一，理解无后效性对求解动态规划类题目非常重要 概念：某阶段的状态一旦确定，则此后过程的演变不再受此前各种状态及决策的影响（某度上找的定义） 理解：无后效性指的是之前做过的事现在还可以继续去做，这便是前一阶段做的事对后一阶段无影响。如果前面做过了后面便不能去做或者做的事受限这便是有后效性 例：这篇博客讲的很清楚 01背包问题动态规划更多可看 问题描述： 有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使价值总和最大。 我们可以用一个数组dp[i][c]来表示考虑前i个物品并且剩余容量为c时的最大价值。 首先要说明它满足最优子结构性质: 假设最优解为($x_1, x_2$, …).$x_i$可以选取0或1. 现在随机选取最优解中的部分($x_1, x_2,…x_i$)。假设它不是子问题的最优解，那么一定存在一个比他更优的解($y_1, y_2,…y_i$)。使得value($x_1, x_2,…x_i$)<value($y_1, y_2,…y_i$) 则value($y1, y_ ...

引例钢条切割问题 有一根长为$R_n$的钢条，切若干米获得的收益不同（例如切1米1元，切2米3元），请问怎样切割使得收益最大？ 朴素的方法是我们可以把所有情况列举出来求最优解，但是总共有2^(n-1)种方案，复杂度显然过高，因此需要更简便的方法。 我们虽然是把它分成若干段，但是其实我们不是一瞬间把所有段都切好的，我们也是一条一条进行切割，所以问题可以转化为切一段和剩下所有段的最优解。即 R_n = \max_{1\le i \le n}( P_i+R_{n-i})其中$R_n$是长为n时的最优解。$P_i$是切长度为i可以获得的收益。 rod(int* p, int n){ if(n == 0) { return 0; } int q = -2147483648; for(int i=1; i<=n; i++) { q = max(q, p[i]+rod(p, n-i)); } return q;} 这是上面说明的递归算法。事实上，这种方法复杂度 ...

介绍词汇获取主要是为了弥补现有机读词典的不足。它主要关注词汇的搭配，动词子范畴，附着歧义，选择倾向，语义相似性等问题。 评价方法 Precision（精确度）: 精确度是你筛选出来的集合中正确的数量。也就是$\frac{tp}{fp+tp}$ Recall（召回率）: 召回率是系统选择的正确结果占所有正确结果的比例，即$\frac{tp}{tp+fn}$ F-measure: $F = \frac{1}{\alpha \frac{1}{precision} + (1 - \alpha)\frac{1}{recall}}$ fallout: 系统错误选择的非目标项在非目标集合中所占的比例, 即$\frac{fp}{fp + tn}$ 动词子范畴我们把根据动词所允许搭配的补足成分的类型（名词短语，介词短语等）对动词进行分类称之为子范畴。 例如She greeted me。他就属于一种子范畴，动词前面和后面都是代词，换成其他动词也是相同的结构。

机械硬盘 结构： 由若干个盘片组成，每个盘片有2两面，每一面上有若干个磁道（柱面就是指和中心轴平行的圆柱面，有多个每个盘上都有两个磁道在上面） ，每个磁道上又划分成若干个扇区，扇区是数据访问的最小单位。中间的轴在不停转动。每个扇区都有一个编号。 显然如果扇区划分时是从中心发出多根射线的话是不好的。因为内圈的扇区划分小，外面的扇区划分大，因此每个扇区读写数据数目可能会有较大的差距。但是很可能只需要利用其中很小一部分，这样就造成了浪费。所以磁道与磁道之间扇区数目是不同的，尽量使数据分布均匀。 图中左边的架子是读写头，可以前后滑动。数据就是通过读写头进行读写的。 大致过程：先移动到对应扇区（寻道），然后等待读写头划过我们要读取的扇区。之后在读取这个扇区。要注意即使只需要读取一个字节也要把这个扇区全部读取完。如果是写的话，先把扇区中数据读取出来，然后再在这些数据中进行更改，最后再把这些数据写入到扇区中。 一般寻道在2-9ms，旋转也是10ms左右，而读取只需要0.02ms，所以说大头都在寻找过程中。并且要比dram慢2500倍，比sram慢40000倍。 旋转时间如果没有特殊规定一般都是算旋 ...

定理 ：$\frac{(n-1)S^{2}}{\sigma^{2}}$ 证明 \begin{aligned} \frac{(n-1)S^2}{\sigma^2} =& \sum_{k=1}^n\frac{(x_i-\overline{x})^2}{\sigma^2}\\ =& \sum_{k=1}^n\frac{(x_i - \mu +\mu - \overline{x})^2}{\sigma^2}\\ =&\frac{1}{\sigma^2} \sum_{i=1}^{n}(( x_i-\mu)^2 - 2(x_i-\mu )(\bar{x} - \mu) + (\bar{x}-\mu)^2)\\ =& \frac{1}{\sigma^2} \sum_{i=1}^{n}( x_i-\mu)^2 - 2(\bar{x} - \mu)\sum_{i=1}^{n}(x_i-\mu ) + \sum_{i=1}^{n}(\bar{x}-\mu)^2\\ =& \frac{1}{\sigma^2} \sum_{i=1}^{n}( x_i-\mu)^2 - 2(\bar{x} - ...