分治技术的基本思想与特点
分治技术的基本思想是将一个规模为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. 利用凝聚技术写出的矩阵乘法算法,并分析算法的时间开销,证明算法的正确性。

凝聚算法两篇原始论文:

近期本人的一系列网站入驻DreamHost,有些规矩还是要遵守的。因为DreamHost机房位于Virginia, United States,因此受美国法律限制。这里翻译一下DreamHost的Abuse Center,学习下规矩。

[singlepic=14254]

Spam and UBE

[singlepic=14267,,right]

垃圾邮件(通常被定义为’不请自来的批量电子邮件’ ,而且还包含Usenet的垃圾邮件和博客评论/ Trackback跟踪垃圾邮件)是一个巨大的问题,作为在互联网其中一个最大的虚拟主机服务提供商,DreamHost确保我们的服务是没有用在这样的方面。

为什么垃圾邮件是不好的?
有好几个原因,但是最重要的原因是:垃圾邮件是最根本的资源偷窃。不论谁最终收到了垃圾邮件,都必须以磁盘空间、CPU时间和内存消耗的形式为之付出代价。而发送者则不需要付出如此之多的代价(可能根本没有代价),相反地,代价转嫁给了接受邮件服务器的拥有者,最终导致了对最终用户收取的高价格。因为邮件不是接受者需要的,垃圾邮件发送者迫使人们为他们不想要的广告买单。
你可以把垃圾邮件看作是生活中的一捆邮件,只不过是接收人要去付邮费,即便接收人并不想要这些邮件。

DreamHost’s anti-spam policies
你可以在这里查看我们关于垃圾邮件的规定:
http://www.dreamhost.com/spam.html
所有的用户都必须在注册DreamHost时阅读并同意遵守这些规定,并作为允许托管的条件。
这些规定包含了所有批量发送的电子邮件,无论是从我们的服务器发出的还是使用了第三方服务器或服务,而使用了我们托管的域名和网站做地址的。我们的规定还限制了新闻组发表文章、博客评论/trackback、论坛发帖等,使用了我们托管的域名或网站。

最重要的要求
当你准备发送批量邮件的时候,有三件事情必须熟记在心。这些事情是非常重要的,我们有必要使用粗体和大字体显示它们:

  1. 接受者必须特别要求自己的地址出现在你的发送列表中(“opt-in”)。
  2. 接受者必须确认自己要加入你的发送列表的意图(“opt-in confirmation”)。
  3. 你必须能提供证明opt-in确认的过程确实发生过(提供日期/时间/IP记录的确认信息)。

换句话说,在你的订阅中,你必须遵守我们的反垃圾邮件规定的条款1和条款2。在我们所执行的垃圾邮件相关的停权操作中,有95%都是因为没有做到这两点而导致的。在这几项条款上我们不能宽大处理(出于善意!),所以一定要确认你真正理解了这几项条款。

处理方式
DreamHost保留在任何时候,有警告或者无警告地封闭发现的侵犯版权法的帐户的权利。DMCA通告被认为是典型的侵犯证据,同样也是停权的理由。

名词解释

Term: Opt-In
An “opt-in” occurs when people ask to be placed on your list. Typically this is through a form on your web site, but an opt-in could also be someone signing up for periodic mailings at a trade show, concert or other real-world event.

Term: Opt-In Confirmation
“Opt-in confirmation” is a process wherein a person who has opted-in confirms that they want to be on that list before receiving bulk email associated with that list. This ensures that, for example, someone can’t sign someone else up for a list without their knowledge or consent. Only the person who has access to the email address being subscribed to the list can confirm the opt-in. This is sometimes called “closed-loop confirmation” or (erroneously) “double opt-in”.

Opt-in confirmation as required by DreamHost works like this: Upon an email address being subscribed to a list, a single email is sent to the subscriber’s email address with a unique tagged link that they must follow prior to being added to the list or receiving any bulk email from it. Those who do not follow that link receive no further email. Those who do follow the link are added to the list and their IP address (along with the date and time) is logged. Access to that logging information must be provided in full to DreamHost for independent review upon request.

侵犯版权

[singlepic=14263,,right]

我们不允许我们的用户是用我们的服务从事或者在知情的情况下促使传播或获取被版权保护的东西。除非你获取了版权所有者的明确许可,表示你可以这样做,或者你自己就是版权所有者。下列任意一条都是不允许的:

  1. 下载或传播商业DVD、电视节目等等。
  2. 存储非法获取的DVD、电视节目的“备份”。
  3. 传播属于别人的图片、照片、录像。
  4. 传播歌曲或者音乐文件。

请注意,我们同样禁止可能破坏版权的行为。这意味着链接到私有文件(即便是不位于DreamHost服务器上的)、运行版权保护文件的BitTorrent trackers,开办破解软件的论坛等等行为都是不被允许的。
明显地,这些因素都是主观的,并且很容易在无意中违反。基于这样的原因,我们会对于侵犯权的行为采取一种合理的方法。例如,在站点中包含了一个或者两个YouTube录像,与网站的主要目的就是索引和链接向商业好莱坞电影链接的行为是完全不同的。

名词解释

Term: Distribution
For the purposes of our policies, ‘distribution’ entails either distributing material directly from your account (ie. sharing files from your web space or via FTP) or embedding material located on non-DreamHost servers so that it displays within your server. It also includes willfully facilitating copyright infringement by linking to known infringing works, as described above.

Term: Acquisition
For the purposes of our policies, ‘acquisition’ entails using your DreamHost account to illegally obtain copyrighted material. This usually involves the use of BitTorrent, the ‘wget’ tool, FTP, etc.

Term: Storage
For the purposes of our policies, ‘storage’ involves the storage of copyrighted material that was obtained unlawfully. So, if you use BitTorrent or some other tool from your own computer to illegally obtain a DVD rip and then store a copy under your DreamHost account (even if it’s not being re-distributed), such activity would be prohibited.

侵犯商标

[singlepic=14268,,right]

我们不允许我们的客户从事侵犯商标的行为。这并不是说你不能用任何商标,而是说你不能以可能导致商业混乱的方式使用商标。记名使用商标,例如批评或分析,都是被美国宪法第一修正案所保护的。

处理方式
商标法是很复杂的,比版权法更加复杂。DreamHost无从推断你的意图是否考虑了合法性。我们基于我们的法律顾问、一一处理每一个申诉,并且保留封闭那些我们认为故意侵犯商标法的站点或帐户的权利。对于那些显然的故意侵犯行为,例如网络钓鱼行为,会导致立即停权。
如果你想用一个商标,并且觉得不会侵犯商标所有者的权益,我们强烈建议您首先咨询有资格的顾问,然后再做。

黑客、侵入和拒绝服务式攻击

[singlepic=14264,,right]

我们不允许一些非法入侵计算机的行为,典型的如下:

  • 侵入:任何人,试图通过利用第三方系统或服务安全漏洞,或者获取敏感的信息(包含密码)的欺骗行为,都将被永久封停帐户,不会退款。
  • 拒绝服务式攻击:类似地,任何人,使用任何方式,破坏或使第三方系统或软件超负载(拒绝服务式攻击),都将被永久封停帐户,不会退款。
  • 木马工具:不仅仅是上面的,存储或提供侵入或拒绝服务式攻击的工具也是不被允许的,将被永久封停帐户,不会退款。

处理方式
DreamHost保留在任何时候,有警告或者无警告地封闭出现以上行为的帐户的权利。根据具体情况,DreamHost也可能会联系相关部门和公司,并全力配合调查。

欺诈行为

[singlepic=14265,,right]

DreamHost遇到过很多种欺诈种类,下面是常见的几种:

Type: Fraudulent sign-ups
This occurs when someone uses false information and (usually) a stolen a credit card in order to sign up for a DreamHost account. While we do have a number of protections in place to prevent this from occurring, occasionally some will slip through. We usually catch these down the road – they often engage in other types of fraud once they are on our servers – though sometimes we don’t find out until the true owner of the purloined credit card used to sign up contacts us.

Type: Phishing
This occurs when a customer creates a fake web site (usually a bank, an eBay/Paypal login screen, etc) in an attempt to fool people into entering their sensitive information into a web-based form. Such information may include a login and password, a credit card number, etc. These are then collected by the criminal for their own use. Victims are typically directed to the site via spam email designed to appear to be coming from a bank, eBay, etc.

Some of these phishing sites and emails are quite convincing in appearance. For that reason, it is advised that you never follow a link contained within an email purporting to be a bank or transactional site such as eBay – no matter how convincing it looks. Such institutions, if you ask, will give you the same advice. Go to the site directly by typing their true URL into your web browser.

Type: Pump-and-dump schemes
This is a form of fraud where criminals send large volumes of spam in order to hype a stock (typically a penny stock), usually citing some sort of “breakthrough!” or upcoming product announcement. Recipients of the email are encouraged to buy the stock and achieve a windfall. The true purpose of the scam is to artifically inflate the value of the stock after the criminal has purchased at a lower price so that they may sell it at a profit. In the end, those who bought the stock at the direction of the criminal hold an over-valued stock which drops in value shortly thereafter.

Type: Advance fee (419) scams
The 419 scam was named after the Nigerian criminal code this type of fraud violates (Nigeria is where the scam originated and is often practiced).

The scam works like this: The victim receives an email from someone (often a prominent person from an African country) asking them to help move some large sum of money out of the country. In exchange for their help, the victim is promised some percentage of the money transferred. At some point the victim is asked to send the criminal some amount of money to facilitate the transaction, after which the criminal is never heard from again. Variations on this include references to the victim receiving a large inheritance, winning a lottory (with a significant “administrative fee”), etc.

There are many types of advance fee scams. Below are a few of the more common varieties.

Type: Escrow/Shipping scams
Escrow and shipping scams are actually a common variation of the advance fee 419 scam mentioned above.

In these scams, the criminal posts for sale a high value item (ie. a motorcycle, laptop or TV) for an unusually low price, often though eBay. When potential buyers put in a bid, they are asked to instead pay via an escrow service of the seller’s choosing in order to lower the cost of the transaction (cheating eBay out of their cut in the process, with the victim’s greed taking precedence).

Of course, this escrow service does not actually exist, but is rather a fake web site created by the criminal. The buyer is directed to wire their payment to the false escrow service, after which neither the escrow service or the seller are never heard from again. A variation of this works the same way, except that the criminal creates a fake shipping company web site instead.

Type: False storefront scams
These are another common variation of the advance fee 419 scam, wherein the criminal create a fake storefront with incredibly under-priced goods for sale. The buyer is instructed to send their payment, often via wire, to the criminal. Once the payment is sent, the seller is never heard from again and the site taken down.

Type: Employment scams
One last common type of advance fee 419 scam is the employment scam, which works like this: The victim is sent an email from a company or employment service expressing interest in employing them. If the victim expresses any interest, the criminal asks them to wire an administrative fee of some kind. Once the funds are sent, the so-called employer is never heard from again.

处理方式
DreamHost保留在任何时候,有警告或者无警告地封闭从事欺诈行为的帐户的权利。

诽谤和中伤

[singlepic=14266,,right]

诽谤(一种形式的中伤)是一种书面形式的言论,是一种虚假的观点,可能会对个人、公司、集团或实体造成伤害。
请注意,作为在线服务提供商,DreamHost并不根据客户的网站判定客户的状态。我们并不能控制和编辑他们网站的内容。我们确实托管着一些可能令人不快的网站(甚至是让我们觉得不快!),但是我们想明确声明的是,我们托管这些网站,并不表明我们赞同这些观点或者与这些内容的产生有任何瓜葛。

儿童色情

[singlepic=14262,,right]

DreamHost不容忍使用我们的服务进行儿童色情(包括分发、获取或存储儿童色情)。罪犯将立即举报给相关法律部门,并且会被判处相当长时间的监禁。

前几日,Der愚跑去美国爽了一段时间,期间参加了WWDC 2008,见了将死的Steve Jobs,拿了一堆东西回来,而且令人羡慕地到计算机行业人士的圣地——加州大学伯克利分校(University of California at Berkeley)和斯坦福大学(Stanford University)逛了一大圈。

此人是开源狂热份子,喜好四处贴开源标签,四处度人…Anyway,照片虽然出自我的相机,但绝不代表本人相机水平,估计这小子开了夜档太阳下拍,而且手指挡住镜头好多次…

结论是,太Der…

Rotating Girl

先不要看下面的文字,仔细多看两遍上面的图片,这个人往哪个方向转?顺时针还是逆时针?

非常有意思的测试,看看你的左右脑切换能力,耶鲁大学的实验
如果你看见这个舞女是顺时针转,说明你用的是右脑;
如果是逆时针转,说明你用的左脑。
耶鲁大学耗时5年的研究成果。
据说,14%的美国人可以两个方向都能看见。

大脑就是你自己的智囊。科学研究证明,大脑分为左半球和右半球。左半球是管人的右边的一切活动的,一般左脑具有语言、概念、数字、分析、逻辑推理等功能;右半球是管人的左边的一切活动的,右脑具有音乐、绘画、空间几何、想像、综合等功能。
人的左右半脑是不平衡发展的,统计显示,绝大多数人是左脑发达(其中大约一半的人比较均衡一些)。全球有10%的人是左撇子,即右脑比较发达。而左右脑的发育程度不同,隐含了你的很多特质和天赋的秘密:
理解数学和语言的脑细胞集中在左半球;发挥情感、欣赏艺术的脑细胞集中在右半球。
右半脑发达的人在知觉和想像力方面有可能更强一些;而且知觉、空间感和把握全局的能力都有可能更强一些。在各种动作上相对更敏捷一些。
右脑最重要的贡献是创造性思维。右脑不拘泥于局部的分析,而是统观全局,以大胆猜测跳跃式地前进,达到直觉的结论。在有些人身上,直觉思维甚至变成一种先知能力,使他们能预知未来的变化,事先做出重大决策。
左脑的记忆回路是低速记忆,而右脑的是高速记忆,左脑记忆是一种“劣根记忆”,右脑记忆则让人惊叹,它有“过目不忘”的本事。
处理简单的语言问题时人们左脑相对活跃;左脑发达的人处理事情比较有逻辑、条理。
左脑发达在社交场合比较活跃,善于判断各种关系和因果。
左脑发达善于统计,方向感强。
左脑发达善于组织。
左脑发达善于做技术类、抽象的工作(如电脑编程)。
男性是根据右脑和左脑各自不同的分工来使用大脑的;相比之下,女性却可以同时使用左脑和右脑。
男性和女性大脑的最大区别主要是大脑皮层的构造不同。女性大脑的沟通交流能力特别发达,她们细致、敏感,能够通过察言观色来了解对方的心理,直觉也很灵敏。从构造上看,女性左右脑的脑梁部分粗于男性,因此左右脑可以顺利地同时使用。
多数男性方向感天生就比女性强。
男性的语言表达能力和理解能力远逊于女性。

原理分析
在Fireworks的帮助下,我破解了这副动画迷惑人的关键。人有两个方向,顺时针和逆时针都对,而且一旦看出某一个方向,你会深信不疑就是这个方向在转。但是,脚下的影子,伸出脚的影子只有一个方向,逆时针的。
迷惑在于,某个侧面上看,影子是没有厚度的。如下图,这是某个帧。

[singlepic=13993]

这个帧上,伸出的腿既可以看成是右腿,也可以看成左腿,认定右腿则会导致人物是顺时针转动,而看成左腿的话,人物看起来是逆时针转动。关键在于我们讨论人往哪个方向转,是一个三维的概念,这个影子没有厚度这一维。