改變世界的九大演算法：讓今日電腦無所不能的最強概念
Nine Algorithms That Changed the Future:
The Ingenious Ideas That Drive Today’s Computers
呵呵，其他先進的筆記更值得參考
(我是慶祝4/1自愚愚人的外行人&現代IT文盲補修資訊通識普科)
第1章 引言：讓今日電腦威力無窮的神奇概念
演算法：天才就在彈指間
偉大演算法的條件是什麼？
這些偉大的演算法為什麼重要？
第2章 搜尋引擎的索引：配對與排序
AltaVista：第一個網路規模的配對演算法
把每個網頁內文完整標示索引
古早時代的陽春式索引
依據索引(搜尋關鍵字)，列出相關網頁
=>極度無效率，電腦必須讀遍每個網頁的所有內容
文字─位置技法
標示紀錄每個網頁關鍵字索引的位置=>以讓電腦更有效率的進行片語查詢=>而非大費周章搜尋所有網頁的所有內容，還能縮短相鄰兩個片語的搜尋
排序與相鄰
「瘧疾」「原因」
排序自動會將兩者放在一起
元詞技法
網頁語言HTML
找到有關鍵字的標題文章=>更有效率地找到重點文章
光是標註索引和配對技法還不夠
元詞技法讓AltaVista成為第一代搜尋王
第3章 網頁排序：讓谷歌起飛的技術
PageRank如何將相關的網頁排序？
超連結技法
電腦很會記數-看看每個網頁各有多少外部的連結數
連結數越多(不論褒貶)的網頁，排序越前面
權威性技法
X跟Y的網頁連到Z，Z的權重=X的權重+Y的權重
隨機漫遊技法
網頁間連來連去
用模擬的方式來看每1000次隨機漫遊，各網頁被造訪的次數或百分比
網頁排序的實作
網路垃圾連結和搜尋引擎展開軍備競賽
用漫遊者模擬技術來取代隨機漫遊
第4章 公鑰加密：用明信片寄送祕密
用共同的祕密來加密
設定一個公開的共同祕密
混漆技法
先各選一種個人色，再公開宣布一種公共色，然後製造出公共個人混色，再將對方的公共個人混色拿回來加入自己的個人色。經過這四個步驟就可以製造出兩個人的共同祕密色。
實務上的公鑰加密
第5章 錯誤更正碼：錯誤可以自己修正！
偵錯與改正的必要性
99.9999%的正確率對於電腦不夠好
重複的技法
多傳遞幾次，但不能保證答案正確
如果每次傳遞的錯誤與失真率是50%，要靠傳很多次才能達到所需的可靠度
傳輸200M 的資料1000次不可行
冗餘技法
把數字編碼成字母
1=>One
2=>Two
即便以上字母扭曲，接收者還是可以猜出正確數字
校驗技法
多加上校驗碼，直到收到正確的訊息
階梯式校驗碼幫助偵測兩個以上的錯誤
定點目標技法
e.g., 把16位數字轉換成4*4
行跟列再分別設定校驗碼=>二維校驗
第6章 模式辨識：從經驗中學習
辯識圖像與模式是人工智慧的領域
問題是什麼？
模式辨識就是一種分類的問題
要餵給電腦訓練資料
最近鄰居技法
最相近，不需要餵訓練資料
二十個問題技法：決策樹
透過不斷問問題，好問題可以幫助縮減可能性
神經網路
01之間的判斷靠神經網路來加權判斷與學習調教
第7章 資料壓縮：白吃的午餐
無損失的壓縮：終極的白吃午餐
資料內容很大一部分都是相同的重複
長度編碼、較長的符號編碼用簡表轉換
有損失的壓縮：不是白吃的午餐，但很划算
圖像的壓縮，降低畫素
壓縮演算法的由來
偵錯和壓縮兩者剛好是對立
最適壓縮-霍夫曼編碼
Shannon–Fano coding
第8章 資料庫：追求一致性
資料庫的兩大議題：效率與可靠度
資料庫架構≒有條理的表格
交易與待辦事項清單技法
資料不斷更新，所有更新有如交易事項與代辦事項，要更新資料庫(避免當機、開機之間的落差)，以防止成千上萬使用者造成資料的崩壞與不一致
複製資料庫所用的「準備然後承諾技法」
擁有成千上萬電腦的資料庫，每天都會有些硬碟故障，如何確保資料安全完整？
1.資料副本、異地備援
複本資料庫
2.每天特定時間備份，迴轉交易，確保資料一致
3.第一階段準備(代更新事項)，第二階段承諾(update 資料庫)
關聯式資料庫與虛擬表格技法
用幾個比較小但有相互關聯的表格，會比用一個完整的資料庫來得方便(容量小、更容易更新與維護)
關聯性資料庫就是網路行銷的關鍵
第9章 數位簽章：這軟體到底是誰寫的？
數位的東西一定可以拷貝與複製
如何創造一個不能被拷貝與偽造的簽名？
數位簽章究竟用來做什麼？
簽章=>簽署法律文件、支付款項
數位簽章其實是在別人傳送文件給你之前使用：電腦核對數位簽章
下載軟體與執行某程式的安全性警告、https
書面簽字
銀行透過客戶簽名的字卡來比對是否為偽造
(正確的兩大前提：1.行員的辨識可靠 2.當事人的簽名難以偽造)
上鎖的簽字
數位簽章的第一步是完全捨棄書面簽章，改由上鎖、鑰匙和鎖箱來證明文件的真偽。在這套方法下，每位參與者都有大量的鎖，同一個人的鎖必定是一模一樣。此外，每位參與者的鎖必須互斥，沒有人能製造或取得與別人相同的鎖。最後，這些鎖都附有生物測定感應器（biometric sensor）以確保只能被擁有者上鎖。上述就是所謂的「實體鎖技法」（physical padlock trick）。
數位簽章依賴一個只有簽章者知道的秘密以及被簽章的訊息，這個簽章者是用同一個秘密來簽章他的每個訊息，但是不同的訊息會有不同的簽章。因此，雖然任何人都可拷貝簽章，但卻無關緊要，因為簽章不能被移轉到另一個訊息上，因此光是拷貝並無法完成偽造。
RSA數位簽章
第10章 什麼是可計算的？
程式錯誤、毀壞和軟體的可靠度
透過反證法來判斷
用於分析其他程式的程式
就是應用軟體
電腦的極限給我們的啟示
Church–Turing thesis
第11章 結論：未來會如何呢？
頗具潛力的演算法
偉大的演算法可能失去光彩嗎？
我們學到了什麼？
旅程的結束
師大資工 演算法筆記
尊敬與崇拜的陳鍾誠 老師
用十分鐘 學會《資料結構、演算法和計算理論》
十個真的改變世界的重量級演算法
稍稍能夠體會-為什麼IT/MIS的會覺得EHS的人很笨與迂腐...
因為讀太多沒有條理的法規與太長根顢頇的官員打交道，很難維持理智與智力
真實世界當中的決策，往往流於當下的感覺與衝動，所謂專家智慧與主管經驗的判斷，其實沒有演算的邏輯與準則可言？！...
沒有留言:
張貼留言