作者neverfly (neverfly)
站内Prob_Solve
标题Re: [问题] 关於演算的观念
时间Mon Aug 24 13:53:25 2009
※ 引述《hannibal0416 (han)》之铭言：
1F：推 march20:请问这定义出处为何? 08/17 08:54
2F：推 flamerecca:knuth的圣经本"the art of computer programming" 08/17 11:24
3F：推 march20:口也, 要注意 knuth 在说这段话时, 并没用 "必需" 这样的 08/17 18:47
4F：推 march20:强烈字眼 (喵的, 我在说废话, 请省略 XD) 08/17 18:52
5F：→ hannibal0416:呃，没"必需"@@我抄的笔记有@@，可能抄错了@@ 08/18 13:10
6F：推 march20:你应该是没抄错, 原文似乎是widely accepted requirements 08/18 23:41
7F：推 march20:真的要挑骨头, 只能说这个定义不够严格 XD 08/18 23:42
还是拿原文来讨论比较有劲吧。
Knuth (1968, 1973) has given a list of five properties that are widely
accepted as requirements for an algorithm:
Finiteness:
"An algorithm must always terminate after a finite number of steps"
Definiteness:
"Each step of an algorithm must be precisely defined; the
actions to be carried out must be rigorously and unambiguously specified
for each case"
Input:
"...quantities which are given to it initially before the algorithm
begins. These inputs are taken from specified sets of objects"
Output:
"...quantities which have a specified relation to the inputs"
Effectiveness: "... all of the operations to be performed in the algorithm
must be sufficiently basic that they can in principle be done exactly and in
a finite length of time by a man using paper and pencil"
他在定义里面哪里没有用"必须"这麽强烈的字眼了？
难道"must"这个字有其他更严谨的定义吗？
因为演算法的定义可以不止一种，上面的定义只不过是knuth所订出来的，
只要你开心，你也可以订一个不需要有限性的演算法定义，只不过没什麽人鸟而已，
所以这个定义才会说是被广泛接受的，而不是真理。
但是你要说knuth订的不够严格，我想这可能算是一种人身攻击吧。
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 114.43.192.50
8F：推 march20:你说的我都同意, 但为什麽这样叫人身攻击? 08/25 06:02
9F：推 march20:而且我都承认是在挑骨头了, 表示我也觉得这样说不合理咩XD 08/25 06:14
10F：→ AmosYang:就演算法来说 "可能" 这两个字并不是很严谨啊… (离题) 08/25 11:22
11F：推 march20:喵的, 我想说离题太远, 跟大家道歉, 没想到真的有人觉得 08/25 12:34
12F：推 march20:定义演算法很无聊? 还觉得 08/25 12:34
13F：推 march20:"Each step of an algorithm must be precisely defined" 08/25 12:35
14F：推 march20:之类的说法不可能 "更严格" ? 08/25 12:35
15F：推 march20:有 Introduction to the Theory of Computation 的人 08/25 12:35
16F：推 march20:请翻一下 3.3 然後说 "严格地定义演算法" 很无聊 08/25 12:36
17F：推 march20:再次重申 "人身攻击" 跟 "人格攻击" 一点都不相同 08/25 12:36
18F：推 march20:而且我一个也没犯, 谢谢! 08/25 12:36
20F：推 Hseuler:这的确没有人身攻击啊 08/25 17:14
21F：→ neverfly:原来所谓的严格定义，是要严格定义在定义前面那句描述 08/25 17:33
22F：→ neverfly:而不是严格定义出定义本身，真是让人大开眼界 08/25 17:33
23F：→ neverfly:演算法的定义本来就不止一种，怎能要求Knuth一定要说： 08/25 17:34
24F：→ neverfly:"Each step of an algorithm must be precisely defined" 08/25 17:34
25F：→ neverfly:这麽果断的话？他底下的定义本身又哪里没有用强烈的字了? 08/25 17:34
26F：→ neverfly:就好像有人解了一题难题，然後补上："这是其中一种解法" 08/25 17:36
27F：→ neverfly:然後有人推论出："吼，这代表他的解法不够严格"一样奇怪 08/25 17:36
28F：推 march20:那请告诉我什麽叫 "precisely" defined 08/26 00:30
29F：推 march20:请问给出像类似 Turing machine 的定义会不会比单这句 08/26 00:31
30F：推 march20:precisely defined "严格" 呢? 08/26 00:31
31F：推 march20:然後我完全看不懂 "原来所谓的严格定义" 08/26 00:32
32F：推 march20:"原来所谓的严格定义，是要严格定义在定义前面那句描述" 08/26 00:32
33F：推 march20:是在讲什麽. 再来, 请你说明我何处做了怎样的人身攻击? 08/26 00:33
34F：推 march20:(当看到 "人身攻击" 之後, 总个人火了起来....) 08/26 00:33
35F：推 march20:我同意 "解法" 本身没 "严格" 的问题, 但这里是讲 "定义" 08/26 00:34
36F：推 march20:定义本来就有严格不严格的问题了. 照你这样说量子力学 08/26 00:35
37F：推 march20:也不需要存在,而量子力学的存在不就是对牛顿的"人身攻击"? 08/26 00:36
38F：推 march20:对了 "Each step of an algorithm must be precisely defi 08/26 00:45
39F：推 march20:fined" 就是 knuth 说的, 请看仔细 08/26 00:45
40F：推 march20:而且我并没用你说的 "给出其中一种解法, 所以不严格" 这种 08/26 03:11
41F：推 march20:说法来推论 knuth 的定义不严格,你告诉我,我哪里这样说了? 08/26 03:12
42F：推 march20:请不要将不相关的两个言句自行做联结, 并据以为非好吗? 08/26 03:13
43F：推 ledia:这种显然是拿一句话就来乱战的, 没必要为他生气 08/28 11:07
44F：→ ledia:让小的来混战就好 (误) 08/28 11:08
45F：推 flamerecca:以knuth的声望 指责他那本书不严谨似乎蛮强烈的 08/28 11:58
46F：→ flamerecca:倒也不是说就不可批评他或怎样 只不过... 08/28 11:59
47F：→ flamerecca:私心是认为march20大以错误的论述说人 因看起来就变得 08/28 12:00
48F：→ flamerecca:有点像那群整天批评相对论的怪人吧.... 08/28 12:01
49F：推 march20:我承认我的说法确实有不合理, 但说这个说法不够严格的人 08/28 13:40
50F：推 march20:可是 knuth 自己唷 XD 08/28 13:40
51F：推 march20:我最不能接受的是 ptt 上特别爱用所谓的 "人身攻击" 08/28 13:41
52F：推 march20:偏偏知道什麽叫"人身攻击" 的少之又少, 似乎只要有一吵架 08/28 13:42
53F：推 march20:"人身攻击" 马上就可以变成大绝一样 08/28 13:43
54F：推 march20:(那个什麽 must 的, 是我胡言乱语, 不过似乎没人看到我写 08/28 13:56
55F：推 march20:的那句, 再次为我的胡言乱言道歉 XD, 不过不够严格可就不 08/28 13:57
56F：推 march20:是随便说了, 虽然是在挑骨头. 这两件事彼此无关, 请 08/28 13:58
57F：推 march20:勿作联结...) 08/28 13:58
58F：推 march20:好了, 接下来还有什麽 "错误推论" 请多指教! 08/28 14:00
60F：→ AmosYang:接下来我们来看看 Knuth 对 ad hominem 演算法的定义(误) 08/28 17:41