通往名校的最後一塊拼圖—演算法！
近年來，越來越多人投入到研究所考試之中。資工所更是熱門的戰場。然而，要考上一家好的資工所並不容易。原因之一是因為台大、交大、成大、中央等名校已將演算法這一科納入考科中。在演算法這科中，除了本來資料結構的內容更伸入外，更需要數學的技巧來分析，甚至有更多的設計題型，需要以各種不同的技巧來解決。而演算法的範圍涵天蓋地，對於準備考試的同學來說很難以在有限時間內以有效率的方式將演算法準備得很周全，更難的是要培養對於各式問題的直覺與經驗。不少同學因為此科難以準備而放棄。但是，正因如此，演算法變成了一個門檻，只要能夠準備得宜，就可以輕易的領先競爭對手。
演算法通常出現在資工所考試科目中的"軟體設計"或"資料結構與演算法"一科中。在這一考科中，演算法和資料結構各佔50分。雖然演算法只佔50分，但是由於在準備上有較高的進入門檻，因此若能有系統的建立對演算法的概念以及必備知識，將是上榜與否的重要關鍵。
演算法的考題來源鮮少出自一本資料結構的課本，而是專門介紹演算法的教科書。一般來說，由Thomas H. Cormen等所著的"Introduction to Algorithms"是台大、交大、成大、中央等校的演算法必備教科書；另外，中央、暨南以及輔仁的部分考題會出自R.C.T. Lee所著的"Introduction to the Design and Analysis of Algorithms"。但是由於這兩本教科書的分量都相當的多，且討論的範圍也不盡相同。若同學利用這兩本書進行自修，不論在時間上或是對於內容的理解均付出相當大的力氣。因此，若要準備研究所考試，應同時由考題分析以及知識的建立雙管齊下，方能得到最大的效益。
演算法在本質上可以分成兩個部分，一個部分是設計，及如何設計出一個演算法來解決特定的問題；另一個部份則是分析，即分析演算法的特性、推導出演算法是否有效率、驗證是否正確以及在理論上的難度等。因此，這種情形也同樣的反應在考題上。
在演算法的考題題型中，可大略分成以下幾項：
1.計算題：
此處的考題是以複雜度計算或是遞迴關係的求算為主。因此在準備時必須熟悉各種複雜度的定義，以及計算的技巧。遞迴關係則主要是在於是否能妥善的利用類似像master theorem、recursion tree等演算法中特有的技巧來解決。當然，各種數學的技巧也勢必備的。
2.設計題：
這一類考題型式，首先事會給定時間複雜度和其限制，要求考生針對題目的要求來設計一個演算法。而這一類考題又分成兩種類型，一類是演算法中所謂的名題(例如：LCS、求closer pair、selection problem等)；另一類才是真正的設計題，通常是基本章節中或是有名問題的變形或再延伸。對於前者的準備方式，不外乎就是充分的認識演算法各相關章節中有名的問題，才能在考試中順利的作答。而對於後者，除了要將名題練熟之外，還必須熟悉演算法中相關的設計概念(如greedy、dynamic programming、prune and search、branch and bound等)，更需要一點點的聯想力，在考試時才可聯想及發揮。
3.證明題：
如同上述，演算法的分析也是很重要的一環，因此證明題也經常會出現。證明題主要分成兩種類型，一種類型是偏數學分析的證明，另一種則是證明某問題是NP-complete的證明。在第一類型中的證明題，會類似像離散數學中的證明題一般，給一個命題，要你證明其為真，或者是要你判斷是真是偽，並做證明或反證。此類的題目除了平常在數學方面的訓練以外，更要對題目所提及的演算法有非常充分的認識才可以在考場中正確的回答出來。而對於NP-complete的證明，最重要的是要了解其背後的理論基礎及其過程，進而將其記憶並推廣。
綜合以上，雖然演算法看似不可捉模，但是仍有清晰的脈絡可循。若能先熟知考試的題型及方向，在有組織的建立演算法的基本架構，必能融會貫通，在最短的時間餒打通任督二脈，答到強迫取分、輕鬆榮登各校金榜的目的。
留言列表
研究所各考科 (15)