计算机问题求解 – 论题1-6 - 如何将算法“告诉”计算机？ 计算机问题求解 – 论题1-6 - 如何将算法“告诉”计算机？ 2018年10月23日
问题1： 你觉得你生来最重要的 经验是什么？ 我觉得是“运用语言”。
问题2： 你能描述一下什么是 “语言”吗？
计算机的“Native Language” 可是，人实在难懂，更别说写了！ 数据所在位置 指令存放地址 计算机能懂的“指令”
von Neumann Architecture 四大部分 存储程序 顺序执行 问题3： 你知道图林和冯诺依曼吗？ 你知道他们各自的贡献吗？
汇编语言 用汇编语言实现 如下算法： 对输入的非负整数进行 累加，遇到负数停止。
问题4： 你能说说相比机器语言，汇 编语言有些什么好处吗？ 但是…
我们期望的程序设计语言应该……
问题5： 我们要的是“机器为人服务”， 而不是“人为机器服务”，你 觉得我们离这个目标差得远吗？
从算法到程序：一个例子 数据净化问题：0是无效数据 问题6： 你给个算法？
C++程序：头部
逐个输入数据； 指针赋值 打印输入的数据
利用“左”“右”两个指针将有效数据集中在前部，并记录有效数据个数。 顺便问一句，这个语句是干什么的？ 输出清洗后的数据。
Java程序：头部 注意： 输入输出部分与 C++差别很大
逐个将数据输入data 计数器与指针赋值 打印未经清洗的数据
注意： Java程序与C++ 程序结构相似， 而且除了输入输 出，其它语句也 非常相似！
这是用Python语言实现的converging-pointers算法。与C++程序非常相似。
问题7： 你如何理解这段话？
问题8： 那么，怎样才能达到“an unambiguous and formal fashion”呢？ 回忆一下，逻辑语言是如何定义的？
语言是一个集合 问题9: 这是个什么样的集合? 为了简单起见，考虑一个只有“句子”组成规则，但“句子”没有“含义”的语言 首先，必须定义“所允许的符号”-“字母表 = {a, b} 再规定哪些“用a, b构成的符号串”是语言L中“合法”的句子 1. a是<前缀>; 2. <前缀>接a仍然是前缀 3. <前缀>接b是合法句子 4. <合法句子>接b仍然是合法句子 4. 任何合法句子只能通过实行上述规则有限次得到 问题9: 这是个什么样的集合? L = {w | w = aa*bb* }
问题10: 什么是Syntax? Syntax（文法）规定什么样的句子属于特定语言。
最简单的文法：Regular Expression
语言可以由“Acceptor”来判定 开始 b 出错 a 前缀 句子 问题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++语言的算术表达式的完整严格的文法。 试用其它算法解数据清洗问题，编写相应程序，并与课堂上介绍的算法进行比较。