Category Archive for '數學'

Posted By Mr. Thursday 我們要在網路上找東西的時候,常常會到搜尋引擎裡面,打關鍵字來找文章。然而今天要提到的搜尋演算法,卻和搜尋引擎的「搜尋」兩個字的意思有些不一樣。所謂搜尋演算法,就是一種演算法(之前提到演算法可以看成是一堆步驟,有先後順序,有重覆執行的步驟,有依照條件不同而部分執行的步驟),這個演算法可以幫忙我們解決一個問題,就是在茫茫大海中找到一根針。 舉例來說,今天可能遇到一個問題,是要找出1到100之間的質數。所謂的質數(prime number),就是除了1和他本身可以整除以外,其他小於他的數字都沒辦法整除他,舉例來說:7是質數,因為除了1和7,其他數字像是2,3,4,5,6都沒辦法整除7,所以7是質數。也許你會感到奇怪,我們沒事尋找質數要做甚麼呢?其實質數扮演滿多重要的角色,尤其在之前Mr. Friday在〈ClickClickClick的中忍考試 : 民族主義與網路安全?〉提到資訊安全的問題,一些非對稱式的加密演算法,就是建立在質數的基礎上面,因為質數不好分解,所以兩個乘在一起的質數要分解開來,需要花費很多時間,當花費的時間夠久,加密得到的保障也越大,也就達到加密的效果(譬如說某個密件10年後才能公開,這個演算法能夠讓駭客10年內無法解開就算有效)。因此,找到大質數也是件很重要的事情。

Read Full Post »

一般網路對於搜尋引擎的使用,不外乎就是輸入關鍵字 (input),然後搜尋引擎吐出搜尋結果 (output) 給你。因此我們不難發現現在搜尋引擎的 input 主要是以文字為主,使用者輸入查詢關鍵字,搜尋引擎根據這些文字來搜尋,較為複雜的「以文找文」應用在業界雖然已經出現許久,但是並沒有被大家使用得很廣泛,主要還是因為應用的方式有限,實用性不高。

Read Full Post »

上面這個公式翻譯成白話文的話,就是假設有 n 個網頁連結到你的網站,那麼你的 PageRank 就是這些網頁個別的 PageRank 值除以他們個別的對外連結數目,再白話一點,在你的立場來看,別人的 PageRank 值就是他們手上握有的投票數目,他們對外連結的數目就代表了他們把自己手中的票均分成幾份投了出去。也就是說,別人連結到你的網站,就表示他投了票給你,但是這票的效力有多少,就取決於他把票投給了幾個人,如果他手中的 PageRank 值是 5 (也就是五票),而他把票投給 10 個人的話 (也就是有十個對外連結),那麼你從他手中拿到的票就只有 0.5 票。

Read Full Post »

最近 PTT 的八卦版有一些人在吵一個很有趣的問題:「寫程式究竟需不需要懂數學?」問題一出現之後,正反意見立刻於板上展開廝殺,有些跨入業界的人主張數學不是那麼 重要,最重要的是主管要你的 code,你能準時交出來就好了。也有的人主張數學很重要,寫程式一定要懂數學。我的想法是,數學對於程式設計的發展有著非常重要的角色,然而是不是每個學習程式的人都需要去學習數學,或著是學到某個程度,就是見仁見智。你不懂數學,但是把工具和程式語言用得好,並且能夠展現出軟體工程的素養,你是一個軟 體業界需要的重要人才。你懂了數學,可以打造出更有效率的演算法,對於 Google 這種愛計較搜尋效率和結果的公司,你還是一個重要的人才。

Read Full Post »

想像一下,我剛才說了一句話,那句話是:「想像一下,我剛才說了一句話,那句話是:「想像一下,我剛才說了一句話,那句話是:……….」」,如此下去,就好像站在兩面平行擺設的鏡子中間,鏡子中的影像不斷的重複。再舉個例子,寫完一封信想要匿名保密,就署名「知名不具」。回信的人寫:「知知名不具 具」。之後再回信的時候就變成:知知知名不具具具,加上括號可能比較清楚:(知(知(知名不具)具)具)。

Read Full Post »

Posted by Mr. Friday 首先要感謝一下各位讀者…前兩篇刊出後, 瀏覽人數直線上升, 兩天下來瀏覽人次直接衝過3000人…小弟還是第一次看到這麼多閱讀量, 著實高興了一下, 希望之後大家還會對我的其他文章捧場一下囉(偷打廣告XD), 在此先謝過大家囉. 不過有些讀者看完第二篇之後覺得太深奧了, 還有人說好像在看排隊理論的論文, 不太想看下去, 這這…好吧, 這第三篇我直接下猛藥. 本篇的重點在於 1. 數據顯示, (瞬間平均)下載速度最快是出現在BT檔發佈後的第50小時!!! 2. 數據顯示, 在BT中, 上傳的量越多, 下載速度反而比較慢!!! 3. 數據顯示, 同時開多個BT下載, 下載速度不會變慢!!! 有沒有比較想往下看了呢? XD

Read Full Post »

Posted by Mr. Friday 前一篇文章介紹了BT的基本運作原理,這一篇文章就來看看學術界對這個機制的探討吧。 關於BT機制本身的實驗文章其實不少。2004年一群法國人發表了一篇Dissecting BitTorrent:Five Months in a Torrent’s Life。內容是他們把Red Hat 9的原始檔(約1.77G)放在網路上供人下載,透過Tracker的紀錄機制,觀察BT的下載特性。相較於這群法國人觀察的是單一BT檔的下載過程,紐西蘭Delft大學的研究生則觀察了國外比較有名的BT分享論壇(Supernova.org、Youceff.com等)幾個月來的人潮(大約有六萬人)。從這些鄉野實驗,可以得到幾個基本的結論: (1) BT檔案往往會有flash crowd情形:分享開始的前幾天會湧入大量人潮,然而高潮退去後人也散得快。 (2) 下載的速度呈現「多數人下載慢,極少數人下載速度超快」的情形;不過即使「多數人下載慢」,下載的平均速度仍然比ftp快上不少。根據實驗,平均下載速度是240K,90%的人速度不會超過520K。有極少數的人下載速度會達到每秒3000K以上。 (3) 檔案的存活天數難以從檔案分享十天後的狀況來預測:紐西蘭學生嘗試著去預測檔案存活天數,不過失敗了。後面我們會看到另外一篇paper是如何成功預測的。 就這樣而已嗎?這兩篇實驗雖然做了一段蠻長的時間,可是得出的結論好像跟沒做差不多;我們這些下載者不用做實驗也知道。不過學術界就是這樣:會有人先去做最基本的實驗,弄出一大堆看似無用的數據,接著就會出現根據這些數據做出的漂亮推論。2004年,著名期刊SIGCOMM石破天驚地刊出了一篇論文:「Modeling and Performance Analysis of BitTorrent-Like Peer-to-Peer Networks」,作者是UIUC的Dongyu Qiu與R. Sirkant。該篇文章用廣泛而嚴謹的數學模型推導BitTorrent在穩定態效能、檔案分享效度、Free Rider(不提供上傳頻寬但享受下載速度的懶蟲)等問題,做了一番精闢的解析,讓所有網路學教授驚覺BT中的價值:不只是因為根據BT的數學隨機模型極有研究價值(經數學驗證,BT擁有「無人數上限」、「下載速度不受人潮影響」的特性),更讓他們驚奇的是,這些教授竟然都沒發現身邊有這麼傑出的軟體,而且還是一個無名小卒寫的XD。從該篇文章之後,有更多的學術資源投入與BT相關的研究,BT技術的影響也深入到其他應用,例如隨選視訊(VOD)、CDN等等。

Read Full Post »