秀一下我的计算机桌面~
背景的那棵树就在我的窗外200米的地方,我每天到实验室来都会经过这棵树。我觉得这棵树很有风格,所以天空有层次的日子总是带着相机去拍一张。其实最好的一张是蓝天白云的,可惜是N73拍出来的,肯定放不到1680*1050吧,所以用着这样SONY T100拍的,改天拿450D去拍。

[singlepic=15816,700,437]

先看一篇瘾科技的《小姜杂谈:PB 的挑战》

[singlepic=15462]

什么是 PB?抱歉,各位苹科科的爱好者们,我说的不是 PowerBook;抱歉,各位化学爱好者们,我说的也不是铅。这里想说的是 PetaByte (也就是 1000 TB,或 1,000,000 GB)的纪元来临时的挑战。1 PB 的纪元?现在就想这个做啥?毕竟现在硬盘主流连 1TB 都还不到不是吗?从数据储存的角度来看,这样说是没错,七月号的 Wired 杂志上举了几个很生动的例子告诉我们,其实要用光 1000TB 的容量还蛮困难的:

  • 现在出去买一台玩家级的新电脑,容量大约是 1TB(或者,小姜库存的*哔*片也大约这个数)。
  • 每周上传到社交网站 Facebook 上的照片总量是 20TB。
  • 哈柏太空望远镜从发射以来产生的总数据量大约是 120TB
  • 大型强子碰撞器每周产生的数据量大约是 330TB。
  • 美国国家气候中心所以收集下来的资料总量约是 460TB。
  • Youtube 上所有的影片的总量约是 530TB(比想象中小?)。
  • Ancestry.com(一个家族追根数据库)加上内附的 1790-2000 人口普查数据大约是 600 TB。

看吧!PB 的事还是留给后代子孙去烦恼好了,看起来要一次用掉 1PB 还早呢!是啦,要变出 1PB 的数据看起来是有困难,但从数据处理的角度来说,1PB 只是 Google 服务器每 72 分钟处理的数据量而已。虽然从数据储存的角度来看,我们还处在 TB 时代,但已经有很多预兆告诉我们,下一个量级单位带来的会是完全不同的一组新挑战。小姜在后面想了五个可能:

PB 时代的第一大挑战是什么?就是数据的过滤。就算人类已经有产生 PB 级数据量的能力,但事实是我们并没有把这些数据全部有效地存取的技术。因此选择哪些数据更有价值,就成为了很重要的课题。之前就有提过的大型强子碰撞器, 事实上因为是在观测为时非常短的现象,因此每秒大约要拍下十亿张的照片,才能确保不漏掉什么重要的事情。如果全部的数据都要保留的话,每秒钟就必须储存 10PB 左右的数据 — 也就是说每秒钟会塞满 10,000 颗 1TB 容量的硬盘。这是一个靠现有技术绝对不可能办到的事情,所以必须靠硬件和软件的过滤,找出每秒大约 100 个值得关注的事。即使如此,一年仍将产生约 15PB 的数据,或 15,000 颗 1TB 的硬盘,藏在这些数据里头的,有黑洞、异次元、平行宇宙,还有两三个诺贝尔奖吧?

第二个挑战,是资料的分析。 分析和过滤不一样,过滤是试图减少数据量,但分析却是变出更多的资料来。一个例子是选举结果的预测 — 一个仔细想想并没有意义,但无论候选人、选举人还是媒体都乐此不疲的游戏。美国在 2004 年时,候选人 Howard Dean 收集了 100GB 的资料来分析,当时被认为是一个很恐怖的大数据库。今年的总统选举,Catalist 公司收集了一个 15TB 的超大数据库,详细分析每个人的性别、婚姻、年龄、种族、收入等各种资料,并且从中获得判断一个人会投给共和党还是民主党的重要信息。依照同样的比例增加 下去,下一次美国总统选举时的资料量和分析结果肯定会达到数 PB 之谱,届时对数据探勘、分析所需的运算资源的要求会非常可怕,或许非要用 Cloud Computing 的方式才能运算的地步。嘿嘿,或许到时候预测系统都比你自已清楚你会投给谁…

第三个挑战,是数据的呈现。 这是一个比较抽象的关念,举个例子来说好了,目前的数码相机分辨率都高达 10mp 或更多,但一般人用的屏幕就算是最常见的高档屏幕分辨率(1920×1200)事实上才 2.3mp 而已。那多的那些资料不就可惜了?Wikipedia 现在就有点这种感觉,很多很好的文章和内容因为不容易取得,很难发挥它应有的真正价值。

第四个挑战,是数据的传输。 之前在网络上看过一个很有趣的问题:将 1PB 的资料从美国西岸送到中国,是用传输的快,还是用帆船把整个服务器运过去快?一点简单的数学告诉我们,要在合理的时间范围内把数据传完…就假设三个月 好了。要在三个月内把 1PB 的数据传完,传输送率要大约 1Gb/s 才行。这个数字不是特别的不可能(学术单位间常常有这么大量数据来往),但绝对不是一般民众能负担得起的。以目前的技术来说,如果你要传 1PB 的超高画质*哔*片给在美国的朋友的话,绝对是用海运的比较快…

最后,第五个挑战,是数据的搜寻。 拜 Google 大神所赐,这或许是我们最不须要要担心的一环了。但 Google 的强大也仅限于公开的网络而已,自已电脑上的档案要能分类清楚依然是很困难的一件事。Windows Vista 本来想要加入的 WinFS 档案系统和随之而来的关连式档案架构似乎带来了一线曙光,但最后我们还是被卡在树状结构的 NTFS 里。当个人电脑数据量也到 1PB 的时候,嗯,真难想象到时候会是个怎么样的恶梦。

个人电脑容量跨越 1GB 门坎是多久以前?好像差不多是十年前左右,所以如果发展方向不变的话,再十年我们就会进入全面 PB 的时代。但在那之前,就们就已经有够多要担心的事了:在上面的五个问题当中,小姜最担心的是数据的传输,因为传输频宽的建立要时间和金钱的投入。要能够顺 利地提升到下一个阶段,现在就要开始做准备啰!

信息技术或者说计算机技术在发展过程当中遇到了若干个瓶颈,我之前在《SMP in Linux》一文中提到过这些瓶颈以及解决方法。现在看起来,CPU多核和众核已经成了趋势,在Intel的驱动下普及应该不会有太大问题,硬盘也开始以难以置信的速度迅速扩张,希捷一年出货硬盘1.83亿块, 每秒钟近6块。看起来,网络速度已经成最近相当一段时间内的最大瓶颈。正如小姜提到的,1PB的资料从美国西岸送到中国,是用传输的快,还是用帆船把整个服务器运过去快?这个问题现实中我真的是天天面对着。
我的DreamHost硬盘很大很大,2TB大,而传输速度实在不敢恭维,在中国,我需要先把数据传到一个骨干网服务器上,然后挂着传到美国的服务器。即便这样,一个月我也只传了几十GB数据而已。
纵然技术迅速发展,无良的ISP依然收着难以置信的价格,甚至奥运村也不放过。与美国日本韩国相比,我们的宽带速度甚至连人家小灵通上网速度都不如。
我有一个梦想,睡在凉爽的骨干机房里,享用着100MB直接连接到骨干网的网速,该有多爽~

美国生活科学网(livescience.com)日前评出了自1822年以来的10大革命性计算机,其中IBM设计和组装的走鹃(Roadrunner)超级计算机位居榜首.
以下就是美国生活科学网所评出10大革命性计算机简介:

第十名:巴贝奇分析机

[singlepic=15178]

查尔斯·巴贝奇(Charles Babbage, 1792-1871)生前为英国皇家学会会员、剑桥大学数学教授。他最早提出人类制造出通用计算机理念,用以代替大脑计算复杂的数学问题。由于还没有没有电子技术应用,巴贝奇设想就架构在当时日趋成熟的机械技术上面。巴贝奇将他设想的通用计算机命名为“分析机”,希望它能自动解算有100个变量的复杂算题,速度达到每秒钟运算一次。

巴贝奇天才般地提出了类似于现代电脑五大部件的逻辑结构,也为后世通用处理器诞生奠定了坚实的基础。英国政府曾资助巴贝奇的研究工作,但后来停止对他的援助。1822年,巴贝奇终于研制出了一台可工作的模型机。近年来,科学界已经普遍确认巴贝奇在信息科学领域的鼻祖地位。1991年,英国肯圣顿(Kensington)科学博物馆根据巴贝奇当年留下来的图纸重新建造了一台差分机。图为后人完成的巴贝奇分析机。

第九名:ENIAC

[singlepic=15189]

1946年2月14日,世界上第一台真正意义上的电子计算机ENIAC在美国宾夕法尼亚大学诞生。该机器使用了18800个真空管,长50英尺,宽30英尺,占地1500平方英尺,重量达30吨。ENIAC真空管的损耗率相当高,几乎每15分钟就可能烧掉一支真空管。不仅如此,ENIAC也是位耗电大户。据说ENIAC每次一开机,整个费城西区的电灯亮度都会随之降低。

第八名:IBM System/360

[singlepic=15181]

1964年4月7日,IBM推出了划时代的System/360大型电脑,它是世界上首台指令集可兼容计算机。在此之前,计算机厂商要针对每种主机量身定做操作系统;而System/360的问世,则让单一操作系统可适用于整系列的计算机。 IBM System/360同时还和多项世界第一联系在了一起,如协助美国太空总署建立阿波罗11号资料库、完成太空人登陆月球计划、建立银行跨行交易系统以及航空业界最大的在线票务系统等重大事件。

第七名:Datapoint 2200

[singlepic=15182]

Datapoint 2200是1970年全球首批投放市场的终端用户电脑之一。该产品制造商为Computer Terminal Corp.(CTC),但该公司如今已不复存在。但Datapoint 2200的很多基本理念仍保留在我们今天所使用的个人电脑当中。如CTC曾向当时尚为创业公司的英特尔提出建议:尽量采用单一芯片,以减少机器的发热量。凭借此建议,英特尔一步步登上了PC处理器领域霸主的地位。

第六名:施乐(Xerox)PARC Alto

[singlepic=15183]

1973年4月,施乐帕罗奥多研究中心(Xerox PARC)推出了Alto,它是首台把计算机所有元素结合到一起的图形界面操作系统。Alto使用3键鼠标、位运算显示器、图形窗口和以太网络连接。 Alto能与另一台Alto计算机和激光打印机连成网络,这又是施乐PARC的一项重大发明。如今回头一看,正是这些技术组合在一起构成了信息革命的基础。

第五名:TRS-80

[singlepic=15184]

TRS-80于1977年推出,制造商为Tandy公司。该产品推出后,首先被放在 Radio Shack连锁店中出售。Radio Shack当时认为,如果首批进货销路不好,公司就留下来当作收银机使用。但由于该机器并不是针对计算机迷,TRS-80销量远远超出了预期。而TRS- 80销量大增后,又衍生出全球首轮第三方个人软件市场。

第四名:Apple II

[singlepic=15185]

Apple II于1977年推出,它是继Apple I的市场逐渐低迷之后的后续产品。Apple II吸取了Apple I存在的诸多不足,并由苹果联合创始人史蒂夫-沃兹尼亚克(Steve Wozniak)对其进行了重新设计。。Apple II更多体现出其游戏型电脑而非家用电脑的特点。Apple II表达了苹果这样一种理念:无论是新入门的电脑用户还是熟练的技术人员,也无论是电脑黑客还是商务用户,当他们在使用苹果电脑时,都能够获得轻松如意的感觉。

第三名:IBM PC

[singlepic=15186]

IBM PC机于1981年推出。该产品处理器是Intel 8088,运行速度为4.77MHz,其主板上配有64KB内存,并可扩展至640KB。由于它采用开放式结构,1982就出现了兼容机。IBM PC的重大历史意义在于:确定了硬件和软件的业界标准,从而使PC产业出现了“井喷”式的规模化增长。如今全球范围内大规模PC产业的形成,其源头就来自于IBM PC机。

第二名:苹果麦金托什机(Macintosh)

[singlepic=15187]

1984年1月24日,苹果发布了全新Macintosh(通常简称为Mac)个人电脑,它是全球首台采用图形用户界面的个人电脑,与当时采用DOS命令行、纯文本用户界面的IBM PC形成了鲜明对比。正是Macintosh的出现,引发了一场计算机世界的革命。Macintosh推出后,微软立即投入巨资研究开发Windows系统。1995年微软发布Windows 95后,普通PC用户已能享受到与Macintosh相当的图形用户界面。

目前广大普通计算机用户所熟悉的窗口、鼠标、桌面、点击、下拉菜单,甚至连桌面上的“垃圾桶”,其实都可以追溯到1984年的苹果Macintosh机。

第一名:IBM走鹃(Roadrunner)

[singlepic=15188]

走鹃超级计算机前不久刚刚组装成功,其造价高达1.33亿美元,它由IBM和洛斯阿拉莫斯 (Los Alamos)国家实验室技术人员共同开发和组装。走鹃提供给美国军方使用,其运算速度达到了1.026 petaflop,即每秒钟可进行1026万亿次浮点运算,为目前全球运行速度最快的超级计算机。走鹃投入使用后,将主要用于运算分析美国军方的机密军事数据,如核武器及其他军事战略数据等,并模仿核战争爆发后对人类生存环境的破坏情况,然后据此得出相应分析结论。

同济大学 计算机软件与理论 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

整个计算过程中各种操作的数量是

  • 比较:mn+nq-2
  • 乘法:mn+mq+nq
  • 除法:mq-1
  • 加减:mn+mq+nq-n

当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次。

  • Winograd算法(1967):2n^3+3n^2-4n+1,2×10^9秒=63.4年
  • Strassen算法(1969):6n^2.31-6n^2,18059秒=5小时
  • 凝聚算法(1989):9n^2-n-3,90秒

由此可见,如果能够将凝聚算法应用在搜索引擎领域,会带来巨大的性能提升。

3. 参考资料
[1]. 矩阵乘法的一个最佳算法. 蒋昌俊, 吴哲辉, 1989, 科学通报第4期, 251-254
[2]. “矩阵乘法的一个最佳算法”一文的进一步研究. 蒋昌俊, 吴哲辉, 1994, Vol. 11, No. 2, 149-153

查看本文PDF版本:凝聚算法在搜索引擎应用设想

分治技术的基本思想与特点
分治技术的基本思想是将一个规模为n的问题分解为k个规模较小的子问题,这些子问题互相独立且与原问题相同。递归地解这些子问题,然后将各子问题的解合并得到原问题的解。
分治法所能解决的问题一般具有以下几个特征:

  • 该问题的规模缩小到一定的程度就可以容易地解决;
  • 该问题可以分解为若干个规模较小的相同问题,即该问题具有最优子结构性质;
  • 利用该问题分解出的子问题的解可以合并为该问题的解;
  • 该问题所分解出的各个子问题是相互独立的,即子问题之间不包含公共的子子问题。

分支-限界技术的基本思想
分支限界法常以广度优先或以最小耗费(最大效益)优先的方式搜索问题的解空间树。
问题的解空间树是表示问题解空间的一棵有序树,常见的有子集树和排列树。在搜索问题的解空间树时,分支限界法与回溯法对当前扩展结点所使用的扩展方式不同。
在分支限界法中,每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点,就一次性产生其所有儿子结点。在这些儿子结点中,那些导致不可行解或导致非最优解的儿子结点被舍弃,其余儿子结点被子加入活结点表中。此后,从活结点表中取下一结点成为当前扩展结点,并重复上述结点扩展过程。这个过程一直持续到找到所求的解或活结点表为空时为止。

贪心技术的基本思想与特点
贪心技术的基本思想是从问题的某一个初始解出发逐步逼近给定的目标,以尽可能快的地求得更好的解。当达到某算法中的某一步不能再继续前进时,算法停止。
该技术的特点是:

  1. 不能保证求得的最后解是最佳的;
  2. 不能用来求最大或最小解问题;
  3. 只能求满足某些约束条件的可行解的范围。

在一般(非0/1)背包问题中,选择什么样的度量标准包,才能使该问题获得最优解?并以该度量为标准,给出背包问题的贪心算法。
在一般背包中,度量物品放入优先顺序的标准是该物品的单位重量的价值度。其用贪心算法描述为:

  1. 将物品按其单位重量的价值由高至低排序。
  2. 选择单位重量价值最高的物品放入背包中,直至背包满或该类物品已全部放入。
  3. 若背包未满,重复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。

另一届题目

  1. 写出求解汉诺塔问题的递归过程,并用树结构画出n=3时的递归调用过程,说明汉诺塔问题的算法时间复杂度。
  2. 有集合s={2,5,6,8,7,3,4,1}用分治技术求s中的最大元素和最小元素。设|s|=n,T(n)表示求出s中最大和最小元素需要进行比较的次数,写出T的解析表达式,并证明T(n)=(3/2)*n-2。
  3. 利用凝聚技术写出的矩阵乘法算法,并分析算法的时间开销,证明算法的正确性。

凝聚算法两篇原始论文:

实验室的活不少,也好久没写代码了(除了CSS和HTML之类的,因为博客代码几乎天天调整)。我的工作也从程序员转变到了系统管理员。

我做的事情,基本上算是从根本架起了一个Microsoft…操作系统,域,数据库,服务器…

就目前的状态看,我还是挺适合做一个网管和系统管理员的。我比较冷静,耐得住寂寞,诚实,可靠,关键是比较勤快。这一点只要看过我管理的机房的人都应该会有深刻的理解。
很多事情,看起来规模宏大,步骤复杂,我能够一连几天做那些枯燥无比的事情却不觉得一点点寂寞。遇到这些事情的时候,只要开始想一些事情,不知不觉沧海桑田。
其实我是个很怕很怕寂寞的人啊!
命中注定一些事情就会发生吧。

Ramdisk可以将一块内存作为磁盘供系统使用。随着内存不断加大,4GB内存比比皆是,系统在空闲状态下经常有很多内存空闲。这个时候,Ramdisk就可以大展身手了。

在我的笔记本上,一共有3GB内存,我开出1GB作为Ramdisk,并且把页面文件、系统和浏览器临时文件都映射到该Ramdisk上。效果明显,系统运行速度有了可以感觉到的进步。

假设我的Ramdisk是E:\,下面讲讲设置方法:

  • 系统临时文件:我的电脑-属性-高级-环境变量-TEMP和TMP都设置成E:\Temp
  • 页面文件:我的电脑-属性-高级-性能-设置-虚拟内存-更改-选中原来的C盘,点下面的无分页文件,然后选中E盘,选中自定义大小,然后分配一定大小的页面文件,这个值不用太大,也不要太小,建议1GB左右,不过我只开了1GB的Ramdisk,所以这里写的512MB-768MB。
  • FireFox页面Cache:Firefox地址栏输入about:config,回车打开。在下面列表中右键新建字符串,名为:browser.cache.disk.parent_directory,值为:E:\Browser Cache
  • IE临时文件:工具-Internet选项-设置-移动文件夹,设置成E:\Browser Cache

RamDisk下载