跳到主要內容

發表文章

目前顯示的是 6月, 2018的文章

[讀書章節心得]演算法星球-第一章:演算法星球

從分配補給的問題說起,由喬治‧丹齊格發展出單純形法(Simplex Algorithmus)試著解決這個問題。 這個解法也是解決線性規劃式以及離散程式的重要基石。而這也是演算法的一小部分而已。 演算法是由許多許多的簡單步驟所組成,而剛好電腦又擅長處理許多許多的簡單步驟。因此演算法能夠在電腦的運算下發揮它最大的威力。 由於電腦的處理能力有其發展極限所在,那演算法呢? 有個簡單的實驗: 1990有兩個團隊來解決同一個離散程式問題。 假設1990年代電腦使用1990年最佳演算法來解決問題速度為1的話: A團隊經由時光旅行帶來2014年的最佳電腦,並使用1990的最佳演算法來解決問題 B團隊經由時光旅行帶來2014年的最佳演算法,並使用1990的最佳電腦來解決問題。 A團隊最後比原來的速度快了6500倍解決了問題,大致符合摩爾定律 B團隊則是比原來的速度快了87萬倍解決問題,可見得,演算法進步的幅度比電腦運算進步的速度快了數百倍。 這樣說來,演算法帶來的性能提升,是從無到有的,而這點可以成立的原因,是因為我們找出了更簡單省事的方法。 在現代網路連結與完善度的需求,也讓演算式解法持續成長。全球網路彼此連結的趨勢下,很快的我們發現,在小規模狀況能夠自然運作的事情,放大規模可能完全失效(量變造成質變);而完善度的需求(系統的資源必須要最佳的運用),這些都是讓演算法改良的動力。 當然,就像我們知道化學與機械的界線在哪邊一樣,演算法也有它的界線。 演算法的界線: 1. 演算法需要一個連結體幫它連結現實,這個連結體就是資訊的輸入,或稱為一個範例模式或是一個對於現實的了解。 每個演算法的品質都會受限於其連接體(資訊輸入)的品質 ,了解這一點才能夠有意義的去使用演算法 2. 演算法的[決定],和社會科學所論述的決定並不相同,因為社會科學的決定著重的是其中的過程,而並非是結果,而演算法最終則是一個結果。因此演算法可以就細節來做出決定,藉此來協助一個社會大方向的決定成為現實。 3. 演算法的最重要界線,則是演算法思考的[核心構成要件]。硬體的發展會受到物理極限的限制,因此從[計算複雜性理論]來決定每種演算法對於特定問題花費的時間與功夫,直到這個問題被演算法解決所花的時間沒辦法再更進一步為止(沒有辦法更簡單了!)。 [計算複雜性理論]

[讀書章節心得]演算法星球-總覽

章節列表: *第一章: 演算法星球 *第二章: 演算法到底是甚麼 *第三章: 值得知道的演算法萬有引力 *第四章: 萬有引力的西邊 *第五章: 仙境 *第六章: 通往平衡的路 *第七章: 新觀點 *回到家 演算法,懶惰這兩個字的登峰造極之作,通常是為了完成一個任務而存在。 必須要說的是,演算法實際上需要的不是電腦,只需要會算數,就可以了解演算法。 第一章大致上說的是演算法的歷史與來由 第二章則是著重在描述甚麼是演算法的這個問題上 第三章則是談論演算法星球上的萬有引力--複雜性(Complexity) 第四章則是從日常生活中去擷取演算法的例子 第五章在介紹搜尋引擎的種種 第六章則是試著把演算法從科技與生活這兩者取得一個平衡的描述,打破演算法屬於科技這種想法 第七章則是再次介紹演算法的四位大師,從他們的觀點來試著了解演算法與這個世界的關係。