[公開課閒聊] 計算機概論第十一講 Algorithm - 台大 于天立

Ped隨手摘

1. 如何評斷演算法表現
2. 會受機器等其他因素影響
   1. 計算執行時間
   2. 執行的數量
3. 相關指標
   1. Big-O
      1. f(n) 屬於 O(g(n)) f(n) upper bound 不會超過 big O 
      2. 指數為n總是比多項式為n來的大 ex.n100次方 屬於(=) O(2n次方)   computer science在這裡常把屬於寫成=
      3. 只在意n極大時的是否能bound住
         1. 不在意n小的時候的表現? n如何算小該如何定義? n很大的時候Big-O仍然比f(n)表現好嗎?
   2. Big-Omega
      1. f(n) 屬於 O(g(n)) f(n) lower bound 不會超過 big Omega
   3. Big-Theta
      1. f(n)既是Big-O又是Big-Omega
4. 主要先抓三種情境 best、worst、average
   1. 因為表現會被輸入資料影響所以才需區分情境
   2. 分析通常最重視 average 有時為了預期最壞的情況會注意worst比較少注意 best的情境
5. 演算法主要issue
   1. 運算結果正確
   2. 效能
6. loop須注意三個屬性
1. precoditions
   1. 進入前的狀況
2. loop invariants
   1. 在loop中不會改變
3. Termination condition
1. 最後停止loop的條件

[公開課閒聊] 計算機概論第六講 Operating systems - 台大 于天立

Ped隨手摘

1. 作業系統組成部分
   1. file manager
   2. device drivers  驅動程式
   3. memory manger
      1. 包含主記憶體與虛擬記憶體
      2. 當主記憶體不足時會將一些暫時用不到的資料先存到硬碟中
   4. scheduler 
   5. dispatcher
2. linux
   1. 指的只是 kernel 其實不包含 GUI 之類的東西
   2. made by GNU
3. MacOS
   1. base on BSD
4. boot strapping (booting) 含意: 不求人
   1. boot loader 會去把在 ROM 中的作業系統載入到主記憶體中後再將控制權交給作業系統
   2. BIOS可以和 boot loader 溝通
5. process
1. process state
   1. program counter 程式跑到第幾行
   2. general purpose register  register進行的動作
   3. associated memory cell 記憶體位置
2. process table
1. 記憶體位置
2. 優先順序
3. waiting / ready