資料庫系統概論 – 交大修課心得

computer

課程資料

資料庫系統概論

開課:梁婷老師

修課年度:100資工系

這學期因為 project 在期末考前一個月就要交了,所以課程也變更了一下順序。

期中考範圍:

  • Databases and Database Management Systems - 資料庫系統簡介,包含其和傳統儲存方式相比的優點
  • ER and EER Model - 使用圖像方式協助設計資料模型
  • Relational Model
  • Relation Schema Design and Functional Dependencies - 怎樣的資料表格設計才是好的設計?
  • Relational Design Algorithms and Further Dependencies

上半學期主要教我們如何將想儲存的資料,設計成適當的格式以儲存於資料庫之中。好讓我們可以開始設計專題的資料庫。後期就比較注重於資料庫系統背後的原理與架構了。

期末考範圍:

  • SQL - 一種標準化存取資料庫的語言
  • Relational Algebra - 關聯式資料庫數學理論
  • Disk File
  • File Structure - 資料庫系統檔案儲存的實做方式
  • Transactions
  • Concurrency
  • Recovery - 資料庫系統如何從當機中復原,保證資料狀態的正確性?
  • Query Optimization

使用的課本是《Database System: Models, Languages, Design, and Application Programming》,美國版書名是《Fundamentals of Database Systems》。選擇此書的原因是因為,老師覺得這本比起《Database System Concepts》容易理解。個人也稍微看過《DSC》那本,我也覺得《DSMLDAP》是比較好理解的。

不過由於老師上課投影片結合多家書籍內容,而其中許多採用的定義其實跟課本不太一樣。像是 primary index, cluster index 的定義等等,都與所使用教科書不同,需多加注意。而像是 extendible hashinglinear hashing 的操作,也和課本細節有些微不同, 考試可能會出現。

上課方式

用投影片教學。老師曾說每個讀資工系的人都有個夢想是創造自己的程式語言。她也曾想過。老師很希望有人問她問題,害羞的話寄電子郵件也無妨。

評分方式

評分如下:

  • 小考成績 15%
  • 期中考成績 30%
  • 期末考成績 30%
  • project 35% (proposal 20% demo 80%)

總分 110 分,所以就沒有調分了,最後平均約 72.5,大概有 16 的同學 90 以上。

小考方面總共有 7 次,有時會事先通知要小考,有時不會。7 次中,取三次高分採記。由於似乎也剛好有三次小考是有交的就直接算 100 分,所以算是點名性質,也因此不會另外每次點名。

小考可以 open book,也可和同學討論。期中期末都是 close book,這點跟去年不太一樣。

Project 的部份是1~2個人一組,以網頁界面實做一個資料庫應用程式。像是訂書系統、選課系統等等。期目自訂,一開始要先交一個 proposal,設計資料庫 schema 等等。接著再去 demo,並交一份介紹投影片。demo 感覺只要沒有什麼 bug,分數就不錯。排版應該不太佔分。

程式語言不限定,一般是用 PHP。不過特別規定不能使用一些太強大的資料庫套裝功能,而要自己直接用SQL操作。我們這組採用的是 Python 配合 Django,當然就不能使用裡頭的 models 了。

原始碼可以在 github 上觀看:animedbs。真的做了好久,簡直是心血結晶!

設計 SQL 時使用了 MySQL Workbench,感覺幫助良多。

結語

基礎方面,理論的部份還好。實做 project 的話,有些相關經驗會有幫助。我覺得這堂課修起來最辛苦的地方有兩個,首先是 project,似乎是一開始的 proposal 不小心把資料庫設計的太複雜,所以花了很久的時間才實做完成。尤其這學期我剛好修了不少實做課,所以感覺力不從心。不過可以使用任意語言這點滿令人高興的,一直想學 Django ,這次終於有機會使用。

另外一個辛苦的地方大概是定義不清的問題吧,因為投影片採用各家書籍,有時會出現不同定義,例如 natural join, equi-join,老師是說使用哪種定義都可以。不過也有一些是投影片只有一種講法,但和課本不同的情形。也有遇到公佈的小考解答解法跟老師教的其實不太一樣。助教表示僅供參考。另外就是 B+ tree 要怎麼刪除資料,課本沒有寫出詳細演算法,可能也得細心多看才能理解。這些小問題需要多加注意,所以有時滿困擾的。

平常這堂課都會有一些不同年級的同學來修。這學期應該是因為跟專題(一)衝堂,所以修課人數非常少,只有四十幾個人,相比起來是溫馨的小班教學。

辛苦的一學期終於結束了,覺得很開心。

嵌入式系統設計概論與實作 – 交大修課心得

digital-camera

課程資料

嵌入式系統設計概論與實作

開課:曹孝櫟老師

修課年度:100資工系

上課時針對嵌入式系統各方面探討,包含 bootloader 原理,OS,硬體,開發,業界情況,一些嵌入式作業系統、開發工具。實驗用的板子是是 ARM 平台,並常使用 linux 系統,所以也會提到這部份的課題。在 OCW 網站上有影音可看:〈嵌入式系統設計概論與實作〉

實驗部份主要是利用 PCM7230 板子做實驗,包含燒錄開機程式和作業系統等等。最後的實驗和專題則是在 Openmoko 手機平台上進行,不過老師說每年不一定一樣。

老師上課時有提到一本教科書《Real-Time Concepts for Embedded Systems》,內容主要是嵌入式系統實做的一些概念。如果要跟實驗比較相關的話,推薦《Building Embedded Linux Systems》,尤其對實驗 1 非常有幫助。

上課方式

上課主要是使用投影片上課。老師非常能言善道,有時一張投影片就可以講一節課。說話速度很快,內容也很有趣,有時會有一些經驗談。雖然因為不點名,而且上課內容跟實驗內容也沒有絕對關係,加上又不考試,所以後期學生較少。然而其實是很值得一聽的。

實驗的方面是以兩人為一組,每組會發一份板子等實驗用具。要自己找時間去做,然後在星期三晚上去 demo。由於一開始的實驗需要用到 RS232parallel port,但是最近的電腦很少支援,所以也有額外開放時間讓同學到實驗教室使用電腦。

評分方式

沒有期中期末考和小考,所有評分就由 8 次 lab 和最後的期末 project 決定

  • Labs 80%
  • Final Project 20%

有時候lab會有額外的 bonus 可以做,不過最後lab評分似乎是看大家做的情形來決定分數,所以如果大部分的人都有做 bonus 的話,就得做完所有 bonus 才能得到滿分。本學期課程中僅有 lab 3 的 bonus 可以讓分數超過該次實驗的滿分。

考試作業

每次實驗都需繳交報告,有時也得繳交原始碼。期末專題的部份,需繳交 proposal, slides, report,最後以簡報方式介紹自己的專題,並實際 demo。

一開始的實驗因為剛在熟悉環境所以每兩個星期交一次,後來的實驗就是每星期一次了。Lab 主題如下:

Lab 1 - Environment Setup/System Installation/Hello World

在 PC 上建立 PCM7230 平台的 toolchain,包含 gcc cross compiler, 編譯 glibc,以及燒錄開機程式, linux kernel,檔案系統等等。並執行 hello world 程式。

Bonus:

  • 撰寫 echo 程式透過 RS232 和 host 溝通。
  • 設定開機時自動執行程式。

Lab 2 - Bootloader

重新編譯 Intrinsyc i-boot-lite bootloader,加上自訂訊息,以及新增多重開機功能。實際燒錄至板子上。

Bonus: 研究 bootloader 的組語程式碼,並加上註解說明程式流程。

Lab 3 - Non-OS Embedded Application

移除 iboot bootloader 中的不必要功能,縮減大小。新增檔案加密功能,可以加密放置在 CompactFlash Card 上的檔案。

Bonus:

  • 在 CF Card 插入時自動加密其上特定或所有檔案。
  • UBoot bootloader 移植到 PCM7230 平台上。
  • 修改 UBoot,使其可以有監聽網路封包的功能。

Lab 4 - Windows CE

透過 Windows CE .NET Platform Builder 4.2 編譯並安裝 Windows CE 至板子上,透過 eMbedded Visual C++ 4.0 撰寫 hello world 程式至板子上。

Bonus:

  • 縮減 WinCE 作業系統大小。
  • 開機時自動執行 hello world。

Lab 5 - Linux Kernel and Root Filesystem

重新編譯 Linux 核心,並修改檔案系統,安裝 bash ,設定開機時自動執行程式。

Bonus: 透過各種方法縮減核心大小。

Lab 6 - Interrupt Tracing and Simple Device Driver Programming

在 linux 核心中插入訊息,觀察中斷發生流程。編譯範例驅動程式,觀察滑鼠移動時的印出訊息。

Lab 7 - Network Packet Tracing

修改 linux 核心以及 /proc 檔案系統,實做簡易網路封包監聽功能。

Lab 8 - Burning U-boot/Kernel/Root Filesystem for Openmoko

利用 Openmoko 官方提供的工具燒錄 bootloader / kernel / root filesystemNeo FreeRunner 手機上,然後執行範例程式,觀察重力加速器的數值。

Final Project

利用 Openmoko 手機平台,配合至少一種感應器,實做創意專題。也提供材料費可以購買外裝感應器。

結語

自己覺得整個課程最難的地方其實是第一個實驗,要安裝 linux 作業系統(也可安裝在 Virtual machine 上),而且因為要建立的 toolchain 平台是非常古老的版本,所以常會有奇妙的相容性必須解決,或者得使用非常古老的 linux 作業系統,途中常常要自己 Google 才能找到答案。

由於 RS232 的接頭實在太難找,但一開始沒有開放電腦教室,我們還曾去順發購買線材,從主機板上剛好有的 RS232 接頭接出來。(如果主機板完全沒有 RS232 的話,想買 RS232 卡會非常貴,不切實際)

後期的實驗大致上只要照著實驗講義做就不會有問題,如果有問題,通常是硬體有問體。(確實也曾遇到不少次硬體問題)不過在做 WinCE 實驗時,會有一些軟體似乎要在 Windows XP 上才能跑。(或者也可能是 32-bit / 64-bit 等問題)所以感覺修這堂課也重灌了很多次作業系統 (笑)

整體來說嵌入式其實不像之前學長們說得那麼辛苦,至少跟這學期的編譯器和人工智慧比起來似乎輕鬆不少,這學期也要感謝組員的幫忙所以才那麼順利。

微處理機系統實驗 – 交大修課心得

mother-board-581597_640

課程資料

微處理機系統實驗

開課:陳添福老師

修課年度:100資工系

撰寫在 microcontroller 上執行的程式,利用實驗版或甚至麵包版,實際使單晶片和環境互動。所謂的 microcontroller,指的是把中央處理器、記憶體、各種輸入出介面等等都整合在一起的小型計算機。

這堂課使用的微處理機為 8051,使用的語言一開始為 8051 的組合語言,但到後來多半用 8051 C 來做更複雜的操作。其他一些跟這門課相關的議題:〈微處理機系統實驗〉

上課方式

使用投影片上課。雖然官方上有分上課和晚上的上機時間,不過老師比較喜歡連在一起上,所以在開學時就把上課改成上機前的晚飯時間。上機課兩人一組,在工三二樓的電腦教室上課。

評分方式

沒有期末考和小考。由於學生要求,所以沒有期中考,所有評分就由 10 次 lab 和最後的期末 project 決定。Lab 做不出來都可以補 demo,不會扣分,不過每次的實驗報告要準時交。

評分比例和每次實驗的成績一直都沒有公佈,建議如果往後有機會修習的話可以向老師要求公佈所有原始成績。

考試作業

Lab 主題如下:

  • Lab 1 - LED:控制 LED 燈,使其輪流閃爍。
  • Lab 2:讀取按鍵輸入,在矩陣顯示器上顯示數字
  • Lab 3 - 七段顯示器 + 麵包版:操作 7 段顯示器,顯示特定數字。一開始先是實驗版上的顯示器,接下來要自己接麵包版。
  • Lab 4 - Keyboard I/O:用 4x4 數字鍵盤配合七段顯示器製作計算機。
  • Lab 5 - Timer/ Counter:透過計時器製作時鐘,透過計數器計算按鈕按下次數。
  • Lab 6 - 8051 Interrupt:透過外部按鈕中斷控制LED。透過計時器中斷控制七段顯示器,達成倒數時鐘。跟上次 Lab 很像,只是透過中斷,可以達成更精準控制。
  • Lab 7 - LCD:用 LCD 顯示數字,製作可調整的鬧鐘等等,這裡常會遇到硬體問題,值得注意。
  • Lab 8 - 8051 RS232 序列傳輸:透過 RS-232 接頭和電腦通訊,可以在終端機上顯示文字,也可以接收鍵盤輸入終端機的內容。在這 Lab 裡,使用的是 Windows 內建的「超級終端機」,不過其實用 PuTTY 也可以連,而且還可以用控碼等等來達成特殊效果,在期末專題時或可一試。近年的電腦,慢慢沒有 RS-232 接頭了…
  • Lab 9 - External Memory & ADC:將程式燒錄到外部記憶體,再讓 8051 從記憶體中開始執行。另外還有讀取光敏電阻/熱敏電阻的訊號。
  • Lab 10 - 8051 周邊 I/O:玩玩磁簧開關、蜂鳴器、繼電器等等元件,為專題準備。

最後幾個星期就是做期末專題,大家點子都不太一樣。這期間要上台報告兩次,一次是專題構想,一次則是最後講解專題。大家可以觀摩彼此的專題,最後還有觀眾投票,前幾名有神秘小禮物。

筆者這組的期末專題是一個搶答遊戲,利用 RS-232 從電腦終端機顯示題目,兩個玩家透過按鍵搶答,答對時玩家的四驅車會前進,誰先到達終點即獲勝,題目中也有利用蜂鳴器來實做的猜歌題。也有同學是做打地鼠遊戲。

結語

這堂課重要的就是實驗啊,所以都不點名,也沒有考試。注意到作業投影片和上課投影片常常當天才放上去,所以對我而言想提早準備也有點辛苦。

這門課感覺最花心力的其實是硬體問題,組語和 C 的語法其實不多。記得最後做期末專題時我們還用了烙鐵之類的,記得我烙了半天弄不好,還有熱心的朋友跑來幫我。

然後就是,買材料還滿花錢的,本來想用紅外線模組,不過失敗了,似乎限制頗多,不見得能達到想要的效果。

延伸閱讀

密碼學概論 – 交大修課心得

padlocks

課程資料

密碼學概論

開課:陳榮傑老師

修課年度:100資工系

探討加密背後的數學原理,如何在第三方可以攔截或假造訊息的情況下,加密訊息以保證僅有信任的人可以得知真正的內容。也會討論延伸的議題如 digital signature, secret sharing 等等。一些相關議題也可參考:〈密碼學概論〉

上課方式

老師會用自己的投影片,配合 Windows 筆記本的手寫講解,再加上課本頁面。平常不點名,只有一次要簽名,不過有事先提醒。由於要實做加密演算法,可能要稍微寫過 C/C++ 程式會較好。另外,若有學過離散數學的話,對 RSA中國餘式定理等等原理也會較熟悉。據說網路安全和電腦安全概論也和此課程有些重疊。老師也常向我們推薦下學期開的橢圓曲線密碼學,是這堂課中部份課題的延伸。這幾門課都是資安學程的課程。

評分方式

評分方式為:

  • Homeworks 25%
  • Midterm 35%
  • Final Exam 40%

作業主要分兩種,一種是紙筆作業,主要是一些計算題,考試大部分的題型都是作業習題,只有改動數字,所以作業值得反覆練習。另一種作業則是程式作業,實做各種加密演算法,透過 E3 繳交之後,助教會逕行批改,不過要一直到期末考結束後才知道自己的分數。似乎有不少人的程式作業分數因不明的原因偏低,不過向助教反應後都有提昇。

據稱每年的程式作業都會選擇不一樣的加密法,不過加密法的演算法老師都會給,這學期實做了 RC4 以及 SHA-1。筆者也把自己的程式碼釋出於 github,可以當作參考:100-crypto

考試方面,有一個期中考和一個期末考。總分都會超過 100 分,題目主要出自習題及考古題,不過也會有新的題目。期末考提前一個星期考完,所以最後一個星期都沒有課。

結語

老師說他本來沒有要教橢圓曲線密碼學,不過後來和助教討論之後,發現這學期同學的成績似乎比較好,所以最後就教了(笑)。筆者比較過兩個學期的期末成績,這學期的高分群真的比較多。

我也研究了一下老師使用的教科書,在上學期使用的是《An Introduction to Mathematical Cryptography》,這學期使用的則是《Cryptography, An Introduction》。後者省略了許多細節,而且完全沒有練習題。前者對數學背景寫得比較詳細,筆者多以那本配合老師的講義使用。不過其實兩本書的內容有些是沒有重疊的。

在課程大綱上特別標記了前者在圖書館有電子書下載,後者則是可自由下載的開放電子書。老師似乎是希望同學可以不用花那麼多錢買教科書。筆者剛開始為了能在上課時參考課本,到影印店影印了課本,不過到後半學期就幾乎沒看,而且整本書有教的部份其實也不多,現在覺得其實沒有影印的必要性。

作業習題和考古題得多做,考試題型大多數都從裡頭出來。

筆者一開始先是閱讀《An Introduction to Mathematical Cryptography》來打底,在上課時一開始是配合影印本,邊聽課、邊查閱資料。期中之後的數個星期,看完了《Intro. to Math Cryptography》,就比較少在課後複習,尤其老師恰巧一直沒派手寫作業,又覺期中這樣有很多考古題的考試型態尚可臨時抱佛腳,或許因此稍微懈怠。課程進入橢圓曲線後,上課便以老師的投影片為主,不再閱讀課本。到了期末時,其實讀起來覺得有點趕,現在想來應該要提前複習投影片才是。

心理疾病介紹 – 交大修課心得

medicines

課程資料

心理疾病介紹

開課:高之梅老師

修課年度:100通識(群己)

介紹各種心理疾病,一開始先簡介各大心理學派及其對心理疾病的解釋,接下來的主題分別是:

  • 焦慮及適應問題 - 畏懼症、恐慌症、強迫症
  • 情緒低落與憂鬱
  • 自我傷害行為
  • 創傷後壓力症候群及災難心裡反應
  • 悲傷與失落
  • 情感性疾患 - 躁鬱
  • 精神分裂症及相關知覺障礙
  • 發展心理問題:人格障礙發展心理問題 - 自閉症、阿茲海默氏症

參考書目為:《變態心理學(修訂版)》,這本書很大一本,我從浩然借來以後,因為難以閱讀,所以很快就還了。由於考試還滿簡單,沒看這本書應該也沒什麼關係。英文版為《Abnormal Psychology》

上課方式

用投影片上課,有時會小點名或者讓同學臨時分組討論。這學期是討論憂鬱症與自我傷害的故事,讓大家分享聽聞過的經驗。我覺得討論的經驗十分有趣。

因為老師語調有點緩慢,上課時有些同學其實在看自己的書。不過有時會播放疾病相關電影,這時大家多會專心觀影,確實有許多精彩橋段。放過的影片有愛你在心口難開、伴我情深、時時刻刻、飛越杜鵑窩等等。

評分方式

評量的方式為:

  • 出席 40%
  • 口頭報告 30%
  • 期末考 30%

平常偶爾會點名,也曾有早到的加分。

在一開始上課時就會請同學自行分組,約 7~8 個人一組。每組要決定報告一種心理疾病,會在接近期末時開始進行各組報告。報告的形式為簡報口頭報告,各組多會配合相關電影講解。

我們這組還演了小劇場 =w=b

報告的氣氛還算和諧,老師不會特別說各組的缺點。

期末考主要是是非題,最後還有問答題是要根據上課播放過的影片來敘述各種心裡疾病的症狀。題目寫起來還算簡單,不過也沒有信心可以完全寫對。無法得知最後期末考的成績,最後我的學期成績是 86 分。

結語

老師感覺很和善,她說最好要有修過普通心理學,不過感覺影響沒有很大。整學期下來 loading 不大。雖上課本身有點枯燥,不過因為分組報告,得到了一些團隊合作的經驗,也認識了一些人,真的很感謝組員的幫忙,也讓我學到不少。考完期末考時,老師還為我們的其他期末考加油打氣!

組合語言與系統程式 – 交大修課心得

assembly

課程資料

組合語言與系統程式

開課:陳永昇老師

修課年度:99資工系

組合語言的部份使用的是《Assembly Language for x86 Processors》,教了以下章節:

  • 1. Basic Concepts
  • 2. x86 Processor Architecture
  • 3. Assembly Language Fundamentals
  • 4. Data Transfers, Addressing, and Arithmetic
  • 5. Procedures
  • 6. Conditional Processing
  • 7. Integer Arithmetic
  • 8. Advanced Procedures
  • 9. Strings and Arrays
  • 10. Structures and Macros
  • 13. High-Level Language Interface
  • 14. 16-Bit MS-DOS Programming
  • 17. Expert MS-DOS Programming

系統程式的部份使用的是《System Software: An Introduction to Systems Programming》,教了以下章節:

  • 1. Background
  • 2. Assemblers
  • 3. Loaders and Linkers
  • 8. Software Engineering Issues

額外有出了一份寫 DOS 病毒的作業,可以學習一些感染 EXE 檔的技巧。

本門課的組語主要是用 MASM 組譯器的格式,同時也會運用到教科書中的諸多 routines。由於老師並不會特別教導組譯環境的設置,同學需自行閱讀教科書及作者網站,我寫了一種環境設置的方法和其他一些跟這門課相關的議題:〈組合語言與系統程式〉

上課方式

使用投影片上課,大抵上上課氣氛很自由,不會有什麼壓力。由配分可見它是以實作為主的課程,本文也以介紹作業為主。

每份作業都需 demo(包含期末 project 在暑假 demo),是在 demo 時從 E3 上下載之前上傳的程式碼,由於並不會事先公佈所有的測資,所以要細心一點。組語作業如果有多做功能可以主動向助教提出,可以得到不等的額外加分。

另外,事後會公佈全班的 code 供大家學習參考。上到最後一堂課時會有一張特別的投影片:師:「永生難忘」。

不點名,但是有來上課的話可以提早得知作業。作業投影片通常在宣佈後一星期放上E3。此外,死限延期或其他特殊事項也是只有在上課時公佈,或者在上課時提早公佈。

評分方式

這門課的配分是這樣的:

  • 60% 4次組語作業
  • 25% SIC/XE 組繹器(可用任意語言寫)
  • 15% 期末考

沒有期中考,不過另外有一個期中組語上機考,是考較為簡單組語程式題目,也可攜帶參考資料和作業原始碼,但若未通過則 4 次組語作業不能算分。

根據前人的經驗,只要作業都滿分,就算期末考六十幾分也能得到 99,有付出就有收穫。

考試作業

作業通常會在上課公佈,晚一點則會公佈在 E3,死限通常在星期日的夜晚。

第一個作業是三個組語小程式:

  1. 輸入兩個 32-bit 正整數,輸出其最小公倍數。
  2. 輸入一個日期,輸出那天星期幾。
  3. 輸入一個正整數,輸出所有比它小的質數。

第二個作業是用組語寫一個 finite-state machine 可以解析一行輸入的組合語言(MASM 格式),如:

1
2
3
4
5
6
7
8
9
Input=> L1: sub ecx, var   ; substract ecx by var

Result=>

        LABEL             L1
        INSTRUCTION       sub
        REGISTER          ecx
        IDENTIFIER        var
        COMMENT           substract ecx by var

如果有錯誤輸入,該錯誤 token 輸出 unknown,但其後的正確 token 仍需正確辨識。不需判斷 grammar 錯誤,如 mul 應該只能接受一個 operand:

1
2
3
4
5
6
7
Input=> mul eax, 5

Result=>

        INSTRUCTION       mul
        REGISTER          eax
        INTEGER           5

禁止使用 .IF .WHILE 等 directives

第三個作業是寫一個計算機,可以計算輸入運算式結果,支援 + - * / ( ),如 2+4-6*2 = -6。輸入運算式最長為 100 字,數字長度最長也是 100 位(需使用大數運算)。

第四個作業是 16-bit DOS programming:

  1. 寫一個 TSR 鋼琴程式,鍵盤需可正常輸入,但按下按鍵會發出聲音。
  2. bonus(這題本來不是 bonus,後來更改評分):寫一個 TSR 病毒程式,執行後會常駐於系統中,在你開啟另一個 exe 檔時感染該執行檔,使其執行被插入的程式碼(如列印一行字),但仍保持原有的功能。

期末 Project期限在期末考後的一個星期後。是要以如《 System Software: An Introduction to Systems Programming》 一書的格式,撰寫一個 SIC/XE 組譯器可以產生 relocatable object program。

其中 60% 要支援所有 addressing modes, 教到的 assembler directives,以及以下除外的指令:浮點數運算、SW register 相關指令,SIO, TIO, HIO,LPS, STI, SVC,SSK。

40% 佔分則為:Literals, Symbol-defining statements, Expressions, Program Blocks and Control Sections。

我有把一部分的作業原始檔放在 github 上,可供參考:99-asm

上機考有三題:

  1. 印出 Pascal’s triangle
  2. 給一個長度 4 字串,輸出任一重排後字串。
  3. 給兩個最多 40 位的二進位數字,輸出相減後結果。

不需全部解出也算通過。

期末考的題目主要配分是系統程式占的較重,所以不要只看組語的部份。仔細觀察可以發現,題目大多為課本習題,特別是系統程式的部份。這次的組語大多為選擇題,系統程式相對較難。老師會給考古題,不過有重疊的題數大概只有一兩題。

結語

想要預習或自修的話,《 Assembly Language for x86 Processors》 這本書每章背後都有程式練習題,筆者做過幾章,覺得挺有幫助,感覺跟程式語言有關的課練習都是十分重要。組語的教學也可以參考小木偶的網頁

系統程式部份可以邊寫組譯器邊看,這樣會有更深的理解。自己修這門課花了很多心思在作業上,不知不覺就會忘了讀系統程式。但這門課的系統程式部份實際上佔分滿多的。

雖然沒有期中考確實讓期中的壓力減輕不少。但對筆者而言,組譯器的撰寫顯得有些匆忙,逼近期末考周時,因為要準備考試,沒時間寫期末 Project。即使考完期末考,最後一個星期忙著搬宿舍,能寫的時間不是很有彈性,不得已得花很長得時間連續不斷寫 Project,寫到最後動力遞減,很容易想放棄。

現在想起來,我認為最好可以一開學就開始寫 SIC/XE 組譯器,一方面可以邊寫邊看課本來準備期末考,二方面透過時段的切割可以避免學期末擠在一起時的壓力。

況且其實一開學就會說期末 project 是什麼了,就算最後發現要求不太一樣,也依然有理解系統程式課程的好處。

延伸閱讀

演算法概論 – 交大修課心得

computer

課程資料

演算法概論

開課:蔡錫鈞老師

修課年度:99資工系

這門課所使用的教科書是:《Introduction to Algorithms》,教到的主題大約為:

上課方式

使用投影片上課,作業通常得在上課前交,不接受遲交。所有的作業都會公佈在網頁上(在課堂公佈前就貼上課程網站了)投影片上有很多註解,有別班的同學說他自己覺得比他們班的投影片好理解,不妨參考:〈課程投影片〉

評分方式

成績主要由期中、期末考,手寫及程式作業,以及上機考所決定。不點名,作業會抓抄襲,

小道消息指出,程式作業會搜尋一下網路看你是否直接下載別人的程式。

期中考分數分布:

分數 人數
00∼ 09分 0 人
10∼ 19分 1 人
20∼ 29分 6 人
30∼ 39分 6 人
40∼ 49分 10 人
50∼ 59分 11 人
60∼ 69分 4 人
70∼ 79分 5 人
80∼ 89分 2 人
90~ 99分 1 人

考試作業

雖然老師一直強調注重實做的能力,認為修這班的學生一定要寫 code,不過覺得程式作業其實沒有想像中繁雜。(至少跟先前修吳育松老師的資料結構比起來,感覺 coding 時間少了很多)

第一個程式作業是實做 merge sort 和 heap sort。第二個是實做 Exercise 9.3-8:在 O(lg n) 時間找出兩個 sorted array 的中位數。第三個作業是修改老師寫到一半的程式碼,實做 chained hash table (事實上只要改數行)。第四個是 DP 有關的三個題目。第五個是實做 Huffman codes 並且作成一個可以壓縮和解壓縮檔案的程式(需要 demo)。第六個是實做跟 Maximum-flow 有關的題目以及跟 A* search algorithm 有關的題目。

大體上除了第五個作業外,都是純粹演算法的題目,而沒有很多實做的細節,所以通常在一百行內就結束,最長也差不多兩百多行。只是有些題目到底要怎麼套用演算法可能需要深切的思考跟那種沒有複雜演算法但實做起來要花很多時間的 project 大不相同。

而手寫的題目大多是證明題,助教對證明嚴謹度十分要求。由於課本後面的解答大多忽略很多細節,所以直接照著寫一定是會被扣分的。(就算用老師公佈的解答寫在期中考上也會被扣分,筆者親身經歷。)筆者覺得寫手寫作業的時間比 coding 長很多。

題外話,在這堂課的訓練之下,寫到後來慢慢自己對嚴謹度的要求也愈來愈高。像是這題:

16.3-7

Generalize Huffman’s algorithm to ternary codewords (i.e., codewords using the symbols 0, 1, and 2), and prove that it yields optimal ternary codes.

筆者為了達到十足的嚴謹度,足足寫了 A4 紙兩面半才證完。(雖然我覺得應該不可能要寫到這種地步才能拿滿分,並且數學好的人說不定可以用短一點又嚴謹的方法證明它吧)

考試方面有期中考和期末考,幾乎都是考考古題,主要仍以證明為主,少部份是操作演算法

還有一兩題是手寫短程式。

還有一個期中上機考,幾乎都是考作業題,如果上機考不好,最後還有個上機補考。

結語

演算法是資工最核心的學科之一,沒事可以多讀讀 Introduction to Algorithms。如果對 online judge 形式的作業不熟悉可以參考:〈基礎程式設計〉。學校的網站上有很多題目可供練習,未來應該會有很多課都採用此一介面來交作業及考試。

想看一下演算法的介紹可參考:演算法筆記

數位電路實驗 – 交大修課心得

electronics

課程資料

數位電路實驗

開課:陳健老師

修課年度:99資工系

這門課是教如何利用 Verilog 硬體描述語言來設計數位電路。感覺前半段很偏向數位電路設計的部份,一直關注 gate level。接著主要的主題是 finite-state machine。後來上機課開始使用 FPGA ,透過 Verilog 來設計並合成許多遊戲類的電路。最後上課的內容則是 coding style,debug 經驗談,以及一些 Intel 設計 CPU 的小故事等等。

主要教科書是《Digital Design》,但大體上除了最後有一個作業以外,幾乎是不會用上。不過感覺裡頭的 Verilog 練習題應該能提供不錯的訓練(寫完該作業後的心得)。

參考教科書有數本

  1. 《Verilog HDL》
  2. 《The Verilog Hardware Description Language》
  3. 《Verilog HDL Synthesis, A Practical Primer》

我看過的有第一和第三本,第一本是相當不錯的 Verilog 語言教材,第三本有些枯燥,不過看完對合成能有更多了解。基本上每本書內容都不多,Verilog 語言的語法會用到的部份其實是相當的少。

其他關於數位電路實驗的議題可參考:〈數位電路實驗〉

上課方式

上課是用投影片教學,一部分是《Digital Design》 的投影片,另一部分據稱是據稱是 MIT 的講義。最後還會有另一系列的投影片後來才出現。

助教會在上課時先公佈下週要 demo 的作業。而晚上是上機課,要在下課前 demo 上週派的作業。

考試作業

這學期的上機有 10 個:

Lab 0 是熟悉 Xilinx ISE 軟體的使用,只要複製助教的 code 即可。

Lab 1 是熟悉 FPGA 板的使用,它看起來很像一般的網路卡等等,上面有 LED 燈、按鈕、還有螢幕、滑鼠、鍵盤接頭。用上面的開關當作輸入,LED 當作輸出,實做一個 2-bit decoder。剛拿到板子真的很興奮,和跑軟體模擬感覺大不同。

Lab 2 是要用 gate level (直接用 and, or, not 等 gates) 來設計一個 4-bit comparator。

Lab 3 是做一個 Stack,和另一班的範例很像。

Lab 4 是用板子的 LED 燈顯示各種不同的閃燈,還可以切換速度!這裡一直遇到板子的問題,按鈕常常沒有反應,一直要換板子,懷疑怎麼有那麼多壞板子。到後來的 lab 6 助教提供 ucf 設定檔後,才不易再遇到同樣問題。

Lab 5 是撲克牌遊戲機,抽排比大小,用軟體模擬的方式檢查是否正確。

Lab 6 則是把 lab 5 小小修改使其可以合成到 FPGA 板上,讓兩個人能抽牌比大小。用板上的 LED 燈顯示排大小和勝負,用板上的按鈕決定是否抽牌。其實玩比大小也可以玩得很開心。

Lab 7 是利用板子上的旋鈕和 VGA 接頭,在螢幕上輸出一個可被旋鈕控制的圓圈。旋鈕的輸入助教都幫我們寫好了,只要直接讀取它的值就知道是左轉還是右轉。螢幕的輸出也是,只要讀取就能知道目前的座標,再給該座標應該輸出什麼顏色就行了。

VGA 的原理可參考〈Pong Game〉

Lab 8 是 OOXX 遊戲,也是透過螢幕輸出。這次最主要的主題是如何從 ROM 中讀取圈和叉的圖像並輸出至正確的位置。

Lab 9 是打磚塊遊戲。將之前 labs 所有技巧都用上,總分加倍,很多 bonus 的最後專題。

筆者當初的期末專題打磚塊遊戲已開放原始碼於 ArkanoidOnVerilog @ github,其中也包含了我們整個修改的歷史,歡迎參考。

考試方面有三次上機考,第一次上機是用 gate level 寫,考你如何把複雜的邏輯化簡成容易實做的邏輯。(會這麼說是因為筆者覺得時間非常短,光打字就很趕了)第二次上機難度降低,是 State Machine。第三次上機考的比較久,是用 FPGA 板,考 VGA 的使用,也是寫遊戲。

除此之外還有紙筆測驗期中考。期中考意外的出了很多算的上是「數位電路設計」那堂課的範疇,像是 State transition table 等等。本來有期末考,但取消了。

期末時派了幾題 Digital Design 課本的 Verilog 習題,老實說不是很好寫,我幾乎花了寫打磚塊一半的時間才完成。上課曾經小考過一還兩次,還有幾次是寫建議問題算是點名吧。

結語

有時有外籍生問老師問題後老師就會維持用英語授課一段時間,大家都會心一笑。偶而有小考或寫問題心得不會事先通知。

感覺修數位電路設計的時候就順便玩玩 Xilinx ISE 好像也不錯,在網站上就可以下載了:〈Xilinx Downloads〉

這門課要讀的東西不多但寫作業很花時間。實做類的課程就是多練習就有進步。

交通安全與生命教育 – 交大修課心得

traffic

課程資料

交通安全與生命教育

開課:吳宗修老師

修課年度:99通識

上課內容包含交通法規常識、如何保命、如何在交通事故中佔有有利的法律地位。還有持續的叮嚀:不要開快車、不要開快車、不要開快車。

「不急不急,天堂會等你」

〈吳宗修的交通安全與生命教育 理論與實務的完美結合〉

Driving is serious business.

When you are in driving, you are in danger.

有時會看到頗為驚悚的畫面,讓人心生警惕。

上課方式

看影片,有些是交通宣導廣告,也有一些行車紀錄畫面。此外還有老師針對影片的補充說明及閒聊。發作業後會抽同學上來講自己寫的東西,然後老師會據此補充講解。自己覺得上起課來十分沉悶。

評分方式

這門課沒有考試,不過有十個作業。

  1. 節錄三則交通事故報導,並重點摘錄與分析原因
  2. 撰寫自己曾遇過的交通工具故障經驗,這事件對你造成什麼影響?
  3. 紀錄馬路用路人行為
  4. 寫出五個開快車的理由,並分析是否值得。
  5. 勸導三名行經清華夜市未走天橋及斑馬線而直接穿越馬路的路人,並作成紀錄。向五名親友說明走天橋的理由。
  6. 訪問出車禍的親友,做成報告。
  7. 手寫千字以上文章,宣導生活中需注意交通知識的重要性。
  8. 如果你在車禍中喪生,你的親友會怎麼反應,有何改變?嚴肅的撰寫一篇文章探討。
  9. 至法院旁聽交通開庭,並撰寫心得。
  10. 上完課的心得與建議,對什麼影片印象深刻?這門課以後可以出些什麼作業?你想和以後的修課者說什麼(三百字以上)的話?

Bonus:投書至市政府反應一則交通意見,加總分2分。

我把一部分的作業放上來供大家參考:

根據多位同學的經驗,想要得高分,內容要豐富,字數不能少。把內容寫多就有機會9x分。此外,除手寫作文外,繳交格式皆為A4紙,多張時要訂好,否則會被扣分。筆者每次作業大概寫1~3張,分數約落在70~85。最後的期末成績為90。

老師會按座位表點名,據稱上課如果睡覺或做別的事會被登記。(似乎有作業分數高但總分比認真同學低的案例)上課嚴禁手機響起,否則會被當,若不幸響起聽聞有寫報告補救方案。此外不得食用零食飲料,中堂不下課,不過似乎可自行走出教室。

結語

我就從期末心得中節錄吧:

交通安全這堂課,可以學到一些很有價值的交通知識。老師很用心的想教會我們一些像是防衛性駕駛的觀念。不僅長常識,還能保命,謹記老師的話:「不急不急,天堂會等你。」可以避免發生不必要的交通事故,同時,還會學到一些發生事故時的處理方法,以後就不會手忙腳亂。

上課時主要是看各種交通宣導影片還有聽老師講解交通知識和一些事故案例。這門課的作業皆為書面,其中比較特別的是要去旁聽法院交通庭、到清大夜市勸阻不走斑馬線的行人,還有一個手寫的千字作文。

注意作業不要遲交,否則會扣分,就算你晚進教室也應該一進來就繳交,不要等到下課。並且紙張須使用固定的格式,不可使用任意大小。另外要注意的事項是不要在教室中飲食以及請把手機關機。

分享一下參觀法庭的經驗,想知道何時有開交通庭可以上新竹地方法院網站上的庭期查詢,而要進入法庭非常自由,只要直接走進去就好了,要離開時也是一樣。不過要注意不能喧嘩,手機最好也關機。

身處交通大學,怎可不修交通安全?十分推薦學弟妹來修這堂課。

作業系統概論 – 交大修課心得

computer

課程資料

作業系統概論

開課:黃世昆老師

修課年度:99資工系

課本是 《Operating System Concepts》

上課方式

這堂課的價值主要偏實做。上課主要是用投影片講解,有時老師會講 Linus 的故事。

評分方式

這學期老師只有點一次名,不過有算分。以前聽說這堂課有很多 lab, Bonus 可以做,到了期中,就有人已經 8x 了,還說學期末有六個人 100,不過這學期盛況不再, Bonus 只剩兩個。

即使如此,作業依然不少,確實可以學到許多。像是 user thread scheduler 若不是修這堂課,我大概也不會有機會寫吧。

bonus 佔 10 分,所以作業考試和 bonus 加一加,分數上限是 110 分。學期末還有調分,最後有及格的人的平均是 81。

考試作業

老師好像蠻喜歡 Linux 而不是 Windows,所以許多作業主要在 Linux 上進行。這學期有三個 online judge 的作業,越早寫完,寫出題數愈多,分數愈高。除了把題目解出來外,每份作業還要另外寫一份報告解釋自己的作法並附上相關討論。

第一個是要寫一個小型的 online judge 去 judge 老師的程式,主要是要透過 fork 執行程式並想辦法取得子程式的資源使用,及輸出入的重導。

第二個是一般基礎程設的題目:〈2009-04: On Disk Scheduling〉,相對而言比較簡單。

第三個是用 makecontext/setcontext/getcontext/swapcontext 實做 thread scheduler:〈OS-0002: A user thread scheduler〉。這個作業不太好想,一開始為了搞清楚題意費了不少心思,寫好的第一個版本異常複雜,後來跟同學討論才想出較簡單的寫法。

除此之外,還有一些程式作業:有一個是要寫個程式製造 zombie process,並寫個報告說明什麼是 zombie process。還有一個是要用 C++ 配合 pthread, semaphore 實做 monitor。還有一個是要寫程式印出在 stack, heap 等等的變數及 functions 的記憶體位址,並比較與/proc/xxx/maps 的關係。

最後還有兩個 Bonus:

第一個是要用虛擬機 (ex. VirtualBox)安裝任一 Linux,並且加入自訂 system call 重新編譯核心,同時要寫一份報告及 demo system call 的使用。

推薦使用 Ubuntu,無論是安裝,編譯核心,加 system call,網路上都有 step by step 的教學。(因為版本會一直更新,所以這裡就不附連結了)安裝起來並不困難,只要一直按下一步就好了,如果有修過 SA 的,一定會很感動,他跟 FreeBSD 比真是天壤之別。

第二個是要取得 child process 的記憶體使用量的資訊(實際上為了完成 onilne judge hw1,本來就一定要完成這件事。)

我有把自己的報告和作業程式碼放在 github 上,可供參考:

考試方面,一共有三次期中考,老師都會給考古題,雖然會考很多新東西。

第一次考試,是到系計中線上考試,題型主要是選擇、填充等等。有一些記憶和觀念的問題,也有計算題。還有一些老師說是常識。第二次難度加深,還出了一題佔分 25 的程式題,是作業 monitor 的延伸。第三次改成紙筆考試,考得又更難了一些,計算題比重變得很高,尤其出了 page replacement 的題目。這題雖然在老師給的考古題就有出現,不過計算起來相當耗時。看到他的一瞬間,就直覺認為這份考卷要寫完很難。

結語

因為很多人作業寫不完的緣故,所以作業的 deadline 一直在延。我也在期末堆了四份報告和一份 online judge 沒寫,結果寒假第一個禮拜幾乎都在寫 OS 作業 囧

老師寄來的信,說話總是很客氣。

Bonus 中要裝的 Linux 真的推薦用 Ubuntu,我自己電腦上的主要作業系統就是灌 Ubuntu,反而 Windows 7 才是裝在虛擬機裡。感覺最方便的就是,不管是要寫 Java, Perl, Pthyon, Lisp, 還是 Prolog,執行環境都是直接用內建的套件管理員就可以輕鬆裝好。而且他上面又有很多方便的程式開發工具。

我都用 Vim 寫程式、gcc 編譯、gdb 除錯、git 管理程式碼。特別是 gdb,介紹給幾個人後,他們都覺得很棒,推薦大家可以試試看。

另外介紹一個工具叫 valgrind 是我上吳育松老師的資料結構時得知的。在除錯用 pthread 寫的 multithreaded 程式時,valgrind 和 gdb 真是配合的天衣無縫。我寫 monitor 作業時,他們真的幫助良多,否則我真不知要除錯多久。

延伸閱讀

p.s. 這篇文章裡提到的工具,有些也可在 Windows 上使用,在資工系計中甚至資訊服務中心的工作站上也都有,大家可以試試看。