程序设计思想与方法

程序设计思想与方法董笑菊电子信息与电气工程学院计算机科学与工程系教师信息办公地点：电院楼群3号楼327室电话：34205060转602[e-mail]@sjtu.edu.cn网址~xiaoju/CT助教？–？作业请确定通过Python验证后发给助教每个星期日晚上12点之前课程信息教材–JohnM.Zelle–PythonProgramming:AnIntroductiontoComputerScience参考资料–JeffreyElkner,AllenB.Downey,andChrisMeyersHowtoThinkLikeaComputerScientist:LearningwithPython.–Python学习手册_第3版课程信息下载python软件的地址:textsoft09python2.5/2.6版成绩组成考试作业、大作业平时上机(共5次)–周次：3,6,9,12,15–时间：下午12:55到15:30(三学时)–地点：计算中心?房间出勤777关于课程课程名称是“程序设计思想与方法”,教学内容对应于近年来国际上提出的新课程—“计算思维”计算思维应成为所有人的基本能力–与阅读,书写,算术能力一样!888计算思维computationalthinking计算思维是计算机科学家利用计算机解决问题时的思想和方法–计算机科学是关于“计算”的学问–计算思维建立在由人或机器执行的计算过程的能力和限制之上了解计算机的能力，并充分利用计算机只能按照给定的指令一步步做，无跳跃按照计算机的特点去思考计算思维的特点是概念化思考,而非编程是基本能力,而非机械的生搬硬套是人的思考方式,而非计算机的是数学思维和工程思维的互补及组合是思想,而非人造物人人皆有,处处皆是9计算思维的例子问题抽象,表示,建模问题难度与机器的能力问题解决的效率,近似解,失误率…变难为易:分解,约简,嵌入,转换,模拟递归地思考并行处理类型检查程序美学,系统设计的简洁与优雅10计算思维的例子(续)模块化预取和缓存–图像缓存对最坏情况的预防,保护,恢复–数据丢失同步启发式推理规划,学习,调度时空等不可兼得要素的权衡……11日常生活中的计算思维小学算术:长除法,最大公约数查字典:线性,二分排队:先来先处理整理扑克牌:插入排序书包:预取与缓存邮递员投递路线:尽可能只经过一次烧菜:并行处理生产:流水线……12计算思维对其他学科的影响统计学中的机器学习计算生物学,生物信息学计算博弈论计算化学,纳米计算计算物理学,量子计算计算数学,计算几何,计算机证明定理工程中的计算机模拟医学影像分析电子商务,计算广告学电影特效,计算机作曲,NBA统计分析……13对本课程的定位学习计算机科学解决问题的思想方法,应用于其他专业领域不是程序设计语言课程!–本课程需要编程,以加深对计算思维的理解–坏消息:学习编程语言需要掌握非常繁琐的细节–好消息:Python语言非常简单,易学易用也不是算法和数据结构课程!–当然会学习这方面的一些基本技术14计算机与程序问题的提出当今时代,计算机几乎无处不在:–企业管理–产品设计–气象预报–电影制作–工业控制–游戏,写文章,上网,……问题:计算机究竟是什么?怎么能做这么多不同的事情?16171717通用计算机计算机是具有如下特征的机器:–能够存储和处理信息输入处理输出–信息处理由程序控制计算机程序是一个详细的逐步执行的指令序列,告诉计算机该做什么程序可改变:不同的程序完成不同的处理任务人们造了各种各样的计算机,但:所有计算机具有相同的能力!软件统治硬件程序决定了计算机做什么–没有程序,计算机只是一堆废铁程序设计:编写软件的过程程序设计极具挑战性–既要具备大视野–又要关注细枝末节为何学程序设计?–做计算机的主人–乐趣–培养问题求解能力18什么是计算机科学?并非研究计算机!–正如天文学不是研究望远镜的.–EWDCS要回答的基本问题:什么是可计算的?对此问题的回答有三种方式:–实际设计一个解决问题的算法–理论分析问题的可解性无解的,不是能行可解的–通过实验来研究问题19硬件基本知识20主存CPU输入设备输出设备次级存储器硬件基本知识(续)中央处理器(CPU)–执行运算–只提供简单的运算,如加法,比较等–高速：每秒百万条指令存储器存储程序和数据–CPU只能直接访问主存(RAM)–主存快但易失,次级存储器慢但持久输入/输出设备–人与计算机交互21硬件基本知识(续)提取执行周期(fetchexecutecycle)–提取：从存储器取指令–解码：指令表示什么–执行：做相应的动作22程序设计语言问:用什么语言告诉计算机做什么?答:用精确无歧义的程序设计语言–精确的语法和语义23程序设计语言有不同层次的程序设计语言–计算机自己的母语:机器语言例如:0000010000000001.是Intel8086能理解的一条指令.–把机器语言用助忆符表示:汇编语言上例即:ADDAL,1.需要汇编器处理后机器才懂.–适合人用的语言:高级语言如:x=y+1.需要编译器或解释器翻译后机器才懂.24高级语言252013年1月编程语言排行榜榜单(No.8Python)高级语言高级语言的翻译–编译源代码编译成目标代码,再执行一次编译,多次执行.–解释源代码直接被解释执行每次执行都要重新解释.26高级语言高级语言的翻译–编译源代码编译成目标代码,再执行一次编译,多次执行.271.6.THEMAGICOFPYTHON5(Program)CompilerMachineCodeRunningInputsOutputsSourceCodeProgramFigure1.2:CompilingaHigh-LevelLanguageCodeComputerInputsOutputsSource(Program)RunninganInterpreterFigure1.3:InterpretingaHigh-LevelLanguage.Eachkindofcomputerhasitsownmachinelanguage.AprogramforaPentiumCPUwon’trunonaMac-intoshthatsportsaPowerPC.Ontheotherhand,aprogramwritteninahigh-levellanguagecanberunonmanydifferentkindsofcomputersaslongasthereisasuitablecompilerorinterpreter(whichisjustanotherprogram).Forexample,ifIdesignanewcomputer,IcanalsoprogramaPythoninterpreterforit,andthenanyprogramwritteninPythoncanberunonmynewcomputer,asis.1.6TheMagicofPythonNowthatyouhaveallthetechnicaldetails,it’stimetostarthavingfunwithPython.Theultimategoalistomakethecomputerdoourbidding.Tothisend,wewillwriteprogramsthatcontrolthecomputationalprocessesinsidethemachine.Youhavealreadyseenthatthereisnomagicinthisprocess,butinsomewaysprogrammingfeelslikemagic.Thecomputationalprocessesinsidethecomputerarelikemagicalspiritsthatwecanharnessforourwork.Unfortunately,thosespiritsonlyunderstandaveryarcanelanguagethatwedonotknow.WhatweneedisafriendlyGeniethatcandirectthespiritstofulfillourwishes.OurGenieisaPythoninterpreter.WecangiveinstructionstothePythoninterpreter,anditdirectstheunderlyingspiritstocarryoutourdemands.WecommunicatewiththeGeniethroughaspeciallanguageofspellsandincantations(i.e.,Python).ThebestwaytostartlearningaboutPythonistoletourGenieoutofthebottleandtrysomespells.YoucanstartthePythoninterpreterinaninteractivemodeandtypeinsomecommandstoseewhathappens.Whenyoufirststarttheinterpreterprogram,youmayseesomethinglikethefollowing:Python2.1(#1,Jun212001,11:39:00)[GCCpgcc-2.91.6619990314(egcs-1.1.2release)]onlinux2Typecopyright,creditsorlicenseformoreinformation.TheisaPythonpromptindicatingthattheGenieiswaitingforustogiveitacommand.Inprogramminglanguages,acompletecommandiscalledastatement.HereisasampleinteractionwiththePythoninterpreter.高级语言高级语言的翻译–编译–解释源代码直接被解释执行，每次执行都要重新解释281.6.THEMAGICOFPYTHON5(Program)CompilerMachineCodeRunningInputsOutputsSourceCodeProgramFigure1.2:CompilingaHigh-LevelLanguageCodeComputerInputsOutputsSource(Program)RunninganInterpreterFigure1.3:InterpretingaHigh-LevelLanguage.Eachkindofcomputerhasitsownmachinelanguage.AprogramforaPentiumCPUwon’trunonaMac-intoshthatsportsaPowerPC.Ontheotherhand,aprogramwritteninahigh-levellanguagecanberunonmanydifferentkindsofcomputersaslongasthereisasuitablecompilerorinterpreter(whichisjustanotherprogram).Forexample,ifIdesignanew