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

《计算机问题求解 - 算法在计算机科学中的地位.ppt》由会员分享，可在线阅读，更多相关《计算机问题求解 - 算法在计算机科学中的地位.ppt（28页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

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

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

4、bb* ,问题10:什么是Syntax?,Syntax（文法）规定什么样的句子属于特定语言。,最简单的文法：Regular Expression,语言可以由“Acceptor”来判定,问题11：这个“机器”接受的是什么语言？,Regular Syntax能力有限,下面的语言就无法用regular syntax描述： L = anbn | n=0,1,2, ,上下文无关文法：G=(N,T,S,P)，这里： N = 句子 T = a,b S = 句子 P = 句子 is: ; 句子 is: a句子b ,所谓“上下文无关”是指非终结符的替换与其前后的符号无关。这样的文法还不足以描述： L = anbncn | n=0,1,2, ,Bachus-Naur范式,问题12：什么是Semantics?,如果你用高级语言写的程序已经能在计算机上运行，并给出正确结果了，“语义”还有问题吗？,问题13：不管什么文法、语义都不能让计算机直接听懂你要它干什么，那你的程序是怎么运行的呢？,你能画出解释执行的示意图吗？,课外作业,写出你现在用的C+语言的算术表达式的完整严格的文法。试用其它算法解数据清洗问题，编写相应程序，并与课堂上介绍的算法进行比较。,