计算机问题求解 - 算法在计算机科学中的地位.ppt

《计算机问题求解 - 算法在计算机科学中的地位.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、计算机问题求解–论题1-6-如何将算法“告诉”计算机？2018年10月23日问题1：你觉得你生来最重要的经验是什么？我觉得是“运用语言”。问题2：你能描述一下什么是“语言”吗？计算机的“NativeLanguage”指令存放地址计算机能懂的“指令”可是，人实在难懂，更别说写了！数据所在位置vonNeumannArchitecture四大部分存储程序顺序执行问题3：你知道图林和冯诺依曼吗？你知道他们各自的贡献吗？汇编语言用汇编语言实现如下算法：对输入的非负整数进行累加，遇到负数停止。问题4：你能说说相比机器语言，汇编语言有些什么好处吗？但是…我们期

2、望的程序设计语言应该……问题5：我们要的是“机器为人服务”，而不是“人为机器服务”，你觉得我们离这个目标差得远吗？从算法到程序：一个例子数据净化问题：0是无效数据问题6：你给个算法？C++程序：头部逐个输入数据；指针赋值打印输入的数据利用“左”“右”两个指针将有效数据集中在前部，并记录有效数据个数。输出清洗后的数据。顺便问一句，这个语句是干什么的？Java程序：头部注意：输入输出部分与C++差别很大逐个将数据输入data计数器与指针赋值打印未经清洗的数据注意：Java程序与C++程序结构相似，而且除了输入输出，其它语句也非常相似！这是用Python

3、语言实现的converging-pointers算法。与C++程序非常相似。问题7：你如何理解这段话？问题8：那么，怎样才能达到“anunambiguousandformalfashion”呢？回忆一下，逻辑语言是如何定义的？语言是一个集合为了简单起见，考虑一个只有“句子”组成规则，但“句子”没有“含义”的语言首先，必须定义“所允许的符号”-“字母表={a,b}再规定哪些“用a,b构成的符号串”是语言L中“合法”的句子1.a是<前缀>;2.<前缀>接a仍然是前缀3.<前缀>接b是合法句子4.<合法句子>接b仍然是合法句子4.任何合法句子只能通过实

4、行上述规则有限次得到问题9:这是个什么样的集合?L={w

5、w=aa*bb*}问题10:什么是Syntax?Syntax（文法）规定什么样的句子属于特定语言。最简单的文法：RegularExpression语言可以由“Acceptor”来判定开始b出错a前缀a句子bba问题11：这个“机器”接受的是什么语言？RegularSyntax能力有限下面的语言就无法用regularsyntax描述：L={anbn

6、n=0,1,2,…}上下文无关文法：G=(N,T,S,P)，这里：N={句子}T={a,b}S=句子P={句子is:;句子is:

7、a句子b}所谓“上下文无关”是指非终结符的替换与其前后的符号无关。这样的文法还不足以描述：L={anbncn

8、n=0,1,2,…}Bachus-Naur范式问题12：什么是Semantics?如果你用高级语言写的程序已经能在计算机上运行，并给出正确结果了，“语义”还有问题吗？问题13：不管什么文法、语义都不能让计算机直接听懂你要它干什么，那你的程序是怎么运行的呢？你能画出解释执行的示意图吗？课外作业写出你现在用的C++语言的算术表达式的完整严格的文法。试用其它算法解数据清洗问题，编写相应程序，并与课堂上介绍的算法进行比较。