# 20191031 南山高中資訊班課程 政治大學 碩一 王柏仁 --- ## 今日重點 1. 接續上次計算機組織內容 2. 作業系統概論 3. 動態規劃 (Dynamic Program) --- # 點開 https://bit.ly/nssh_1003 --- # 計算機組織 - 記憶體 - 記憶體階層 - 匯流排 - 同步 與 非同步 --- # 作業系統 - 基本組成元件 - 資源利用 與 死結 ---- # 作業系統 - 記憶體管理方式 - 一般記憶體 - [第十七天 Memory Management(記憶體管理)--上](https://ithelp.ithome.com.tw/articles/10207187) - [第十八天 Memory Management(記憶體管理)--中](https://ithelp.ithome.com.tw/articles/10207475) - [第十九天 Memory Management(記憶體管理)--下](https://ithelp.ithome.com.tw/articles/10207797) ---- # 作業系統 - 記憶體管理方式 - 虛擬記憶體 - [資料-1](https://mropengate.blogspot.com/2015/01/operating-system-ch9-virtual-memory.html) - [資料-2](http://epaper.gotop.com.tw/pdf/aee030300.pdf) - 磁碟及檔案管理 --- # 動態規劃 - 將一個問題分成許多子問題，遞迴求解，最後再由子問題的答案得到原本問題的答案 - 相同的子問題會出現不只一次，將子問題的答案記錄起來 --- # Top Down vs Bottom Up --- # Top down : - 只要知道遞迴式就可以了，剩下交給遞迴跑 - code一般為遞迴函式 - 注意遞迴過深 --- # Bottom up : - 子問題一定要比母問題先跑到 (注意迴圈跑法) - code一般為for迴圈 --- # 狀態、狀態轉移 - 條件判斷 - 狀態因條件而改變 --- # 背包客問題 - [範例](https://www.geeksforgeeks.org/0-1-knapsack-problem-dp-10/) - 基本概念： `B[i][j]= max(B[i – 1][j], V[i]+B[i – 1][j – W[i]]` - 樹狀圖 - 建[表格](https://www.youtube.com/watch?v=8LusJS5-AGo) --- # 題目： - [東東爬階梯](https://zerojudge.tw/ShowProblem?problemid=d212) - [DELIVERY DEBACLE](https://zerojudge.tw/ShowProblem?problemid=d054) - [擺花](https://zerojudge.tw/ShowProblem?problemid=a697) - [傳球遊戲](https://zerojudge.tw/ShowProblem?problemid=d105)