字體：小 中 大 |
|
|
|
| 2008/11/07 22:26:30瀏覽1943｜回應4｜推薦38 | |
| 引用文章染上了『海角七號熱』症候群的大宗師
『海角七號』跟教育有什麼關係？道德教育嗎？說髒話的文化教育嗎？婚前性行為的健康教育嗎？沙灘都要BOT的社會發展教育嗎？ 這些都不是我的專長。 有多少人注意到了郵差阿嘉為何對送郵件這件事感到挫折？為何阿嘉第一天上班就需要去茂伯家報到？ 想起來，台灣的公職考試有個郵政特考，還很熱門呢！我沒考過，不知道到底考什麼。 說說看完『海角七號』後，我覺得跟自己最切身的教育問題是什麼，也提供所有想走高科技的人一個最基本的軟體演算法問題-最短路徑問題。 
當阿嘉與茂伯坐在板凳上分信件時，馬上讓我想到演算法中間解決圖中任意兩個頂點之間最短路徑的問題。 當茂伯把他心目中的路線一一報給阿嘉聽時，阿嘉一副不理睬的表情，我還真的對阿嘉產生很大的反感。但是，我馬上又幫阿嘉抱不平：一個搞音樂的人，很難有耐心去搞邏輯問題的。 怪不得，阿嘉送信會送不完，因為他的腦袋根本不適合去做郵差這份工作。阿嘉的繼父在衝動之下，表現出來的是一種無知，而且是濫用特權而侵害到居民的利益。在電影中，這個行為其實沒有被大探討。繼父代表在片中很討好，但是導演（或是編劇）其實並沒有將他完美化，或是偶像化。 回到這個每次面談軟體工程師時，我都會考的技術問題。 上圖中的每個點可以表示是社區中的住址，邊上的數字代表著每個住址的間距。演算法可以用來找到兩個城市之間的最短路徑。在送信這件事情中有兩個關鍵： 第一．在最短距離內送完（才能省油）。 第二．在最短時間內送完（才能早點下班）。 仔細去看上面這個圖，距離其實不是絕對的，而是有方向性的。而送信的地點也不是這麼單純的路徑，而是交錯不斷的街道，與其他如上、下坡，順向與逆向交通流量的考量，有時還得加上郵差自己想吃中飯，買飲料的『打混』站。 我考應試者的演算法，最基本的目的就是要找到從A到B到C再回到A的最低花費路徑。 而在這個簡單的提目中，我可以從應試者的反應中去了解他的溝通技巧，邏輯，與對於基本演算法的功力。若通過第一樣考驗，下一步就是考他寫程式的技巧。 這裡談到的可以回溯到數學上一個主要分支：圖論（graph theory） 圖論裡面是從『柯尼斯堡七橋問題』衍生出來的。（引述維基的內容） 『這個問題是基於一個現實生活中的事例：當時東普魯士柯尼斯堡（今日俄羅斯加里寧格勒）市區跨普列戈利亞河兩岸，河中心有兩個小島。小島與河的兩岸有七條橋連接。在所有橋都只能走一遍的前提下，如何才能把這個地方把所有的橋都走遍。』 萊昂哈德·歐拉（Leonhard Euler）在1736年圓滿地解決了這一問題，證明這種方法並不存在，也順帶解決了一筆畫問題。他在聖彼得堡科學院發表了圖論史上第一篇重要文獻。歐拉把實際的抽象問題簡化為平面上的點與線組合，每一座橋視為一條線，橋所連接的地區視為點。這樣若從某點出發後最後再回到這點，則這一點的線數必須是偶數。
歐拉最後給出任意一種河──橋圖能否全部走一次的判定法則。如果通奇數座橋的地方不止兩個，那麼滿足要求的路線便不存在了。如果只有兩個地方通奇數座橋，則可從其中任何一地出發找到所要求的路線。若沒有一個地方通奇數座橋，則從任何一地出發，所求的路線都能實現，他還說明了怎樣快速找到所要求的路線。』 在了解這個問題後，下一個問題就是所謂的『旅行推銷員問題』 旅行推銷員問題（Traveling Salesman Problem， 又稱為旅行商問題、TSP問題）是一個多局部最優的最優化問題：有n個城市，一個推銷員要從其中某一個城市出發，唯一走遍所有的城市，再回到他出發的城市，求最短的路線。 能解決最基本的『旅行推銷員問題』，之後才是開始真正的面試，從半導體物理，半導體元件等等問到超大型積體電路，與奈米電路設計，電路功能，功效等等真正的電機/電子工程系的真正問題。 很多人問我，大學要學什麼課，其實，若大一或大二的計算機概論沒有把這學好，一切都很難學的紮實，有興趣來面試，或是想送小孩來面試的朋友們，『海角七號』已經洩出最重要的一個題目了。 圖形取自 http://en.wikipedia.org/wiki/Seven_Bridges_of_K%C3%B6nigsberg http://www.cs.mcgill.ca/~cs251/OldCourses/1997/topic29/ http://en.wikipedia.org/wiki/Travelling_salesman_problem |
|
| ( 時事評論｜教育文化 ) |
