资讯科学基础-国立北斗家商.docVIP

資訊科學基礎修課有感 資料處理科 張銘棋 一、寫在前面 在剛考上雲科大的資管所，身為新鮮人的喜悅尚未消失時，就有學長提到下學期的「資訊科學導論」是比較生澀難懂的一門課程，要我們多加「小心」，其中含意不言可喻，心中不免擔心了起來…，與其說難，倒不如說是不確定感吧，已經離開校園六年了，再來讀這些理論科學的東西，會有何結果呢？ 首先自己必須忘掉年齡及目前的工作職位，才不會有學習的藉口，也才不會有本位主義，畢竟我們學習的主要目的，是學習以前沒有學過的理論及觀念，騰出內心空間則收穫可期。 調整工作時間儘量準時到校上課。我個人覺得上課是最節省時間的方法，也是吸收老師精華最有效的方式。也許有時會抽不出時間預習，但是會發覺自己得花更多時間去了解功課。我個人認為工作很重要，但卻是可安排的，而學習機會難再得，因此取捨之間必須慎重。 上課跟上同學學習的腳步，大家在課前分組預習，交互討論分享自己的見解（華山論劍？），互相勉勵、互相幫助。以減輕課程負擔，一方面達到老師的要求，一方面也是要提昇學習的進度，因為自己不是資訊、資工本科系出身，所以要在自學的過程當中，不斷與其他同學請教與討論，以瞭解書本上的定理、定義。 在上這門課之前一直覺得是很的東西難以理解但是經過了這一學期的課雖不敢說但是至少開啟了一扇讓我能更繼續自我學習下去的門對有了初步的了解 二、資訊的存在與傳遞 清晨騎著腳踏車享受清晨的陽光，舒服的迎接美好的一天，龍潭路上芒果樹兩、三隻的鳥兒的吱吱叫聲、同學互相寒喧問早，也有停在路旁用手機講話的人、用Notebook處理工作事務的上班族等，光光一段不到五分鐘的車程，就讓我發現許多不同的溝通方式，也說明了不同的溝通方式，也能產生相同的資訊傳遞，只是不同的種族表達的方式不同而已。例如：光「我愛你」三個字，在台灣地區就可能有國語、台語、客家語、山地語四種不同的語言，但是表達的意思卻是相同的。但隨著網際網路的興起，及使用手機族群的激增，這些溝通工具的出現，無疑是為了使「資訊」傳遞更為方便；電話、呼叫器、Email、手機，不但為我們帶來資訊傳遞的方便性，而且能夠正確快速的表達你所要表達給對方的資訊及想法。 由此可知，資訊的存在與傳承以及資訊的表現方式，各有不同的方法以及媒介，另一方面來說，許多資訊的根本的本質只是一個形體、一段音符、一種頻率、一句話甚至是一個表情都可以是資訊，資訊是無所不在的，只看使用資訊的人想不想去取得資訊，以及取得資訊的成本是否符合成本效益，由於取得資訊並不見得可以百分之百正確，而問題本身的Entropy也不見得固定，因此許多問題並不是容易解決的（整個世界充滿著很多P、NP、NPC問題，如果我們可以解決最難的NPC問題，那麼就會產生像骨牌效應一樣，所有NP的問題就會解決。）。 演算法為在資訊科學中解決某一問題的方法，它包含了完整性、機械性與可決定性三項要素。在現實生活中，電腦處理的能力受限於記憶體大小與中央處理器速度等等，導致演算法本身的資料結構對於其執行效率有很大的影響；因此才導致同一問題會有許多種解決方式如：貪婪演算法與動態規劃方式，其無非是要提升其效率與計算準確率。 在分析演算法中，主要以時間複雜度與空間複雜度兩者為標的。以演算法中三大基本指令，序列性(equence)、重覆性(teration)、遞迴性(ecursive)為中心，分析每一步驟所須的處理時間與空間，分析演算法的優劣。 透過演算法的分析，我們可以得知某些演算法的運算時間會隨著輸入的參數呈現指數成長，稱指數問題，如：河內塔；另一部份則呈多項式成長。多項式問題是一件較好解決的問題，相反的指數問題是資訊界中很棘手的問題，科學家無不希望能透過多項式的處理時間而解決指數問題，類似的問題在資訊科學界中一直是個很有趣的問題，也才有N與NP問題及一堆解決相關議題的想法 貪婪策略（Greedy Method）常用來解決最佳化問題（Optimization Problem）。貪婪法是最直接的解法，每次的決策都是朝向目前“最好”的方向前進，而且不回頭。可稱作是由上至下(op-Down)方法。在最小擴張樹inimum Spanning Trees）問題中的Kruskal’s演算法與rim’s演算法即是一個很典型的貪婪演算法。此外應用貪婪演算法精神的例子不勝舉，諸如：最短路徑hortest Paths）、背包問題napsack Problem）與排程問題cheduling）皆是。舉例來說，某一個銀行出納櫃檯要服務n個顧客，銀行的目標是希望顧客在櫃檯等待的平均時間要最少。解決之道是每次都從尚未服務的顧客中，選擇需要服務時間最短的顧客來服務，如此就可達到預期目標。像這樣每次都選擇最小服務時間的策略就是一種貪婪策略，但是除此之外，為顧及服務品質，也不能讓先來的顧客等太久—即使他必須佔用較多的處裡時間