Saturday, December 29, 2007

wikipedia: Paradigm 与 methodology

Paradigm: 中文翻译好像是"典范","范例"。
其实好像也不是很准确,应该是style的意思才对。
如我们平时接触的OOP,AOP,functional programming就是一种paradigm.是一种特定的编程风格,反映了程序员思考问题,对于程序运行的一种观点。
在wikipedia列出的一长串例子中,我所见过的有:
  • OOP,
  • AOP
  • COP(Component-oriented Programming),类似微软的OLE(object linking & embedding)
  • Imperative Programming(相对于declarative programming)
  • Logic Programming(如Prolog)
  • Literate Programming(传说中的文化式编程)
  • Pipeline programming(典型的UNIX风格)
  • Recursive programming(相对于iterative programming)
  • Structured programming
  • reflective programming(反射式编程,如java)

而methodology中文翻译应该是"方法学"
是解决具体实际问题时所采用的一种套路,风格。
是前人的经验所积累,总结出来的。
就是软件工程中介绍的一些开发模型。如:
  • RUP(Rational Unified Process)
  • XP(Extreme Programming)
  • Waterfall model


Friday, December 28, 2007

Workshop的意思

老是收到科大一堆关于xxx workshop的邮件。按照以往打游戏的经验,workshop貌似是制造武器的工厂.......
今天终于忍不住上wikipedia查了一趟,发觉还有这个意思:
A workshop is also a gathering or training session which may be several days in length. It emphasizes problem-solving, hands-on training, and requires the involvement of the participants. Often Symposium, a lecture or a meeting can become a workshop when it is accompanied by a practical demonstration.

BTW: Symposium 是 座谈会 的意思。

Tuesday, December 25, 2007

校内网开通rss导入功能

此文经由邮件发到我的blog中。
貌似校内网的服务器也不能突破GFW的封锁,因此使用了MSN的feed来导入,
能正确导入。
但是其功能"自动检测有无新的文章并提示导入"尚未经测试成功。
如果可以的话,今后就可以所有的博文都聚合到我的blog里面了。
再做个链接:
blog: http://iveney.blogspot.com
space: http://xiaoiveney.space.live.com

Tuesday, December 18, 2007

用ethereal等抓包要注意的一个事项

今天抓包帧时发觉抓下来的包不符合以太网帧的要求:没有Preambel和FCS(这里是CRC校验)
上wikipedia查了查才发觉是这么回事:
Frames are the format of data packets on the wire. Note that a frame viewed on the actual physical hardware would show Start Bits, sometimes called the Preamble, and the trailing Frame Check Sequence. These are required by all physical hardware and is seen in all four following frame types. They are not displayed by packet sniffing software because these bits are removed by the Ethernet adapter before being passed on to the network protocol stack software.

我太菜了,orz

--
Best wishes,
Yours, iveney
Department, of Computer Science,
Zhongshan University (Sun Yat-sen University),
Guangzhou, China

Monday, December 17, 2007

一个IP多个域名:用Apache建立虚拟主机

以下在内网中测试通过……

修改apache的conf(/etc/httpd/conf/httpd.conf)

1.修改ServerName为域名,如果没有则为IP。
比如我机子的IP是172.18.33.144
则修改为:
ServerName 172.18.33.144

2.添加NameVirtualHost项
NameVirtualHost 172.18.33.144
如果只有一个IP,也可以把IP域置为"*"

3.添加VirtualHost
首先添加一个全局的VirtualHost(这个Host可以直接通过访问IP访问到)
NameVirtualHost 172.18.33.144
<VirtualHost 172.18.33.144>
        ServerAdmin iveney@mymail.com
        DocumentRoot "/var/www/html"
        ServerName 172.18.33.144
</VirtualHost>

接着添加多个VirtualHost
<VirtualHost 172.18.33.144>
        ServerAdmin iveney@mymail.com
        DocumentRoot /mnt/E/Page
        ServerName www.iveneyPage.com
</VirtualHost>

<VirtualHost 172.18.33.144 >
        ServerAdmin iveney@mymail.com
        DocumentRoot /mnt/E/Page/Distributed
        ServerName www.iveneyDistributed.com
</VirtualHost>


最后测试,在/etc/hosts中添加域名解析项
172.18.33.144 www.iveneyPage.com
172.18.33.144 www.iveneyDistributed.com


然后重启apache,输入以上两个网址,成功.

Saturday, December 15, 2007

一些有用的资料

系统性地介绍整个计算领域的领域。(CS只是狭义的"计算/computing"的一个在教育机构里提供的一个专业方向,类似的还有软件工程,计算机工程,信息系统等)
本来想直接附件给你的,但是我网络实在太差,你有时间就下回来慢慢看吧。虽然是英文的,但是计算机的术语早点接触英语好些,不然将来又要再学一遍。

ACM Curricula Recommendations
http://www.acm.org/education/curricula.html

2005的overview report,ACM建议的Computing Curricular
http://www.acm.org/education/curric_vols/CC2005-March06Final.pdf

2001定下来的ACM IEEE-CS Computing Curricular的CS分卷
http://acm.org/education/curric_vols/cc2001.pdf

另外在这里有部分的中文翻译,以后可能会陆续推出。
http://godel.blog.sohu.com/

--
Best wishes,
Yours, iveney
Department, of Computer Science,
Zhongshan University (Sun Yat-sen University),
Guangzhou, China

Wednesday, December 12, 2007

关于foo与bar

今天在看google的distributed computing教程时再次发觉两个大家都应该很熟悉的字眼:foo与bar。
类似的字眼还有rhs,lhs,分别表示right hand side和left hand side。
顺便上wikipedia搜了搜foo/bar/foobar,发觉挺有来历的。

按照解释,foo的作用类似于一种元语义变量,在CS中广泛被使用于表示一个复杂系统中的任意的一个概念或部分(更多地被用于程序设计、伪代码中),如数据,变量,函数,命令等。
foo常常与bar,foobar连用。它们的作用相当于数学方程式中的x,y,没有具体意义。
在Eric. Raymond的The New Hacker's Dictionary(jargon file)一书中有描述。

foo的来历:
foo与bar放在一起是foobar,是从FUBAR[1]派生出来的。但是根据RFC3092[2]的描述,foo最早起源于20世纪30年代的卡通,"including The Daffy Doc and comic strips, especially Smokey Stover and Pogo. "。然后慢慢地被用于军事俚语。

事实上,在wikipedia上查foo与foobar会得到不同的结果,都提到了foobar不同的来源。foobar词条解释说,这个词可能是从以下几种途径来的:
1.从FUBAR派生
2.DEC公司的技术手册上大量使用得而传播
3.电子信号(这点没看懂)

anyway,它的来源已经没人能完全确定了。我们只要知道它的作用无非是类似与代数方程中的x,y就好了。

[1]FUBAR是军事中的俚语,表示Fucked Up Beyond All Recognition 或者 Fucked Up Beyond All Repair,翻译过来意思应该是"被*得老妈都不认得".......

[2]RFC3092:Etymology of "Foo": http://www.ietf.org/rfc/rfc3092.txt

--
Best wishes,
Yours, iveney
Department, of Computer Science,
Zhongshan University (Sun Yat-sen University),
Guangzhou, China

Thursday, December 6, 2007

不得不说的cc: Creative Common License

上网搜索文章,往往是能搜到一堆相同的结果,但是往往转载出处却是未知。
中国人多,人肉转载机也多。
Creative Common License势在必行了。

这篇文章写得不错:

大家来使用"创作共用"许可协议吧!

附上cc官网:
知识共享@中国大陆

另外一篇严肃的文章是:
"创作共用"协议挑战"版权所有"

Byzantine General Problem

今天偶然遇到一个好玩的问题:拜占庭将军问题。描述如下:
Two generals are on hills either side of a valley. They each have an army of 1000 soldiers. In the woods in the valley is an enemy army of 1500 men. If each general attacks alone, his army will lose. If they attack together, they will win. They wish to send messengers through the valley to coordinate when to attack. However, the messengers may get lost or caught in the woods (or brainwashed into delivering different messages). How can they devise a scheme by which they either attack with high probability, or not at all?

以下转两篇介绍的文章:
前进中的可信计算(Ⅵ):拜占庭将军问题
原作者为 闵应骅
转载如下:

一个可信的计算机系统必须容忍一个或多个部件的失效。失效的部件可能送出相互矛盾的信息给系统的其他部件。这正是目前网络安全要对付的情况,如银行交易安全、存款安全。美国2001/9/11遭 恐怖袭击之后,大家普遍认识到银行的异地备份非常重要。纽约的一家银行可以在东京、巴黎、苏黎世设置异地备份。当某些点受到攻击甚至破坏以后,可以保证账 目仍然不错,得以复原和恢复。从技术的角度讲,这是一个很困难的问题。因为被攻击的系统不但可能不作为,而且可能进行破坏。国家的安全就更不必说了。对付 这类故障的问题被抽象地表达为拜占庭(Byzantine)将军问题。

拜占(Byzantine)将军问题

拜占庭帝国就是515世 纪的东罗马帝国,拜占庭即现在土耳其的伊斯坦布尔。我们可以想象,拜占庭军队有许多分支,驻扎在敌人城外,每一分支由各自的将军指挥。将军们只能靠通讯员 进行通讯。在观察了敌人以后,忠诚的将军们必须制订一个统一的行动计划。然而,这些将军中有叛徒,他们不希望忠诚的将军们能达成一致,因而影响统一行动计 划的制订与传播。问题是:将军们必须有一个算法,使所有忠诚的将军们能够达成一致,而且少数几个叛徒不能使忠诚的将军们做出错误的计划。

解决拜占庭将军问题的算法必须保证:

A.所有忠诚的将军必须基于相同的行动计划做出决策。

    忠诚的将军按算法的要求行动,而叛徒则按他们自己的意志行动。算法要保证不管叛徒怎么做,条件A都能得到保证。忠诚的将军们不但要能达成一致,而且要同意一个合理的计划。这就要求条件B

B.少数叛徒不能使忠诚的将军做出错误的计划。

这一条是很难做到的,因为"错误的计划"很难形式地加以定义。

我们考虑将军们怎么达成一致。设有n个将军,v(i)表示第i个将军送出的信息。每个将军用相同的方法把v(1),…,v(n)按某一种逻辑方式组合起来,形成一个行动计划。要满足条件A,将军们就必须用同样的方法来组合这些信息。而条件B要求使用的方法是健壮的。考虑最简单的情况,如果决定只有进攻和撤退两种可能, v(t)就是将军认为选择那一种行动最好,而最后的决定则基于多数表决。少数叛徒只有在忠诚的将军们几乎随机地(每一种选择的概率都是1/2)做出决策时才能影响决策,但既然每一种选择的概率都是1/2,那就不管怎么决策都不能说是坏的。

如果把第i个将军的信息v(i)送给其他将军。由于条件A要求每一个忠诚的将军得到v(1),…,v(n)相同的值,而叛徒将军可以给不同的将军送不同的值。为了使条件A得到满足,下面两条必须成立。

1.每一个忠诚的将军得到v(1),…,v(n)相同的值。

这就意味着忠诚的将军并不一定使用第i个将军送来的信息作为v(i)。因为第i个将军可能是叛徒。但这又可能使忠诚的将军送来的信息也被修改,因为忠诚的将军并不知道第i个将军是忠诚的,还是叛徒。如果要满足条件B,这是不能允许的。例如,我们不能因为少数叛徒说"撤退",忠诚的将军说"进攻",而做出"撤退"的决定。因此,要求

2.对每一个 i,如果第i个将军是忠诚的,其他忠诚的将军必须以他送出的值作为 v(i).

我们可以重写条件1如下。

1' 对每一个 i,不论第i个将军是忠诚的,或是叛徒,任何两个忠诚的将军使用相同的值v(i).

条件1'2都只牵涉到第i个将军怎么送一个值v(i)给其他的将军。因此,我们可以用司令送命令给副官的方式叙述如下:

拜占庭将军问题:一个司令要送一个命令给他的n-1个副官,使得

IC1 。所有忠诚的副官遵守同一个命令。

IC2。假如司令是忠诚的,则每一个忠诚的副官遵守他送出的该命令。

条件IC1IC2称为交互一致性条件。注意,如果司令是忠诚的,IC1可以从IC2推出来。但是,司令并不一定是忠诚的。

这个问题比过去的容错更困难。因为过去的容错都是针对那样一些软硬件故障,其故障效果是固定的。而拜占庭故障却假定故障机是鲜活的,它可以做坏事。

拜占庭将军问题的可解性

1)叛徒数大于或等于1/3,拜占庭问题不可解

如果有三位将军,一位副官是叛徒,如图1所示。当司令发进攻命令时,副官2可能告诉副官1,他收到的是"撤退"的命令。这时副官1收到一个"进攻"的命令,一个"撤退"的命令,而无所适从。

如果司令是叛徒,如图2所示。他告诉副官1"进攻",告诉副官2"撤退"。当副官2告诉副官1,他收到"撤退"命令时,副官1由于收到了司令"进攻"的命令,而无法与副官2保持一致。

正由于上述原因,在三模冗余系统中,如果允许一机有拜占庭故障,即叛徒数等于1/3,因而,拜占庭问题不可解。也就是说,三模冗余对付不了拜占庭故障。三模冗余只能容故障-冻结(fail-frost)那类的故障,就是说,元件故障后,它就冻结在某一个状态不动了。对付这类故障,用三模冗余比较有效。

          

(2) 用口头信息,如果叛徒数少于1/3,拜占庭问题可解

注意,这里说"少于 1/3 "表明,要对付一个叛徒,至少要用四模冗余。在四模中有一个叛徒,叛徒数是少于1/3的。所谓口头信息,是指它满足三个条件: 传送正确, 接收者知道是谁发的。 沉 默(不发信息)可以被检测。拜占庭问题可解是指:所有忠诚的副官遵循同一命令。若司令是忠诚的,则所有忠诚副官遵循其命令。我们可以给出一个多项式复杂性 的算法来解这一问题。算法的中心思想很简单,就是司令把命令发给每一副官,各副官又将收到的司令的命令转告给其他副官,递归下去,最后用多数表决。如图3所示。如果司令是忠诚的,他送一个命令v给所有副官。若副官3是叛徒,当他转告给副官2时命令可能变成x。但副官2收到{v, v, x} ,多数表决以后仍为v,忠诚的副官可达成一致。如果司令是叛徒,如图4所示。他发给副官们的命令可能互不相同,为x, y, z。当副官们互相转告司令发来的信息时,他们会发现,他们收到的都是{x,y,z},因而也取得了一致。

   

3)用书写信息,如果至少有2/3的将军是忠诚的,拜占庭问题可解

所谓书写信息,是指带签名的信息,即可认证的信息。它是在口头信息的基础上,增加两个条件: 忠诚司令的签名不能伪造,内容修改可被检测。 任何人都可以识别司令的签名,叛徒可以伪造叛徒司令的签名。一种已经给出的算法是接收者收到信息后,签上自己的名字后再发给别人。由于书写信息的保密性,可以证明,用书写信息,如果至少有2/3的将军是忠诚的,拜占庭问题可解。

如图5所示。如果司令是叛徒,他送"进攻"命令给副官1,并带有他的签名0,送"撤退"命令给副官2 ,也带签名0。副官们转送时也带了签名。于是副官 1收到{"进攻":0,"撤退":0,2},说明司令发给自己的命令是"进攻",而发给副官2的命令是"撤退",司令对我们发出了不同的命令。对副官2也同样

                                    

拜占庭将军问题的形式描述

考虑网络N,包含n个处理器,或叫游戏者,记为1,2,…,n,设n4。每一个处理器是一个交互的、概率的多项式时间图灵机。设网络N是完全的以私人通道连接,即每对处理器皆可互相通信而不能被其他处理器读取。该网络是同步的,即有统一的时钟。在dd+1 个脉冲间送出的信息将在d+1个脉冲时收到。

游戏者i称为是好的,如果它遵循协议,即正确执行其程序,在适当的时间在适当的地点写入返回的值。i称为是坏的,如果它破坏了该协议。如果坏的游戏者被敌手选用和控制,则更一般的故障行为可能发生。敌手是一个算法,在一个网络中发作,腐化一定比例的游戏者。

定义:设A是一个概率算法,r为常数。A称为是一个r-敌手,如果A可以在任何n 游戏者的、运行任何协议 P的网络上发作,并且满足:

(1) A可以读取非私人通道上的任何通信链路。

(2) A可腐化任何t个游戏者。当A腐化i时,A可以读取 i的所有数据,并夺取i输出的执行写控制。

(3) 动态性: A可以在P的任何步骤上腐化游戏者。

(4) 急促性:A 读第d周期内通过非私人通道传送的信息。第d周期私人通道信息在第d周期送给坏游戏者。基于这些信息,A在第d周期腐化其他的游戏者(少于t个)。而且在第d周期把d周期信息送给新被腐化者。这一过程继续到腐化t个游戏者。在第 d+1个脉冲之前,A不需要选择在第d周期由坏游戏者送给好游戏者的信息。

(5) A 可以即时完成无限步的计算

有文章给出了拜占庭一致性算法,不要求亲信伙伴和预处理。给定私人通信链路,可望在常数时间内达成一致,如果同步网络故障机;异步网络,故障机。如果不能保证私人通信,可以用密码得到在容错和敌手有限计算能力的运行时间两方面最优的算法。在这种情况下,对异步网络也能容 n/3个故障。

可信计算中的拜占庭将军问题

可 信计算中必须考虑人为的故障,特别是人为恶意的攻击。这是保证计算安全性的基本出发点,在今天的网络环境下有非常重要的现实意义。拜占庭将军问题不过是保 持并行计算中数据一致性问题的一个抽象表达。一种抽象表达往往能把本质问题从繁琐的工程实现中提取出来,对于基础研究极其重要。工程师们常常被繁琐的工程 任务所左右,在保证安全的要求下要考虑的问题非常多,而忽略了提纲挈领的功夫。

在可信计算领域,过去考虑的故障-冻结模式,假定部件故障以后就"死"去了,不再工作了。现在我们必须考虑故障 - 活动模式,即部件故障以后,它可能仍然活动,甚至进行系统所有者所不希望它做的事情。这正是电子对抗中要着力研究的问题。

并 行计算中有两个基本问题:一个是控制的同步性;一个是数据的一致性。不论是并行的处理器,还是并行的线程,总需要保持某种程度上的同步,以期达到各个计算 部件之间的协同与合作。尽管这种同步可以是紧耦合,也可以是松散的耦合。另一方面,各计算部件之间的数据一致性也至关重要。例如银行系统在为用户存取款服 务时,人名的查找必须和存取款数量相对应,否则就错了。而这两件事可能由不同的计算部件或不同的时刻完成。而这种一致性常常能被故障,特别是恶意攻击所破 坏。敌人的攻击也常常是利用这一点。拜占庭将军问题只把数据简化为二值的01。当然,多版本的一致性不单是"进攻"和"撤退"这样简单的信息,但原理是一样的。

为了保持多版本的一致性,系统需要一定的时间。在这段时间内,系统还没来得及达成一致,系统可能有可攻击的脆弱之处。这段时间表现为故障潜伏期,即敌人的攻击不一定马上生效,系统在某一时机来到时就可能做出错误的响应。

解 拜占庭将军问题的算法给我们提供数据一致性的思路和算法。而在该算法中就有各位将军的同步问题。这些问题都为计算可信性的提高以启发。要解决拜占庭将军问 题需要四模冗余,硬件开销是很大的。所以,现在银行的异地备份并不都是四模冗余。这就看你的系统要求有多高的安全性,相对于那些投资,孰轻孰重。

从拜占庭将军问题解法可以看出,签名和认证对保证数据安全有节省硬件的效果。这些技术将在后文详细介绍。


关于"拜占庭将军算法"byzantine generals problem 

一。拜占庭将军算法的背景:

对 于系统坏掉的风险,可以这样假设:我们的操作员可能会误操作、可能会被贿赂或背叛,系统本身可能就有木马程序,系统可能会被黑客或病毒占领,我们自己开发 的系统可能有漏洞,我们的开发人员可能会留下后门,这些都可以导致系统坏掉。因此,在这些假设在变成可能的残酷现实中,生存技术是应真正被采用的一种信息 安全技术。   入侵容忍体系就是生存技术中的核心。如果我们的网络和系统学会生存,那么也就是建立起一个完善的入侵容忍体系。   入侵容忍的技术在这样的假设空间中实现它的价值:个人的公开行为在一定的概率下是可预知的,系统在一定的概率下能够正确完成基本的功能。一定的概率并 不是指全部,所以,可以允许有错误,因此,入侵容忍还有对纠错理论的联想:即利用纠错码可以在一个错误百出、但有信道容量的信道中准确无误地传输数据,网 络系统就这样在错误中"生存"下来的,这就是我们说的入侵容忍体系,它的生存技术有两种实现方式:一是攻击响应的入侵容忍方法,它不需要重新设计系统,可 通过高效的检测系统发现异常,利用资源配置系统调整系统资源,并对对错误进行修补(修补系统);二是攻击遮蔽的入侵容忍方法,它需要重新设计整个系统,并 通过冗余、容错技术,门槛密码学技术及"拜占庭"技术来实现。------------------------------------------- ----

二。算法介绍: "拜占庭"技术,起源于拜占廷将军问题,这是入侵容忍体系的一个基本理论问题。   在1982年被提出的"拜占廷将军问题"在今天被许多学者看好,然而在商业上还没有体现其价值。特别是中国的产业界把它放在了一个被遗忘的角落。

描述如下:  

几个师包围着敌人的一座城市。每一个师都由它自己的司令统帅,司令之间只能通过报信者互相通信。他们必须统一行动 。

某一位或几位司令可能是叛徒,企图破坏忠诚的司令们的统一行动 。

司令们必须有一个算法,使所有忠诚的司令能够达成一致,而且少数几个叛徒不能使忠诚的司令们做出错误的计划,即判国的将军虽然可以传递了虚假消息,也不会影响爱国的将军得到正确的决策。   

拜占廷将军问题就是要让爱国的将军达成一致,而不是找叛国的将军。

我 们的入侵容忍体系就是这样,只要在众多服务器上得到的正确的计算结果,,那么我们就可以相信这个数据,而不需要去寻找到底谁是间谍。如果要容忍一个捣乱的 服务器,在数量上究竟会需要几个服务器?"拜占廷将军"问题可以为我们解答这个问题:在进行混乱真实消息的传播中,两个将军中一个判国,另一个肯定打败 仗,三个将军中如果有一个判国,则判国的将军一定有办法让两个爱国的将军不能达成一致,若再增加一个将军,既4个将军中如果只有一个判国,在不知道谁是判 国者的情况下,存在一种算法使将军们达成一致,实际上就是三个爱国的将军能够达成一致,而不管判国的将军如何捣乱。既4个将军的团体能够容忍1个叛国将 军。同样我们知道,当有t个判国者在捣乱而又无法找出他们的时候,存在一种算法或称做弹性协议,通过这种协议,能够保证爱国的将军达成一致。如果我们把能 够容忍t个叛国者的协议叫t弹性协议,学者证明了,不存在3t个将军下的t弹性协议而一定存在3t+1或以上将军下的t弹性协议。就是说要有3t+1个或 以上将军才能保证爱国的将军能够达成一致。既要想容忍t个判国者,必须保证总的将军的个数大于3t。   这样看来,"拜占廷将军"问题应用于信息安全就是入侵容忍体系的重要技术基础之一。以上讲述的仅仅是"拜占廷将军"问题中简化描述,加之以叙述的形 式,就是一个描述性的推理,实际上"拜占廷将军"问题程序计算的方法是很复杂的。   据荆老师的介绍,作为入侵容忍体系的理论问题,它可以应用在现实中。实验室开发的CA入侵容忍资料库系统就是应用的案例。当用户查找证书的时候,如何 保证得到的是最新的证书而不是过期的证书呢?如果一个服务器保留已经作废的证书欺骗你会如何呢。利用拜占廷法定数目团体系统,实验室很好地解决了这个问 题。即使 t个服务器捣乱,输出旧的证书,系统利用拜占廷协议,保证用户一定能够得到最新的证书。   由此看来,入侵容忍技术作为网络生存的重要技术,是保证网络和系统安全的一个新的概念和思路。网络的等级保护不仅仅是空间的,也应该是逻辑上的和技术 上的。深层防御就是在不同的地方,用不同的方式,建立多条防线,保护关键网络,入侵容忍技术在这个方面就有这不俗的表现。   

最后对于如何更好的开发和利用生存技术、如何建立完善入侵容忍体系的问题,荆老师神情急切,他说,这应该是当前中国信息安全最需要的。-----------------------------------------------

英 文解释:这个问题是在1982年由Lamport, Shostak, Pease提出,后少人问津。为了利于对"拜占廷将军"问题原意的理解和避免曲解,把英文解释奉上: Byzantine General Problem ——The problem of reaching a consensus among distributed units if some of them give misleading answers. The original problem concerns generals plotting a coup. Some generals lie about whether they will support a particular plan and what other generals told them. What percentage of liars can a decision making algorithm tolerate and still correctly determine a consensus?

三。具体分析:

1。叛徒数大于或等于1/3,拜占庭问题不可解。

情况一:A,B,C三个司令,C是叛徒。A发消息给B,C"进攻",C发消息给B"撤退"(因为是叛徒)。B收到两个矛盾的命令,无法作出决策。

情况二:A,B,C三个司令,A是叛徒。A发消息给B"进攻",发消息给C"撤退"(因为是叛徒)。B。C收到不同的命令。

2.用口头信息,叛徒数少于1/3,拜占庭问题可解.

口头信息三条件
      传送正确
      接收者知道是谁发的
      沉默(不发信息)可被检测
什么叫可解?
     IC1:所有忠诚副官(B.C,指消息接受者)遵循同一命令。
     IC2:若司令(A,消息)是忠诚的,所有忠诚副官遵循其命令

可 以证明,多项式复杂性算法OM(m)可以解决拜占庭问题(L Lamport, R Shostak, and M Pease. The Byzantine generals problem. ACM Transactions on Programming Languages and Systems, 1982, 4(3))

如果记容忍t 个叛国者的协议叫t弹性协议(即,在t弹性协议存在的情况下,可以胜利),则:

Ø     当n=3 时,不存在1弹性协议
Ø     当n>=1,不存在 t>=n/3t弹性协议
n如果记容忍 t个叛国者的协议叫t弹性协议,则:
Ø    当n=3 时,不存在1弹性协议
Ø     当n>=1,不存在 t>=n/3t弹性协议
    当n>=1,不存在 t>=n/3t弹性协议
------------------------------------
OM(m):m个叛徒
OM(0) :发送者将其命令送给每个接收者
           每个接受者使用这个值,如果没有收到就认为是"退"
 

n OM(m),m>0

Ø

Ø

               发送者发送他的值给每个接收者
               发送者发送他的值给每个接收者

        如果第i 个接收者获得的值是vi 接收者i执行算法OM(m-1) 发送vin-2 个其他的接收者

          i个接收者会收到从不同 n-1人发来的n-1个值, 取多数认同的值就可以

n OM(m),m>0

Ø

Ø

               发送者发送他的值给每个接收者                发送者发送他的值给每个接收者

        如果第i 个接收者获得的值是vi 接收者i执行算法OM(m-1) 发送vin-2 个其他的接收者

          i个接收者会收到从不同 n-1人发来的n-1个值, 取多数认同的值就可以

3。用书写信息,至少两个忠诚,拜占庭问题可解
在口头信息的基础上, 书写信息又增加了两个条件
     忠诚司令的签名不能伪造,内容修改可检测
     任何人都可以识别司令的签名, 叛徒可以伪造叛徒司令的签名
SM(m)算法
    接收者信息收到后,签上自己的名字,再送给别人
    用书写信息, 只要有两个忠诚的司令, 拜占庭问题就可解

--------

可以证明,算法SM(m)可以解决m个叛徒的拜占庭问题。

SM(1):如A是叛徒。A给B发"进攻",给C发"撤退"命令(都被A签名)。B比较从C发来的命令("撤退",该命令被C签名了)知A是叛徒。C比较从B发来的命令("进攻",该命令由B签名),知A是叛徒。

情况2:B是叛徒。A给B,C发"进攻"命令

四,来自原作者的相关翻译

http://delivery.acm.org/10.1145/360000/357176/p382-lamport.pdf?key1=357176&key2=8885096311&coll=GUIDE&dl=ACM&CFID=65103519&CFTOKEN=82710215

一支拜占庭的军队在敌人的城堡外驻扎,该军队有多个将军,他们各自控制自己的部队,并能相互之间进行通信通过messager。观察敌人后他们必须决策。但是,在这些将军中存在叛徒,会阻止将军们的意见达到一致。因此,必须有一个算法,来保证:

1。所以忠心的将军都执行同一决策。

2。以少数存在的叛徒不能使将军们作出怀的决策。

要判断什么样的决策是坏的,很难。因此,我们只讨论如何让将军们作出决策。

每 个将军观察敌人,将自己的观察后的决策通知其他人。设v(i)是第i个将军的观察后的决策。每个将军以某种方法将v(1),v(2)....v(n)综合 起来(可看作是一个n维函数)得到一个计划。上面的条件1,很容易实现,只有所有将军采用相同的方法来综合v(1),v(2)....v(n)的信息。条 件2的满足还有更强的方法。

如果每个将军要做的决策只是进攻或撤退(attack or retreate),设v(i)是第i个将军所做的认为最好的决策。那么从v(1),v(2)....v(n)到最后的计划的映射方法,就可以是多数原 则,即看attack or retreate的决策谁多,就认为是最好的。但是这种情况下,占少数的叛徒还是有机会影响最后的计划,在下面的情况下:如果忠心的将军的意见从数量差不 多分成两派。在这种两种意见的支持率不相上下的情况下,无论哪种意见都难称得上是好的。

但是条件1还是有问题,因为叛徒可能给不同的将军发不同的信息。即对第i个将军而言v(k)与第j个将军的v(k)可能是不同的(如果k是叛徒的话)。

因此,对条件1还要满足:

1。每个忠心的将军要获得相同的v(1),v(2)....v(n)

2.如果第i个将军是忠心的,则他发给每个忠心的将军的信息必须被用作v(i)。

对条件1重写(1。每个忠心的将军要获得相同的v(1),v(2)....v(n)):

1a。两个忠心的将军使用相同的v(i)。

1a和2是第i个将军发送的信息的条件,在这样的限制下,我们来考虑一个将军是如何向其他将军传送消息的。可以将这个问题描述为一个司令向他的副官发命令,得到Byzantine Generals Problem.司令必须将他的命令发送个n-1个副官,并且:

IC1所有忠心的副官遵守相同的命令。

IC2如果司令是忠心的,每个忠心副官遵守他的命令。

因此,对于最初的问题(一支拜占庭的军队在敌人的城堡外驻扎。。。。),第i个将军向其他将军发送自己的决策可以看作是第i个将军发出"用v(i)作为我的决策"的命令,到可相对视为其副官的n-1个将军。


Wednesday, December 5, 2007

关于 ACE(Adaptive Communication Environment,自使用通信环境)的介绍

一直有听闻ACE是一个强大的,用于网络编程的C++库,但是始终无缘一见其内在。
今天在china-pub搜书时又见到有这个名词了,于是搜索了一下,了解了大概的意思。
尽管以下文字仅能看懂20%……还是先做个标记吧 ^^

1. ACE目录结构介绍

ACE(ADAPTIVE Communication Environment),中文的意思就是自适配通讯环境,ACE是一个用于开发网络程序的优秀的C++的框架,在国外有很广泛的使用,在国内一些大的开 发通讯产品的公司也有使用。我接触ACE也有一段时间了,虽然时间不长,但我还是感觉到ACE确实是一个好东西,对于丰富自己的知识面有很大的帮助。虽然 我们项目目前是采用C语言来开发,但是当接触ACE后,你会发现"喔,原来程序还可以这样"。例如:我觉得ACE里面Reactor框架就是一个非常的东 西,我们在开发网络程序的时候,常常采用poll来监视各种网络事件,但当采用该框架后,你现在只是需要关系你的业务逻辑,当发生特定的网络事件后,框架 会回调你的业务逻辑。其实按照这个思路,我们完全可以用C来实现类似的功能,当你完成这个后,你会发现你原来用C语言写的过程风格的代码竟然有了OO的味 道。

ACE确实是好东西,但也不是能轻松的就能掌握的,我们还需要一步一步的来蚕食这个大象。

万丈高楼平地起,首先我们还是了解一下ACE的目录结构,从整体上对ACE有一个认识,为今后的进一步学习打下一个基础。

解开ACE的压缩包后,你会发现一个ACE_wrappers目录,这个目录也就是ACE的HOME目录,它下面还包含着一些子目录:

ace:这个目录是ACE中最重要的目录,它包含了ACE的所有源码,但遗憾的是,ACE的所有源文件和头文件全部杂乱的堆在这个目录里,这可能也 是很多开源软件的缺点。其实ACE的代码完全可以按照不同的功能进行不同目录的划分,例如:Reactor框架和thread框架代码完全可以划分开,我 想一个代码组织良好的ACE,将会给大家的学习带来极大的好处,我将在后面的文章里给出ACE代码划分的方法;
ACEXML:这个目录包含了用ACE实现的一个XML解析器;
apps:这个目录包含了用ACE来实现的一些较大的应用程序,例如:JAWS,一个WEB服务器;

ASNMP:基于ACE的SNMP协议实现;
bin:包含里用例方便开发的perl脚本程序,例如:在WIN32上开发DLL时候,需要导出DLL的接口;
docs:ACE的一些帮助文档,其中ACE-subsets.html文档,对我们划分ACE的代码有很大的帮助;

examples:是用ACE来编写的一些例子程序,方便更好的学习和理解ACE;
include:也是ACE中一个比较重要的目录,它包含了在不同的平台上编译时候的编译规则,库的编译规则等;
netsvcs:一些基于ACE的在分布式系统中常用的程序,例如:分布式系统日志系统,网络锁,时间同步等;

TAO:基于ACE的实时CORBA实现,TAO在分布式系统中使用相当广泛,也是一个不可多得的好资源;
tests:用来对ACE进行回归测试,也提供了一个学习ACE的很好的例子代码;


2. ACE和ICE介绍1

自从上世纪九十年代以来,计算工业一直在使用像DCOM CORBA这样的面向对象中间件平台。在使分布式计算能为应用开发者所用的进程中,面向对象中间件是十分重要的一步 。开发者第一次拥有了这样的可能:可以构建分布式应用 ――中间件平台会照管大部分网络杂务,比如整编(marshaling )和解编(unmarshaling)(对数据进行编码与解码,以进行传送)、把逻辑对象地址映射到物理传输端点、根据客户和服务器的原生机器架构改变数据的表示,以及应需自动启动服务器。然而,由于一些原因,无论是 DCOM 还是 CORBA,都未能成功占领大部分计算市场:(1) DCOM Microsoft 的独家解决方案,在异种网络中,各种机器会运行多种操作系统,无法使用 COM(2) DCOM 不能支持大量对象(数十万或数百万),这在很大程度上是它的分布式垃圾收集机制来的开销造成的。(3) 尽管有多家供应商提供 CORBA 产品,几乎不可能找到一家供应商,能够为异种网络中的所有环境提供实现。尽管进行了大量标准化工作,不同的 CORBA 实现之间仍缺乏互操作性,从而不断地造成各种问题;而且,由于供应商常常会自行定义扩展,而CORBA 又缺乏针对多线程环境的规范,对于像C C++ 这样的语言,源码兼容性从未完全实现过 .(4) DCOM CORBA 都过于复杂。 在异种环境中,让 DCOM CORBA 共存从来都不是一件容易的事情:尽管有供应商提供互操作产,这两种平台之间的互操作从来都不是无缝的,而且难以管理,会产生互不相连的技术孤岛。2002 年,Microsoft .NET 平台取代了 DCOM。但尽管.NET 提供了比DCOM 更强大的分布式计算支持,它仍然是 Microsoft 的独家解决方案,因而不是异种环境下的选择。另一方面,CORBA 近年来已停滞不前,许多供应商离开了市场,给消费者留下了不再受到广泛支持的平台;剩下的少数供应商在进一步标准化方面的兴趣也已衰退,致使CORBA 规范中的许多缺陷未能得到解决,或是在它们被报告多年之后才得到解决。在DCOM CORBA 衰败的同时,分布式计算社群对SOAPweb services产生了浓厚的兴趣。使用无处不在的 WWW 基础设施和HTTP 来开发中间件平台的想法十分迷人――至少在理论上。 SOAP web services 曾经允诺要成为Internet 上的分布式计算通用语言。 但尽管引发了很大的公众效应,发表了许多论文,web services 却没有能兑现其允诺:用web services 架构开发的商业系统非常少。其原因是:无论是在网络带宽方面,还是在 CPU 开销方面, SOAP 都会给应用造成严重的性能恶化,以致于该技术无法适用于许多有苛刻性能要求的系统。尽管SOAP 提供了"on-the-wire" 规范,要开发现实的应用,那仍是不够的,因为该规范提供的抽象层次太低。应用可以把各种 SOAP 消息拼凑在一起,但这样做极其繁琐而易错。缺乏更高级的抽象促使供应商提供各种应用开发平台,使遵从 SOAP 的应用开发自动化。但是,除了协议一级,这些开发平台完全没有标准化,不可避免是私有的,所以用一家供应商开发的应用无法与其他供应商的中间件产品一起使用。
关于SOAP web services 的架构安全性,有一些严重的担忧。  
   
这些使人不快的选择, ZeroC, Inc. 决定开发Internet Communications Engine ,简称Ice Riverace公司(
http://www.riverace.com)采用开放源码商业模式对 ACE进行商业支持。此外,ACE 开发组的许多成员目前正在进行The ACE ORB TAO http://www.cs.wustl.edu/~schmidt/TAO.html)的开发工作。 ACE自适配通信环境(ADAPTIVE Communication Environment )是可自由使用、开放源码的面向对象(OO)框架( framework),它实现了许多用于并发通信软件的核心模式。ACE 提供了一组丰富的可重用C++包装外观( wrapper facade)和框架组件,可跨多种平台完成通用的通信软件任务,其中包括:事件多路分离和事件处理器分派、信号处理、服务初始化、进程间通信、共享内存管理、消息路由、分布式服务动态(重)配置、并发执行和同步,等等。 ACE的目标用户是高性能和实时通信服务和应用的开发者。它简化了使用进程间通信、事件多路分离、显式动态链接和并发的OO 网络应用和服务的开发。此外,通过服务在运行时与应用的动态链接,ACE 使系统的配置和重配置得以自动化。ICE(Internet Communications Engine) ZeroC提供的一款高性能的中间件,基于ICE 可以实现电信级的解决方案。前面我们提到过在设计网站架构的时候可以使用ICE实现对网站应用的基础对象操作,将基础对象操作和数据库操作封装在这一层,在业务逻辑层以及表现层 (java,php,.net,python)进行更丰富的表现与操作,从而实现比较好的架构。基于 ICE的数据层可以在未来方便的进行扩展。ICE 支持分布式的部署管理,消息中间件,以及网格计算等等。     IceACE 在性能与开发简便上深化了.CORBA这是一个老牌的分布式中间件平台,并且以其标准实现困难,开发者使用困难而著称。   Ice 采用的许多思想也能在 CORBA 及以前的一些分布式计算平台中找到。在有些方面, Ice CORBA 非常接近,而在另外一些方面,它们的差异则意义深远,并且在架构上有着广泛的影响。如果你曾经使用过 CORBA,了解这些差异十分重要。尽管从表面看来, Ice 对象模型与CORBA 对象模型是一样的,但它们在一些重要方面却有所不同。类型系统 Ice 对象和CORBA 对象一样,都只有一个派生层次最深的(most derived 主接口。但Ice 对象可以提供其他接口作为facets。重要的是要注意到,一个 Ice 对象的所有facets 都具有相同的对象标识,也就是说,客户看到的是具有多个接口的单个对象,而不是看到多个对象、每个对象有不同的接口。facets 提供了极大的架构灵活性。特别地,它们为版本管理问题提供了一种解决途径:你可以简单地给已经存在的对象增加新的facet,轻松地扩展某个服务器的功能,而不会破坏已有的、已经部署的客户。代理语义 Ice 代理( CORBA 对象引用的等价物) 不是不透明的。 客户只要知道对象的类型和标识,无需其他系统组件的支持,就可以创建出代理(在使用间接绑定时, 不必了解对象的传输地址)。
  
  ACE
的好处包括:
(1)
增强可移植性:在ACE 组件的帮助下,很容易在一种OS平台上编写并发网络应用,然后快速地将它们移植到各种其他的 OS平台上。而且,因为ACE 是开放源码的自由软件,你无需担心被锁定在特定的操作系统平台或编译器上。
(2)
更好的软件质量:ACE的设计使用了许多可提高软件质量的关键模式,这些质量因素包括通信软件灵活性、可扩展性、重用性和模块性。
(3)
更高的效率和可预测性: ACE经仔细设计,支持广泛的应用服务质量( QoS)需求,包括延迟敏感应用的低响应等待时间、高带宽应用的高性能,以及实时应用的可预测性。
(4)
更容易转换到标准的高级中间件:TAO 使用了ACE提供的可重用组件和模式。它是 CORBA的开发源码、遵循标准的实现,并为高性能和实时系统作了优化。为此,ACETAO被设计为能良好地协同工作,以提供全面的中间件解决方案


3. ACE和ICE介绍2

ACE还包含一个高级的网络编程框架,集成并增强了较低层次的 C++包装外观。该框架支持将并发分布式服务动态配置进应用。ACE 的框架部分包含以下组件:
(1)
事件多路分离组件:ACE Reactor(反应器 )Proactor (前摄器)是可扩展的面向对象多路分离器,它们分派应用专有的处理器,以响应多种类型的基于I/O、定时器、信号和同步的事件。
(2)
服务初始化组件: ACE Acceptor(接受器)和 Connector(连接器)组件分别使主动和被动的初始化任务与初始化一旦完成后通信服务所执行的应用专有的任务去耦合。
(3)
服务配置组件: ACE Service Configurator(服务配置器)支持应用的配置,这些应用的服务可在安装时和/ 或运行时被动态装配。
(4)
分层的流组件:ACE Stream组件简化了像用户级协议栈这样的由分层服务组成的通信软件应用的开发。
(5)ORB
适配器组件:通过 ORB适配器, ACE可以与单线程和多线程CORBA 实现进行无缝集成。
ACE
框架组件便利了通信软件的开发,它们无需修改、重编译、重链接,或频繁地重启运行中的应用,就可被更新和扩展。在ACE中,这样的灵活性是通过结合以下要素来获得的:( 1 C++语言特性,比如模板、继承和动态绑定,(2 )设计模式,比如抽象工厂、策略和服务配置器,以及(3 OS机制.
除了OS适配层、 C++包装外观和框架组件,ACE 还提供了包装成自包含组件的标准分布式服务库。尽管这些服务组件并不是ACE框架库的严格组成部分,它们在 ACE中扮演了两种角色:

1.
分解出可重用分布式应用的" 积木":这些服务组件提供通用的分布式应用任务的可重用实现,比如名字服务、事件路由、日志、时间同步和网络锁定。
2.
演示常用的 ACE组件的用例:这些分布式服务还演示了怎样用像 ReactorService ConfiguratorAcceptor ConnectorActive Object ,以及IPC包装这样的 ACE组件来有效地开发灵活、高效和可靠的通信软件。
  
     Ice
是一种面向对象的中间件平台。从根本上说,这意味着Ice 为构建面向对象的客户-服务器应用提供了工具、API 和库支持。Ice应适合在异种环境中使用:客户和服务器可以用不同的编程语言编写,可以运行在不同的操作系统和机器架构上,并且可以使用多种网络技术进行通信。无论部署环境如何,这些应用的源码都是可移植的。

 ICE的好处包括:

(1)客户无需询问外部的查找服务,比如命名服务,就能够创建代理。实际上,对象标识和对象的名字被认为是同一事物。这样能够消除命名服务的内容与实际情况失去同步所可能带来的问题;同时,为了让客户和服务器正常工作、必须正常运转的系统组件的数目也会减少。
(2)
通过创建所需的初始对象的代理,客户可以轻松地进行自引导(bootstrap)。这样就无需使用单独的引导服务了。
(3)
不需要对串化代理进行不同的编码。一种统一的表示就足够了,而这种表示是人可以阅读的。这样就避免了 CORBA 的三种不同的对象引用编码( IORcorbaloc ,以及corbaname)所带来的各种复杂问题。开发者多年使用 CORBA 的经验表明,对象引用的不透明性很成问题:它不仅需要更加复杂的API 和运行时支,还会妨碍我们构建现实的系统。为此, CORBA 增加了像 corbaloc corbaname 这样的机制,以及用于进行引用比较的is_equivalent hash 操作(这些操作的定义有问题)。所有这些机制都降低了对象引用的不透明性,但CORBA 平台的其他部分仍试图维持引用是不透明的这样一个错觉。结果,开发者在两方面所得的东西都是最糟的:引用既不是完全不透明的,也不是完全透明的―― 这样所带来的混乱和复杂性相当大。对象标识Ice 对象模型假定对象标识在任何地方都是唯一的(但并没有把这个要求强加给应用开发者)。这种对象标识的主要好处是,你可以迁移服务器,也可以把多个不同服务器中的对象合并进 一个服务器,而不用考虑名字冲突的问题:如果每个 Ice 对象都具有唯一的标识,它就不可能与另外的域中的对象的标识发生冲突。Ice 对象模型还使用了强对象标识:使用本地的客户端操作,你就能确定两个代理表示的是否是同一个对象(在CORBA 中,要进行可靠的标识比较,你必须调用远地对象上的操作)。本地标识比较要高效得多,而且对于有些应用领域而言(比如分布式事务服务),这样的比较也至关紧要。

      Ice 在架构上提供的好处
      (1)
面向对象的语义:Ice "在线路上 "完全保留了 面向对象范型。所有的操作调用都使用迟后绑定,所以操作的实现的选定,是根据对象在运行时的(而不是静态的)实际类型决定的。
      (2)
持同步和异步的消息传递:Ice 提供了同步和异步的操作调用和分派,并且通过 IceStorm 提供了发布-订阅消息传递机制。这样,你可以根据你的应用的需要来选择通信模型,而不必把你的应用硬塞进某种模型里。
      (3)
支持多个接口 :通过facets ,对象可以提供多个不相关的接口,同时又跨越这些接口、保持单一的对象标识。这提供了极大的灵活性,特别是在这样的情况下:应用在发生演化,但又需要与更老的、已经部署的客户保持兼容。
      (4)
机器无关性: 客户及服务器与底层的机器架构屏蔽开来。对于应用代码而言,像字节序和填充这样的问题都隐藏了起来。
      (5)
语言无关性:客户和服务器可以分别部署,所用语言也可以不同(目前支持 C++ Java,以及PHP (客户端))。 客户和服务器所用的 Slice 定义建立两者之间的接口合约,这样的定义也是它们唯一需要达成一致的东西。
      (6)
操作系统无关性:Ice API 完全是可移植的,所以同样的源码能够在Windows UNIX上编译和运行。
      (7)
线程支持:Ice run time 完全是线程化的,其API 是线程安全的。 作为应用开发者,(除了在访问共享数据时进行同步)你无需为开发线程化的高性能客户和服务器付出额外努力。
    (8)
传输机制无关性 :Ice 目前采用了TCP/IP UDP 作为传输协议。客户和服务器代码都不需要了解底层的传输机制(你可以通过一个配置参数选择所需的传输机制)。
    (9)位置和服务器透明性:Ice run time 会负责定位对象,并管理底层的传输机制,比如打开和关闭连接。客户与服务器之间的交互显得像是无连接的。如果在客户调用操作时,服务器没有运行,你可以通过IcePack 让它们随需启动。服务器可以迁移到不同的物理地址,而不会使客户持有的代理失效,而客户完全不知道对象实现是怎样分布在多个服务器进程上的。
  (10)
安全性: 通过SSL 强加密,可以使客户和服务器完全安全地进行通信,这样,应用可以使用不安全的网络安全地进行通信。你可以使用 Glacier穿过防火墙,实现安全的请求转发,并且完全支持回调。
  (11)
内建的持久机制 :使用Freeze ,创建持久的对象实现变成了一件微不足道的事情。Ice提供了对高性能数据库 Berkeley DB[18] 的内建支持。  Ice 的源码是开放的。尽管要使用Ice 平台,并不一定要阅读源码,通过源码你可以了解各种事情是怎样实现的,或把这些代码移植到新的操作系统上。

  总而言之, Ice ACE 提供了一流的分布式计算开发和部署环境,比我们所知道的其他任何平台都更完整。提供适用于异种环境的面向对象中间件平台 ,提供一组完整的特性,支持广泛的领域中的实际的分布式应用的开发, 避免不必要的复杂性,使平台更易于学习和使用。提供一种在网络带宽、内存使用和CPU 开销方面都很高效的实现 ,提供一种具有内建安全性的实现,使它适用于不安全的公共网络。


Tuesday, December 4, 2007

[人物]W.Richard Stevens

W.Richard Stevens
以下摘自:http://www.china-pub.com/main/sale/renwu/luminary.asp?id=14
国际知名的Unix和网络专家,《TCP/IP 详解》(三卷本)作者   W.Richard Stevens(1951-1999),是国际知名的Unix和网络专家;受人尊敬的计算机图书作家;同时他还是广受欢迎的教师和顾问。Stevens先 生1951年生于赞比亚,他的家庭曾多次搬迁,最终定居于南非。早年,他就读于美国弗吉尼亚州的费什本军事学校,后获得密歇根大学学士、亚利桑那大学系统 工程硕士和博士学位。他曾就职于基特峰国家天文台,从事计算机编程;还曾在康涅狄格州纽黑文市的健康系统国际公司任主管计算机服务的副总裁。 Stevens先生不幸病逝于1999年9月1日,他的离去是计算机界的巨大损失。
 
传世之作有:
《UNIX环境高级编程》――这本我有第二版,很经典。

TCP/IP详解系列:
《TCP/IP详解 卷1:协议》
《TCP/IP详解 卷2:实现TCP/IP》
《TCP/IP详解卷三:TCP事务协议,HTTP,NNTP和UNIX域协议》

UNP系列:
《UNIX 网络编程(第二版)第1卷:套接口API和X/Open 传输接口API》
《UNIX 网络编程(第二版)第2卷:进程间通信》

今天才知道这些东西的含义:CCENT/CCNA/CCNP/CCIE

CCENT(Cisco Certified Entry Networking Technician,思科连网技术人员入门级认证)

CCNA(Cisco Certified Network Associate,思科网络安装和支持工程师)

CCNP(Cisco Certified Network Professional,思科认证网络高级工程师)

CCIE(Cisco Certified Internetwork Expert,思科认证互联网专家)

以上一个比一个高级(从上到下)
而且必须有prerequisite的关系,CCNA->CCNP->CCIE。
其中CCENT和CCNA是最基础的,不需要prerequisite,而CCENT是新推出的难度只有CCNA一半的认证。

以上考试价格都在1000RMB以上,不过对于工作应该有帮助,特别是CCNP及CCIE。

CS本科生水平,应该要达到CCNA吧……

Sunday, December 2, 2007

关于lucene

最近想给自己某程序附加上文档的索引,想起有lucene这样东西。于是找到了下面的文章。

实战 Lucene,第 1 部分: 初识 Lucene
http://www.ibm.com/developerworks/cn/java/j-lo-lucene1/

另外这里有篇介绍lucene工作原理的文章:
深入 Lucene 索引机制
http://www.ibm.com/developerworks/cn/java/wa-lucene/

写得非常浅显易懂并且带有示例的关于lucene的文档,IBM dw出品必属精品阿。
可惜似乎只有这篇了,找不到第2部分以及后续的文档。

>> 插入:Lucene简介

Lucene 简介

Lucene 是一个基于 Java 的全文信息检索工具包,它不是一个完整的搜索应用程序,而是为你的应用程序提供索引和搜索功能。Lucene 目前是 Apache Jakarta 家族中的一个开源项目。也是目前最为流行的基于 Java 开源全文检索工具包。

目前已经有很多应用程序的搜索功能是基于 Lucene 的,比如 Eclipse 的帮助系统的搜索功能。Lucene 能够为文本类型的数据建立索引,所以你只要能把你要索引的数据格式转化的文本的,Lucene 就能对你的文档进行索引和搜索。比如你要对一些 HTML 文档,PDF 文档进行索引的话你就首先需要把 HTML 文档和 PDF 文档转化成文本格式的,然后将转化后的内容交给 Lucene 进行索引,然后把创建好的索引文件保存到磁盘或者内存中,最后根据用户输入的查询条件在索引文件上进行查询。不指定要索引的文档的格式也使 Lucene 能够几乎适用于所有的搜索应用程序。

>> 插入完

按照示例敲了一下,挺有感觉的,总结如下:
0.我的lucene是用yum直接安装的,装好后在/usr/share/java/lucene-1.4.3.jar中,其中会自动生成一个lucene.jar的符号链接在同目录中,因此必须把该包加入到CLASSPATH变量中。
1.OOP思想的好的贯彻。整个包(org.apache.lucene )的组织结构非常好,具体可以参考文章。
2.工作原理大致是:首先编写索引程序,用于建立索引;其次是建立查询程序,用于查询生成的索引。最后,执行索引程序生成索引,并用查询程序生成query并从建立好的索引数据库中取得数据。
3.默认的分词器很强大,可以识别出文本编码为UTF8还是GBK等(只在这两种中测试过),但是因为是用最基础的,预定义的分析器,因此似乎对于中文的分词没有处理(默认是一个中文字当作一个词)
4.想到的一般应用 (对于个人快速使用非常方便)
4.1.编写的静态website可以简单地使用lucene进行全文检索(当然要编写中文分词,下同)
4.2.小说内容搜索
4.3.源代码内容搜索(这个其实已经有更好的实现拉)


Saturday, December 1, 2007

http://www.ibm.com/developerworks/cn/linux/l-cn-ppp/index2.html?ca=drs-cn

http://www.ibm.com/developerworks/cn/linux/l-cn-ppp/index2.html?ca=drs-cn

--
Best wishes,
Yours, iveney
Department, of Computer Science,
Zhongshan University (Sun Yat-sen University),
Guangzhou, China

一篇简单的介绍内存池及一个简单实现的文章

http://www.ibm.com/developerworks/cn/linux/l-cn-ppp/index6.html?ca=drs-cn

Linux 文件系统剖析-按照分层结构讨论 Linux 文件系统

http://www.ibm.com/developerworks/cn/linux/l-linux-filesystem/index.html?ca=drs-cn

在文件系统方面,Linux® 可以算得上操作系统中的 "瑞士军刀"。Linux 支持许多种文件系统,从日志型文件系统到集群文件系统和加密文件系统。对于使用标准的和比较奇特的文件系统以及开发文件系统来说,Linux 是极好的平台。本文讨论 Linux 内核中的虚拟文件系统(VFS,有时候称为虚拟文件系统交换器),然后介绍将文件系统连接在一起的主要结构。


--
Best wishes,
Yours, iveney
Department, of Computer Science,
Zhongshan University (Sun Yat-sen University),
Guangzhou, China

Thursday, November 29, 2007

iveney学CS历险记之《编译原理》

刚才有个UST的朋友问我某个project怎么做,不得已就把compiler的东西又在脑海中翻了一遍。
考虑到刚考完没多久,还有印象,就顺便写写吧。

课本:编译程序设计原理,北大
经典教材:龙书 虎书 鲸书,还有本《编译原理及实践》(有个TINY实例的)也很不错

记得以前看文章介绍说,本来编译原理是cs为数不多的几门core course之一,但是由于目前其理论和实践都已经发展到很完美的阶段了,也就被剔出了acm还是什么的订的cs curriculum(不担保以上断言的真实性……)
事实上,我觉得这门课还是很有必要上的,不然我们就成了知其然而不知其所以然的民工。从我们刚刚接触程序设计时,我相信大家就经常遇到书本上说,"程序运行时xxxx","内存中xxxx",等等。我当时就一直在想,为什么会这样呢?为什么不是那样呢?而这些问题在"程序结构与组织"、"运行时刻环境","运行存储管理"等章节中有介绍。下次我们遇到BT的一些++--的问题,就可以大胆地说compiler-dependent了。

正如Leeman在这门课的outline中所说,我们学习应该是这样一个顺序:
入门:programming fundamental
进阶:compiler construction
大师:the principle of programming language

而编译原理是位于中间的,可见其重要性。
上次在科大时就曾经跟老师讨论过说为什么那里没有这门课程,他们说没有老师精通就没开了……但是奇怪的是有一门the principle of programming language,而且老师都是UC Berkeley和Standford出来的大牛,不会教不了compiler吧……这个学期有个师弟去那边交换选了这门课,看了看介绍,发觉貌似是编译原理与程序设计语言原理的压缩体,两者都讲了。
其实分类也不必这么拘泥,学到东西就好了。

还记得Prof. Jun Zhang在数值计算课程中所说,"我们整个学期所学的东西归纳下来就是这个流程图"。在编译原理这门课中,我觉得我们也是围绕着CS dept@SYSU所采用多年的那本北大的《编译程序设计原理》中那幅编译过程的流程图来展开的。
不过我们课程的着重点貌似在词法分析,语法分析和语义分析中,而后续的中间代码生成,代码优化,代码生成则比较简略。

词法分析比较简单,其中的有限自动机理论非常奇妙与好玩。不能不说的就是正则表达式,实在是one of the most powerful tools,强烈有朝一日可以精通之……
语法分析有点难度,我反反复复看了好多遍,每次都有很多收获。两大类分析法又可再细分之,各种分析法优劣参半。
语法指导定义与翻译模式则是让语言按你的想法工作的重点,解释了符合语法的语句应该执行什么动作。
运行时刻环境则可以让人对程序在内存中的组织有了深入的了解,以及过程调用,参数传递,符号表等的组织也能得到认识。
后面的几章没有重点学习……就不说了……
可以学的还有很多,比如一些类、重载、多态的实现,以及函数式语言,解释器的构造都值得深入了解。

Leeman:"编译原理是理论与实践的完美结合",在这里得到了完美的体现。
FA理论应用于regular expression以及词法分析器,LR分析法的正规化使得编译程序的自动生成成为可能。

关于项目:
我们的项目分为五步,分别是:
0.给出类似TINY语言的语法(参考《编译原理及实践》),给出两个错误与正确的src
1.手工写lexer
2.用JFlex写lexer
3.用JavaCUP自动生成parser
4.用top-down方法写parser

有3个加分实验,
1.从正则表达式构造有限自动机的方法研究(报告形式)
2.正则表达式匹配器(考察有限自动机、LR分析法)
3.计算器(考察算符分析法)

都非常有趣~可惜我能力有限,遇到很多难题,基本上都是向吴毅大牛咨询的,在此谢过 m(_ _)m
仍然记得第二个加分实验用了我整个星期而大牛一晚就解决了,差距阿差距……
顺带赞美Java的Exception handling,真的是非常方便与强大,为编写代码带来了很大帮助。

由于特殊原因,没能上成Leeman的课,是暑假自学然后参加缓考的,希望大四下学期能有时间去听听课。
最后,我想说,这是一门古老而经典的课程,赞美。

Sunday, November 25, 2007

11.24.广州.白云山广外机经 by iveney

/ * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
* 前序:住宿篇
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * /

由于自己在大学城那边,做车过去保守估计要一个小时(可以做1路或者76路),而自己又是很怕坐车的人,因此提早了一天过去那边住顺便复习。
我住的宾馆是学生宿舍那边的柏豪酒店,单/双人房一样价钱,打折后180-200之间。我住过两次了,还不错,三星级的,而且很新,挺舒服,最主要是能上网。
我可以在那边很安静的复习,还能上网灌灌水 ^_^
由于是下午3点考的,我想睡个中午觉才出门,服务员也很好人地不给我算钟点房(一开始说1个小时30元),让我呆到两点才退房。

/ * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
* 考试:等待
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * /

考场是广外六教的B108室,离宾馆很近,就在学生宿舍3栋旁边。考虑到考试时间跨过我正常进餐时间,于是我买了一瓶红牛,一瓶牛奶和一个sandwich。
进场前喝了红牛提提神,等到两点半后,工作人员叫大家看自己的顺序编号,是按照姓名字母序排的,我排得很后,汗。接下来我们进入旁边的课室,写confidential statement。
写好后,开始按顺序入场。

这段时间是最郁闷的,本来不紧张的,呆久了就紧张了。进场速度很慢,非常慢,很多人都开始看书或聊天了。由于我是一个人,旁边的mm很pp又不好意思搭讪,坐在那不知干什么好。
我是最不喜欢考试前还狂看书的,但是后来实在闷得发慌,就拿出mp3来听一些lecture的录音。

/ * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
* 考试:进场
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * /

等了好久终于轮到我进场,乖乖地递上身份证和学生证(护照也可以,不过我没),阿姨扫了我两眼就进去了。
进去后先把东西放下,我随身带了一包纸巾和眼药水。然后拍照,拍完后工作人员把自己领到位置,就开考了。

/ * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
* 考试:环境介绍
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * /

这个考场环境很不错,很安静,唯一能听到的外界声音就是上下课的铃声。
房间有两个,从进场入口进去后,里面还有个门到隔壁的房间,我是在里面的房间考的。
座位周围有隔板,键盘,鼠标都很好,屏幕是15寸LCD,很舒服,可惜我不习惯LCD斜着放,平时我都是正对着用的,anyway,已经很好了。
有4张草稿纸,很好,笔是圆珠笔,不喜欢,个人比较喜欢铅笔。

开始考试后,工作人员帮你输入密码进入考试程序。
在确认了自己的身份还有一些繁琐的introduction之后就进入了阅读考试。

PS.一看那恶心的滚动条就知道是Java写的程序,~(-_-~)。
做的过程中有时会卡,但是时间不会算的,我猜可能是网络传输方面的延迟,看起来不像是程序的延迟?
好处是可以趁机看阅读文章,在next之前调好文章看~
另外口语答完题时也会有大概5-10秒的延迟,可能是压缩录音数据并传输,可以趁机舒缓心情。

/ * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
* iBT:Reading
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * /

阅读没有加试,我哭。

发觉不知是不是平时做题难的问题,觉得阅读比做练习要简单。
不过这个简单是局限在文章上的简单,题目的话感觉比barron稍难,起码就词汇题来说我不能秒杀。
发觉做阅读真的不需要看全文的,直接拖动滑动条到底然后continue,直接做题。
因为iBT的阅读出题基本上是按照段落顺序来出的,很少有段落会不问问题,因此在一边做题的同时就一边阅读了文章,省了不少时间。
当做到倒数第三题左右,基本上是已经读完全文了,这时做归纳题,总结题就方便很多了。

20分钟完成,我用了18分钟。
1.洞穴艺术,主要是介绍了远古人如何在洞穴里作画。第一段介绍原因,中间主体部分介绍了学者推断是大面积的作画,必须要靠不同的身体姿势,如趴着之类的来完成;另外由于洞内暗,要用灯光照,而颜料又快干,因此必须有助手。助手和画师都是训练有素的。最后一段忘了……

40分钟完成,这两篇好像比较简单,用了20来分钟就解决了,然后检查了一遍就顺便在草稿纸上默写口语模板……
2.蛇类动物的二叉舌头功能研究 。先是提出了某人的理论说是用来舔猎物味道进嘴里某器官,后来被科学家推翻,然后又有一个假设,被广泛接受。有4大supporting evidence,包括他们的感觉分别传入大脑中两个半脑以进行对比比较。其他忘了……最后把蛇,蜥蜴等的舌头的作用与其他动物的spatial感觉器官(类似耳朵)进行对比。

3.专利。看到题目我很兴奋,因为早上刚好做了一篇某阅读软件关于专利的阅读,叫"conquest by patent",有些细节还是一模一样的,嘿嘿。主要是按专利的发展,举了一些国家的专利的例子并指出优缺点。最后着重介绍美国的专利系统。


/ * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
* iBT:Listening
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * /

听力有加试,都是老题:(1)mm丢钱包 (2)神经glia cell (3)浪漫主义与新古典主义
但是我不知是不是题目与以前机经的不一样,因为mm丢钱包最后一题是问mm这句话什么意思
man: I'm glad I can help you
mm: You are glad.
问mm那句话什么意思。而机经里好像是说mm说"you help!"是什么意思。

另外,我觉得听力其实内容不难(我听了两个月的BBC/VOA/CNN news并坚持听写了一段时间的scientific american 60 second science,听力有明显提高,但是听到慢题会很烦,容易走神 -_-|||),但是题目比较难,很多题都不是那么明显的。barron里的听力好像比较长,听得我想睡觉,但是题目的选项区别比较明显,非常intuitive。
而iBT的选项还要经过一些推敲才能选,很多都不能确定。

还有,我没有看OG的listening题型,只做过delta的练习和barron的两个test。发觉有一种题型我没遇过,就是给出几个选项要选2个的。

以下不确保顺序正确

10分钟答题
1.mm宿舍的stove坏了去求助管理员,而管理员说不关他事叫mm找对面的单位,但mm说是那边叫过来的。管理员知道情况后说是电力供应问题,可能要下星期一甚至星期二才能好。mm很郁闷,因为她周末有party,她说好吧我可以推迟到下星期,管理员说为什么呢,你可以借你对面的来用,mm抱怨说那里太mess。管理员又建议说你可以用xxx活动室的,本来不给租但是现在特殊情况他会尽量帮mm申请,mm很高兴。
2.介绍人的情感与记忆的联系,这篇由于语速有点慢搞得我走神了。首先是说一个实验,给一堆图片让人记,结果active,negative记得最深,neutral的最差。而negative又比active效果好,有个学生介绍自己爬楼梯摔的经验,教授说对。然后说另一个实验,证明大脑不同区域对应不同情感,而其中的前庭脑(xxxfront的)跟创造力对应。然后说开心时时那里活动比较激烈,然后举了某个作家的例子。
3.两种类型的动物进食习惯 。一种是generalist,一种是specialist。第一种啥都能吃,如rat;第二种只吃固定的东西,如xxx动物(忘了),只吃某种树木的叶子,蛋白质少还有毒。然后对比了两种习惯的优劣,分别举了一些例子。如generalist中某种老鼠如果只能吃一种,他也会挑有营养的来吃。这个时候有学生问:xx为什么不吃其他东西以使自己选择广呢?教授反问:"xx说:我能得到什么?"固定吃这种树叶就完全足够了,因为这种东西别人不敢吃,有毒,而找其他东西还可能与别人竞争呢。

10分钟答题
1. 一男生要毕业了,找老师询问career问题。老师说自己以前也是很迷茫并take one year off,后来决定继续学习与读PhD。后来老师突然想起有个学生参加了某个program,叫gg去问那学生,那个program可以出国,又可以做老师之类的。
2.讲18-19世纪英国壁纸的发展。由于工业革命,涌现出了一些色彩鲜艳的壁纸,并且有大量的用人手做不出来的壁纸,另外由于某设备的出现,使得可以大量生产,价格降低。而一些reformer认为这是在show科技,而忽视了艺术价值。后来有一种xxx风格的,主要是在壁纸上画其他材质如树木,石头的图案以假乱真,受到reform大力批评。但是结果是,新科技生产的壁纸受到平民追捧,而reformer自己坚持有艺术价值的只出现在政府等高级机构中。
3.讲化石与地壳的年代鉴别。主要是两种方法,首先是相对法,给出了一幅grand canyon的图,基本根据是,一层一层的沉积岩中,年代新的比年代老的接近顶,然而也可能出现例外,因为由于地壳运动,老的会爬到新的上面去。然而根据这种方法只能大概估算出岩层属于大概哪一个时期,而不能算出具体时间段。后来介绍的是绝对方法,教授强调绝对是指相对与第一种方法而言的。利用放射元素法鉴定岩石成分半衰期之类的推算出年代,说这种方法远比第一种方法复杂。

加试就不说了。

/ * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
* iBT:10 minutes break
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * /

休息时间是这样算的,考完听力,提示说有5秒内进入休息时间,然后开始倒计时,这时把证件拿出去前台放着就好了。
我跑出去把干粮吃了再上了个厕所就回去了。
吃得比较慢,但是想到模板已经写好了,就没所谓了,回去还剩2分多钟。
我是完全不打算偷题的,觉得没用。
一个小细节是,时间结束好貌似不会自动返回程序,因为有个工作人员过来帮我按ctrl+alt+del调出某窗口再输入密码才proceed的。

/ * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
* iBT:Speaking
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * /

之前阅读,听力挤了好多时间写模板orz。
听力做得一般般,my oral english sucks...
比较郁闷的是,做到一半时有个工作人员在后面看我 -_-#
不知是不是看到我写了满满一页纸的模板照着读在鄙视我呢……

1.一个自己记得的special event
我答的new year festival

2.喜欢与去过的地方还是没去过的地方旅游呢?
我答的去没去过的地方

3.
阅读:学校校报通知,computer lab的printer不再免费了,改成每次进去10页免费,后来的每页3cent(好像)。两个原因:一是节省,二是省下来的钱用来买新的打印机。
对话:两学生讨论,mm强烈支持,理由同上。

4.
阅读:information overload,说现代人太多东西干。两种解决方法,一是处理poportion,一是全部放下不管。
听力:教授举了两个例子,一是公司招人,但收到太多申请,因此只看一部分。而一个学者用email订阅了某个association的邮件,每星期一封推荐一些文章;但某次开始每天都推荐,学者看不完因此决定停看一星期。

5.
mm找到一个summer job,但又自己原来的公寓放在那又没用。gg建议说,一是找个人租出去;一是自己把两个公寓的钱都付了。mm说自己要省钱买电脑。

6.
教授介绍说在高山上植物是如何对抗恶劣环境的。
一是alpine shrub,长得很低,以防止大风。
二是moutain cramberry,叶子长vax以减少水分蒸发。

/ * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
* iBT:Writing
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * /

综合写作很简单,观点鲜明的驳斥。我写得比较多,300多字。个人比较比较害怕综合作文,练习得比较多。
短文说的是zoo的功能由以前的研究转为更强大的用途。
1是保护endangered species
2是提供给科学研究观察animal behavior的机会
3是提供为人们科普知识

驳斥:
1是根本保护不了,因为物种基因多样性太小,而且很可能有不好的基因积累。
2是根本观察不了,因为动物不是生活在正常的自然环境中,而是limited space。
3是人们去动物园根本不是为了学习,他说如果人们要去学习完全可以在自己家里DIY看科普材料。

独立写作,我想不出什么好的观点,只写了450字左右。如果平时有练习的话,时间是绝对够的(没怎么练习过,只大概看了看iBT作文满分的技巧,并写了大概10篇提纲就上场了……觉得这种东西按照模板来写还是很快的,我也不求要写得很牛B)。我打字比较快,20分钟就写完了。
支持反对型:
People will spend less time in cooking or preparing food in twenty years than nowadays.

以下供参考
1是客观原因,人们越来越忙(顺便把之前的information overload吹上去…… -.-),没有那么多时间去做,因此快餐店如KFC,M记盛行。
2是客观原因,科技发达,发明了很多帮助人们做菜的工具,如微波炉,做菜机器等,并且还会有新的机器发明。
3是主观原因,由于文化的交叉与渗入,人们会越来越喜欢出外吃饭,尝试不同的风味,如墨西哥餐,法式,泰式等。

作文剩下来的时间没必要continue,用来修改:
1是改句型,弄些倒装之类的
2是改单词,用些文绉绉的formal词语
3是改词法语法错误,主要是单复数,时态,拼写错误等。

/ * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
* 考试:离场
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * /

考完后不要立马走人,要举手等工作人员过来帮你确认。完事后去前台再让他确认下就可以滚蛋了。

出来后,有个工作人员在外面办理邮寄成绩单的事宜,广州本地14块,外省22块好像。

肚子饿,可以马上去外面吃饭,满大街的食肆,很好很强大。

也没什么很大的感觉,毕竟自己就只复习了两周……能上90分就开心死了,�。

/ * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
* 小小的总结
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * /

OG:
考前2天才看的,发觉真是太有用了。可惜没看完。
对着里面的介绍每题做一次,然后把练习也做一次。我认为,如果是只用1天复习的话,就一定是看OG莫属了。

delta:
口语和写作没做,觉得太偏,特别是综合作文,简直BT……

机经:
我只看了加试的机经,都碰到了,偷笑ing。可惜题目我觉得有点难度,跟加试机经描述好像有点出入。
因此我建议看机经一看考场介绍,二看考试技巧,三看加试就够了。(那我前面岂不是写了一堆垃圾……呵呵)
特别是加试,打印出来每天看一篇看到半夜被人叫醒一问也能背出来为止。

阅读与听力:
没特意去练,做了delta所有的阅读听力练习以及barron的两套test
delta的太简单,不过循序渐进可以供人熟悉题型,还是有必要做做以让自己熟悉题型的。
barron的练习不错,但是那个软件太垃圾,卡得要死。

口语:
这个我最怕了,不过在论坛上看到一个很有用的帖子,《破解IBT口语-23分并不难》,简直就是无敌。
http://bbs.gter.net/bbs/thread-690639-1-1.html
另外看了看OG的介绍。可惜只坚持了5天……

写作:
综合:觉得比较新颖,有重点练过。把某帖的8篇都写了。想发那帖的连接发觉找不到了……就是有8篇作文题目以及录音的,大家有兴趣可以找找……
独立:没练过……只看过《ibt满分作文》的关于185分类,以及每类的模板。另外就是写了大概10篇提纲这样子。

11.24.广州.白云山广外机经 by iveney

/ * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
* 前序:住宿篇
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * /

由于自己在大学城那边,做车过去保守估计要一个小时(可以做1路或者76路),而自己又是很怕坐车的人,因此提早了一天过去那边住顺便复习。
我住的宾馆是学生宿舍那边的柏豪酒店,单/双人房一样价钱,打折后180-200之间。我住过两次了,还不错,三星级的,而且很新,挺舒服,最主要是能上网。
我可以在那边很安静的复习,还能上网灌灌水 ^_^
由于是下午3点考的,我想睡个中午觉才出门,服务员也很好人地不给我算钟点房(一开始说1个小时30元),让我呆到两点才退房。

/ * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
* 考试:等待
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * /

考场是广外六教的B108室,离宾馆很近,就在学生宿舍3栋旁边。考虑到考试时间跨过我正常进餐时间,于是我买了一瓶红牛,一瓶牛奶和一个sandwich。
进场前喝了红牛提提神,等到两点半后,工作人员叫大家看自己的顺序编号,是按照姓名字母序排的,我排得很后,汗。接下来我们进入旁边的课室,写confidential statement。
写好后,开始按顺序入场。

这段时间是最郁闷的,本来不紧张的,呆久了就紧张了。进场速度很慢,非常慢,很多人都开始看书或聊天了。由于我是一个人,旁边的mm很pp又不好意思搭讪,坐在那不知干什么好。
我是最不喜欢考试前还狂看书的,但是后来实在闷得发慌,就拿出mp3来听一些lecture的录音。

/ * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
* 考试:进场
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * /

等了好久终于轮到我进场,乖乖地递上身份证和学生证(护照也可以,不过我没),阿姨扫了我两眼就进去了。
进去后先把东西放下,我随身带了一包纸巾和眼药水。然后拍照,拍完后工作人员把自己领到位置,就开考了。

/ * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
* 考试:环境介绍
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * /

这个考场环境很不错,很安静,唯一能听到的外界声音就是上下课的铃声。
房间有两个,从进场入口进去后,里面还有个门到隔壁的房间,我是在里面的房间考的。
座位周围有隔板,键盘,鼠标都很好,屏幕是15寸LCD,很舒服,可惜我不习惯LCD斜着放,平时我都是正对着用的,anyway,已经很好了。
有4张草稿纸,很好,笔是圆珠笔,不喜欢,个人比较喜欢铅笔。

开始考试后,工作人员帮你输入密码进入考试程序。
在确认了自己的身份还有一些繁琐的introduction之后就进入了阅读考试。

PS.一看那恶心的滚动条就知道是Java写的程序,~(-_-~)。
做的过程中有时会卡,但是时间不会算的,我猜可能是网络传输方面的延迟,看起来不像是程序的延迟?
好处是可以趁机看阅读文章,在next之前调好文章看~
另外口语答完题时也会有大概5-10秒的延迟,可能是压缩录音数据并传输,可以趁机舒缓心情。

/ * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
* iBT:Reading
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * /

阅读没有加试,我哭。

发觉不知是不是平时做题难的问题,觉得阅读比做练习要简单。
不过这个简单是局限在文章上的简单,题目的话感觉比barron稍难,起码就词汇题来说我不能秒杀。
发觉做阅读真的不需要看全文的,直接拖动滑动条到底然后continue,直接做题。
因为iBT的阅读出题基本上是按照段落顺序来出的,很少有段落会不问问题,因此在一边做题的同时就一边阅读了文章,省了不少时间。
当做到倒数第三题左右,基本上是已经读完全文了,这时做归纳题,总结题就方便很多了。

20分钟完成,我用了18分钟。
1.洞穴艺术,主要是介绍了远古人如何在洞穴里作画。第一段介绍原因,中间主体部分介绍了学者推断是大面积的作画,必须要靠不同的身体姿势,如趴着之类的来完成;另外由于洞内暗,要用灯光照,而颜料又快干,因此必须有助手。助手和画师都是训练有素的。最后一段忘了……

40分钟完成,这两篇好像比较简单,用了20来分钟就解决了,然后检查了一遍就顺便在草稿纸上默写口语模板……
2.蛇类动物的二叉舌头功能研究 。先是提出了某人的理论说是用来舔猎物味道进嘴里某器官,后来被科学家推翻,然后又有一个假设,被广泛接受。有4大supporting evidence,包括他们的感觉分别传入大脑中两个半脑以进行对比比较。其他忘了……最后把蛇,蜥蜴等的舌头的作用与其他动物的spatial感觉器官(类似耳朵)进行对比。

3.专利。看到题目我很兴奋,因为早上刚好做了一篇某阅读软件关于专利的阅读,叫"conquest by patent",有些细节还是一模一样的,嘿嘿。主要是按专利的发展,举了一些国家的专利的例子并指出优缺点。最后着重介绍美国的专利系统。


/ * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
* iBT:Listening
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * /

听力有加试,都是老题:(1)mm丢钱包 (2)神经glia cell (3)浪漫主义与新古典主义
但是我不知是不是题目与以前机经的不一样,因为mm丢钱包最后一题是问mm这句话什么意思
man: I'm glad I can help you
mm: You are glad.
问mm那句话什么意思。而机经里好像是说mm说"you help!"是什么意思。

另外,我觉得听力其实内容不难(我听了两个月的BBC/VOA/CNN news并坚持听写了一段时间的scientific american 60 second science,听力有明显提高,但是听到慢题会很烦,容易走神 -_-|||),但是题目比较难,很多题都不是那么明显的。barron里的听力好像比较长,听得我想睡觉,但是题目的选项区别比较明显,非常intuitive。
而iBT的选项还要经过一些推敲才能选,很多都不能确定。

还有,我没有看OG的listening题型,只做过delta的练习和barron的两个test。发觉有一种题型我没遇过,就是给出几个选项要选2个的。

以下不确保顺序正确

10分钟答题
1.mm宿舍的stove坏了去求助管理员,而管理员说不关他事叫mm找对面的单位,但mm说是那边叫过来的。管理员知道情况后说是电力供应问题,可能要下星期一甚至星期二才能好。mm很郁闷,因为她周末有party,她说好吧我可以推迟到下星期,管理员说为什么呢,你可以借你对面的来用,mm抱怨说那里太mess。管理员又建议说你可以用xxx活动室的,本来不给租但是现在特殊情况他会尽量帮mm申请,mm很高兴。
2.介绍人的情感与记忆的联系,这篇由于语速有点慢搞得我走神了。首先是说一个实验,给一堆图片让人记,结果active,negative记得最深,neutral的最差。而negative又比active效果好,有个学生介绍自己爬楼梯摔的经验,教授说对。然后说另一个实验,证明大脑不同区域对应不同情感,而其中的前庭脑(xxxfront的)跟创造力对应。然后说开心时时那里活动比较激烈,然后举了某个作家的例子。
3.两种类型的动物进食习惯 。一种是generalist,一种是specialist。第一种啥都能吃,如rat;第二种只吃固定的东西,如xxx动物(忘了),只吃某种树木的叶子,蛋白质少还有毒。然后对比了两种习惯的优劣,分别举了一些例子。如generalist中某种老鼠如果只能吃一种,他也会挑有营养的来吃。这个时候有学生问:xx为什么不吃其他东西以使自己选择广呢?教授反问:"xx说:我能得到什么?"固定吃这种树叶就完全足够了,因为这种东西别人不敢吃,有毒,而找其他东西还可能与别人竞争呢。

10分钟答题
1. 一男生要毕业了,找老师询问career问题。老师说自己以前也是很迷茫并take one year off,后来决定继续学习与读PhD。后来老师突然想起有个学生参加了某个program,叫gg去问那学生,那个program可以出国,又可以做老师之类的。
2.讲18-19世纪英国壁纸的发展。由于工业革命,涌现出了一些色彩鲜艳的壁纸,并且有大量的用人手做不出来的壁纸,另外由于某设备的出现,使得可以大量生产,价格降低。而一些reformer认为这是在show科技,而忽视了艺术价值。后来有一种xxx风格的,主要是在壁纸上画其他材质如树木,石头的图案以假乱真,受到reform大力批评。但是结果是,新科技生产的壁纸受到平民追捧,而reformer自己坚持有艺术价值的只出现在政府等高级机构中。
3.讲化石与地壳的年代鉴别。主要是两种方法,首先是相对法,给出了一幅grand canyon的图,基本根据是,一层一层的沉积岩中,年代新的比年代老的接近顶,然而也可能出现例外,因为由于地壳运动,老的会爬到新的上面去。然而根据这种方法只能大概估算出岩层属于大概哪一个时期,而不能算出具体时间段。后来介绍的是绝对方法,教授强调绝对是指相对与第一种方法而言的。利用放射元素法鉴定岩石成分半衰期之类的推算出年代,说这种方法远比第一种方法复杂。

加试就不说了。

/ * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
* iBT:10 minutes break
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * /

休息时间是这样算的,考完听力,提示说有5秒内进入休息时间,然后开始倒计时,这时把证件拿出去前台放着就好了。
我跑出去把干粮吃了再上了个厕所就回去了。
吃得比较慢,但是想到模板已经写好了,就没所谓了,回去还剩2分多钟。
我是完全不打算偷题的,觉得没用。
一个小细节是,时间结束好貌似不会自动返回程序,因为有个工作人员过来帮我按ctrl+alt+del调出某窗口再输入密码才proceed的。

/ * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
* iBT:Speaking
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * /

之前阅读,听力挤了好多时间写模板orz。
听力做得一般般,my oral english sucks...
比较郁闷的是,做到一半时有个工作人员在后面看我 -_-#
不知是不是看到我写了满满一页纸的模板照着读在鄙视我呢……

1.一个自己记得的special event
我答的new year festival

2.喜欢与去过的地方还是没去过的地方旅游呢?
我答的去没去过的地方

3.
阅读:学校校报通知,computer lab的printer不再免费了,改成每次进去10页免费,后来的每页3cent(好像)。两个原因:一是节省,二是省下来的钱用来买新的打印机。
对话:两学生讨论,mm强烈支持,理由同上。

4.
阅读:information overload,说现代人太多东西干。两种解决方法,一是处理poportion,一是全部放下不管。
听力:教授举了两个例子,一是公司招人,但收到太多申请,因此只看一部分。而一个学者用email订阅了某个association的邮件,每星期一封推荐一些文章;但某次开始每天都推荐,学者看不完因此决定停看一星期。

5.
mm找到一个summer job,但又自己原来的公寓放在那又没用。gg建议说,一是找个人租出去;一是自己把两个公寓的钱都付了。mm说自己要省钱买电脑。

6.
教授介绍说在高山上植物是如何对抗恶劣环境的。
一是alpine shrub,长得很低,以防止大风。
二是moutain cramberry,叶子长vax以减少水分蒸发。

/ * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
* iBT:Writing
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * /

综合写作很简单,观点鲜明的驳斥。我写得比较多,300多字。个人比较比较害怕综合作文,练习得比较多。
短文说的是zoo的功能由以前的研究转为更强大的用途。
1是保护endangered species
2是提供给科学研究观察animal behavior的机会
3是提供为人们科普知识

驳斥:
1是根本保护不了,因为物种基因多样性太小,而且很可能有不好的基因积累。
2是根本观察不了,因为动物不是生活在正常的自然环境中,而是limited space。
3是人们去动物园根本不是为了学习,他说如果人们要去学习完全可以在自己家里DIY看科普材料。

独立写作,我想不出什么好的观点,只写了450字左右。如果平时有练习的话,时间是绝对够的(没怎么练习过,只大概看了看iBT作文满分的技巧,并写了大概10篇提纲就上场了……觉得这种东西按照模板来写还是很快的,我也不求要写得很牛B)。我打字比较快,20分钟就写完了。
支持反对型:
People will spend less time in cooking or preparing food in twenty years than nowadays.

以下供参考
1是客观原因,人们越来越忙(顺便把之前的information overload吹上去…… -.-),没有那么多时间去做,因此快餐店如KFC,M记盛行。
2是客观原因,科技发达,发明了很多帮助人们做菜的工具,如微波炉,做菜机器等,并且还会有新的机器发明。
3是主观原因,由于文化的交叉与渗入,人们会越来越喜欢出外吃饭,尝试不同的风味,如墨西哥餐,法式,泰式等。

作文剩下来的时间没必要continue,用来修改:
1是改句型,弄些倒装之类的
2是改单词,用些文绉绉的formal词语
3是改词法语法错误,主要是单复数,时态,拼写错误等。

/ * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
* 考试:离场
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * /

考完后不要立马走人,要举手等工作人员过来帮你确认。完事后去前台再让他确认下就可以滚蛋了。

出来后,有个工作人员在外面办理邮寄成绩单的事宜,广州本地14块,外省22块好像。

肚子饿,可以马上去外面吃饭,满大街的食肆,很好很强大。

也没什么很大的感觉,毕竟自己就只复习了两周……能上90分就开心死了,�。

/ * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
* 小小的总结
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * /

OG:
考前2天才看的,发觉真是太有用了。可惜没看完。
对着里面的介绍每题做一次,然后把练习也做一次。我认为,如果是只用1天复习的话,就一定是看OG莫属了。

delta:
口语和写作没做,觉得太偏,特别是综合作文,简直BT……

机经:
我只看了加试的机经,都碰到了,偷笑ing。可惜题目我觉得有点难度,跟加试机经描述好像有点出入。
因此我建议看机经一看考场介绍,二看考试技巧,三看加试就够了。(那我前面岂不是写了一堆垃圾……呵呵)
特别是加试,打印出来每天看一篇看到半夜被人叫醒一问也能背出来为止。

阅读与听力:
没特意去练,做了delta所有的阅读听力练习以及barron的两套test
delta的太简单,不过循序渐进可以供人熟悉题型,还是有必要做做以让自己熟悉题型的。
barron的练习不错,但是那个软件太垃圾,卡得要死。

口语:
这个我最怕了,不过在论坛上看到一个很有用的帖子,《破解IBT口语-23分并不难》,简直就是无敌。
http://bbs.gter.net/bbs/thread-690639-1-1.html
另外看了看OG的介绍。可惜只坚持了5天……

写作:
综合:觉得比较新颖,有重点练过。把某帖的8篇都写了。想发那帖的连接发觉找不到了……就是有8篇作文题目以及录音的,大家有兴趣可以找找……
独立:没练过……只看过《ibt满分作文》的关于185分类,以及每类的模板。另外就是写了大概10篇提纲这样子。

Thursday, November 22, 2007

iBT教会了我有模板这样东西

iBT告诉我,原来八股文是最牛B的
iBT告诉我,原来口语于是有模板的

模板牛,模板秒,模板就是呱呱叫

--
Best wishes,
Yours, iveney
Department, of Computer Science,
Zhongshan University (Sun Yat-sen University),
Guangzhou, China

Wednesday, November 14, 2007

郁闷

11.24,决战。

--
Best wishes,
Yours, iveney
Department, of Computer Science,
Zhongshan University (Sun Yat-sen University),
Guangzhou, China

Tuesday, October 30, 2007

[zz]算法常用术语英中对照

Approximate String Matching 模糊匹配
Arbitrary Precision Arithmetic 高精度计算
Bandwidth Reduction 带宽压缩
Bin Packing 装箱问题
Calendrical Calculations 日期
Clique 最大团
Combinatorial Problems 组合问题
Computational Geometry 计算几何
Connected Components 连通分支
Constrained and Unconstrained Optimization 最值问题
Convex Hull 凸包
Cryptography 密码
Data Structures 基本数据结构
Determinants and Permanents 行列式
Dictionaries 字典
Discrete Fourier Transform 离散Fourier变换
Drawing Graphs Nicely 图的描绘
Drawing Trees 树的描绘
Edge and Vertex Connectivity 割边/割点
Edge Coloring 边染色
Eulerian Cycle / Chinese Postman Euler回路/中国邮路
Factoring and Primality Testing 因子分解/质数判定
Feedback Edge/Vertex Set 最大无环子图
Finite State Machine Minimization 有穷自动机简化
Generating Graphs 图的生成
Generating Partitions 划分生成
Generating Permutations 排列生成
Generating Subsets 子集生成
Graph Data Structures 图
Graph Isomorphism 同构
Graph Partition 图的划分
Graph Problems ― hard 图论-NP问题
Graph Problems ― polynomial 图论-多项式算法
Hamiltonian Cycle Hamilton回路
Independent Set 独立集
Intersection Detection 碰撞测试
Job Scheduling 工程安排
Kd-Trees 线段树
Knapsack Problem 背包问题
Linear Programming 线性规划
Longest Common Substring 最长公共子串
Maintaining Line Arrangements 平面分割
Matching 匹配
Matrix Multiplication 矩阵乘法
Medial-Axis Transformation 中轴变换
Median and Selection 中位数
Minimum Spanning Tree 最小生成树
Minkowski Sum Minkowski和
Motion Planning 运动规划
Nearest Neighbor Search 最近点对查询
Network Flow 网络流
Numerical Problems 数值问题
Planarity Detection and Embedding 平面性检测和嵌入
Point Location 位置查询
Polygon Partitioning 多边形分割
Priority Queues 优先队列
Random Number Generation 随机数生成
Range Search 范围查询
rate of convergence 收敛速度
robustness 鲁棒性
Satisfiability 可满足性
Searching 查找
Set and String Problems 集合与串的问题
Set Cover 集合覆盖
Set Data Structures 集合
Set Packing 集合配置
Shape Similarity 相似多边形
Shortest Common Superstring 最短公共父串
Shortest Path 最短路径
Simplifying Polygons 多边形化简
Solving Linear Equations 线性方程组
Sorting 排序
Steiner Tree Steiner树
String Matching 模式匹配
Text Compression 压缩
Topological Sorting 拓扑排序
Transitive Closure and Reduction 传递闭包
Traveling Salesman Problem 旅行商问题
Triangulation 三角剖分
Vertex Coloring 点染色
Vertex Cover 点覆盖
Voronoi Diagrams Voronoi图