2018/05/21

演算法的描述法

  因為應用環境以及需求的不同,演算法的描述方式有著各種不同的方法,並無一統一之標準存在。除了本書使用的流程圖之外,比較常見的還有下列的數種:

一、自然語言描述

直接用自然語言一步一步的描述解題的步驟。這種描述法常見於各種說明文件以及操作手冊中,有時會輔以說明性的圖片。但是,運用在描述一個演算法時,最好加入下列的考量,才能清楚明確並具有較大的彈性:

  1. 在整個步驟說明之前方加上二個獨立的段落,分別說明給予(或已知,或輸入)的資料(及條件),以及最後要得到的結果(或輸出);
  2. 將各步驟之說明獨立成段落,各段落給予適當之編號,以方便流程之敘述與參照。

  這個方法的最大優點是幾乎沒有任何的技術需求,任何人都可以馬上上手。但是它有如下的幾個問題,使用時必須設法加以規避或處理:

  1. 自然語言的多義性,往往造成不同解讀者有不同想法;
  2. 句中所使用的代名詞所確切指稱的對象往往難以精確掌握;
  3. 難以全面掌握,有些流程可能會漏掉而未加以描述,造成整體的執行邏輯不完整;
  4. 有些結構(如遞迴法)不易用此方法來描述。

二、虛擬程式碼

和電腦語言相較,自然語言的邏輯架構顯得複雜而鬆散。為了補救此一問題,虛擬程式碼的作法是在整體架構上採用程式語言的架構,嚴格限制為只有循序、分歧、以及重複三種,而在此架構中的執行動作或是判斷條件則仍是以自然語言進行。
  基本上,只要花一點時間理解前述所謂的程式語言三種架構,就可以不至於太困難的上手。但這裡開始有一些標準化的要求出現。例如,所謂「程式語言」,到底在演算法的描述中要不要選定一種程式語言的「語法」或「表示法」加以遵循?早期最常見到的是採用Algol或是Pascal在流程控制上的語法。當然,不同的語言在先天上便有其限制,因此,也有些作者便揉入其他的語法結構自行設計類似的語法,或是語言。
  前述難以全面掌握,有些流程可能會漏掉而未加以描述,造成整體的執行邏輯不完整的問題並無法因加入程式語言的架構而解決。

三、程式語言的程式碼

隨著電腦運算能力以及程式語言教育的普及,許多作者開始直接以選定的語言來呈現各種資料結構和演算法的介紹。或許這種作法的最大好處是縮短設計、實作、展示的週期,也讓學習者直接有程式碼可抄,但它的問題並不少,這本書的序言中已談了不少,在此不再贅述了。

相關章節:

書名:《秒懂資料結構》1.3節 本書表達方法說明
作者:施保旭
出版:五南圖書出版有限公司
ISBN:978-957-11-8458-6
購買:博客來專頁

2018/02/02

第一本完全沒有程式碼的資料結構讀本:《秒懂資料結構》誕生

真的,「程式設計」該分成「程式語言編程」與「資料結構暨演算法設計」兩大塊。前者需要對於使用的程式語言具有相當的熟練度,而後者則需要解析問題與運用資料結構的能力。如果你對程式語言有畏懼感或是純粹不熟悉,讀這本書可以讓你燃起信心:「程式設計」不是「資」字輩系所獨享的菜;「資」字輩同學更可以跳脫特定語言的束縛。
2018 修訂
目前版次:第一版第二刷

我對於國內資訊相關的書籍一直有兩點抱怨:

  1. 介紹工具的書總是充斥著一大堆畫面截圖,介紹理論性的書則是充斥著延綿多頁的程式碼。所謂「充斥」,有的佔了將近三分之一至一半的總篇幅。除了佔版面有灌水之嫌外,在內文中對它們的討論實在是不成比例。介紹工具的書暫且不說,介紹理論的書籍中對這些程式碼幾乎談都不談,只是印在那兒,要看的人自己去看。根據這幾年的經驗,只要接觸程式碼,同學大半哀鴻遍野,真的很好奇這些程式碼到底有多少人去讀一讀它?上課怎麼教?可是,篇幅決定書價啊?
  2. 喜歡附一片光碟。不管收錄的是第幾版,大部分書所附的軟體其實在出版當下便已屬舊版,必須另行到軟體相關網站下載,光碟完全無用。至於書中的程式碼或範例,何不放在網路上讓有需要者去下載就好呢?何必附上這麼一片增加製作成本、提高書價呢?許多電腦不安裝光碟機已漸成趨勢了,有再附光碟的必要嗎?

說歸說,過去一年,我很努力的寫了一本「完全沒有程式碼的資料結構讀本」,完全擺脫了前述惡習。書最近上市了。以下是這本書的基本資料:

書名:《秒懂資料結構》
作者:施保旭
出版:五南圖書出版有限公司
ISBN:978-957-11-8458-6
購買:博客來專頁

書的序言如下:

  對於以資訊為核心的理工系所而言,「資料結構」是核心課程,是許多專業課程的基礎;對於以資訊為應用或工具的整合性系所而言,「資料結構」則是將工具發揮至極致,甚至能拉出與其他競爭者差距的必修課程;在就業考試或國考中,只要和資訊沾上邊,即使沒有考科叫「資料結構」,只要考「計算機概論」或是「電腦概論」,資料結構實際便在其中扮演很重要的角色。
  以前念書時,教授很喜歡搞數學,到了期末課本只上了半本。為了升學,我搜集了一堆課本,從頭到尾努力的啃過,在這過程中,圖解(包括演算法的流程圖以及測試案例的分解動作圖)成了最大幫手,克服了近乎自學的困境。到了職場,歷經技術研發、產品開發、系統整合、專案管理,到今日以誤人子弟為業,逐漸體驗到唯有真正理解過的才能帶著走。教了多年的「資料結構」,每年換一本課本,總不合意。今年暑假,在聖嬰現象的溽暑中,終於下定決心自己寫一本,將多年來累積的筆記與教學講義加以文字化。市面上「資料結構」的產品已多如過江之鯽,為什麼還要再來寫一本?為了思考其存在價值,我決定這本書的特色是:

  • 不貪多、不求快:我們寧可將時間、篇幅花在核心議題的觀念介紹,以及用不同的角度以生活化的話題來做比擬,連繫生活經驗,目的是讓讀者能確切的掌握這些觀念,甚至在必要時,可以用他自己的語言重述這些觀念。
  • 不被任何程式語言所綁架:資料結構的多寡以及支援資料結構實作的強弱,本就是不同程式語言演化時的重點。因此,當一本書採用特定一種程式語言來介紹資料結構的主題時,其內容便被該語言所綁架,該語言未支援的無法討論,能討論的在其他語言又未必和書上所說的相同。用電腦程式來解釋資料結構,又往往將資料結構的問題,轉變成了程式設計的問題。即使在實務上,演算法的設計者與程式的寫作者往往是不同人。實務如此,學習時又何必要求學習者必須二項功力同時兼備?「設計」與「製作」的分開,往往是加速進步的一個關鍵。因此,我們捨棄用電腦語言來做例子的作法,而將重點放在觀念上。觀念掌握了,如何寫成程式是程式設計功力的問題,而程式設計的功力高低,不該成為學習資料結構的入門門檻。
  • 不限以資工/資科的專業生為想像讀者:太多書雖未明言,實際均以資工/資科背景的學習者為假想讀者,因此,對於其他在程式設計上受訓有限的人而言,讀起來便是一件苦差事。甚至,許多學習者修習一門課並不是因為他要以此作為進修或職場工作目標,而只是因為在整體課程設計中,它是核心課程,同學必須修習,否則在團隊合作中將與另一項專長的人無法溝通。此時,他們需要的是觀念的理解,而非程式寫作。在整合性的科系越來越多時,面臨此困境的學生也越來越多。事實上,這些年來,由於對客製化、介面調適化,以及功能延伸性的重視,越來越多的軟體提供了它自己的「描述語言」(Script Language),使用者可以使用這些語言把原來的軟體當作平台,而進行二次開發,許多二次開發人員均不是資工/資科背景。我們希望達到的境界是,資工/資科背景的讀者可以知其然亦知所以然,其他讀者則可以掌握資料結構的精神與設計技巧。總之,我們假設的讀者是,「學習上或是工作上,需要寫程式或是需要與寫程式的人共事者」。
  • 盡量延後術語的定義:任何一門發展已久的學問常常面臨的一個問題是「專業術語」相當的多。此現象的主要原因是早期有些觀念是在不同領域中發展,後來才逐步匯流,而各家的術語依然殘留,甚至有一義多詞的情形。基本上,對於術語的定義,我們將盡量推遲,需要用到時才加以定義,甚至直接以案例說明該術語的意涵,以免徒增困擾。
  • 仔細切割材料,縮小各章的規模,同時使其定位更加明確。有些較具技術性或數學推演的課題,則把它們放到習題中,然後於習題參考解答中去詳析它。這樣設計的目的很簡單:減少蔓藤效應。學習理論曾指出,一項學習的開始和結束前的一小段時間學習效果最好,我們的設計便是要製造最多的「開始」和「結束」,也避免因學習單元過長引起的學習焦慮感。
  這是一本學習、實證、與教學之後的反芻之作,希望能獲得期待中的效用,讓喜歡或不喜歡「資料結構」的學習者均能接受。期待各方的指正。

其他相關連結:

2017/09/19

讀韓愈〈應科目時與人書〉


  為了謀得一官半職,韓愈可是費煞苦心的。幾封求達官貴人提拔的書信都是〈與XX書〉,而這封則只是「與『人』書」,也就是抄送各家可能幫得上忙的所有人士之用,天曉得求了多少人?所以,一試再試猶得不到賞識的青年人也不必太灰心,偉大的韓愈花的心力可比我們大多了。

2017/09/12

讀韓愈〈送孟東野序〉


  牛頓運動定律說,如果沒有外力介入,則物體靜者恆靜,動者將永遠保持其原有之速度。老子所謂『治國如烹小鮮』,也是要執政者少出餿主意攪亂人民的生活。韓愈從同一命題的另一個角度來看,今天既然有人會有所出聲,必然在某些方面有所不平。

2017/09/06

讀韓愈〈送李愿歸盤谷序〉


  鄉居無憂時,最好的情境是『起居無時,惟適之安。』渾渾噩噩,睡到自然醒。但這有一個先決條件必須言明:衣食無憂!鄉居生活並不如古人在文章中所歌頌的那麼美好。看天吃飯,在許多季節裡,生活汲汲遑遑的程度比都市人有過之而無不及。『與其有樂於身,孰若無憂於心』,心中無憂才是真正的解脫,只是,古人的隱居多是在仕途不得已下之所為,是自我安慰?還是對外自我解嘲?

2017/08/30

讀韓愈《送董邵南序》


  董邵南到中央謀官不成,只好想到地方藩鎮的勢力範圍去試試,這是人之常情,『吾待善賈者也。』韓愈自己其實也是這麼幹的。
  本文先是稱讚董邵南的才能,想必在地方上可以找到賞識之士,勉勵其加油。可是又話鋒一轉,不知當地風俗有沒有因為主政者而有所變化,你期待中的當地人情世故搞不好已和你想像不同哦!你還是小心些。感覺上這盆冷水潑得夠嗆。