1

　　每學(xué)期，弗吉尼亞·威廉斯（Virginia Williams）教授都試圖給她的計(jì)算機(jī)科學(xué)本科生上一堂“基礎(chǔ)課”，告訴他們“數(shù)學(xué)是一切的基礎(chǔ)”。

　　通常，選修威廉斯的算法入門課程的學(xué)生都是想要學(xué)習(xí)高階的編程，不少學(xué)生希望有很多編程練習(xí)，或許還能應(yīng)用到深度學(xué)習(xí)等算法，掌握前沿的計(jì)算技術(shù)。但相反，威廉斯的課程卻和數(shù)學(xué)緊密相關(guān)，課上幾乎沒有編程內(nèi)容，而是側(cè)重于如何圍繞核心數(shù)學(xué)模型和概念設(shè)計(jì)算法。

　　數(shù)學(xué)深深地影響了威廉斯的生活。作為兩位數(shù)學(xué)家的孩子，她很早就愛上了這門學(xué)科。在她日后的研究生涯中，她也運(yùn)用數(shù)學(xué)技能在計(jì)算機(jī)科學(xué)領(lǐng)域掀起了波瀾。

　　2012 年，她對一種用于矩陣相乘的算法進(jìn)行了改進(jìn)。矩陣乘法是計(jì)算機(jī)科學(xué)中的一種基本運(yùn)算，而威廉斯的算法被認(rèn)為是 24 年來最快的迭代。幾年后，她和其他科學(xué)家共同建立了一個(gè)新興領(lǐng)域，名為“細(xì)粒度復(fù)雜性”（fine-grained complexity），試圖在某種程度上解釋某些算法解決各種問題最快能有多快。

　　她現(xiàn)在從事的關(guān)于矩陣乘法的研究工作略有變化，已經(jīng)轉(zhuǎn)變?yōu)樽C明現(xiàn)有技術(shù)“已經(jīng)再好不過了”。她說：“我們無法再提高我們自己的算法的表現(xiàn)，所以我們想出了一些方法來解釋為什么我們不能，以及為什么其他方法也不能提高表現(xiàn)。”

　　2

　　威廉斯在保加利亞長大，她從小熱愛數(shù)學(xué)，在學(xué)校里是一名極具天賦的學(xué)生。1999 年，威廉斯考入加州理工學(xué)院。在大二的時(shí)候，她被計(jì)算機(jī)科學(xué)這一新領(lǐng)域吸引。她第一次上編程課就愛上了這門課程。她著迷于矩陣乘法的算法，這些算法的核心是一些繁重的數(shù)學(xué)運(yùn)算。

　　矩陣乘法的算法會對一些與數(shù)據(jù)相對應(yīng)的多個(gè)數(shù)組進(jìn)行計(jì)算，并輸出一個(gè)含有一些目標(biāo)值的組合矩陣。這種算法應(yīng)用廣泛，包括計(jì)算機(jī)圖形學(xué)、產(chǎn)品設(shè)計(jì)、人工智能和生物技術(shù)。2012 年，她針對矩陣乘法開發(fā)了一種新的算法，比庫珀史密斯-威諾格拉德算法（Coppersmith-Winograd algorithm）更快，后者自 20 世紀(jì) 80 年代以來在矩陣乘法中占據(jù)主導(dǎo)地位。威廉斯的方法減少了矩陣相乘所需的步驟。她的算法只比目前的記錄保持者稍慢一點(diǎn)。

　　在 2010 到 2015 年間，威廉斯和她的丈夫、MIT 教授賴恩·威廉斯（Ryan Williams）成為“細(xì)粒度復(fù)雜性”領(lǐng)域的主要奠基人。

　　“計(jì)算復(fù)雜性”中的更早領(lǐng)域所研究的，是基于算法在解決一個(gè)問題時(shí)所需的計(jì)算步驟的閾值，來發(fā)現(xiàn)一些有效的算法，以及可能低效的算法。而細(xì)粒度復(fù)雜性目標(biāo)是將原先的定性區(qū)別細(xì)化為定量指導(dǎo)，以找到解決問題所需的確切時(shí)間。細(xì)粒度復(fù)雜性還通過計(jì)算等價(jià)性將問題歸類在一起，可以更好地證明算法是否真的是最優(yōu)解。

　　例如，有問題A和問題B，表面上看起來，這兩個(gè)問題可能在它們所要解決的內(nèi)容，以及算法所需的步驟上非常不同。但細(xì)粒度復(fù)雜性表明它們的背后其實(shí)是一樣的。因此，如果解決問題A的算法存在更少步驟的可能，那么問題B也一定存在一種步驟更少的算法，反之亦然。另一方面，如果一個(gè)問題存在可證明的最優(yōu)算法，那么所有等價(jià)問題都有最優(yōu)算法。如果有人找到一個(gè)更快的算法來解決一個(gè)問題，那所有等價(jià)問題都可以被更快地解決。

　　自從他們共同開創(chuàng)這個(gè)領(lǐng)域以來，它已經(jīng)逐漸壯大。目前，許多研究生和科研人員都在從事與細(xì)粒度復(fù)雜度相關(guān)的工作。威廉斯也在嘗試在其他學(xué)科中引入細(xì)粒度復(fù)雜性的想法。

　　3

　　威廉斯的另一個(gè)感興趣的課題是“計(jì)算社會選擇”（computational social choice）。她主要研究的是對體育賽事、投票方案等系統(tǒng)進(jìn)行操縱時(shí)所需的計(jì)算復(fù)雜性。在這些系統(tǒng)中，競爭對手成對出現(xiàn)。威廉斯作為一個(gè)網(wǎng)球愛好者，在 2010 年發(fā)表了一篇論文，她發(fā)現(xiàn)操縱一個(gè)淘汰賽讓某一位運(yùn)動員贏得比賽其實(shí)并不復(fù)雜，這取決于對配對比賽的勝利者的準(zhǔn)確預(yù)測和其他一些因素。

　　2019 年，她與其他科學(xué)家合著了一篇論文，表明賽事組織者可以通過某種最初的賽事安排，并在特定的預(yù)算內(nèi)賄賂某些頂級選手，來確保一個(gè)最受歡迎的選手贏得比賽。盡管模擬所有可能的組合來操縱這些方案非常復(fù)雜，但威廉斯說：“當(dāng)我需要從平時(shí)的工作中解脫出來時(shí)，我就鉆研這個(gè)領(lǐng)域。這是一個(gè)有趣的節(jié)奏變化。”

　　現(xiàn)如今，由于計(jì)算機(jī)的普及，威廉斯的研究生進(jìn)入她的課堂時(shí)所掌握的計(jì)算機(jī)科學(xué)方面的經(jīng)驗(yàn)，比她同齡時(shí)要豐富得多。威廉斯表示，她希望在算法課堂有限的時(shí)間里，讓學(xué)生能看到一點(diǎn)數(shù)學(xué)之美，因?yàn)閿?shù)學(xué)讓我們看到一切是如何在一起協(xié)作的，以及為什么會這樣。

　　威廉斯說：“為了做好研究，你必須沉迷于一個(gè)問題。我希望他們能在我的課程中找到一些能讓他們?yōu)橹缘臇|西。”

總結(jié)

以上是生活随笔為你收集整理的寻找算法的真正潜力的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。