在現代,人們所使用的軟件功能越來越豐富,也越來越強大。就像這幾年來開始火起來的人工智能,例如,前段時間穀歌的“AlphaGo”就依次打敗了韓國與中國最優秀的圍棋手,甚至最新的“AlphaGo·零”更以一百比零的成績打敗了“AlphaGo”。在這其中,像這樣的人工智能是怎麼運作的呢?這就要依靠程序的算法了。程序的算法是計算機科學的一門分支,主要研究設計算法的方法,算法有效性和算法運算效率的計算與證明。

計算機科學,或叫做“計算科學”、“計算機科學及工程”和“計算機科學與技術”,是一種應用科學,是系統性研究資訊與計算的理論基礎以及它們在電腦系統中如何實現與應用的實用技術的學科。計算機科學包含很多分支領域,主要分為四大類:計算理論,算法與數據結構,編程方法與程式語言,以及電腦組成與架構,而算法正屬於計算理論。

香港科技大學也有在工學院下設計算機科學與工程系,與土木及環境學系,機械及航空航天學系,化學及生物工程學系,工業工程及物流管理學系和電子計算機工程系組成了工學院。香港科學大學本身作為一間研究型大學,研究為學校的核心,通過教育來提升學生的知識水平,加強學生的創新和思維能力。工學院也以此基礎,通過對學生的教育及研究來創造世界級的革新與突破。作為工學院最熱門的學系之一,計算機科學及工程系致力於提供學生最優秀的教育。在2017年度QS排名中,香港科技大學的計算機科學及工程排名為世界第19位,大中華區第3位。而作為理論計算機科學的重要基礎,算法成爲了計算機科學及工程學生不可缺少的基礎知識。算法的設計及應用(COMP3711)正因此而作爲一門計算機科學必修專業課而開設。

算法的設計及應用這一門課主要教授多種算法的基礎,算法設計的基礎與其有效性驗證。課程包括四大部分:算法設計基礎、排序算法基礎、隨機算法基礎和圖論算法基礎。算法設計基礎將會講解主定理、分治法、動態規劃及貪心法這四種算法設計技巧以及相關的例子;排序算法基礎會介紹冒泡排序、選擇排序、插入排序、歸並排序和快速排序這五種常見的排序;隨機算法基礎將會教授隨機算法的理論、隨機函數及其應用;而圖論算法基礎將會教授廣度優先搜索、深度優先搜索的基礎和最短路問題、最小生成樹問題以及最大流最小割問題的各種算法。在實際生活中,我們無法看見算法,但是算法卻遍佈於我們所使用的各式各樣、位於平板電腦、計算機和手機上的各式程序與應用中,方便著我們的生活。

在其中,最常見並且最明顯的應用便是地圖應用了。像穀歌地圖這樣的引用可惜協助我們尋找去特定地點的最短路徑,而尋找最短路徑正是算法中的最短路問題。在穀歌地圖中,開發者使用了戴克斯特拉算法來尋找最短路徑。戴克斯特拉算法將一張地圖轉換成帶權重的邊和頂點的有向圖,通過對每一條邊權重的預判,從而實現了以最快的速度搜索到最短的路徑。另外一個例子便是我們畫圖時我們我們經常使用的填充工具。在畫圖時填滿一塊特定的區域實際上是一個最小生成樹問題。爲瞭解決這個問題,我們需要使用深度優先搜索的遞歸方法,通過檢查臨近的點是否可以填充來實現“填滿顔色“的效果。如果沒有使用這種方法,我們在使用填充工具時就會出現填充緩慢出現的問題。

算法無處不在,在我們的每天在使用的應用之中,無論是地圖還是搜索,我們處處會使用到算法。這門課作爲一門基礎課,為更好的軟件打好基礎。

參考資料

  1. 計算機科學
    https://zh.wikipedia.org/zh-hk/计算机科学
  2. 演算法
    https://zh.wikipedia.org/wiki/算法
  3. 香港科技大學工學院
    https://www.seng.ust.hk/web/eng/cat.php?catid=1
  4. 香港科技大學計算機科學及工程學系
    http://www.cse.ust.hk/admin/about/
  5. COMP3711課程筆記