iT邦幫忙

鐵人檔案

2019 iT 邦幫忙鐵人賽
回列表
自我挑戰組

當傳統演算法遇到新的計算模型 系列

參賽天數 21 天 共 21 篇文章 | 4 人訂閱 訂閱系列文
DAY 1

Day 1: 演算法無所不在

寫程式的目的,即是把不斷重複的計算流程自動化。而演算法,則是用以明確定義自動化後的計算流程。在設計演算法之前,除了對於要解決的問題有一定程度的認識以外,還必須考...

2018-10-16 ‧ 由 tmt514 分享
DAY 2

Day 2: 隨機存取模型(一) Word RAM Model, Part 1

好啦,昨天好像有點講太長了。今天開始文章會很短。今天來介紹隨機存取模型~ 為什麼會有隨機存取模型呢?我們知道現在的電腦有「記憶體位址」這樣的東西。為了讓中央處理...

2018-10-17 ‧ 由 tmt514 分享
DAY 3

Day 3: 隨機存取模型(二) Word RAM Model, Part 2

如果我們想要儲存的資料都「短短的」, 如同今天這篇也短短的 ,一個字組可以同時塞入很多資料,這麼一來,我們可以藉由 CPU 的能力幫助我們快速運算。一個常見的應...

2018-10-18 ‧ 由 tmt514 分享
DAY 4

Day 4: 隨機存取模型(三) Word RAM Model, Part 3

讓我們今天繼續跟向量奮戰吧! 向量的內積 在可以使用乘法而且不會溢位的情況下,我們可以用一次乘法 (摺積,Convolution、又稱捲積) 就把內積的值算出來...

2018-10-19 ‧ 由 tmt514 分享
DAY 5

Day 5: 隨機存取模型(四) Word RAM Model, Part 4

慘慘慘今天整個沒有時間... 今天來聊聊字組內任意順序的調換。這個動作對於排序的其中一步是相當重要的。 簡單來說,在字組內部排序的時候,我們想要依照某個順序重新...

2018-10-20 ‧ 由 tmt514 分享
DAY 6

Day 6: 隨機存取模型(五) Word RAM Model, Part 5

前情提要 我們在這個模型中,假設了一個長度為 w-bit 的字組內可以儲存 k 個整數值,基於避免溢位、或互相影響的情形下,我們不妨假設每個數值前面都順便預留了...

2018-10-21 ‧ 由 tmt514 分享
DAY 7

Day 7: 外部存取模型 External Memory Model

要處理的資料在同一台電腦裡面,如果資料量超過實際記憶體能夠存取的範圍的話,在存取時就必須要到硬碟裡面把資料撈出來。所以實際上整個程式運作的瓶頸便是在與硬碟溝通所...

2018-10-22 ‧ 由 tmt514 分享
DAY 8

Day 8: 平行計算模型(一)Parallel Computation Model, Part 1 -- 加總問題

共享記憶體 在這篇文章當中,我們探討的平行計算模型是,所有的處理器都有共享記憶體。看到這個詞應該很多朋友第一時間腦中都會蹦出一個詞彙叫做 共享經濟,想必相當划算...

2018-10-23 ‧ 由 tmt514 分享
DAY 9

Day 9: 平行計算模型(二) Parallel Computation Model, Part 2 -- 搜索問題

一些經典的搜索問題—比方說數獨、比方說N皇后問題等,當我們被允許使用不只一個執行緒找答案的時候,通常可以有不錯的加速效果。而理由不外乎就是因為這些搜索演算法的工...

2018-10-24 ‧ 由 tmt514 分享
DAY 10

Day 10: 平行計算模型(三) Parallel Computation Model, Part 3 -- 前綴極小值問題

今天跟大家聊個簡單的問題:前綴極小值問題。 我們知道計算 min 可以在 O(n/p) 時間算得,但由於有 n 個值要輸出,一個顯然的平行算法可以在 O(n^...

2018-10-25 ‧ 由 tmt514 分享