韓信點兵 - 中國剩餘定理

>> 2009年8月30日 星期日

相傳漢高祖劉邦,欲擒韓信,但不知其統御兵士多少,恐有變數,故試探問道︰「卿有兵何?」
那知韓信巧妙地回答︰「兵不知數,三三數之剩二,五五數之剩三,七七數之剩二。」
劉邦不懂得答案,問請教於張良。張良正在心中緊張地搬運「籌策」計算看,滿臉迷惑,低聲而惶恐的回答:「兵數無法算,不可數!」
這位以「籌策之術」著名當代,號稱「運籌帷幄之中,決勝千里之外」的張良,竟然也如此回答。大漢皇帝劉邦大吃一驚,一下子酒全化為冷汗,酒全醒了。
這個問題俗稱為「韓信點兵」,大約在三國到魏晉南北朝之間(公元280 ~ 473年)有一本數學古書名叫「孫子算經」就已有這個問題的解:
「三三數之賸二,置一百四十,五五數之賸三,置六十三,七七數之賸二,置三十,並之,得二百三十三,以二百一十減之,即得。凡三三數之賸一,則置七十,五五數之賸一,則置二十一,七七數之賸一,則置十五,即得。」
哈哈,原來當時韓信手上最少只有二十三人就把劉邦嚇怕了。
孫子算經的解法其實也是現今數論證明的內涵,因為其解法遠在一千五百年前就已經為中國人發現,故名中國剩餘定理。它是整數論裡一個非常重要的法則。

Read more...

空蝕效應(Cavitation)和超空蝕效應(Supercavitation)及其應用

>> 2009年8月9日 星期日

「空蝕效應」(Cavitation)是流體動力學、材料學和物理化學的復雜現象,又稱剝蝕或氣蝕。這是用來描述運動物體受到空化沖擊后表面出現的變形和材料剝蝕現象。在流動的液體中,當局部區域的壓力因某種原因而突然下降至與該區域液體溫度相應的氣化壓力以下時,部分液體氣化,溶於液體中的氣體逸出,形成液流中的氣泡(或稱空泡),這一過程稱為空化。空泡隨液流進入壓力較高的區域時,失去存在的條件而突然潰滅,原空泡周圍的液體運動使局部區域的壓力驟增。如果液流中不斷形成、長大的空泡在固體壁面附近頻頻潰滅,壁面就會遭受巨大壓力的反復沖擊,從而引起材料的疲勞破損甚至表面剝蝕,這就叫空化剝蝕,簡稱空蝕。

1902年,最先在英國驅逐艦“Cobra” 號螺旋槳上發現空蝕。接著在水工建筑物和水力機械上也看到同樣的現象。當時認為槳葉材料的剝落是海水腐蝕造成的,但是試驗証明在蒸餾水中運動的物體也會出現類似的剝蝕, 因而確認這種現象僅是機械力沖擊的結果。據現在分析,上述兩種因素都起作用。在空化過程中,空泡急速產生、擴張,又急速潰滅,在液體中形成激波或高速微射流。金屬材料受到沖擊后,表面晶體結構被扭曲,出現化學不穩定性,使鄰近晶粒具有不同的電勢。物體表面局部點上材料剝落后,出現的新的純淨金屬和周圍舊金屬之間構成一對電極而產生腐蝕電流,從而加速電化學腐蝕過程。剝蝕區域中材料的機械性能顯著惡化,從而導致空蝕量激烈增加。因為空泡在潰滅過程中能形成電離層,所以施加適當的外磁場就能控制空蝕程度。

空蝕的程度以空蝕強度來衡量。空蝕強度常用單位時間內材料的減重、減容、穿孔數和表面粗糙度變化作為特征量。空蝕過程分為幾個階段:最初隻有材料表面的變形或少量減重,形成空蝕潛伏區;然后單位時間的減重突然增大,形成空蝕加速區;過些時間后,單位時間的減重慢慢減小,形成空蝕減速區;最后,單位時間的減重基本不變,形成空蝕穩定區。因為液體和材料的性質不同,上述各個階段中的變化也有差異。

空蝕是空化的后果,但並非所有空化都造成材料的損壞,隻有不穩定的空化,如不定常流動中出現的空化或封閉空泡的尾端,才會引起空蝕。因此,空蝕往往出現在物體的局部區域。空蝕的機理與材料受固體微粒或液滴沖擊而損壞是不同的。為消除和減輕空蝕損壞,運動部件應在盡可能穩定的條件下運轉。消極的辦法是在可能發生空蝕的部位涂上或包上彈性強的材料,或注入氣體以吸收空泡潰滅所輻射的能量,也可用化學防腐方法來減輕空蝕過程的腐蝕作用。

超空蝕(Supercavitation)就是運用相同的理論,從穿過水中的物體前方開始,產生一個足以包覆整艘船艦的大氣泡,使得船艦本身完全在氣泡中船行。如此一來,船艦變成和在空氣中前進沒兩樣,除了最尖端產生空蝕效應的那個點阻力較大之外,其餘部份阻力都和在空氣中一樣小。


傳說中蘇聯就用這個技術發展出了一枚名為 Shkval 的火箭魚雷,
可以在水下以每小時 400 公里以上的時速前進。美國自然不可能從這樣的研究中缺席,除了研究超空蝕效應的魚雷和炮彈(可以直接從船上炮轟潛艦)外,自然使用超空蝕效應的潛水艇也在時程上。這個由 DARPA 在 2006 年發包給 Electric Boat(通用動力公司的子公司)的合約,將在明年測試第一艘 1/4 大小的試驗船,最終目標是一艘 30 公尺長,時速 185 公里以上的潛水艇。俄羅斯的火箭引擎推動超空蝕魚雷VA-111 暴風能以200海里(每小時230英里) 的速度行駛。

Read more...

新電腦世代 - CPU加GPGPU的組合

>> 2009年5月31日 星期日

如果說Windows95當年是使用者經驗(User Experience)的一個大躍進,那這個大躍進的成功背後兩大誘因:
一)大部份中央處理器(CPU - Central processing unit)已提供了浮點運算器(FPU) - 由於80486後的CPU已整合了浮點運算器而不再需要另外購買數位輔助處理器(Coprocessor),所以其後大部份軟件都直接使用浮點運算指令,因此大大增強了電腦浮點運算能力。
二)繪圖加速晶片的出現 - 當年出現了很多專爲Windows設計的繪圖加速卡,其原理是用硬件來處理圖像操作好像BitBlt等,因此使用者介面(UI - User Interface)的反應快了很多

等了這多年,Windows的使用者經驗(User Experience)好像再沒有多大的突破,我認爲原因之一是沒有相關的硬體技術的突破,新版本的Windows只會用愈來愈多的系統資源(System Resource),令系統愈來愈慢。而GPGPU(General-Purpose Graphics Processing Units通用繪圖處理器)和OpenCL(Open Computing Language開放運算語言)的出現會是一個新突破.

傳統來說CPU(Central Processing Unit)和GPU(Graphic Processing Unit)兩者河水不犯井水。CPU是十八般武藝樣樣通,尤其擅長處理無可預知的任務;GPU則是精通一種任務,尤其是高度平行(highly parallel)的任務。GPGPU的慨念是以GPU來進行通用的計算,運用GPU裡內含的數十個(高階晶片裡甚至有數百個)處理核心,來加速處理任務。這些任務若交給中央處理器(CPU)來做,其執行效率可能比較差。因此GPU可以作爲CPU的協同處理器,GPU的高速運算能力讓他們在許多不同的應用上都能有很大的助益。

隨著市售的GPU可程式化程度的提升,愈來愈多的應用將會出現。這正是CUDA和OpenCL切入之處,讓開發者能有效率地利用目前閉鎖在繪圖處理器內的運算效能。CUDA是Nvidia提供用來的程式化GPU的API,而OpenCL是一種支援異質運算(heterogeneous computing)的程式設計環境。所謂異質運算,意指混用多核心的CPU與繪圖處理器(GPU)。在和NVIDIA的合作下,Apple於2008夏季向Khronos遞交OpenCL的提案,希望能為GPU運算打造一個跨平台。NVIDIA的內容發展副總裁Neil Trevett擔任OpenCL工作小組的主席一職,Nvidia的軟體研發團隊並直接為此組織提供支援。支持OpenCL的廠商包括Apple(蘋果)、AMD、Intel(英特爾)、Nvidia等,雖然Microsft(微軟)不支持OpenCL,但其程式設計介面(API)DirectX 11亦將會提供使用GPU的API。

已有軟件廠商利用CUDA技術,研發了一個Adobe Premiere Pro的外掛程式。通過外掛程式,使用者就可以利用GPU去加速H.264/MPEG-4 AVC的編碼速度。速度是單純利用CPU作軟件加速的7倍左右。而Mathematica亦將支援使用CUDA來提高計算速度。其它可受惠的應用還包括經常使用FFT(Fast Fourier Transform快速傅立葉轉換)的圖像處理(e.g. JPEG編碼), SSL編碼, Realtime harddisk Encryption等。

OpenCL將成為蘋果作業系統(Snow Leopard)的一部分,而DirectX 11將成為Windows 7的一部分(我相信未來Linux亦會有針對 OpenCL 的支援)。這對消費者的意義是,如果你的筆記型電腦內建Nvidia GPU或ATI (AMD) GPU,作業系統就會跑得比較快,因為作業系統基本上是用兩個處理器來執行。這個CPU加GPGPU的組合,對運算力有相當要求的 H.264 技術有很大的幫助,因為在一些較低規格的電腦,有圖形處理器的幫助,可以很流暢播放 H.264 的片段。就算在智能手機都有高速的圖形處理器和數碼訊號處理器,藉這些硬件來彌補手機處理器運算能量的不足。

使用CPU加GPGPU的組合是電腦史上的其中一大重大改變,短期內未必會改變電腦業界的發展,但長遠而言對電腦業界的版圖,會帶來相當大的改變。但令用戶更充分使用硬件的資源,無論如何都會是一件值得高興的事。

Read more...

從另類搜尋引擎Wolfram Alpha說起到圖靈機(Turing Machine)

>> 2009年5月17日 星期日

Wolfram Alpha是一個很特別的搜尋引擎,這個搜尋引擎最近相當受到網路界的矚目,許多網路觀察家都期待這個產品會成為挑戰 Google 的明日之星,媒體也利用大篇幅來報導這個即將上市的搜尋引擎,大家期待的程度真可說是未上市先轟動。但其實Wolfram Alpha的功能一點也不像Google,更不能說上它是谷歌(Google)殺手。


一般來說Google,Yahoo, MSN Live Search等搜尋引擎的用途是以文字搜尋相關網站 (i.e. 你輸入一個keyword,搜尋引擎幫你從茫茫網站中找到和你的keyword相關的網頁),但Wolfram Alpha的真正用途是查找數據,並從找到的數據進行運算,最後用圖表顯示資料。

可能你沒聽過Wolfram Research這間公司但或許會聽過Mathematica這個有名的數學軟件,Wolfram Alpha就是出品Mathematica的天才創辦人斯蒂芬·沃爾夫勒姆(Stephen Wolfram)的另一傑作。

斯蒂芬·沃爾夫勒姆(Stephen Wolfram)是廣泛地認為是當今科學和技術計算中最重要的革新者。他1959年出生於倫敦,先后在伊頓公學,牛津大學和加利福尼亞理工學院學習。他15歲時發表了他的第一篇學術論文。20歲就在加利福尼亞理工學院獲得了理論物理的博士學位。Wolfram早期的科研工作主要在高能物理、量子場理論和宇宙論方面,包括幾個當今著名的結果。Wolfram 從1973年起開始使用計算機,並且很快成為正在形成的科學計算領域中的領導者。1979,他開始構造SMP——第一個現代計算機代數系,並於1981年開始商業化發行。

由於早期在物理和計算方面的科研工作,1981年Wolfram成為最年輕的MacArthur獎學金獲得者。1981年後期, Wolfram 開始了一個雄心勃勃的新的科學方向:發展本質復雜性的一般理論。 Wolfram的關鍵思想是使用計算機實驗來研究稱作細胞自動控制的簡單計算機程序的行為。1982年,他首先獲得了關於復雜性原因的一系列令人吃驚的發現。Wolfram的關於細胞自動控制的論文的發表導致了科學思維的較大的轉變,並提出了一個新的科學領域的基礎,Wolfram稱該領域為『復雜系統研究』 。

20世紀80年代中期,Wolfram繼續進行復雜性的研究,發現了大量的計算和本質間的基本聯系。提出了諸如計算不可化簡性的概念。Wolfram的工作導致了廣泛的應用——提供了稱為復雜性理論和人工生命的流行運動的主要科學基礎。Wolfram本人使用自己的思想開發了一個新的隨機生成系統和計算流體動力學的新方法——這二者現在被廣泛的使用著。在他的復雜系統研究的工作之後,Wolfram於1986年創建了該領域的第一個研究中心和第一本雜志。接著,在非常成功的學術生涯——首先在加利福尼亞理工學院,然後在普林斯頓高級研究學院,最後在伊利諾斯大學作為物理、數學和計算機科學的教授。其後Wolfram 開辦了Wolfram Research公司。

Wolfram於1986年后期開始開發Mathematica。Mathematica第一版於1988年6月23日發行,作為計算領域的主要進步,立即得到了熱烈歡呼。在隨后的幾年中,Mathematica的流行度迅速增長。Wolfram Research公司成為世界軟件工業的領導。被公認為在技術和商業兩方面都是優秀的。在Mathematica第二版於1991年發行後,Wolfram開始將他的時間分配到Mathematica開發和科學研究兩個方面。從Wolfram Research公司建立起,Wolfram 一直是 Wolfram Research公司的總裁和執行總裁,並且仍然自己負責Mathematica核心系統的設計

2002年,Wolfram出版了一本書"A New Kind of Science"《一個種新科學》,書中他設定了一種特殊的圖靈機(Turing Machine):反復運用最簡單的法則,最後會發展成為一個可解釋宇宙現象的復雜模型。(圖靈機是英國數學家阿蘭·杜林(Alan Mathison Turing)于1936年提出的一種抽象計算模型,其更抽象的意義為一種數學邏輯機,可以看作等價于任何有限邏輯數學過程的終極強大邏輯機器。)

2007年5月,Wolfram 2,3圖靈機研究獎設立,獎勵給証明它是普適的或不是普適的人。2007年10月來自英國伯明翰的一名 20 歲大學生 Alex Smith 已經証明 Wolfram 2,3 圖靈機是通用的。Alex因此獨得了 Wolfram圖靈機研究獎的 25000美元獎金。你可以在這裡閱讀証明的 PDF 版本。現在我們可以確定地球其實可以用一台超級電腦來模擬。

Read more...

無限多項,其和卻是有限

>> 2009年4月23日 星期四

如果有對你對你說把無窮無限多項的級數加起來的和是有限數,你相信嗎。

這種現象,初步看來似乎自相矛盾,但仔細想一想,就會發現非常合理,而且比比皆是。
例如: 0.3333333....  = 3/10 + 3/100 + 3/1000 + ....


Read more...

紋影攝影技術(Schlieren Photography)的應用

>> 2009年4月10日 星期五

紋影(Schlieren)這個現象最早是由英國發明家羅伯特·胡克(Robert Hooke)在1665年發現的,其後由德國科學家托普勒(August Joseph Ignaz Toepler)製造出第一個紋影攝影(Schlieren Photography)裝置。

紋影攝影技術可以拍到平時肉眼看不到的氣流形態,它的原理是利用氣流對光波的擾動,將不可被肉眼看見的氣流的變化,轉化成可以被看見的圖像。最原始的紋影攝影需要一個明亮的光源,精確放置的鏡片,一塊彎曲的鏡子,一個刀片擋住部分的光線,還有其他一些設備用以觀測到空氣中的波動並將其拍攝成像。右圖就是用紋影攝影技術拍下開槍時的氣流形態。

這項技術最初被應用於風洞的氣流研究,特別是高速激波的研究。但這種技術稍加改變,就可以應用於反隱身飛機。不管什麼飛機,在空氣中飛行的時候,都會引起相對平靜的氣流的劇烈擾動,就如同高速快艇在水面上飛馳,掀起一道白色的波浪一樣。飛機對氣流的擾動,會形成巨大的尾渦流,這些渦流會在空中保持很長一段時間,因此,機場上客機的飛機起飛必須間隔一段時間,以使后面的飛機避開前面飛機的渦流,避免發生飛機失控的事故。

飛機的渦流是如此的巨大和持久,雖然用肉眼看不見,但是在紋影攝像機面前,就如同平靜水面上的劃過的波浪一樣清晰。紋影攝影反隱身正是基於這個原理。紋影攝像機雖然看不見隱身飛機,但可以清晰的看見飛機飛行產生的空氣渦流軌跡,而這個渦流軌跡是無法用現有技術消除的,在攝像機上,就像藍天上飛機的尾氣雲一樣明顯。不管任何飛機,都無法擺脫被發現的命運,包括隱身飛機。雖然隱身飛機對自己的尾氣進行了很多技術處理,比如添加特殊的化學物質來降低尾流的溫度,採用特殊的噴射途徑,使其迅速與周圍的空氣混合,如此等等。通過降低紅外信號特征,來實現難以被探測的目的。但是,它無法改變的是,尾流會加熱周圍的空氣,使飛機飛過的地區溫度明顯高於天空背景的溫度。因此,改進紋影攝像機,使其工作的波段處於中遠紅外的波段,在紅外紋影攝像機面前,夜空中隱身飛機擾動的氣流軌跡,就像夜空中流星的軌跡一樣明顯,隱身就根本無從談起。

如果將紅外紋影攝像機,結合被動光學測距技術,就可以對隱身飛機進行有效的定位,多個紋影攝像機連接成監控網絡,就能對隱身飛機進行持續的跟蹤,並且能引導自己的飛機和防空導彈消滅隱身飛機。

美國國防部長羅伯特·蓋茨在2009年4月6日公佈了2010年國防預算案,其中建議停止生產美軍最先進的F22戰鬥機。我想停產F22戰鬥機的其中一個原因可能是因爲F22戰鬥機的其中一個昂貴的原因或賣點:"低可偵測性"(Low Observable)和"隱身性"(Stealth)只是在應用雷達的偵測上面,可是在紋影攝影技術下已變得沒有用武之地了。實在沒有必要用這般貴的造價去造一架"對方有能力偵測到"的"隱身"戰鬥機。

Read more...

甜甜圈=咖啡杯?

>> 2009年1月2日 星期五

如果小明對你說︰『甜甜圈和咖啡杯是一樣的…』 你會有什麼反應呢?

答案是: 小明是拓撲學家(topologist) =P, 因爲數學家John L. Kelley曾說:
拓撲學家是不知道甜甜圈和咖啡杯的分別的人。
看看下圖你就會明白了:

Read more...

  © Free Blogger Templates Joy by Ourblogtemplates.com 2008

Back to TOP