科學人／演算法與資料結構的大師：塔揚

塔揚（Robert Tarjan）圖／Renatokeshet, GFDL , via Wikimedia Commons

塔揚（Robert Tarjan）是1986年圖靈獎得主。他在大學畢業之際，面臨一項重要抉擇：繼續研習數學，或是轉向當時方興未艾的計算機科學。他選擇了後者，渴望把數學能力應用於更具實踐意義的領域。在進入美國史丹佛大學攻讀博士期間，塔揚原本想研究人工智慧。在課程導師高德納（Donald E. Knuth）的引導下，他接觸到《電腦程式的藝術》第一卷，自此轉向演算法分析領域，並深深爲之着迷。這一轉變不僅影響了他自身的研究方向，也爲計算機科學界帶來了一連串深遠的突破。

在史丹佛大學期間，塔揚與霍普克洛夫特展開合作，致力於開發圖論演算法。當時的學術界缺乏一套有效的效率分析框架，他們提出一種通用計算模型：以最壞情況執行時間爲基礎，忽略常數因子，確保機器無關性。他們把圖的平面性測試做爲範例問題，成功設計出第一個線性時間的平面性演算法。這項研究是塔揚於1972年在佛洛伊德（Robert W.Floyd）指導下完成的博士論文主題。

這項研究的貢獻解決了圖的可視化難題，更進一步強化了深度優先搜尋（DFS）做爲演算法核心技術的地位。塔揚隨後開發的線性時間強連通分量查找演算法，進一步鞏固了DFS的重要性。這些技術如今已成爲計算機科學領域演算法課程的標準內容。

除了演算法設計，塔揚在資料結構領域的貢獻同樣深遠。他主張，不必拘泥於每次操作的最壞情況時間，更應着眼於整體操作序列的總耗時，這正是所謂的均攤分析（amortized analysis）。

1981~1985年，塔揚兼任紐約大學教授。他與學生薩納克（Neal Sarnak）共同展開持久性資料結構（persistent data structures）研究，修改資料結構時保留過去版本。他們與德里斯科爾（Jim Driscoll）合作發表多篇論文，爲現代版本控制系統與區塊鏈技術間接提供了理論基礎。

塔揚深受學生敬重。他在普林斯頓所授的演算法理論課程廣泛涵蓋其研究領域，例如最小生成樹、不相交集合、費伯納契堆與網路流演算法。他以耐心著稱，重視與學生的個別指導，致力於每位學生的專案達到「A級品質」。這種嚴謹而友善的教學風格，深深影響着新一代的演算法研究者。

塔揚的學術生涯是一段關於創新、堅持與理論美感的旅程。他的研究成果早已成爲演算法設計的基石，影響力跨越數十年、數個世代，爲計算機科學的發展樹立了堅實而優雅的典範。

本專欄感謝臺灣電腦資訊發展館、中華民國資訊軟體服務商業同業公會支持

（本文出自2025.09.01《科學人》網站，未經同意禁止轉載。）