首页 » 技术分享 » 【IT竞技、IT 峰会】

【IT竞技、IT 峰会】

 

ACM-Association for Computing Machinery , 即美国计算机协会.

ICPC-International Collegiate Programming Contest , 即国际大学生程序设计竞赛.

ACM国际大学生程序设计竞赛(英文全称:ACM International Collegiate Programming ContestACM-ICPCICPC)是由美国计算机协会(ACM)主办的,一项旨在展示大学生创新能力、团队精神和在压力下编写程序、分析和解决问题能力的年度竞赛。经过近30多年的发展,ACM国际大学生程序设计竞赛已经发展成为最具影响力的大学生计算机竞赛。

  竞赛的历史可以上溯到1970年,当时在美国德克萨斯A&M大学举办了首届比赛。当时的主办方是the Alpha Chapter of the UPE Computer Science Honor Society。作为一种全新的发现和培养计算机科学顶尖学生的方式,竞赛很快得到美国和加拿大各大学的积极响应。1977年,在ACM计算机科学会议期间举办了首次总决赛,并演变成为目前的一年一届的多国参与的国际性比赛。迄今已经举办了34届。

  最初几届比赛的参赛队伍主要来自美国和加拿大,后来逐渐发展成为一项世界范围内的竞赛。特别是自1997IBM开始赞助赛事之后,赛事规模增长迅速。1997年,总共有来自560所大学的840支队伍参加比赛。而到了2004年,这一数字迅速增加到840所大学的4109支队伍并以每年10-20%的速度在增长。

  1980年代,ACM将竞赛的总部设在位于美国德克萨斯州的贝勒大学。

  在赛事的早期,冠军多为美国和加拿大的大学获得。而进入1990年代后期以来,俄罗斯和其它一些东欧国家的大学连夺数次冠军。来自中国大陆的上海交通大学代表队则在2002年美国夏威夷的第26届和2005年上海的第29,2010年哈尔滨的34届全球总决赛上三夺冠军。这也是目前为止亚洲大学在该竞赛上取得的最好成绩。赛事的竞争格局已经由最初的北美大学一枝独秀演变成目前的亚欧对抗的局面。

  ACM-ICPC以团队的形式代表各学校参赛,每队由3名队员组成。每位队员必须是在校学生,有一定的年龄限制,并且最多可以参加2次全球总决赛和5次区域选拔赛。

  比赛期间,每队使用1台电脑需要在5个小时内使用CC++Java中的一种编写程序解决710个问题。程序完成之后提交裁判运行,运行的结果会判定为正确或错误两种并及时通知参赛队。而且有趣的是每队在正确完成一题后,组织者将在其位置上升起一只代表该题颜色的气球。

  最后的获胜者为正确解答题目最多且总用时最少的队伍。每道试题用时将从竞赛开始到试题解答被判定为正确为止,其间每一次提交运行结果被判错误的话将被加罚20分钟时间,未正确解答的试题不记时。例如:AB两队都正确完成两道题目,其中A队提交这两题的时间分别是比赛开始后1:002:45B队为1:202:00,但B队有一题提交了2次。这样A队的总用时为1:00+2:45=3:45B队为1:20+2:00+0:20=3:40,所以B队以总用时少而获胜。
==============================================================

ACM-ICPC比赛随想(清华大学 刘汝佳)

刘汝佳,198212月生,毕业于重庆外国语学校,清华大学计算机科学与技术系2005级研究生。高二时创立信息学初学者之家网站 OIBH),高三入选IOI2001国家集训队。大学一年级时获ACM/ICPC世界总决赛银牌(世界第四),IOI2002/03/04国家集训队指 导老师。曾与黄亮合作出版了《算法艺术与信息学竞赛》丛书,自2002年至今为科学委员会学生委员,在命题方面和辅导学生方面成绩突出,同时兼任NOI 站总监。

从第一次听说ACM/ICPC到现在,已经有快七个年头了。最开始因好奇而关注,而现在因了解而关注——关注比赛,更关注参加比赛的人。ACM/ICPC 是一个五味瓶。没有接触过它的人不会知道其中的酸甜苦辣,而一旦置身其中,每个选手都会对它产生一种特殊的感情,时间越长,这种感情也越复杂、越浓烈。感 情来源于对算法与题目的喜爱,来源于对成功的向往和失败的恐惧,来源于各种选择与放弃中的徘徊与摇摆不定,来源于程序世界与现实生活的巨大差异,也来源于 通往理想的曲折道路——探索其中时的无助和艰辛。等到退役的那一天,回过头来再看当时的自己,相信每位选手都会发现自己的很多方面成熟了许多——远不只是 编程能力和算法功底。以前我觉得这是比赛的副产品,而现在我认为这才是比赛的主要目的,至少对于选手自己是如此。

虽然我从心里喜欢这个比赛,但我并不鼓励每个人参加。并不是每个人在每个时期都适合参加这个比赛,且适合的人选也并不代表一定能取得好成绩——比赛场上是 没有一定的,任何一个选手都必须有勇气承担风险,就像所有其他有潜在回报的事一样。另一方面,对于所有下定决心参加比赛的选手,我鼓励他坚持到底,因 为只有这样才会受到真正的磨练。在参加不参加的岔路口上,大多数选手被两个问题所困绕。第一个是我能获奖么?奖会给我带来什么好处?,第二 个是抛开荣誉,从比赛中学到的东西值得我花费这么多时间吗?。第一个问题我无能为力,也不愿意回答,因为这取决于很多复杂的因素。而这些因素,更多的 要靠自己把握。而对于第二个问题,我可以毫不犹豫的说:答案是肯定的,但前提是要视野开阔,不要把自己局限在一个狭小的空间之内。大家都知道, ACM/ICPC竞赛要求选手在理论上具有一定的知识和能力、编程上要求速度和正确性,但我认为更重要的一点是:ACM/ICPC培养选手实践能力和洞察 力。这两点相对于理论和技术本身而言更难培养,也是高素质人才更需要的。这里的实践能力因追求生产效率和创造性而显著区别于依葫芦画瓢型的体力式的技术 能力,而洞察力让有心的选手往各方面发展,让自己的才能展现到计算机科学、自然科学乃至艺术、人文方面的各个角落。一位MIT教授曾在课上对学生说:从 某种意义下,计算机科学不是关于计算机的,它也不是一门科学。对于这样一个开放型事物,如果能够用洞察力寻找方向,用效率和创造性开辟道路,发展空间将是 巨大的。

我的选手生涯是短暂的。三年半前夏威夷总决赛回来以后虽然有些不甘心,但我从心理上已经不再用选手的标准来要求自己了。随后在完成《算法艺术与信息学 竞赛》的日子中,我的思维方式渐渐转向了教练和命题者,虽说少了比赛时的激情,但能更加理智和清醒的看待问题了。那本书是我正式出版的第一本著作,一个各 种思想、知识、资源的复杂编织体,虽然有诸多遗憾,但是真实的反映了写作当时我的状态,相信不同动机和立场的人阅读时会有不同的感想和认识。竞赛的题目有 着统一的外观,但它们背后的东西包罗万象。这些相关的知识都有着很强的应用背景,而非专门为竞赛而设计,因此有着独立的体系和相应的文献。程序设计语言、 数据结构、算法设计方法、计算理论等内容都是经典的计算机科学分支,而高等数学、数论、组合数学、概率论、图论、组合游戏论、人工智能、计算几何、计算机 图形学、生物信息学等内容也常见于各类竞赛中。虽然这些学科只有一小部分内容目前已经在题目中出现,但是对这些小部分知识的理解和实践将十分有利于对 这些学科进行更全面、深入的学习。对任何知识的学习都离不开三方面:理论、模型和实现。理论部分相对容易把握,但要求学习时一丝不苟,善于总结、抓住本 质。主要培养选手的洞察力;模型部分比较灵活,富有创造性,不管是模型的建立还是求解,都需要大量积累和思考。这也是最有启发性的部分,主要培养选手的创 造力。实现部分比较自由,也是个人风格的体现,很难有一个固定的标准,但有很多前人经验和模式可以遵循。这部分有很多其他资料可以参考,也属于实践性最强 的部分,主要培养选手的效率(当然也包括正确性。没有正确性就谈不上有效率)。有了前面的宏观叙述,这三方面孰轻孰重、关系如何,自然就很明了了。

对于大多数人来说,ACM/ICPC只是生命中一个很小的部分,但每一位有心的人都可以把这段经历变得重要而有价值。准备ACM/ICPC的日子是一段麻 醉期,很多平时在意的时候都可以在准备竞赛时置之不理,也不去过多的考虑未来可能来临的烦恼。思想最单纯的时候做事是最有激情最快乐的,而在这样的时期, 与志同道合的人建立的友情也是最可贵的。不管曾经、正在或者即将面临多大困难和艰辛,也不管结果如何,我想把一句话送给关注ACM/ICPC的每一个人: “ACM/ICPC is healthy, just do it.”

==========================================================================

浙江大学获ACM-ICPC World Finals 2011冠军

在美国当地时间2011530下午2时结束的第35ACM国际大学生程序设计竞赛全球总决赛中,浙江大学荣获全球总冠军,美国的密歇根大学Ann Arbor分校获得第二,清华大学获第三。

被誉为计算机领域奥林匹克竞赛ACM国际大学生程序设计大赛,是世界上规模最大、历史最长、最具影响力的大学生国际级计算机类赛事。竞赛由国际计算机界历史悠久、颇具权威性的组织ACM学会即美国计算机协会主办,旨在使大学生运用计算机来充分展示自己分析问题和解决问题的能力。

比赛中,各大学以团队形式参赛,每队由3名队员组成。每队只能使用1台电脑,5个小时内用CC++Java中的任意一种程序语言编写程序,解决11个问题。最后的获胜者为正确解答题目最多且总用时最少的队伍。

今年第35ACM/ICPC总决赛在美国佛罗里达州的奥兰多举办,共有来自30多个国家和地区的105支队伍300余名世界各大学计算机精英汇聚奥兰多比拼才智。这些队伍是从来自全世界88个国家的2070个大学的8305个队伍中经过层层选拔,最终晋级世界总决赛。

以下是浙江队人员名单:

教练:王灿

选手:莫璐怡 欧阳嘉林 巫泽俊

PlaceNameSolvedTimeLast solved1Zhejiang University812282902University of Michigan at Ann Arbor814622913Tsinghua University7800218

4St. Petersburg State University78932805Nizhny Novgorod State University79382736Saratov State University7966272

7Friedrich-Alexander-University Erlangen-Nuremberg710882888Donetsk National University711552899Jagiellonian University in Krakow71176287

10Moscow State University7118727611Ural State University7134529612University of Waterloo71555279

13Taurida V.I. Vernadsky National University6  13National Taiwan University6  13University of Warsaw6  13St. Petersburg State University of IT, Mechanics and Optics6  13Nanyang Technological University6  

13Universidad de Buenos Aires - FCEN6  13Korea Advanced Institute of Science and Technology6  13Peking University6  13Sharif University of Technology6  13Carnegie Mellon University6  

13Shanghai Jiao Tong University6  13Lviv National University6  13The Chinese University of Hong Kong6  13Zhongshan (Sun Yat-sen) University6  27University of Electronic Science and Technology of China5  

27Taras Shevchenko Kiev National University5  27Massachusetts Institute of Technology5  27Belarusian State University5  27Universidade Federal de Pernambuco5  27University of Tokyo5  

27South Ural State University5  27Kazakh-British Technical University5  27Perm State University5  27Kyoto University5  27Novosibirsk State University5  

27Fudan University5  27Harbin Institute of Technology5  27Tianjin University5  27University of Helsinki5  42Universidade Federal do Paraná4  

42Moscow Institute of Physics & Technology4  42Wuhan University4  42Universidade de S?o Paulo - Escola Politécnica4  42Princeton University4  

42Universidade de S?o Paulo - Instituto de Matemática e Estatística4  42International Institute of Information Technology - Hyderabad4  42East China Normal University4  42Universidad Nacional de Córdoba - FaMAF4  42University of Alberta4  

42Seoul National University4  42Swiss Federal Institute of Technology Zurich - VIS4  42Beijing Jiaotong University4  42Indian Institute of Technology - Delhi4  42University of Wroclaw4  

42University of Stellenbosch4  42Pontificia Universidad Católica del Perú4 

 

2010 ACM/ICPC总决赛结束 上海交通大学获得冠军

俄罗斯大学获第32ACM国际大学生程序设计大赛冠军 清华第六

北京时间410日早消息,32ACM国际大学生程序设计大赛(以下简称“ACM大赛”)全球总决赛于加拿大当地时间49日下午揭晓,俄罗斯圣彼得堡IT、机械和光学大学在100个参赛队中脱颖而出,获得全球冠军。清华大学以第六名的成绩获得银牌,创下此次18个中国参赛队的最好成绩。

俄罗斯圣彼得堡IT、机械和光学大学获得第32ACM大赛冠军

清华大学队教练邬晓钧、队员王栋、唐文斌、龙凡及教练吴文虎

  此次俄罗斯大学表现极为抢眼,在12强中,有5名来自俄罗斯,显示出俄罗斯军团的强大实力。尽管此次中国参赛队阵容庞大,共有上海交通大学、清华大学、国立台湾大学及香港中文大学等18所大学进入总决赛,但只有清华大学一家进入12强。曾在20022005年两度夺得全球冠军的上海交通大学此次并列第13名。

  此次清华大学代表队的三名队员均为计算机系本科生,分别是大二学生龙凡、唐文斌,及大一新生王栋。龙凡及唐文斌去年曾参加过ACM比赛。担任教练的清华大学计算机系教授吴文虎表示,此次队员们发挥正常,比赛期间的心态也非常好。吴教授透露,清华大学参加ACM大赛以来,连续11年进入总决赛,表现一直较为稳定。教练邬晓钧博士也表示,学生们都比较重视享受比赛的过程,而不只是比赛结果,学校也不会为了参赛而打乱各个系对学生的培养计划。

  此次全球总决赛设立了11个高难度编程问题,这些问题均以真实环境下的商业难题为原型,旨在考察参赛者的知识、耐力和商业敏感性,竞赛时间限定为五小时,各参赛队伍需要在这短短数小时内展示出其在一个学期中所学的知识和技能,优胜者将是那些在最短时间内以正确方式解决最多问题的参赛队。

  ACM大赛由美国计算机协会(ACM)主办,一项旨在展示大学生创新能力、团队精神和在压力下编写程序、分析和解决问题能力的年度竞赛。经过近30多年的发展,ACM国际大学生程序设计竞赛已经发展成为最具影响力的大学生计算机竞赛。

  最初几届比赛的参赛队伍主要来自美国和加拿大,后来逐渐发展成为一项世界范围内的竞赛。特别是自1998IBM成为赞助商后,赛事规模增长迅速。今年共有来自83个国家1821所院校的6700多支参赛队参加了秋季区域预选赛,最终有100个参赛队进入总决赛。 

  总冠军

  俄罗斯圣彼得堡IT、机械和光学大学

  金牌

  第二名:美国麻省理工大学

  第三名:俄罗斯伊热夫斯科州立科技大学

  第四名:乌克兰利沃夫国立大学

  银牌

  第五名:俄罗斯莫斯科州立大学

  第六名:清华大学

  第七名:美国斯坦福大学

  第八名:克罗地亚萨格勒布大学

  铜牌

  第九名:加拿大滑铁卢大学

  第十名:俄罗斯彼得罗扎沃茨克州立大学

  第十一名:俄罗斯圣彼得堡大学

  第十二名:白俄罗斯州立大学

  中国参赛大学得分榜:

  清华大学                 6               解答7个问题
  复旦大学                并列第13       解答6个问题
  上海交通大学         并列第13       解答6个问题
  北京大学                并列第13       解答6个问题
  中山大学               并列第23       解答5个问题
  国立台湾大学         并列第31       解答4个问题
     浙江大学                并列第31       解答4个问题
  香港中文大学          并列第31       解答4个问题
  中国电子科技大学   并列第31       解答4个问题
  山东大学                 并列第47       解答3个问题
  北京交通大学          并列第47       解答3个问题
  天津大学                 并列第47       解答3个问题
  国防科技大学          并列第47       解答3个问题 

===================================================

中国高校ACM-ICPC 历届获奖情况(第1届~第34届)

年份/总决赛/地点/冠军/大学/国家

342010中国哈尔滨上海交通大学中国

332009瑞典斯德哥尔摩圣彼得堡大学信息、机械和光学系俄罗斯

322008加拿大Banff圣彼得堡大学信息、机械和光学系俄罗斯

312007日本东京华沙大学波兰

302006美国得克萨斯州 Saratov国立大学俄罗斯

292005中国上海上海交通大学中国

282004捷克布拉格圣彼得堡精密机械和光学学院俄罗斯

272003美国洛杉矶华沙大学波兰

262002美国夏威夷上海交通大学中国

252001加拿大温哥华圣彼得堡州立大学俄罗斯

242000美国奥兰多圣彼得堡州立大学俄罗斯

231999荷兰埃因霍温滑铁卢大学加拿大

221998美国亚特兰大查尔斯大学捷克

211997美国圣何塞哈维玛德大学美国

201996美国费城加州大学伯克利分校美国

191995美国纳什维尔阿尔伯特-爱因斯坦大学德国

181994美国菲尼克斯滑铁卢大学加拿大

171993美国印第安纳波利斯哈佛大学美国

161992美国堪萨斯城墨尔本大学澳大利亚

151991美国圣安东尼奥斯坦福大学美国

141990美国华盛顿奥塔哥大学纽西兰

131989美国刘易斯维尔加州大学洛杉矶分校美国

121988美国亚特兰大加州理工学院美国

111987美国圣刘易斯斯坦福大学美国

101986美国辛辛那提加州理工学院美国

 091985美国新奥尔良斯坦福大学美国

 081984美国费城约翰霍普金斯大学美国

 071983美国墨尔本内布拉斯加大学美国

 061982美国印第安纳波利斯贝勒大学美国

 051981美国圣刘易斯密苏里-罗拉大学美国

 041980美国堪萨斯城华盛顿大学圣刘易斯分校美国

031979美国华盛顿大学圣刘易斯分校美国

 021978美国底特律麻省理工学院美国

 011977美国亚特兰大密歇根州立大学美国 

      

 IBM赞助、哈尔滨工程大学承办的第三十四届美国计算机协会(ACM)国际大学生程序设计大赛(ICPC)全球总决赛201025日在哈尔滨成功举行,最终中国的上海交通大学代表队摘取了此次ACM大赛世界冠军。

  来自全球顶尖大学的103支参赛队伍参加了素有脑力大赛”("The Battle of the Brains")之称的ACM-ICPC 全球总决赛,他们通过使用开放标准技术进行软件设计,以解决仿真环境下的商业难题。每支参赛队伍由三名学生组成,他们需要解决11个不同难易程度的问题。总决赛设计的问题围绕IBM“智慧的地球愿景,根据现实世界中的真实问题而设计,例如,预报飓风或海啸带来的大量降水将会造成的影响。在短短五个小时内,学生们需要解决的计算机编程问题远远超过其在一个学期所学的内容。

  评委根据在最短时间内正确解决的问题数量来评判各参赛队的名次,上海交通大学成功地解决了7个问题,获得金奖和第一名。世界冠军们将获得由IBM 提供的奖品、奖学金和最高智慧奖杯,此外他们还将获得在IBM 工作或实习的机会。

  IBM 软件集团战略总监兼ICPC 赞助主管Doug Heintzman 先生表示:随着IBM‘智慧的地球举措的不断推进,借助新兴技术改善日常生活的可能性明显提升。今年获得全球总决赛资格的学生们,日后都将成为努力推进创造、发展和实施技术进步的领军人物。

  在ACM-ICPC竞赛期间还举办了全球技术展示,这为学生们提供了亲身体验新兴技术的机会,这将有利于催生新的创意,并为他们今后的职业生涯奠定基础。

  ICPC执行总监、美国贝勒大学(Baylor University)教授Bill Poucher博士表示:这些学生都是各自所属领域的顶尖人才,拥有解决当今世界最严峻问题的潜力。ACM-ICPC为他们提供了一个平台,使他们有机会在IBM等需要新型人才的顶尖企业面前展示才华,从而获得更多最优秀的工作机会。

  莫斯科国立大学、台湾大学、基辅塔拉斯-谢甫琴科国立大学分别赢得了比赛的第二、第三和第四名,他们都获得了金牌以及在IBM的正式工作。

  地区冠军分别是:斯坦福大学(北美地区)、莫斯科国立大学(欧洲地区)、英国大学埃及分校(非洲和中东地区)、巴西伯南布哥联邦大学(拉美地区)、上海交通大学(亚洲地区)和澳大利亚西澳大学(南太平洋地区)

  今年获得奖牌的前十二支参赛队伍是:

   上海交通大学,(金牌,世界冠军)     郑曌、吴卓杰、金斌

我们三个各有所长,吴卓杰比较沉稳,技术全面,而金斌写代码特别快。队长郑曌说,比赛时分工也很讲究,一些复杂冗长的代码就请吴卓杰完成,而需要速度的时候就让金斌显身手。郑曌是主心骨,负责分配任务并作决断。)

   莫斯科国立大学,(金牌,第二名)

   台湾大学,(金牌,第三名)

   基辅塔拉斯-谢甫琴科国立大学,(金牌,第四名)

   俄罗斯国立彼得罗扎沃茨克大学,(银牌,第五名)

   清华大学,(银牌,第六名)

  俄罗斯国立萨拉托夫大学,(银牌,第七名)

  波兰华沙大学,(银牌,第八名)

   俄罗斯圣彼得堡国立大学,(铜牌,第九名)

   中山大学,(铜牌,第十名)

   复旦大学,(铜牌,第十一名)

   瑞典皇家理工学院,(铜牌,第十二名)

  此次参加哈尔滨全球总决赛的103支队伍是从来自六大洲82个国家1,931所大学的7,109支参赛队中选拔产生的。从1997IBM开始赞助此项赛事以来,比赛规模不断扩大,如今参赛人数已经增加了800%

       ACM大赛分区域预赛和国际决赛两个阶段进行。竞赛涵盖范围广泛,包括简单题、计算几何、数论、组合数学、搜索技术、动态规划、图论等很多内容。

 ==============================================

34 (上海交通大学:郑曌、吴卓杰、金斌)

29 (上海交通大学:戴文渊、赵爽、杨博海)

26 (上海交通大学:周健、陆靖、林晨曦)阿里巴巴同事:王坚和林晨曦

     (周健:ACM比赛不仅仅是编程能力的一个比赛,更是一个团队之间的竞争。所以,除了要着重提高自己的数据结构和算法能力,还需要在训练中注重队友之间的配合,比如互相熟悉对方的代码,这样在比赛时就能够帮助对方差错,比如说要训练互相讲题,减少沟通失误,这样在比赛时就能够节省读题的时间,等等。配合的方法还可以有很多种,原则就是能够使的一道题从读题,想算法,编程,改错的各个环节都能够有第二个人顶上去,这样就不至于由于一个人状态不好,导致整场比赛皆输。 

     (陆靖:说实话,我可能没有特别多的经验可以谈。我觉得,ACM比赛的重要特征之一就是重视团队合作。尽管个人的解题能力是比赛的基础,但仅凭个人的能力在ACM比赛中能取得的成绩总是有限的。所以,我觉得除了提高个人的编程能力以外,在团队的合作方式上下功夫可能是能在短时期内提高队伍整体的成绩的近路。比如,在比赛前期3个人合作尽快确定整套题的难度分布,找到应该先解决的简单题。在中期,队友之间可以利用打印的程序互相为对方的程序debug,来节约使用电脑的时间。在后期,可以利用队友解其他题的时间对难题进行充分的准备以后再上机编程。在这个过程中,需要的能力可能包括队友之间针对题目描述、内容的高效、准确地交流(做题目的人可能最初不是自己读题目的人)。也包括,比如,熟悉队友的程序的编程风格等等。 

===================================================================================

热烈庆祝浙大ZodiacACM/ICPC世界总决赛中勇夺银牌 2009

世界第六,亚洲亚军,获得银牌一枚
cong!!!
顺便也恭喜一下清华和华南理工,分别拿到了金牌和铜牌,呵呵

附名单:
发信人: SoariEz (SoariEz), 板面: Algorithm
  : Results World Finals
发信站飘渺水云间 (Wed Apr 22 00:16:35 2009), 转信

---------------------------------------------------------------------------------------------------------------

复旦大三生证明世界级猜想 攻克十年无解问题

记者昨天从复旦大学获悉,该校计算机学院大三学生郭泽宇关于最小曼哈顿网络问题的论文被第25届计算几何国际会议录用,文章同时作为最佳论文之一被邀请投稿到会议特刊DiscreteandComputationalGeometry(DCG)。这意味着计算几何领域十年来的重要猜想被这位年仅20岁的本科生成功解决。 

  据悉,计算几何国际会议是计算几何领域最高级别的会议,这一会议,中国内地数学家已经阔别了整整十八年。 

  20086月,郭泽宇申请了复旦大学本科生学术研究资助计划的李政道基金项目。最小曼哈顿网络问题是计算机学院朱洪教授给自己指导的本科生们所开设的题目,该课题在城市规划、网络路由、大规模集成电路设计以及计算生物学等众多领域有着很好的应用前景。不过自曼哈顿网络的复杂度问题于1999年提出至今,没有人知道问题的答案,从而使得对这一问题的研究成为计算几何中最为重要的几个未解决问题之一。郭泽宇大胆地选择了这一问题作为项目攻克对象。这既让朱洪教授和博士研究生孙贺这两位项目指导老师感到欣喜,也让“ 学者评审专家们捏了一把汗。基于鼓励本科生创新和支持年轻人闯劲的考虑,郭泽宇最终得到了资助。经过200多个日夜的思考和探索,这一难题终于被他找到突破口。 

  在郭泽宇的项目申请书中,中国科学院院士陆汝钤作为推荐老师,对本科生学术研究资助计划给予了充分的肯定,他认为通过这一方式使许多学生脱颖而出,走上了从事科学研究的道路。记者了解到,1998年,在李政道先生倡导和设立的政基金支持下,复旦大学开始开展资助优秀本科学生尽早接触学术研究的计划,并逐渐形成了一个层次分明、申请时间灵活、申请形式多样的本科生学术研究资助平台,即复旦大学本科生学术研究资助计划。 

  从1998年到2008年,共有1556位学生获得资助开展研究,其项目学科涵盖了医学、工学、理学、文学、教育学等多个领域。另据不完全统计,在2008年,参加复旦大学本科生学术研究资助计划资助项目的同学在国内外期刊发表论文30篇,其中第一作者文章20篇。

 =============================================================

发信人: sunmoonstar (摔锅啦), 信区: ACM_ICPC 
  : [公告] 2008北京大学校赛获奖名单 
发信站: 北邮人论坛 (Wed May 28 16:48:15 2008), 站内 
  
看来你们周六周日都要往北大跑了。 
  
颁奖仪式时间地点通知:  
5
31日(星期六)晚上7  
北京大学理科2号楼2736颁奖厅 
  
http://acm.pku.edu.cn/pku2008/
http://acm.pku.edu.cn/pku2008/resource/获奖名单.xls 
  
排名                队名                  解题数     学校     
01   Pipalu:
唐文斌,郭华阳,王栋            9        清华     
02   Eccentric:
陈彦卿,陈峰宏,王靖           9        北大信科     
03   Excalibur:
秦腾,姚金宇,雷涛             8        北大信科     
04   imba:
娄天禺,辜斯缪,王永亮            6        交大     
05  
贾由,姜子麟,申栋材                     6        北大元培     
06   OneMoreTry:
臧家瑞,温翔,冯天骁          6        北大信科     
07  
贾振东                                 6        北大物院     
08   ZH:
黄劲松,周航,罗睿辞                  6        北大信科     
09   :
王可斌,蒋威,伍逸煊             5        北大信科     
10   Rainer:
张棋                            5        北大信科     
11   Bupt1:
曹超杰,向旻,刘一洲             5        北邮    
12   ACACAC:
钱昊,金鑫,李昂                  5        北大信科     
13   TJU-TeamA:
卢旭,徐瑞涛,张敏琪         5        天津大学     
14    ICE:
刘晓恺,赵真龙,魏文哲              5    北大数院     
15    Spirit:
郑泽宇,李天翼,冯浩             4    北大信科     
16    BTeam:
张嘉琳,邹佳辰,郭浩泉          4    北航     
17    Zealot:
杨浩,王泽亮,黄群               4    北大信科     
18    FivexThree:
张宇,刘金宝,颜乐驹         4    北大信科     
19    OICQ:
顾森,雷淼,余昊男                 4    北大中文     
20    bitcats:
范敬凡,张达,李外            4    北理工     
21   
鲁鲁西:潘昊,闫丰润,王小龙             4    北大信科     
22   
此队无熊:陈醒,吴轲,陆顾婧             4    北大信科     
23    Z3:
朱诗雄,张韧,张东颖                 3    北大元培     
24    Sentinel:
丁珂,李井,曲直               3    北大信科     
25    ZWCbest:
张宇识,王绍迪,陈静超          3    北大信科     
26    Cis Rookies:
李博,薛业翔,斯文骏        3    北大信科     
27    TriSwordsmen:
怀宾,蔡斌,程安来       3    宁波理工     
28    Dream:
黄柏彤,李森,张晓东              3    北大信科     
29    xjr:
汪瑜婧,郭英龙,田昊枢              3    信科数院     
30    OneOneOne:
陈科吉,梁博文,陈培          3    北大信科     
31   
糯米丸子:钱梦仁,汤元超,顾张磊         3    北大信科     
32    BNU_1:
龚治,易超,林子敏              3    北师大     
33    Giant-killer:
张辰飞,朱星炜,杨明       3    北大信科     
34    Knight:
杨挺,钟诚,俞毓锋               3    北大信科     
35    newHope:
王皓玉,王峰波,王锦鹏        2    地大     
36   
快乐三人行:梁诗鸣,张顺廷,陈巍         2    北大信科     
37    TJU-TeamB:
杨晨豪,邱侠斐,王晓宁      2    天津大学     
38    DoubleTriangle:
冯霁,常好哲,王海栋     2    南开     
39    Magic3:
张伟良,裴国东,李海龙           2    软件学院     
40    TIHS:
丁羽,                            2    北大信科     
41    Kingdom of Kings:
王宇昕,金鑫,蒲敬     2    北大信科     
42    C++Primer:
李龙,于弢,陈瑜              2    北大信科     
43   
三阶有向图:邓瑞伶,徐可,顾从云         2    北大信科     
44    Three Suns:
李雁章,吴沛文,李怡文       2    北大信科     
45    POJ Hunter:
陈政,杨昊哲,赵树娟         2    北大信科     
46    Little_nick:
马晓乐,马舒浩,雒佳俊      2    北大信科     
47    RUO:
李政宇,谢全,王昊                  2    北大信科     
48    ZDL:
张敏林,戴少阳,栾添                2    北大信科     
49    SunSon:
向永清,高运凯,方彬             2    北大信科     
50    NKfresh:
叶时炜,毛旭东,杨建祥          2    南开     
51    Miles:
林嘉怡,张雨萌,康迪              2    北大信科     
52    LHJ_elephant_player:
李辰,黄舒志,金庸  2    北大信科     
53    Temp:
宋恒,乔衎,任斐                   2    北航     
54    WHY:
王骏成,黄福青,张东扬              2    北大信科     
55    Bupt4:
洪定乾,王坤山,曾魁              2    北邮     
56    PMS:
邢雪源,武嘉怡,苟瑞                2    北大信科     
57    challenging:
王旭,薛潇博,邱林          2    北大信科     
58    ALAC:
罗海鹏,马郓,王晗                 2    北大信科     
59    x.i.u:
胡薇,沈才立,方仙法              2    北大信科     
60    Bupt2:
宋子寅,虞里杉,薛阳阳            2    北邮     
61    Running way:
孙军渭,张笑阳,陈琛        2    北大信科

======================================================

   排名                                    解题数               学校     
一等奖  

     1    Pipalu:唐文斌,郭华阳,王栋        9                  清华     
     2    Eccentric:
陈彦卿,陈峰宏,王靖       9                  北大信科     
     3    Excalibur:
秦腾,姚金宇,雷涛         8                  北大信科    
二等奖 

     4    imba:娄天禺,辜斯缪,王永亮        6                  交大     
     5    
贾由,姜子麟,申栋材                6                  北大元培     
     6    OneMoreTry:
臧家瑞,温翔,冯天骁      6                  北大信科     
     7   
贾振东:贾振东                      6                  北大物院     
     8    ZH:
黄劲松,周航,罗睿辞              6                  北大信科     
     9    :
王可斌,蒋威,伍逸煊         5                  北大信科     
     10    Rainer:
张棋                       5                  北大信科     
     11    Bupt1:
曹超杰,向旻,刘一洲        5                  北邮     
     12   ACACAC:
钱昊,金鑫,李昂              5                  北大信科     
     13 TJU-TeamA:
卢旭,徐瑞涛,张敏琪       5                  天津大学     
     14  ICE:
刘晓恺,赵真龙,魏文哲            5                  北大数院     
 
三等奖   

     15    Spirit:郑泽宇,李天翼,冯浩         4                  北大信科     
     16    BTeam:
张嘉琳,邹佳辰,郭浩泉      4                  北航     
     17    Zealot:
杨浩,王泽亮,黄群           4                  北大信科     
     18    FivexThree:
张宇,刘金宝,颜乐驹     4                  北大信科     
     19    OICQ:
顾森,雷淼,余昊男             4                  北大中文     
     20    bitcats:
范敬凡,张达,李外        4                  北理工     
     21   
鲁鲁西:潘昊,闫丰润,王小龙         4                  北大信科     
     22   
此队无熊:陈醒,吴轲,陆顾婧         4                  北大信科     
     23    Z3:
朱诗雄,张韧,张东颖             3                  北大元培     
     24   Sentinel:
丁珂,李井,曲直            3                  北大信科     
     25  ZWCbest:
张宇识,王绍迪,陈静超        3                  北大信科     
     26  Cis Rookies:
李博,薛业翔,斯文骏      3                  北大信科     
     27  TriSwordsmen:
怀宾,蔡斌,程安来     3                  宁波理工     
     28    Dream:
黄柏彤,李森,张晓东          3                  北大信科     
     29    xjr:
汪瑜婧,郭英龙,田昊枢          3                  信科数院     
     30    OneOneOne:
陈科吉,梁博文,陈培      3                  北大信科     
     31   
糯米丸子:钱梦仁,汤元超,顾张磊     3                  北大信科     
     32    BNU_1:
龚治,易超,林子敏          3                  北师大     
     33    Giant-killer:
张辰飞,朱星炜,杨明   3                  北大信科     
     34    Knight:
杨挺,钟诚,俞毓锋           3                  北大信科     
     35    newHope:
王皓玉,王峰波,王锦鹏    2                  地大     
     36   
快乐三人行:梁诗鸣,张顺廷,陈巍     2                  北大信科     
     37 TJU-TeamB:
杨晨豪,邱侠斐,王晓宁     2                  天津大学     
     38 DoubleTriangle:
冯霁,常好哲,王海栋    2                  南开     
     39    Magic3:
张伟良,裴国东,李海龙       2                  软件学院     
     40    TIHS:
丁羽,                        2                  北大信科     
     41    Kingdom of Kings:
王宇昕,金鑫,蒲敬 2                  北大信科     
     42    C++Primer:
李龙,于弢,陈瑜          2                  北大信科     
     43   
三阶有向图:邓瑞伶,徐可,顾从云     2                  北大信科     
     44    Three Suns:
李雁章,吴沛文,李怡文   2    北大信科     
     45    POJ Hunter:
陈政,杨昊哲,赵树娟     2    北大信科     
     46    Little_nick:
马晓乐,马舒浩,雒佳俊  2    北大信科     
     47    RUO:
李政宇,谢全,王昊              2    北大信科     
     48    ZDL:
张敏林,戴少阳,栾添            2    北大信科     
     49    SunSon:
向永清,高运凯,方彬         2    北大信科     
     50    NKfresh:
叶时炜,毛旭东,杨建祥      2    南开     
     51    Miles:
林嘉怡,张雨萌,康迪          2    北大信科     
     52    LHJ_elephant_player:
李辰,黄舒志,金庸      2    北大信科     
     53    Temp:
宋恒,乔衎,任斐               2    北航     
     54    WHY:
王骏成,黄福青,张东扬          2    北大信科     
     55    Bupt4:
洪定乾,王坤山,曾魁          2    北邮     
     56    PMS:
邢雪源,武嘉怡,苟瑞            2    北大信科     
     57    challenging:
王旭,薛潇博,邱林      2    北大信科     
     58    ALAC:
罗海鹏,马郓,王晗             2    北大信科     
     59    x.i.u:
胡薇,沈才立,方仙法          2    北大信科     
     60    Bupt2:
宋子寅,虞里杉,薛阳阳        2    北邮     
     61    Running way:
孙军渭,张笑阳,陈琛    2    北大信科    

===============================================================

绍兴高中生唐文斌杀进世界顶级编程决赛2006-05-02 13:00:00

    新华网浙江频道52日电昨天上午,绍兴一中高三学生唐文斌乘车到上海,并从这里登上了直飞美国的国际航班,只身前往拉斯维加斯,他去参加一项世界顶级电脑编程比赛———美国Topcoder电脑编程锦标赛决赛。

       据了解,全球共有48人进入决赛,他们都是来自世界各地的电脑编程精英。此次进入决赛的华人选手共有4人,除唐文斌外,其他3人都是博士出身,两人是清华大学的,一人是美国斯坦福大学的;唐文斌是惟一一个杀入决赛的中学生。

       后来,学校的老师已不能指导他了

       据《都市快报》报道,几天前,唐文斌还在学校的机房呆着。由于电脑成绩突出,高二时,唐文斌被清华大学破格录取,这意味着他高中毕业就可以直接去清华了。没有升学烦恼的唐文斌几乎不需要上课堂,学校的信息中心便成了他的书房

       唐文斌清楚地记得第一次得奖是初三上学期,那时,刚学了两个月电脑,他带着尝试的心情参加了全国信息学(计算机)程序设计竞赛,出乎意料地,不小心混了个一等奖。唐文斌幽默地说。

       2003年在上海举行的第20届全国信息学奥林匹克竞赛上,唐文斌获得了银牌的最后一名,并入选奥林匹克国家集训队。接下来的日子,拿奖成了唐文斌的家常便饭:连续两届获得全国信息学奥林匹克联赛浙江赛区一等奖;第20届、21届全国信息学奥林匹克竞赛二等奖;第22届全国信息学奥林匹克竞赛一等奖……

       到后来,学校的老师已经不能指导唐文斌了,他便开始在网上看资料,也在网上认识了许多这个专业的朋友,他们在网上学习交流。除了学习,网络也给了唐文斌不一样的视野。

      今年2月,唐文斌看到Topcoder电脑编程锦标赛,便在线报名参加。

      并不希望通过这次比赛留在美国

      Topcoder电脑编程锦标赛初赛共分三轮,每一轮比赛有三道题目,有个固定的分数,并限定时间,唐文斌说,答题既要快,又要准!感觉很刺激。

       第一轮初赛,他成功进入了全球400强!第二轮、200强!第三轮,100强!直到最近举行的半决赛中,他成功杀入了全球48强,获得赴美参加现场决赛的资格。

       据介绍,这48名决赛选手共分3组,每组16人,唐文斌在他所在的小组排第10名。

       当问及接下来可能改变的命运时,唐文斌显得很低调,我并不希望通过这次比赛留在美国工作。他说,赛后他要回来,因为下半年他要去清华读书。

      链接

      Topcoder锦标赛全球计算机领域里鼎鼎有名的电脑赛事,由美国Topcoder公司举办,公司依托微软、AD等国际知名企业,专业举办各类电脑赛事,以此在全球范围内搜寻优秀的电脑天才,然后输送到这些国际大公司,为其所用。

====================================================================================

2009年两岸三地(北京清华大学,新竹清华大学,香港科技大学)程序设计竞赛在新竹清华大学举行。

71日到5日,北京清华大学计算机系派出了由2位领队、7名学生组成的代表队赴台参赛。代表队成员如下:

北京清华一队:唐文斌,郭华阳,杨弋;

北京清华二队:余林韵,俞华程,周冬;

女队:陈丹琦(女)。三校女生合作组成一个女队参赛。

领队:系副主任刘卫东、系学生工作办公室主任徐玉华

72日,经过5个小时的激烈比赛,北京清华一队获得第一名,北京清华二队获得第二名,三校女生队获得第三名。

赛后,代表队游览了中国文化遗产荟萃的台北故宫博物院和美丽如画的日月潭

 =====================================================================

计算机基础知识
第一章计算机基础常识
第二章操作系统简介
第三章计算机网络
第四章计算机信息安全基础知识

Pascal语言

第一章开始编写pascal语言程序
第二章Pascal语言基础知识
第三章顺序结构程序设计
第四章选择结构程序设计
第五章循环结构程序设计
第六章数组与字符串 
第七章函数和过程
第八章子界与枚举类型
第九章集合类型
第十章记录与文件类型
第十一章指针 
第十二章程序调试

常用算法与策略 
第一章算法的概念
第二章递归
第三章回溯
第四章排序 
第五章查找 
第六章穷举策略 
第七章贪心算法 
第八章分治策略 

数据结构
第一章什么是数据结构 
第二章线性表 
第三章栈 
第四章队 
第五章树 
第六章图 

动态规划
第一章什么叫动态规划 
第二章用动态规划解题 
第三章典型例题与习题 
第四章动态规划的递归函数法
第五章动态规划分类1

数学知识及相关算法
第一章有关数论的算法 
第二章高精度计算 
第三章排列与组合 
第四章计算几何 
第五章其它数学知识及算法 

图论算法
第一章最小生成树 
第二章最短路径 
第三章拓扑排序(AOV网) 
第四章关键路径(AOE网) 
第五章网络流 
第六章图匹配 

搜索算法与优化
第一章双向广度优先搜索 
第二章分支定界法 
第三章A*算法 

 

1.USACO Training  Program Curriculum 的网络课程 ----美国计算机奥赛组织USACO (USA Computer Olympiad) 为全球免费提供的一项训练课程,包括讯息渐进的23篇课文和97道编程练习题目。(4个月/2Hours,  152KB的97个程序的源代码)

http://train.usaco.org/usacogate

 ==================================================================

省选辅导知识讲解目录:参加省选和NOI还需要哪些知识? by Matrix67

(一)
    NOIp结束后,我开始给我们学校高一高二的同学进行选拔赛辅导,时间是从12月11日到2月底,主要讲解NOIp以外的知识。期末考试的日期是2月1日,以这个日期为分界点可以把辅导分成两个阶段。前一阶段全部进行知识讲解,讲到了组合数学。这个阶段一星期上三次课,每个星期总计大概有8到9个课时。讲到1月24日后大家就回去准备期末考试了。后一阶段是在寒假中了,上了两个星期,模拟考试和知识讲解交替进行。每一天大概6到7课时。
    我讲的进度飞快,下面所有的知识基本上是讲完了的,不算模拟考试的话总共用了20多天共70到80课时。当然,这些时间里包括了扯蛋,乱谈,和集体玩SC、CS、WWP的时间。记得有一天扯蛋扯了一个多小时。
    最后的结果不令人满意,因为这次重庆选拔赛的题目很怪,没有用到什么比NOIp高级一点的东西。因此,下面我整理的课程安排在实践上看还没有确切的最终效果可供参考。    
(二)
    NOIp的知识点并不多,很多参考书上都有。但是NOIp之外的东西一下子就多了,想再要排出一份课程来就很麻烦了。比如,不少比较交叉的东西很不好归类。我的这份知识列表很多时候怎么看怎么不顺眼,有些重复,有些遗漏,有些归类混淆。这份列表只是一个参考,我强行地归一下类仅仅是因为课程的安排需要有一个顺序。这只是一个初步的尝试,很多科学性的问题值得思考。
(三)
    我收到过很多邮件,不少人问我想要参加NOI还需要哪些知识。需要的知识很多,列一张表出来的话需要经过仔细的思考。然后我就我仔细思考了一下。我发现,NOI需要的东西还真他妈的多。现在,我就把我想到的东西写在下面供大家参考。这里面没写贪心、分治之类的东西,因为它们里面不包含什么特别的知识点,只有一大堆题目。
    我预言这篇日志一定是访问量最高的,因为这里面关键字云集。若某人查资料找到这里来失望地发现其实只是一群关键字的话,我先给您说不是。
(四)
    OIBH上的牛人其实不多,真正牛的人很少上OIBH。像我这样的NOI菜鸟时常在想,什么时候能像集训队的那些牛一样研究一些更高级的东西。很多东西我都不会,比如线性时间构造后缀树,查找最大重复子串,HLPP也没有仔细研究过。但是,我仍然很想帮助更多的OI新手。我经常看到OIBH上很多人问问题却没有人回答或回答很简略,这并不是因为大牛们不会,而是它们没有时间来写冗长的分析讲解。网上相关的资料其实是很多的,不过能顺利理解英文的OIer似乎不占多数,一些中文讲解也有很多问题,有很多讲不清的地方。嗯,既然大牛们没有空写,那就把任务交给我吧。后来我就写了一些风格比较相近的长篇知识讲解,冠名“Matrix67的OI点滴”。前几天觉得这真他妈的形式化,然后把标题里的这句话都删了。还有很多东西我都想写,自己该写什么就写什么更自由一些,不用限制在一个自己规定的框架里。今后我打算继续写下去,仍然以大众化的、容易理解的、罗嗦的语言来描述各种算法。省选辅导让我把这些知识又回顾了一遍,很多东西更清晰了。我想按着下面的线索把我在辅导中讲的东西写下来,提供更多网络上不好找的资料。

时间复杂度(渐近时间复杂度的严格定义,NP问题,时间复杂度的分析方法,主定理)
排序算法(平方排序算法的应用,Shell排序,快速排序,归并排序,时间复杂度下界,三种线性时间排序,外部排序)
数论(整除,集合论,关系,素数,进位制,辗转相除,扩展的辗转相除,同余运算,解线性同余方程,中国剩余定理)
指针(链表,搜索判重,邻接表,开散列,二叉树的表示,多叉树的表示)
按位运算(and,or,xor,shl,shr,一些应用)
图论(图论模型的建立,平面图,欧拉公式与五色定理,求强连通分量,求割点和桥,欧拉回路,AOV问题,AOE问题,最小生成树的三种算法,最短路的三种算法,标号法,差分约束系统,验证二分图,Konig定理,匈牙利算法,KM算法,稳定婚姻系统,最大流算法,最小割最大流定理,最小费用最大流算法)
计算几何(平面解几及其应用,向量,点积及其应用,叉积及其应用,半平面相交,求点集的凸包,最近点对问题,凸多边形的交,离散化与扫描)
数据结构(广度优先搜索,验证括号匹配,表达式计算,递归的编译,Hash表,分段Hash,并查集,Tarjan算法,二叉堆,左偏树,斜堆,二项堆,二叉查找树,AVL,Treap,Splay,静态二叉查找树,2-d树,线段树,二维线段树,矩形树,Trie树,块状链表)
组合数学(排列与组合,鸽笼原理,容斥原理,递推,Fibonacci数列,Catalan数列,Stirling数,差分序列,生成函数,置换,Polya原理)
概率论(简单概率,条件概率,Bayes定理,期望值)
矩阵(矩阵的概念和运算,二分求解线性递推方程,多米诺骨牌棋盘覆盖方案数,高斯消元)
字符串处理(KMP,后缀树,有限状态自动机,Huffman编码,简单密码学)
动态规划(单调队列,凸完全单调性,树型动规,多叉转二叉,状态压缩类动规,四边形不等式)
博奕论(Nim取子游戏,博弈树,Shannon开关游戏)
搜索(A*,ID,IDA*,随机调整,遗传算法)
微积分初步(极限思想,导数,积分,定积分,立体解析几何) 

Matrix67原创
matrix67.com

==========================================================================

什么是P问题、NP问题和NPC问题 by Matrix67.com

这或许是众多OIer最大的误区之一。
    你会经常看到网上出现“这怎么做,这不是NP问题吗”、“这个只有搜了,这已经被证明是NP问题了”之类的话。你要知道,大多数人此时所说的NP问题其实都是指的NPC问题。他们没有搞清楚NP问题和NPC问题的概念。NP问题并不是那种“只有搜才行”的问题,NPC问题才是。好,行了,基本上这个误解已经被澄清了。下面的内容都是在讲什么是P问题,什么是NP问题,什么是NPC问题,你如果不是很感兴趣就可以不看了。接下来你可以看到,把NP问题当成是 NPC问题是一个多大的错误。
    还是先用几句话简单说明一下时间复杂度。时间复杂度并不是表示一个程序解决问题需要花多少时间,而是当问题规模扩大后,程序需要的时间长度增长得有多快。也就是说,对于高速处理数据的计算机来说,处理某一个特定数据的效率不能衡量一个程序的好坏,而应该看当这个数据的规模变大到数百倍后,程序运行时间是否还是一样,或者也跟着慢了数百倍,或者变慢了数万倍。不管数据有多大,程序处理花的时间始终是那么多的,我们就说这个程序很好,具有O(1)的时间复杂度,也称常数级复杂度;数据规模变得有多大,花的时间也跟着变得有多长,这个程序的时间复杂度就是O(n),比如找n个数中的最大值;而像冒泡排序、插入排序等,数据扩大2倍,时间变慢4倍的,属于O(n^2)的复杂度。还有一些穷举类的算法,所需时间长度成几何阶数上涨,这就是O(a^n)的指数级复杂度,甚至O(n!)的阶乘级复杂度。不会存在O(2*n^2)的复杂度,因为前面的那个“2”是系数,根本不会影响到整个程序的时间增长。同样地,O (n^3+n^2)的复杂度也就是O(n^3)的复杂度。因此,我们会说,一个O(0.01*n^3)的程序的效率比O(100*n^2)的效率低,尽管在n很小的时候,前者优于后者,但后者时间随数据规模增长得慢,最终O(n^3)的复杂度将远远超过O(n^2)。我们也说,O(n^100)的复杂度小于O(1.01^n)的复杂度。
    容易看出,前面的几类复杂度被分为两种级别,其中后者的复杂度无论如何都远远大于前者:一种是O(1),O(log(n)),O(n^a)等,我们把它叫做多项式级的复杂度,因为它的规模n出现在底数的位置;另一种是O(a^n)和O(n!)型复杂度,它是非多项式级的,其复杂度计算机往往不能承受。当我们在解决一个问题时,我们选择的算法通常都需要是多项式级的复杂度,非多项式级的复杂度需要的时间太多,往往会超时,除非是数据规模非常小。
    自然地,人们会想到一个问题:会不会所有的问题都可以找到复杂度为多项式级的算法呢?很遗憾,答案是否定的。有些问题甚至根本不可能找到一个正确的算法来,这称之为“不可解问题”(Undecidable Decision Problem)。The Halting Problem就是一个著名的不可解问题,在我的Blog上有过专门的介绍和证明。再比如,输出从1到n这n个数的全排列。不管你用什么方法,你的复杂度都是阶乘级,因为你总得用阶乘级的时间打印出结果来。有人说,这样的“问题”不是一个“正规”的问题,正规的问题是让程序解决一个问题,输出一个“YES”或“NO”(这被称为判定性问题),或者一个什么什么的最优值(这被称为最优化问题)。那么,根据这个定义,我也能举出一个不大可能会有多项式级算法的问题来:Hamilton回路。问题是这样的:给你一个图,问你能否找到一条经过每个顶点一次且恰好一次(不遗漏也不重复)最后又走回来的路(满足这个条件的路径叫做Hamilton回路)。这个问题现在还没有找到多项式级的算法。事实上,这个问题就是我们后面要说的NPC问题。
    下面引入P类问题的概念:如果一个问题可以找到一个能在多项式的时间里解决它的算法,那么这个问题就属于P问题。P是英文单词多项式的第一个字母。哪些问题是P类问题呢?通常NOI和NOIP不会出不属于P类问题的题目。我们常见到的一些信息奥赛的题目都是P问题。道理很简单,一个用穷举换来的非多项式级时间的超时程序不会涵盖任何有价值的算法。
    接下来引入NP问题的概念。这个就有点难理解了,或者说容易理解错误。在这里强调(回到我竭力想澄清的误区上),NP问题不是非P类问题。NP问题是指可以在多项式的时间里验证一个解的问题。NP问题的另一个定义是,可以在多项式的时间里猜出一个解的问题。比方说,我RP很好,在程序中需要枚举时,我可以一猜一个准。现在某人拿到了一个求最短路径的问题,问从起点到终点是否有一条小于100个单位长度的路线。它根据数据画好了图,但怎么也算不出来,于是来问我:你看怎么选条路走得最少?我说,我RP很好,肯定能随便给你指条很短的路出来。然后我就胡乱画了几条线,说就这条吧。那人按我指的这条把权值加起来一看,嘿,神了,路径长度98,比100小。于是答案出来了,存在比100小的路径。别人会问他这题怎么做出来的,他就可以说,因为我找到了一个比100 小的解。在这个题中,找一个解很困难,但验证一个解很容易。验证一个解只需要O(n)的时间复杂度,也就是说我可以花O(n)的时间把我猜的路径的长度加出来。那么,只要我RP好,猜得准,我一定能在多项式的时间里解决这个问题。我猜到的方案总是最优的,不满足题意的方案也不会来骗我去选它。这就是NP问题。当然有不是NP问题的问题,即你猜到了解但是没用,因为你不能在多项式的时间里去验证它。下面我要举的例子是一个经典的例子,它指出了一个目前还没有办法在多项式的时间里验证一个解的问题。很显然,前面所说的Hamilton回路是NP问题,因为验证一条路是否恰好经过了每一个顶点非常容易。但我要把问题换成这样:试问一个图中是否不存在Hamilton回路。这样问题就没法在多项式的时间里进行验证了,因为除非你试过所有的路,否则你不敢断定它“没有Hamilton回路”。
    之所以要定义NP问题,是因为通常只有NP问题才可能找到多项式的算法。我们不会指望一个连多项式地验证一个解都不行的问题存在一个解决它的多项式级的算法。相信读者很快明白,信息学中的号称最困难的问题——“NP问题”,实际上是在探讨NP问题与P类问题的关系。
    很显然,所有的P类问题都是NP问题。也就是说,能多项式地解决一个问题,必然能多项式地验证一个问题的解——既然正解都出来了,验证任意给定的解也只需要比较一下就可以了。关键是,人们想知道,是否所有的NP问题都是P类问题。我们可以再用集合的观点来说明。如果把所有P类问题归为一个集合P中,把所有 NP问题划进另一个集合NP中,那么,显然有P属于NP。现在,所有对NP问题的研究都集中在一个问题上,即究竟是否有P=NP?通常所谓的“NP问题”,其实就一句话:证明或推翻P=NP。
    NP问题一直都是信息学的巅峰。巅峰,意即很引人注目但难以解决。在信息学研究中,这是一个耗费了很多时间和精力也没有解决的终极问题,好比物理学中的大统一和数学中的歌德巴赫猜想等。
    目前为止这个问题还“啃不动”。但是,一个总的趋势、一个大方向是有的。人们普遍认为,P=NP不成立,也就是说,多数人相信,存在至少一个不可能有多项式级复杂度的算法的NP问题。人们如此坚信P≠NP是有原因的,就是在研究NP问题的过程中找出了一类非常特殊的NP问题叫做NP-完全问题,也即所谓的 NPC问题。C是英文单词“完全”的第一个字母。正是NPC问题的存在,使人们相信P≠NP。下文将花大量篇幅介绍NPC问题,你从中可以体会到NPC问题使P=NP变得多么不可思议。
    为了说明NPC问题,我们先引入一个概念——约化(Reducibility,有的资料上叫“归约”)。
    简单地说,一个问题A可以约化为问题B的含义即是,可以用问题B的解法解决问题A,或者说,问题A可以“变成”问题B。《算法导论》上举了这么一个例子。比如说,现在有两个问题:求解一个一元一次方程和求解一个一元二次方程。那么我们说,前者可以约化为后者,意即知道如何解一个一元二次方程那么一定能解出一元一次方程。我们可以写出两个程序分别对应两个问题,那么我们能找到一个“规则”,按照这个规则把解一元一次方程程序的输入数据变一下,用在解一元二次方程的程序上,两个程序总能得到一样的结果。这个规则即是:两个方程的对应项系数不变,一元二次方程的二次项系数为0。按照这个规则把前一个问题转换成后一个问题,两个问题就等价了。同样地,我们可以说,Hamilton回路可以约化为TSP问题(Travelling Salesman Problem,旅行商问题):在Hamilton回路问题中,两点相连即这两点距离为0,两点不直接相连则令其距离为1,于是问题转化为在TSP问题中,是否存在一条长为0的路径。Hamilton回路存在当且仅当TSP问题中存在长为0的回路。
    “问题A可约化为问题B”有一个重要的直观意义:B的时间复杂度高于或者等于A的时间复杂度。也就是说,问题A不比问题B难。这很容易理解。既然问题A能用问题B来解决,倘若B的时间复杂度比A的时间复杂度还低了,那A的算法就可以改进为B的算法,两者的时间复杂度还是相同。正如解一元二次方程比解一元一次方程难,因为解决前者的方法可以用来解决后者。
    很显然,约化具有一项重要的性质:约化具有传递性。如果问题A可约化为问题B,问题B可约化为问题C,则问题A一定可约化为问题C。这个道理非常简单,就不必阐述了。
    现在再来说一下约化的标准概念就不难理解了:如果能找到这样一个变化法则,对任意一个程序A的输入,都能按这个法则变换成程序B的输入,使两程序的输出相同,那么我们说,问题A可约化为问题B。
    当然,我们所说的“可约化”是指的可“多项式地”约化(Polynomial-time Reducible),即变换输入的方法是能在多项式的时间里完成的。约化的过程只有用多项式的时间完成才有意义。
    好了,从约化的定义中我们看到,一个问题约化为另一个问题,时间复杂度增加了,问题的应用范围也增大了。通过对某些问题的不断约化,我们能够不断寻找复杂度更高,但应用范围更广的算法来代替复杂度虽然低,但只能用于很小的一类问题的算法。再回想前面讲的P和NP问题,联想起约化的传递性,自然地,我们会想问,如果不断地约化上去,不断找到能“通吃”若干小NP问题的一个稍复杂的大NP问题,那么最后是否有可能找到一个时间复杂度最高,并且能“通吃”所有的 NP问题的这样一个超级NP问题?答案居然是肯定的。也就是说,存在这样一个NP问题,所有的NP问题都可以约化成它。换句话说,只要解决了这个问题,那么所有的NP问题都解决了。这种问题的存在难以置信,并且更加不可思议的是,这种问题不只一个,它有很多个,它是一类问题。这一类问题就是传说中的NPC 问题,也就是NP-完全问题。NPC问题的出现使整个NP问题的研究得到了飞跃式的发展。我们有理由相信,NPC问题是最复杂的问题。再次回到全文开头,我们可以看到,人们想表达一个问题不存在多项式的高效算法时应该说它“属于NPC问题”。此时,我的目的终于达到了,我已经把NP问题和NPC问题区别开了。到此为止,本文已经写了近5000字了,我佩服你还能看到这里来,同时也佩服一下自己能写到这里来。
    NPC问题的定义非常简单。同时满足下面两个条件的问题就是NPC问题。首先,它得是一个NP问题;然后,所有的NP问题都可以约化到它。证明一个问题是 NPC问题也很简单。先证明它至少是一个NP问题,再证明其中一个已知的NPC问题能约化到它(由约化的传递性,则NPC问题定义的第二条也得以满足;至于第一个NPC问题是怎么来的,下文将介绍),这样就可以说它是NPC问题了。
    既然所有的NP问题都能约化成NPC问题,那么只要任意一个NPC问题找到了一个多项式的算法,那么所有的NP问题都能用这个算法解决了,NP也就等于P 了。因此,给NPC找一个多项式算法太不可思议了。因此,前文才说,“正是NPC问题的存在,使人们相信P≠NP”。我们可以就此直观地理解,NPC问题目前没有多项式的有效算法,只能用指数级甚至阶乘级复杂度的搜索。
    顺便讲一下NP-Hard问题。NP-Hard问题是这样一种问题,它满足NPC问题定义的第二条但不一定要满足第一条(就是说,NP-Hard问题要比 NPC问题的范围广)。NP-Hard问题同样难以找到多项式的算法,但它不列入我们的研究范围,因为它不一定是NP问题。即使NPC问题发现了多项式级的算法,NP-Hard问题有可能仍然无法得到多项式级的算法。事实上,由于NP-Hard放宽了限定条件,它将有可能比所有的NPC问题的时间复杂度更高从而更难以解决。
    不要以为NPC问题是一纸空谈。NPC问题是存在的。确实有这么一个非常具体的问题属于NPC问题。下文即将介绍它。
    下文即将介绍逻辑电路问题。这是第一个NPC问题。其它的NPC问题都是由这个问题约化而来的。因此,逻辑电路问题是NPC类问题的“鼻祖”。
    逻辑电路问题是指的这样一个问题:给定一个逻辑电路,问是否存在一种输入使输出为True。
    什么叫做逻辑电路呢?一个逻辑电路由若干个输入,一个输出,若干“逻辑门”和密密麻麻的线组成。看下面一例,不需要解释你马上就明白了。
  ┌───┐
  │ 输入1├─→┐    ┌──┐
  └───┘    └─→┤    │
                      │ or ├→─┐
  ┌───┐    ┌─→┤    │    │    ┌──┐
  │ 输入2├─→┤    └──┘    └─→┤    │
  └───┘    │                ┌─→┤AND ├──→输出
                └────────┘┌→┤    │
  ┌───┐    ┌──┐            │  └──┘
  │ 输入3├─→┤ NOT├─→────┘
  └───┘    └──┘
    这是个较简单的逻辑电路,当输入1、输入2、输入3分别为True、True、False或False、True、False时,输出为True。
    有输出无论如何都不可能为True的逻辑电路吗?有。下面就是一个简单的例子。
  ┌───┐
  │输入1 ├→─┐    ┌──┐
  └───┘    └─→┤    │
                      │AND ├─→┐
                ┌─→┤    │    │
                │    └──┘    │  ┌──┐
                │                └→┤    │
  ┌───┐    │                    │AND ├─→输出
  │输入2 ├→─┤  ┌──┐      ┌→┤    │
  └───┘    └→┤NOT ├→──┘  └──┘
                    └──┘
    上面这个逻辑电路中,无论输入是什么,输出都是False。我们就说,这个逻辑电路不存在使输出为True的一组输入。
    回到上文,给定一个逻辑电路,问是否存在一种输入使输出为True,这即逻辑电路问题。
    逻辑电路问题属于NPC问题。这是有严格证明的。它显然属于NP问题,并且可以直接证明所有的NP问题都可以约化到它(不要以为NP问题有无穷多个将给证明造成不可逾越的困难)。证明过程相当复杂,其大概意思是说任意一个NP问题的输入和输出都可以转换成逻辑电路的输入和输出(想想计算机内部也不过是一些 0和1的运算),因此对于一个NP问题来说,问题转化为了求出满足结果为True的一个输入(即一个可行解)。
    有了第一个NPC问题后,一大堆NPC问题就出现了,因为再证明一个新的NPC问题只需要将一个已知的NPC问题约化到它就行了。后来,Hamilton 回路成了NPC问题,TSP问题也成了NPC问题。现在被证明是NPC问题的有很多,任何一个找到了多项式算法的话所有的NP问题都可以完美解决了。因此说,正是因为NPC问题的存在,P=NP变得难以置信。P=NP问题还有许多有趣的东西,有待大家自己进一步的挖掘。攀登这个信息学的巅峰是我们这一代的终极目标。现在我们需要做的,至少是不要把概念弄混淆了。

========================================================================

ACM 清华大学----唐文斌

  信息学奥赛国家队教练,第22届全国信息学奥林匹克竞赛金牌,现就读于清华大学,参与了第23届全国青少年信息学奥林匹克竞赛命题工作。唐文斌是 2006 年TopCoder Open全球48名现场决赛入围者中惟一的一名中学生。自2003年,唐文斌连续3年3次获得信息学浙江赛区的一等奖,2005年荣获第22届全国信息学 奥林匹克竞赛金牌,作为信息学天才选手,唐文斌高二时就被清华大学破格录取。学生评价:“唐文斌讲课知识涵盖面大,丰富,所给例题很好。”

唐文斌:一边游学 一边成长
        最年轻的百度之星还是个高三学生!
        窗外是北京秋日明净的蓝天,一排白杨直入云端。
        电脑前,绍兴少年唐文斌神情专注,十指如飞。
        从4000余人的初赛,到300人的复赛,再到50人的总决赛现场,这颗小星星杀出重围,在林立的高手中占据了一席之地。
        提交完程序,他打开QQ,跟天南海北的朋友报告情况,嘴角浮起笑容。
       从初二开始,借着全国青少年信息学奥林匹克竞赛的东风,唐文斌一边攻擂,一边结识了众多圈内好手。一起切磋琢磨,一起玩耍嬉戏。绍兴、上海、北京……和自己的技术一起旅行,见到新朋旧友,对唐文斌来说是很爽的一件事情。 
      四处游学开阔了他的眼界,也给了他健康阳光的心理和自信。 
      电脑之外,身高一米八的唐文斌神情轻松,言语幽默,很有人缘儿。 
      自我介绍时,面对众人好奇的目光,他俏皮道:“我这个老年人,到这里来充当小朋友了!”
      百度之星集体游赏颐和园时,他蹦蹦跳跳,跟谁都聊得来,成了队伍里的开心果。
      一群聪明的头脑聚到一起,激发了大家的上进心。成绩揭晓的前一天晚上,他预测:“从理论上讲,应该是楼天城会得第一。”他认为自己发挥得只能说还可以。 
       他解释说,早先跟楼天城一起参加过奥赛集训,而且听清华的朋友讲,在大学里楼天城还保持每天做题的习惯。赛后楼天城曾跟他谈论自己采用的比较独特的解题办法,他认为很有希望。 
        结果证明他的眼光不错。
        晚上,他清华的朋友周来看他时,这个非同一般的高三生宣布:“我铁定去清华了!”出色的“游学”成绩已经让他登上了清华大学的直通车。
        这意味着,他的高三生活可以这样度过:写程序、打“极品飞车”,偶尔出去比赛,见识象百度这样的公司,认识更多朋友。
        比起小学一年级时因为插班的缘故,以年级第一身份留级(这个第一可是正数的哦,他说),这样的选择显然让他更有成就感。

=======================================================================

陈世熹 :大牛无形
      世界上永远有这么一种人,他安静着,绝不喧哗,却透露出那么一股刚健的力量。他根本不去讨好这个世界,他不做任何的让步,然而每个看到他的人都会想:这是个人物。
     陈世熹就绝对是这样的一个人物。
传说中的大牛
2005,10月16日下午,2:45pm。
      陈世熹和其他六名上海选手,作为首批远道而来的“百度之星” 空降北京。还没走出接近口,他就让前来接机的工作人员感到一丝凉意:和其他选手的活跃与兴奋明显不同,他一张棱角分明的脸,目光始终有神的注视着前方某个地方。休息的时候,大家聊得热火朝天,他也并不插话,就静静的靠在椅子上闭目养神。 
       第一天晚上,除了丰盛的晚宴,就是破冰大会——大家互相介绍自己,做游戏。
那个晚上,每一颗“程序之星”都闪闪发亮,风趣而个性的自我介绍层出不穷。而陈世熹,却是最让人记得清楚的一个。当他走上台,他仅仅是简短有力的报出自己的姓名和学校,随即就走下台去了……
破冰大会,失败一人? 
       然而,他的名字在“星星”们中引起一阵骚动。原来陈世熹在高校软件界内的,早就是公认的绝世高手了,他是是华东地区高校程序界的带头人。平时可谓是“神龙见首不见尾”,众多Fans也只是在网上管窥一豹的看见他的一段程序,或者对算法的一点看法,便已经觉得受用无穷,感而慨之了。有人在下面感叹:“今天总算是见到活人了!”然而,激动之余,却苦于难以沟通,一时群雄纷纷摇头。
大牛无形……
在自己的世界中
      和C接触久了,才发现他根本没有传说中那么可怕。他也喜欢看动漫,喜欢火影忍者的激情,讨厌one piece的罗嗦,不过动慢总是更新太慢,最近在看小说。
       他的第一次编程,可以追溯到小学5年级。在那个众多聪明小孩骗着家长给他们买学习机打游戏的时候,C英明神武的父亲拿着别人送的学习机让他打游戏玩,而碰巧家里适时的出现了一本有关basic编程的书。于是游戏没怎么打,倒是喜欢上编程了,从此开始了他十几年的编程生涯。
       初中的时候C参加了第一次程序比赛,300分的满分他拿了270分,是中学组的第一名,比初中组的第二名高100分,比高中组的第一名都高了几分。那个高中组的第一名所在的学校是这种竞赛的强校,而那次比赛是他们认为的没有对手的比赛,C的出现让他们大吃一惊,那是对“半路杀出个程咬金”最好的诠注。而C本人却说:“没什么感觉。”
      C说,自己不是一个参赛型的选手,他更喜欢做自己的研究,沉浸在他的世界中,他是自己王国的设计师与建筑师,构建着一个宏伟而美丽的程序王国。对于比赛,他觉得他不算最厉害的。的确,比赛里,他拿的是亚军。只是说,比赛里。
他是一个活在自己世界中的,奇才,绝对的。
我要改变全世界
     C符合一个程序天才的所有条件:超出常人的天赋,与众不同的举止,还有他充满玄妙的自己的世界。在他的脑袋里,到底蕴藏着什么?
    “其实我希望做出一件东西,可以改变全世界。”
      C说,这不是不着边际的空想,他有自己的伟大理想,这个改变不是普通的一样发明创造,而应该是自计算机问世以后人类的又一个里程碑,他希望能有机会开发出真正的人工智能。而关于自然语言的处理,也会是人工智能的一个重要方面,毕竟能够理解自然语言,人工智能就成功了一半,
       这次,来参加百度的比赛,他也是抱着这样一个目的:希望从百度这里受到一点启发。
      中文是最具有智慧的语言,能够做好中文信息处理的搜索引擎是最了不起的搜索引擎,而能处理中文自然语言的人工智能必然是最聪明的人工智能咯。
      C同学的梦想很美好,也很宏大,希望这次百度的程序之旅中,在这个百度提供给程序之星智慧碰撞的大舞台中,他能看到一些把梦想变为现实的可能性,毕竟百度是一个把梦想变为现实的地方,这里,又会是无数个梦想起飞的地方。

=======================================================================================

楼天城:没有想到的冠军
       百度之星程序大赛的冠军头衔花落楼天城!
       这多少让人有些吃惊。在众多参赛高手中,尽管楼天城在圈内也算小有名气,但在这次活动中却显得非常低调,给人一种争当绿叶的感觉。在众多百度之星中,显得并不耀眼的他在比赛结束后便有些沮丧,称自己发挥得并不好。
       这次大赛,许多选手认为,选题出得不是简单,而是太简单了。而楼天城也有这样的感觉。正因为太简单,所以,“这些简单的题反而不太会做,出错的地方太多了。”
       对他这个说法,本次比赛的定题人——百度首席架构设计师周利民躲在旁边善意地一笑。周解释说,这些选题看似简单,但极其容易出错,这就是简单中的不简单。他说,这些选题是百度高级工程师——他们都是国内有关中文搜索引擎方面的绝顶高手出的,最终又经过充分讨论,最终才获得选定。
        一位业界高手认为,百度的选题,与其他类型的考题差别还是比较大的,它更强调实用性与操作性,对于以培养产品研发人才为目标的百度来说,这样的竞赛题目是非常具有实际价值。
       而楼天城的比赛现状也证实了这一说法。
       楼天城来自杭州,这位到了高一才开始接触编程的高中生,一接触软它便热爱上了它。到了高二、高三,其实他玩软件是有功利性目的的。如果能够在参加比赛中获得前20名,便可以免试进入清华大学。 
       当然,楼天城自然进入这前20名,成为免试进入清华的学生之一。
       楼天城是计算机系大二的学生。他说他进入大学后,反而没有时间玩软件开发了。“因为学校的课程太紧了,很少有时间玩它。”他在学校的成绩,属于那种第一梯队的那种。
       而楼天城的志向并不在于软件,他对自己的未来“还没有考虑好。想出国读研。但要出国也不那么容易,再看看吧。”
       这个高个而比较壮实的大男孩,其实比较腼腆,坐在哪儿都挺安稳的那种。与人说话都很认真,跟在大集体中活动,绝不会越雷池一步。听到集合或有行动等安排等,会非常敏感地警觉一下,然后去做。
       这样的性格有可能使他不太可能将来去玩软件开发,他说他喜欢做发展不太迅速,可以进行深度研究的那种科学领域。“软件发展太快了,永远在追赶,我不太喜欢。”
       但是,软件他也不想放弃,“有一门手艺留在手上,总是好的。”所以,他进入大学后,也会参与软件方面的兴趣小组,但“投入的时间并不多”。
       实际操作的不足,使他的“手”生疏起来,这便是他认为他考得不好的原因。而对他最终能够考到第一,他认为,可能是他当年进行过长期而刻苦的训练有关,“基本功比较好吧”。楼说。
       获得冠军有些兴奋的楼天城,对百度的感觉良好。
       他说他一直喜欢百度,而参与此次比赛,他发现百度人特别富有激情。更令他感到吃惊的是,他发现,百度的高手才是真正的高手,因为他听到百度的工程师们在谈一些软件方面的问题,这些工程师研究到了很深的地步,“我几乎一句也听不懂,他们好厉害。”

============================================================================================

杨淋升:在程序之美中找到归属 
       如果杨淋升不开口说话,没有人会发现他是一个外籍华人。 
       在庆祝决赛结束的晚会上,他静静地站在那里,微笑着,穿着印有百度logo的黑色带帽衫,他就像一抹安静的阳光。 
       看着周围那些同样进入百度之星决赛的“星星”们,他说自己很高兴,很开心。听到有人赞美他有本土气质,他就笑得更开心了。 
       20岁的杨淋升,是印尼华人,现在在清华读化工系,大三。他是本次百度之星程序大赛里唯一的留学生。 
       他说他真的很喜欢这里。 
归于中国 
       杨凌升从小在印尼长大,回忆起那段经历,他流露出淡淡的悲愤。他说,在印尼,华人比较受到排挤,虽然自己入了印尼籍,却从来没有觉得过自己是印尼人。加上父母都是中国人,而且极其热爱中国的文化,所以从小就受到熏陶,很想回中国,所以在新加坡读了中学以后,就回来了。 
       然后读了清华。 
       和其他留学生不同,杨凌升非常喜欢交朋友,尤其是和中国学生交朋友。他参加各种社团活动,认识了一大帮志同道合的人。其中就包括清华科协。 
       正是清华科协的一个朋友,看到了百度之星程序大赛的消息,告诉他,说,你适合去参加,你很优秀,你去吧。  
       于是他就来了。然后就进了复赛,然后又进了决赛。百度的工作人员了解到他是留学生以后,还专门打个他打电话。 
        他说这种有人关心的感觉,很好。回到中国以后,再也不会感觉到像以前那样飘浮了。 
        他补充说:这是不是叫归宿? 
属于编程  
        另一次飘浮感,产生于高三。 
        和很多天生聪明的孩子一样,杨淋升读高中时,兴趣极为广泛,喜欢数学、物理、化学、最喜欢的是计算机。报考大学让他颇费了一番心思:读数学物理,可以当科学家,读计算机,可以当程序员;到底干什么好呢?最后,开化工厂的理想俘虏了他,他进了清华的化工系。 
       其实选一个专业,就和与它结婚一样。谈恋爱时喜欢一个人,结了婚,却发现全然不是那么一回事,这种事太常见了。杨淋升就属于这种类型。和化工系的蜜月没多久过去了,他发现自己牵肠挂肚的,还是编程。于是他又掉过头去,和计算机搞“外遇” 
        最初只是课余兴趣,写写程序玩儿。却越来越发现自己深陷其中,不能自拔。他说,废寝忘食以后,整整齐齐地代码在自己手下诞生,你会觉得那是一件艺术品。更神奇的是,这些艺术品,同时也是一把把利器。 
       大二的时候,杨淋升觉得登陆学校网关的小软件不够方便,于是就自己重新写了一个。因为足够简单快速,被很多人所传播使用。杨淋升说,看到自己写的东西,能给别人带来方便,被那么多人用,那种快感简直无法用语言形容。 
       他说,那时候他知道自己爱上编程了。完全浸淫其中,不觉疲乏。这种热爱,这种快感,大概是自己最强劲的动力了。 
        他说,百度的工程师,一定很幸福,可以用自己的技术改变这个世界好多好多人的生活;  
        他说,他特别喜欢大赛第一阶段的名称,“程序之美”, 
        他说,真的很美。这里的一切都很美。 
        美,就是归宿。
=========================================================================================

 清华大学2010~2011学年度校历

●2009年5月,在第二届全国大学生网络商务创新应用大赛全国总决赛中,由我校经管学院4名二年级学生张晨、伍丹、郑睿和任仕廷组成的B-insight团队以商业方案《以健身房为例,探讨企业如何开发利用博客群的商业价值》荣获总决赛一等奖。
●2009年6月,历时3个月的“2009TCL全国大学生工业创意设计大赛”在深圳落下帷幕,我校学生赵颖凭借作品《灵卷》力拔头筹,获得大赛金奖及2万元奖金,并获得赴香港交流学习的机会。
●2009年6月,我校法学院学生殷玥、廖宇飞包揽美迈斯北京地区法学奖学特等奖(共设2名)。美国美迈斯律师事务所美国美迈斯律师事务所创建于1885年,是全球最大和最负盛名的国际综合性律师事务所之一
●2009年6月9日,在杭州市首届“赛伯乐杯”大学生创业大赛中,我校学生组成的创业团队以“青峰绿色建筑科技有限责任公司”荣获大赛总分第一,并获得特等奖。
●2009年6月,由瑞士Holcim可持续建筑基金会举办的2009年Holcim可持续建筑全球大奖赛揭晓,由建筑学院教师张悦带领,联合北京市规划委员会等共同协作完成的设计项目—“北京乡村地区的可持续规划与设计”从全球数千个优秀项目中脱颖而出,获得亚太地区金奖,并赢得10万美元奖金。
●2009年6月, 2009全国大学生演讲比赛在横店举行,全国50多所高校的200多位学生参加了比赛,来自我校的美国籍留学生华杰凯的中文水平令人刮目相看,并荣获一等奖;同时我校还荣获团体一等奖。
●2009年6月30日至7月5日,在奥地利格拉茨举行的第13届机器人世界杯(RoboCup)比赛中,我校自动化系本科生程昊、陈伟、任雪玉,研究生董浩、矫健组成的“清华火神”队(指导教师:赵明国)获得人形TeenSize组季军。这也是我国参赛队伍中获得的唯一一块硬件组的奖牌。他们同时获得技术挑战赛的第三名。
●2009年7月20日,由网易联合TopCoder共同举办的首届“有道难题——网易暨TopCoder编程挑战赛”圆满落下帷幕。最终来自我校计算机系本科一年级的杨弋同学从17000名参赛者中脱颖而出,摘得桂冠,赢得了5万元现金大奖。而同样来自我校的俞华程和楼天城则分获二、三名,周冬获得第五名,唐文斌获得第七名。
●2009年8月5日, 2009“巨人杯”当代艺术院校大学生年度提名展在今日美术馆开幕,唯一的最高奖“巨人奖”花落我校美术学院邹流昊同学,他的获奖作品为油画作品《以路记路》。
●2009年8月16日,我校代表队在第四届全国大学生“飞思卡尔”杯智能车大赛中获得1个特等奖和1个一等奖。其中,工物系2006级本科生于昊、朱雪洲和汽车系2007级本科生张凯琦组成的“三角洲光电队”获得光电组特等奖,汽车系2006级本科生曾龙、方川、魏弘川和工物系2007级本科生吴笃蕃组成的“三角洲CCD队”获得摄像头组一等奖。
●2009年8月6~18日,在日本东京举行的第20届大学生国际设计竞赛暨IDC2009机器人大赛中。我校4名自动化系本科生于洋、杨文韬、徐迪、张小聪所在的小组均进入了八强。其中,2007级本科生杨文韬和美国MIT、日本东京电机大学以及泰国朱拉隆功大学学生组成的四人小组获得大赛冠军。
●2009年8月末,我校代表队获得第七届周培源全国大学生力学竞赛团体赛唯一的特等奖。我校代表队组成人员有:领队兼总教练高云峰副教授(航院);材料力学实验教练胡德贵高工(航院)、蒋小林高工(航院);理论力学实验教练王波高工(航院)。队员梁斌(航院航 61)、汪利(土木系结73)、黄萧(航院航62)、陈丹(航院航71)、林瑞佳(土木系结72)。
●2009年9月22日,我校计算机系索岳获首届“微软杯”IEEE中国学生论文大赛第一名。索岳的获奖论文是“Open Smart Classroom: Extensible and Scalable Learning System in Smart Space using Web Service Technology”。大赛由IEEE中国联合会与微软亚洲研究院联合主办,这也是IEEE首次在中国举办此类竞赛。
==============================================================================================

在首届中国理论计算机科学人才培养研讨会上,第二期清华大学理论计算机科学讲席教授团组首次集体亮相——这20位国际上理论计算机科学的知名学者,包括美国国家科学院院士4名、美国国家工程院院士1名、美国人文科学院院士2名、奈望林纳奖(Nevanlinna Prize)得主2名,齐聚清华园共同探讨如何培养中国的理论计算机科学的顶尖人才,并与清华学生进行了面对面的交流和探讨。

  这是国际理论计算机科学领域又一次难得的盛会。

  从姚期智先生2003年作为首期讲席教授团组成员来到清华以来,清华理论计算机科学的事业在一步一步扎扎实实地向前推动。2003年,姚期智先生领衔的 10位国际知名的华人学者加盟清华大学首期理论计算机科学讲席教授团组,为清华,也为中国的理论计算机科学开启了新的篇章;2004姚先生毅然离开普林斯顿大学,来到清华做全职教授,开始在清华探索中国的“图灵之路”;2006年姚先生创建清华大学软件科学实验班,以自己在国外多年的理论研究与教学经验为基础,借鉴国外计算机教育的先进方法,结合世界上最优秀的软件研究院之一--微软亚洲研究院资深专家的实践经验,致力于从根部开始着手培养具有国际一流水平的清华的理论计算机科学拔尖创新型人才;2007年,姚先生创办清华大学理论计算机科学研究中心以开展各项工作,同时开始积极筹划组建由20位国际知名学者组成的第二期讲席教授团组为人才培养创造国际一流的环境;2008年,姚先生开始招收“预研班”学生,从软件科学实验班的高年级的本科学生中里挑选出11名学生组成预研班,为他们在研究生实验室安排了独立工位,根据学生情况进行因材施教的个人化特别培养。更为难得的是,在推动理论计算机科学在清华全面发展的同时,姚先生亲自为学生制定培养方案,编写教学计划,并亲自为本科生和研究生上课,具体指导他们进行学术研究。
  经过4年的努力,目前,清华大学理论计算机科学从本科生到研究生乃至博士后已经形成了一条完整的培养线。教学研究管理初具稳定规模,成为国际上知名的理论计算机科学中心,综合实力在该领域达到世界前列。
  为了培养具有国际一流水平的计算机领域的拔尖创新型人才,姚期智先生密切联系当前国际上理论计算机科学一流的学者,共同参与到理论计算机科学人才培养的各项工作当中。事实证明,由这些学者组成的讲席教授团组,在中国“图灵之路”这项充满希望和挑战的道路上发挥着重要作用。
  首届讲席教授团组:理论计算机科学在清华从无到有的见证者
  由于深切感受到了理论计算机科学研究的欠缺给整个计算机学科发展带来的不利影响,清华大学计算机系的张钹院士和时任系主任的周立柱教授向学校提出希望通过清华大学讲席教授团组的方式引进国际知名的理论计算机科学学者,给计算机科学的研究带来新的动力。
  2002年,当张钹院士和周立柱教授计划邀请姚期智先生回国创办一个理论计算机科学讲席教授团组的时候,还没有预见到,当年这样的一个筹划会在几年之后给中国理论计算机科学的发展带来历史性的机遇。
  清华校友、香港城市大学教授邓小铁受托帮助联系国际计算机界最高奖项“图灵奖”获得者、美国普林斯顿大学威廉及爱娜麦克里工程及应用科学讲座教授姚期智先生到清华做讲席教授,领衔理论计算机科学领域的讲席教授团组,姚先生颇为痛快地答应了。
  随后的工作进展迅速地进展着。在清华计算机系应明生教授、马少平教授等人积极的联系和推动下,姚先生在接受邀请之后,进而邀请了堵丁柱、蔡进一、姜涛、葛可一等10位旅美华人科学家,组建了清华大学理论计算机科学的首期讲席教授团组,这里面几乎包囊括了所有海外华裔中最为出色的理论计算机科学家。2006年底首期讲席教授团组聘期结束,但他们大多还和清华理论计算机研究中心(以下简称“中心”)保持着紧密的联系,共同进行人才培养和科学研究。
  由于当时的理论计算机科学在中国的研究基本上是空白,姚期智和其他的讲席教授组成员为启动这一领域的研究倾注了大量的心血。
  为了弥补学生在理论计算机科学知识方面的欠缺,除了一些讲座和学术报告之外,他们每人利用每年到清华至少工作一个月的时间,为同学们开设了《算法分析与设计》和《计算理论导论》两门课程。课程不仅侧重基础知识,而且在课上,教授们还会把自己研究领域的最新进展介绍给同学们,与同学们共同讨论下一步的发展和研究方向,很多颇有价值的研究成果就是这样在这样的课堂上产生了。
  为了根据学生不同的特点使得学生获得最为具体的指导,这10位教授与当时的十余名学生双向选择,每人固定指导1-2位博士生。通过派学生出国到导师所在学校或研究机构学习、讲席教授每年到清华讲课,以及平时的电话和网上沟通对学生进行具体的指导。
  2004年,在杨振宁先生诚挚的邀请和清华校方的努力下,姚期智先生毅然地辞去了普林斯顿大学的终身教职,来到清华大学做全职教授。这个决定和行动意味着清华的理论计算机科学发展获得了一个前所未有的开创性局面,而姚先生的决心和行动也给讲席教授团组的工作带来了更大的推动力,“我被姚先生离开普林斯顿大学全职到清华工作的决心所深深打动了。同时我认为,我们有能力帮助国内的大学在理论计算机科学方面有所突破,而这所大学,我想最好的选择就是清华了。我有机会和姚先生旗下的两位博士研究生进行了非常紧密的合作。我认为,他们是我从事这个领域的研究20年以来遇到的最好的学生。”首期讲席教授团组成员、美国康斯威星大学教授蔡进一说。
  在姚先生、蔡进一和其他讲席教授团组成员的指导下,2005级博士生陆品燕逐渐在国际理论计算机科学领域崭露头角。他先后在理论计算机界的最高会议STOC和FOCS,计算复杂性理论的最高会议CCC,算法设计方向的最高会议SODA等发表了论文,并在欧洲理论计算机重要会议ICALP 2007上发表一篇有关全息算法(Holographic Algorithm)的论文,该论文解决了该领域的一个基础性难题,并获得欧洲理论计算机协会颁发的最佳论文奖(Best Paper Award),这也是该奖项首次颁给华人学者。
  截至目前,陆品燕在博士阶段已经在国际上发表的14篇学术论文中,有11篇是在讲席教授团组的指导下完成的。陆品燕非常喜欢在姚期智领导的这个团队里面进行科学研究,他说:“不同的教授对于同一个学术问题会有不同的理解,研究的思路也是很不同的,在这样的研究团队中,我会接触到很多不同的研究方式,并且慢慢形成自己的思路。此外,在众多研究风格不同的讲席教授组成员当中,学生总可以根据自己的兴趣和喜好找到一位作为自己近期研究的指导教师,这也是讲席教授团组的一个很大的好处。”
  2008年暑假,陆品燕又一次到美国威斯康星大学与蔡进一教授共同进行研究,这是他第三次到威斯康星大学。他这样形容这种合作的研究状态:“蔡老师非常全身心地投入到指导我的工作当中,在一起的时候我们几乎每天都会有讨论,研究需要的时候,甚至包括周末,下班时间和吃饭时间等,我们的很多思路和结果都是在这样的思维碰撞中产生的。从他身上,我学到了很多做学问的态度和做学问的方法。蔡老师人也很不错,跟他在一起,你不会觉得自己是一个学生,更多的是觉得彼此就是科学道路上的合作伙伴。”
  在姚期智和讲席教授团组的指导下,2003级博士生陈汐先后有3篇论文被理论计算机科学界最重要的两大会议——STOC和FOCS录用,一篇论文入选计算机算法领域首要会议SODA 2007。他与讲席教授团组成员、香港城市大学邓小铁教授合作完成的Settling the Complexity of 2-Player Nash-Equilibrium一文出色地解决了理论计算机科学的著名难题——二人博弈中纳什均衡点的复杂性问题,并因此获得2006年度FOCS最佳论文奖。
  同样是在2006年,姚期智领导的理论计算机科学研究团队有3篇论文入选理论计算机科学领域最顶级学术会议FOCS,不仅实现了国内学者在该会议上“零的突破”,入选篇数甚至超过了美国计算机科学领域的“超一流”大学加州大学伯克利分校。2006年,姚期智领导的团队还为国内计算机学者填补了在《美国科学院院刊》上发文的空白。
  2007年,美国纽约州立大学石溪分校教授葛可一在首期讲席教授团组结束后在美国取得进修假,在中心工作访问一年,除了开设一门研究生课程外,还主持每周的以英语演说的论文研读课,并继续和清华研究生共同合作进行研究;美国明尼苏达大学教授堵丁柱现在还和中心联合培养博士研究生,每年定期访问中心2个月以上,中心的博士生马长存现正在堵丁柱那里进行学术交流访问,刚刚毕业的博士生程永席也将到堵丁柱那里做博士后的研究;美国加利福尼亚大学教授姜涛正在继续指导中心的博士生肖晶进行博士论文的研究等等。
  “姚先生领导的清华理论计算组的学生以及其他几位讲席教授团组的教授都完全热心地投入研究工作。姚先生为大家提供了非常好的工作环境,包括研究室,国外访客等,即使是美国一流大学的计算机系也往往难以具备如此理想的环境。”葛可一说。
  第二期讲席教授团组:与姚期智携手推动清华理论计算机科学迈向世界一流
  秉承第一期讲席教授团组成功的经验,姚期智先生从2007年开始联系和组建清华大学理论计算机科学研究中心的第二期讲席教授团组。该讲席教授团组于2008年1月正式成立。现在这20名国际知名的学者,正在和中心合作培养20名博士生。
  这20名国际知名的学者中,有的跟姚先生相识多年,有的在学术上跟姚先生保持着密切的交流,而其中的绝大部分,更是在近年实地访问过中心,进而被姚先生领导的科研团队的学术实力和学术氛围所吸引。
  目前,第二届讲席教授团组教授的课程构架,以及以“一对一”的形式进行博士生的指导等工作正在进行中。在运作形式上体现为:既要求讲席教授团组成员每年有固定的时间段来清华访问,也保证博士生在就学期间有机会出国出境进行学术访问。
  在通过中心严格的研究生资格考试之后,中心的每位博士研究生就学期间将有数次机会出境学术访问,中心规定第二次出境学术访问需间隔上次出境访问一个学期,单次出访时间最长不超过6个月。
  10月13日,在清华大学理论计算机科学人才培养研讨会的首场学术报告中,美国国家科学院院士、加州大学圣地亚哥分校首席科学家Ronald Graham以一口流利的中文作为开场白,令全场大为惊诧。
  他为在场的师生做了题为“斯坦纳树”的学术报告,幽默的语言,恰到好处的讲解,引得场内不时发出会心的笑声。学术报告的最后,他还展示了一张具有特殊意义的照片——时任国家主席的江在一次接见中与他握手。
  软件科学实验班2006级学生朱晨光向Ronald Graham教授提问,他在做了初步的回答之后告诉学生:“茶歇的时候请你来找我,我会继续和你讨论这个问题。”
  在和记者的交谈中,这位长着一头金发、富有幽默感的大牌学者时不时蹦出几个中文的词汇——原来这位美国科学院院士是中国的老朋友,已经数次来访中国,先后到过香港、北京、上海、济南等地。而此次的清华之行,已经是他第5此来访北京了。
  谈起为什么要加入姚期智先生领导的清华理论计算机科学讲席教授团组,他说:“我和姚先生相识已久。姚先生在清华的出色工作已经显示了他的卓越能力,并且,他的决心让人敬佩。此外,清华学生具有的聪明才智也是我加入这个团队的重要原因。我正在尝试以我自己的能力去帮助他。”
  对于姚期智先生在清华致力于培养理论计算机科学“明日之星”的种种举措,Ronald Graham非常赞成,他说:“我跟姚先生正在筹划共同培养清华的学生,相信我跟清华理论计算机科学研究中心会有很好的合作。”
  在采访中,几乎所有的学者在交谈中都对清华大学理论计算机研究中心的学术水平和学生素质给予了很高的评价。加州大学伯克利分校的Luca Trevisan教授说:“我2006年首次来到清华大学,在与姚先生和他的学生接触中,姚先生的科研态度和清华学生的优秀才能给我留下了深刻的印象,这也是我为什么后来加入姚先生领导的讲席教授团组的重要原因。”
  2008年3月,Luca Trevisan教授受邀加入讲席教授团组并第二次来到清华,发现中心的科研队伍比以前还要壮大,学术氛围更加浓厚。以出席研讨会为契机,他第三次访问清华,并将在清华用一个月的时间指导学生。“我会给学生做一些学术报告,与他们探讨科研中遇到的问题。目前,我正在给2008级博士生乔友明以科研上的指导。” Luca Trevisan教授说,“希望我与姚先生带领的科研团队的合作,能够促进加州大学伯克利分校与清华大学计算机领域学生的交流与合作。”
  讲席教授团组成员、普林斯顿高等研究院教授Avi Wigderson已经是第三次到访清华了。这位奈望林纳奖(Nevanlinna Prize)得主在研讨会上以“ The Art of Reduction”为题向师生介绍了自己研究的最新进展。他说:“我认识姚先生也许有25年了,此次我将在清华停留一个月,与学生们一起讨论和研究问题。”
  谈到此次研讨会,Avi Wigderson教授说,理论计算机领域如此众多的一流学者聚在一起是一个很特别、很难得的机会,学生可以从中学到很多,受益匪浅。他还特别提到:“姚先生为在中国建立一个高水平的理论计算机科学研究中心付出了很大的努力。这个中心将在未来吸引更多的学者来这里工作,共同培养优秀的学生和进行科学研究。”
  讲席教授团组成员、麻省理工学院教授、奈望林纳奖获得者Madhu Sudan说:“姚先生是一位令人尊敬的学术大师。在这里,我看到清华的学生是非常有潜力和希望的。我相信这次他们有机会和来访的学者们讨论,会对他们将来的学术发展意义非常。”
  2006级博士生张家琳在2008年2月-5月访问了布朗大学,与Maurice Herlihy教授一起就分布式计算这个领域进行了研究。“Maurice Herlihy教授在学术上对学生要求很严格,但是为人非常和蔼可亲。由于他也主要从事分布式计算这方面的研究工作,所以他能够给我很具体的指导。”张家琳说。借中国理论计算机科学人才培养研讨会之机,Maurice Herlihy教授这次将在中心和张家琳继续进行学术研究工作。
  在姚先生和讲席教授组成员的共同支持下,2008年9月,中心已经送俞炜同学去麻省理工学院的Madhu Sudan教授的研究团队访问5个月。近期将送戴德承同学到普林斯顿大学Sanjeev Arora教授处访问5个月。
  合作的讲席教授团组成员以及相对应指导的学生,会定期把学生的科研进展情况汇报给中心。
  在姚先生的带领和组织下,通过讲席教授团组对学生的指导,与学生的互动和交流,不仅能够培养学生出色的研究理念和方法、完善的科研素质,还能够在博士生阶段就给学生一个国际化的舞台和视角,为他们今后在国际上的发展奠定更为坚实的基础。
  以讲席教授团组的形式,借助全世界最为杰出的理论计算机科学学者的力量为清华和中国培养理论计算机科学杰出人才的这种模式,已经取得了显著的成效。
  2007年全年,清华大学理论计算机科学研究中心在国际期刊或者是国际会议上发表论文31篇,其中16篇是在顶级会议或者是知名期刊上发表的;而2008年1-6月仅半年的时间,中心在国际期刊或者是国际会议上发表论文19篇,其中有12篇是在顶级会议或者是知名期刊上发表的。
  现在,在中心所在地,清华大学信息科学技术大楼的4区6层,经常会有来自世界各地的知名学者来访,其中有数位图灵奖获得者,还有来自世界各地的学者做博士后。在实验室,在会议室,不时闪现的各种肤色的面孔,告诉人们,这里已经成为理论计算机科学一个国际上的要地。

============================================================================

2009年度腾讯创新大赛全国总决赛成功举办

2009年度腾讯创新大赛全国总决赛,于7月28号在腾讯深圳总部成功举办。腾讯公司联席首席技术官熊明华先生和腾讯公司副总裁奚丹先生与云集来自全国最顶尖的精英参赛选手进行了深入座谈交流,他们均是由全国预赛筛选和一流高校精心选派的高手组成,代表了国内同类比赛的最高水准。

来自16所高校67名顶尖选手参加了总决赛的技术精英赛和创新精英赛。技术精英赛的参赛选手展现出了高超的程序设计能力,北京大学秦腾、清华大学俞华程等同学最终胜出。创新精英赛的参赛选手与腾讯资深专家进行了精彩纷呈的现场答辩。比赛结束后,选手们仍意犹未尽,继续激烈讨论,久久不愿离开赛场。腾讯公司国际业务高级执行副总裁David Wallerstein、腾讯研究院院长郑全战博士、腾讯公司人力资源部副总经理马海刚和腾讯公益慈善基金会执行秘书长窦瑞刚先生为获奖同学颁奖并祝贺。

2009年度腾讯创新大赛是第三届腾讯举办的全国高校高端创新大赛,腾讯公司表示将持续打造和举办此类高水平的大赛,让更多的大学生展现才华和提升能力。腾讯公益慈善基金会捐助了本次大赛的奖金,号召青年大学生要更加积极的参与到社会公益事业当中去。

附:2009年度腾讯创新大赛全国总决赛赛果

技术精英赛赛果:

技术精英赛全国总决赛一等奖:北京大学秦腾

技术精英赛全国总决赛二等奖:清华大学俞华程、清华大学郭华阳

技术精英赛全国总决赛三等奖:清华大学唐文斌、同济大学刘城、清华大学周冬

技术精英赛全国总决赛优秀奖:清华大学杨弋、北京大学王靖、北京大学杨浩、华南理工大学李植炜、复旦大学唐铕泽

创新精英赛赛果:

创新精英赛全国总决赛一等奖:北京大学李文

创新精英赛全国总决赛二等奖:北京航空航天大学宫晓妍

创新精英赛全国总决赛三等奖:南京大学解涛、北京大学何浪

高校最佳组织奖:

北京大学和清华大学作为本年度腾讯创新大赛的重要支持高校获得高校最佳组织奖。

==============================================================================

2007 ACM 清华大学----杨弋

 2007年全国信息学奥林匹克竞赛的冠军又一次光临了杨弋,这个来自安徽师大附中的男孩在该领域独占鳌头。别人都评价他“聪明”,而他自己却说“我没什么特长”。跟他的谈话在晚风中落下浅色的痕迹,他思想的小宇宙并不亚于其在计算机方面显露的才华。  
       杨弋是个活泼的大男孩。记者好不容易才在球场边逮到打篮球的他。他有些羞涩,几经劝说,才接受了采访。杨弋在跟人对话时会注视着你的眼睛,但是说完一句话又会害羞地低下头,脸上一副思考的表情。  
       坐在球场边的凳子上,杨弋从他第一次接触电脑开始谈起。那是他上小学的时候,由于当时的电脑配置都很低,所以除了打字,几乎就不能干别的。后来,电脑慢慢升级了,杨弋也开始玩游戏,学编程。那时候,程序对杨弋来说就像是游戏,他一下子爱上了这种“游戏”。  
别人眼中的“超人”  
       小学六年级时,他与初中的学生一起参加全国信息学分区联赛,获得了一等奖;2002年,上初中的杨弋第一次参加了NOIP,取得了全省一等奖的好成绩。 2004年,他入选安徽省队并在当年的全国信息学奥赛中获得第16名,入选国家集训队;在2005年的IOI国家队选拔赛中,他获得第五名,因国家队仅有 4个名额,杨弋很遗憾地落选了。2006年,杨弋圆了国家队之梦,以NOI第一名和APIO第一名的成绩入选国家队。今年,他又以617分的成绩再次高居 榜首。NOI结束之后,他将代表中国参加IOI比赛。  
       在本届NOI最佳女选手获得者陈瑜希的眼里,杨弋是个“超人”,他在比赛中往往比第二名多出很多,他的地位几乎是无人能够撼动的。而杨弋却有着自己的烦恼,他郑重地说:“我觉得要把一个人当人看,我们所认为的完人是不存在的。”  
       由于安徽师大附中只有杨弋一个人参加了信息学奥赛,他坦言自己和同学的生活节奏是不同的,参加完比赛回到学校,同学会拉着他说:“下午要考试了。”没有人关注他在干些什么。他心里淡淡的失落是写在脸上的。  
       我安慰他说:“有得必有失!”杨弋立刻兴奋地说:“我去年在冬令营面试的时候就是因为把这句话说完,从而超时而扣分的。”2006年NOI冬令营中,杨弋虽然论文分数不高,但由于基础扎实,仍然稳居第一。  
       对杨弋来说,他的未来注定是与信息技术联系在一起的。他在2006年已经被保送清华,而之所以又参加2007年的NOI,这个男孩心里还有另一个梦——多一次参与IOI的机会。如果今年的IOI失败了,他还可以卷土重来。  
重视思维训练的男生  
       杨弋说自己每周花在练习题上的时间大概有20~30小时,有时候甚至是40小时。他最初接触的是LOGO语言,后来迷上了BASIC、PASCAL和C语言,从简单复制代码、检查程序输出进程,到后来热爱编程,花费了大量时间在学习语言、编程上。  
       由于很小就曾在IOI选拔赛中取得全国第五名的好成绩,这让他觉得,自己可以顺着这条路继续走。“那么高的起点,谁又会放弃呢?”在初中刚学习信息技术时,他也走过弯路。最初是不停地做新题,可是到考试时发现,连基本的题目都做不对。于是,他转变思路,加大基本题型的练习量,成绩一下子提了上去。他说自己并不花费太多时间在特别难的题目上,因为这会使他产生一种挫败感。但是为了提高的各种编程能力,杨弋会做一些有助于自己提高的题目。  
       杨弋觉得相比较于老师的引导,自学更为重要。他喜欢和同学交流,产生的火花能够帮助他继续思考,形成自己的思路。杨弋也喜欢上论坛跟别人讨论,但他又觉得现在论坛过多,很多问题都是浅尝辄止,不像以前论坛少时大家讨论得那么充分了。杨弋曾经在PKU的论坛上力挫群雄,获得月赛的冠军。另外,还在SGU、 SPOJ等论坛征战。在TOPCODER中,杨弋截至2007年6月的得分是2900。这使杨弋在该领域内人气很旺。  
       问到杨弋最擅长的题目是哪种类型的,他立刻纠正了我的说法:“只有在你去做的过程中,你才知道自己是不是擅长这道题目的类型,不可能你没有做题先去把它划分类型。”杨弋很重视思维的过程。  
       他也给刚刚参加NOI的同学提了建议:“不要慌着做新题,看到别人又学会了一些新知识、新思路,自己肯定会有一点压力。不过不要着急。考卷还是基本类型和题目,关键是平时要训练自己的思维方式。”  
       杨弋觉得参加考试是一种很好的锻炼。“因为平时做练习题和真正的考试是不一样的。”但是,他不赞成大家把所有时间都花在练习和训练上,因为做练习题是一个枯燥的过程,过于疲劳可能会使人不想再参加比赛,丧失了乐趣的比赛就会失去动力。  
      杨弋的文化课成绩也是在班里名列前茅的,虽然他为自己找了一个致命的缺点:“不喜欢给卷子纠错。”他喜欢思维的跳跃,喜欢接受新的知识。他一直用自己的步骤和方法来安排学习,而且似乎效果还不错。  
充满辩证的未来  
       问到杨弋的爱好,他腼腆地说:“我没有什么特别坚持的爱好,就是没事去踢球或进行一些其他的球类运动。”停了一下,思索片刻后很认真地说,“其实人一辈子能干好几件事已经很不容易了。”  
       杨弋喜欢打游戏,参加NOI时,会跟别的选手对战“CS”。杨弋在家也是个可爱的孩子,妈妈说:“以后当大老板吧!”杨弋会笑着说:“那怎么可能?”  
       在团体对抗赛中,杨弋是安徽队的指导,他不停地跑前跑后,跟选手们交流,时而专注地看着大屏幕。这个时候的他,更像是个驰骋在计算机世界的孩子,享受着自己的付出和汗水带来的成功与乐趣。  
      明年的NOI中,他将具有出比赛题的资格。用他的话说:“可以折磨别人了。”他说,自己没有座右铭,也没有偶像。他还没有发现自己觉得希望成为的那种 人。记者问他是否崇拜自己,他却连连摇头。他说:“现在无法去设想未来,只有走到了那个阶段,才会有所取舍。简单的设想可能是无法实现的。”这句话充满了 辩证法的味道。

我市18岁的杨弋现在是安师大附中一名高三学生,但从小就天赋异常的他已获得过很多的奖项和荣誉。

早在6岁时,杨弋就因巧解“八阶双重幻方”的最小和获得了中央四部委授予的“21世纪之星”称号;小学六年级的时候参加安徽省中学生信息学竞赛,获得第 10名;2004年,获得全国信息学奥林匹克竞赛银牌,还在读初中的杨弋被保送清华大学;2006年和2007年连续两年获得全国信息学奥林匹克竞赛第一名,并入选国家队;2007年获得第19届国际信息学奥林匹克竞赛金牌,总分排名全球第二;在2008年全球高中生计算机程序设计大赛决赛中,杨弋以 1499.37的高分夺得全球第一名。

采访杨弋的时候,正是其他高中生为高考而紧张冲刺的时候,杨弋却显得异常轻松。长着一张娃娃脸的杨弋是个憨厚可爱的大男孩,看上去和一般中学生没什么两样。“你学习是不是特别用功刻苦?” 杨弋回答:“还好吧,我每天一般学习5-6个小时,就是特别喜欢睡觉,但学习的效率挺高。”

“杨弋总是把试卷做完才肯吃饭,不得到100分不满足。”杨弋的母亲告诉记者,杨弋从小就特别爱学习,他在上小学前基本上达到了小学五年级的水平。杨弋的母亲是小学数学老师,她经常从学校带回一些试卷给杨弋做。

“我对学习有兴趣,兴趣是我最好的老师!”杨弋如是说。读小学一年级时,家人送给他一台“小霸王”学习机,光是看说明书,他就几乎把学习机的全部功能学会。发现儿子对电脑有着特别的天赋,二年级时,父母又为他买了台486电脑。从此,他开始一头扎进了这门科学的海洋里,计算机成绩一直名列芜湖市前茅。杨弋不仅具有计算机编程特长,而且在德、智、体、美、劳各方面全面发展,小学升初中的会考中获得全市状元。2006年还获得芜湖市“三好学生”称号。

由于经常在国内国际大赛中拿奖,杨弋现在已经把获奖看得很淡了。但谈起自己能被选为一名奥运火炬手还是很自豪的。杨弋兴奋地说:“现在我特别喜欢每周的两节体育课,火炬来芜湖传递的日子越来越近,为那神圣的一刻,我有信心以最佳的状态当好奥运火炬手!”

=======================================================================================

2009722日)网易"有道难题前三名优胜者背景介绍 

杨弋,安徽芜湖人,19岁的他目前是一名就读于清华大学计算机专业的本科一年级学生。翻看杨弋的个人简历,让人印象最为深刻的当数那一长串他曾获得的荣誉,以及参加各类竞赛所取得的骄人成绩。

杨弋6岁时便获得了由中央四部委授予的"21世纪之星"称号;还在读小学六年级的杨弋,就曾代表学校参加安徽省中学生信息学竞赛,与比他大三、四岁的孩子同场竞技,并取得了第 10名的好成绩;小学升初中的考试中,他还凭借优异的成绩成为芜湖市的会考状元。 

  2004年,身为一名初中生的杨弋获得全国信息学奥林匹克竞赛银牌,并入选国家集训队。由于在计算机方面的突出成绩和才能,杨弋还取得了保送清华大学的资格。2006年和2007年,杨弋又连续两年获得全国信息学奥林匹克竞赛第一名;2007年获得第19届国际信息学奥林匹克竞赛金牌,总分排名全球第二;在2008年TopCoder全球高中生计算机程序设计大赛决赛中,杨弋又以 1499.37的高分成为世界冠军。

  此外,杨弋还获得过芜湖市"三好学生"等光荣称号,并在2008年被选为芜湖市的奥运火炬手,参与了北京奥运会火炬传递活动。

  "有道难题"编程挑战赛亚军:俞华程

  俞华程,1989年出生于浙江杭州,目前就读于清华大学计算机系。俞华程高中就读于杭州第二中学,自幼酷爱数学的他,曾在"华罗庚金杯"少年数学邀请赛(简称"华杯赛")中夺得过金牌。

"有道难题"编程挑战赛亚军:俞华程

  进入高中后,俞华程在计算机方面的天赋逐渐显露出来,他曾多次在NOI(National Olympiad in Informatics,全国信息学奥林匹克竞赛)的比赛中取得了上佳表现,因此入选了国家集训队,后被保送进入清华大学计算机系学习。在2008年,俞华程以558分取得IOI的金牌,总成绩为世界第一。 

  "有道难题"编程挑战赛季军:楼天城

  楼天城,1986年出生,浙江人。楼天城高中就读于杭州第十四中学,2004年成绩优秀的他获得了保送进入清华大学学习的机会,2008年开始进入全球唯一华人图灵奖得主姚期智院士所领导的清华大学理论计算机中心攻读博士学位。

"有道难题"编程挑战赛季军:楼天城

  楼天城是目前中国公认的大学生计算机编程第一人,由于近年来不断在国内外各类知名的计算机编程竞赛中屡获骄人战绩,被其他计算机竞赛的爱好者称为"楼教主"。高中阶段,楼天城就获得过全国青少年信息学联赛、全国高中数学联赛的一等奖,并于03年入选了国家集训队。此外,他还在IOI(International Olympiad in Informatics,国际信息学奥林匹克竞赛)的比赛中获得过过金奖。

  近年来,楼天成在TopCoder算法中国区竞赛以及ACM/ICPC中国赛区各站赛事中,均取得了第一名的优异成绩。同时,楼天城也开始在各类国际赛事中崭露头角,他先后参加了数十场ACM/ICPC等国际性的大型计算机编程竞赛,并在与全世界的编程高手角中屡屡获胜。在2008年,他获得了Google编程挑战赛的冠军头衔。

 

======================================================================

国青少年信息学奥林匹克联赛(National Olympiad in Informatics in Provinces 简称 NOIP)
出国参加国际信息学奥林匹克竞赛(International Olympiad in Informatics 简称 IOI)

选手竞赛用机上配备下列软件系统:   
操作系统:Linux,内核版本:2.4   
桌面系统:GNOME/KDE;   
浏览器:Firefox, Konqueror   
编辑工具:mcedit, vim, kate, kwrite, kdevelop, rhide   
编译系统: gcc ≥3.2.2, g++ ≥3.2.2, Free Pascal ≥2.0.1   
调试工具: gdb, ddd   
上述软件都配有英文说明文档。操作系统和编译系统的具体版本以及对各种编程语言的使用限制见附件1。对该附件的修改在每次竞赛至少5个月前公布。   

竞赛内容  
NOI竞赛的题目以考查选手对算法和编程能力的掌握为主。题目类型有以下三种:   
非交互式程序题  
非交互式程序题要求选手提交答案程序的源文件。该程序从一个正文文件中读入数据,并向指定的输出文件中写入计算结果。
非交互式程序题的题面包括下列内容:   

求解问题的描述 
输入文件名和输出文件名(可以是标准输入/输出)   
输入数据格式、输出数据格式、以及输入数据范围   
对程序使用计算资源的限制,以及其它可能的限制   

交互式程序题  
交互式程序题要求选手提交答案程序的源文件。该程序通过调用所提供的库函数实现数据的输入和输出。交互式程序题的题面包括下列内容:   

求解问题的描述   
库函数的功能、函数原型、以及获取和链接方式   
输入数据格式、输出数据格式、以及输入数据范围   
对程序使用计算资源的限制,以及其它可能的限制   

答案提交题  
答案提交题不要求选手提交程序的源文件。选手需要按题目要求,根据给定的输入数据文件生成一组输出数据文件。该组数据文件既可以是由选手的程序输出的,也可以是由选手手工构造的。当选手使用自行设计的程序生成题目答案时,其所使用的程序不应提交。答案提交题的题面包括下列内容:   ·

求解问题的描述  
输入数据格式、输出数据格式   
输入数据文件的获取方法   

对于交互式程序题和非交互式程序题,对选手程序使用内存大小的限制包括运行代码、程序运行时所需的栈和堆在内的所有工作内存的总和。当题面中没有给出对使用内存 的限制时,以选手用机的实际使用限制为准。对选手程序运行时间的限制一般均大于标准答案程序所需最长运行时间的50%以上,以避免测试中的超时判断误差。   

竞赛前的练习和标准化笔试题  

选手在正式竞赛前应有不少于2个小时的练习时间,以熟悉竞赛场地、设备和软件环境、以及答案提交方式。竞赛前的练习应安排在第一场竞赛的前一天。在赛前练习结束后,应安排不少于30分钟的时间进行标准化笔试题的测试。标准化笔试题包含单选题、多选题和填空题,题目涉及的内容包括计算机和编程的基本知识、NOI竞赛所使用的操作系统、编程工具等的使用方法,以及基本竞赛规则。标准化笔试题的成绩计入选手竞赛的总成绩。   

竞赛时间   
NOI的竞赛分为两场,每场竞赛的时间为5小时。两场竞赛之间应间隔一天。   

赛场纪律  

选手可以携带书写工具,如钢笔、铅笔等,以及手表和适量的衣物等进入赛场。有特殊情况需要携带其它物品者需事先取得竞赛委员会的批准。   选手不可以携带上述规定之外的其它物品,如纸张、书籍、食品、饮料等进入赛场。选手被严格禁止携带软盘、光盘、U盘等存储设备和介质,以及手机、电子辞典、PDA等电子及通信设备。凡携带上述被严格禁止的设备进入竞赛场地者,在竞赛开始后一经发现,无论是否使用,均以作弊论处,取消其该场竞赛的资格和成绩。   选手在竞赛中不得与其他选手交谈,不得干扰他人的竞赛活动,不得损坏竞赛设备。   选手在竞赛过程中如需入厕,需举手向赛场服务人员示意并征得允许。   

竞赛的开始和结束  
竞赛选手应佩戴选手标志,在竞赛前5分钟入场,按指定位置就座。竞赛在竞赛场地负责人发出竞赛开始的指令后开始。在竞赛开始前选手不得触动竞赛桌面上包括计算机、键盘、鼠标和试卷在内的任何物品。  

竞赛场地负责人应在竞赛结束前5-15分钟之间发出竞赛即将结束的提示,并在竞赛结束时间到达时发出竞赛结束的指令。在听到竞赛结束的指令后,除了获得加时补偿的选手外,其余选手应立即停止竞赛活动,并携带属于个人的物品离开竞赛场地。   

竞赛中的答疑  
选手在竞赛过程中对竞赛的题目、竞赛设备以及编程环境有疑问时,应举手向竞赛场地负责人或场地服务人员提问。   

选手在竞赛过程中遇有计算机或软件工具故障,或其它妨碍竞赛的情况,应及时举手向竞赛场地负责人或场地服务人员报告。竞赛场地负责人或场地服务人员应及时处置。对于妨碍选手竞赛超过3分钟的,应记录在案并给以加时补偿。   

答案的提交  
选手完成的赛题答案必须按题目的要求保存为规定格式的文件,并存放在规定的目录下。选手提交的程序源文件必须不大于100KB。答案提交类题目的答案文件不得超过题目规定的大小;题目未规定大小的必须不大于100KB。未按规定的格式、名称和大小生成和保存答案文件的将视为未提交,并且不被评测,因此不能得分。  

对于程序设计题,选手提交的答案不得包含下列内容:   
试图访问网络   ·
使用fork或其它线程/进程生成函数   ·
打开或创建题目规定的输入/输出文件之外的其它文件   ·
以任何方式对标准输入/输出文件的重定向   ·
运行其它程序   ·
改变文件系统的访问权限   ·
读写文件系统的管理信息   ·
使用除读写规定的输入/输出文件之外的其它系统调用   
违反上述规定中的任何一项的程序将被视为违规,因此不被评测,不能得分。   

评测和成绩发布
除另有说明者外,选手提交的程序设计题将在Linux系统上使用下列编译命令进行编译:   ·
C程序: cc -static -o <程序名> <程序名>.c -lm   
C++程序:g++ -static -o <程序名> <程序名>.cpp -lm   ·
Pascal程序:/usr/local/bin/ppc386 -XS -o<程序名>c <程序名>.pas   

未能通过编译并正确生成可执行文件的程序在该题目上不得分。能够通过编译并正确生成可执行文件的程序将在与选手编程环境相同的系统平台上,在题面规定的限制条件下运行和评测。对于程序设计题,选手答案的得分将取决于结果的正确性、算法的效率、以及程序运行的效率。评测将使用多个测试点,以区分选手答案的正确程度和效率。在正确性和效率方面都符合题目要求的答案将获得该题目的满分。算法和程序实现正确,但效率较低的答案也可能在若干测试点因超时而无法获得分数。   

选手的程序必须在程序执行结束时显式地返回0。返回其它值的程序将被认为是结果不正确,并因此不能得分。   对于答案提交题,只对选手答案的正确性进行评测。   

评测结果将在竞赛结束后150分钟之内,以成绩单的形式发给选手所在队的领队签收。成绩单上将标出选手各题在每个测试点上的得分,以及未得满分的测试点的错误信息,参见附录。选手每道题的得分为其在该题各个测试点上的得分之和。选手每天的得分为其在当天各道题上的得分之和。   

复测  
选手在接到成绩单后可以在规定的时间之内,在其竞赛时使用的计算机上对其答案进行复测。选手在竞赛结束时所提交的答案依然保存在题目所规定的文件目录中,复测所需的测试数据和答案在复测开始前将被下发到选手计算机上指定的文件目录中。   
复测时,选手可以和领队或其他队员进行讨论,但不得妨碍其他队的队员的复测活动。   

申诉  
复测完毕后,竞赛选手对于评测成绩有异议的,可向科学委员会提出申诉。申诉须在复测结束后3小时之内,由竞赛选手本人提出。提出申诉的竞赛选手须按规定填写申诉表(附件2),由本队领队签字后提交给现场评测人员或科学委员会成员。   申诉必须依据竞赛选手本人在竞赛时提交的程序或答案以及在复测时获得的结果提出。   

申诉的受理 
科学委员会在接到选手的申诉后应及时研究,并决定是否受理。对于受理的申诉,科学委员会应尽快做出处理,并使用申诉处理表(附件3)将处理结果书面告知申诉人。对于改变了选手得分的申诉处理,科学委员会在处理完毕后应向申诉人发放新的成绩单,并按新的得分计算申诉人的竞赛成绩。   对于不受理的申诉,科学委员会应在选手提交的申诉表中注明拒绝受理的理由,并尽快将申诉表退还申诉人。申诉人如对科学委员会不受理的决定有异议,并有新的理由和证据的,可以再次提出申诉。   

下列申诉将不被受理:   ·
以修改过的程序或答案为依据的   ·
没有复测结果支持的   ·

超过申诉时间的   ·
对评测结果中的超时有异议,且复测结果的运行时间与题目时间限制之差小于题目时间限制5%的。   对于以修改过的程序或答案为依据提出申诉并且声称依据原始程序或答案的,一经查实,将对申诉人及其领队给予警告。情节严重者将取消申诉人当天的竞赛成绩。   

附则   
本规则自2007年6月开始执行。   
本规则由科学委员会负责解释。   
全国青少年信息学奥林匹克竞赛(NOI)是由中国计算机学会主办的一项面向全国青少年的信息学竞赛和普及活动。也是与联合国教科文组织提倡的国际信息学奥林匹克竞赛,同步进行的一项竞赛活动。
NOI 网址:http://www.noi.cn

转载自原文链接, 如需删除请联系管理员。

原文链接:【IT竞技、IT 峰会】,转载请注明来源!

0