算法分析與設(shè)計(jì)前言

算法分析與設(shè)計(jì)前言第一頁，共二十九頁，編輯于2023年，星期三課程簡介《算法設(shè)計(jì)與分析》是計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)一門專業(yè)選修課。通過本課程的學(xué)習(xí)，學(xué)生可以了解計(jì)算機(jī)應(yīng)用中的各種常用算法，掌握設(shè)計(jì)和分析各種算法的基本原理、方法和技巧。能運(yùn)用所學(xué)到的知識熟練地分析各種算法并能指出解決同一問題的各種算法的好壞。第二頁，共二十九頁，編輯于2023年，星期三課程要求了解計(jì)算機(jī)應(yīng)用中的各種常用算法了解評價(jià)算法的準(zhǔn)則和方法掌握設(shè)計(jì)和分析算法的基本原理、方法和技巧提高分析問題和解決問題的能力第三頁，共二十九頁，編輯于2023年，星期三課程內(nèi)容

第一章緒論計(jì)算機(jī)發(fā)展及其與算法的關(guān)系算法分析的原則本書用到的一些符號和術(shù)語第四頁，共二十九頁，編輯于2023年，星期三課程內(nèi)容

第二章動態(tài)規(guī)劃最短路徑問題、最佳原理流動推銷員問題矩陣鏈乘問題最長公共子序列圖的任意兩點(diǎn)間的最短距離整數(shù)規(guī)劃同順序流水作業(yè)的任務(wù)安排問題可靠性問題、設(shè)備更新問題第五頁，共二十九頁，編輯于2023年，星期三課程內(nèi)容

第三章優(yōu)先策略最短樹的Kruskal算法求最短樹的Prim算法求最短路徑的Dijkstra算法文件存儲問題有期限的任務(wù)安排問題第六頁，共二十九頁，編輯于2023年，星期三課程內(nèi)容

第四章Huffman編碼、FFT算法和數(shù)據(jù)壓縮Huffman編碼快速傅里葉變換（FFT）卷積及其應(yīng)用第七頁，共二十九頁，編輯于2023年，星期三課程內(nèi)容

第五章分治策略二分查找整數(shù)乘法矩陣乘積的Strassen算法矩陣乘積的Winograd算法布爾矩陣的乘法問題第八頁，共二十九頁，編輯于2023年，星期三課程內(nèi)容

第六章線性規(guī)劃的分解原理線性規(guī)劃和單純形法簡介Dantzig—Wolfe分解算法第九頁，共二十九頁，編輯于2023年，星期三課程內(nèi)容

第七章最佳二分樹二分樹最佳二分樹第十頁，共二十九頁，編輯于2023年，星期三課程內(nèi)容

第八章內(nèi)存分類法之一分類分類的下界估計(jì)二分插入分類法Shell分類法第十一頁，共二十九頁，編輯于2023年，星期三課程內(nèi)容

第九章內(nèi)存分類法之二遞選分類法二分樹遞選分類法堆集分類法第十二頁，共二十九頁，編輯于2023年，星期三課程內(nèi)容

第十章內(nèi)存分類法之三下溢分類法快速分類法第十三頁，共二十九頁，編輯于2023年，星期三課程內(nèi)容

第十一章內(nèi)存分類法之四歸并分類法Ford—Johnson歸并插入分類法基數(shù)分類法第十四頁，共二十九頁，編輯于2023年，星期三課程內(nèi)容

第十二章求第k個(gè)元素求最小及第二小元素求第k個(gè)元素第十五頁，共二十九頁，編輯于2023年，星期三課程內(nèi)容

第十三章外存分類法外存歸并分類法置換選擇段的構(gòu)造三條帶的外存歸并分類法第十六頁，共二十九頁，編輯于2023年，星期三課程內(nèi)容

第十四章分類網(wǎng)絡(luò)分類網(wǎng)絡(luò)舉例0—1原理歸并網(wǎng)絡(luò)Batcher奇偶?xì)w并網(wǎng)絡(luò)第十七頁，共二十九頁，編輯于2023年，星期三課程內(nèi)容

第十五章查找及均衡樹AVL樹——關(guān)于高度均衡的二分樹關(guān)于高度均衡的二分樹的插入和刪除第十八頁，共二十九頁，編輯于2023年，星期三課程內(nèi)容

第十六章2-3樹和2-3-4樹2—3樹2—3—4樹紅黑樹第十九頁，共二十九頁，編輯于2023年，星期三課程內(nèi)容

第十七章B—樹B—樹概念插入和刪除第二十頁，共二十九頁，編輯于2023年，星期三課程內(nèi)容

第十八章哈希表什么是哈希表哈希函數(shù)的構(gòu)造方法解決沖突的方法哈希算法的分析（線性探測法分析）二重哈希法第二十一頁，共二十九頁，編輯于2023年，星期三課程內(nèi)容

第十九章DFS算法和BFS算法概述DFS算法無向圖的DFS算法有向圖的DFS算法互連通塊問題強(qiáng)連通塊問題BFS算法第二十二頁，共二十九頁，編輯于2023年，星期三課程內(nèi)容

第二十章α—β剪技術(shù)和分支定界法α—β剪技術(shù)分支定界法和流動推銷員問題同順序加工任務(wù)安排問題第二十三頁，共二十九頁，編輯于2023年，星期三課程內(nèi)容

第二十一章整數(shù)規(guī)劃概述0—1規(guī)劃和它的DFS搜索（隱枚舉）解法分支定界法在解整數(shù)規(guī)劃中的應(yīng)用第二十四頁，共二十九頁，編輯于2023年，星期三先修課程數(shù)據(jù)結(jié)構(gòu)程序設(shè)計(jì)第二十五頁，共二十九頁，編輯于2023年，星期三學(xué)時(shí)安排序號 內(nèi)容 學(xué)時(shí)安排

1 緒論 2

2 動態(tài)規(guī)劃6

3 優(yōu)先策略2

4 分治策略2

5Huffman編碼、FFT算法4

6 線性規(guī)劃分解原理4

7最佳二分樹2

8 內(nèi)存分類法之（1一4）8

9 求第k個(gè)元素2

10 外存分類法2

11 分類網(wǎng)絡(luò)2

12 查找及均衡樹等6

13 DFS算法和BFS算法4

14 α-β剪技術(shù)和分支定界法2

15 整數(shù)規(guī)劃2

16復(fù)習(xí)考試2第二十六頁，共二十九頁，編輯于2023年，星期三教材《計(jì)算機(jī)算法導(dǎo)引——設(shè)計(jì)與分析》，盧開澄，清華大學(xué)出版社第二十七頁，共二十九頁，編輯于2023年，星期三主要參考書《算法設(shè)計(jì)和分析》，朱洪等，上?？萍嘉墨I(xiàn)出版社，