Ped學記: 公開課

顯示具有 公開課 標籤的文章。顯示所有文章

2017年9月9日星期六

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

Ped隨手摘

如何評斷演算法表現
會受機器等其他因素影響
1. 計算執行時間
2. 執行的數量
相關指標
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
主要先抓三種情境 best、worst、average
1. 因為表現會被輸入資料影響所以才需區分情境
2. 分析通常最重視 average 有時為了預期最壞的情況會注意worst比較少注意 best的情境
演算法主要issue
1. 運算結果正確
2. 效能
loop須注意三個屬性

precoditions
1. 進入前的狀況
loop invariants
1. 在loop中不會改變
Termination condition

最後停止loop的條件

2017年6月18日星期日

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

Ped隨手摘

演算法表示法
1. Flowchart (流程圖)
  1. 太複雜的演算法用流程圖難以表達需要靠自己簡化
2. Pseudocode (P不發音) 虛擬碼
  1. 介於自然語言和程式語言之前，不用嚴謹的語法，主要用來表達想法
問題解決
1. 分析、了解問題後才有辦法去提出並執行解決計畫，最後再去評估這個解法是否正確與能否用以解其他問題
2. 老師特別強調分析問題
3. 通常需要 top-down 和 bottom-up 並行
迴圈
1. 包含三個必要部分
  1. 迴圈進行前的初始化
  2. 測試條件是否符合繼續的條件
  3. 更改某參數以確定迴圈會結束
插入排序法未排序資料一次一個，跟排序好的新陣列中每個值比較，比未排序大的值往下移一個位置，最後會多一個洞放置新資料
二分搜尋法先拿中間值和目標值比較，較大的話只要搜尋下半部，較小則搜尋上半部，可節省搜尋時間
遞迴
1. 終止條件需寫在最前面
2. 由於遞迴會不斷呼叫自己，迴圈的速度會比遞迴快很多，如果可以用迴圈解的話可以考慮使用迴圈
演算法重要技巧

divide and conquer (D&C)
1. 先把問題切分成需多子問題，再一個個解決，二分搜尋法即是此種方式
2. 每個子問題是獨立的，並不會互相影相
3. top down
dynamic programming (DP)

一樣會先切分許多子問題，各子問題間的結果會互相影響，並產生最後的結果，最短路徑問題即可用此方式解
bottom up

2017年6月13日星期二

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

Ped隨手摘

XML 現在的瀏覽器大多可以解讀
伺服器與客戶端
1. 通常圖形運算多在客戶端、資料運算則較多在伺服器端
2. 客戶端
  1. Java applets、Flash 需要先安裝
  2. Javascripts
3. 伺服器端
  1. CGI、Servlets(jsp、asp)、PHP
Internet協定

最簡單的四層
1. application 建立訊息並指定要傳送至哪個地址
2. Transport 將訊息切分成許多封包，並在接收時負責將封包組合回原訊息
3. Network 決定要從哪甚麼路線傳送，接收封包後確認本身是否為目的地，不然繼續往下傳送
4. Link 實作傳送與接收封包
5. OSI有更細的七層分別(由此四層再分更細)
藉由 port 區分傳送來的資料避免丟錯應用程式
TCP／IP
1. Transport Layer
  1. TCP(transmission control protocol) 先做一次握手再傳送，適合遠端傳送
  2. UDP(user datagram protocol) 不確認對方是否想收到或是否收到訊息，直接傳送，速度較快，但較不可靠
2. Network Layer
  1. routing 決定為 ip
3. TCP／IP 指的是一整個套件而非兩種通訊協定
安全性
1. 攻擊與防護
  1. Malware 釣魚攻擊偽裝成被使用者信任的來源騙取密碼或植入惡意程式
  2. Denial of service (Dos) 阻斷式攻擊主要靠防火牆擋ip防堵
  3. Spam 垃圾信件
  4. 可以透過可信任的VPN或是proxy連線
公私鑰加密架構

SSL (secure socket layer) 可套用在各種通訊上 ex.sftp、https、ssh
互為反函數：A加密B能解密，B加密A能解密
傳送訊息時用傳送方用接收方的 public key 加密；接收方再用接收方的 private key 解密
數位簽章用以確認是對的人傳送的
1. A先用自己的private加密再用B的public加密；B用自己的private key 解密再用A的public key解密就能確認訊息真的是A傳送的
被信任的第三方 Certificate authority(CA) 簽署過較能確定傳送方 public key 的正確性
非對稱性加密演算法現在常用 RSA
申請憑證流程：(Ped補充)
1. 申請方會先把 public key 和網站基本資料放進CSR(certificate signing request)
2. CA 將public key簽署完後會核發 ceriticate 給申請方
3. 申請方將 ceriticate 作為SSL 的 public key 使用
4. 瀏覽器中會預裝CA的public key通過認証後瀏覽器就會使用此public key加密

2017年6月4日星期日

[公開課閒聊] 計算機概論第八講 Network & Internet - 台大于天立

Ped隨手摘

Scope
1. LAN 區域網路通常會配發虛擬 ip 外界傳輸無法直接傳輸至此ip 需傳輸給 router後再透過他配送訊息
2. MAN 大型區域網路
3. WAN 整個外部網路
Topology
1. 連線型態目前最流行的是 Bus 例如利用 hub 連線的方式，傳出的訊號會廣播給所有的人
2. 不同 topology 通常會有不同協定
協定
1. 協定規定好後並無強制力
2. token ring
  1. 取得 token 的機器才能發言
  2. 只能把訊息與token往同一方向傳遞
3. CSMA/CD
  1. 有線網路使用，發現兩個機器同時要傳輸時會產生一隨機等待時間
4. CSMA/CA
  1. 無線網路使用，偵測到有空的頻道時等待隨機等待時間後再傳輸能夠減少同時間傳輸的機率
  2. 發生碰撞時就重新傳輸
無線 ap (access point)
1. 無線傳輸都是和ap溝通
2. 無線網路標準 IEEE 802.11 (b, g, i, n, ac, ....)
連接網路的機器
1. 以下三個機器不處理協定的轉換
2. repeater
  1. 會把訊號增強
  2. 會將訊號廣播給所有連接中的電腦
  3. 僅能連接兩個分區
3. bridge
  1. 類似repeater 但廣播時會分區廣播
  2. 僅能連接兩個分區
4. switch
  1. 類似 bridge但可連接兩個以上分區
5. router
  1. 能夠處理不同協定間的傳輸
  2. 通常也包含防火牆的功能
溝通模式
1. server-client
  1. 網頁伺服器與瀏覽器
  2. 郵件伺服器
2. p2p (peer-to-peer)
distributed systems 可以透過網路連接可利用 .NET 等framwork 操作
Internet

ICANN 負責管理domain，其會將domain管理權下放給各個 registrar
利用 gateway (通常是router) 與外界連結
ip 透過 ISP(Internet service provider) 配發
domain name 透過 DNS (domain name server) 可查詢對應的 ip

2017年6月3日星期六

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

Ped隨手摘

scheduler 排程
1. 管理 process table
  1. 加入新程序
  2. 移除新程序
  3. 決定哪些程序是 ready 那些是 waiting
dispatcher 分派
1. 執行程式
  1. 利用中斷的方式去切換不同程序的執行
  2. process switch 會讓系統看似一次可以同時處理很多 process 但如果資源實在太不足反而會因為 process switch 浪費過多時間
critical region
1. 當有檔案進入 critical region 時其他程式無法對該檔案同時進行寫入也無法中斷
造成 deadlock 的必要條件
1. 競爭無法分享的資源 ex.需要寫入同一個檔案
2. 逐次要求部分所需資源 ex.一開始需要100bytes 寫完檔案後再要100bytes
3. 將資源分配出去後卻無法強制討回
解決deadlock 如果強制拿走某個程序的資源容易遇到 starvation 的問題
1. starvation 新的程序又繼續拿走資源導致某個程序永不被執行
2. 其中一個解決方法是 aging 一直拿不到資源時優先權會提高
安全性

避免不安全密碼、壞習慣
利用偵測軟體紀錄並分析怪異行為
威脅來源
1. 病毒把自己的程式碼依附在其他的可執行檔上
2. 蠕蟲能夠自行複製傳播
3. 木馬偽裝成其他程式背後多做了非預期的惡意行為
權限分級可有限度的防止惡意行為

2017年5月31日星期三

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

Ped隨手摘

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

process state
1. program counter 程式跑到第幾行
2. general purpose register register進行的動作
3. associated memory cell 記憶體位置
process table

記憶體位置
優先順序
waiting / ready

2017年5月29日星期一

[公開課閒聊] 計算機概論第五講 Data manipulation & operating systems - 台大于天立

Ped隨手摘

pipelining
1. 不同行為用到的電路是不同的，此技術是讓不同行為可以同時進行 ex.fetch、decode、execute 同時跑
parallel 平行運算
1. 名詞解釋
distributed 分散式系統
1. 不同電腦間利用網路同時進行處理不同任務
平行與分散常見的議題
1. data dependency 接下來的計算依賴前一步計算的結果
2. load balancing 工作平均分配
3. synchronization 同步
4. reliability　可靠性
多核心 CPU 因為資料可進行平行運算的比例與不同核心間溝通的時間造成多核心運算加速有個極限
作業系統最大的目的
1. 讓系統可以最大化的使用運算資源，平順的切換不同任務的進行
作業系統類別
1. real-time 即時反應
2. time-sharing and mutitasking 使用者可同時執行多個任務，系統切分每個任務可占用的執行時間
3. multiprocessor 使用多核心平行進行多個任務
user 僅能透過 shell 與 kernel 溝通包含文字與圖形介面

2017年5月27日星期六

[公開課閒聊] 計算機概論第四講 Data manipulation - 台大于天立

Ped隨手摘

電腦的結構
1. Registers (暫存器)
  1. 通常用 SRAM
  2. 常見的有
    1. program counter
      1. 程式在記憶體中目前執行到的位置
    2. instruction register
      1. 從記憶體中取出現在正要執行的指令
2. Bus (連接記憶體和CPU)
3. Motherboard (主機板)
4. CPU
5. Main Memory
CPU
1. ALU Arithmetic/logic unit 算數/邏輯運算元
2. Control unit
Machine Instructions (機械指令/機械碼)
1. 利用指令集操作CPU
2. 組合語言(assembly)和機械指令原則上是一對一的對應
3. 大概會有的指令
  1. LOAD 從記憶體取出資料
  2. STORE 把資料放回主記憶體
  3. I/O 輸入輸出
  4. 加減乘除
  5. SHIFT
    1. logic shift 移動方向的最後一個bit補零
    2. Arithmetic shift 第一個位(正負數) 永遠不動
  6. ROTATE
    1. 移出去的bit捕到領一個方向
  7. 流程控制
    1. JUMP 類似 goto 分為有無條件的JUMP
    2. HALT (停止流程
4. 現在的主流是 CISC (complex instruction set computing)
詳細解釋 Machine Instruction
1. op-code
  1. 告訴CPU要執行甚麼動作
2. Operand
  1. 運算元指定對某個記憶體定址執行 op-code 指定要進行的行為
  2. 用以表達記憶體位置的bytes數會影響能使用的主記憶體大小 (ex.32位元最多能插 4G )
3. 機械碼範例: 356C
  1. 3:store 5:register位置 6C:主記憶體位置
  2. 白話: 把register 位置 5 的資料寫入主記憶體 6C 的位置
  3. 組合語言會轉成較易表示的格式: ex. STORE 5, 6C
高階語言 to Machine Instruction流程範例
1. 寫好的C語言 compile to Object 檔
2. Object 再和 libary link 成為一個 binary(可執行檔)
3. compile 的方式會影響到效能因為有各種翻法
Machine cycle
1. 組成動作
  1. fetch 從主記憶體中將指令取至register
  2. decode 解碼讓CPU知道指令的意思
  3. execute
2. clock ex.3GHz 就是一秒可以跑 3*1000000000 次 machine cycle
I/O 與 CPU 間溝通至 bus 前還有一層 controller 會稍微暫存指令以免太頻繁佔據通道流量
與其他設備通訊

DMA direct memory access
1. 周邊裝置需要存取主記憶體前只需要通過一次CPU的授權
握手 Hand shaking
1. 收到訊息後回傳通知對方已收到
2. 比較嚴格的會先告知對方我要送訊息, 對方允許後才開始傳送
平行 / 序列傳輸
1. 不一定平行傳輸比較快
傳輸單位

bps (bit per second) 注意不是 byte

2017年5月6日星期六

[公開課閒聊] 計算機概論第三講 Data Storage - 台大于天立

Ped隨手摘

二進位小數轉成十進位其實常有誤差存在，十進位常常不是二的倍數
壓縮

非失真壓縮
1. Run-length : 一連串相同的位元在紀錄時就只記連續幾位 ex.11111 連續5bits 為1
2. Frequency-dependent : 常用的碼用比較少位元數代表;少用的用比較長的位元數表示
  1. Huffman code
    1. 固定長度編碼接收端比較好分割，但會比較占空間。
      1. ex.A=00;B=01;C=10
    2. 利用二元樹依出現頻率由短至長編碼有機會會更省空間
      1. ex.A出現9次；B出現3次；C出現2次；D出現1次 A=0;B=10;C=110;D=111
3. dictionary : 將常用的 pattern 用一組較短位元數紀錄他，跟frequecy有點關係
  1. LZW
    1. 不用把字典傳給接收端，因為接收端可用和傳送端同樣的演算法進行解碼
失真壓縮
1. relative/difference : 只記錄有改變的地方
  1. ex.影像、聲音
如果原始資料重複的pattern (redundancy) 很少，反而可能會壓大
Communication errors

壓縮過的資料如果有遺失會導致解碼錯誤
error detection : 可發現傳送的資料有誤，但無法回復
1. check code
  1. 身分證字號
  2. ISBN
2. parity bits
  1. ex.多傳一個 bit 讓資料永遠為奇數，但同時錯兩個 bit 時就沒救了 XD
  2. RAID (磁碟陣列)
error-correcting code (ECC)

repetition code

多傳幾次ex.傳三次 010 因為 0 比較多所以回復成 0
ex.(7,4)Hamming Code

發生錯誤時根據 Hamming distance 還原成最近的

2017年5月3日星期三

[公開課閒聊] 計算機概論第二講 Data Storage - 台大于天立

Ped隨手摘

聲音怎麼紀錄
1. sampling rate
  1. bps(bit per second) 每秒鐘用多少 bits 紀錄聲音檔取決於兩個參數
    1. 取樣率
    2. 紀錄震幅用的 bits 數
2. MIDI
  1. 由音效卡由設定好的聲音再現不同的音效卡呈現出來可能不同
整數
1. Overflow
  1. 兩個正數加起來變一個負數或兩個負數加起來變一個正數
    1. 由於記憶體不足導致計算結果無法表達
小數

fixed-point
1. 直接換算
  1. ex.101.101 = 5又5分之8
floating-point

正負 sign
指數 exponent
假數 mantissa
ex.11010101 = 1(負sign) 101(1指數) 0101(.0101假數) = -(1/4+1/16)x2的一次方 = -5/8
所以轉換成十進位除不盡或記憶體不足的時候會有誤差 => Truncation Error

2017年5月2日星期二

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

Ped隨手摘

為什麼用 2 進位?
1. 方便對應 true false
2. 電器常用電壓作為辨別，比較好判斷 (ex.五伏電壓)
為什麼用 16 進位?
1. 較2進位方便人類表達
2. 2的倍數易於轉換2進位
記憶體位置本身也是以2進位表示，記憶體位置中擺著以 cell 為單位的資料，資料至少以8bits(1byte)為單位
1. 以1D的方式排列
2. 現在幾乎都是隨機存取
  1. 可直接取得目標記憶體位置的資料
主記憶體如DDR等技術都是持續供電以奈米等級的小電容紀錄01，增加容量的方式就是讓電容越排越密，越來越小
硬碟則是用磁性紀錄因為一個檔案會分開存在硬碟的不同位置，將不同位置的資料組合回一個檔案供讀取是buffer常被拿來用做的事，他會一次讀一堆資料後再整理出我們要的丟出來
各式各樣如何用二進位記錄資料說明：

文字

Unicode、ASCII

圖片

BMP、SVG

數字

直接從換算成2進位

訂閱：文章 (Atom)

2017年9月9日 星期六

2017年6月18日 星期日

2017年6月13日 星期二

2017年6月4日 星期日

2017年6月3日 星期六

2017年5月31日 星期三

2017年5月29日 星期一

2017年5月27日 星期六

2017年5月6日 星期六

2017年5月3日 星期三

2017年5月2日 星期二

2017年9月9日星期六

2017年6月18日星期日

2017年6月13日星期二

2017年6月4日星期日

2017年6月3日星期六

2017年5月31日星期三

2017年5月29日星期一

2017年5月27日星期六

2017年5月6日星期六

2017年5月3日星期三

2017年5月2日星期二