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