0

37
1

文字

分享

0
37
1

【快訊】數學與計算機科學的交織──2021 阿貝爾獎

PanSci_96
・2021/04/08 ・3202字 ・閱讀時間約 6 分鐘
  • 作者/李奕萱

阿貝爾獎(Abel Prize)自2003年開始由挪威國王頒發給傑出數學家的獎項。阿貝爾獎的歷史可以追溯到1899年,當時挪威數學家索菲斯·李(Sophus Lie)得知阿佛烈·諾貝爾(Alfred Nobel)計劃設立的諾貝爾獎將不包括數學獎,又剛好正逢數學家尼爾斯·亨里克·阿貝爾(Niels Henrik Abel)誕辰100週年紀念,便提出設立阿貝爾獎。 不幸的是,索菲斯·李不久後逝世、提供資金的奧斯卡二世國王也因為瑞典和挪威聯合王國解散而下台,阿貝爾獎這件事也就不了了之。

2001年,人們覺得應該給數學家一個相當於諾貝爾獎的獎項,便再次將阿貝爾獎提案給挪威總理。隔年挪威政府便宣佈撥款2億挪威克朗在數學家阿貝爾誕辰200週年時正式設立阿貝爾獎,並由挪威自然科學與文學院成立阿貝爾委員會負責審理。

阿貝爾獎的獎金高達750萬挪威克朗,是國際數學獎中的最高金額。圖/wikipedia

雖然說阿貝爾獎被譽為數學界的諾貝爾獎,但表彰方向卻和諾貝爾獎不盡相同。舉例來說,諾貝爾物理學獎主要是頒發給對物理作出重要發現或發明的人,像是2020年的諾貝爾獎得主就是成功觀察到銀河系中心的超大質量緻密天體,並發現黑洞的形成是廣義相對論的確鑿預測,因而得獎。阿爾貝獎則是大多頒獎給在數學領域發展中的重要推手,也就是引領數學界的人。

今年挪威科學院將2021年的阿貝爾獎頒給匈牙利羅蘭大學(Eötvös Loránd University)的洛瓦茲·拉茲洛(László Lovász)和美國普林斯頓大學的以色列數學家阿維·威格森(Avi Wigderson),表彰他們對理論計算機科學與離散數學的貢獻,以及將兩者塑造成現代數學的重要領域

“for their foundational contributions to theoretical computer science and discrete mathematics, and their leading role in shaping them into central fields of modern mathematics”

剪不斷理還亂的計算機科學和數學

1970年代,理論計算機科學和純數學是沒什麼關係的兩個學術領域。經過幾十年的發展,這兩個學科之間早已變得極為密切,在現代數學,我們甚至很難分清它們之間的界限。其中,洛瓦斯和威格森就是在最前線開疆闢土的人。

阿貝爾委員會主席漢斯·蒙特·卡斯(Hans Munthe-Kaas)表示:「在過去的幾十年中,洛瓦茲(圖中左)和威格森(圖中右)一直是這一發展的領導力量。他們的工作以多種方式交織在一起,尤其是它們都為理解計算中的隨機性和探索有效計算的邊界做出了根本性貢獻。」圖/The Abel Prize

計算複雜性理論 (Computational complexity theory)是數學和計算機科學領域的一個重要分支。從小我們就知道算數學要快、狠、準,如何更快、更輕鬆地解決問題一直是人類追求的目標。計算複雜性理論通過引入數學計算模型計算各個演算法的資源使用情形,像是時間(透過幾個步驟產出結果)、空間(需要佔用多少記憶體),再進一步進行複雜性分類、聯絡。洛瓦茲設計的LLL演算法、威格森的去隨機化研究對拓寬和深化這個領域的貢獻無疑是最重要的領導者。

從數學到計算機科學──拉茲洛·洛瓦斯

圖/wikipedia

洛瓦茲於1948年出生在布達佩斯,從小就對數學有濃厚的天份,22歲便拿到博士學位,他的早期靈感大部分來自數學家艾狄胥·帕爾(Erdős Pál)。艾狄胥的成就集中在離散關係的數學,而不是典型的連續變量上,也就是組合學、圖論等領域。

組合學(Combinatorics)、圖論(Graph theory)都是離散數學的範疇。前者主要解決組合模型中的存在、計數以及構造等方面的問題;後者作為組合學的分支,將對象之間的關係通過邊和節點組成數學結構圖。拉斯洛·洛瓦茲作為新一代數學家自然不會將離散數學侷限在純數學的理論研究中,他意識到離散數學在計算機科學中非常具有發展潛力,並著手研究離散數學可以解決計算機科學問題的方法。

圖論中的經典七橋問題:在所有橋都只能走一遍的前提下,如何才能把這個地方所有的橋都走遍呢?圖/wikipedia

最著名的研究是由洛瓦茲(Lovász)以及荷蘭數學家阿爾揚·倫斯特拉(Arjen Lenstra)和亨德里克·倫斯特拉(Hendrik Lenstra)的名字命名的LLL演算法(LLL lattice)。這種稱為LLL的算法將由整數組成的大向量分解為各種類型的最短向量的總和,也就是可以計算出空間中的點集與原點的距離。

最初的LLL演算法被應用將多項式時間(Polynomial time,P)以有理係數多項式表示,來找出他的實數近似值來解決固定維數的整數線性規劃問題。LLL演算法在數論、密碼學和通訊計算等領域也都具有顯著的應用,更是現今可以抵禦量子計算機攻擊的加密系統之一。

從計算機科學到數學──阿維·威格森

威格森對他的研究領域一直都充滿熱情,常常感染身旁的同事一起參與研究。圖/Wikipedia

威格森於1956年出生於以色列海法。威格森最著名的成就之一就是闡明了隨機性在計算中的作用。在聊隨機性之前,我們先來聊聊什麼是P, NP:

P和NP是複雜性的類別,P問題是可以快速計算出來的問題,NP問題則是可以快速驗證的問題。

當問你17乘以19是多少時,你可能沒辦法馬上心算出來,但按一按計算機就一定能得出答案,那麼這個問題就是屬於P問題,包含了所有容易解決的計算問題。現在,問你323的所有質因數有哪些呢?問題複雜了許多吧!我們必須從2、3、5……開始慢慢找,正著找質因數很困難,如果我們反著找呢?先告訴你17、19是323的質因數,是不是只要把它們乘在一起就能驗證答案對不對了?這個例子就是屬於NP問題,包含了可能是很難解決的計算問題,但只要有答案就很容易被驗證正確與否。

科學家便提出了一個看法:「會不會其實P=NP?」也就是說NP問題有可能可以被簡單解決。威格森的主要研究就是將複雜性類別一一歸位,將多項式時間演算法完全去隨機化,更快速的得到結果,並把隨機演算法和複雜性理論結合,提出P = BPP(bounded-error probabilistic polynomial time),回答了多年來對P/NP問題的疑問,大大拓寬了資訊界的未來視野。

P/NP問題是一個在理論資訊學中計算複雜度理論領域裡至今未被解決的問題,也是克雷數學研究所七個千禧年大獎難題之一。圖/wikipedia

威格森對貨幣加密的零知識證明也很有貢獻,零知識證明簡單來講就是在不透露任何資訊的情況下驗證正確性的方法。最初是在保護個資方面,像是我們想要申請某個購物網站的會員,我們就必須提供姓名、電話、出生年月日等各種資料來驗證我們的真實身份,但在零知識證明之下我們可以選擇提供「零密碼證明」、隱藏真實密碼,達到完全保護個資的目的。

有些人可能會有疑問說數學有用嗎?數學不是只能拿來算錢嗎?那你就錯了!數學一直扮演著承載科學的角色,躲在背後支持著科學發展,不難發現每一門科學都或多或少跟數學交織在一起,每一年頒發的阿貝爾獎、菲爾茲獎、諾貝爾獎都顯現出這些數學家、科學家正將科學這個巨網越織越堅固。一起為今年的得獎者送上掌聲吧!

圖/Giphy

參考資料

文章難易度

4

12
2

文字

分享

4
12
2

今晚,我想來點……圓周率的派(π)!

PanSci_96
・2021/03/14 ・2391字 ・閱讀時間約 4 分鐘
  • 作者/李奕萱

3 月 14 日是什麼節呢?白色情……呸呸呸!身為科學愛好者今天過的是 π day 啦!

π day 訂在 3 月 14 日,並通常在下午 1 時 59 分慶祝,是取自圓周率(π)的近似值 3.14159 而來。圖/pixabay

2009 年,美國眾議院正式通過麻省理工提出將 3 月 14 日定為國家圓周率日的申請,將 3 月 14 日正式定為圓周率日(pi day)。世界各地的科學家會吃圓周率(派,pie)、喝圓周率(雞尾酒,piña colada)、玩圓周率(皮納塔,piñata)……來紀念這個科學界的重要常數── π。這些人有多喜歡 π 呢?他們甚至發明了 π 語言!

早在 1988 年物理學家 Larry Shaw 就在舊京山的科學探索館舉辦了第一次的「π」對,人們吃派和討論關於π的事物。圖/Wikipedia

什麼是π語言呢?

π語言(Pilish),是一種特殊的書寫格式,每個單詞中的字母數與π的對應數字匹配。第一個單詞包含三個字母,第二個單詞包含一個字母,第三個單詞包含四個字母,依此類推。舉例來說:How I need a drink, alcoholic in nature, after the heavy lectures involving quantum mechanics! 就是典型的π語言,How 由三個字母組成,I 由一個字母組成,並接續下去。人們利用這個格式創作 π 文章或是 π 詩,其中最有名的是邁克爾·基思(Michael Keith)發表的一首以 π 為主題的詩《piku》:

It’s a moon,

A wheel revolving on golden earth, and lotus blossoms.

Mountains embrace windmills, and it all reflects this number, pi.

這首詩不僅符合每個字母數的規定,甚至每句的音節數也符合規定:第一句 3 個音節,第二句 14 個音節,第三句 15 個音節。π 語言除了是一種創作形式,也衍伸出一種記憶技巧──圓周率文字學(Piphilology),先記憶 π 語言撰寫的故事再回復成數字的形式來背誦 π。你想不想也試著寫看看 π 詩呢?

邁克爾甚至用這種語言寫了一本一萬字的書,叫做《不醒》(原文書名 Not A Wake: A Dream Embodying π’s Digits Fully For 10000 Decimals,也符合 π 語言的格式喔!)。圖/amazon

所以 π 是怎麼來的呢?π 又代表什麼呢?


π 源自於希臘語的 περίμετρος,有「周長」的意思,為一個圓的周長和其直徑的比值,看似很簡單的定義卻讓人類研究了數千年還是對她著迷不已。π 是無理數,用小數來表示的話就會形成一個無限的不循環小數,也就是你無法找出這些數字的規律,現代有超級電腦可以幫忙計算,那麼在沒有電腦甚至沒有計算機的的古代呢?

π 的計算最早要回溯到古埃及時期,以畫圓面積的方式計算出 π =3.16,雖然離更正確的 3.14159… 有一段差距,但當時可是公元前 1850 年的石器時代呢!後來曹魏時期的數學家劉徽和希臘化時期的阿基米德相繼提出了以相似多邊形逼近的來估算圓形周長的方式,而這些新方法也讓我們更加接近 π。

π 又有人稱作阿基米德常數,阿基米德晚年致力於幾何研究,相傳在羅馬戰士攻進城裡時阿基米德還在研究 π 的計算。圖/wikipedia

那麼 π 這個神秘的常數,在各個學界有什麼不一樣的地位呢?對於一般人來說,課本告訴我們計算π的時候要代近似值 3.14;對於軟體工程師來說,只要輸入指令就能直接從後台計算π;對數學家來說,近似值根本是邪教!!π 就是圓周跟直徑的比值,就是無法被窮盡的無理數。而這時工程師說話了:「那就當作 3 吧!」數學家頓時氣死在路邊……

工程師把數學裡兩大無理數:圓周率(π)代入 3、數學常數(e)代入 2,時常被做成迷因調侃。

海浪居然也跟 π 有關?


你知道嗎?海浪、聲音、電、路燈光線強度……這些看似跟圓形沒什麼關聯的事物其實都跟 π 有關係喔!還記得高中物理學過的海浪的簡諧運動嗎?當你把一塊會漂浮的木頭丟到海裡,木頭隨著海浪做上下規律的簡諧運動,當你把那塊浮木的運動軌跡記錄下來你就能得到一福完美的波浪圖,而圓型的秘密其實就藏在這幅圖裡!

除了波浪有做簡諧運動,水分子本身也在做簡諧運動。圖/Daniel A. Russell from Longitudinal and Transverse Wave Motion

想像有一個圓形操場,你沿著跑道等速繞圈圈,並且有一道平行光從北邊打過來,這時你就會發現自己印在南邊牆上的影子軌跡也形成一幅一模一樣的波浪圖。也就是說海浪的起伏可以看作是等速度圓周運動的投影,這就說明了簡諧運動中的週期公式 \( T=2π\sqrt{\frac{m}{k_m}} \)為什麼有π在裡面了!

π 還有一些有意思的故事!

世界上有一群熱愛 π 的人,那就有另一群討厭π的人,他們認為我們在計算圓的時候應該使用的常數是 τ(念 Tau,τ=2π),也就是圓周和半徑的比值,τ 的擁護者則會在 6/28 慶祝 τ day。除了科學界慶祝圓周率,影劇界也會開π的玩笑,星際爭霸戰影集在某年 3 月 14 日的劇集中將π的最後一位數當作電腦破譯密碼,但我們知道π是一個無理數,所以我們大概也就永遠無法破解那部電腦了。π 就是這麼神秘且令人著迷,甚至法國奢侈品牌紀梵希就曾經推出一款命名為π的男性香水,是專為聰明、有遠見的男人設計的木質調香。

史巴克:「我們應該都知道 π 是一個無法被解決的超越數吧!」圖/IMDb

3 月 14 日不僅是 π day 同時是愛因斯坦的生日、史蒂芬霍金的忌日,是不是也為這天蒙上更神秘的色彩呢,那麼何不一起吃個派慶祝 π day 吧!

參考資料:

  1. Pi – Wikipedia
  2. Larry Shaw (Pi) – Wikipedia
  3. Exploratorium – Wikipedia
  4. 阿基米德 – 維基百科,自由的百科全書
  5. Daniel A. Russell(2016). Longitudinal and Transverse Wave Motion.
  6. Longitudinal and Transverse Wave Motion

所有討論 4
網站更新隱私權聲明
本網站使用 cookie 及其他相關技術分析以確保使用者獲得最佳體驗,通過我們的網站,您確認並同意本網站的隱私權政策更新,了解最新隱私權政策