计算思维教学认识与实践交大黄林鹏.ppt

计算思维教学认识与实践,黄林鹏上海交通大学计算机科学与工程系教授,全国计算机基础教育研究会 理事上海市计算机基础教育学会 常务理事上海市高校计算机等级考试委员会 委员,上海第二工业大学 2013.4,目录,计算时代需要计算的思维计算思维的定义、内涵（AAA）和外延计算思维是人的思维还是计算机的思维？教授计算思维需要依赖计算机吗？（Plugged？）国外计算机课程教学改革融计算思维于程序设计教学的实践（Why Python？）问题驱动-任务导向 的计算思维教学探索计算模型（图灵机还是Lambda演算？）Computational+X 和计算机科学地位（讨论）改革的动力和阻力（讨论）后计算思维时代是什么？（讨论）,计算时代需要计算的思维,个人计算,云计算,超级计算,计算中心,移动计算,真实和虚拟世界,2007年1月Nature：Social Sciences:Lifes A Game（社会科学：生活就是一场游戏）。越来越多的人“生活”在Cyber世界中，人跟人之间的沟通越来越借助于机器今天如果突然失去机器，世界将崩溃,计算的重要性,YD认为中国文明的根系是靠基于农耕文明的伦理来维系。,算计 计算,农耕文明 到 工业文明 到 信息时代,计算思维的定义,2006年，美国卡内基梅隆大学的Jeannette M.Wing（周以真）教授首先提出计算思维的概念。定义：运用计算机科学的基础概念进行问题求解、系统设计、以及理解人类行为等的一系列思维活动。观点：源自数学思维和工程思维的计算机思维，与阅读、写作与算术能力一样，应成为人类的基本技能。强调：计算思维是“人的，不是计算机的思维”，“计算思维是人类求解问题的一条途径，但决非试图使人类像计算机那样去思考”。,计算思维的内涵,计算思维,计算思维3大支柱(Cuny,Snyder,Wing 2010),计算思维7种方式,Skills,habits and approaches integral to solving problems using a computer,Thinking patterns that involve systematically and efficiently processing information and tasks.,(Wing 2006,2008),Pertains to defining,understanding and solving problems with computers,计算思维是人的思维还是关于计算机的思维,计算思维是“人的，不是计算机的思维”，“计算思维是人类求解问题的一条途径，但决非试图使人类像计算机那样去思考”。,去想机器是如何计算的细节？,关注问题本身的求解方法？,计算思维的提出使人们开始反思，为什么思想要被某种体系结构或某种程序设计语言所限制，为什么不能以解决问题的自然方式进行思考。为此许多计算机教育工作者开始整理、归纳计算机学科数十年来形成的解决问题的有效方法，在计算机科学教育中进行尝试。,教授计算思维需要计算机吗？,不插电 还是 插电？如果使用计算机，应该选择什么样的语言？,CT：Skills,habits and approaches integral to solving problems using a computer,有计算机为什么不用？,驾驭计算需要不断实践（coding-debugging-tuning）,编程能带来乐趣、增加信心、培养能力,CTUSA,美国国家科学基金会2006年首先提出了“扩大计算参与面”B P C（Broadening Participation in Computing）计划。通过扩大计算的参与对象，使更多的人受益。2007年又启动了“振兴大学本科计算教育的途径”CPATH（CISE Pathways to Revitalized undergraduate Computing Educating）计划，目标是促成早就具有基本计算思维能力的、在全球有竞争力的美国劳动大军确保美国在全球创新企业的领导地位；将计算思学习机会融入到计算机、信息科学、工程技术和他领域的本科教育中，以增加开发具有计算思维力的学生人数；展示突破性的、可在多类学校中广的、以计算思维为核心的本科教育模式。2011年度美国国家科学基金会又启动了二十一世纪计算教育CE21（Computing Education for 21st Century）计划，其目的是提高K-14（中小学和大学一、二年级）老师与学生的计算思维能力。,USA：工资提高2.8%，效率提高20%CHINA：工资提高20%up，效率提高0%,国外：Berkeley分校,加州大学Berkeley分校：学生对于学校原先开设的程序设计课程的反馈意见大多是“Dry.Difficult.Irrelevant.（枯燥，难学，专业无关）”。经过分析，认识到按照传统的方法讲解程序设计，学生往往难以接受，容易产生排斥心理，大多会选择放弃进入计算机专业学习。UML创始人，著名计算机科学家Grady Booch提出计算机科学的讲授应是“passion,beauty,joy and awe（激情、美丽、乐趣、敬畏）”。受此启发，Berkeley于2009秋季开设了课程“The Beauty and Joy of Computing”，教学目标是使程序设计对于学生来说是“Fun.Easy to learn.Can relate to it.”。,“The Beauty and Joy of Computing”,Introduction to Computational Thinking,普度大学的计算思维引论课程是美国自然科学基金委的CPATH(本科计算机教育复兴之路，)项目下课题SECANT（基于计算思维的科学教育，Science Education in Computational Thinking）。由计算机科学、物理学、统计学、和化学等专业的教师一起协作开设的课程。课程目标是借助基本程序设计方法、数据和数据管理理论以及仿真和可视交互技术给科学专业的学生讲授计算思维。,普度大学的计算思维引论课程,MIT 6.00,Introduction to Computer Science and Programming 20多年来一直使用Scheme语言来阐明计算机程序的构造并予以解释，教材：SICP，一些学生表现有极大的热情，而大部分学生由于各种原因则困惑不解。2007年，受各种因素影响，MIT对6.00课程进行了改革，使用学生更加容易理解和掌握的Python语言作为工具来讲解程序设计和计算机科学。课程目标是使学生理解计算在问题求解中的作用，明确课程的主旨是帮助所有学生，包括那些不打算进入计算机专业学习的学生，具备能编写求解实用问题的简单程序的自信。,MIT600课程大纲,CTCHINA,国内：中科院王飞跃教授首先建议开设计算思维与计算文化，李国杰院士和陈国良院士也多次倡导在我国开展计算思维的教育2 0 1 0 年5 月召开了合肥会议，讨论如何将计算思维融入这些课程中；2 0 1 0 年7 月，在西安会议上发表了九校联盟（C 9）计算基础教学发展战略联合声明，确定了以计算思维为核心的计算机基础课程教学改革；2 0 1 0 年9 月在太原会议上决定将合肥会议和西安会议中有关计算思维的讨论形成拟上报的书面材料；2 0 1 0 年1 1 月在济南会议上，将在全国更大范围内，深入讨论以计算思维为核心的基础课程教学改革，并建议立项研究；2 0 1 1 年8 月，在深圳会议上正式确定以计算思维进行立项研究；2 0 1 0 年秋季，在上海交通大学，2 0 1 1 年春季，在南方科技大学，陈国良院士讲了一个学期的计算思维；2 0 1 1 年春季，在西安交通大学同时开了三个班，大家非常积极；2 0 1 1 年秋季，在深圳大学也针对专门的班级开设了计算思维课程。2012年高教司基于计算思维课程建设项目,融计算思维于程序设计教学的实践,重点是计算“思想”和“方法”，而不拘泥于某种特定的程序设计语言。讲授“问题建模问题分析寻求方案方案比较方案实现的“问题求解驱动式程序设计”方法，逼近真实世界问题求解。将50多年来计算机学科所形成的解决问题的思维模式和方法渗透到不同学科。,上海交大的CT教学实践,为什么要改革？,计算思维与其他课程,课程内容,什么是计算(计算机软硬件基础知识，计算机如何工作）简单的数据处理(数据的表示,类型,操作,简单数据结构,.)问题的表示(抽象,建模,形式化.)结构化/模块化/逐步求精(函数,分而治之,.)面向对象的设计思想和方法化繁为简的思想(分解,转换,模拟,.)预取与缓冲的思想(硬件的缓存,软件缓冲管理)排序与查找递归（算法设计策略），归纳（正确性证明）和递推（复杂度分析）搜索(回溯,深度、广度优先.)并行与并发的思想(MPI、多线程编程)保护与恢复（容错，检查点）最优化与动态规划计算模型，计算机的能力和局限热点问题和未来的计算,教学概括,名称：程序设计思想与方法性质：通识课程（注：任选4门/9门）学分：2+1（其中1学分是实践）对象：全校一年级新生教学语言：中文/英文,目标1,在程序设计思想方面，使学生：理解计算在解决科学问题中的作用重视计算作为科学发现的基础工具探索不同算法在效率和性能方面的影响理解实用的基本程序设计原则基本理解不同程序设计语言解决实际问题的可能性基本理解计算的限制和不可解问题,目标2,在程序设计方法方面，使学生能：分析和抽象问题设计和实现针对科学问题的有效的软件解决方案有效地使用通过函数说明所描述的软件库 理解基本数据结构的使用和功能编写完成有明确使用目标的程序，可视化其结果阅读和改写已存在的程序,参考书,教学参考书John Zelle:Python Programming:An Introduction to Computer Science,Franklin,Beedle&Associates,2004.D.Harel:Algorithmics-The Spirit of Computing,Addison-Wesley,3rd edition(with Y.Feldman),2004.,教材？参考书？,课堂教学,通过授课、演示，使学生能更好地理解运用计算思维求解问题的思想和方法，并能够编写一些简单的但可解决实际问题的程序，以提高学生应用计算思维方法求解问题的兴趣。在课堂教学中还引入讨论，使同学们能更好地将计算思维融入到不同专业和学科。课外学习主要让学生自行了解要解决问题的背景知识，寻找合适的工具和构件库，培养学生自主学习的意识和解决问题的能力。,课堂教学,考核及成绩评定方式最终成绩由出勤情况、个人作业&小组大作业、期终考试成绩相结合。各部分所占比例如下：出勤情况&个人作业：30%。主要考核学生对知识点的掌握程度、独立分析和解决问题的能力。小组大作业：20%。主要考核团队合作分析和解决较大型、复杂问题的能力。考试：50%。主要考核对程序设计的基本思想和方法的掌握程度。,实践环节,实践环节包括个人作业和小组作业个人作业旨在培养学生运用所学知识独立分析实际问题和解决实际问题的能力，并在实践中不断加深对计算思维的理解，最终具备一定的终身学习能力。小组大作业使学生了解和体会团队合作精神在解决大型、复杂科学问题中的重要性。由2-3名学生完成一个大作业。各专业学生可结合自己的专业自己选取感兴趣的题目，也可以在指定的一组题目中选取题目。,教学内容和学时分配,教学语言和教学规模,教学情况,问题驱动-任务导向,问题求解 对计算机科学中的典型问题 按照 计算思维 求解问题的方式进行 重新整理；把每一个问题讲透；诱导学生进一步思考；结合“实际例子”进行讲解,分治与递归,基本思想把规模为n的问题分解为k个规模较小子问题，它们相互独立且与原问题相同，从而有相同的处理结构（递归落体）例子：斐不那契序列原点：一对雌雄兔子规律：每月产下1对兔子，一生只产2次，二次产后死亡计算:0th=1+0=1(对);1th=1+1=2;2th=2+1(2-1)=3;3th=3+2(3-1)=5;nth个月活着的兔子 F(n)=F(n-1)+F(n-2);0,1,1,2,3,5,8,11,19,30,49，.求F(100)?例子：求2个数的最大公约数 欧几里得算法GCD（a,b),abGCD(a,b)=GCD(a-b,b)=GCD(a-k*b,b),a=kb+r,0r b+r2r(r余数）,2023/10/18,两个例子的联系是什么？若需要n次模运算则 aF(n+2)且bF(n+1),简单的方法是什么？复杂度如何？,USA选举,会平局吗？,找出可能（所有）的平局？,简单的方法？,问题抽象,一般化,排序,任务：将小朋友从低到高从左到右排成一列,3个小孩？,2个小孩,OK操作：比较，换位比较数：1移动数：1（可能）,OK操作：无比较数：0移动数：0,1个小孩,2 3.8,大问题分解小问题，小答案组合大答案,Thinking patterns that involve systematically and efficiently processing information and tasks.,插入排序,思想：增量式，可持续1个人排好序2个人排好序3个人排好序 n个人排好序1个人排序 OKn-1个人排序OK n个人排序OK 分治：n=（n-1）+1 递推关系：移动次数 T(n)=T(n-1)+n-1，T(1)=0 比较次数 T(n)=T(n-1)+n-1，T(1)=0,可能操作数目：比较数：n-1移动数：n-1,反复和前面人进行比较找到插入点,归纳,递归,递推,选择,插入排序 分治：n=（n-1）+1选择排序 分治：n=1+（n-1）递推关系：移动次数 T(n)=T(n-1)+1，T(1)=0 比较次数 T(n)=T(n-1)+n-1，T(1)=0,归并排序,插入排序 分治：n=（n-1）+1选择排序 分治：n=1+（n-1）归并排序 分治：n=n/2+n/2递推关系：比较次数 T(n)=2T(n/2)+n-1，T(1)=0 移动次数 T(n)=2T(n/2)+n，T(1)=0 额外空间？,分,治,治,合,比较：n-1移动：n额外空间,归并排序,大问题分解为小问题，小答案组合成大答案,插入排序 分治：n=（n-1）+1选择排序 分治：n=1+（n-1）归并排序 分治：n=n/2+n/2 T(n)=2T(n/2)+n-1，T(1)=0 分（代价1）治 合（代价：n-1）数据移动代价+额外存储代价 如何消除？分（代价n）治 合（代价0）快速排序 分治：n=i+(n-i)(理想i=n/2),大问题分解为小问题，小答案组合成大答案,快速排序,快速排序,比第一个低或一样高,比第一个高,分,3位一体,二分搜索,我心里想一个1到1000的整数，你问问题，我回答Y或N，如何问才能尽快猜到我想的数？我心里想一个整数，你问问题，我回答Y或N，如何问才能尽快猜到我想的数？我心里想一个1到24的整数，你问问题，我回答Y或N，问4次能猜到我想那个数吗？,二分,松弛,悖论构造,归约转换,知识有两种，一种是对事物的亲身了解，还有一种是知道从何处可找到相关信息。约翰逊1775在两个问题间找到一个归约（reduction，或者变换transformation）。归约是使用解决其它问题的“黑盒工具”来解决另一个问题。,已知有解的问题,难的问题,约简 转换 例,排序 和 最小凸包,网络最大流和匹配问题,不可解问题,停机问题（数据-程序）#try.pyimport testdef main(file):if test.halt(file):while True:print“continue”print“stop”main(“try.py”),假定停机问题是可判定的：存在一个函数，假定其为库test.py中定义的halt，则可以构造一个程序try.py.,反证法-悖论构造法-对角线法,计算模型,图灵机,（Lambda）演算函数式语言的核心 Lisp，Scheme，ML，HaskellJAVA语言,Python语言，C+语言目前都支持lambda表达式可讲解抽象，高阶函数，数据-程序、递归的语义等概念进阶：Pi演算、对象演算等,图灵机 A.M.Turing,1936年 演算 A.Church,1935年递归函数 K.Gdel,1936年正规算法 A.A.Markov,1951年,Church-Turing论题:直观可计算的函数类就是图灵机以及任何与图灵机等价的计算模型可计算(可定义)的函数类。,In the mid 1960s,Peter Landin observed that a complex programming language can be understood by formulating it asA tiny core calculus capturing the languages essential mechanismsA collection of convenient derived forms whose behavior is understood by translating them into the core,还是面向机器的思考,数学（函数）思维,讨论,Computational+X 和计算机科学工作者的地位改革的动力和阻力后计算思维时代是什么？,