Re: [問題] 複雜度的問題

看板CSSE (電腦科學及軟體工程)作者reader (讀者)時間20年前 (2005/01/26 12:46)推噓0(0推 0噓 0→)

留言0則, 0人參與討論串9/11 (看更多)

※ 引述《klain (klain)》之銘言： : 而且，algorithmic complexity這個名稱好像也不多見， : 還是你是想說Kolmogorov complexity? : 綜觀下來，不知道你想說明的是什麼呢? 用 Turing machine 來計算的複雜度稱作 Turing machine complexity. 另外還有 Bit Complexity 之類的。 Kolmogorov complexity 則算是 algorithmic complexity 當中最主要的一支吧，當然我並不熟悉。我覺得本來這就是一種沒有精確定義的通稱，但意義應該是可以理解的。 : : 另外有不同領域但其實差不多的 program analysis 和 logical depth. : : 其中 program analysis 就真的是研究最短的程式碼長度了。由於它 : : 比較不會陷入函數分析或 Turing Machine 中，看起來比較像電腦科學 : : 領域的東西。 : 請問你文中的"program analysis"跟"函數分析"是一樣的東西嗎? : 又，如果是一樣的，有這名詞的定義嗎? : 我想，可能需要更精確的了解名詞後再討論。 Program Analysis 比較有名的好像是這本書： http://www.imm.dtu.dk/~riis/PPA/ppa.html 它的簡介： http://www.imm.dtu.dk/~riis/PPA/summary.html 另外這裡有以前朋友給我看的一篇文章： http://www.di.ens.fr/~cousot/publications.www/Cousot-81-PFA-ch10-p303-342.pdf 這東西有夠難，所有相關的東西，我從來就沒有真的看懂過。 : 亂入一下， XD : logical depth是不是在討論計算機組織的時候的data path的長度呀? 不是。 logical depth 是 IBM 的 Charles Bennett 提出的東西。常常看見有人提到，但就是沒看到資料。 : 這我也完全不懂，哈哈 : 以上有錯請訂正。對了，這二篇簡介不錯： What is Complexity? http://bruce.edmonds.name/evolcomp/evolcomp_2.html From Philosphy to Program Size http://www.umcs.maine.edu/~chaitin/eesti.html -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 61.222.173.26