作者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