2023 年秋季修課心得

演算法設計與分析(ADA)

• 學分：3 學分
• 授課教師：蕭旭君
• 學期成績：A+

• 上課內容：

    這門課的上課內容相當豐富，前半學期主要介紹了一系列經典的演算法典範，包括分治法(divide and conquer)、動態規劃(dynamic programming)以及貪婪演算法(greedy)。進入後半學期，課程圍繞著三個主要主題展開：圖論演算法、均攤分析(amortized analysis)以及 NP 完備性(NP-completeness)。

    評分方式包括作業佔 35%、期中考佔 20%、期末考佔 25%，還有迷你手寫作業佔 10% 以及迷你程式作業佔 10%。作業共有四次，其中包含 12 題的程式題，使用 C++ 語言進行撰寫。值得一提的是，作業和期中考期望水準相當高，多數題目都來自競程選手的範疇，因此充滿了挑戰性。教授雖然宣稱最終成績會根據學校的標準來切等第線，實際上常常會因為整體表現不理想而對原始成績進行調分，再以學校的標準來確定等第線。

• 心得：

    在這學期中，我第一次深入學習了許多演算法的基本概念，這對我來說算是新的知識領域。雖然無法像雙號班的同學能在上課了解一些資訊史或是現在的純演算法實驗室在做什麼研究，但我在這門課中建立了堅實的基礎演算法能力。這樣的學習經驗讓我對工程師所需的基本演算法技能有了更深刻的認識。

系統程式設計(SP)

• 學分：3 學分
• 授課教師：鄭卜壬
• 學期成績：A+

• 上課內容：

    這門課主要探討 UNIX 系統上程式的運作、kernel 與程式之間的互動，以及作業系統在資源分配方面的角色。舉例來說，期初內容聚焦在 UNIX 系統上檔案讀寫(File I/O)的機制，例如 write() 這個 system call 的執行流程，從 file descriptor table、open file table、i-node table 一直到 kernel buffer cache，最終檢查緩衝區快取(buffer cache)是否存放所需資料，若無則可能進入 event queue 等待硬碟讀寫(disk I/O)的機會。在這個例子中，我們會學到系統維護了什麼資料結構，kernel 又會在什麼時候接管 CPU 等等。而後面的授課內容則會詳細的討論以下幾個章節：檔案讀寫(file I/O)、檔案系統(files and directories)、行程間通訊(inter-process communication)、行程控制(process control)、訊號(signal)以及執行緒(thread model)。在課堂中，特別強調程式設計師需要充分考慮的議題，如 race condition 和死結(deadlock)等。

    此課程的評分標準為程式作業佔 32%、手寫作業佔 8%、期中考和期末考各佔 30%。由於通常期中平均分較低，教授會在期末考中提高滿分為 130 分，最終成績不會進行調整，以學校的標準作為期末等第的評定基準。

• 心得：

    這門課的程式作業為我提供了豐富的學習機會，每個作業都深入涉及當前學習內容的核心概念，同時也要求製作簡單的報告。以下列舉各個作業涵蓋的主題：

  1. 第一次作業：學習了 file lock 及 I/O multiplexing 的重要性，並且認識到在 socket I/O 中可能會出現封包切割的問題 —— 儘管這個問題不該出現在 SP 這門課中──然而，我認為作為一個未來的程式設計師，尤其是系統相關的問題，這樣的問題更應該被程式設計師注意到。
  2. 第二次作業：練習了 fork() 和 exec() 相關函式的實作，並學會了兩種常見的行程間溝通(IPC)技巧，如 pipe() 及 mkfifo() 等，以解決 race condition 相關的問題。
  3. 第三次作業：探討了與訊號(signal)和 nonlocal jump 相關的 syscall，特別需要注意避免 deadlock 相關的問題。
  4. 第四次作業：練習了 multi-threading (pthread, POSIX-thread)相關的 user-level thread操作，進一步豐富了多執行緒操作的經驗。

    雖然在作業中相對較少涉及檔案系統相關的問題，但期考中對檔案系統(file system)、檔案與目錄權限等方面的題目也佔了不小的比重。整個學期的內容呈現了相互關聯性，特別是在深入探討 exec()、fork() 等 syscall 與 set-UID bit 的關係後，前後各章節的內容相互呼應。

    課程中最大的收穫來自於作業，至少熟悉了各種 syscall 的使用。同時，學到了一項實用的技能，即在使用不熟悉的函式或 syscall 時先查閱相關的說明網頁(manual page)，這給出了這些函式的使用方法清晰且全面的指引。這樣的學習過程不僅培養了對系統程式的深入理解，也培養了查找資源並解決問題的獨立能力。

自動機與形式語言

• 學分：3 學分
• 授課教師：林智仁
• 學期成績：A+

• 上課內容：

    這門課的課程內容皆在於建立電腦科學中對於「演算法」形式定義以及時間複雜度等等的定義。我們會考慮一些自動機並且找到可被這些自動機所辨識的語言，其中此處說的語言並不是指人類的自然語言，而是指一些字串所形成的集合，有時會被稱做形式語言。學期的前三分之二大概會探討的自動機有：

  1. 確定有限狀態自動機(deterministic finite automata, DFA)，可被此自動機辨識的語言為正規語言(regular language)，此種自動機類似數位電路設計相關課程會提及的有限狀態自動機(finite state machine)。這種自動機沒有任何的記憶功能，即不會有額外紀錄資訊的空間。
  2. 非確定有限狀態自動機(nondeterministic finite automata, NFA)，對於同一個符號（字元）可以有多種轉移的可能（包含沒有轉移），此種自動機與 DFA 等價。
  3. 下推自動機(pushdown automata, PDA)，類似 NFA 是一種非確定性自動機，只是有一個堆疊(stack)作為記憶體使用，可辨識上下文無關文法(context-free grammar, CFG)所生成的語言。
  4. 確定下推自動機(deterministic pushdown automata, DPDA)，類似 PDA 只是轉移函數變成確定轉移函數，即對於每一個讀入字元，都有一個可行的轉移狀態。然而 DPDA 與 PDA 不辨識同樣的語言。
  5. 圖靈機(Turine machine, TM)，類似 DFA 但是具有無限長度記憶體的機器，由於其轉移函數的形式定義，可以被圖靈機辨識以及可以被圖靈機接受(或說判定)的語言不完全相同，因此後面會探討可判定性(decidability)，而後面證明一個語言的不可判定性，則需仰賴一個在演算法設計與分析(ADA)也會學到的技巧──可歸約性(reducibility)──即把一個問題 P 歸約到另一個問題 Q，藉此來說 Q至少比 P「困難」，以此來說明一個語言的不可判定性。
  6. 非確定圖靈機(nondeterministic Turine machine, NTM)，轉移函數為非確定性的圖靈機。

    此外還會介紹其他圖靈機在其記憶體(tape)上有所放寬或限制的圖靈機，像是多帶圖靈機(multitape Turine machine), 線性有界自動機(linear bounded automata)等等。學期的最後三分之一則會介紹一些關於複雜度理論的問題，舉例來說，我們會介紹電腦科學界最著名的未解問題，即 TM 可在多項式時間內判定的語言與 NTM 可在多項式時間內判定的語言是否一樣，目前學界普遍認為這是不同的。

    這門課的評分方式為：六次作業共佔學期成績 25%，三次期考各佔學期成績 25%。依原始成績排序後，分配各個等第的比例使單、雙班的比例一致。

• 心得：

    我選擇在大二上修讀這門課，主要是因為我認為自己在系上修的課程相對較少，同時對於資訊領域的實力感到還不夠充實。面對這樣的情況，我傾向選擇了一門純理論且內容相對豐富的數學課程。課程的基本目標是建立對於「問題」、「演算法」以及「時間複雜度」等概念的嚴謹數學定義。我覺得這門課對我而言，提供了建立對演算法和電腦的抽象思考的機會。

    然而，我也要承認這門課的內容相對偏向純理論，對於不打算從事純演算法相關研究的人而言，可能並不是那麼直接有幫助。自動機理論等概念對大部分人來說，可能只需要了解一些基本概念就足夠應對實際問題。

機器學習(ML)

• 學分：3 學分
• 授課教師：林軒田
• 學期成績：A+

• 上課內容：

    這門課的課程內容基本上是按照約 10 年前或更早期的教學影片來教學。前半部份為《機器學習基石》，在這部份中會講解機器學習中最基礎的概念，像是為什麼機器學習可以做到只看一部分資料，卻可以在沒看過的資料也有不錯的表現，這就會牽涉到可一般化(generalization)的理論。而後面又會提到一些簡單的線性模型，如線性回歸(linear regression)以及邏輯迴歸(logistic regression)。前半學期的最後則是會提到如何對抗過度擬合(overfitting)，這種狀況通常是因為使用太強的模型而導致我們忽略雜訊(noise)造成的影響，我們會學到驗證(validation)以及正則化(regularization)兩種方法來降低我們的模型複雜度。

    而學期後半的內容則是《機器學習技法》的課程內容，主要就是在探討更多不同的經典機器學習模型，如從原本的線性分類器(linear perceptron)推廣到後面的支持向量機(support vector machine, SVM)，這比原本的線性分類器更強也更有韌性(robustness，指更不容易授雜訊干擾的模型)。此外也會提到利用混合(blending)以及裝袋(bagging)這兩個技巧，以及他們衍生出來的演算法，像是 adaBoost、decision tree 以及 random forest 等等著名的演算法。而學期的最後則會提到神經網路(neural network, NNet)類的演算法。

    這門課的成績是用六次作業以及期末報告來決定的。每次作業有 13 題(含加分題)，共 260 分。而期末報告有兩份，一份是常規報告而一份是加分報告，兩份報告的原始分數皆為 600 分。如果一個組別選擇同時做常規及加分報告，則最後期末報告的總分為 [ 0.9\cdot\mathrm{Regular}+0.3\cdot\mathrm{Bonus}, ] 而若一個組別選擇不做加分報告，則期末報告的總分即為常規報告的分數。而學期成績則是用所有作業成績以及期末報告的成績來決定，但不會依照學校的標準給等第。

• 心得：

    機器學習這門課讓我深入理解了機器學習中一些最基本且核心的概念，作業更是提供了豐富的數學推導練習，幫助我鞏固課堂學習。這門課成功地建立了我在機器學習理論方面的堅實基礎。

    然而，我也注意到每次作業中僅包含少量的程式實作，再加上前半學期介紹的模型過於簡單，導致實務應用方面的可用性相對有限。這使我對於課程在應用層面的教學效果感到一些不足。儘管如此，我認為對於完全沒有接觸過機器學習的新手來說，這門課仍然是一個很好的入門選擇。然而，對於已經具備一些機器學習基礎的人而言，課程的意義可能相對有限。

計算機概論

• 學分：3 學分
• 授課教師：莊永裕
• 學期成績：A+

• 上課內容：

    這門課的主要內容在讓我們了解一台電腦的架構以及如何讓電腦運作起來。一開始從底層的物理元件，逐漸地建構出一些元件如 CPU、記憶體，最後組成一台電腦。之後便會提到機器語言、組合語言，最後越來越高階，如虛擬機器(virtual machine)、高階語言、作業系統等等。基本上整門課使用 The Elements of Computing Systems: Building a Modern Computer from First Principles 作為參考書。

    這門課的評分方式為作業 50%、期中考 20%、期末報告 25%、課堂參與 5%。作業包含了五個程式作業以及一份手寫作業，其中程式作業有四次主要在寫參考書作者提供的硬體描述語言來模擬一些硬體的運作，另一份程式作業是要寫一些組合語言，而手寫作業則是在期中考前的複習考卷，期中考有一半會是與手寫作業類似的題目。期末報告教授提供了很多的選項，常見的選擇包含用 Python 或 C++ 撰寫一個組譯器(assembler)或是 VM translator，或是用課本提供的高階語言 Jack 來開發一個遊戲，然而報告內容不完全侷限在這些選擇裡，只要與課程內容相關即可。此外，期末報告是可以多人共同完成，最多可以到 5 人，但人數越多報告的內容就要更精緻，才能得到相應的分數。課堂參與則是教授的黑箱分數，並未公佈此項成績的算分方式。

• 心得：

    修習《計算機概論》讓我回顧了前半學期與之前修過的《數位系統與實驗》的內容，有些部分有一定的重疊。而到了課程的後半段，特別是在期中考前後，我接觸到了一些對我來說新的內容。我深入了解了如何使用基礎的數位元件構建電腦的架構，並更深入了解了電腦的運作原理，例如資料路徑(data path)等方面。

    在整個學期中，我幾乎沒有參加課堂，因此對於虛擬機器(virtual machine)的部分沒有太多的了解。然而，其他的內容，如機器語言、組合語言、Jack language，以及 Jack OS 等，都是我在複習期中考或是期末報告中深入練習的內容。特別是 Jack language 是我第一次接觸基於物件的語言，儘管其功能不如真正的物件導向語言那麼豐富，我仍然從中學到了很多。

    最後，我要特別感謝期末願意和我一起合作做期末報告的同學陳璿修。謝謝他的協助，我才得以在期末過得較輕鬆一點。這門課也讓我更深刻地理解了程式設計師的一個原則：只要程式能正常運作，就不要輕易修改它──即使你對其內部運作方式並不了解。

大學國文：文學鑑賞與寫作（一）

• 學分：3 學分
• 授課教師：沈凡玉
• 學期成績：A

• 上課內容：

    這門國文課的上課內容分為兩個主要部分，前半學期探討漢樂府，後半學期則包含古詩以及魏晉詩歌。課程的評量方式包括兩份回家作業，以及學期末的應用書信文作業（課堂中完成）。此外，期中考以及期末考將佔據 25% 的學期成績。值得注意的是，課堂表現也佔 10% 的學期成績，其中包括出席率以及教授可能進行的黑箱分數調整。

    第一份回家作業要求學生在台大三週（或台大 $x$ 年）後，撰寫自己在校的體驗以及期望，這份作業佔學期成績的 10%。第二份作文要求學生從一部上課時看的電影選擇一個相關的題目，撰寫一篇論說文，這佔學期成績的 20%。最後的應用書信文作業涉及寫作實務，佔學期成績的 10%。此外期中期末考都是申論題，我們需要清楚且有根據的分析一些上課提到過的文本。

• 心得：

    一開始修這門國文課，我對文學並沒有太大的興趣，特別是在沒有足夠社會歷練的情況下閱讀古詩，難以產生深刻的感觸。因此，我覺得我在這門課的學習收穫相對有限。一開始的幾堂課，我還嘗試聽一下教授在講些什麼，但學期過半後，我偶爾才會抬頭聽一下教授的講解，有點感到可惜。

代數一

• 學分：5 學分
• 授課教師：謝銘倫
• 學期成績：A

• 上課內容：

    這門課的主旨為使學生熟悉一些基本的代數工具，主要會涵蓋以下主題：群論(group theory)、群作用(group action)、群表現理論(group representation)、環論(ring theory)、模(module, especially module over PIDs)、體論(field theory)、Galois理論等等。而這門課的算分方式為作業 30%、期中考 35%、期末考 35%，最後的等第會有滿大幅度的調分。

• 心得：

    《代數》這門課讓我深入學習了許多未來在純數學研究中將會非常有用的代數工具，尤其是學期後半段的核心內容 —— Galois 理論，這在數論中有著廣泛的應用。然而，代數的理論讓我開始感受到其抽象性和複雜性，這導致在學期的後半段，我感到學習的進度與課堂內容有點脫節，作業也變得非常具挑戰性。

    這學期的學習經驗讓我反思到，或許我需要更專注於在資訊領域的進步。我開始認識到，必須思考未來的發展方向，而不能再僅僅基於興趣而選擇修課。儘管這門課讓我學到很多，但我也感到了一些學習上的無力感，或許我對數學的熱愛並不如以前了。

健康體適能

• 學分：1 學分
• 授課教師：林威名
• 學期成績：A+

• 上課內容：

    這門課的設計與高中體育課的形式相似，每幾周會有一個特定主題，包括：課程介紹與認識環境、熱身動作與跑步動作、校園大猜謎、AED 與 CPR 急救訓練、河濱腳踏車、籃球，以及重量訓練等等主題。而課程評分方式為：出席 30%、上課參與度 20%，而期末報告佔 50%。

• 心得：

    理論上，這門課應該是在大一時與同屆同學一起修習，但由於大一時我選擇修「分析」，所以沒有參加健康體適能課程。幸運的是，這學期成功加簽這門早八的課程。整體而言，這是一門相對輕鬆的課程（早八的時間除外），活動內容豐富，能在學習健康知識的同時參與不同類型的運動，感覺輕鬆又有趣。

• Previous
  自動機與形式語言筆記
• Next
  2024 年春季課程心得