29 December 2007

HTML escape character list / HTML 转义字符对照表

Symbol	Code	Entity Name
€		€
Space
!	!
"	"	"
#	#
$	$
%	%
&	&	&
'	'
(	(
)	)
*	*
+	+
,	,
-	-
.	.
/	/
0	0
1	1
2	2
3	3
4	4
5	5
6	6
7	7
8	8
9	9
:	:
;	;
<	<	<
=	=
>	>	>
?	?
@	@
A	A
B	B
C	C
D	D
E	E
F	F
G	G
H	H
I	I
J	J
K	K
L	L
M	M
N	N
O	O
P	P
Q	Q
R	R
S	S
T	T
U	U
V	V
W	W
X	X
Y	Y
Z	Z
[	[
\	\
]	]
^	^
_	_
`	`
a	a
b	b
c	c
d	d
e	e
f	f
g	g
h	h
i	i
j	j
k	k
l	l
m	m
n	n
o	o
p	p
q	q
r	r
s	s
t	t
u	u
v	v
w	w
x	x
y	y
z	z
{	{
\|	\|
}	}
~	~
Non-breaking space
¡	¡	¡
¢	¢	¢
£	£	£
¤	¤	¤
¥	¥	¥
¦	¦	¦
§	§	§
¨	¨	¨
©	©	©
ª	ª	ª
«	«
¬	¬	¬

®	®	®
¯	¯	¯
°	°	°
±	±	±
²	²	²
³	³	³
´	´	´
µ	µ	µ
¶	¶	¶
·	·	·
¸	¸	¸
¹	¹	¹
º	º	º
»	»	»
¼	¼	¼
½	½	½
¾	¾	¾
¿	¿	¿
À	À	À
Á	Á	Á
Â	Â	Â
Ã	Ã	Ã
Ä	Ä	Ä
Å	&#197	Å
Æ	Æ	Æ
Ç	Ç	Ç
È	È	È
É	É	É
Ê	Ê	Ê
Ë	Ë	Ë
Ì	Ì	Ì
Í	Í	Í
Î	Î	Î
Ï	Ï	Ï
Ð	Ð	Ð
Ñ	Ñ	Ñ
Ò	Ò	Ò
Ó	Ó	Ó
Ô	Ô	Ô
Õ	Õ	Õ
Ö	Ö	Ö
×	×	×
Ø	Ø	Ø
Ù	Ù	Ù
Ú	Ú	Ú
Û	Û	Û
Ü	Ü	Ü
Ý	Ý	Ý
Þ	Þ	Þ
ß	ß	ß
à	à	à
á	á	á
â	â	â
ã	ã	ã
ä	ä	ä
å	å	å
æ	æ	æ
ç	ç	ç
è	è	è
é	é	é
ê	ê	ê
ë	ë	ë
ì	ì	ì
í	&#237	í
î	î	î
ï	ï	ï
ð	ð	ð
ñ	ñ	ñ
ò	ò	ò
ó	ó	ó
ô	ô	ô
õ	õ	õ
ö	ö	ö
÷	÷	÷
ø	ø	ø
ù	ù	ù
ú	ú	ú
û	û	û
ü	ü	ü
ý	ý	ý
þ	þ	þ
ÿ	ÿ
Ā	Ā
ā	ā
Ă	Ă
ă	ă
Ą	Ą
ą	ą
Ć	Ć
ć	ć
Ĉ	Ĉ
ĉ	ĉ
Ċ	Ċ
ċ	ċ
Č	Č
č	č
Ď	Ď
ď	ď
Đ	Đ
đ	đ
Ē	Ē
ē	ē
Ĕ	Ĕ
ĕ	&#277
Ė	Ė
ė	ė
Ę	Ę
ę	ę
Ě	Ě
ě	ě
Ĝ	Ĝ
ĝ	ĝ
Ğ	Ğ
ğ	ğ
Ġ	Ġ
ġ	ġ
Ģ	Ģ
ģ	ģ
Ĥ	Ĥ
ĥ	ĥ
Ħ	Ħ
ħ	ħ
Ĩ	Ĩ
ĩ	ĩ
Ī	Ī
ī	ī
Ĭ	Ĭ
ĭ	ĭ
Į	Į
į	į
İ	İ
ı	ı
Ĳ	Ĳ
ĳ	ĳ
Ĵ	Ĵ
ĵ	ĵ
Ķ	Ķ
ķ	ķ
ĸ	ĸ
Ĺ	Ĺ
ĺ	ĺ
Ļ	Ļ
ļ	ļ
Ľ	&#317
ľ	ľ
Ŀ	Ŀ
ŀ	ŀ
Ł	Ł
ł	ł
Ń	Ń
ń	ń
Ņ	Ņ
ņ	ņ
Ň	Ň
ň	ň
ŉ	ŉ
Ŋ	Ŋ
ŋ	ŋ
Ō	Ō
ō	ō
Ŏ	Ŏ
ŏ	ŏ
Ő	Ő
ő	ő
Œ	Œ
œ	œ
Ŕ	Ŕ
ŕ	ŕ
Ŗ	Ŗ
ŗ	ŗ
Ř	Ř
ř	ř
Ś	Ś
ś	ś
Ŝ	Ŝ
ŝ	ŝ
Ş	Ş
ş	ş
Š	Š
š	š
Ţ	Ţ
ţ	ţ
Ť	Ť
ť	&#357
Ŧ	Ŧ
ŧ	ŧ
Ũ	Ũ
ũ	ũ
Ū	Ū
ū	ū
Ŭ	Ŭ
ŭ	ŭ
Ů	Ů
ů	ů
Ű	Ű
ű	ű
Ų	Ų
ų	ų
Ŵ	Ŵ
ŵ	ŵ
Ŷ	Ŷ
ŷ	ŷ
Ÿ	Ÿ
Ź	Ź
ź	ź
Ż	Ż
ż	ż
Ž	Ž
ž	ž
ſ	ſ
Ŕ	Ŕ
ŕ	ŕ
Ŗ	Ŗ
ŗ	ŗ
Ř	Ř
ř	ř
Ś	Ś
ś	ś
Ŝ	Ŝ
ŝ	ŝ
Ş	Ş
ş	ş
Š	Š
š	š
Ţ	Ţ
ţ	ţ
Ť	Ť
ť	Ɂ
Ŧ	Ŧ
ŧ	ŧ
Ũ	Ũ
ũ	ũ
Ū	Ū
ū	ū
Ŭ	Ŭ
ŭ	ŭ
Ů	Ů
ů	ů
Ű	Ű
ű	ű
Ų	Ų
ų	ų
Ŵ	Ŵ
ŵ	ŵ
Ŷ	Ŷ
ŷ	ŷ
Ÿ	Ÿ
Ź	&#377
ź	ź
Ż	Ż
ż	ż
Ž	Ž
ž	ž
ſ	ſ

28 December 2007

Two photos, by Diana Walker

STEVE JOBS AT HOME IN 1982 — "This was a very typical time. I was single. All you needed was a cup of tea, a light, and your stereo, you know, and that's what I had." —Steve Jobs

ANNE TYLER — The author Anne Tyler at home in Baltimore, Maryland, 1985.

Steve Jobs Said 【转载】

[from: http://ririanproject.com/2007/04/20/10-golden-lessons-from-steve-jobs/]
1. Steve Jobs said: "Innovation distinguishes between a leader and a follower."
Innovation has no limits. The only limit is your imagination. It's time for you to begin thinking out of the box. If you are involved in a growing industry, think of ways to become more efficient; more customer friendly; and easier to do business with. If you are involved in a shrinking industry – get out of it quick and change before you become obsolete; out of work; or out of business. And remember that procrastination is not an option here. Start innovating now!
2. Steve Jobs said: "Be a yardstick of quality. Some people aren't used to an environment where excellence is expected."
There is no shortcut to excellence. You will have to make the commitment to make excellence your priority. Use your talents, abilities, and skills in the best way possible and get ahead of others by giving that little extra. Live by a higher standard and pay attention to the details that really do make the difference. Excellence is not difficult - simply decide right now to give it your best shot - and you will be amazed with what life gives you back.
3. Steve Jobs said: "The only way to do great work is to love what you do. If you haven't found it yet, keep looking. Don't settle. As with all matters of the heart, you'll know when you find it."
I've got it down to four words: "Do what you love." Seek out an occupation that gives you a sense of meaning, direction and satisfaction in life. Having a sense of purpose and striving towards goals gives life meaning, direction and satisfaction. It not only contributes to health and longevity, but also makes you feel better in difficult times. Do you jump out of bed on Monday mornings and look forward to the work week? If the answer is 'no' keep looking, you'll know when you find it.
4. Steve Jobs said: "You know, we don't grow most of the food we eat. We wear clothes other people make. We speak a language that other people developed. We use a mathematics that other people evolved… I mean, we're constantly taking things. It's a wonderful, ecstatic feeling to create something that puts it back in the pool of human experience and knowledge."
Live in a way that is ethically responsible. Try to make a difference in this world and contribute to the higher good. You'll find it gives more meaning to your life and it's a great antidote to boredom. There is always so much to be done. And talk to others about what you are doing. Don't preach or be self-righteous, or fanatical about it, that just puts people off, but at the same time, don't be shy about setting an example, and use opportunities that arise to let others know what you are doing.
5. Steve Jobs said: "There's a phrase in Buddhism, 'Beginner's mind.' It's wonderful to have a beginner's mind."
It is the kind of mind that can see things as they are, which step by step and in a flash can realize the original nature of everything. Beginner's mind is Zen practice in action. It is the mind that is innocent of preconceptions and expectations, judgements and prejudices. Think of beginner's mind as the mind that faces life like a small child, full of curiosity and wonder and amazement.
6. Steve Jobs said: "We think basically you watch television to turn your brain off, and you work on your computer when you want to turn your brain on."
Reams of academic studies over the decades have amply confirmed television's pernicious mental and moral influences. And most TV watchers know that their habit is mind-numbing and wasteful, but still spend most of their time in front of that box. So turn your TV off and save some brain cells. But be cautious, you can turn your brain off by using a computer also. Try and have an intelligent conversation with someone who plays first person shooters for 8 hours a day. Or auto race games, or role-playing games.
7. Steve Jobs said: "I'm the only person I know that's lost a quarter of a billion dollars in one year…. It's very character-building."
Don't equate making mistakes with being a mistake. There is no such thing as a successful person who has not failed or made mistakes, there are successful people who made mistakes and changed their lives or performance in response to them, and so got it right the next time. They viewed mistakes as warnings rather than signs of hopeless inadequacy. Never making a mistake means never living life to the full.
8. Steve Jobs said: "I would trade all of my technology for an afternoon with Socrates."
Over the last decade, numerous books featuring lessons from historical figures have appeared on the shelves of bookstores around the world. And Socrates stands with Leonardo da Vinci, Nicholas Copernicus, Charles Darwin and Albert Einstein as a beacon of inspiration for independent thinkers. But he came first. Cicero said of Socrates that, "He called philosophy down from the skies and into the lives of men." So use Socrates' principles in your life, your work, your learning, and your relationships. It's not about Socrates, it's really about you, and how you can bring more truth, beauty and goodness into your life everyday.
9. Steve Jobs said: "We're here to put a dent in the universe. Otherwise why else even be here?"
Did you know that you have big things to accomplish in life? And did you know that those big things are getting rather dusty while you pour yourself another cup of coffee, and decide to mull things over rather than do them? We were all born with a gift to give in life, one which informs all of our desires, interests, passions and curiosities. This gift is, in fact, our purpose. And you don't need permission to decide your own purpose. No boss, teacher, parent, priest or other authority can decide this for you. Just find that unique purpose.
10. Steve Jobs said: "Your time is limited, so don't waste it living someone else's life. Don't be trapped by dogma - which is living with the results of other people's thinking. Don't let the noise of other's opinions drown out your own inner voice. And most important, have the courage to follow your heart and intuition. They somehow already know what you truly want to become. Everything else is secondary."
Are you tired of living someone else's dream? No doubt, its your life and you have every right to spend it in your own individual way without any hurdles or barriers from others. Give yourself a chance to nurture your creative qualities in a fear-free and pressure-free climate. Live a life that YOU choose and be your own boss.

21 December 2007

"The Seven Steps Toward a Thesis" - by Eduard Hovy

"The Seven Steps Toward a Thesis"

by Eduard Hovy
USC Information Sciences Institute

The idea
- Is there a claim?
- Is the claim clear?
- Is the idea large or small?
- Is the idea as large as it can be? Can you generalize it, or apply it elsewhere?
Motivation, Use, or Application
- Why should we care?
- How can the claim be used? Are there other applications?
Details of the Idea
- What are the basic items/elements /representation units of the idea?
- What are the rules or types of interrelationships between them?
- How elaborated are these items and rules/relationships?
- How much of the phenomena do they cover?
Data
- Is there enough data in the study?
- Is it representative? trustworthy? applicable?
Discovery Methodology
- Is the method of investigation clear?
- Is it appropriate? Does it ignore phenomena that look relevant?
- Is it well-reasoned? no biases or mistakes?
History
- Is prior work recognized? used?
Proof
- Is there an evaluation?
  - If so, is it adequate? Complete enough?
    - Does it speak to the claim?
    - Does it actually prove the claim?
  - If not, why not?
    - Is there a discussion of how one might try to test or prove the claim?
    - Can one make predictions and (easily) test them?

17 December 2007

Why Not C? What are O'Caml (caml.inria.fr) and Haskell (haskell.org)?

Why Not C?
Hal Daume III
-------------

I've been asked on many occasions a question like: "Why don't you use
x", where x is "C", "C++" or "Java." There are, of course, many
reasons, but here is list the four that I find most compelling. These
all essentially boil down to the fact that I think a programming
language should be a friend who helps you accomplish your goals, not
an enemy you should have to fight with.

1. I refuse to allocate my own memory.

I find the process of dealing with low-level bugaboos like allocating
memory obnoxious. It serves only to clutter otherwise clear code. It
also makes debugging a major hassle and causes programs to core dump
like crazy. I'm aware of various libraries that allow some languages
that don't have build in memory management to do naive things like
reference counting, but this is -- if nothing else -- simply an
admonishon that your language has failed you. Memory management is
not something that should be tacked on to a language in the form of a
library. I believe this for many reasons: aesthetics, efficiency,
etc.

2. I refuse to write 20 lines where one will suffice.

This is mostly aimed at Java, since I don't really know of any other
language that got this so wrong. The whole "everything must be a
class" thing with Java is just such a pain to deal with. Comparing,
for instance, the Hello World program in C to Java is just laughable.
More than that, I also just don't find the whole OO paradigm all that
expressive. Everything I want to express is typically easily
accomplishable with a simple data type declaration and a few simple
functions on that data type. This refusal also includes refusing to
write 20 characters when one will do (e.g., x.equals(y) rather than
x=y).

3. I refuse to live without higher order functions.

This might seem a bit elitist, but once you get use to writing code
with higher order functions, it's really hard to go back. Sure, C has
function pointers, C++ has something nasty like that and Java has
anonymous classes, but this is all just really too much hassle for
dealing with something so basic (see point 2).

4. I refuse to live without algebraic data types.

They are simply too expressive. Try writing code for reading in parse
trees in C or C++ or Java (for a real challenge, do it in Perl). This
is just a painful experience. Algebraic data types are too useful to
live without, especially when dealing with any sort of structured
data. Having to introduce heavy-weight classes to handle the same
thing is overkill (not to mention terribly inefficient).

So that sums it up, more or less. My languages of choice, of course,
are O'Caml (caml.inria.fr) and Haskell (haskell.org). I wind up using
O'Caml for everything, primarily because the code it produces tends to
be more efficient than Haskell and because it has better support for
arrays. I would write Haskell exclusively if it optimized array
operations better and had built-in syntax supporting them.

13 December 2007

A student from that lab

His Blog:
http://jackylee0424.spaces.live.com/default.aspx

Experience Talk (2)

发信人：DavidChiou@bbs.ee.ntu.edu.tw (邱大刚)
日期：03 Apr 1998 09:39:18 GMT
标题：Re: MIT Media Lab admission
信群：tw.bbs.campus.advancededu看板：AdvancedEdu
代号：< 3Nk1S7$pDz@bbs.ee.ntu.edu.tw>
组织：台大电机Maxwell BBS

> >刚刚接到一封信,是MIT Media Lab的admission,
> >加上RA奖学金（凡是被接受的都有RA）。该lab是
> > MIT研究多媒体相关技术专门的研究所.
>看了您的入学背景资料，小弟实在相当钦佩！
>我想基本上我们是走相同领域的人，想请教您当时申请MIT时是申请EE还是CS？
> （因为不太知道MIT Media Lab算是EE还是CS的？）

照比较通俗的讲法，MIT Media Lab算是一个与多媒体相关专门的
研究所，是在EECS研究所之外，于1985年新成立的专门研究所。
综合EE/CS/Art/Psychology等领域的人来作相关研究，去年有本畅
销书「数位革命」，就是在描述该Lab的发明等等，研究的技术诸如
digital television, holographic imaging, computer music,
computer vision, electronic publishing, artificial
intelligence, human/machine interface design, and
education-related technologies.等等。

该研究所目前并没有大学部。至于该校EE/CS中自然也会有与这方
面相关的研究，不过据我所知其比重就较少，而且较偏向理论，与Media
Lab偏向应用是不同的，可说该研究所为MIT多媒体方面的重镇。

详细的介绍可见http://www.media.mit.edu。在台大资讯BBS
（telnet://bbs.csie.ntu.edu.tw login:bbs）中留学版的精华区
已整理许多相关的资讯，有兴趣的朋友可以参考。

>是EE还是CS的？）

MIT EE的录取率约1/5, CS录取率约1/20, Media Lab的录取
率介于二者之间（与EE差不多）。目前CS领域没有台湾毕业后过去的，
EE方面据悉1992, 1996分别有台大电机系学长申请上，Media Lab
目前好像只有一位台大电机系学长在念PhD，尚不知详情。

不过其实在台湾的毕业学校或许不是重点，重点是要合乎他们的须要。
毕竟该研究所台湾人极少（我可能是第2个），人家不大会知道台湾什么
大学比较好。

> ，所以想请教一下，要如何申请到这样的名校！有什么要注意或加强的？（
>虽然您之前的post已经写很多了，让我受益良多，真是感谢！）希望您
>能补充，好吗？

方才已张贴「申请TOP研究室经验」，希望能有所帮助:)

申请MIT这一路的记载及经验，都完全记录在台大资讯站的精华区。

祝好运! :)

--
无心者公无我者明
--
※ Origin:台大电机Maxwell站◆ From: dclcad6.ee.ntu.edu.tw

Experience Talk

[Source: http://bbs.nsysu.edu.tw/txtVersion/treasure/oversea-study/M.884577628.A/M.884759413.A/M.1004028781.A/1-15 ]

发信人：DavidChiou@bbs.ee.ntu.edu.tw (邱大刚)
日期：03 Apr 1998 04:53:24 GMT
标题：申请TOP研究室经验-前言
信群：tw.bbs.campus.advancededu看板：AdvancedEdu
代号：< 3Njg6b$ofq@bbs.ee.ntu.edu.tw>
组织：台大电机Maxwell BBS

前面看了小弟的标准化资料，相信会跌破许多人的眼镜。
然而其实要申请上顶尖的研究所，常常是不能只靠GPA、GRE、
TOEFL等标准化成绩的，毕竟全世界到处都有大学，每间大学
都有最高分的人，要考高分有时只差在K不K书而已:)

可是在特殊的研究领域有所专才的人，就不见得那么多了，
尤其若是本身的才能与对方教授所须的人才契合的话，这特别会
是对方在全球无数申请者中，选出你的原因。

然而话说回来，通常要申请上顶尖的研究所，如果GPA不
高的话，在第一关就被刷掉了，要能被录取也的确是蛮靠运气的，
这就靠个人的造化了...我的意思只在于录取顶尖的研究所，不
能光靠GPA，也必须也靠其他的方面，才有机会脱颖而出。

以下个人将之所以能申请上MIT Media Lab的原因，依照
重要性先后来排序，作一个小小的分析。这只是个人的经验，
并非放诸四海皆准，只希望将这个案例提供未来的申请者作一个
小小的参考。

皆下来将就个人的经验，将以下七点，分别略述：

□与教授投缘
□工作经验
□推荐信
□著作、奖项
□成绩
□态度
□周边的人

-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-. -.-.-.-.-.-.-

--
无心者公无我者明
--
※ Origin:台大电机Maxwell站◆ From: h103.s103.ts.hinet.net

发信人：DavidChiou@bbs.ee.ntu.edu.tw (邱大刚)
日期：03 Apr 1998 04:55:30 GMT
标题：申请TOP研究室经验-与教授投缘
信群：tw.bbs.campus.advancededu看板：AdvancedEdu
代号：< 3Njg9J$ofo@bbs.ee.ntu.edu.tw>
组织：台大电机Maxwell BBS

□与教授投缘

这位教授的研究领域，刚好与先前我所有的经验与资历符合。
然而她在人文方面亦学有专精，这点我比较没有正式的资历，于
是也向她请教要如何弥补这一方面，她也给予正面的回应，我就
照作。也因此我个人的专才与她所须的人才，是个不错的契合，
这是能够顺利申请最大的关键，我想也是未来作研究开不开心的
最大关键:)

尤其若最终目标是要读到PhD的话，老板会陪你好几年，
而老板也会很小心地挑要陪他好几年的人。

*申请时程记录:

在去年四月，我决定要出国后，就发E-mail给这位教授了：
她的HomePage上有列出过去的所有研究主题及paper。我瞄到
其中一个project因为当时时局的关系（Netscape及MS已占去
大多的web browser市场），所以已中止了。然而实际上照新的
技术来说，不须要透过browser就可以达成同样的service。
于是我就写了蛮详细的说明，将该project如何能够复活的各种
可能性作一番分析，E-mail给她。信的最后提说我准备要出国，
正在考虑她的group，请问她是否收学生云云。

结果这封信一去不回，她没回信。

年中的时候，我又发了一封E-mail，说有意明年申请出国，
请问她须要的是哪一方面人才? E-mail上并attach自己的RESUME，
并且提过以前寄过的那封信。

这次她就回信了，说前阵子不在，所以一直没回信、很抱歉云云，
然后说看了我的RESUME觉得很不错，对于他们的研究来说是a good
match。就这样，我决定了要申请这个研究小组。

之后一直有保持联络，例如她的web当了，我也会去提醒一下:p
后来还有一些事件，造成她会对我印象特别深刻，兹举例如下。

*验证实力

1.对于已中止的project的idea

如前所述。其实这项的帮助并不会很大，因为既然该project
已中止了，就不大可能会重新继续。不过因为我对这方面很熟，
所以最少可让教授知道我在这方面的热心与实力。

2.将所有以前papers全部读完并且做心得报告

在寄出申请书之前，我将先前的papers几乎全部印出来读完，
并且针对每份写出心得报告。报告中先将从此paper中学到的
精采佳句录出，然后写自己的相关idea。我将精采的idea摆
前面，平庸的摆后面。（没用的idea当然就不写。而且语句
都是用很客气的"may"这种，毕竟人家是这方面的专家，要是
我写错的话反而就丢脸了。）

这份报告有10页之长，排版也很清晰，附在申请书中寄出去。
而且其中有少数几个idea本身就可以成为一个单独的研究主题。

Anyway,其实应该是要重质不重量， 10页那么长的东西，人家
教授不可能会仔细看的，我只是因为个人嗜好，所以写得很详细，
一方面多多学些东西，也可供以后自己被录取后参考之用。单就
申请来说，若只将最重要的idea写出来，简洁有力，应该效果
会最大。

去年还有台大电机系第一（or二?）名毕业，申请Stanford EE
的学姊，先将申请教授的著作买了读过，再用E-mail和该教授
讨论问题，并且到美国去interview，最后得到Stanford EE
admission加上奖学金的案例。简言之，对于这种顶尖的研究室，
要有奖学金，能多付些心思是较好。

3.发现MIT Media lab主机的问题

有一次机缘凑巧，发现跟该研究小组相关的一个网路主机的bug
（其实不算bug，只是因为负责的学生在忙，还没完全装完而已）。
就提醒他们可以改善这点。这事还惊动了MIT Media lab其它
小组的人，相信让对方对我在网路上的能力也有点印象。

4.解答悬疑二年的问题

有次我玩http://www.dejanews.com上面的newsgroup搜寻
引擎。玩着玩着，突然想到输入该教授的名字看看，就看到许多
以前她提出来的问题、别人的回应，还有别人提到她作的系统的
posts等等。

其中有一封是二年前她post的，最后大家的结论是「没救」。
我将问题仔细看过后，发现根本不须要用那种方式来处理此系统，
换种方式就OK了，不会有bug。于是就post给她。二年了，
当中没有任何人能够解决她的这个小bug，而我解决了此问题。
虽然不是什么重要的见解，然而也是很精采的一笔。

5.改善现今的系统

现今的系统还有些效率的问题等等，或是一些网页上有小问题，
我发现时也会顺便通告一声。这位年轻教授是自己写网页的，
所以通告这些事情也算是小恩小惠，相信也有一点点帮助。

最重要的一点是，我们是在和"人"互动，尊重对方的感受是很
重要的，所以我都是用很客气的语气E-mail（这和在Statement of
Purpose上面很有自信的表现方式是截然不同的。毕竟人家自己知道
自己的研究方向，你如果idea的确有价值，就算相当客气，也会很
闪耀），也声明说仅供参考，了解对方很忙，所以不必回信没有关系，
只是顺便发现所以义务帮忙而已。让对方在没有心理负担的情况下提供
admission。也要小心不要让人觉得像苍蝇一样，尤其是对于大牌教授，
一定要言简意赅，他们天天忙得不得了，没时间管这些。

在审核开始后，我也有顺便提到若有须要interview，我可自费
到美国，因为最喜欢的就是该group的研究。纵使没有奖学金也没
关系，我很愿意自己出钱。（结果最后只须要一个phone interview，
并且拿到full RA:免学费，还加上每个月约台币五万元的薪水。）

MIT Media Lab的录取与否，最大的因素在于该教授要不要收你
（其他学校则不一定，许多是由committee审核的），而在这一点我
得到了肯定，是申请成功的关键。

再者，对于其他有研究实力、却可能成绩不很好的同学，直接与
有兴趣的教授联络，肯定是有帮助的。因为审核委员会对你的专才不
见得有兴趣，更可能不知道你专才有什么价值，可是对方"教授"自
然是求才若渴，对他来说研究能力不亚于成绩的重要性，成绩高代表
你会K书、有毅力读书，却不代表一定能有利于他的研究。也因此，
如果你的能力能契合对方的须要，而且让对方明白这一点的话，相信
就是成功的第一步了。

-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-. -.-.-.-.-.-.-

--
无心者公无我者明
--
※ Origin:台大电机Maxwell站◆ From: h103.s103.ts.hinet.net

发信人：DavidChiou@bbs.ee.ntu.edu.tw (邱大刚)
日期：03 Apr 1998 05:08:18 GMT
标题：申请TOP研究所经验-工作经验
信群：tw.bbs.campus.advancededu看板：AdvancedEdu
代号：< 3NjgPJ$orr@bbs.ee.ntu.edu.tw>
组织：台大电机Maxwell BBS

□工作经验

有位在美国的教授在来台大的座谈中提过，有正式工作经验的人，
通常会比较负责，因此他们觉得选择有工作经验的人是蛮不错的。尤其
若工作经验与他们的研究相关的话，自然能在入他们的研究小组后迅速
上手，这会对他们的研究非常有帮助，因此是一大好处。

个人现在是AT&T Labs-Research（全球顶尖通讯实验室之一，要
说是全球第一也不为过）的研究助理。这是个全球知名的实验室，而
美国人对于AT&T相当有好感。相信这点也是重要关键。

个人原本是AT&T summer student名额，去年同期由于AT&T
预算裁减，所以全球只有8个summer student，其余7位都是
UC Berkeley等名校的研究生，只有我1个人是台大大学生。
后来因为表现不错、老板也很好心，就将我的summer contract
延长至一整年。这一年的工作经验，不但学到了许多，而且对我的申
请也十分有帮助。国外教授一听是在AT&T作研究，立刻眼睛就亮起
来了。（当然人家也会追问工作性质等等。）

实际上，这类跨国公司在台湾通常没有R&D研究部门，或是
在台湾只有很小的研究部门。（不过我们研究室是直属于美国总部的。）
总之，要加入这类跨国研究室（HP等也是），只要机缘到了，那么在
台湾甚至比在美国应征还容易，因为他们在台湾比较没有求才的管道
你如果刚好遇到这个机缘，就把握吧! :)

我个人是被教授推荐去的，当初其他同学还都不敢接这个case呢。
算是很幸运。

-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-. -.-.-.-.-.-.-

--
无心者公无我者明
--

发信人：DavidChiou@bbs.ee.ntu.edu.tw (邱大刚)
日期：03 Apr 1998 05:09:55 GMT
标题：申请TOP研究室经验-推荐信
信群：tw.bbs.campus.advancededu看板：AdvancedEdu
代号：< 3NjgRK$ojx@bbs.ee.ntu.edu.tw>
组织：台大电机Maxwell BBS

□推荐信

听说许多国外的教授在审台湾人时，推荐信都最后看，因为有经验
的人都知道台湾的推荐信写得很浮滥。我在AT&T的老板还说，以前他
帮忙审admission时，看到台湾一大堆人的推荐信都是勾1%的，太
假了。也因此AT&T的老板说他不给我都勾1%，以免让人觉得浮滥。

也因此，虽然在美国本土来说推荐信甚至是最重要的条件之一（不
亚于成绩），然而在台湾的推荐信特别不值钱，这点是蛮可惜的。

至于我个人的推荐信则是很好的。（虽然说出自台湾所以多少会打
折。）四封推荐信中，二封是专题教授，一封是AT&T的supervisor，
一封是导师，而以前三封为主。

这三封都是我有扎扎实实努力作研究时的老板，我在二学分的专题
研究上，花的时间相当于其他所有科目加起来，而且也有研究成果，并
且还帮老板带其他的学弟妹，因此很获看重，推荐信更是推心置腹。专
题老师还打算亲自帮忙和他母校的朋友联络，不过当然因为一开始就有
MIT的消息，所以就先搁置着没联络，拿到MIT admisson后就不须要
麻烦他了。

也因此，如果你是真的在作研究，而老板的确很想帮忙的话，那么
如果能让他们和他们母校中的熟人联络，应会蛮有帮助的，否则台湾人
的推荐信常会被打折，这点要有心理准备。再者，纵使你老板是名校毕
业的，也不见得对你申请该校有帮助，一定要他在信中特别注明（除非
admission committee都认识他），或是必要时由他帮忙联络母校的人，
才会比较有用。如果他在该校的科系与你的科系不同，那自然也不会有
帮助，就跟台大电机跟台大土木的教授彼此不会认识一样，和台大电机
的教授聊说你认识台大土木的教授，并不会因为同样是「台大」的教授
而有特别的帮助。（不过当然若该教授能证实你的能力，那么不管是什
么学校或科系的，都很有帮助。）

再者，MIT的教授有打电话给我的老板，询问我的情形。结果当然
是很不错。不过当然一般学校不会这么严，所以这种情况比较少见。

-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-. -.-.-.-.-.-.-
--
一个人既然是一个文化分子,于是他的内心就怖满了价值观念:
他做任何事情都是考虑"值不值得"... －殷海光,中国现代化的问题.
--

发信人：DavidChiou@bbs.ee.ntu.edu.tw (邱大刚)
日期：03 Apr 1998 05:11:59 GMT
标题：申请TOP研究室经验-著作、奖项
信群：tw.bbs.campus.advancededu看板：AdvancedEdu
代号：< 3NjgU0$o1q@bbs.ee.ntu.edu.tw>
组织：台大电机Maxwell BBS

□著作、奖项

其他学校这种状况比较不明显，不过MIT Media Lab的人似乎都是
带着一拖拉库的奖项，各种区域比赛、全国比赛、世界比赛，不管是
EE/CS方面甚至是Art方面的，能证明在与该研究小组的领域有专才，
自然是最好。

至于有著作的话自然是黄袍加身，若跟要申请的研究小组相关，更
是炙手可热。不要过注意的是必须早点submit，最好在申请书寄出前
知道是否被录取了，这样子才会记录在申请书上。

-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-. -.-.-.-.-.-.-

--
悠哉贤故友,抱道乐林泉,坐到无疑地,参穷有象天,
胸中消块垒,笔底走云烟,更笑忘机鸟,常窥定后禅。

-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-. -.-.-.-.-.-.-.-.-.-.-.-.-
欢迎光临【狮子吼站】：佛教、慈善、台大社团、健康饮食、X档案
IP Address: cbs.ntu.edu.tw ( 140.112.143.30)
--

发信人：DavidChiou@bbs.ee.ntu.edu.tw (邱大刚)
日期：03 Apr 1998 05:13:42 GMT
标题：申请TOP研究室经验-成绩
信群：tw.bbs.campus.advancededu看板：AdvancedEdu
代号：< 3NjgW7$oHm@bbs.ee.ntu.edu.tw>
组织：台大电机Maxwell BBS

□成绩

成绩自然通常是最先考虑的，除非有其他方面弥补。

TOEFL通常600以上就没什么大差别了，就如同我们不会因为有
个美国人中文成绩满分，就收他进来（中文系除外）。

GRE的话听说对于申请奖学金会蛮重要的，甚至有的学校在审核
奖学金的时候，是依照GRE成绩来给的。而通常印度人及大陆人的
GRE成绩都相当高，所以台湾人申请MS很少有奖学金。不过当然若
教授因为你有研究能力而肯给你奖学金，那么就可弥补GRE的不足了。

GPA自然是最重要的之一。但overall GPA不好的人请别灰心，
因为听说美国有的学校GPA给的也是蛮严的，3出头也算是不错的GPA。
世界上每个学校、每个系都有自己的GPA标准，因此3.5不见得是高、
也不见得是低。这点大家自己不要先缺乏信心:)不过当然能到顶尖的学
校，除非有特殊长才，否则通常GPA都是超高的。

如果您在哪几科与申请领域的成绩特别高的话，甚至可以列出一
张表，将特别高的科目突显出来、甚至标上名次，这样子该校才会知
道您这方面很强（否则人家根本不会注意到这事!每天有上百份申请
书要审。），而不仅止于看您的overall GPA。

-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-. -.-.-.-.-.-.-
--
悠哉贤故友,抱道乐林泉,坐到无疑地,参穷有象天,
胸中消块垒,笔底走云烟,更笑忘机鸟,常窥定后禅。

-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-. -.-.-.-.-.-.-.-.-.-.-.-.-
欢迎光临【狮子吼站】：佛教、慈善、台大社团、健康饮食、X档案
IP Address: cbs.ntu.edu.tw ( 140.112.143.30)
--

发信人：DavidChiou@bbs.ee.ntu.edu.tw (邱大刚)
日期：03 Apr 1998 05:14:51 GMT
标题：申请TOP研究室经验-态度
信群：tw.bbs.campus.advancededu看板：AdvancedEdu
代号：< 3NjgXS$ofw@bbs.ee.ntu.edu.tw>
组织：台大电机Maxwell BBS

□态度

在写SOP时，态度要相当有自信。（但是不能乱写，那会露出
马脚。所以最好要找贵校研究所该领域的教授请益。）

在亲自联络时，态度要客气与诚恳、并为对方着想。

在整个申请的过程中，态度不要封闭、要乐于和他人分享资讯，
这样子更会得到源源不绝的帮助，共同增上。我觉得纵使admission
不谈，在这过程中学到了很多的经验，我们可以将原先觉得申请学校
很麻烦的心态转过来，从另一个角度，就会觉得在这当中获得许多成长了。

在等待结果的历程中，不必太紧张。毕竟此时紧张用处不大，
放轻松、好好过日子，可活得久一点:)大不了明年再来，到时本
钱又更好，谁怕谁:)当然接到rejection,尤其是连番的rejection
轰炸，多少会有些难过，然而毕竟生活不是只为了一个admission，
心胸练习着更开阔些，就较不会在意了:)

我也是接了6个rejection（其中4个大概是因为缺GRE CS
Subject）,然后才接到一个recommendation,后来才接到正式的
MIT admission的。

个人在接到MIT admission后就立刻将其它的admission谢
绝、将结果尚未公布的学校放弃申请，以避免占到人家的名额。毕
竟学校只须要去一家，而一个人有没有品才是我们能在社会上立足
的重要因素。

所以在申请的时候可以多申请几家，以防万一，不过当有好消
息时，别忘了其他还在等待的朋友。如果确定不去哪一家的话，就
赶快退掉吧，让别人干着急是不好的事，早点退掉不须要的
admission，利人利己，皆大欢喜。

-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-. -.-.-.-.-.-.-

--
悠哉贤故友,抱道乐林泉,坐到无疑地,参穷有象天,
胸中消块垒,笔底走云烟,更笑忘机鸟,常窥定后禅。

-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-. -.-.-.-.-.-.-.-.-.-.-.-.-
欢迎光临【狮子吼站】：佛教、慈善、台大社团、健康饮食、X档案
IP Address: cbs.ntu.edu.tw ( 140.112.143.30)
--

发信人：DavidChiou@bbs.ee.ntu.edu.tw (邱大刚)
日期：03 Apr 1998 05:17:33 GMT
标题：申请TOP研究室经验-周边的人
信群：tw.bbs.campus.advancededu看板：AdvancedEdu
代号：< 3Njgak$ofo@bbs.ee.ntu.edu.tw>
组织：台大电机Maxwell BBS

□周边的人

MIT Media Lab的academic head，一位国际知名的教授，在
去年底到中研院出席一项国际学术会议时，我和他遇到了（这要谢
谢cyy学长的告知，我才跑去那个国际会议参观）。因为机缘凑巧，
没人要带他去买画，就变成我带他大老远去买画，和他在计程车上
用英文聊了很久，相谈甚欢。（聊的大多不是学术上的，而是各国
民俗以及他的见闻。）

一开始在带他去买画前，我请他帮忙转递RESUME时，他自然
是不大愿意，说太忙了，所以我就不勉强他，赶快收起来我的RESUME。
后来因为谈得很高兴，他甚至秀给我看MIT PhD的信物戒指，说若
我在那毕业就会拿到那戒指云云。离去之前，还主动跟我要我的
RESUME，说会亲自交给申请的教授。

而申请的教授后来还E-mail给我，说那位教授和我谈得
很高兴。我想这是很有帮助的，所以才能一个phone interview
就得到admission了（一般都须要特地跑到美国去interview）。

不过这种机会实在是可遇而不可求，也蛮巧的，随缘吧。只
不过若刚好让你遇到这个机会，就别吝于广结善缘:)

而在申请的过程中，其余一同奋斗的人，也是相当重要的，
团结力量大，大家加油吧! :)

-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-. -.-.-.-.-.-.-

--
悠哉贤故友,抱道乐林泉,坐到无疑地,参穷有象天,
胸中消块垒,笔底走云烟,更笑忘机鸟,常窥定后禅。

-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-. -.-.-.-.-.-.-.-.-.-.-.-.-
欢迎光临【狮子吼站】：佛教、慈善、台大社团、健康饮食、X档案
IP Address: cbs.ntu.edu.tw ( 140.112.143.30)
--

问答录：MIT Media Lab

February 21
你好想请教有关MIT Media Lab

Hi,你好我是台湾的学生，对MIT media lab很有兴趣，之前就听说有一位成大的学长很厉害被MIT media lab挖角，真是羡慕死了！没想到今天竟然就逛到你的网页，真是幸运呀～

你好你可以让我知道你的背景现在在哪念书念的是什么有做过什么样的研究这样我比较了解和谁在说话不好意思，冒昧问了你那么多问题却忘了自我介绍……

简单说明一下我的背景：我大学念清大life science，辅系computer science、台大biomedical egineering研究所毕业，做过neuroscience 、cancer vaccine和bioinformatics （especially focusing on genomics）等方面的研究，发表过一篇nanotech相关的短文，三篇posters、目前还有一篇paper刚送出去正在审。 award方面、大学和研究所都得过一些奖学金、硕士论文得过两个奖，办过几次摄影展结果不小心就上了远见杂志、作品得过全国比赛第三名。

TOEFL>250 (CBT) 至于为什么会对Media lab产生兴趣，却又不确定这适不适合我呢？喜欢摄影的人特别擅长观察，学理工的人又特别喜欢逻辑思考，坦白说，我脑海中经常蹦出奇怪的新点子，当然不是那种天马行空遥不可及的点子，而是这些构想是经过思考其可行性及需求的、我不只是想，还曾经一一画出设计图、找到可应用的现有技术。

为此我还一度以为自己要朝产品设计的领域发展，后来发现大部分的产品设计（或工业设计）多偏重于外型设计，着重"造型"上有所突破，与我的理想不符，因为我的构想大多牵涉到功能方面，造型及机构设计只是其中一部份而已。要达到这些功能，有些是需要结合IT、EE领域的新技术，有些是要牵涉到材料、有些是跟生物技术相关的、当然也有些构想只需要应用习知已久的技术就可以达到。

而我所在的环境是以生物医学的学术研究为主，所以让我觉得要将这些构想实现，在我目前所处的时空环境下是会事倍功半的。我得知MIT media lab的风气是鼓励新构想的实现、并更能刺激新点子产生、而这里的研究内容又很广泛，并不仅限定于单一领域，同时又与业界有密切的接触，这是否正符合我的特质呢？

但是，如上封信所述我对Media lab的了解不够深，我不确定这里是否真的跟我所认知的一样。不过，至少当我看见某些我脑海中的点子在media lab的网页上有人正将它化为实现的时候，那种得到共鸣的兴奋感是很强烈的！所以我才只好请教你啰～以上就对media lab目前的了解如有错误请指正。看完我写了这一堆，就你的观察和经验，你觉得media lab适合有我这类想法的人吗？还是有你觉得更适合的选择？

嗯,看到你惊人的经历,现在是在读博士吗?还是在哪做研究? 看来我也要自我介绍一下,我大学念成大建筑(志愿是爸爸填的,因为他想让我当建筑师),大学的时候只喜欢玩,不喜欢读书,后来一值专注于画3D,还好有几个老师鼓励我,让我毕业(大学GPA<3)并且上了建筑研究所।研究所的时候投了两篇conference>250门槛। -- 由于我目前正在准备出国念书，但是毕竟选学校是个不能马虎的决定，然而我遇到最大的困难就是不确定MIT media lab是否真的适合我，毕竟每个人的需求不同，要找到最适合自己的program才能发挥最大的效益，不是吗？但是光看学校网页上的介绍，又借了"MIT media lab"这本书来看，总觉得还是隔了一层……

不知道你是否有空可以分享一下在MIT media lab的经验呢？我和你有点不依样我当时想出国念书的目的就是为了要来MIT Media Lab।所以那时候只丢了两间.我觉得要找到适合自己"兴趣"的program更重要. "发挥最大的潜力'比'发挥最大的效益'重要多了.

之前我是读建筑的,就能力上而言, media lab并不适合我,但是我并不担心,而且这反而是我想学更多的动力.介绍你另一本有关MIT Media Lab的书- e猫掉进未来汤,这本书更能反映我这里的环境我很好奇，当初你是如何确定MIT media lab就是最适合你的选择呢？就学生而言，"潜力"这两个字比"效益"适合多了，谢谢！
我这边写得不完整，我指的是学生到了适合的地方，不管对学生或是对老板、对lab、对学校，整体的效益才会是最大的。效益这个字也许不是很贴切吧！ anyway……

2001年底Bill Mitchel(当时media lab的head)到台湾来演讲的时候,看到了那时候的一些project,让我眼睛一亮,就觉得非来不可了,突然感觉到其他地方都太无聊了,原本以画3D讨生活的我,顿时间觉得3D实在是太无聊,电脑里的东西又碰不到,太假,想要作一些真正能让人摸的到,感觉的到的东西,然后就在2002年的时候申请MIT Media Lab 2003的秋季班. -- 第一个我想请问有关申请方面，如果没有十分厉害的作品，是否就比较难申请上？

另外，programming能力若不到"精通"的地步，是否念起来会很吃力？在我看来作品是反映一个人的观点,创造力,与能力.如果你有很特别的观点,配上新奇的点子和不错的能力.作品就会很厉害了. programming是实作上的需求,这点要自己要求自己,自己认为学够了就够了毕竟创造力是一回事，写程式是另一回事.一般而言你们coding占所有工作时间的比重有多高？大部分的时间是花在写程式为主吗？除了写程式、设计电路、作外形等之外，落实想法的方法你们还会用到哪些？如果遇到不能用电脑解决的事情、例如像不同的材料应用，这时候会怎么做？应该也常和校内其他lab合作吧…

Coding要看project,我自己的大部分都是以设计概念,外型,感测方式,和电路为主,遇到coding的就都找其他同事一起合作.有关材料方面,我有哈佛的学长专门研究智慧型材质,资讯方面都是从这里的朋友得来的.

-- 你的作品这么出名，一定有不少企业会希望将你研究设计的东西商品化，那么这中间你们与业界合作的模式是怎么进行的呢？我蛮好奇的耶…… 我不懂你说的是哪个作品,我的作品有有名的,也有没名的.但是企业是把钱花在刀口上,所以要看时机.通常我们做研究是不管企业要什么 -- 大部分的PhD programs都是为了培养学术研究人才，所以发的paper越多越好就越吃香，然而据我的了解MIT media lab相对其他系所是比较"需求"导向，或说"商品"导向，与业界合作也很频繁（如有错误请指正），因此你觉得在这个环境念PhD应该是写论文、发paper比重较高还是与业界合作比重较高呢？你扮演的角色除了研究设计之外，还有牵涉到其他方面吗？
media lab是个学术单位,学术成就是很重要的,只是我们的研究都偏生活,所以研究的主题很有变成商品的潜力.平常在研发之余就是在赶paper的deadline(例如CHI,SIGGRAPH,IUI ,UIST等等的会议,请自行google一下).我所扮演的脚色除了要找出设计的需求和作设计之外,我还要动手做出来设计sensor,电路,作外型,写程式.

这个领域是不是以conference paper为主而非journal paper呀…… 因为journal不用跑去当地发表压,为了要多往世界各地跑,投conference paper不是比较恰当吗 -- 另外，我常听说有人在与同学讨论或和厂商合作的过程中，自己提出来的新创意被合作讨论的对象窃取，当然，自己的老板也不见得了解真相。在MIT这个竞争激烈的环境，你们如何避免这种事情发生，万一发生了会怎么处理呢？我觉得创意被别人采纳并且拿去用是一件很好的事我很希望我的创意被大家采用大部分mit的研究人员也都是如此想的所以有了好的创意,其实第一件事就是要到处和大家说争取不同的建议让别人来告诉你你的创意新不新可以怎么改善 -- 最后是比较世俗的问题，但是还是忍不住想问一下，若是企业靠你的商品赚了一大笔钱，他们……会分你一杯羹吗？还是研究的归研究…做生意的归做生意？ …钱不重要专心作研究就好呀？另外专利归属是归学生、老师、还是学校、厂商？这个状况还没发生耶如果发生之后我在和你说专利的归属请你参考http://www.media.mit.edu/sponsors/ip.html 做研究和做生意的的确是两回事我做研究也不是为了赚钱只是想在更好的环境做研究如果真的只想赚钱或是享受生活那我就会去开个咖啡店炒炒股票了如你所说的你们的作品都很有变成商品的潜力，换句话说，当有人对你们的作品有兴趣想开发成商品的时候，你们彼此间扮演的角色是什么？合作模式是什么？

"full sponsors of the Laboratory have the opportunity to share in all of its intellectual property, license-fee free and royalty free."也就是说sponsor赞助学校经费，借此学校提供资源给学生，学生进行创意和作品的开发，产出的专利可供sponsor任意使用……这样对吗？是的.所有的专利都是给media lab sponsor所共有的. -- 是否有人将media lab开发设计的东西商品化然后自行创业呢？很多 -- 不好意思，问题有点多，希望你没有被我烦到～～恩，若你有空希望能分享一些经验，感谢感谢！不知该怎么回报你，需要点台湾名产吗？欢迎来信订购…… Good luck for your application and我想吃廖家牛肉面和安平虾卷请想办法帮我带来

10 December 2007

KMP算法详解【转载】

如果机房马上要关门了，或者你急着要和MM约会，请直接跳到第六个自然段。我们这里说的KMP不是拿来放电影的（虽然我很喜欢这个软件），而是一种算法。KMP算法是拿来处理字符串匹配的。换句话说，给你两个字符串，你需要回答，B串是否是A串的子串（A串是否包含B串）。比如，字符串A="I'm matrix67"，字符串B="matrix"，我们就说B是A的子串。你可以委婉地问你的MM："假如你要向你喜欢的人表白的话，我的名字是你的告白语中的子串吗？" 解决这类问题，通常我们的方法是枚举从A串的什么位置起开始与B匹配，然后验证是否匹配。假如A串长度为n，B串长度为m，那么这种方法的复杂度是O (mn)的。虽然很多时候复杂度达不到mn（验证时只看头一两个字母就发现不匹配了），但我们有许多"最坏情况"，比如，A= "aaaaaaaaaaaaaaaaaaaaaaaaaab"，B="aaaaaaaab"。我们将介绍的是一种最坏情况下O(n)的算法（这里假设 m<=n），即传说中的KMP算法。之所以叫做KMP，是因为这个算法是由Knuth、Morris、Pratt三个提出来的，取了这三个人的名字的头一个字母。这时，或许你突然明白了 AVL 树为什么叫AVL，或者Bellman-Ford为什么中间是一杠不是一个点。有时一个东西有七八个人研究过，那怎么命名呢？通常这个东西干脆就不用人名字命名了，免得发生争议，比如"3x+1问题"。扯远了。个人认为KMP是最没有必要讲的东西，因为这个东西网上能找到很多资料。但网上的讲法基本上都涉及到"移动(shift)"、"Next函数"等概念，这非常容易产生误解（至少一年半前我看这些资料学习KMP时就没搞清楚）。在这里，我换一种方法来解释KMP算法。假如，A="abababaababacb"，B="ababacb"，我们来看看KMP是怎么工作的。我们用两个指针i和j分别表示，A[i-j+ 1..i]与B[1..j]完全相等。也就是说，i是不断增加的，随着i的增加j相应地变化，且j满足以A[i]结尾的长度为j的字符串正好匹配B串的前 j个字符（j当然越大越好），现在需要检验A[i+1]和B[j+1]的关系。当A[i+1]=B[j+1]时，i和j各加一；什么时候j=m了，我们就说B是A的子串（B串已经整完了），并且可以根据这时的i值算出匹配的位置。当A[i+1]<>B[j+1]，KMP的策略是调整j的位置（减小j值）使得A[i-j+1..i]与B[1..j]保持匹配且新的B[j+1]恰好与A[i+1]匹配（从而使得i和j能继续增加）。我们看一看当 i=j=5时的情况。 i = 1 2 3 4 5 6 7 8 9 ……
A = a b a b a b a a b a b …
B = a b a b a c b
j = 1 2 3 4 5 6 7 此时，A[6]<>B[6]。这表明，此时j不能等于5了，我们要把j改成比它小的值j'。j'可能是多少呢？仔细想一下，我们发现，j'必须要使得B[1..j]中的头j'个字母和末j'个字母完全相等（这样j变成了j'后才能继续保持i和j的性质）。这个j'当然要越大越好。在这里，B [1..5]="ababa"，头3个字母和末3个字母都是"aba"。而当新的j为3时，A[6]恰好和B[4]相等。于是，i变成了6，而j则变成了 4： i = 1 2 3 4 5 6 7 8 9 ……
A = a b a b a b a a b a b …
B = a b a b a c b
j = 1 2 3 4 5 6 7 从上面的这个例子，我们可以看到，新的j可以取多少与i无关，只与B串有关。我们完全可以预处理出这样一个数组P[j]，表示当匹配到B数组的第j个字母而第j+1个字母不能匹配了时，新的j最大是多少。P[j]应该是所有满足B[1..P[j]]=B[j-P[j]+1..j]的最大值。再后来，A[7]=B[5]，i和j又各增加1。这时，又出现了A[i+1]<>B[j+1]的情况： i = 1 2 3 4 5 6 7 8 9 ……
A = a b a b a b a a b a b …
B = a b a b a c b
j = 1 2 3 4 5 6 7 由于P[5]=3，因此新的j=3： i = 1 2 3 4 5 6 7 8 9 ……
A = a b a b a b a a b a b …
B = a b a b a c b
j = 1 2 3 4 5 6 7 这时，新的j=3仍然不能满足A[i+1]=B[j+1]，此时我们再次减小j值，将j再次更新为P[3]： i = 1 2 3 4 5 6 7 8 9 ……
A = a b a b a b a a b a b …
B = a b a b a c b
j = 1 2 3 4 5 6 7 现在，i还是7，j已经变成1了。而此时A[8]居然仍然不等于B[j+1]。这样，j必须减小到P[1]，即0： i = 1 2 3 4 5 6 7 8 9 ……
A = a b a b a b a a b a b …
B = a b a b a c b
j = 0 1 2 3 4 5 6 7 终于，A[8]=B[1]，i变为8，j为1。事实上，有可能j到了0仍然不能满足A[i+1]=B[j+1]（比如A[8]="d"时）。因此，准确的说法是，当j=0了时，我们增加i值但忽略j直到出现A[i]=B[1]为止。这个过程的代码很短（真的很短），我们在这里给出：

程序代码

j:=0;
for i:=1 to n do
begin
    while (j>0) and (B[j+1]<>A[i]) do j:=P[j];
    if B[j+1]=A[i] then j:=j+1;
    if j=m then
    begin
       writeln('Pattern occurs with shift ',i-m);
       j:=P[j];
    end;
end;

最后的j:=P[j]是为了让程序继续做下去，因为我们有可能找到多处匹配。这个程序或许比想像中的要简单，因为对于i值的不断增加，代码用的是for循环。因此，这个代码可以这样形象地理解：扫描字符串A，并更新可以匹配到B的什么位置。现在，我们还遗留了两个重要的问题：一，为什么这个程序是线性的；二，如何快速预处理P数组。为什么这个程序是O(n)的？其实，主要的争议在于，while循环使得执行次数出现了不确定因素。我们将用到时间复杂度的摊还分析中的主要策略，简单地说就是通过观察某一个变量或函数值的变化来对零散的、杂乱的、不规则的执行次数进行累计。KMP的时间复杂度分析可谓摊还分析的典型。我们从上述程序的j 值入手。每一次执行while循环都会使j减小（但不能减成负的），而另外的改变j值的地方只有第五行。每次执行了这一行，j都只能加1；因此，整个过程中j最多加了n个1。于是，j最多只有n次减小的机会（j值减小的次数当然不能超过n，因为j永远是非负整数）。这告诉我们，while循环总共最多执行了n次。按照摊还分析的说法，平摊到每次for循环中后，一次for循环的复杂度为O(1)。整个过程显然是O(n)的。这样的分析对于后面P数组预处理的过程同样有效，同样可以得到预处理过程的复杂度为O(m)。预处理不需要按照P的定义写成O(m^2)甚至O(m^3)的。我们可以通过P[1],P[2],...,P[j-1]的值来获得P[j]的值。对于刚才的B="ababacb"，假如我们已经求出了P[1],P[2],P[3]和P[4]，看看我们应该怎么求出P[5]和P[6]。P[4]=2，那么P [5]显然等于P[4]+1，因为由P[4]可以知道，B[1,2]已经和B[3,4]相等了，现在又有B[3]=B[5]，所以P[5]可以由P[4] 后面加一个字符得到。P[6]也等于P[5]+1吗？显然不是，因为B[ P[5]+1 ]<>B[6]。那么，我们要考虑"退一步"了。我们考虑P[6]是否有可能由P[5]的情况所包含的子串得到，即是否P[6]=P[ P[5] ]+1。这里想不通的话可以仔细看一下： 1 2 3 4 5 6 7
B = a b a b a c b
P = 0 0 1 2 3 ? P[5]=3是因为B[1..3]和B[3..5]都是"aba"；而P[3]=1则告诉我们，B[1]和B[5]都是"a"。既然P[6]不能由P [5]得到，或许可以由P[3]得到（如果B[2]恰好和B[6]相等的话，P[6]就等于P[3]+1了）。显然，P[6]也不能通过P[3]得到，因为B[2]<>B[6]。事实上，这样一直推到P[1]也不行，最后，我们得到，P[6]=0。怎么这个预处理过程跟前面的KMP主程序这么像呢？其实，KMP的预处理本身就是一个B串"自我匹配"的过程。它的代码和上面的代码神似：

程序代码

P[1]:=0;
j:=0;
for i:=2 to m do
begin
    while (j>0) and (B[j+1]<>B[i]) do j:=P[j];
    if B[j+1]=B[i] then j:=j+1;
    P[i]:=j;
end;

最后补充一点：由于KMP算法只预处理B串，因此这种算法很适合这样的问题：给定一个B串和一群不同的A串，问B是哪些A串的子串。串匹配是一个很有研究价值的问题。事实上，我们还有后缀树，自动机等很多方法，这些算法都巧妙地运用了预处理，从而可以在线性的时间里解决字符串的匹配。我们以后来说。

[ 转载: 原文by Matrix 67 ]

6 December 2007

Erik Demaine: If Only Your Professor Were This Cool

by Monica Byrne 2005 comments: 2

(Originally published in Atomica magazine.)

Erik Demaine loves burnt caramel ice cream. He was born on the last day of February, making him a Pisces. He wears a size 13 in men's platform heels.

Also, when he was 20 years old, he went to MIT - not as a student, but as the youngest professor ever hired by the renowned university.

Erik blends in well with MIT's unique aesthetic. Now 24-years-old, he stands tall at 6'2, with a sand-blond beard and a ponytail of fuzzy hair reminiscent of a young Robert Plant. He relaxes at his desk in jeans, hiking books and a t-shirt. "They're sort of universal," he says in a soft, measured voice, explaining his fashion sense. "I can change my expression by changing my t-shirt. Every one I have has some sort of story." Today, he is wearing a t-shirt with a picture of a man juggling axes. He, himself, is an intermediate juggler.

Surprised? Despite racking up over a hundred papers with a Christmas list of collaborators, garnering a $500,000 MacArthur Fellowship and earning the adoration of his students, Erik is arrestingly down to earth.

"You want props? I have props!" He enthusiastically volunteers to help the photographer, going to shelves crowded with ivory shapes of pleated curves and blown vases of vermilion glass. Bright-blue bowls and foam-glass paperweights on the windowsill catch the sunlight reflected off a canary-yellow wing of MIT's Stata Center, the architectural marvel where his office is housed. He holds up a gigantic paper star, a smaller version of which he had made for his mother?s Christmas tree one year, and grins for the camera.

Every object in his office has a history. Puzzles of wood and metal share space with paper sculptures resembling the Sydney Opera House. Some are gifts from master origami artists. Other pieces come from the glass-blowing workshop of his father, an artisan and frequent collaborator.

"My father has led many different lives," he says, professing his admiration. Erik's parents divorced when he was young. He and his father left Halifax, Nova Scotia, and spent the next six years traveling throughout the United States. "Every place made an impression on me," he says. "Miami Beach, Providence, Chicago, and Traverse City - the Cherry Capital of the World!?

When Erik was growing up, his father worked primarily as an artist. Wherever they moved, his father would sell art at crafts shows. In a Miami Beach apartment complex, Erik basked in a rich community of kids his own age with whom he'd play whenever they got out of school. Describing formal school as "just an excuse to meet kids and hang out with them," Erik was home-schooled by his father, who taught him an hour a day from home-school instruction manuals. His longest stint in formal schooling was a month in Miami Beach, where he stayed only because he developed a crush on a cute girl in his class. "Eventually it became clear that she wasn't interested in me, and so I left. Although we did get to dance once, and that was nice. She showed me how."

Most of his young life, however, Erik was free to pursue his own interests. He wrote his first computer program at age seven. It was a text-based CHOOSE YOUR OWN ADVENTURE-style of game, set in his apartment complex. When his ambitions began to outpace his knowledge, his father suggested enrolling in math classes at Dalhousie University, and attended class right alongside him. Erik was twelve years old. "[It was] nothing particularly unusual, except that I was short for the first year. My fellow students were great and treated me like anyone else." But he shies away from the moniker "genius," a term most journalists jump to use. "I didn't show any sign of being particularly smart or anything, [except that I had] an unusually long attention span."

This is unusual in the age of short attention spans, which does not exclude people like me, who have the attention span of a hummingbird. Picking up a rippled shape like a Dali sombrero, I asked, "Is this the shape that might not exist?" referring to a previous interview.

"We're not sure it does, no."

"Well, shouldn't it exist, if I'm holding it?"

"Oh, that's just in the real world! In the mathematical world, we don't know." That is, the mathematical vocabulary for describing such a shape has not yet been called into being - and Erik may be just the one to do it. "I'm a mathematician, so most of the time I don't live in the real world. Therefore I'm not bound by things like physics! It's a great place to be because I can do whatever I want."

Mathematics is as much an act of creativity as an act of science. His field, which he helped found, is called computational origami. In other words, he develops the mathematics necessary to describe paper-folding. "Origami offers a wealth of intriguing geometry problems which have been a lot of fun to solve," he explains. Far from being an idle pastime, origami is key to understanding modern problems. For example, proteins constitute nearly everything in a living being. They both make up a cell's structure and carry out its work. Like a pipe cleaner bends, proteins begin as strings that assume intricate conformations that dictate their function. In other words, proteins are biochemical origami.

If a protein does not fold correctly, it cannot do its job; or worse, it does harm to the cell. "If we could solve these problems, we could design drugs that target particular viruses - and maybe cure diseases like Mad Cow that come from proteins misfolding."

Besides being a buoyant optimist, Erik is also a stalwart rationalist. "Ultimately, within this universe I can believe that [there's nothing science can't prove]. The closest thing to a God I can come is someone who creates the initial conditions for the universe and sets the rules. Conservation of energy, quantum physics - and then "Go!" The universe is on its own course. From [its] inception on to its destruction, it's a computer."

Rationalism, too, has its own built-in sense of awe. "I know things that no one can prove," says Erik, with a tone of reverence. Specifically, the Gödel Incompleteness Theorem "proves that there are things you can't prove - yet are true." Put another way, the Gödel Incompleteness Theorem states that, in every mathematical system, there are known truths that cannot be derived from the precepts of that system.

The beauty and joy of mathematics are so endemic to Erik's daily life that they inform how he behaves personally. An algorithm, for instance, is "like a cooking recipe, only for solving a problem." They're also useful to navigate personal affairs. "Logic is the obvious thing for understanding a problem and all the possible solutions, as opposed to being more emotional about the issue. I'?s very pleasing to be in an objective process. [When you] prove something, it's not like you can get upset when it's true!" Even though this approach serves him well, he admits sheepishly that it's "very geeky."

Increasingly, however, geek is chic in this era of globalism and technology. Like popular scientists Noam Chomsky and Stephen Pinker, Erik has also considered activism. He feels particularly strongly about banishing archaic copyright laws in the Information Age. "The whole notion of having information protected doesn't make sense. It's illegal to decode a DVD even though it's encrypted in a stupid way. These days, the purpose of copyright is to protect companies. But, fundamentally, information wants to be free."

Similarly unbounded, Erik isn't afraid of diving into new territory. He juggles, has taken hip hop dance classes ("very exhausting"), and dressed up as a Bearded Lady for an Improv Boston show, where he is a regular. "That was an accomplishment by itself. I got the high heels, the dress, the garter belts, the stockings - it was a real pain. I didn't have quite the right body type. [The dress] was lavender one-piece. It was pretty tight against my fake breasts."

Erik relishes defying what?s popular. As a child, he manifested this same tendency as stubbornness: "I used to not eat chocolate because it was too popular - therefore it couldn't be good!" Though he likes chocolate now and, also, popular math, he is particularly attracted to the most intractable problems. His latest venture took him into an esoteric subfield of graph theory, otherwise known as what Matt Damon was scrawling on the chalkboard in GOOD WILL HUNTING. In this subfield, about 20 papers have been published in the last 20 years, which, in scientific time, is a snail's pace. But Erik is eager to take it on. "You can find really interesting innovations that way," he says.

Constant collaboration is another way Erik innovates. On his right hand are sweat-blurred scrawls from ballpoint pens, mind-triggers known only to him: "Tom. Italy. Jenna. Summer. GREEN." And, faded from two days of showers, "Consistent histories proposal."

"It's one model of time travel, an alternative to the parallel worlds [hypothesis]," he explains. Recently, Erik spoke at the first (and, theoretically, only) Time Travelers' Convention, held on a cold, rainy night at MIT. The community was encouraged to leave notes on acid-free paper in obscure books, giving the exact time and geographic coordinates of the Convention, so that future humans could travel back to it in 2005. An open-spaced pen was roped off so that the travelers would not materialize into the trees.

Unfortunately, no one (that we know of) showed up, but that did nothing to dampen Erik's imagination. Explaining the parallel worlds (or "multiverse") hypothesis, which allows the solution of time travel paradoxes, he says, "The universe is flipping coins, and every time it flips a coin, it actually comes out both ways, and the universe branches. It happens all the time."

If this is true, untold millions of universes branch out of Erik?s office every day. As an assistant professor, his time is filled with meetings with graduate students, collaborators, colleagues, advisees, reporters, friends; classes taught and seminars attended; problems posed and problems solved; writing and reading and revising papers that will eventually be published in peer-reviewed journals. "One thing I try to practice doing is context switch from doing one thing to doing something completely different in two seconds. That's what I aspire to."

It sounds like the life of a workaholic. On the contrary, Erik makes no distinction between work and play. His work is his life's play, and he wouldn't have it any other way. "The thing that drives me is having fun. Right now I enjoy being a professor and I will be, probably, for several more years. [But] my goal in life is to keep having fun - that can go anywhere. I'll never retire."

In the background of his office is a stack of emergency food. Instant noodle bowls are piled next to a monstrous bag of beef jerky. "Whenever I eat it, I have this image of being in an adventure," he explained, smiling. For the average visitor, though, just a simple conversation feels like an adventure. Erik's territory is the infinite space of the mind, and he's only beginning to explore.

算法导论的 Erik Demaine 老师 - 原来是天才少年

Prodigy prof skipped school until he started college at 12

February 26, 2003

The following is an edited version of an article published in the Jan. 18 issue of New Scientist (vol. 177, issue 2378, page 40--reprinted with permission). The interview was conducted by Steve Nadis, a former Knight Science Journalism Fellow at MIT. The original interview is available online.

When he was 12, Erik Demaine talked himself into Dalhousie University in his home town of Halifax, Nova Scotia, despite having no grades or academic record to speak of. Eight years and a Ph.D. later, he became MIT's youngest professor in the fall of 2001. He specializes in computational origami--the geometry of paper folding.

Q. You left school at the age of seven and spent the next five years on the road with your father. Why?

A. Mainly because it seemed like a fun thing to do. My dad, Martin, was a craftsman, which made it easy for him to travel and sell his stuff at craft fairs throughout the U.S. It was a very free-form existence. Our movements weren't guided by anything more specific than "that seems like an interesting place to go."

Q. What happened to your formal education during those years of wandering?

A. My dad taught me from home-school manuals we got from an agency. When I was nine, it became more efficient for me to teach myself from the same materials. That approach worked well for everything but spelling, which is hard to test yourself on. But we figured out a system for that, too.

Q. Were you ever curious about what went on inside the classroom?

A. I checked out normal schools from time to time to make sure I wasn't missing anything. My longest stint was a month in a Miami school because I was intrigued by a cute girl. But I left once I realised she had no interest in me. The main thing I learned was how much time is wasted in school. When you take away lunch, recess and other breaks, the nine-to-three day reduces to about one hour of real instruction. Home schooling is much more efficient.

Q. When did you become interested in mathematics?

A. It started from playing video games when I was quite young. I asked my dad how people wrote those games, and he said you first have to learn how to write a computer program. He got hold of some books on programming so he could teach me, and soon I was reading the books on my own. After a year or so of that, he said, "If you want to be good at computers, you have to be good at mathematics." So I said, "OK, let's learn some mathematics." I started with a high school algebra text, and things took off from there.

Q. Do you feel any sort of age gap at MIT, being far younger than both your faculty colleagues and many of your students?

A. That's becoming less of an issue now that I can go to bars legally, but age has never really been important in my life. Some people who accomplished a lot when they were young have stressed their age as a way of making their achievements stand out even more. I try to downplay the age thing because eventually everyone gets older.

Q. What's your father up to these days?

A. He's a visiting scientist at MIT with an office in this lab. When MIT offered me a position, they offered him a position too, which was great. Sometimes we work together; other times we work separately. He has tried to keep up in mathematics, learning this stuff as I've been learning it, but as I've got deeper into the field our roles have changed somewhat.

Q. What was your first real accomplishment in mathematics?

A. Six years ago, when I began my Ph.D. work in computational geometry at the University of Waterloo in Ontario, my dad remembered "the paper cut problem" from an article written in the 1960s on paper folding and mathematics. The idea is to take a piece of paper, fold it any way and as many times as you want, and then make one straight cut and see what shapes you get. The question is, are all shapes possible? I worked on this problem for two years at Dalhousie with my dad and adviser Anna Lubiw. After experimenting for a while, we realised you could make all kinds of shapes, such as butterflies, swans, hearts or stars.

Q. What are you doing when you're not working on folding problems?

A. I have a separate project that involves a new approach to organizing data. My hope is to make web searches quicker and more efficient. Last week, a mathematician from Spain visited me and we looked at the classic problem in facility location: where, for instance, would you site 100 fast-food outlets to make them closest to the most people? I also work in combinatorial game theory, studying the complexity of computer games such as Tetris, which in fact is what got me into mathematics in the first place. My goal is to keep moving into new areas of mathematics and not be confined to a single branch.

Q. Does it seem weird to you to have a tenured job and so much stability in your life, given your nomadic past?

A. I guess I'm getting used to it. Stability seems like a good thing to me, and I can't see any downside. If you don't want it, you can always throw it away.

A version of this article appeared in MIT Tech Talk on February 26, 2003.

27 November 2007

Re: Power Law, 幂律定律

幂律分布研究简史

胡海波* 王林
（西安理工大学电子系西安 710048）

摘要 自然界与社会生活中存在各种各样性质迥异的幂律分布现象，因而对它们的研究具有广泛而深远的意义。近年来，借助于有效的物理和数学工具，及强大的计算机运算能力，科学家们对幂律分布的本质有了进一步深层次的理解。本文从统计物理学的角度，简要介绍了幂律分布的研究史以及最新的进展，并对它的形成机制及动力学影响作了一些言简意赅的阐述。

关键词 幂律分布，优先连接，自组织临界，HOT理论

A brief research history of power law distributions

HU Hai-Bo WANG Lin
(Department of Electronic Engineering, Xi'an University of Technology, Xi'an 710048, China)

Abstract: Various power law distribution phenomena with different characters are ubiquitous in nature and society, thus their research carries broad and far-reaching significance. In recent years, by effective physical and mathematical tools and powerful computational faculties, scientists have had a farther and substantial understanding of the essence of power law distributions. This paper introduces briefly the research history and current development of power law distributions from the perspective of statistical physics, and presents some concise and comprehensive expatiation on the mechanisms for generating them and their influence on certain dynamic characters.

Key words: power law distributions, preferential attachment, self-organized criticality (SOC), highly optimized tolerance (HOT)

------------------------------------------
* E-mail: sdhuzi@163.com
§ E-mail: wanglin@xaut.edu.cn
------------------------------------------

1 引言

　　自然界与社会生活中，许多科学家感兴趣的事件往往都有一个典型的规模，个体的尺度在这一特征尺度附近变化很小。比如说人的身高，中国成年男子的身高绝大多数都在平均值1.70米左右，当然地域不同，这一数值会有一定的变化，但无论怎样，我们从未在大街上见过身高低于10厘米的"小矮人"，或高于10米的 "巨人"。如果我们以身高为横坐标，以取得此身高的人数或概率为纵坐标，可绘出一条钟形分布曲线（如图1左图所示），这种曲线两边衰减地极快；类似这样以一个平均值就能表征出整个群体特性的分布，我们称之为泊松分布。另外一个我们要注意的，是最高的人与最矮的人的身高之比，根据吉尼斯世界纪录[1, 2]，世界上最高的人与最矮的人（均已去世）的身高分别是2.72米和0.57米，二者之比为4.8，这个数值并不是很大，我们将在下文中证实。

　　对于另一些分布，像国家GDP或个人收入的分布，情况就大不一样了，个体的尺度可以在很宽的范围内变化，这种波动往往可以跨越多个数量级。比如根据世界银行的统计[3]，最富有的国家――自然是美国――其2003年GDP高达10,881,609,000,000美元（一个天文数字），而数据显示同年 GDP最低的国家――西非岛国圣多美和普林西比――只有54,000,000美元，二者之比高达201511.3。个人收入分布亦是如此，想想世界首富比尔・盖茨那高达465亿美元的个人资产就清楚了。国家或城市人口的分布也会出现类似的情形，据世界银行的统计[4]，2003年人口最多的国家――中国 ――总人口数多达1,288,400,000，而数据显示同年人口最少的国家――西太平洋上的帕劳群岛――人口数仅为20,000（不及中国一个普通县城的人口数），二者之比有64420之多。以收入或人口数为横坐标，以不低于该收入值或人口数的个体数或概率为纵坐标，可绘出一条向右偏斜得很厉害，拖着长长"尾巴"的累积分布曲线（如图1右图所示），它与钟形的泊松分布曲线有显著的不同。这种"长尾"分布表明，绝大多数个体的尺度很小，而只有少数个体的尺度相当大，像国家人口，全世界有300多个国家和地区，只有11个国家的人口数超过一亿。

screen.width*0.5) this.width=screen.width*0.5;" alt="如果图片缩小请点击放大" border="0">
图1 泊松分布(左)与"长尾"分布(右)

2 幂律分布研究：上个世纪及以前

　　对"长尾"分布研究做出重要贡献的是Zipf和Pareto[5]，虽然他们并不是这种分布的最早发现者。

　　1932年，哈佛大学的语言学专家Zipf在研究英文单词出现的频率时，发现如果把单词出现的频率按由大到小的顺序排列，则每个单词出现的频率与它的名次的常数次幂存在简单的反比关系：P(r)～r^(-α)，这种分布就称为Zipf定律，它表明在英语单词中，只有极少数的词被经常使用，而绝大多数词很少被使用。实际上，包括汉语在内的许多国家的语言都有这种特点。物理世界在相当程度上是具有惰性的，动态过程总能找到能量消耗最少的途径，人类的语言经过千万年的演化，最终也具有了这种特性，词频的差异有助于使用较少的词汇表达尽可能多的语义，符合"最小努力原则"。分形几何学的创始人 Mandelbrot[6]对Zipf定律进行了修订,增加了几个参数，使其更符合实际的情形。

　　19世纪的意大利经济学家 Pareto研究了个人收入的统计分布，发现少数人的收入要远多于大多数人的收入，提出了著名的80/20法则，即20%的人口占据了80%的社会财富。个人收入X不小于某个特定值x的概率与x的常数次幂亦存在简单的反比关系：P[X≥k]～x^(-k)，上式即为Pareto定律。

　　 Zipf定律与Pareto定律都是简单的幂函数，我们称之为幂律分布；还有其它形式的幂律分布，像名次――规模分布、规模――概率分布，这四种形式在数学上是等价的[5, 7]，幂律分布的示意图如图1右图所示，其通式可写成y=c*x^(-r)，其中x，y是正的随机变量，c，r均为大于零的常数。这种分布的共性是绝大多数事件的规模很小，而只有少数事件的规模相当大。对上式两边取对数，可知lny与lnx满足线性关系，也即在双对数坐标下，幂律分布表现为一条斜率为幂指数的负数的直线，这一线性关系是判断给定的实例中随机变量是否满足幂律的依据。判断两个随机变量是否满足线性关系,可以求解两者之间的相关系数；利用一元线性回归模型和最小二乘法可得lny对lnx的经验回归直线方程，从而得到y与x之间的幂律关系式。图2显示的是图1右图在双对数坐标下的图形，由于某些因素的影响，图2前半部分的线性特性并不是很强，而在后半部分（对应于图1右图的尾部），则近乎为一直线，其斜率的负数就是幂指数。

screen.width*0.5) this.width=screen.width*0.5;" alt="如果图片缩小请点击放大" border="0">
图2 双对数坐标下一个幂律分布的示意图，直线表示对图1右图尾部的线性拟合

　　实际上，幂律分布[8]广泛存在于物理学、地球与行星科学、计算机科学、生物学、生态学、人口统计学与社会科学、经济与金融学等众多领域中，且表现形式多种多样。在自然界与日常生活中，包括地震规模大小的分布[9](古登堡-里希特定律)、月球表面上月坑直径的分布[10]、行星间碎片大小的分布 [11]、太阳耀斑强度的分布[12]、计算机文件大小的分布[13]、战争规模的分布[14]、人类语言中单词频率的分布[5]、大多数国家姓氏的分布 [15]、科学家撰写的论文数的分布[16]、论文被引用的次数的分布[17]、网页被点击次数的分布[18]、书籍及唱片的销售册数或张数的分布 [19, 20]、每类生物中物种数的分布[21]、甚至电影所获得的奥斯卡奖项数的分布[22]等，都是典型的幂律分布。

　　以网页被点击次数的分布为例[23]，尽管中国向七千九百万网民提供的网站接近六十万个，但只有为数不多的网站，才拥有网民一次访问难以穷尽的丰富内容，拥有接纳许多人同时访问的足够带宽，进而有条件演化成热门网站，拥有极高的点击率，像新浪、搜狐、网易等门户网站。

　　网页被点击次数的幂律分布其幂指数在0.60-1.03之间，而网站访问量的幂律分布其幂指数则接近1[24]。对于Pareto定律，在成熟市场中，金融资产收益率的幂律分布其幂指数约等于3[25]。特别需要指出的是，一些幂律分布的幂指数带有一定的普适性，如月球表面的月坑，直径大于r的月坑总数 N(r)与r满足幂律关系，其幂指数D≈2.0，这一指数不仅对月球的月坑有效，甚至对火星和金星的火山口也有效[11]；还有一个是行星间碎片大小的分布，其幂指数在2.0-2.1之间，这一区间不仅对陨石和小行星（如木星和火星轨道之间的小行星）这样的大碎片有效，而且对高速子弹打入岩石时所形成的小碎片大小的分布也有效[11]；英文单词出现频率所满足的Zipf定律，不仅对报纸、《圣经》有效，而且对狄更斯的小说，莎士比亚的戏剧等也有效，甚至对其它一些国家的语言也是有效的，且幂指数α均约等于1[26, 27]；情报学和科学学中有一个著名的公式，即洛特卡（Lotka）定律，它表明一定时期某一学科或主题内，撰写了x篇论文的作者数y(x)与x满足幂律关系，不管学科或主题如何变化，其幂指数均在1.2-3.7之间，且大致按基础自然科学、技术科学、社会科学与人文科学的顺序递增[28]。

　　幂律表现了一种很强的不平等性，对个人收入的分布来说这确实是一件很恐怖的事，但同时也说明了，单纯依据人均收入来衡量两个城市或国家的发展水平，并没有多大的实际意义，必须还要提供一个衡量收入分布不均程度的参数――基尼系数[29, 30]，才能增强比较的可靠性。

　　统计物理学家习惯于把服从幂律分布的现象称为无标度现象，即，系统中个体的尺度相差悬殊，缺乏一个优选的规模。可以说，凡有生命的地方，有进化、有竞争的地方都会出现不同程度的无标度现象。

3 幂律分布研究：当前

　　许多领域（像生物学、计算机科学）的进展都面临着要处理一些复杂系统问题[31]，自然界和社会中的系统的复杂性可归因于一个个交织的网络（像生态网、因特网）的复杂性，通过这些复杂网络，系统的各个组成部分相互之间发生着各种线性的、非线性的作用。复杂网络[32-35]的研究应运而生，它是近年来刚刚兴起的一个研究方向，隶属复杂性科学，教导我们从网络的观点来看待整个世界，甚至我们人类都可看成是复杂网络中的一个个小小的节点。钱学森[36]给出了复杂网络的一个较严格的定义：具有自组织、自相似、吸引子、小世界、无标度中部分或全部性质的网络称为复杂网络。目前，这个新领域已聚集了一大批杰出的物理学家、生物学家、计算机网络专家、数学家和社会学家。

　　从统计物理学来看，网络是一个包含了大量个体及个体之间相互作用的系统。近年来在对复杂网络的研究过程中，科学家们亦发现了众多的幂律分布，虽然这些网络在结构及功能上是如此的千变万化，相差迥异。复杂网络中节点的度值k*相对于它的概率P(k)满足幂律关系，且幂指数多在大于2小于3的范围内[31, 32]；这一现象是如此的普遍，如此地令人惊叹不已，以至于人们给具有这种性质的网络起了一个特别的名字――无标度网络[37]§。这里的无标度是指网络缺乏一个特征度值（或平均度值），即节点度值的波动范围相当大。

------------------------------------------
* 节点的度定义为与该节点相连接的节点的个数。
§ 可能地，Price[17] (Science, 1965)所研究的索引网络是第一个被发现的无标度网络。
------------------------------------------

　　无标度网络在自然界和现实生活中的实例举不胜举**，像Internet[38]、WWW[39, 40]这样的技术性网络，电子邮件网络[41]、电影演员合作网络[42]、引文关系网络[43]这样的社会性网络，甚至细胞代谢网络[44]、蛋白质调控网络[45]、食物链网络[46]等之类的生物网，都是典型的无标度网络。在过去的40多年里，科学家们一直想当然地认为现实中的网络都是随机的，随机图论[47]就是专门为了研究随机网络而发展起来的一门数学学科，但无标度特性的发现打破了这种构想。随机网络的度分布是泊松分布，度值比平均值高许多或低许多的节点，都十分罕见，是一种高度"民主"的网络，而无标度网络的度分布则是幂律分布，节点度值相差悬殊，往往可以跨越几个数量级，是一种极端"专制"的网络，二者之间有本质的区别。这两种网络的一个形象化的比较如图3[48]所示。

------------------------------------------
** 存在一些指数型度分布的复杂网络[37]，如高速公路网，电力网。
------------------------------------------

screen.width*0.5) this.width=screen.width*0.5;" alt="如果图片缩小请点击放大" border="0">
图3 具有相同节点数和边数的随机网络（左）和无标度网络（右）

　　度分布满足幂律的无标度网络还有一个奇特的性质――"小世界"特性[49]，虽然WWW中的页面数已超过80亿，但平均来说，在WWW上只需点击19次超链接，就可从一个网页到达任一其它页面。"小世界"现象在社会学上也称为"六度分离"，它来源于1967年，美国哈佛大学的社会心理学家Milgram 的一个实验[50-52]，这个实验证实，世界上任何两个人，不论他（她）是中国的藏民，非洲的难民，还是美国的政界高层，好莱坞的明星，甚至北极的爱斯基摩人，美洲的土著印第安人，都可通过熟人找熟人的方式建立联系，而两者之间的平均最少"中介"数是6，如此看来，整个地球确实是一个小小的世界。

　　图4[53]是Internet的拓扑图，它具有很强的自相似性，跟河流网之类的分形图非常类似。分形理论的创始人Mandelbrot[54]曾说过，"当你看到一个非整数指数关系，就应想到分形。不过你应当小心从事"。可以说，幂律分布与分形、非线性、复杂性密切相关，它支配了所有自然演化的具有自相似特性的无标度网络。无标度网络的度分布是一个非整数指数关系，这种网络的拓扑图呈现分形特征也在情理之中。近年来，物理工作者们日渐对无标度网络的拓扑结构产生了浓厚的兴趣，并构建了多种物理定义，从不同的角度研究了无标度网络的分形维问题[55-57]。

　　简单性一向是现代自然科学、特别是物理学的一条重要的指导原则[58]。许多科学家相信自然界的基本规律是简单的，爱因斯坦就是这种观点的突出代表者，他曾说过，"要使我们的理论尽可能得简单――但不是更简单。"从普适简单的幂律，我们似乎可以说，大自然是如此的复杂，而支配它的物理定律却又是如此的简洁优雅。

4 幂律分布的形成机制

　　如此广泛的幂律是怎样形成的呢？这是目前许多学者关注的焦点，毕竟一味地到处寻找幂律关系并没有多大的意义，而支配它形成的最根本的动力学原因才是最重要的。从现象到本质的探索一直是物理学的使命，十几年来，或者几十年来，为了解释幂律分布的形成原因，科学家们提出了几种机制，包括增长与优先连接 [42, 59]、自组织临界[60, 61]、HOT理论[62, 63]、渗流模型[8,64-66]及一些随机过程[7, 8, 67]等。

　　一些解释幂律形成原因的机制是相当复杂的，甚至动用了"临界现象理论"和"重正化群"[68, 69]等工具。其实，一些简单的代数方法――像"指数组合"[7, 8]、"变量替换"[70]――亦能产生幂律分布，比如，Miller[71]曾用"指数组合"的方法解释了英文单词频率的幂律分布，Reed和 Hughes[7]利用该机制，并结合随机过程，解释了城市人口分布、生物物种数分布等幂律分布。

screen.width*0.5) this.width=screen.width*0.5;" alt="如果图片缩小请点击放大" border="0">
图4 Internet在自治系统层次上的拓扑图

　　4.1 优先连接

　　Barabási与Albert针对复杂网络中普遍存在的幂律分布现象，提出了网络动态演化的BA模型[42, 59]，他们解释，成长性和优先连接性是无标度网络度分布呈现幂律的两个最根本的原因。所谓成长性是指网络节点数的增加，像Internet中自治系统或路由器的添加，以及WWW中网站或网页的增加等，优先连接性是指新加入的节点总是优先选择与度值较高的节点相连，比如，新网站总是优先选择人们经常访问的网站作为超链接。随着时间的演进，网络会逐渐呈现出一种"富者愈富，贫者愈贫"的现象。社会学家所说的"马太效应"[72]，《新约》圣经所说的"凡有的，还要加给他，叫他有余"，同优先连接也有某种相通之处。

　　"优先连接性"的思想并不是BA模型的原创，早在1925年，Yule [73]在解释每类植物物种数的分布满足幂律分布的原因时就已经提出了类似的思想，虽然当时研究的对象不是复杂网络。1955年，Simon[74]对优先连接性作了进一步深入的研究***，他对网络中可能存在的幂律不怎么感兴趣，但他列举了五种可以用他的理论解释的幂律分布：文献中单词频率的分布，科学家撰写的科技文献数量的分布，城市人口的分布，收入的分布及每类生物中物种数的分布。

------------------------------------------
*** 在Simon的工作之前，Champernowne[75]就提出了一个类似于"乘法过程"的数学模型，解释了个人收入分布的幂律现象。实际上，Simon的工作只是Champernowne模型的推广。
------------------------------------------

　　"优先连接"并不适用于所有出现幂律分布的情况，即便是对于某些无标度网络，用它解释幂律的成因也显得很不合理。以生态系统中的食物链为例，认为被捕食者最有可能被猎物广泛的杂食性捕食者吃掉，确实是一件很荒唐的事。还有像Internet、航空网等网络，流量或容量的限制可以在一定程度上抑制优先连接性，电影演员的合作网络中，节点（演员）的衰老或隐退也能起到类似的作用。

　　4.2 自组织临界

　　自组织临界理论[61]是一个影响深远的理论，在复杂系统的研究领域中,该模型曾一直被认为是产生幂律分布的动力学原因，幂律亦可作为自组织临界的证据。它认为，由大量相互作用的成分组成的系统会自然地向自组织临界态发展；当系统达到这种状态时，即使是很小的干扰事件也可能引起系统发生一系列灾变。布鲁克海文实验室的Bak、加州大学圣巴巴拉分校的汤超和佐治亚理工学院的Wiesenfeld等人用著名的"沙堆模型"[61, 76]形象地说明了自组织临界态的形成和特点（如图5[76]）：设想在一平台上缓缓地添加沙粒，一个沙堆逐渐形成。开始时，由于沙堆平矮，新添加的沙粒落下后不会滑得很远。但是，随着沙堆高度的增加，其坡度也不断增加，沙崩的规模也相应增大，但这些沙崩仍然是局部性的。到一定时候，沙堆的坡度会达到一个临界值，这时，新添加一粒沙子（代表来自外界的微小干扰）就可能引起小到一粒或数粒沙子，大到涉及整个沙堆表面所有沙粒的沙崩。这时的沙堆系统处于"自组织临界态",有趣的是，临界态时沙崩的大小与其出现的频率呈幂律关系。这里所谓的"自组织"是指该状态的形成主要是由系统内部各组成部分间的相互作用产生，而不是由任何外界因素控制或主导所致，这是一个减熵有序化的过程；"临界态"是指系统处于一种特殊的敏感状态，微小的局部变化可以不断被放大、进而扩延至整个系统。

screen.width*0.5) this.width=screen.width*0.5;" alt="如果图片缩小请点击放大" border="0">
图5 "沙堆模型"

　　幂律分布是自组织临界系统在混沌边缘，即从稳态过渡到混沌态的一个标志，利用它可以预测这类系统的相位及相变。自组织临界理论可以解释诸如火山爆发、山体滑坡、岩层形成、日辉耀斑、物种灭绝、交通阻塞、以及金融市场中的幂律分布现象。这种理论的启示是小事件和大事件可能有相同的起因,这为地震、恐龙灭绝、森林火灾等复杂大系统的突变提供了新的解释。以恐龙灭绝为例,古生物学家经过对化石的研究指出,这一重大事件不是经历了数万年或者几年,而是在20多天的突变中"一朝覆灭"的。恐龙的灭绝可以被看作是处于临界状态下的生态系统发生的一次"大雪崩"。

　　4.3 HOT理论

　　另一种解释幂律分布形成原因的重要理论是HOT[62, 63, 77]，由加州大学圣巴巴拉分校的Jean Carlson以及加州理工学院的John Doyle提出。他们宣称，对于由许多子系统连结成的复杂系统, 不管是自然演化还是人为设计的, 当该系统可以有效地容忍某些不确定因素时(具强健性)，将对其它未被考虑到的不确定因素变得更敏感。也就是说，强健性和敏感度具有相互递换的效果。这里的不确定因素包含系统内部的不确定因素以及外在环境的干扰。以生态系统为例，如果它可以容忍气温变化、湿度、养分等巨幅变化，那么这生态系统却可能无法容忍一些意料之外的小干扰，如基因突变、外来族群迁入、或新的病毒，这些干扰可能会造成生态环境的巨大改变。

　　当一复杂系统处于HOT状态时，该系统将满足幂律，也就是说，全局性的优化过程可导致幂律分布：具有特征尺度的输入经过一个全局性的系统"产量"优化过程后，可产生具有幂律分布特性的输出。全局性优化在生态系统、航空航天与汽车系统、林业系统、因特网、交通运输及电力系统中具有广泛的应用，HOT理论可以解释上述系统中出现的幂律分布现象，比如可以解释林业系统中火灾规模所呈现的幂律分布。

　　4.4 随机过程

　　一些随机过程也可以产生幂律分布："随机行走"模型可以解释物种寿命所呈现的幂律分布[78]；"Yule过程"[21, 73]是一个生成幂律的比较通用的机制，通过调节它的某些参数，可以产生幂指数范围相当宽广的幂律分布，并可与实际观测值相一致。

　　产生幂律分布的机制是相当多的，是否存在某个单一的、通用的理论可以解释所有的性质迥异的幂律分布呢？有一部分学者，特别是自组织临界理论的支持者，声称他们的理论可以，但大多数科学家认为[79]，幂律分布是许多不同的过程或作用导致的结果，这就像经典力学，牛顿的经典力学固然很伟大，但它仅适用于宏观低速的情形。

5 幂律分布的动力学影响

　　幂律分布的动力学影响主要是对复杂网络而言的。网络动力学性质的基本研究对象是动力学模型在不同网络上的性质与相应网络的度分布的联系，在一定程度上说，这是一种关于网络的结构与功能关系的研究。

　　幂律特性的度分布对无标度网络的动力学性质有着极其深刻的影响。以疾病或病毒在网络中的传播这一物理过程为例，以前的基于规则网络及随机网络的研究表明 [80-82],疾病的传染强度存在一个阈值，只有传染强度大于这个阈值时,疾病才能在网络中长期存在,否则感染人数会呈指数衰减。但对无标度网络上传染病模型的研究结果表明，不存在类似的阈值[83-86]，只要传染病发生，就将长时间存在下去，这一特性表明，要想在Internet这样的无标度网络上彻底消灭病毒，即使是已知的病毒，也是不可能的[37]。

　　另外，度分布的幂律特性对网络的容错性和抗攻击能力也有很大的影响，对网络的攻击分为随机攻击和选择性攻击两种类型[87]，分别称为网络的容错能力与抗攻击能力。研究表明[87, 88]，无标度网络具有很强的容错性，但是对基于节点度值的选择性攻击抗攻击能力相当差。比如对万维网或因特网中集散节点的攻击，有可能造成整个网络的瘫痪，对于某些微生物来说，它们体内度值很高的蛋白质通常掌握着细胞的生死（如图6[37]所示）。度分布满足泊松分布的随机网络，其容错性和抗攻击能力则是基本相当的[87]。可见，网络的结构稳定性是与网络的度分布特性紧密联系在一起的。

screen.width*0.5) this.width=screen.width*0.5;" alt="如果图片缩小请点击放大" border="0">
图6 酵母菌体内蛋白质的相互作用关系图

　　对于幂律分布对网络的其它动力学方面的影响，比如对网络上Ising模型[89, 90]、XY模型[91]、临界现象[92]及沙堆模型[93]等的影响，限于篇幅，本文不再赘述，有兴趣的读者可以参考相关文献。幂律分布对现实中无标度网络的动力学性质影响深刻，这在相当程度上改变了我们对原有物理世界的看法，并进一步显示了幂律分布的重要性。

6 结束语

　　幂律分布已有超过一百年的研究历史了，即使在现在，仍然是众多学科研究的热点。它那简洁优雅的形式，可以将许多似乎毫不相干的事物联系在一起，这种独特的魅力吸引了一大批杰出的物理学家、生物学家、天文学家、地质学家、数学家和社会学家，并不断有新的研究者加入到该领域。但即便如此，要真正从本质上把握驱动系统呈现幂律分布的物理过程与机制，仍然有许多试验或理论性的工作要做。另外，不同类型的幂律分布幂指数有很大的不同，究竟是什么原因导致了这种不同？这仍然是一个尚未完全解决的问题。不过，我们相信，不久的将来，在众多科学家的共同努力下，人类最终将根本性地破解幂律分布之谜，为物理世界的简洁之美再谱华章。

参考文献
[1] http://www.guinnessworldrecords.com/gwr5/content_pages/record.asp?recordid=48409, 2005
[2] http://www.guinnessworldrecords.com/content_pages/record_category_a.asp, 2005
[3] http://www.worldbank.org/data/databytopic/GDP.pdf, 2004
[4] http://www.worldbank.org/data/databytopic/POP.pdf, 2004
[5] http://www.hpl.hp.com/research/idl/papers/ranking/ranking.html, 2000
[6] 张济忠.分形.北京：清华大学出版社，1997. 348[ Zhang J Z. Fractal. Beijing: Tsinghua University Press, 1997. 348 (in Chinese) ]
[7] Reed W J, Hughes B D. Phys. Rev. E, 2002, 66: 067103
[8] Newman M E J. arXiv: cond-mat/0412004 v2
[9] Gutenberg B, Richter R F. Bulletin of the Seismological Society of America, 1944, 34:185
[10] Neukum G, Ivanov B A. Crater size distributions and impact probabilities on Earth from lunar, terrestrial planet, and asteroid cratering data. In: Gehrels T (ed.). Hazards Due to Comets and Asteroids. Tucson: University of Arizona Press, 1994. 359
[11] 张济忠.分形.北京：清华大学出版社，1997. 326[ Zhang J Z. Fractal. Beijing: Tsinghua University Press, 1997. 326 (in Chinese) ]
[12] Lu E T, Hamilton R J. Astrophysical Journal, 1991, 380: 89
[13] Crovella M, Bestavros A. IEEE/ACM Transactions on Networking, 1997, 5(6):835
[14] Roberts D C, Turcotte D L. Fractals, 1998, 6: 351
[15] Zanette D H, Manrubia S C. Physica A, 2001, 295: 1
[16] Lotka A J. J. Wash. Acad. Sci, 1926, 16: 317
[17] Price D J de S. Science, 1965, 149: 510
[18] Adamic L A, Huberman B A. Quarterly Journal of Electronic Commerce, 2000, 1: 5
[19] Cox R A K, Felton J M, Chung K C. Journal of Cultural Economics, 1995, 19: 333
[20] Kohli R, Sah R. Working paper, Harris School of Public Policy, University of Chicago, 2003, 04.01
[21] Willis J C, Yule G U. Nature, 1922, 109: 177
[22] http://www.collisiondetection.net/mt/archives/001136.html, 2005
[23] http://news.xinhuanet.com/newmedia/2005-03/17/content_2710396.htm , 2005
[24] Teslyuk A B, Krashakov S A, Shchur L N. arXiv: cs.NI/0404010
[25] 张宇，张建玮，王正行.物理，2004, 33(10): 734[ Zhang Y, Zhang J W, Wang Z X. Wuli(Physics), 2004, 33(10): 734 (in Chinese) ]
[26] http://staff.science.nus.edu.sg/~parwani/c1/node87.html, 2002
[27] Montemurro M A. arXiv:cond-mat/0104066 v2
[28] 张济忠.分形.北京：清华大学出版社，1997. 350[ Zhang J Z. Fractal. Beijing: Tsinghua University Press, 1997. 350 (in Chinese) ]
[29] Colander D C. Microeconomics 4th ed. Boston: McGraw-Hill, 2001. 428
[30] Hu H B, Wang L. Advances in Complex Systems, 2005, 8(1): 159
[31] Barabási A-L. Emergence of scaling in complex networks. In: Bornholdt S, Schuster H G (Eds.). Handbook of Graphs and Networks: From the Genome to the Internet. Berlin: Wiley-VCH, 2002. Chapter 3
[32] Albert R, Barabási A-L. Rev. Mod. Phys., 2002, 74: 47
[33] Newman M E J. SIAM Review, 2003, 45: 167
[34] Evans T S. arXiv: cond-mat/0405123
[35] 周涛，柏文洁，汪秉宏等.物理，2005, 34(1): 31[ Zhou T, Bai W J, Wang B H et al. Wuli(Physics), 2005, 34(1): 31 (in Chinese) ]
[36] http://news.qdu.edu.cn/news.aspx?newsid=1514, 2003
[37] Barabási A-L, Bonabeau E. Scientific American, 2003, 288: 50
[38] Faloutsos M, Faloutsos P, Faloutsos C. Computer Communications Review, 1999, 29: 251
[39] Adamic L A, Huberman B A. Science, 2000, 287: 2115
[40] Albert R, Jeong H, Barabási A-L. Nature, 1999, 401: 130
[41] Ebel H, Mielsch L-I, Bornholdt S. Phys. Rev. E, 2002, 66: 035103(R)
[42] Albert R, Barabási A-L. Science, 1999, 286: 509
[43] Redner S. Eur. Phys. J. B, 1998, 4: 131
[44] Jeong H, Tombor B, Albert R et al. Nature, 2000, 407: 651
[45] Jeong H, Mason S P, Barabási A-L et al. Nature, 2001, 411: 41
[46] Montoya J M, Solé R V. Santa Fe Institute Working Papers, 2000, 00-10-059
[47] Bollobás B. Random Graphs 2nd ed. 北京：世界图书出版公司北京公司，2003
[48] http://physicsweb.org/articles/world/14/7/9/1, 2001
[49] Watts D J, Strogatz S H. Nature, 1998, 393: 440
[50] Milgram S. Psychology Today, 1967, 2: 60
[51] Travers J, Milgram S. Sociometry, 1969, 32:425
[52] Buchanan M. New Scientist, 2004, 181(2430): 32
[53] http://www.nd.edu/~networks/gallery.htm , 2004
[54] 张济忠.分形.北京：清华大学出版社，1997. 300[ Zhang J Z. Fractal. Beijing: Tsinghua University Press, 1997. 300 (in Chinese) ]
[55] Rozenfeld A F, Cohen R, ben-Avraham D et al. Phys. Rev. Lett., 2002, 89: 218701
[56] Csányi G, Szendrői B. arXiv:cond-mat/0406070 v1
[57] Song C M, Havlin S, Makse H A. Nature, 2005, 433: 392
[58] 郝伯林.物理，2001，30(8): 466[ Hao B L. Wuli(Physics), 2001, 30(8): 466 (in Chinese) ]
[59] Barabási A-L, Albert R. Physica A, 1999, 272: 173
[60] Bak P, Tang C, Wiesenfeld K. Phys. Rev. Lett., 1987, 59: 381
[61] 帕⋅巴克.大自然如何工作.武汉：华中师范大学出版社，2001[ Bak P. How Nature Works. Wuhan: Central China Normal University Press, 2001(in Chinese) ]
[62] Carlson J M, Doyle J. Phys. Rev. E, 1999, 60: 1412
[63] Carlson J M, Doyle J. Phys. Rev. Lett., 2000, 84: 2529
[64] Broadbent S R, Hammersley J M. Proc. Cambridge Philos. Soc., 1957, 53: 629
[65] Hammersley J M. Proc. Cambridge Philos. Soc., 1957, 53: 642
[66] Grimmett G. Percolation 2nd ed. Berlin: Springer-Verlag, 1999
[67] Mitzenmacher M. Internet Mathematics, 2004, 1: 226
[68] Reynolds P J, Klein W, Stanley H E. J. Phys. C, 1977, 10: L167
[69] Wilson K G, Kogut J. Physics Reports, 1974, 12: 75
[70] Sornette D. Critical Phenomena in Natural Sciences. New York: Springer-Verlag, 2000, 288
[71] Miller G A. American Journal of Psychology, 1957, 70: 311
[72] Merton R K. Science, 1968, 159: 56
[73] Yule G U. Philos. Trans. R. Soc. London B, 1925, 213: 21
[74] Simon H A. Biometrika, 1955, 42: 425
[75] Champernowne D. Economic Journal, 1953, 63: 318
[76] 斯图亚特・考夫曼.科学新领域的探索.长沙：湖南科学技术出版社，2004, 236[ Kauffman S A. Investigations. Changsha: Hunan Science & Technology Press, 2004, 236(in Chinese) ]
[77] Sornette D. Critical Phenomena in Natural Sciences. New York: Springer-Verlag, 2000, 317
[78] Sneppen K, Bak P, Flyvbjerg H et al. Proc. Natl. Acad. Sci. USA, 1995, 92: 5209
[79] Newman M E J. Nature, 2000, 405: 412
[80] Anderson R M, May R M. Infectious Diseases of Humans. Oxford: Oxford University Press, 1992
[81] Hethcote H W. SIAM Review, 2000, 42: 599
[82] Leveille J. HP Labs Technical Reports, 2002, HPL-2002-287
[83] Pastor-Satorras R, Vespignani A. Phys. Rev. E, 2001, 63: 066117
[84] Pastor-Satorras R, Vespignani A. Phys. Rev. Lett., 2001, 86: 3200
[85] Lloyd A L, May R M. Science, 2001, 292: 1316
[86] Dorogovtsev S N, Mendes J F F. Adv. Phys., 2002, 51: 1079
[87] Albert R, Jeong H, Barabási A �L. Nature, 2000, 406: 378
[88] Holme P, Kim B J, Yoon C N et al. Phys. Rev. E, 2002, 65: 056109
[89] Forogovtsev S N, Goltsev A V, Mendes J F F. Phys. Rev. E, 2002, 66: 016104
[90] Herrero C P. Phys. Rev. E, 2002, 65: 066110
[91] Medevedyeva F, Holme P, Minnhagen P et al. Phys. Rev. E, 2003, 67: 036118
[92] Golsev A V, Forogovtsev S N, Mendes J F F. Phys. Rev. E, 2003, 67: 026123
[93] Zhou T, Wang B H. arXiv: cond-mat/0406575

Announcement: all rights reserved to this paper's authors: Haibo Hu & Lin Wang

Whale Box

29 December 2007

HTML escape character list / HTML 转义字符对照表

28 December 2007

Two photos, by Diana Walker

Steve Jobs Said 【转载】

21 December 2007

"The Seven Steps Toward a Thesis" - by Eduard Hovy

"The Seven Steps Toward a Thesis"

17 December 2007

Why Not C? What are O'Caml (caml.inria.fr) and Haskell (haskell.org)?

13 December 2007

A student from that lab

Experience Talk (2)

Experience Talk

问答录：MIT Media Lab

10 December 2007

KMP算法详解【转载】

6 December 2007

Erik Demaine: If Only Your Professor Were This Cool

算法导论的 Erik Demaine 老师 - 原来是天才少年

Prodigy prof skipped school until he started college at 12

27 November 2007

Re: Power Law, 幂律定律

Tintin's Links

Blog Archive

29 December 2007

28 December 2007

21 December 2007

"The Seven Steps Toward a Thesis"

17 December 2007

13 December 2007

10 December 2007

6 December 2007

Prodigy prof skipped school until he started college at 12

27 November 2007

Subscribe To

Tintin's Links

Blog Archive