0

38
3

文字

分享

0
38
3

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

Yi-Hsuan Lee_96
・2021/04/08 ・3202字 ・閱讀時間約 6 分鐘 ・SR值 534 ・七年級

  • 作者/李奕萱

阿貝爾獎(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

參考資料

文章難易度
Yi-Hsuan Lee_96
3 篇文章 ・ 1 位粉絲
Science Communicator | 數學系畢業,跑到心理系當了一年間諜,現在是應用科學研究生。喜歡文學、古典戲劇和薏仁。立志在台灣創造一個老人小孩都能樂在其中的科普空間。

0

2
2

文字

分享

0
2
2
【成語科學】運籌帷幄:古人不用筆算數學?一隻小竹棍居然可以開三次方根、解方程式!
張之傑_96
・2023/07/28 ・1261字 ・閱讀時間約 2 分鐘

劉邦(漢高祖)打敗項羽,取得天下,建立漢朝。一天舉行盛大宴會,他問群臣:「我為什麼會勝?項羽為什麼會敗?」群臣都說劉邦善於用人,項羽恰恰相反。劉邦點頭稱是,司馬遷在《史記‧高祖本紀》記下劉邦說的一段話

夫運籌帷幄之中,決勝於千里之外,吾不如子房。

帷幄,指營帳子房,是張良的字籌,指算籌,是古時的運算工具。這段話的意思是說,張良在營帳中運用算籌計算,就能決勝千里之外,這方面我(劉邦)不如張良。因此,這個成語的原意是在營帳中策劃謀略,後來泛指謀劃或指揮。讓我們造兩個句吧。

要不是孔明運籌帷幄,劉備哪有三分天下的機會!

在里長的運籌帷幄下,為社區更新取得有利的條件。

不用筆,那用什麼?

成語的出典說了,句子也造了,接下去就要談談這個成語的科學意義。我們現在演算數學,都是用筆在紙上運算,也就是筆算。古人呢?古人從來不用筆算,而是使用工具運算。元代以前使用算籌,元代以後使用算盤

算盤一直使用到 1980 年代,小朋友家裡可能還有。至於算籌,只有少數博物館裡才能看到。

國立自然科學博物館內藏的漢朝骨製算籌複製品。圖/wikipedia

其實算籌只是一根根小竹棍,外形和筷子差不多。小朋友千萬不要看輕這些小竹棍,中國古代的數學曾經輝煌一時,就是用這些小竹棍運算出來的。

驚人的運算能力 曾經輝煌一時的數學成就

算盤被木框框住,計算能力受到限制。凡是算盤能算的,算籌一定能算。反過來,算籌所能算的,算盤就不見得勝任。算盤主要是生意人用的,算籌可作各種運算,數學家喜歡用它。中國的數學宋代發展到顛峰,元代以後不進反退,到了明代已沒人懂得宋代的數學了。

算籌平時放在算袋裡,繫在腰上,運算時取出,在席子上或桌子上擺弄。除了加減乘除,還能開平方、開立方,甚至解高次方程等高中才學得到的數學!關於算袋,有個小故事,傳說秦皇島東巡時,把算袋扔到海裡,變成了烏賊,所以烏賊又稱算袋魚。

十四世紀朱世傑《四元玉鑒》中的「古法七乘方圖」,紀錄宋代展出的「楊輝三角形」,就是我們現在所說的「巴斯卡三角形」。圖中一根根長條物就是當時用來計算的「算籌」。楊輝三角形的產生也顯見宋代數學已經發展出高次多項式的乘法。圖/wikipedia

數學家用算籌運算時,有時擺弄得極快,不要說外行人,連內行人的眼睛幾乎都跟不上,所以古人用「運籌如飛」來形容。因此,用算籌運算,運算過程不會留下記錄,一陣擺弄之後,最後得出答案。這對一般才質的人來說,學起來的確有點困難。

張之傑_96
98 篇文章 ・ 221 位粉絲
張之傑,字百器,出入文理,著述多樣,其中以科普和科學史較為人知。

2

2
2

文字

分享

2
2
2
買樂透真的可以賺錢?大數法則揭示了賭博的真相!——《統計,讓數字說話》
天下文化_96
・2023/03/05 ・2394字 ・閱讀時間約 4 分鐘

  • id S. Moore、諾茨 William I. Notz
  • 譯者:鄭惟厚、吳欣蓓

什麼是大數法則?

期望值的定義是:它是可能結果的一種平均,但在計算平均時,機率大的結果占的比重較高。我們認為期望值也是另一種意義的平均結果,它代表了如果我們重複賭很多次,或者隨機選出很多家戶,實際上會看到的長期平均。這並不只是直覺而已。數學家只要用機率的基本規則就可以證明,用機率模型算出來的期望值,真的就是「長期平均」。這個有名的事實叫做大數法則。

大數法則
大數法則(law of large numbers)是指,如果結果為數值的隨機現象,獨立重複執行許多次,實際觀察到的結果的平均值,會趨近期望值。

大數法則和機率的概念密切相關。在許多次獨立的重複當中,每個可能結果的發生比例會接近它的機率,而所得到的平均結果就會接近期望值。這些事實表達了機遇事件的長期規律性。正如我們在第 17 章提過的,它們是真正的「平均數定律」。

大數法則解釋了:為什麼對個人來說是消遣甚至是會上癮的賭博,對賭場來說卻是生意。經營賭場根本就不是在賭博。大量的賭客贏錢的平均金額會很接近期望值。賭場經營者事先就算好了期望值,並且知道長期下來收入會是多少,所以並不需要在骰子裡灌鉛或者做牌來保證利潤。

賭場只要花精神提供不貴的娛樂和便宜的交通工具,讓顧客川流不息進場就行了。只要賭注夠多,大數法則就能保證賭場賺錢。保險公司的運作也很像賭場,他們賭買了保險的人不會死亡。當然有些人確實會死亡,但是保險公司知道機率,並且依賴大數法則來預測必須給付的平均金額。然後保險公司就把保費訂得夠高,來保證有利潤。

  • 在樂透彩上做手腳

我們都在電視上看過樂透開獎的實況轉播,看到號碼球上下亂跳,然後由於空氣壓力而隨機彈跳出來。我們可以怎麼樣對開出的號碼做手腳呢? 1980 年的時候,賓州樂透就曾被面帶微笑的主持人以及幾個舞台工作人員動了手腳。

他們把 10 個號碼球中的 8 顆注入油漆,這樣做會把球變重,因此可保證開出中獎號碼的 3 個球必定有那 2 個沒被注入油漆的號碼。然後這些傢伙就下注買該 2 個號碼的所有組合。當 6-6-6 跳出來的時候,他們贏了 120 萬美元。是的,他們後來全被逮到。

歷史上曾有主持人在樂透上做手腳,後來賺了 120 萬美元隨後被逮捕。圖/envatoelements

深入探討期望值

跟機率一樣,期望值和大數法則都值得再花些時間,探討相關的細節問題。

  • 多大的數才算是「大數」?

大數法則是說,當試驗的次數愈來愈多,許多次試驗的實際平均結果會愈來愈接近期望值。可是大數法則並沒有說,究竟需要多少次試驗,才能保證平均結果會接近期望值。這點是要看機結果的變異性決定。

結果的變異愈大,就需要愈多次的試驗,來確保平均結果接近期望值。機遇遊戲一定要變化大,才能保住賭客的興趣。即使在賭場待上好幾個鐘頭,結果也是無法預測的。結果變異性極大的賭博,例如累積彩金數額極大但極不可能中獎的州彩券,需要極多次的試驗,幾乎要多到不可能的次數,才能保證平均結果會接近期望值。

(州政府可不需要依賴大數法則,因為樂透彩金不像賭場的遊戲,樂透彩用的是同注分彩系統。在同注分彩系統裡面,彩金和賠率是由實際下注金額決定的。舉例來說,各州所辦的樂透彩金,是由全部賭金扣除州政府所得部分之後的剩餘金額來決定的。賭馬的賠率則是決定於賭客對不同馬匹的下注金額。)

雖然大部分的賭博遊戲不及樂透彩這樣多變化,但要回答大數法則的適用範圍,較實際的答案就是:賭場的贏錢金額期望值是正的,而賭場玩的次數夠多,所以可以靠著這個期望值贏錢。你的問題則是,你贏錢金額的期望值是負的。全體賭客玩的次數合起來算的話,當然和賭場一樣多,但因為期望值是負的,所以以賭客整體來看,長期下來一定輸錢。

然而輸的金額並不是由賭客均攤。有些人贏很多錢,有些人輸很多,而有些人沒什麼輸贏。賭博帶給人的誘惑,大部分是來自賭博結果的無法預測。而賭博這門生意仰賴的則是:對賭場來說,結果並非不可測的。

對賭場來說,贏錢金額期望值為正。圖/envatoelements
  • 有沒有保證贏錢的賭法?

把賭博很當回事的賭客常常遵循某種賭法,這種賭法每次下注的金額,是看前幾次的結果而定。比如說,在賭輪盤時,你可以每次把賭注加倍,直到你贏為止—或者,當然,直到你輸光為止。即使輪盤並沒有記憶,這種玩法仍想利用你有記憶這件事來贏。

你可以用一套賭法來戰勝機率嗎?不行,數學家建立的另一種大數法則說:如果你沒有無窮盡的賭本,那麼只要遊戲的各次試驗(比如輪盤的各次轉動)之間是獨立的,你的平均獲利(期望值)就會是一樣的。抱歉啦!

  • 高科技賭博

全美國有超過 700,000 台吃角子老虎(拉霸)。從前,你丟硬幣進去再拉下把手,轉動三個輪子,每個輪子有 20 個圖案。但早就不是這樣了。現在的機器是電動遊戲,會閃出許多很炫的畫面,而結果是由隨機數字產生器決定的。

機器可以同時接受許多硬幣,有各種讓你眼花撩亂的中獎結果,還可以多台連線,共同累積成連線大獎。賭徒仍在尋找可以贏錢的賭法,但是長期下來,隨機數字產生器會保證賭場有 5% 的利潤。

——本文摘自《統計,讓數字說話》,2023 年 1 月,天下文化出版,未經同意請勿轉載。

所有討論 2
天下文化_96
129 篇文章 ・ 614 位粉絲
天下文化成立於1982年。一直堅持「傳播進步觀念,豐富閱讀世界」,已出版超過2,500種書籍,涵括財經企管、心理勵志、社會人文、科學文化、文學人生、健康生活、親子教養等領域。每一本書都帶給讀者知識、啟發、創意、以及實用的多重收穫,也持續引領台灣社會與國際重要管理潮流同步接軌。

0

2
2

文字

分享

0
2
2
假藥也能治療?安慰劑效應的原因:「不」隨機化實驗!——《統計,讓數字說話》
天下文化_96
・2023/03/03 ・1932字 ・閱讀時間約 4 分鐘

  • 作者:墨爾 David S. Moore、諾茨 William I. Notz
  • 譯者:鄭惟厚、吳欣蓓

實驗法中「隨機化」的必要性

隨機化比較實驗是統計學裡面最重要的概念之一。它的設計是要讓我們能夠得到釐清因果關係的結論。我們先來弄清楚隨機化比較實驗的邏輯:

  • 用隨機化的方法將受試者分組,所分出的各組在實施處理之前,應該各方面都類似。
  • 之所以用「比較」的設計,是要確保除了實驗上的處理外,其他所有因素都會同樣作用在所有的組身上。
  • 因此,反應變數的差異必定是處理的效應所致。

我們用隨機方法選組,以避免人為指派時可能發生的系統性偏差。例如在鐮形血球貧血症的研究中,醫師有可能下意識就把最嚴重的病人指派到羥基脲組,指望這個正在試驗的藥能對他們有幫助。那樣就會使實驗有偏差,不利於羥基脲。

從受試者中取簡單隨機樣本來當作第一組,會使得每個人被選入第一組或第二組的機會相等。我們可以預期兩組在各方面都接近,例如年齡、病情嚴重程度、抽不抽菸等。舉例來說,隨機性通常會使兩組中的吸菸人數差不多,即使我們並不知道哪些受試者吸菸。

實驗組與對照組除主要測量變數外,其餘條件必需盡可能相似。圖/envatoelements

新藥研究上不隨機分組帶來的後果:安慰劑效應

如果實驗不採取隨機方式,潛藏變數會有什麼影響呢?安慰劑效應就是潛藏變數,只有受試者接受治療後才會出現。如果實驗組別是在當年不同時間進行治療,所以有些組別是在流感季節治療,有些則不是,那麼潛藏變數就是有些組別暴露在流感的程度較多。

在比較實驗設計中,我們會試著確保這些潛藏變數對全部的組別都有相似的作用。例如為了確保全部的組別都有安慰劑效應,他們會接受相同的治療,全部的組別會在相同的時間接受相同的治療,所以暴露在流感的程度也相同。

要是告訴你,醫學研究者對於隨機化比較實驗接受得很慢,應該不會讓你驚訝,因為許多醫師認為一項新療法對病人是否有用,他們「只要看看」就知道。但事實才不是這樣。有很多醫療方法只經過單軌實驗後就普遍使用,但是後來有人起疑,進行了隨機化比較實驗後,卻發覺其效用充其量不過是安慰劑罷了,這種例子已經不勝枚舉。

曾有人在醫學文獻裡搜尋,經過適當的比較實驗研究過的療法,以及只經過「歷史對照組」實驗的療法。用歷史對照組做的研究不是把新療法的結果和控制組比,而是和過去類似的病人在治療後的效果做比較。結果,納入研究的 56 種療法當中,用歷史對照組來比較時,有 44 種療法顯示出有效。然而在經過使用合適的隨機化比較實驗後,只有 10 種通過安慰劑測試。即使有跟過去的病人比,醫師的判斷仍過於樂觀。

過去醫學史上常出現新藥實際沒療效,只能充當安慰劑效果的情況。圖/envatoelements

目前來說,法律已有規定,新藥必須用隨機化比較實驗來證明其安全性及有效性。但是對於其他醫療處置,比如手術,就沒有這項規定。上網搜尋「comparisons with historical controls」(以歷史對照組來比較)這個關鍵字,可以找到最近針對曾使用歷史對照組試驗的其他醫療處置,所做的研究。

對於隨機化實驗有一件重要的事必須注意。和隨機樣本一樣,隨機化實驗照樣要受機遇法則的「管轄」。就像抽一個選民的簡單隨機樣本時,有可能運氣不好,抽到的幾乎都是相同政治傾向一樣,隨機指派受試者時,也可能運氣不好,把抽菸的人幾乎全放在同一組。

我們知道,如果抽選很大的隨機樣本,樣本的組成和母體近似的機會就很大。同樣的道理,如果我們用很多受試者,加上利用隨機指派方式分組,也就有可能與實際情況非常吻合。受試者較多,表示實驗處理組的機遇變異會比較小,因此實驗結果的機遇變異也比較小。「用足夠多的受試者」和「同時比較數個處理」以及「隨機化」,同為「統計實驗設計」的基本原則。

實驗設計的原則
統計實驗設計的基本原則如下:
1. 要控制潛在變數對反應的影響,最簡單的方法是同時比較至少兩個處理。
2. 隨機化:用非人為的隨機方法指派受試者到不同的實驗處理組。
3. 每一組的受試者要夠多,以減低實驗結果中的機遇變異。

——本文摘自《統計,讓數字說話》,2023 年 1 月,天下文化出版,未經同意請勿轉載。

天下文化_96
129 篇文章 ・ 614 位粉絲
天下文化成立於1982年。一直堅持「傳播進步觀念,豐富閱讀世界」,已出版超過2,500種書籍,涵括財經企管、心理勵志、社會人文、科學文化、文學人生、健康生活、親子教養等領域。每一本書都帶給讀者知識、啟發、創意、以及實用的多重收穫,也持續引領台灣社會與國際重要管理潮流同步接軌。