李中志
不少人說 FFT (快速傅立葉轉換) 是所有算法中最重要的一個，我不是很同意，但在CS以外領域可能不假。別說通訊，影像的壓縮也用到。連我一直唱衰的量子計算，我也得承認量子電腦的確可以再助 FFT 一臂之力，叫 QFT，雖然離實用還遠，但算法上已證可行，這是量子計算少數不唬爛的例子。
FFT 在1963年由一個普林斯敦的數學教授 John Tukey 向甘迺迪解釋，他是總統的科學顧問。甘迺迪應該是有聽沒有到，一旁的 IBM工程師 Dick Garwin 也在想一樣的問題，回去後立刻叫程式員 John Cooley 寫 code. Cooley 催促 Tukey 發表，但 Tukey 沒有興趣，當時算法還不算門嚴謹的學科，普林斯敦的大教授認為那只是個簡單的觀察，別人可能早就發現了，不值得發表。Cooley 只好幫他寫，掛共同作者，這篇演算法史上最重要的論文之一就這樣在1965年發表了。
FFT 的故事很有趣，google 一下可以找到很多，YT 有不錯的影片解說。
我不解的是，多數給大學部學生的算法教科書不是沒提FFT，就是放到最後面，沒時間教。其實 FFT 的算法不難，比較吃力的部分是數學，用到虛數，但大二學生剛修完微積分或線性代數，反而比 CS 的研究生更記得那些東西，何況數學部分懂就懂了，而程式技巧也只是典型的 Divide and Conquer。我教算法時一定會插入 FFT，不管教科書有沒有，若非社區大學的轉學生，我覺得學生還頗能掌握，而且能適時拉回學生對數學的重視。建議教算法的老師不要跳過 FFT。
++++++
人工智慧概述
約翰·懷爾德·圖基的遺產
約翰·懷爾德·圖基（1915-2000）是一位美國數學家和統計學家，以創造“比特”（bit）和“軟體”（software）這兩個術語以及開創探索性數據分析而聞名。他是一位神童，主要在家接受教育，在麻薩諸塞州新貝德福德長大。他先在布朗大學獲得化學學位，後來在普林斯頓大學獲得數學博士學位。二戰期間及戰後，他的研究方向轉向統計學，並開發了革命性的數據分析方法，例如箱線圖和莖葉圖。
早年生活和教育
圖是根據1915年出生於麻薩諸塞州新貝德福德，他的父母都是教師，因此他從小就接受父母的家庭教育。
他三歲學會閱讀，很快就展現出數學和科學的天賦。
他曾就讀於布朗大學，並在那裡獲得了化學學士和碩士學位。
之後，他轉至普林斯頓大學，並於1939年獲得數學博士學位，此前他已將研究方向從化學轉向數學。
職業生涯及貢獻
二戰期間，他曾在火力控制研究辦公室工作，運用統計學解決實際問題。
戰後，他同時在普林斯頓大學和AT&T貝爾實驗室任職，35歲時成為普林斯頓大學的終身教授，並創立了該校的統計學系。
在貝爾實驗室工作期間，他創造了「比特」（bit）和「軟體」（software）這兩個術語。
他被譽為探索性數據分析（EDA）的先驅，該方法強調數據視覺化和探索，以發現模式並提出假設。
圖基開發了創新的資料視覺化工具，包括箱線圖和莖葉圖。
他因在頻譜分析和快速傅立葉變換演算法方面的工作，分別於1973年和1982年榮獲美國國家科學獎章和IEEE榮譽獎章。
晚年生活
圖基於1985年退休，但仍繼續從事研究工作。
他於2000年7月26日在美國新澤西州新不倫瑞克省去世，享年85歲。
- Author: Mark Jones Lorenzo.
- Subject: John W. Tukey, a highly influential American statistician, mathematician, and computer scientist.
- Key Contributions:
- Exploratory Data Analysis (EDA): An approach to data analysis Tukey equated with "detective work".
- Fast Fourier Transform (FFT): An algorithm that revolutionized digital signal processing.
- Data Visualization: Created innovative tools like the stem-and-leaf plot and the PRIM-9 interactive graphics system.
- Computing: Coined the terms "software," "hardware," and "bit".
- Statistical Techniques: Developed methods such as the jackknife, multiple comparisons, and robustness.
- Career: Spent decades as a professor at Princeton University and a researcher at AT&T's Bell Laboratories.
- Additional Topics: The book also covers his work on U.S. census analysis, election forecasting, health and environmental regulation, his collaborations (and intellectual disagreements) with contemporaries like Alfred Kinsey, and his intellectual friendship with physicist Richard Feynman.
Early life and education
- Born in New Bedford, Massachusetts, in 1915, Tukey was homeschooled by his parents, who were both teachers.
- He learned to read at age three and quickly developed a talent for mathematics and science.
- He attended Brown University, where he earned both his bachelor's and master's degrees in chemistry.
- He then moved to Princeton University, earning a Ph.D. in mathematics in 1939 after switching his focus from chemistry.
Career and contributions
- During World War II, he worked at the Fire Control Research Office, applying statistics to practical problems.
- After the war, he began a joint career at Princeton University and AT&T Bell Laboratories, becoming a full professor at Princeton at age 35 and founding the university's statistics department.
- He coined the terms "bit" and "software" while working at Bell Labs.
- He is credited with pioneering Exploratory Data Analysis (EDA), a methodology that emphasizes data visualization and exploration to find patterns and formulate hypotheses.
- Tukey developed innovative data visualization tools, including the box-and-whisker plot and the stem-and-leaf diagram.
- He was awarded the National Medal of Science in 1973 and the IEEE Medal of Honor in 1982 for his work on spectral analysis and the fast Fourier transform algorithm.
Later life
- Tukey retired in 1985 but continued to be active in his research.
- He passed away in New Brunswick, New Jersey, on July 26, 2000, at the age of 85.
Adventures of a Statistician: The Biography of John W. Tukey Paperback – August 22, 2018
by Mark Jones Lorenzo (Author)
Meet John W. Tukey, one of the most consequential statisticians and original thinkers of the twentieth century.*
Growing up one hundred years ago in New Bedford, Massachusetts, a large coastal town primarily known for its commercial fishing and textile industries, John Wilder Tukey quickly showed himself to be a child prodigy. The son of educated parents whose high school classmates voted them most likely to give birth to a genius, he learned to read on his own by three years of age, mastered using a hand-crack desk calculator to speed up arithmetical calculations shortly thereafter, and was poring through technical journals in the New Bedford Free Public Library by the time he was a teenager.
Homeschooled until being admitted to Brown University, Tukey majored in chemistry there--even as he spent countless hours in the university library compiling lists of statistical techniques on index cards, simply because he found them interesting and useful. With multiple degrees in hand, Tukey's next stop was Princeton University, where his interests shifted to mathematics. After earning a doctorate in topology, an especially abstract branch of mathematics, Princeton retained him as a lecturer. But with the United States poised to enter World War II, Tukey joined the Fire Control Research Office (FCRO), where he was exposed to a set of life-and-death problems that bore little resemblance to abstract mathematics: namely, calculating the trajectories of artillery and ballistics and the motions of rocket powder, working with stereoscopic height and range finders, and improving the Boeing B-29 Superfortress bomber. With the stakes never higher, a chance encounter during the war with a fellow polymath and unconventional thinker twenty years his senior set the course for the rest of Tukey's professional life--as well as changing the field of statistics forever.
In Adventures of a Statistician, author Mark Jones Lorenzo chronicles John Tukey’s life and times, from his decades spent at Princeton as a teacher and administrator and also at AT&T's Bell Laboratories as a scientific generalist; to his development of the fast Fourier transform (FFT) algorithm, which launched a revolution in digital signal processing; to his innovative ideas in displaying and summarizing data, such as with the intuitive stem-and-leaf plot and the interactive graphics of the PRIM-9 computer system; to his creation of exploratory data analysis, an approach to performing statistics he equated with "detective work"; to his intellectual war with sex researcher Alfred Kinsey over appropriate kinds of statistical sampling; to his productive yet sometimes strained relationships with fellow statisticians such as Ronald Fisher, George Box, and Erich Lehmann; to his enlightening friendship with the legendary physicist Richard Feynman; to his mentoring of dozens of doctoral students, many of whom went on to have highly successful careers in their own right; to his inventive use of language, having coined words like "bit"; to his development of sophisticated mathematical methods to detect underground nuclear explosions; to his groundbreaking work on the jackknife, multiple comparisons, robustness, and many other statistical techniques; and to his accomplishments in health and environmental regulation, U.S. census analysis, election forecasting, and public policy, among a host of other significant and impactful achievements.
Nearly a decade in the making, Adventures of a Statistician is more than just the complete biography of John W. Tukey, perhaps the most revolutionary applied statistician of the past century. It’s also a fascinating intellectual journey through the recent history of statistics as well.
* Please note: This item is a corrected reprint, released in August 2020, of Adventures of a Statistician.
統計學家的冒險：約翰·W·圖基傳記（平裝本）－2018年8月22日
作者：馬克瓊斯洛倫佐
認識約翰‧W‧圖基，他是二十世紀最具影響力的統計學家和獨創思想家之一。 *
一百年前，約翰·懷爾德·圖基在麻薩諸塞州新貝德福德長大。新貝德福德是一個沿海大鎮，以商業捕魚和紡織業而聞名。圖基從小就展現神童的才能。他的父母受過良好的教育，高中同學都認為他們最有可能生出一個天才。圖基三歲就能自學閱讀，不久後便熟練了使用手搖計算器來加快算術運算速度，十幾歲時就開始在新貝德福德公共圖書館裡研讀技術期刊。
圖基在家自學，直到被布朗大學錄取。他在那裡主修化學，儘管如此，他仍然花費無數時間在大學圖書館裡用索引卡整理統計技術清單，只因為他覺得這些技術既有趣又實用。在獲得多個學位後，圖基的下一站是普林斯頓大學，在那裡他的興趣轉向了數學。在獲得拓撲學博士學位後，普林斯頓大學聘請他擔任講師。拓樸學是數學中極為抽象的分支。但隨著美國即將捲入第二次世界大戰，圖基加入了火控研究辦公室（FCRO），在那裡他接觸到了一系列生死攸關的問題，這些問題與抽象數學幾乎毫無關聯：例如，計算火砲彈道和彈道學，模擬火箭火藥的運動，使用立體測高儀和測距儀，以及改進波音B-29堡壘轟炸機。在形勢空前嚴峻的戰爭期間，一次偶然的邂逅讓他結識了一位比他年長二十歲的博學之士，這位學者思維獨特，也為圖基的職業生涯定下了基線，並永遠地改變了統計學領域。
在《統計學家的冒險》一書中，作者馬克瓊斯洛倫佐詳細記錄了約翰圖基的生平：從他在普林斯頓大學擔任教師和行政人員的數十年，到他在AT&T貝爾實驗室擔任科學通才；從他開發的快速傅裡葉變換（FFT）演算法引發了數位訊號處理的革革命；到他在數據展示和匯總方面的創新理念，例如直觀的莖葉圖和PRIM-9計算機系統的交互式圖形；到他創立的探索性數據分析方法，他將這種統計方法比作“偵探工作”；再到他與性學研究者阿爾弗雷德·金賽就統計抽樣方法展開的學術辯論。本書的亮點在於他與羅納德·費舍爾、喬治·博克斯和埃里希·萊曼等統計學家之間富有成效卻又時而緊張的關係；在於他與傳奇物理學家理查德·費曼之間富有啟發性的友誼；在於他指導了數十位博士生，其中許多人後來在各自的領域取得了巨大的成功；在於他創造性地運用語言，創造了「比特」（bit）等詞彙；在於他開發了用於探測地下核爆炸的複雜數學方法；在於他在刀切法、多重比較、穩健性以及許多其他統計技術方面的開創性工作；在於他在健康和環境監管、美國人口普查分析、選舉預測和公共政策等領域取得的成就，以及其他眾多意義重大且影響深遠的成就。
歷時近十年完成的《統計學家的冒險》不僅僅是約翰·W·圖基——或許是上個世紀最具革命性的應用統計學家——的完整傳記，它也是引人入勝的統計學近代史探索之旅。
* 請注意：本書是《統計學家的冒險》的修正重印版，於 2020 年 8 月發行。
7
沒有留言:
張貼留言