ACM与大学生素质教育讲座.ppt

图灵奖、ACM/ICPC与创新型人才培养,董文永QQ：23294844,提纲,图灵奖获得者对我们的启示ACM/ICPC的发展历史与现状ACM/ICPC对创新素质的影响ACM/ICPC的学习模式与训练模式武汉大学的参赛历程与经验,一.合格IT人才应该具备的素养,基础知识专业技能方法能力社会能力,机遇,成功,图灵,阿伦图灵(Alan MTuring，19121954)生于英国伦敦帕丁顿镇(Paddington)。13岁时进入谢博恩中学寄宿学习，数学课学习成绩很好，演算能力特别强。毕业后进入剑桥大学的国王学院(KingS College)攻读数学，并以数学学位考试第一的好成绩毕业。,1935年，图灵对数理逻辑(mathematical logic)发生兴趣并开始研究。1936年，图灵结合自己的研究成果在撰写的论文“论可计算数及其在判定问题中的应用”中，提出了一种可将推理过程化作一些简单机械动作的计算机抽象模型。这个模型就是人们现在常说的“图灵机”。图灵因此被称为计算机科学理论的奠基人之一。,ACM 图灵奖,ACM 图灵奖是ACM 于1966年(即图灵去世后12年)第一个设立的奖项，专门奖励在计算机科学领域做出创造性贡献的杰出科学家(从实际执行过程来看，较偏重于在计算机科学理论和软件方面做出贡献的科学家)。,获奖者分布情况,这些获得者中，从国籍来看，美国占绝对多数，为65，然后依次为英国12，加拿大5，德国、荷兰、瑞士、印度、拉脱维亚、以色列各占2 5；从毕业院校来看，美国的加州大学伯克利分校和普林斯顿大学较多，各占125，卡内基一梅隆大学、加州理工学院、麻省理工学院(MIT)和哈佛大学各占10，英国剑桥大学占75，英国牛津大学、美国芝加哥大学和密歇根州立大学各占 5；,从所学专业来看，数学专业占绝人多数，为62，物理专业占10，电气工程专业占7，计算机科学专业仅占5；从最高学位来看，具有博士学位占绝对多数，为825，硕士学位占75，学士学位占10；从他们所从事的方向来看，计算机硬件仅占15，而绝大部分为计算机软件与理论，占85，其中程序设计语言方向占25，算法及计算复杂性占225，人工智能占15，数据库占10，操作系统占75，其它方向合起来占10。,1、个人天赋很高，且学习勤奋。,天赋高和学习勤奋几乎是任何领域成功人事的共同素质。如1970年获奖者詹姆斯威尔金森(JWilkinson，19191986)，16岁免试进剑桥大学；1971年获奖者约翰麦卡锡(JMcCarthy，1927)，初中自学大学低年级高数课；1974年获奖者唐纳德克努特(DKnuth，1938一)，人称“数学天才”，以各门功课平均975高分中学毕业，且写科幻小说出版并获奖；,1975年获奖者之一的赫伯特西蒙(HSimon，19161992)，小时聪明好学，跳过2级，17岁上芝加哥大学，获政治学学士、博士学位，但却是人工智能符号主义学派的创始人，又作为经济学家获过诺贝尔奖；还有1978年获奖者罗伯特弗洛伊德(RFloyd，1936)，芝加哥大学文学学士学位毕后，其计算机科学知识是在西屋公司自学的，等等。这些科学家的天赋和勤奋无一例外的为他们的成功奠定了良好的基础。,2、数学功底深厚，且兴趣广泛。,由前面的统计分析可以看出，在些获得者中，数学专业占绝大多数，为625。这一方面是由于早期没有计算机科学专业，另一方面也说明计算机科学与数学这两个学科的紧密联系，以及计算机科学领域要想成功对人才数学知识的较高要求。,因为从现在的研究成果来看，计算机科学与技术学科的基本问题是什么能(有效地)自动进行，什么不能(有效地)自动进行，它以描述和变换信息的算法过程，包括其理论、分析、设计、效率分析、实现和应用的系统为研究对象。其学科的本质还是数学。,如图灵1936年划时代的论文所指出的一样，理论上凡是可以用计算机来处理的问题和处理过程，都可以用应用数学来描述；凡是可以用以离散数学为代表的构造性数学描述的问题及处理过程，只要所涉及的论域是有穷的，或虽无穷但存在有穷表示，也一定可以用计算机来实现。因此，深厚的数学基础知识是从事计算机科学与技术学科的必要条件。,除此之外，在对这些科学家进行分析时，我们不难发现虽然它们大多数从事的是数学，但兴趣非常广泛。如1967年获奖者莫里斯威尔克斯(MVWilkes，1913一)，还喜欢物理和无线电，并组装收音机；1969年获奖者马文明斯基(MLMinsky，1927一)，喜欢电子学和化学，在哈佛大学主修物理，从修数学、电气工程、遗传学、心理学，后来改学数学；1976年获奖者之一的米凯尔拉宾(M0Rabin，1931一)，还喜欢微生物学，等等。,3、师从名校名家，且受教育程度高,如1975年获得者赫伯特.西蒙和艾伦.纽厄尔(ANeweli，1927-1992)，其艾伦.纽厄尔就是赫伯特.西蒙在卡内基一梅隆大学的博士研究生，后来成为及其亲密的合作者；1976年获得者米凯尔.拉宾和达纳.斯科特(DSscott)，两人在2O世纪5O年代中期先后师从著名的逻辑学家和计算机专家阿隆索.邱奇。,1994年获得者爱德华.费根鲍姆(E-AFeigenbaum)和劳伊.雷迪(RReddy)，其中爱德华.费根鲍姆也是赫伯特.西蒙在卡内基一梅隆大学的博士研究生，而劳伊.雷迪是1971年获得者约翰.麦卡锡在斯坦福大学的博士研究生，等等。,4、阅历丰富，且工作热情高,1966年获得者艾伦.佩里(AJPerlis，1922-1990)，大学毕业正逢二战，应征入伍参加空军服役，战后进入加州理工学院研究生院继续深造，获数学硕士学位，又到麻省理工学院(MIT)攻读博士学位，毕业后在美国陆军军械部阿伯丁试验基地内的弹道研究实验室工作一年，再回母校MIT参加“旋风”(Whirlwind)计算机计划，之后又到普渡大学，创建全美大学中的第一个计算中心，又转入卡内基理工学院.,1967年获得者莫里斯.威尔克斯，取得博士学位后即参加了英国侦察德国潜水艇、军舰和飞机的雷达设备项目的研制，战后回到剑桥大学；,1968年获得者理查德哈明(RHamming，1915-1998)，取得博士学位留校工作两年后，转入路易斯维尔大学任教，两年后转到洛斯阿拉莫斯国家实验室，参加著名的曼哈顿计划，后又到著名的贝尔实验室工作30年，离开贝尔又到美国海军研究生院工作直到退休。,5、思想敏锐，且善于钻研,1968年获得者理查德哈明，对误码问题的解决。当时大家都意识到这一问题对商业、军事等应用会产生严重后果，迫切需要解决，但相当长时间却找不出好的方法。哈明接此任务后，首先意识到线路质量的改善是有限的，外界干扰也是无法绝对避免的，因此这个问题不能通过保证发送码不出错这条途径去解决，而只能通过一旦出错如何发现、如何纠正才能解决。正是由于这一敏锐的思想，加之其刻苦钻研的精神使得他能沿着正确的路线进行，终成为纠错码的发明者和信息学专家,1987年获得者约翰.库克(JCocke)，在设计和开发IBM360计算机时发现，一般的计算机系统中只有约20的指令是经常使用的，它们占程序执行总指令数的80，而指令系统中其余80的指令则很少使用，仅占程序执行总指令数的20，即著名的“2：8定律”。沿着这一条思路，库克在其后来的801计算机项目中就大胆提出了精简指令集计算机RISC的概念，通过钻研实践，于是终成为一种崭新的计算机体系结构。,记得有位科学家曾经说过当今计算机学科的特点是，“高速发展，无情淘汰”。这就必然要求计算机工作者必须时刻保持思想的敏锐性，要敢于发现问题，并且还要善于钻研。,二、ACM/ICPC的发展历史与现状,three major programming contest venuesthe ACM International Collegiate Programming Contest(ICPC)；the International Olympiad in Informatics(IOI)；the TopCoder Programmer Challenge.,ACM-ICPC竞赛简介,ACM是Association for Computing Machinery美国计算机学会的缩写。ACM竞赛是指ACM国际大学生程序设计竞赛（ACM International Collegiate Programming Contest）。该项旨在为大学生提供一个展示问题求解和程序设计能力的机会，同时促进不同地区大学生的文化交流。到今年为止已有来自六个洲的100个国家的3000个大学的10150个队参加比赛。赛程分为两个阶段：洲内预选赛和全球总决赛。只有在洲内预选赛中获胜的队伍才能参加最终的角逐。,ACM/ICPC的发展历史,从1970年举办美国Texas A&M University举办1977年在ACM计算机科学会议期间举办了首次总决赛1980年ACM将竞赛的总部设在位于美国德克萨斯州的贝勒大学。http:/,ACM/ICPC的发展历史,1997年IBM开始赞助总共有来自840所大学的560队伍参加比赛 目前演变成为一年一届的多国参与的国际性比赛 发展成为一项世界范围内的竞赛,ACM/ICPC的发展历史,历届冠军分布情况在赛事的早期，冠军多为美国和加拿大的大学获得进入1990年代后期以来，俄罗斯和其它一些东欧国家的大学连夺数次冠军 上海交通大学代表队则在2002年美国夏威夷第26届和2005年上海举行的第29届全球总决赛上,2006年两夺冠军。这也是目前为止亚洲大学在该竞赛上取得的最好成绩。,历届全球总决赛冠军列表,2009 圣彼得堡信息技术、力学与光学大学 2008 圣彼得堡精密工业大学 2007 Warsaw University 华沙大学2006 俄罗斯的Saratov国立大学 2005 Shanghai JiaoTong University 上海交通大学2004 Petersburg Institute of Fine Mechanics and Optics 圣彼得堡理工学院2003 Warsaw University 华沙大学2002 Shanghai JiaoTong University 上海交通大学2001 The St.Petersburg State University 圣彼得堡州立大学2000 The St.Petersburg State University 圣彼得堡州立大学,历年ACM总决赛中国高校代表队成绩（1995-2007）,三、ACM/ICPC对创新素质的影响,ACMICPC竞赛采用全英文环境，竞赛试题涉及程序设计、数据结构、算法分析与设计、人工智能、离散数学、组合数学、计算几何、密码学及算法复杂性等多学科领域的理论和方法。有些题目没有固定的最优解法，要求参赛者在限定时间内综合运用所学知识对问题进行分析、研究和归纳，并通过抽象、建模、编程调试及提交测试等严格步骤完成命题。,(1)培养学生的创造能力,培养学生的创造意识要在学习中倡导发现，让学习者始终处于探索、刻意求新及力求完美的精神状态之下。ACMICPC竞赛活动以其难和新，激发学生的兴趣；通过任务驱动的方式，让学生在解题的过程中，去构思满足时间和空间要求的完美算法。,(2)培养学生的综合能力,ACMICPC竞赛属智力与应用计算机解题能力的比赛。竞赛要求学生对这些从现实生活中抽象出来的竞赛题目进行抽象化和模型化，通过编程求解。最后是采用测试数据对程序进行严格的测试分数的评定。,(3)激励学生的创新能力,培养创新能力必须把知识运用的综合性、灵活性及探索性作为重要内容。有些ACMICPC竞赛题目是世界性难题，需要学生灵活运用多门学科知识，在已有工作基础上来解决。,(4)培养学生的科学素质,ACMICPC竞赛具有挑战性，符合大学生好胜心理。参加竞赛的学生在比赛过程中调用各种知识进行分析和研究，应用抽象思维能力和逻辑推理能力。许多竞赛题目无固定解题模式，数百条苛刻的测试数据能测定编程失误之处。需要不断修改错误并完善程序，培养了学生求真务实的科学态度。,(5)锻炼学生的心理素质,ACMICPC竞赛在近百支以3人为一组的参赛队中同时展开，要求参赛队在5个小时内完成6至10道题目。每答对一题由工作人员送上代表题号的彩色气球，最后以各队得到的气球个数来决定胜负，场面紧张而热烈。要求参赛者善于调节心态，用坚强的意志、冷静的头脑及灵活的应变能力去应战。,(6)提高学生的团队素质,ACMICPC竞赛时需要3人分工合作和积极配合，以共享思维成果。促进了学生的主体意识和合作意识等多方面素质的协调发展。,四、ACM/ICPC的学习与训练模式,1协作学习，创造最佳学习结果协作学习(Collaborative Learning)是通过小组或团队的形式进行学习的一种策略，小组成员的协同工作是实现学习目标的有机组成部分。ACM竞赛有意让三个人共用一台电脑，且在短时间内完成有一定难度的题目，旨在让小组成员协作完成。比赛中如何充分发挥三个人的力量，团队的配合技巧十分重要，三个队员之间的合理分工，对同一问题的不同想法进行的合理论证都可以大大改进解题的效率。,仅仅比赛时的协作还远远不够，在平时的训练中，协作学习已经开始。短短的一年准备时间，还要应付平时学习，一个人很难掌握所有的学习内容。队员往往根据各自的专业和特长，分工学习，定期集合讨论或做题，根据不同的题型，有不同的主力队员分析、讲解，进而加快学习和理解速度。为了更好发挥各自的长处，且长久发挥一个学校的优势，梯队建设也很有必要，高低年级、不同专业组队，发挥专业特长，保持实力延续，老队员带动新队员，是ACM竞赛准备中分工协作的一个重要方法。,2任务驱动式学习，创造自主学习,在ACM竞赛的准备过程中，学什么、怎么学都由学生自己决定。他们自己设定学习目标，分析学习内容，制定学习计划，获取学习资源，管理学习过程。为了能够得心应手地攻克大赛题目，队员需要掌握大量的基础知识。虽然有些知识很枯燥，但是结合到攻克的题目中，又是那么的学以致用，队员们常常乐此不疲，直到把每一个知识点都理解透彻。,为了攻克这些知识点，队员们采取多样学习方式，可旁听高年级的相关课程，可利用网络寻求直接的经验总结，可钻研参考书目获得理论知识。经历了自主学习过程，选手们常说那些枯燥的离散数学、图论、数值分析等课程，一旦与竞赛内容结合，学习起来就很有动力，也很轻松。当自学变得如此得心应手的时候，很多选手会在一个学期，将三四个学期的课程学习完毕。竞赛的准备过程是学生对计算机科学的基本思想和内涵以及方法的真正体会，是真正的“授之以渔”，而不是“授之以鱼”。,3在网络中学习,国内很多高校提供ACM竞赛平台，它是一个展示才华和交流合作的全英文版平台，提供大量的竞赛题目，任何人都可以注册ID，在平台上答题，平台作为裁判进行评判。,4竞赛式学习,培训采用课堂讲授、课下讨论、实战练习相结合的形式。老队员成为培训的主力军，他们总结竞赛经验，融合网络资源，与新手们共享。有的老队员全程指导上机练习，帮助新手熟悉平台，调试程序。老队员带新队员既加快了新队员前进的步伐，也锻炼了老队员表达、合作的能力。培训是紧张辛苦的，队员既要跟得上培训进度，又要花大量的时间进行实战练习，自学能力、合作能力、编程调试能力飞速增长。总之通过培训可以筛选出比赛的主力军。,5、算法的力量,算法是计算机科学领域最重要的基石之一。编程语言虽然该学，但是学习计算机算法和理论更重要，因为计算机语言和开发平台日新月异，但万变不离其宗的是那些算法和理论，例如数据结构、算法、编译原理、计算机体系结构、关系型数据库原理等等。算法是“内功”，语言、技术、标准是“外功”。整天赶时髦的人最后只懂得招式，没有功力，是不可能成为高手的。,上海大学ACM班,大一、大二竞赛相关的课程从大三开始，每位ACM班学生必须在科研导师的指导下，参与实验室的科研工作。这些实验室的研究方向包括：计算机科学的基础理论、密码学与可信计算、人工智能与机器学习、计算机网络、生物信息学等目前较为前沿活跃的学术领域。,几句名言,“夫志当存高远，慕先贤，绝情欲，弃疑滞，使庶几之志，揭然有所存，恻然有所感；忍屈伸，去细碎，广咨问，除嫌吝，虽有淹留，何损于美趣，何患于不济。若志不强毅，意不慷概，徒碌碌滞于俗，默默束于情，永窜伏于凡庸，不免于下流矣！”这是出自三国时期杰出的政治家、军事家、战略家、散文家、外交家诸葛亮的 诫外生书。,“谚云：世界无难事，只畏有心人。有心之人，即立志之坚者也，志坚则不畏之不成。”这是出自中国老一辈无产阶级革命家任弼时的言志。,黄教授提出：成功就像是一个由三条边稳定支撑的三角形，它的三条边分别是“天资”、“勤奋”和“情商导出的机运”。天资是生而就有、无法改变的，机运也不是总在路口等着你的一辆公交车，它需要你去争取，所以勤奋就占了成功的很大比例。,参考资料,1.入门级，比较容易懂，有很好的小例子，清华大学计算机系的专业入门课教材 程序设计基础，吴文虎 著，清华大学出版社，20032.比较难，内容深刻有趣，阐述了计算机程序设计和程序编译的本质 MIT、Standford、Tokyo的大学计算机系的专业入门教材 计算机程序的构造与解释，裘宗燕 译，机械工业出版社，2004 3.各类算法讲述精辟透彻，英文版，北大计算机系算法分析课的教材 计算机算法-设计与分析导论，英文，Sara Baase,Allen Van Gelder，高等教育出版社，20014.以竞赛题为例讲解常用算法，提供大量的例题资源 算法艺术与信息学竞赛，刘汝佳，黄亮，清华大学出版社，2004,References,5.北大计算机系数据结构教材，数据结构与算法 许卓群，杨冬青，唐世渭，张铭，高等教育出版社，20046.T.H.Cormen,C.E.Leiserson,R.L.Rivest and C.Stein(2001),Introduction to Algorithms(the second edition).TheMIT Press7.H.S.Wilf(1994),Algorithm and Complexity.Draft of the internet edition at http:/,国内OJ网站,1.武汉大学的onlinejudge推荐2.http:/同济大学的onlinejudge4.四川大学的onlinejudgehttp:/5.入门级网站信息,初学初学者之家http:/,主要网站,1.中国信息学奥赛官方网站 2.USA Computing Olympiad 3.Baltic Olympiad in Informatics 4.5.acm/icpc 国际大学生程序设计竞赛主网站,武汉大学参赛经历及经验总结,