[singlepic=14444]
原来的模板主色调是粉红色、灰色和黑色。也用了很长一段时间了，而且是WordPress Theme Viewer里面比较著名的一个模板。我的模板天天改，小改大改都有，性能的功能的和设计的都有，还有转为W3C xHTML Strict级别dtd做的修改，看过我的博客HTML源码的都应该注意到，我的DOCTYPE可是：
<!DOCTYPE html PUBLIC “-//W3C//DTD XHTML 1.0 Strict//EN” “http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd”>
希望大家都遵循Web标准，当心IE8到来时的措手不及哦。
这次改主题，起因是今天在校内看到高中同学王影分享的一个名叫“藤蔓〆图腾”的相册，其中几个图片挺有感觉，华丽却不妖艳，略显凌乱却风格鲜明，于是就下手改出了现在的风格。
自从四川汶川地震以来，背景改成灰色，感觉其实黑白搭配文字块的感觉也不错，于是这次干脆取消所有的颜色，也算正好符合我的心境，什么都看不见。
[singlepic=14410,500,,]
同济大学 计算机软件与理论 0720080247 李征
1. 矩阵乘法最优算法
1.1 矩阵与计算机科学
数学的重要性显而易见。数学是各种科学的基础，计算机也不例外。对于计算机学科起着关键性作用的数学分支主要是离散数学，因为计算机处理的数据还是二进制的离散量，对于连续量的处理还处在模拟的阶段。
此外，计算机科学中大量分支涉比如系统结构和计算机网络等等，都需要一定的逻辑学和图论作为其研究的支撑。作为离散数学的核心，矩阵的重要性不言而喻。众多的复杂计算机模型都可以用简单的矩阵来表示，而矩阵的运算也经常代表着重要的计算机物理含义。本文研究的搜索引擎排名评价体系就是其中之一。
1.2 矩阵乘法的理论下界
设A是一个m行n列矩阵
[singlepic=14397,,center]
B是另一个n行q列矩阵
[singlepic=14400,,center]
矩阵A和B的乘积是一个m行q列矩阵
[singlepic=14401,,center]
其中
[singlepic=14402,,center]
从定义出发计算矩阵的乘积，需要n次乘法运算和n-1次加减运算，得到的是计算矩阵乘法的计算复杂度的上界。当m、n和q被认为是同阶的数的时候，算法复杂度是O(n^3)。
两个矩阵相乘的任何可能的算法，运算次数至少不低于矩阵与向量相乘（当q=1时退化的情况）。此时，需要mn次乘法运算和m(m-1)次加减运算，当m和n同阶时，算法复杂度是O(n^2)。
由此可以得出结论，正确的矩阵相乘算法，其复杂度介于O(n^3)与O(n^2)。
1.3 几个典型的矩阵乘法算法
1.3.1 Winograd矩阵乘法算法
S. Winograd于1967年提出了一个矩阵乘法算法，其核心思想是修改向量内积计算方法，对重复计算部分进行预处理，然后将计算结果多次使用，从而达到简化计算的目的。
Winograd矩阵乘法算法实质是增加约50%的加减法代价以换取减少约50%乘法运算，但是其算法复杂度仍然是O(n^3)，并没有降低算法复杂性的阶。
1.3.2 Strassen矩阵乘法算法
Strassen算法是另外一个矩阵乘法算法，这个算法突破了O(n^3)的计算复杂度阶，由V. Strassen在1969年提出。
Strassen算法主要用于方阵的计算。Strassen观察了简单2阶方阵乘法的计算特点，使用7次乘法计算就能算出结果，而不是平常的8次，从而降低了整个算法计算复杂度阶。
Strassen算法的计算复杂度是O(n^(log2 7) )=O(n^2.31 )。
1.4 一个最优矩阵乘法算法
1989年，我的研究生导师蒋昌俊教授提出了一个新的矩阵乘法算法，称为凝聚算法。凝聚算法把矩阵相乘的计算复杂度降到了理论下界O(n^2)。
凝聚算法从非负整数矩阵出发，即当A和B的元素都是非负整数时，可以通过设置足够大的x和y，分别通过求x的m-1次多项式和y的q-1次多项式的值，把矩阵A的各列的元素和矩阵B的各行的元素凝聚在一起，分别得到n维向量[a1,a2,…,an]和[b1,b2,…,bn]，其中ak和bk分别是矩阵A的第k列元素和矩阵B的第k行元素的“凝聚”结果。通过向量的内积运算，又可以将上述两个向量的各个分量进一步凝聚成一个整数c。最后，以y为除数作q-1次整数求余运算，就把整数c散列成q个整数c1,c2,…,cq，再把ck对x作m-1次整除求余运算，又将ck散列成m个数，就得到了积矩阵C的第k列元素c1k,c2k,…,cmk。算法的关键之处在于设置x和y为足够大的整数，以便使整除求余的散列能够正确地反映前面通过多项式求值和向量内积运算的凝聚效果。
第一步：对x和y的取值是算法的关键，如果x和y的取值不合理，将得不到正确的反散列。
[singlepic=14403,,center]
第二步：对从1到n的k，用Horner方法计算：
[singlepic=14404,,center]
第三步：c=a1b1+a2b2+⋯+anbn
第四步：作除法，依次求商d1,d2,…,d(q-2)，rq和余数r1,r2,…,r(q-1)，使得：
[singlepic=14405,,center]
第五步：
对从1到q的j作除法，依次求商kj1,kj2,…,k(j(m-2))，rjm和余数rj1,rj2,…,r(j(m-1))，使得
[singlepic=14406,,center]
for i=1 to m do
for j=1 to q do
cij=r(j(m-i1+))
repeat
repeat
整个计算过程中各种操作的数量是
当m、n和q被认为同阶时，凝聚算法计算过程中有2n^2-2次比较运算，3n^2次乘法运算，n^2-1次除法运算和3n^2-n次加减运算，计算复杂度为O(n^2)。
2. 矩阵乘法最优算法在搜索引擎排名中的应用
2.1 一种互联网结构建模
万维网（World Wide Web，WWW）是指在因特网上以超文本为基础形成的信息网。万维网为用户提供了一个可以浏览的图形化界面，用户通过它可以查阅Internet上的信息资源。WWW是通过互联网获取信息的一种应用，我们所浏览的网站就是WWW的具体表现形式，但其本身并不就是互联网，万维网只是互联网的组成部分之一。互联网常用的服务包括：WWW、Email、FTP、Usenet、IM等。
在“谁发明了浏览器” 文中介绍了蒂姆-伯纳斯－李（Tim Berners-Lee）于1990年发明了首个网页浏览器－－World Wide Web。在1991年蒂姆-伯纳斯-李建立世界上第一个网站，它于1991年8月6日上网，它解释了万维网是什么，如何使用网页浏览器和如何建立一个网页服务器等等。综合各种资料，1991年8月6日被认为是是万维网诞生的日子。
WWW的基础是超文本和链接，链接也使得一个一个网站被相互链接起来，成为了全球规模的巨大网络。链接分为两种，一种称为内部链接，指从一个网站某个网页，链接到同一网站的另一个网页的链接；另一种称为外部链接，指从一个网站某个网页，链接到另一个网站的某个网页的链接。实际当中考虑的链接是外部链接，因为外部链接反映了整个互联网的拓扑关系。
搜索引擎是一种互联网应用，搜索引擎是自动从Internet搜集信息，经过一定整理以后，提供给用户进行查询的系统。英特网上的信息浩瀚万千，而且毫无秩序，所有的信息像汪洋上的一个个小岛，链接是这些小岛之间纵横交错的桥梁，而搜索引擎，则为你绘制一幅一目了然的信息地图，供你随时查阅。
对于搜索引擎来说，网站及其链接关系可以用图来描述。
[singlepic=14407,,center]
图1 八个网站相互链接的例子
通过邻接矩阵A可以描述整个网络的拓扑结构。邻接矩阵A定义为
[singlepic=14398,,center]
我们认为，一个网站本身是存在指向本身的链接的，因此aii=1。
图1中的示例的邻接矩阵为
[singlepic=14399,,center]
2.2 互联网站价值评价标准
用户通过搜索引擎找到他们所需要的网站和页面，而搜索引擎也被用户寄予厚望，希望能够在排在最前面的搜索结果中得到他们觉得最有价值的目标页面。
互联网络是一个开放的系统，如何去衡量信息的可靠性呢？当然，CNN或者人民日报谈论一个问题，和一个普通博客谈论一个问题，当然是不一样的。即，信息是有权值的。
为每一个网站人工去赋一个权值明显是不现实的。互联网站数目超过了1亿个，而且每个网站不停地在更新，一个固定的权值也是不合适的。
Google设计了PageRank算法。PageRank是一个动态的评价体系，能够动态地对网站和网页提供的信息的重要程度进行评估，并据此作为一项标准，排序用户搜索结果。
一般人们认为，可靠的信息来自于新闻网站、大公司和百科全书。这些网站被人工选出，赋予最高的PageRank权值。然后根据这些网站的外部链接，将自己的PageRank递减地传递下去，被这些网站链接的网站获得了第二级的PageRank，如此传递下去，就可以链接到每一个网站（除了那些没有意义的信息孤岛网站）。
如果我们得到了整个互联网的邻接矩阵A，那么我们可以通过计算A^k，得到经过k次链接后，哪些网站得到了传递过来的PageRank。
2.3 矩阵乘法最优算法在搜索引擎排名中的应用
互联网邻接矩阵是一个超级规模的矩阵，超过1亿维。在这里，我们探讨一下做一次相乘，凝聚算法能够带来的性能提升。
假设：互联网站数目n=1×10^8个，超级计算机（例如2008年6月9日IBM公司的“走鹃”）每秒进行运算1×10^15次。
由此可见，如果能够将凝聚算法应用在搜索引擎领域，会带来巨大的性能提升。
3. 参考资料
[1]. 矩阵乘法的一个最佳算法. 蒋昌俊, 吴哲辉, 1989, 科学通报第4期, 251-254
[2]. “矩阵乘法的一个最佳算法”一文的进一步研究. 蒋昌俊, 吴哲辉, 1994, Vol. 11, No. 2, 149-153
查看本文PDF版本：凝聚算法在搜索引擎应用设想
北京这几天——微软亚洲研究院实习日记
被几个新的blogger问起来，WordPress里的页面（Page）这个概念应该怎么用。众所周知，About个人简历自然应当是一个Page，然而每天写的那些博客应该是Post。那么，什么时候应当用Page呢？
我认为，Page主要是一个用来组织的工具，正如WordPress默认permalink所提示的那样，Page处于根目录下的第一级，而不是隶属于哪一个月。像我右边那样，个人简历，私人相册，两个文集，还有一个子网站应当是比较合理的用法了。
高中周记——Groan & Enrich
高中的日子真的令人怀念。纯洁，甚至有些许狂热。在那些思念的日子里，似乎每天的动力就是她。
熟悉我的人都知道，每天当夜晚来临的时候，我总会在操场上逛上好几圈。可不是为了减肥，是为了想想我为谁而活。
说起来那时候的前景比现在渺茫的多，毕竟，那时候的我是坚信我是永远没有希望的。
也许，以我现在的状态再过几年，我还是能够写出《是谁 是我》那样的文字来吧。
看，我并不是一事无成吧~
分治技术的基本思想与特点
分治技术的基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同。递归地解这些子问题，然后将各子问题的解合并得到原问题的解。
分治法所能解决的问题一般具有以下几个特征：
- 该问题的规模缩小到一定的程度就可以容易地解决；
- 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质；
- 利用该问题分解出的子问题的解可以合并为该问题的解；
- 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。
分支-限界技术的基本思想
分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。
问题的解空间树是表示问题解空间的一棵有序树，常见的有子集树和排列树。在搜索问题的解空间树时，分支限界法与回溯法对当前扩展结点所使用的扩展方式不同。
在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，那些导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被子加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所求的解或活结点表为空时为止。贪心技术的基本思想与特点
贪心技术的基本思想是从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。当达到某算法中的某一步不能再继续前进时，算法停止。
该技术的特点是：
- 不能保证求得的最后解是最佳的；
- 不能用来求最大或最小解问题；
- 只能求满足某些约束条件的可行解的范围。
在一般（非0/1）背包问题中，选择什么样的度量标准包，才能使该问题获得最优解？并以该度量为标准，给出背包问题的贪心算法。
在一般背包中，度量物品放入优先顺序的标准是该物品的单位重量的价值度。其用贪心算法描述为：
- 将物品按其单位重量的价值由高至低排序。
- 选择单位重量价值最高的物品放入背包中，直至背包满或该类物品已全部放入。
- 若背包未满，重复2的过程。
利用回溯技术，给出n-皇后问题的解法，并画出4-皇后问题的深度优先搜索树
启发式搜索9宫问题
写出矩阵相乘的凝聚算法，并分析其各种基本运算的次数与算法的复杂性
设n=3，(W1,W2,W3)=(3,4,5)，(P1,P2,P3)=(2,4,8)，M=9，用动态规划法求解0/1背包问题
设f(i, j)表示背包容量为j，可选择放入的物品为i、i+1、……时背包可入物品价值的最优解，则f(1,9)为所求问题的解，并且
1) f(i,j)=max{f(i+1,j),f(i+1,j-wi)+vi}, 当j>=Wi
2) f(i,j)=f(i+1,j), 当j
f(3,0)=f(3,1)=…=f(3,4)=0，f(3,5)=f(3,6)=…=f(3,9)=8
当y<4时，f(2,y)=f(3,y)=0。
当y=4时，f(2,y)=max{f(3,4),f(3,4-4)+4}=4。
当4
当y=9时，f(2,y)=max{f(3,9),f(3,9-4)+4}=max{8,8+4}=12。
所以f(1,9)=max{f(2,9),f(2,9-3)+2}=max{12,8+2}=12，此时选择的物品是2和3。
另一届题目
- 写出求解汉诺塔问题的递归过程，并用树结构画出n=3时的递归调用过程，说明汉诺塔问题的算法时间复杂度。
- 有集合s=｛2,5,6,8,7,3,4,1}用分治技术求s中的最大元素和最小元素。设|s|=n,T(n)表示求出s中最大和最小元素需要进行比较的次数，写出T的解析表达式，并证明T(n)=(3/2)*n-2。
- 利用凝聚技术写出的矩阵乘法算法，并分析算法的时间开销，证明算法的正确性。
凝聚算法两篇原始论文：
一年，怀念在MSRA的日子，可以天天听这些轻松的歌，如今却只能送给幸福的人们。衷心祝愿你们永远开心，一定要珍惜哦~
Honey Honey
孙燕姿
词/曲：林一峰
编曲：钟成虎/江力平/任柏璋
期待一个好日子 工作不需我操心 能随便想想东西
喝一杯茶也可以 写封信也可以 不做什么也可以
忙碌中又想起你 对我的若即若离 生气了也没痕迹
突然很想拥抱你 吻你措手不及 这只能想像而已
honey honey
要对你说声对不起 我总是没时间陪你
honey honey
你是否想亲亲密密 还是喜欢这段距离
虽然留点空间不见面 反而能够拉紧彼此的心
当我需要拥抱的时候 我总希望你在这里
忙碌中又想起你 对我的若即若离 生气了也没痕迹
突然很想拥抱你 吻你措手不及 这只能想像而已
(Repeat)
继续期待好日子 继续埋首工作里 寄托在下个假期
天空总是蓝蓝的 心情总是快乐
知道我在你心里
-你的QQ签名“吃饭，睡觉，打kiss”是什么意思？
-Google去搜一下吧。有一个同学的签名是“吃饭，睡觉”。
-你怎么了？
-我还好，还可以承受。
-喝酒去吗？
-周四晚上等弟兄们考完随机过程去。