协方差矩阵和相关系数矩阵

| Comments

1.概述

首先从随机变量的方差的性质讲起。
设$X$，$Y$是两个随机变量，$E(X)$，$E(Y)$，$D(X)$，$D(Y)$分别为各自的期望和方差，则有:

$D(X+Y)=D(X)+D(Y)+2E{(X-E(X))(Y-E(Y))} $. (1)

特别的，当$X$，$Y$相互独立时，有:
$D(X+Y)=D(X)+D(Y) $. (2)

对比（1）式和（2）式知，$X$，$Y$相互独立时还应该有:
$E{(X-E(X))(Y-E(Y))} =0 $. (3)

这意味着当$E{(X-E(X))(Y-E(Y))}\neq 0$时，X与Y不相互独立，而是存在一定关系的。

2.相关系数和协方差

我们把$E{(X-E(X))(Y-E(Y))}$拿出来，单独定义一个概念，即协方差，记为$Cov(X,Y)$，即：

$Cov(X,Y)=E{(X-E(X))(Y-E(Y))} $. (4)

而
$\rho _{XY} = \frac{Cov(X,Y)}{\sqrt{DX}\sqrt{DY}}$. (5)

称为随机变量$X$，$Y$的相关系数。
将$Cov(X,Y)$的定义式展开，易得：
$Cov(X,Y)=E(XY)-E(X)E(Y)$. (6)

我们常常用这一式子计算协方差。

Google PageRank 算法

| Comments

1.概述

互联网发展早期的搜索引擎，对web页面的排序，是根据搜索的词组（短语）在页面中的出现次数（occurence ）， 并用页面长度和html标签的重要性提示等进行权重修订。链接名气(link popularity)技术通过其它文档链接到当前 页面（inbound links）的链接数量来决定当前页的重要性，这样可以有效地抵制被人为加工的页面欺骗搜索引擎的手法。

PageRank(网页级别)，2001年9月被授予美国专利，专利人是Google创始人之一拉里•佩奇（Larry Page）。因此，PageRank里 的page不是指网页，而是指佩奇，即这个等级方法是以佩奇来命名的。它是Google排名运算法则（排名公式）的一部分，是Google用于 用来标识网页的等级/重要性的一种方法，是Google用来衡量一个网站的好坏的重要标准之一。PageRank计算页面的重要性，对每个 链入(inbound)赋以不同的权值，链接提供页面的越重要则此链接入越高。当前页的重要性，是由其它页面的重要性决定的。 在揉合了诸如Title标识和Keywords标识等所有其它因素之后，Google通过PageRank来调整结果，使那些更具“等级/重要性”的网页 在搜索结果中令网站排名获得提升，从而提高搜索结果的相关性和质量。

Matlab代码优化方法几则

| Comments

1.计算向量、矩阵化，尽量减少for循环
因为MATLAB本来就是矩阵实验室的意思，他提供了极其强大而灵活的矩阵运算能力，你就没必要自己再用自己编写的for循环去实现矩阵运算的功能了。 另外由于matlab是一种解释性语言，所以最忌讳直接使用循环语句。但在有些情况下，使用for循环可以提高程序的易读性，在效率提高不是很明显的 情况下可以选择使用for循环。

2.循环内大数组预先定义--预先分配空间
这一点原则是极其重要的，以至于在编写m程序时编辑器会给出提示“'ver' might be growing inside a loop.Consider prealloacting for speed.”

3.尽可能利用matlab内部提供的函数
因为matlab内部提供的函数绝对是各种问题的最优算法，那写程序都是他们大师级人物写出来的，程序应该说相当高效，有现成的为什么不用那！ 这个原则就不用实际的程序测试了。

4. 利用内置函数自动记录运行结果
matlab生成的结果变量只贮存在内存空间中，一旦matlab关闭则会丢失，很多时候需要手工将这些结果存储到我们需要的文件中。事实上，matlab提供 了很多函数可以自动记录结果，如fprintf可以将数据写入txt文件，xlswrite可以将数据写入excel文件等等。这样自动化的命令可以缩减大量时间， 从而提高效率。

5. 在迫不得已要使用较多循环而每一步都很耗时的时候，可以将每一步的结果保存成mat文件，然后在循环的开头用if语句与exist函数进行判断， 如果该文件存在的话，就直接进入下一次循环。这样做的好处是不会因为断电、电脑死机或误操作等原因而重头从第一个循环再次运行。

6. 同时运行多的matlab进程。现在的电脑一般都是多核，一般一个matlab进程会占用一个cpu，因此可以在多核电脑上同时打开多个matlab窗口， 从而执行不同的命令。如四核电脑上可以打开三个matlab窗口分别运行不同的程序，cpu的占用率约为80%，这样既加快了进度，又不会影响电脑的使用。

11年浙大复试机试题解

| Comments

11年浙大研究生复试机试题解

A题：A+B for Matrices （ 九度1001）

水题

Problem A 
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

#include <stdio.h>
int m,n,a[10][10],b[10][10];
int main()
{
    int i,j,cnt;
    while(scanf("%d",&m)&&m>0){
        scanf("%d",&n);
        for(i=0;i<m;i++)
            for(j=0;j<n;j++)
                scanf("%d",a[i]+j);
        for(i=0;i<m;i++)
            for(j=0;j<n;j++){
                scanf("%d",b[i]+j);
                a[i][j]+=b[i][j];
            }
        cnt=0;
        for(i=0;i<m;i++){
            for(j=0;j<n;j++)
                if(a[i][j])break;
            if(j==n)cnt++;
        }
        for(i=0;i<n;i++){
            for(j=0;j<m;j++)
                if(a[j][i])break;
            if(j==m)cnt++;
        }
        printf("%d\n",cnt);
    }
    return 0;
}

10年浙大复试机试题解

| Comments

10年浙大研究生复试机试题解

A题：A+B（hdoj3787）（九度1003）

水题，不解释，直接上代码：

Problem A 
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

#include <stdio.h>
long a,b;
int main()
{
    int i,f;
    char s[30];
    while(scanf("%s",s)!=EOF){
        a=b=0;
        if(s[0]=='-'){f=-1;i=1;}
        else {f=1;i=0;}
        while(s[i]){
            if(s[i]!=',')a=a*10+s[i]-'0';
            i++;
        }
        a=a*f;
        getchar();
        scanf("%s",s);
        if(s[0]=='-'){f=-1;i=1;}
        else {f=1;i=0;}
        while(s[i]){
            if(s[i]!=',')b=b*10+s[i]-'0';
            i++;
        }
        b=b*f;
        printf("%d\n",a+b);
    }
    return 0;
}

09年浙大复试机试题解

| Comments

09年浙大研究生复试机试题解

A题：xxx定律（hdoj3782）（九度1031）

水题，直接上代码：

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

#include <stdio.h>
int main()
{
    int n,cnt;
    while(scanf("%d",&n)&&n!=0){
        if(n==1){printf("0\n");continue;}
        cnt=0;
        while(n!=1){
            if(n%2)n=(3*n+1)>>1;
            else n=n>>1;
            cnt++;
        }
        printf("%d\n",cnt);
    }
    return 0;
}

08年浙大复试机试题解

| Comments

08年浙大研究生复试机试题解

A题：又一版A+B（hdoj1877）（九度1026）

水题，直接上代码：

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

#include <stdio.h>
char out[34];
unsigned int m,a,b,c;
int main()
{
    int i;
    while(scanf("%d",&m)&&m!=0){
        scanf("%d %d",&a,&b);
        c=a+b;
        if(c==0){printf("0\n");continue;}
        i=0;
        while(c){
            out[i++]=c%m;
            c/=m;
        }
        while(i)
            printf("%d",out[--i]);
        printf("\n");
    }
    return 0;
}

07年浙大复试机试题解

| Comments

07年浙大研究生复试机试题解

A题：最小长方形（hdoj1859）（九度1020）

水题，不解释，代码如下：

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

#include <stdio.h>
int main()
{
    int lx,ly,rx,ry,tx,ty;
    while(1){
        scanf("%d %d",&tx,&ty);
        if(tx==0&&ty==0)break;
        lx=rx=tx;
        ly=ry=ty;
        while(1){
            scanf("%d %d",&tx,&ty);
            if(tx==0&&ty==0)break;
            if(tx<lx)lx=tx;
            if(ty<ly)ly=ty;
            if(tx>rx)rx=tx;
            if(ty>ry)ry=ty;
        }
        printf("%d %d %d %d\n",lx,ly,rx,ry);
    }
    return 0;
}

06年浙大复试机试题解

| Comments

06年浙大研究生复试机试题解

A题：还是A+B（hdoj1229）（九度1015）

水题，简直水得不能再水

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

#include <stdio.h>
#include <string.h>
int main()
{
    int a,b,k,t;
    while(1){
        scanf("%d %d %d",&a,&b,&k);
        if(a==0&&b==0) return 0;
        t=1;
        while(k--)t*=10;
        if(a%t==b%t)printf("%d\n",-1);
        else printf("%d\n",a+b);
    }
}

05年浙大复试机试题解

| Comments

以下是05年浙大研究生复试机试题解，感觉题目与ACM题相比，难度还相差很远， 基本上直接贴上代码了（后续年度的题解同上）， 而且将整年的5道题的代码在一篇文章中贴出来。

A题：A+B （hdoj1228）（ 九度1010）

水题，不解释，直接上代码：

Problem A 
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

#include <stdio.h> 
#include <string.h> 
char map[][8] = {"zero","one","two","three","four","five","six","seven","eight","nine"};
int cmp( char s[] ) 
{
  for( int i = 0 ; i <= 9 ; i++ )
      if( strcmp( s , map[i] ) == 0 )
          return i;
}
int main() 
{
  char s[8];
  int a,b;
  while(1) 
  {
      a = 0;
      while(scanf("%s",s)&&strcmp(s,"+")!=0)
          a = 10*a + cmp(s);
      b = 0;
      while(scanf("%s",s)&&strcmp(s,"=")!=0)
          b = 10*b + cmp(s);
      if( a == 0 && b == 0 ) break;
      printf( "%d\n" , a+b );
  }
  return 1;
}