馮紐曼

Gordon Lau

Gordon Lau

2018-12-28

今日是12月28日,115年前的今日,一位對現今電腦有深遠影響的天才出世了。他一生對數學、電腦科學、物理學貢獻良多,被譽為電腦科學其 中一位奠基人,與廣為人所知的艾倫‧圖靈齊名,他就是約翰‧ 馮紐曼(John von Neumann)。

von_neumann.gif

電腦結構

要理解他的貢獻,最佳的途徑就是由現今生活事例着手:想像一下,你有一位朋友,說想買一部新的桌面電腦,應該有甚麼組件要買呢?大概你會答道:「 你要先揀好CPU(Central Processing Unit),然後再揀好要幾多Ram(Random Access Memory),再揀要SSD(Solid State disk)定HDD(Hard disk),最後買好機箱及火牛,再買鍵盤(Keyboard)、滑鼠(Mouse)、Mon(Monitor)就得架啦!」如果你的朋友本身不太熟悉電腦,他一定會眉頭緊皺, 不明所以,也許會問:「點解要咁多野?」

這是一個發人深省的問題,現今電腦結構到底從何而來?其實現今桌面電腦、手提電腦、智能電話等等,都是基於馮紐曼於1945年提出的一個電腦結構, 名字就叫做馮紐曼結構(Von Nuemann Architecture)。

von_neumann_architecture.png

馮紐曼的文件提出一部有以下組成部份的電腦:

  1. 處理器(Processing Unit)
  2. 控制器(Control Unit)
  3. 記憶體(Memory)
  4. 外置儲存裝置(Mass Storage)
  5. 輸入及輸出(Input and Output)

現代的CPU同時兼備了1及2,3就是RAM,4就是SSD/HDD,5就是其他所有電腦周邊產品如鍵盤、滑鼠、顯示器等。由此可見,早在第一部個人電腦問世之 前,現代電腦的雛型早已成型,爾後的電腦發展就是不斷改善效能及微小化的課程。

合併排序

編程中有一個很常見的問題,就是將一條序列的物件排序,要將物件排序,有很多不同的方法。電腦科學中有不少類似計算問題,不同的解決方法,通常統稱之為算法(Algorithm)。同樣在1945年,馮紐曼提出了一 個電腦科學學生必學的排序算法,為之合併排序(Mergesort),采用的就是分治法(Divide and Conquer)。將一條序列拆細為許多小序列,再通過合併的 動作將其排好。

merge_sort.gif

以圖示的話,就如以下一幅示意圖。

merge_sort_diagram.png

此合併方法效率相當高,但不一定是最好(平均而言記憶體使用比Quicksort要多),不過合併排序可以輕易並列處理(parallel processing),因此某些 情況比Quicksort更好。

細胞自動機

馮紐曼亦開創了電腦科學中細胞自動機(Cellular Automaton)的研究,所謂細胞自動機,就是一個理論中的模型,由無數個方格所組成,整個平面會隨著 時間演化,每一個方格都有自己的狀態,而每一個方格下一剎那的狀態都取決於鄰居的狀態。有一個很Geeky的遊戲叫生命遊戲(Conway's Game of Life),其中所根據的模型正是細胞自動機。

game_of_life.gif

如果大家有興趣的話,可以去這條連結嘗試一下。

現今大部份對細胞自動機都是關於理論上的研究,可見馮紐曼的研究涵蓋了理論及現實工程的研究。

生平及其他貢獻

馮紐曼是相當多產的學者,一生發表了約150篇論文,除了對電腦科學有巨大貢獻外,在數學上,對幾何學(Geometry)、拓撲學(Topology)、泛函分析 (Functional Analysis)都有很大貢獻,而在物理學上亦對量子力學(Quantum Mechanics)發展有深遠影響,甚至乎對現今經濟學上有舉足輕重地位的 博奕理論(Game Theory)都有涉獵。

馮紐曼生於匈牙利布達佩斯一個猶太家庭,當時是奧匈帝國的一部份,他自小天資聰穎,八歲就能作微積分,講四種語言,輾轉在德國得到博士學位, 1930年移居美國,很多他生平的貢獻都是於美國完成。1957年,馮紐曼於美國因病與世長辭,享年53歲。

要用一篇文章概括馮紐曼的貢獻很困難,因此附上一條維基條目,就是所有以馮紐曼命名的事物列表,列表之長,使人嘆為觀止。

Comments

Read More

資訊熵

破除迷思系列:Programming = Computer Science ?