[文化脈絡中的數學] 期末報告＠Morris' Blog

2013-12-02 09:19:52| 人氣2,678| 回應0 | 上一篇 | 下一篇

[文化脈絡中的數學] 期末報告

推薦 0 收藏 0 轉貼0 訂閱站台

數學與計算機

100502205 資工三B 楊翔雲

　　課堂中講到計算機的歷史，以及 Ada 的相關事蹟，先不論計算機方面的運作，Grace Hopper 曾提出數形變換，數形變換在 ACM-ICPC 競賽上算是一門學問，很多演算法的思路藉由數形變換更能展現出其性質，舉個例子來說「最大平均值問題」查找區間長度大於某個定值時，可以在區間獲得的最大平均值為何，就以數學論數學得到 max⁡((sum[j]-sum[i])/(j-i))when j>i+L 在這裡似乎看不到什麼關連性，但是表示在圖上，卻很明顯地察覺到需要找到最大斜率的切線，藉此便可得到更高效的算法(在此並不想細部描述這其中維護演算法的特性所在)。

　　說起計算機效率，一開始計算機從最常見的加減運算開始，硬體只由數個最簡單的邏輯閘構成，而數學領域的無理數就非常難進入計算機領域，以現在計算機的硬體架構終究無法百分之百保留無理數的存在，通常也只會保留一定精準度於電腦中。例如計算開根號，也許學過數學的人會問程式不也會開根號？根據國高中所學的數學，會談論到中國直式開方法或者是牛頓迭代開根號，更進一步學習到計算機領域的人會覺得二分搜尋也能做開根號，但設計計算機模型的人，真的使用這種演算法進行運作？答案是否定的，由於電腦保留的精度有一定限制，因此各種外星人公式接踵而來，沒人能仔細說明為什麼，但算出來的答案卻是非常精確，這些程式設計師常遺留下各種禍害給數學家們證明和研究。

　　計算模型有好有壞，哪個越簡單可以得到解答，咱們的電腦就用哪個，簡單方法並非指的是單純的直觀做法，電腦與人最大的差別在於善於計算，利用善於計算的特性，來突破繁瑣的推導，例如求平面曲線的極值，從簡單的二分搜尋三分搜尋到模擬退火算法，猜測搭配計算比起推導原先公式來得更加快速。

　　細說計算機最大硬傷－精度取捨，前文曾經描述過一小部分，接著說明為什麼造成了精度上的處理問題，由於為了搭配電路操作，計算機從十進制調整為二進制計算，即使是能在十進制表示的數字跳到二進制也會變得是無窮循環小數，任兩個不同進制轉換間常會發生這種問題，舉個例子來說十進制的 0.3 在二進制為 0.0011，所以程式設計師對於問題的數據處理，都希望盡可能使用可靠數據做操作(如整數計算或者其他特殊表達式)，直到逼不得以時才使用失去精確值的方式計算。雖然現在的程式語言普遍開始支持高精度計算，但是記憶體的開銷卻是好幾倍，計算拖得越久，記憶體就占據越大，直到整台電腦的記憶體用盡，學過更高深數學的人，變會開始學到誤差修正的方程式來補足精度取捨的問題。

　　從電腦遊戲看數學，電腦遊戲中的影像處理、幾何判定都相當地巧妙，在計算機領域也是相當一門學問。舉幾個簡單的例子：如何判定兩個線段相交？以高中所學的應用下去，易想得到倒不如先算兩個線相交，再查看交點是否在線段上。但是本文曾說明了精準度問題，兩條方程式求解很難避免解不會有浮點數存在，實際上是有很多判斷方式可以只藉由加減乘完成，最簡單的方式為套用外積計算得到正負號之間的關係。

　　再舉個簡單例子，射擊遊戲來說，如何判斷射擊點是否在一個簡單多邊形內部，藉此觸發擊倒敵人的效果？根據我們所學的數學技巧，還真想不到怎麼判斷這個看似簡單的問題，那把問題在縮小一點來看，如何判斷射擊點在一個三角形內部？相信很多人開始提了一些思路出來，最常見的方法從射擊點拉到三個頂點得到三個三角形面積總合會等於原先三角形面積，這時候又產生了如何計算三角形面積的處理問題，千千萬萬別用海龍公式，那邪惡的開根號電腦可負荷不了，的確「外積」又來幫助你解決問題了。回到簡單多邊形內部的判定，電腦實際又是採用什麼方式判斷呢？有興趣的人可以上網搜尋「射線法」。

　　寫程式並非單純的程式架構明白就能操作，數學無往不在，數學底子好的人學起程式相當容易上手，然而現在程式慢慢走向資料庫時代，想要什麼計算從資料庫函數去詢問，反而缺少了去研究它如何運作的數學奧妙，去看看當初設計函數的原理，便會明白有多少外星人存在這個世界，《一個sqrt函數引發的血案》網路文章簡單說明了這場外星人的入侵，設計者真的去做了開根號的動作了嗎？也許 1/sqrt(n) 更好計算，那個神祕猜測常數又從哪裡生出來的呢？卻無法查證設計者存在與否，這個神祕事件就這麼展開了。

　　倘若計算機沒了數學支持，相信現在的計算機是相當無趣的一個笨重機器。但是這並不表示現代計算機相當聰明，學過計算機的人都必須要明白，電腦其實相當地笨，它一點也不厲害，只是算的比較快，紀錄比較多條規則而已。別忘記能教電腦如何運作的，仍是工程師們的嘔心瀝血。

補充說明：

　　演算法並不是全部都是最佳化的解決方案，而數學理論也並非單純的有解和無解。前者存在近似演算法、隨機演算法，這些藉由一般經驗法則得到的猜測模型，我想我並不明白賽局理論，但很明顯地不是最佳化的策略，而要怎麼稱呼這個模型採用的演算法呢？為什麼講到數學理論並非單純有解和無解呢？也是有數學家提出了有時有解、有時無解的計算公式，根據一定機率分配這兩種解答，如何進行快速的大整數因數分解？Miller-Rabin Algorithm & Pollard's ρ Algorithm 提供了一種解決方法，至於有多快仍無法考證，但至少比按照一般步驟做好多了。

　　在仔細思考最常見的生活問題，去彩卷行常有人使用電腦選號購票，這代表了什麼問題？電腦選號如何決定亂數？亂數不也是數學公式，那必然有循環存在，因此也會有人不相信電腦選號，也就是說明為什麼公開中獎號碼時，總是要用彩球滾筒依序得到中獎號碼，如果規律被找到，很有可能推出下一次全部的中獎號碼，相信全部買彩票的人不願意樂見有能者猜出下一次號碼。

　　遊戲常有強化裝備的功能，當我們夠了解數學亂數於電腦計算時，那平均期望值變可以讓你決策大概第幾次能夠成功。如果這個亂數寫在顧客端的程式中，很明顯地可以調整亂數種子，使得每次都成功，當然遊戲公司也沒有那麼笨，扯到金錢肯定斤斤計較，當然會藉由網路去得到伺服器分配的亂數。

　　有時並不是他們運氣比較好，而是他們在環境中懵懵懂懂地了解了某些數學模型的模式。