程序设计思想与方法董笑菊电子信息与电气工程学院计算机科学与工程系教师信息办公地点:电院楼群3号楼327室电话:34205060转602E-maildong-xj@cs.sjtu.edu.cnxjdong@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什么是计算机科学?并非研究计算机!–正如天文学不是研究望远镜的.–EWDCS要回答的基本问题:什么是可计算的?对此问题的回答有三种方式:–实际设计一个解决问题的算法–理论分析问题的可解性无解的,不是能行可解的–通过实验来研究问题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