edX HarvardX:CS50x3 Introduction to Computer Science修課記(一)

修了edx上哈佛大學的CS50，一方面是想一探這門哈佛最受歡迎的課程，另一方面則是想好好複習一下C語言。

誤打誤撞進了碼農(?)這行，僅僅憑著從前在大學草草修過的C語言課程，與一路上同事們的熱心協助，就這樣載浮載沉地打滾了幾年。
總覺得基礎仍然薄弱，於是就趁著這個機會，帶上從前修課用的教科書-C Primer Plus(厚厚一本959頁)，展開我的複習大業!

哈佛大學的這門CS50(Introduction to Computer Science)並不假設學生有寫過程式的經驗，事實上，這門課程也許是許多非工科的哈佛學生唯一的一門電腦課程，所以在課程設計上，也盡量不講得太過理論，而是用了許多比喻幫助學生理解程式如何運作，習題的設計也與生活盡量貼近。

課程一共為期十二週，每週的課程包含
lecture     : 包含兩段各一小時David Malan教授在大教室的授課影片
walkthrough : David Malan帶著走一遍程式碼
section     : 助教演習課
shorts      : 針對學習主題解說的小短片
problem set : 習題

現在上到課程第四週，目前的感想是，如果想要有個人手把手地帶著你一步步由淺入深地學習，只是看過lecture的影片其實很不夠。課程並沒有指定的教材與講義，每週兩小時的課程也僅僅是帶著你走過幾個觀念及語法，長篇大論幾十頁的習題，卻要你集當週教學的大成寫個程式出來。

David Malan上課的模式比較像是先為他要你知道的東西做個摘要，並安排一些與學生互動的遊戲引發興趣。像是在談到swap-交換兩個變量值的步驟時，就準備了兩個裝了牛奶和柳橙汁的杯子，請學生示範如何交換兩個杯子的飲料。生動的比喻很容易讓學生印象深刻，但每週兩個小時的時間並不夠好好說明一個觀念並舉些應用的實例。

在這方面，針對一個個學習主題做的short彌補了上大堂課的不足，例如compile的步驟、何謂function、演算法、pointer...等等，每一個小短片都針對一個觀念詳細解說，知識的含量很高。但儘管如此，要真正變成自己的東西，還是得自己動手做過一遍才行。

課後的習題分成兩個部分，第一部分是程式實作題，融入了許多應用的場景作為題材，例如判斷信用卡號碼是否有效、加密程式、打磚塊遊戲等等，在練習之時也會感覺到自己學的東西是真的能做出一些有用的程式出來。不過每一次的習題對於初學者來說，可能都是一個很大的跳躍，可能才剛學會迴圈和if else判斷不久，就得做出一個複雜的結構判斷信用卡號碼的位數，並配合運算式判斷是否有效和是哪家的卡等等。課程並沒有在中間安排幾個小小的練習讓你慢慢摸熟，也因為這是一門網路上的課程，並不像親自在哈佛有個面對面的助教和同學能與你討論，所以自己查資料和debug的工夫可不能少。在完成程式實作的習題後，第二部分則是幾個問答題，像是何謂function、某個演算法為何要這麼作等等問題，幫助你抓住學習的重點。

我認為整個課程含金量最高的就是shorts和習題這兩塊，其實shorts裡講的觀念書上大都找得到，不過有個人帶著走過一遍後，再回去看書就很容易抓到重點。

在哈佛校園裡的這堂課，中間還不時穿插社交活動、課外的project，期末還有個要組隊參加的hackathon，只可惜在網路上無法參與。

回想起在高中、大學的階段，自己未來的方向就得在上過一堆課後逐漸做出選擇，中間遇到過很有心、卻不知道怎麼把學生帶起來的老師，也遇過嘗試突破傳統框架教學、充滿熱忱的老師，也曾經歷過自己上完課完全不知所云，到了做實驗時才領悟的成就感。大部分學過的東西早已還給老師，但幾個自己印象深刻的作品、幾個感動的時刻仍然記得。

學習一個東西，我想除了功利地考量到學會什麼樣的求生技能、多了點機會外，另一樣收穫在增加了見識，瞭解到看起來很厲害的表象，底下原來就是遵循著這一套規則在運作。

關於開放式課程...

現在網路上的學習資源越來越多，我在上大學時開始聽到"開放式課程"的概念，大致上就是將學校上課的實況做個錄影，有點像補習班的為補課做的錄影，配合上課的講義、作業，甚至包含考試題目和解答放到網上開放給大眾免費瀏覽。

到了研究所時，開放式課程越做越好，出現了像是Coursera, edX等等的教學平台，課程內容不再只是隨堂錄影，而是請到教授專門為線上課程錄製影片，影片長度不是以小時為單位的課堂長度，而是拆成一個個的學習點，一段影片針對一個學習點作約十分鐘左右的說明，中間不時穿插互動式的問答。課後也有計分的隨堂測驗、作業等等，當最後修課成績合格時，有的課程還會授與修課證明。

"開放式課程"的課程內容，從早期大學課堂上必修的微積分、普物、普化...，到現在教學平台上五花八門的課程，涵蓋歷史、哲學、心理學、音樂...各個領域。

從2012年開始關注開放式課程，也註冊了幾門Coursera上的課程，但一直要到2014年，才認真地從頭到尾上完幾門課程，包含愛丁堡大學的音樂概論、麻省理工的數位電路設計、和新竹清大的計算機網路概論...，現在正在上哈佛大學的CS50等課程。

其實就算是沒有這些開放式課程，照樣可以從坊間各式各樣的書獲取知識，但是開放式課程提供的是一個不同的角度、一個可相互討論分享的網路社群、和一個外在的動力。

就一個個來說吧!

1. 不同的角度 : 

以我的學習經驗來說，一本教科書擺在面前直接硬啃，跟有人先帶你走過一遍再去啃，後者的效果要好得多，你會比較知道閱讀的重點，理解的速度也較快。

開放式課程的影片，就像是一個老師帶著你先走一遍，而且就我上過MIT的數位電路和正在上的CS50來說，我覺得著重的點也跟以往上課的點不大一樣。

這兩門課程，給我的印象是重視內容的廣度、而不會在課程上說明太多的細節。比如說數位電路關於布林代數的化簡和卡諾圖等等，在台灣可以講好幾節課，但MIT只是舉幾個例子稍稍帶過，不會說明太多繁瑣的計算。相對地，它會用啟發的方式引導學生了解資訊如何"數位化"，如何用電路實現數位化，一個數位電路的基本單元如何構成、有什麼限制等等，它會告訴你這門課程在整個學問體系中的定位在哪裡。學生能比較知道學習這門課的意義為何，但也得自己花些功夫去掌握細節。

另一個印象深刻的是，這兩門課程都用了許多的比喻，比如說哈佛的CS50，要說明電腦僅僅是個一步步執行指令的機器，只不過執行的速度非常地快而已 - 這個概念，就請了幾個學生上台，要他們作出觀眾要求的動作...，相信要比一句話帶過令人印象深刻多了。

還有一點很不一樣的是，修的這兩門課程都很重視實作。舉MIT的數位電路為例，課程作業包含了幾個電腦模擬的lab，開出一個電路規格，學生自己要用基本的組件來組合出要求的電路。而在其他填空的問答題中，也以各種模擬情境來設計問題，比如說一家新創公司找你當顧問解決技術問題、或是政府出資支持你的研究，你要向議員說明這個東西為什麼有用，不是在浪費納稅人的錢...。整個課程營造的氛圍，讓你感覺這不只是一門課而已，而是真的可以作出一些有用的東西。

2. 網路社群 :

我覺得這是"自學"和"跟著開放式課程學習"兩者很大的不同。自己抱著一本書學，碰到不懂的地方或不會的題目，可以google找資料，但網路上的回答不一定切合你的問題，你必須推敲網友的回答該如何應用到你的問題上。

而在開放式課程的學習平台上，往往設有針對每一個學習點和習題的討論區或是臉書社團等等，不懂的可以直接在上面發問，或是先參考之前其他人的問答。討論區裡的網友們，就好像課堂上的同學，有些人還會在上面自我介紹或是分享修課的心得。網路無國界!你會發現同學來自四面八方。逛逛討論區也成了種樂趣!

3. 外在的動力 :

除了有個網路社群陪伴以外，開放式課程也往往設有一個繳交作業的截止日期，錯過了這著日期沒有繳交，就會影響到你最後的成績，直接影響到你最後的修課成績是否合格，能不能拿到修課證明。

雖然說一紙修課證明，不知道對未來有什麼用處，但畢竟是對自己的一個肯定，也就會成為一股鞭策自己的動力了!

學習這件事，在各個階段對我的意義都不大一樣。

上大學以前，學習是一個比較的籌碼，但當時總認為學習是老師與長輩的責任；

上了大學後，學習是一種對自我的試探，但習慣被動後已忘了如何主動學習；

上了研究所，學習是一個求生的手段，工作在即，開始想著如何讓自己有更多的機會；

出了社會後，載浮載沉過一陣子，在這個講求專業與瞬息萬變的行業中，學習-仍然是求生的必備技能，但屏除專業以外，學習，應當也是一種享受。

學習樂理，把玩和弦的變化；學習歷史，瞭解社會的演進；學習藝術，沉澱紛雜的心靈；

學習運動，享受與人的互動；回過頭來，學習專業，享受完成一件任務的成就感。

希望未來的路上，持續有種種的樂趣相隨!

數位電路設計 - 開放式課程筆記(一)

最近幾個月在複習數位電路，同時上了一門edx上MIT和交大OCW的數位電路課程。

EDX MITx: 6.004.1x  https://courses.edx.org/courses/MITx/6.004.1x/1T2015/info

NCTU OCW : 邏輯設計 http://ocw.nctu.edu.tw/course_detail_3.php?bgid=8&gid=0&nid=174#.VTIUZvmUeSp

數位電路(Digital circuit)是電機系大一的必修課，以前大四時想拿個電機輔系跑去聽這門課，但一直到下學期的實驗課寫verilog時才有一點感覺。

交大的這門課的規劃跟以前自己上的進度差不多，大概就是一整個學期先講組合電路(combinational circuit)、再講順序電路(sequential circuit)。

但MIT的進度要緊湊得多，edx上的Digital Circuits不過是校內課程6.004 Computation Structure的三分之一，數位電路在台灣要講一學期的內容只講了6週，接著則進入programmable architecture和computer systems。

比較起來，MIT的這門課程要更注重與其他學門的關係，課後的練習也不時帶你去質疑一些看來基本、但也許不問，就從來不會去深究的電路。除了一般的填答題，還有幾個電路模擬的實驗，按照spec走過一遍更有感覺。

以下就每堂課做個簡單的筆記 :


第一講 : Basics of Information 

1. 定量訊息 :

先對information下個定義 : Data communicated or received that resolves uncertainty about particular fact or circumstance.

要定量一筆訊息，先知道該訊息出現的機率，再來計算要使用幾個0/1來為此筆訊息編碼，可由I(x)=log(base2)(1/機率)得到該訊息的量。
例如在一副牌中出現紅心的機率是1/4，訊息量即為2 bit；黑桃A則是1/52，訊息量為5.70 bit。
得到的訊息量越多，越能去除掉不確定性。

2. 編碼 :

         編碼(encoding) : an unambiguoug mapping between bit strings and the set of possible data

         原則上就是用一串bit的組合來表示一組data。若各個data出現的機率均等，可使用固定t;長度的bit組合；若不均等，可使用不定長度的編碼。

• ASCII共有94個字元，就可用log2(94) ~ 6.555約7個bit表示。
• Binary-Coded Decimal (BCD)可用log2(10) ~ 3.322約4個bit表示。
• 正整數可由二進制編碼表示，而為了閱讀方便，可將二進制改寫成十六進制
• 負數可使用signed magnitude將首位設成1，或是用2補數表示。
• * n個bit的數N，其二補數 = 2^n – N
• 不定長度的編碼可使用Huffman's algorithm, LZW...

3. 偵錯與除錯 :

        當送出與收到的訊息不一樣時，表示有幾個bit出了錯。

          
           Hamming distance : The number of positions in which the corresponding digits differ in two encodings of the same length.

     
        兩段相同長度的編碼，對應位置不同的數值的bit數目，即為Hamming distance。

        要能偵測單個bit的錯誤，可在原先的data再加上一位parity bit，使得總共1出現奇數或偶數次。

        原來兩組有效訊息之間的Hamming distance就從1增加到2。

        若是拿到的訊息出現1的奇偶次數與發送方不同，即表示可能出現單個bit的錯誤。

若是要偵測更多bit錯誤，Hamming distance就要再增加。

•  偵測E個錯誤，兩組有效訊息之間的Hamming distance為E+1
•  更正E個錯誤，兩組有效訊息之間的Hamming distance為2E+1

-----------------------------------------------------------------------------------------------------------------------------------------------------------------

第二講 : The Digital Abstraction

1. 編碼的bit怎麼來 :

使用電壓來編碼 – 電壓容易產生、偵測，也有可能較省電；但容易受環境影響，也有可能受到電容電壓的延遲影響。
但若要使用電壓來趨近一段連續的變化，例如0~10的變化分別以10個電壓位階來表示時，又容易受到干擾。
-> 用電壓僅表示bit的兩個值 0,1

2. 組合電路 : 

• 有一個以上的數位輸入
•  有一個以上的數位輸出
• 有一份功能規格(functional specification)詳述每個輸出與輸入所有可能的值的對應關係
• 有一份時間規格(timing specification)至少包含了穩定有效的輸入至輸出所需的時間
• 沒有directed cycles，從輸入到輸出，每個元件僅會經過一次 * 沒有feedbach loop

3. Noise :

訊息傳送的過程中，有可能會受到外界雜訊的干擾，造成上一級的訊號輸出到了下一級的輸入發生錯誤。因此，提高判斷輸出訊號為1或是0的標準，容許輸出在進入下一級的輸入時能有一定的誤差範圍，稱為noise margin。

• 輸出 :

0 : V <= V(OL)
1 : V >= V(OH)

•  輸入 :

0 : V <= V(IL)
1 : V >= V(IH)

• 標準 :

對於低電位來說，輸出的電壓V(OL) 要小於 V(IL)
對於高電位來說，輸出的電壓V(OH)要大於V(IH)
即有效的輸出電壓須大於V(OH)或小於V(OL)
而有效的輸入電壓須大於V(IH)或小於V(IL)

而V(IL)和V(IH)之間則為Forbidden Zone，當輸入電壓落在此區間時，輸出可為任何值
簡單地說 : V(OL) < V(IL) < V(IH) < V(OH)
output對於判斷是0或是1的要求較為嚴格，當signal從output到input之間若受到雜訊干擾，只要仍在input判斷0和1的範圍之內，仍為有效值。
允許雜訊干擾的範圍 : V(IL) - V(OL) 和 V(OH) - V(IH)，即為noise margin。