自由軟體 - 俠益千里

Course 2 - 俠益千里 ‧ 扶餘海外

紀宗衡講師@真理大學資管系

---

• 行動的初衷 :

讓外國的孩子看得懂外國的新聞。因為他們的家園正在一點一滴的消失，愈來愈多的草原瀕臨沙漠化，愈來愈多的土地被賣出，但是苦於地理與資訊上的隔閡，孩子缺乏了危機意識。

起床，電車，四小時辦公室或工廠的工作，吃飯，電車，四小時的工作，吃飯，睡覺，星期一，星期二，星期三，星期四，星期五，星期六，大部分的日子一天接一天按照同樣的節奏周而復始地流逝。可是某一天，『為什麼』的問題浮現在意識中，一切就都從這略帶驚奇的厭倦中開始了。『開始』，這是至關重要的。厭倦產生在機械麻木的生活之後，但它開啟了意識的運動。

-薛西弗斯神話

我把我的一切都交了出來，財產，作品，只把日記留給我自己。如果你還要折磨我，我就出走!我就出走! 

-托爾斯泰  

俠益千里，就是跳脫日復一日的框架，出走 。

• 當我們透過資訊去服務時，不是工程上的思維，而是管理上的

• 志工:
• 追求更好的生活民質，透過志工想想自己究竟能做什麼
• 因為有需求，才能達到真正的資訊應用
• 不是透過鍵盤，而是實實切切的用自己的手去幫助別人

• 寫程式與志工之間，究竟有什麼關係 ?

• 青年的四個大夢
• 一個人在17~33歲之間，如果沒有完成這四個大夢，將影響他往後會成為怎樣的人
• GitHub
• Social Coding : Code/do-ing together
• 思考如何分工合作、如何做自己想做的，如何做得更好
• 出走
• 你敢不敢走一條未曾走過的路，從安逸的大夢中醒來? 
• 因為走出去，而會與當地有了很深的連結，從文化，從語言，那將是跟著你一輩子的記憶，甚至改變一個人。
• 活動 :
• 偏鄉最大的問題，就是年輕人不回去了，即便我們現在把年輕人找回來，也必須面對他們的就業問題，於是，我們決定著手在留下這一代的年輕人。
• Arduino + Scratch + 布袋戲
• 讓寫程式不只有寫程式，而是包含了環境與文化
• 2013滾滾江原
• 2014俠益千里 : 哈薩克~台灣5500公里
• 服務 : 
• 建置一間電腦教室
• 一個自由軟體與英文的培訓團隊

---

Course 2 - 科技啟蒙

---

• 發表就是最好的記憶
• 鼓勵實作與研究，提供一個發表的舞台
• 科技啟蒙 = 對新手最友善的研討會

數位系統導論 - 布林代數

0.布林代數其實就是0與1的運算

1.三種布林代數的表示

• Boolean Algebra
• Truth table
• Circuit Diagram

2.普遍原則

• Closure
• e.g. 若x*y屬於集合S，則x,y也會屬於S
• Associative law
• a*b*c = a*c*b
• Commutative law
• 1+0 = 0+1, 1*0 = 0*1
• Identity elements
• + : 0+0 = 0 , 1+0=0 ,such that x+0 = x
• *  : 0*1 = 0 ,  1*1=1, such that x*1=x
• Distributive law
• x*(y+z) = x*y + x*z
• x + yz - (x+y)(x+z)
• DeMorgan's Theorem (德摩根定律)

• (x+y)' = x'y'
• (xy)' = x' + y'
• 廣泛用於電路最佳化（And與Or的轉換）
• e.g : x' + y' = (xy)' = NAND gate
• 可以用在SOP與POS之間的轉換

• Absorption
• xy + x = x (x+y) = x

3.運算子優先順序

• 括號 > NOT > AND > OR

4.邏輯閘

x與y為input

• And  : x*y
• Or : x + y
• Not : x = x'
• NAND : -> And ->Not
• NOR :  -> Or -> Not
• Exclusive - Or  (Xor) = xy' + x'y 相同input為0，不同input為1（互斥）
• Exclusive - Nor  = xy + x'y' 相同input為1，不同input為0

5.Positive logic and negative logic

• Postive logic : H =1, L=0
• Negative logic : H=0, L=1
• active high : 1的時候出現反應，為正邏輯
• active low : 0的時候出現反應，為負邏輯

6.Circuit

• Gate : 1個邏輯閘大概由2~14個電晶體構成
• Circuit : 由多組邏輯閘構成
•  A combination of interacting gates
• Integrated Circuit (IC)
• Chip 
• A silicon semiconductor crystal that contains the electronic components for constructing digital gates.
• Level
• SSI
• MSI
• LSI
• VLSI
• System : 放在一個PCB(印刷電路板)上，由很多組電路構成

7.Parameters for Digital Logic Families

由於不同的製作技術，在邏輯閘上以下的參數可能會有所不同

• Fan-Out
• 一個邏輯閘的Output到底能夠推動幾個邏輯閘正常運作
• 一個邏輯閘的輸出，最多能推動幾個輸入
• e.g. Fan-out = 2，Output就只能接兩個
• 假設1代表5V，如果接了3個，有可能一個Output只能達到2V
• 但是不影響原本的布林函數

• Fan - In
• 想做Fan-Out的反面

• Propagation delay (傳遞延遲)
• 邏輯閘是由電晶體構成，電晶體充放電都需要時間，所以會造成延遲
• 一個晶片裡，邏輯閘的數目有幾百萬～幾千萬個
• 即便一個邏輯閘的延遲只有幾奈秒，加總起來仍十分龐大
• 是用最慢產生的最終Output當成傳遞延遲
• 所以說，晶片的表現要好，整體模組的速度要差不多快

• 傳遞延遲跟光罩製作技術（e.g.微米，奈米）有關

• Noise Margin
• e.g. 1~0V之間判斷為0，4~5V之間會判斷為1

8.Computer Aided Design

• 現在的邏輯閘動輒上百萬，我們需要電腦輔助設計(CAD tool)
• EDA is specially used for IC design
• HDL (Hardware Deseription Language)
• 用來描述你電路的語言
• tool幫你compile之後會轉換(Logic synthesis)為邏輯閘(一個實體的電路)

• 電路實現的種類
• ASIC 
• 應用導向的積體電路
• 量身打造你設計出的電路
• FPGA ＆ CPLD
• 給你的是晶片，裏面cell都固定
• 我們可以自己把電路燒上去
• 只要電路沒有超過cell，都能應用上去 

9.NAND and NOR

• 其餘邏輯閘都能由NAND或NOR實做而成
• 為何使用?
• 因為NAND與NOR容易透過電晶體實做
• 因為NAND與NOR比起AND與OR有更低的傳遞延遲
• 電路上的轉換要則
• 1.2個Not = 0個Not，透過增加雙向的Not將AND或OR轉換
• NAND與NOR之間的轉換
• 用兩次迪摩根法則： x' + y' + z' = (xyz)'

Excel維護 - 第一次會議

第一次開會，閒聊時間比我想像來的長~~很~~多~~~，主要都在自我介紹跟分享開發經驗，不過大家都沒說幾句話，當下感覺氣氛超沉悶的崩╰(〒皿〒)╯潰，期待日後能慢慢的有話聊，至少在半年間合作愉快XD

資訊顧問，這個名號感覺纏繞著霸氣，可惜我不是吃了Excel果實的EXEX人，為了不辜負這個名號，只好照三餐問候那張圖表，看著看著就日久生情有了點心得，也寫了一些函式嘗試去改進它

不過我沒聽說過要在會議上發表啊啊啊啊啊!!!!!!!!!

    

 看到會議通知的當下

我的Excel真的只有學了一個禮拜，加上當天重感冒又跑C4 Labs，還來不及進旅店就被拖進了會議室，我在麥克風前就只是隻HP=1的風中蟾蜍。真心認為，這次的發表不甚理想，雖然我本來就是個不擅言詞的人(?)，但是回想不出自己說過什麼還是頭一遭，那時可能真的就靠直覺去做判斷吧，下次應該先擬好一份簡報，至少在狀況差時還能做些應對，幸好沒被Shut down。

我個人其實對除錯蠻感興趣的，不過是在ACM以外的地方，比方是這次的Excel。主要的錯誤是在Google試算表上可得的值，到了Excel裡變成 0，到了Number會少值，而錯誤是出現在多個sumproducts的Arrayformula跟vlookup上

Number會少值其實是我的誤判。Number在遇上函式不相容時，會先把儲存格內容轉為文字型態而非實際數值，這使得countif > 0會少算了浮點數。

Excel在這方面就乾脆多了，直接把所有的值都換成0，讓你不得不跟他來場生死決鬥。

除了一開始在編輯器上錯誤的嘗試之外，曾經想過把sumproducts轉換成sum，可惜功力不夠，參不透所有運算表達的意義，而且對vlookup是無解的。之後又把腦筋動到Arrayformula，結果還是Fail T_T，最後只好嘗試這兩個無效的函式剩下的的交集，都導入了其他試算表的資料，我猜應該是在這方面不太嚴謹吧，當初看到沒有用indirect就感覺毛毛的。
  
       距離下次會議還有兩個禮拜，或許有時間把一些危險的東東糾正過來，之後再對所有問題做個小統整吧～

Array - 陣列

1.陣列

陣列可想成是相同資料型態的一組集合，每個集合中的元素都會有一個索引值，透過 [ ]
陣列存取運算子，我們便能取得陣列中的元素。

2.C語言中實做一個陣列

當編譯器遇到了一個 Element_type array[SIZE] 的宣告，它會分配 SIZE 個連續記憶體給這個陣列，其中每份記憶體都足以儲存Element_type的大小。

也由於分配出的記憶體是連續的，我們能瞭解每一個元素的記憶體位置。對於第i個元素，他的位置是：

array + (i-1)*sizeof(Element_type)

還記得嗎，c的陣列是從0開始的，所以必須先執行 (i-1)。要特別注意，當i=0的時候，就是陣列本身，也是第0個元素儲存的位置，所以我們能夠這麼說：

array = &array[0]

有了每個元素的位置，利用 * 運算子就能夠依照位置取得元素的值了，若要取得第i個元素(從0開始)的值：

array[i] = *(array + i);

上述兩種取值方法是等價的。
 值得一提的是，在C語言中，我們不必對i*sizeof(Element_type)進行處理。

C4 Labs - Meeting 1

---

頭次聽說系上有社群應該是半年前，那時頂多看看議程跟主題，一來是因為怕進去就像個打醬油的，二來是因為真的沒什麼動力能讓我騎15分鐘的夜車。不過歷經一年悠悠哉哉的洗禮後，我終於把E罐填滿了，抱著要挑戰Boss的心情踏入了會議室......


  這次的會議花了大約40分鐘在推SITCON的坑，剩下的則是利用python來做網路爬蟲。

• #1. 什麼是SITCON？

簡單來說，就是以學生為核心的研討會，大家各自分享所長及專業，達到教學相長的目的。 SITCON的演講題目其實蠻多元的，可惜的是２０１４已經結束了～～～不過沒關係，SITCON的研討會都有上傳到Youtube，隨時都能夠回味那些有趣的演講，補全２０１４開幕時的一個梗XD

其實SITCON有的不只是年會而已，還有Hackgen跟不少Workshop，不過Hackgen就是要直接衝code上戰場了，年會比起來就平易近人一點，而且題目也能自由挑選。就像前文說的，如果認為自己有些想分享的，也能去交稿挑戰自己，或者當場報個Lightning talk。

•  #2. 網路爬蟲

網路爬蟲是個能自動抓取網頁上訊息的程式，可以用它來搜集大量的網路資料或偵測網頁內容的變動。

而這次引入的語言是python，聽到這個語言感覺就要被制裁了，幸好有獲得學習管道，不過Mac上也沒裝只好看著指令快速閃過，印象最深刻的也就DDOS選課系統了，這樣真的沒問題嗎？  
整體概念以requests為核心，然後利用beautifulsoup(美麗的湯?)來對獲得的網站進行編碼，最後用while迴圈持續的跑，當目標網站的文字(一個元件的.text值)改變時，會跳出警告，警告內容視需求而定，demo是彈出成功入口的網頁。
爬蟲不單需要python，對HTML與CSS也要有點認知才行，否則在查找原始碼時也不知道哪些是需要的資料。

數位系統導論 - Binary System

#1.數位是什麼？而為什麼要數位？

先回答第一個問題，資料可以用兩種方法來表示，即是類比與數位，兩者最大的區別在於數值連不連續，其中類比是連續的，而數位是離散的。用一條1~5的數線來看，類比資料可以是其中任何一個點，比如1.3、0.1884251，但是數位資料可能只代表了整數點1,2,3,4,5，而在1跟2、2與3、3與4、4與5之間不容許其他任何值存在，只能透夠近似的方式把3.23之類的居中值分配給最接近的點。

而為何要數位呢？正如先前的例子，我們可以發現類比資料是無窮無盡的，比如1與2之間切半得1/2，再切1/4，可以這樣無窮的切下去，但是我們的硬體則是有限的，所以必須把類比資料數位化，方便電腦進行處理。

而多數的數位系統會用兩個離散值來表示狀態，比如

• 0 or 1
• True or False
• High or Low
• On or Off

#2.進位制表示法

2-1

一個N進位的數字1234.5678而言，可以寫作(1234.5678)_N
而他用十進位的值為：1*10³+2*10²+3*10¹+4*10⁰+5*10^-1+6*10^-2+7*10^-3+8*10^-4

十進位轉R進制：

• 整數部分：不斷除R，除完後取商繼續除，直到不能除為止，取餘數排列(除越多次者越高位)
• 小數部分：不斷乘R，乘完後取積繼續乘，直到小數化為整數，(乘最多次為最小小數位數)

2-2
二進位轉八進位：由右往左數，三個(2的三次=8)為一組
e.g. : 10101011 -> 10101011 ->  253
 
二進位轉八進位：由右往左數，四個(2的三次=16)為一組
e.g. : 10101011 -> 10101011 ->  AB

#3.

Signed Magnitude representation

• 第一位用來表示正負e.g. 000 = 0,101= -1
• 容易在運算在溢位

1's Complement representation

• 負數表示法：原值0與1互換
• e.g. 1011000 0100111
• 缺點是存在兩個0 (111與000)

• 1補數的減法 
• 所有的減法都透過與其補數相加達成
• e.g. a - b = a+(-b)
• 相加如果有在最高位元有進位，要將進位值補到最末位元
• 反之，沒有進位則代表真正答案為負，要再取一次原結果的一補數

2's Complement representation

• 表示法：取一補數再+1
• e.g.1011000 取一補數 0100111之後加一得 0101000

•  2補數的減法
• 所有的減法都透過與其補數相加達成
• e.g. a-b = a+(-b)
• 相加如果有在最高位元有進位，直接捨棄進位得答案
• 反之，沒有進位則代表真正答案為負，要再取一次原結果的二補數

---

1.Binary Code

• 每個bit可代表兩個情形(0&1)，則n bits代表了2^n種情形
• e.g. 10進位的數字0~9要區別可以使用4個位元(16種) 

Binary Code 表示法

• BCD 8421
• 2421
• Excess - 3 =BCD + 3
• 84 -2 -1
• 以上每個數字都代表著一個位元
• 比如數字4
• 8421 : 0100 = 8*0+4*1+2*0+1*0
• 2421 : 0100 = 2*0+4*1+2*0+1*0
• Excess -3 : 0111 : BCD+3 = 0100 + 3 = 0111
• 84-2-1: 0100 = 8*0+4*1+2*0+1*0

2.BCD

• 185 = (0001 1000 0101)BCD
• (a3,a2,a1,a0)BCD = 8a3+4a2+2a1+1a0
• BCD編碼並不是self-complementing code，這使得BCD雖然是最直覺的編碼方式，但在某些情形仍需要其他三種補足
• Self Compleementing

3.Gray Code

• 優勢：確保一次只有一個位元改變，使得充放電(可以想做0與1之間的轉換)較少也較省功耗

 設計數位系統必須考慮三樣要素：cost,speed,power，必須要在三者間求得平衡

4.ASCII Character Code

• American Standard Code for Information Interchange
• 運用7個組合表示128種字元

5.Unicode

• 2bytes

6.Error Detection/Correction Code

• 傳遞的過程可能發生Error
• 除了要偵測錯誤，還要把錯誤更正回來
• 使用方法 ： Even parity 與 Odd parity
• Even parity : 將原字元插入1，使其共有偶數個1
• 比如說 : 000插入0 （變為000-0，末位為parity），以維持0個（偶數個）1，001則要插入1，來維持2個（偶數個）1
• Odd parity :將原字元插入1，使其共有奇數個1
• 透過此法，能夠得知位元上的錯誤，比如說在傳送中將001-1誤傳為011-1，在Even parity的保護下，我們知道總共只能有偶數個1，從而得知傳送發生錯誤
• 但是，如果錯了很多個bits，parity bit就不太可行了

---

Binary Storage & Register

• Binary Cell

• 2 stable states,1-bit information(0 or1)

•  Register 暫存器

• 是一組binary cell
• 暫存需要處理或output的資料
• 暫存的資料可能有不同的編譯方式，例如01000001可能表示A or 65 or ......
• 其實暫存器就是由一堆邏輯閘構成的電路
• 暫存器是最快但容量最小的記憶體，位於最高的記憶體階層
• 依據暫存器的大小，可將處理器分為32bits與64bits

簡介資料結構與演算法

1.演算法

演算法是指令構成的集合，遵循這些指令能讓程式完成任務。通常演算法包會包含5個原則。

1. 有0~多個輸入資料
2. 至少要有一個結果
3. 每一個指令都要明確不含糊
4. 每一個指令都要是可行的
5. 在有限的步驟後便會結束，不會產生無窮迴圈

第五點也是一個程式跟演算法最大的不同，例如作業系統，除非系統當機，否則它將一直處於等待迴路中，直到有工作來臨。

1-1.以Selectioon sort為例

（ 這個for loop的目的是要找第i小的數字 ） 

for(i=0;i<n;i++){
Examine list[i] to list[i-1] and suppose that the smallist integer at list[min];
Intercange list[i] and list[min]
假設最小值出現於index min中，找到list[min]時，將list[i]與list[min]互換
}

1-2.以Binary Search為例

1. Given a sorted array list with n>=1 distinct integers, figure out if an integer seachnum is in list or not
2. 因為是排序過的陣列，所以利用中位數來進行搜尋，大則往後，小則往前，借此二分(binary)

while (there more integers to check)
{
 middle = (left+right)/2
 if(searchnum < list[middle]
    right  = middle -1;
 else if (search num == list[middle])
    return middle;
 else left = middle +1;
}

1-3.表示方法：

我們常常透過流程圖與虛擬碼來陳述一個演算法的步驟。值得一提的是虛擬碼，他介於口語與程式語法間，既能兼顧設計邏輯又可簡便表達演算法的內容。

2.Recursive Algorithm

• Direct recursion: 自己呼叫自己
• Indirect recursion: A呼叫B,B再呼叫A 

用於在問題本身是遞迴呼叫時（如階乘，費波那契）Recursive 最重要的是要決定跳出條件，以免造成Stack Overflow

3.Data Abstration

3-1簡介Data type

• Data type definition : A data type is a collection of objects and a set of operations that act on those object.
• e.g. int and arithmetic operations
• 程式語言內附的Data type稱為Predefined的Data type，使用者自行定義的則稱User-defined types ，但不是所有程式語言都會讓使用者創造User-defined data type
•  不論是哪一種類型的Data type，Data type都是由Object與Operation構成
• 就資料安全的角度來看，直接外露object給使用者是相當危險的，所以須透過operation處理

3-2 ADT

Definition: An abstract data type is a data type whose specification of the objects an the operations on the objects is separated from the representation of the objects and the implementation of the operations.

• 外漏給使用者看的只有specification，而specification並不一定要完成
• 抽象就是取出事物普遍性的本質，隱藏不必要的細節，只保留了目標必要的信息
• Catagories of function of a data type
• 建構式
• Transformers
• Observers/Reporters