关闭菜单 参考资料…… William & 玛丽
w m菜单 关闭 William & 玛丽

竞争激烈的编程团队准备参加世界总决赛

Three programmers/one keyboard
三个程序员/一个键盘 为了参加计算机协会国际大学生程序设计大赛的世界总决赛,迈克尔·克里斯滕森(左)和亚伦·杜福尔在白板上解决了一个计算机程序设计问题,队友布雷特·库利正在为第二个问题输入解决方案。金牌队教练黛比·努南在场边观看。约瑟夫·麦克莱恩摄

有时金牌队的人会说“世界”其他时候,他们说“决赛”。

这两个术语都指的是计算机协会国际大学生编程竞赛(ACM-ICPC)的世界总决赛,该竞赛将于5月在波兰华沙举行。金队要走了——他们将与地球上最顶尖的年轻计算机程序员竞争。

金牌团队是Michael Christensen, M.S. 12, Brett Cooley和Aaron Dufour。他们三人在11月初的中大西洋地区比赛中表现出色,在166支球队中排名第二,从而获得了代表威廉玛丽参加决赛的席位。(在地区赛中,威廉玛丽也有另一支队伍——绿队。)从那以后,金队一直在华沙进行训练,他们将在那里与110支世界顶尖的学生程序员队伍竞争。

威廉玛丽学院计算机科学系的讲师黛比·努南(Debbie Noonan)说,这是威廉玛丽学院的团队迄今为止第一次取得进展。努南在过去的15年里一直执教该学院的竞技编程团队,她将和她的丈夫、计算机科学系教授鲍勃·努南(Bob Noonan)一起陪同金队前往华沙。

努南教练说,世界赛的情况将与地区赛类似。每个三人小组只提供一台电脑和键盘。每个团队都要解决8个问题,然后开始计时。在规定时间内正确解决最多问题的队伍获胜。

克里斯滕森说:“竞争的很大一部分是弄清楚首先要做什么,谁应该做。”

划分并编写代码

 

为了解决这些问题,该团队应用了算法,即一步一步的指令,这是人机交流的基本词汇。努南说,在比赛中,团队中的两名成员通常在纸上工作,而第三名在键盘上工作,这样团队在任何时候都至少在处理两个问题。一些选手尝试让队里手指最快的人担任指定的打字员,但金牌团队已经想出了自己的办法来决定谁来使用键盘。

库利说:“不管打字速度和其他因素如何,让思考问题并提出算法的人来打字通常是有用的。”“很多时候我们会在纸上写很多代码,因为只有一台电脑。但你不必一行一行地写出来。”

当团队认为已经解决了一个问题时,解决方案将被发送给评委进行审查。错误的解决方案返回的注释可能来自世界上最糟糕的图灵测试:“不正确的输出”、“错误的输出格式”或“超出运行时间”。努南说,参赛队伍每收到一个糟糕的解决方案,就会受到惩罚。

没有人会用“不被看好”这样的词,但总有一种感觉,威廉和玛丽在世界总决赛中表现得有点超群。在中大西洋地区比赛中,许多被金队击败的队伍来自拥有庞大计算机科学系的学校,这些学校派出了多达9支队伍参加地区比赛。克里斯滕森刚刚参加完一轮面试回来(顺便说一下,他已经接受了微软的一个职位),他在世界总决赛中的位置引起了很多人的兴趣。他了解到,有几所大学校开设了学分制课程,目的是让一支球队进入世界总决赛。

William & 玛丽并没有足够的资源让团队进入世界,但正如Cooley所说,“CS部门给了我们成功和做得好的东西。”努南解释说,成功的基础是该部门的算法分析课程。

她说:“许多问题都属于特定的算法类别,如果你把正确的算法应用到问题上,就会奏效。”“希望这些家伙能根据他们在《算法分析》中学到的东西,把策略应用到竞争问题上。”

依靠多样性

 

金队将带着让他们在地区赛中成为巨人杀手的相同特点前往华沙。克里斯滕森用一个词来概括:多样性。

亚伦主修物理,辅修数学。这在地区赛上真的很有帮助,因为那里有一些关于光速的东西,他知道如何直观地简化公式,这很神奇,”克里斯滕森解释说。他补充说,Dufour也是三者中编程时间最长的,但Dufour指出,竞争对手将使用Java。

“这是一种我不太熟悉的语言,”他说。“而且我可能是最慢的打字员。”

库利指出,克里斯滕森的研究生身份增加了团队的多样性:“他已经获得了学士学位。他学过艾伦和我没有学过的课程。”

成员们意识到多样性有其另一面。

杜福尔说:“与大多数其他队伍相比,我们在地区赛上投入的准备工作确实较少。”“在这方面,我们可能还有很多要做。”

每周训练一次

 

为了磨练他们的团队合作能力,三个人每周都会见面练习。他们首先讨论了一个实践问题,每个人都在单独研究这个问题。随着世界越来越近,他们将进行更实时的模拟竞争条件的演习。

计算机行业对进入世界总决赛的队伍成员有着浓厚的兴趣;这样的竞赛是一种很好的方式,可以从一群新的计算机程序员中找出最优秀、最聪明的人。企业赞助允许芝加哥大学邀请所有参加世界赛的北美队伍参加练习比赛。金牌之队当然要走了;所有费用都已支付。

前往华沙的后勤也带来了许多挑战。为了建立联系并按时参加比赛,金队必须在5月13日离开美国。那天是威廉玛丽学院的毕业典礼,杜福尔和克里斯滕森将获得学位。有一些人担心他们可能会错过这个重要的日子,但努南解决了这个问题。

“你知道,他们的父母花了很多钱让他们上学,他们希望看到他们毕业,”她说。“事实证明,有一些从里士满起飞的航班在晚上晚些时候起飞。现在他们可以去参加毕业典礼,和父母合影,还能参加世界总决赛。”