《算法設(shè)計(jì)與分析》教學(xué)大綱

1 算法設(shè)計(jì)與分析 一 說(shuō)明 一 課程性質(zhì) 計(jì)算機(jī)科學(xué)是一種創(chuàng)造性思維活動(dòng) 其教育必須面向設(shè)計(jì) 計(jì)算機(jī)算法設(shè)計(jì)與分 析正是一門(mén)面向設(shè)計(jì) 且處于計(jì)算機(jī)學(xué)科核心地位的教育課程 設(shè)計(jì)一個(gè)高效的程序 不僅需要編程小技巧 更需要合理的數(shù)據(jù)組織和清晰高效的算法 這正是計(jì)算機(jī)科學(xué) 領(lǐng)域里數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)所研究的主要內(nèi)容 二 教學(xué)目的 通過(guò)對(duì)本課程的學(xué)習(xí)與研究 使學(xué)生掌握算法設(shè)計(jì)的主要方法 培養(yǎng)對(duì)算法的計(jì) 算復(fù)雜性正確分析的能力 為獨(dú)立設(shè)計(jì)算法和對(duì)算法復(fù)雜性分析奠定堅(jiān)實(shí)的理論基礎(chǔ) 對(duì)學(xué)生將來(lái)從事計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 系統(tǒng)軟件和應(yīng)用軟件的研究與開(kāi)發(fā)提供一個(gè)廣泛扎 實(shí)的計(jì)算機(jī)算法知識(shí)基礎(chǔ) 三 教學(xué)內(nèi)容 算法及算法復(fù)雜性基本概念 算法描述 有效算法最常用的設(shè)計(jì)策略 遞歸和 分治法 動(dòng)態(tài)規(guī)劃法的設(shè)計(jì)要點(diǎn)與適用性 貪心算法 回溯法和分支限界法 許多難 解問(wèn)題的高效算法 概率算法 以及 NP 完全理論和 NP 難問(wèn)題的近似解法 傳統(tǒng)算 法實(shí)例分析 算法領(lǐng)域研究熱點(diǎn)介紹 四 教學(xué)時(shí)數(shù) 課堂教學(xué) 36 學(xué)時(shí) 實(shí)驗(yàn)部分 36 學(xué)時(shí) 總計(jì) 36 36 2 54 學(xué)時(shí) 五 教學(xué)方式 講授 上機(jī)實(shí)驗(yàn) 課題設(shè)計(jì) 對(duì)每一教學(xué)內(nèi)容 首先介紹一種算法設(shè)計(jì)策略的基本思想 然后從解決計(jì)算機(jī)科 學(xué)和應(yīng)用中的實(shí)際問(wèn)題入手 由簡(jiǎn)到繁地描述幾個(gè)經(jīng)典的精巧算法 同時(shí)對(duì)每個(gè)算法 所需的時(shí)間和空間進(jìn)行分析 使學(xué)生既能學(xué)到一些常用的精巧算法 又能通過(guò)對(duì)算法 設(shè)計(jì)策略的反復(fù)應(yīng)用 牢固掌握這些算法設(shè)計(jì)的基本策略 以期收到融會(huì)貫通之效 在為各種算法設(shè)計(jì)策略選擇用于展示其設(shè)計(jì)思想與技巧的具體應(yīng)用問(wèn)題時(shí) 有意義重 復(fù)選擇某些經(jīng)典問(wèn)題 使學(xué)生能深刻地體會(huì)到一個(gè)問(wèn)題可以用多種設(shè)計(jì)策略求解 同 時(shí)通過(guò)對(duì)解同一問(wèn)題的不同算法的比較 使學(xué)生更容易體會(huì)到每一種具體算法的設(shè)計(jì) 要點(diǎn) 隨著內(nèi)容的逐步展開(kāi) 學(xué)生也將進(jìn)一步感受到綜合應(yīng)用多種設(shè)計(jì)策略可以更有 效地解決問(wèn)題 二 本文 一 課堂教學(xué)部分 第一章 算法概述 教學(xué)要點(diǎn) 算法的基本概念 算法的計(jì)算復(fù)雜性 教學(xué)時(shí)數(shù) 建議 2 學(xué)時(shí) 教學(xué)內(nèi)容 第一節(jié) 算法與程序 0 5 學(xué)時(shí) 掌握算法的概念及特性 2 理解算法與程序的區(qū)別 了解算法的描述方法 第二節(jié) 算法復(fù)雜性分析 1 5 學(xué)時(shí) 掌握算法復(fù)雜性分析的概念 熟練掌握算法時(shí)間復(fù)雜性和空間復(fù)雜性的表示方法及 O 的定義 了解 和 O 的定義 考核要求 識(shí)記相關(guān)概念 領(lǐng)會(huì)復(fù)雜性分析方法 第二章 遞歸與分治策略 教學(xué)要點(diǎn) 遞歸概念 分治策略 遞歸算法設(shè)計(jì) 教學(xué)時(shí)數(shù) 建議 5 學(xué)時(shí) 教學(xué)內(nèi)容 第一節(jié) 遞歸概念 1 學(xué)時(shí) 熟練掌握遞歸概念 說(shuō)明遞歸算法的工作原理 第二節(jié) 分治法的基本思想 0 5 學(xué)時(shí) 熟練掌握分治法的基本思想和一般原則 理解分治算法設(shè)計(jì)模式 掌握分治算法的復(fù)雜性分析方法 第三節(jié) 基與分治策略的遞歸算法設(shè)計(jì) 3 5 學(xué)時(shí) 熟練應(yīng)用分治法設(shè)計(jì)遞歸算法 1 大整數(shù)乘法 0 5 學(xué)時(shí) 2 Strassen 矩陣乘法 0 5 學(xué)時(shí) 3 棋盤(pán)覆蓋 0 5 學(xué)時(shí) 4 歸并排序 0 5 學(xué)時(shí) 5 快速排序 0 5 學(xué)時(shí) 了解分治法所能解決的一些典型問(wèn)題 應(yīng)用遞歸算法復(fù)雜性分析的一般方法分析各種具體算法的復(fù)雜性 考核要求 領(lǐng)會(huì)遞歸與分治的基本概念 應(yīng)用分治策略解決實(shí)際問(wèn)題并設(shè)計(jì)遞歸算法 遞歸算法的復(fù)雜性分析 第三章 動(dòng)態(tài)規(guī)劃 教學(xué)要點(diǎn) 動(dòng)態(tài)規(guī)劃算法的設(shè)計(jì)思想 適用性以及算法的設(shè)計(jì)要點(diǎn) 教學(xué)時(shí)數(shù) 建議 6 學(xué)時(shí) 教學(xué)內(nèi)容 第一節(jié) 動(dòng)態(tài)規(guī)劃算法的基本思想 2 5 學(xué)時(shí) 掌握動(dòng)態(tài)規(guī)劃算法的基本思想 3 理解動(dòng)態(tài)規(guī)劃算法和分治法的異同 熟練掌握用動(dòng)態(tài)規(guī)劃算法求解問(wèn)題的步驟 第二節(jié) 動(dòng)態(tài)規(guī)劃算法的基本要素 1 5 學(xué)時(shí) 熟練掌握用動(dòng)態(tài)規(guī)劃算法求解問(wèn)題的兩個(gè)重要性質(zhì) 即 最優(yōu)子結(jié)構(gòu)性質(zhì)和子問(wèn)題重疊性質(zhì) 理解自頂向下備忘錄方法的基本思想 第三節(jié) 動(dòng)態(tài)規(guī)劃算法設(shè)計(jì) 2 學(xué)時(shí) 熟練應(yīng)用動(dòng)態(tài)規(guī)劃思想解決具體應(yīng)用問(wèn)題 1 最長(zhǎng)公共子序列 1 學(xué)時(shí) 2 最大子段和 1 學(xué)時(shí) 了解動(dòng)態(tài)規(guī)劃算法所能解決的一些典型問(wèn)題 掌握動(dòng)態(tài)規(guī)劃算法的復(fù)雜性分析方法 考核要求 領(lǐng)會(huì)動(dòng)態(tài)規(guī)劃算法的思想 算法設(shè)計(jì)步驟及基本要素 掌握用動(dòng)態(tài)規(guī)劃思想解決實(shí)際問(wèn)題并設(shè)計(jì)動(dòng)態(tài)規(guī)劃算法 動(dòng)態(tài)規(guī)劃算法復(fù)雜性分析 第四章 貪心算法 教學(xué)要點(diǎn) 貪心算法思想 基本要素及貪心算法設(shè)計(jì) 教學(xué)時(shí)數(shù) 建議 3 學(xué)時(shí) 教學(xué)內(nèi)容 第一節(jié) 貪心算法的基本思想 1 學(xué)時(shí) 理解貪心算法的基本思想 理解局部最優(yōu)和整體最優(yōu)的概念 第二節(jié) 貪心算法的基本要素 1 學(xué)時(shí) 熟練掌握用貪心算法求解問(wèn)題的兩個(gè)重要性質(zhì) 即 貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì) 了解貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)的證明方法 理解貪心算法和動(dòng)態(tài)規(guī)劃算法的差異 第三節(jié) 貪心算法設(shè)計(jì) 1 學(xué)時(shí) 熟練應(yīng)用貪心算法解決具體應(yīng)用問(wèn)題 了解貪心算法可能解決的一些典型問(wèn)題 掌握貪心算法的復(fù)雜性分析方法 考核要求 領(lǐng)會(huì)貪心酸法的思想及基本要素 應(yīng)用貪心算法思想解決實(shí)際問(wèn)題并設(shè)計(jì)貪心算法 貪心算法復(fù)雜性分析 第五章 回溯法 教學(xué)要點(diǎn) 回溯放的基本思想及算法框架 遞歸回溯 迭代回溯 回溯算法設(shè)計(jì) 教學(xué)時(shí)數(shù) 4 建議 4 學(xué)時(shí) 教學(xué)內(nèi)容 第一節(jié) 回溯法的算法框架 2 學(xué)時(shí) 理解問(wèn)題的解空間 掌握回溯法的基本思想 熟練掌握回溯法解題的步驟 理解遞歸回溯和迭代回溯 了解子集樹(shù)與排列樹(shù)的概念 第二節(jié) 回溯算法設(shè)計(jì) 2 學(xué)時(shí) 熟練應(yīng)用回溯算法解決具體應(yīng)用問(wèn)題 轉(zhuǎn)載問(wèn)題 了解回溯法解決的一些典型問(wèn)題 掌握回溯算法復(fù)雜性分析方法 考核要求 領(lǐng)會(huì)回溯法的基本思想 識(shí)記用回溯算法解題的步驟 子集樹(shù) 排列樹(shù) 應(yīng)用回溯法解決實(shí)際問(wèn)題并設(shè)計(jì)回溯算法 回溯算法復(fù)雜性分析 第六章 分支界限法 教學(xué)要點(diǎn) 分支界限法基本思想 分支界限法與回溯法的異同 分支界限算法設(shè)計(jì) 教學(xué)時(shí)數(shù) 建議 3 學(xué)時(shí) 教學(xué)內(nèi)容 第一節(jié) 分支界限法的基本思想 1 5 學(xué)時(shí) 掌握分支界限法的基本思想 理解分支界限法與回溯法的異同 理解分支界限法的搜索策略 熟練應(yīng)用剪枝函數(shù)來(lái)加速搜索 第二節(jié) 分支界限法算法設(shè)計(jì) 1 5 學(xué)時(shí) 熟練應(yīng)用分支界限法解決具體應(yīng)用問(wèn)題 單源最短路徑 設(shè)計(jì)和應(yīng)用剪枝函數(shù) 了解分支界限法解決的一些典型問(wèn)題 熟練應(yīng)用隊(duì)列式分支界限法和優(yōu)先隊(duì)列式分支界限法 考核要求 領(lǐng)會(huì)分支界限法的基本思想 應(yīng)用分支界限法設(shè)計(jì)算法 識(shí)記分支界限法與回溯法的異同 第七章 概率算法 教學(xué)要點(diǎn) 數(shù)據(jù)概率算法 蒙特卡羅算法 拉斯維加斯算法 舍伍德算法 各類(lèi)算法的優(yōu)缺點(diǎn) 教學(xué)時(shí)數(shù) 建議 5 學(xué)時(shí) 5 教學(xué)內(nèi)容 第一節(jié) 概率算法的描述 1 學(xué)時(shí) 理解概率算法的基本思想和基本特征 掌握概率算法的分類(lèi) 區(qū)別各種概率算法 了解概率算法的復(fù)雜度 第二節(jié) 數(shù)據(jù)概率算法 1 學(xué)時(shí) 理解數(shù)據(jù)概率算法的內(nèi)涵 掌握數(shù)據(jù)概率算法的設(shè)計(jì) 了解數(shù)據(jù)概率算法求解的一些典型問(wèn)題 第三節(jié) 舍伍德 Sherwood 算法 1 學(xué)時(shí) 理解舍伍德算法的基本思想 了解舍伍德算法的復(fù)雜度 掌握舍伍德算法求解的一些典型問(wèn)題 第四節(jié) 拉斯維加斯 Las Vegas 算法 1 學(xué)時(shí) 理解拉斯維加斯算法的基本思想和基本特征 了解拉斯維加斯算法的復(fù)雜性 掌握拉斯維加斯算法的設(shè)計(jì) 了解拉斯維加斯算法求解的一些經(jīng)典問(wèn)題 第五節(jié) 蒙特卡羅 Moute Carlo 理解蒙特卡羅算法的基本思想 應(yīng)用蒙特卡羅算法解決實(shí)際應(yīng)用問(wèn)題 了解蒙特卡羅算法求解的一些經(jīng)典問(wèn)題 考核要求 領(lǐng)會(huì)各類(lèi)概率算法的基本思想 掌握各類(lèi)概率算法的設(shè)計(jì) 識(shí)記各類(lèi)概率算法的優(yōu)缺點(diǎn) 第八章 NP 完全性的理論 教學(xué)要點(diǎn) P 類(lèi)與 NP 類(lèi)問(wèn)題 NP 完全問(wèn)題 典型的 NP 完全問(wèn)題 教學(xué)時(shí)數(shù) 建議 5 學(xué)時(shí) 教學(xué)內(nèi)容 第一節(jié) 計(jì)算模型 1 5 學(xué)時(shí) 理解三個(gè)重要的計(jì)算模型 即 隨機(jī)存取和 RAM 隨機(jī)存取存儲(chǔ)程序機(jī) RASP 圖靈機(jī) 第二節(jié) P 類(lèi)與 NP 類(lèi)問(wèn)題 1 學(xué)時(shí) 理解 易 解和 難 解問(wèn)題的概念 掌握非確定圖靈機(jī) DNTM 模型及其時(shí)間復(fù)雜度 理解 P 類(lèi)與 NP 類(lèi)語(yǔ)言 理解多項(xiàng)式時(shí)間驗(yàn)證的概念 理解 COOK 定理的內(nèi)涵及其重要性 第三節(jié) 典型的 NP 完全問(wèn)題 1 學(xué)時(shí) 6 理解一些典型的 NP 完全問(wèn)題 了解典型的 NP 完全問(wèn)題的證明 考核要求 領(lǐng)會(huì)三個(gè)重點(diǎn)的計(jì)算模型 領(lǐng)會(huì) P 類(lèi)與 NP 類(lèi)問(wèn)題 NP 完全問(wèn)題的概念 設(shè)計(jì) RAM 和 RASP 程序 識(shí)記一些典型的 NP 完全問(wèn)題 第九章 近似算法 教學(xué)要點(diǎn) NP 完全問(wèn)題有數(shù)近似算法的設(shè)計(jì)與分析方法 教學(xué)時(shí)數(shù) 建議 2 學(xué)時(shí) 教學(xué)內(nèi)容 第一節(jié) 近似算法 1 學(xué)時(shí) 理解近似算法的思想的應(yīng)用范圍 理解近似算法的性能 第二節(jié) 近似算法設(shè)計(jì) 1 學(xué)時(shí) 掌握近似算法的設(shè)計(jì)與分析方法 了解近似算法求解的一些典型問(wèn)題 考核要求 領(lǐng)會(huì)近似算法的設(shè)計(jì)與分析方法 二 實(shí)驗(yàn)部分 1 基本要求 1 熟練操作有關(guān) C JAVA 編程環(huán)境 2 運(yùn)用理論部分介紹的各類(lèi)算法設(shè)計(jì)思想在相關(guān)環(huán)境下設(shè)計(jì) 編寫(xiě) 調(diào)試和運(yùn)行 求解實(shí)際問(wèn)題的程序 2 項(xiàng)目總表 序號(hào) 實(shí)驗(yàn)項(xiàng)目名稱(chēng) 學(xué)時(shí) 項(xiàng)目類(lèi)別 項(xiàng)目類(lèi)型 1 熟悉 C 或 JAVA 編程的環(huán)境 2 基礎(chǔ) 必做 2 排列問(wèn)題 2 設(shè)計(jì) 必做 3 棋盤(pán)覆蓋問(wèn)題 2 設(shè)計(jì) 必做 4 用棧模擬遞歸 消去算法 Quick sort 中的遞歸 2 綜合 必做 5 Sarassen 矩陣乘法 2 設(shè)計(jì) 選做 6 矩陣連乘問(wèn)題 動(dòng)態(tài)和備忘錄 2 設(shè)計(jì) 必做 7 圖象壓縮 2 設(shè)計(jì) 必做 8 找硬幣 遞歸算法 動(dòng)態(tài)規(guī)劃算法 貪心算法 4 綜合 必做 9 活動(dòng)安排問(wèn)題 2 設(shè)計(jì) 必做 10 哈夫曼編碼 2 設(shè)計(jì) 必做 11 多機(jī)調(diào)度問(wèn)題 2 設(shè)計(jì) 選做 7 注 必做項(xiàng)目數(shù) 17 個(gè) 選做項(xiàng)目數(shù) 6 個(gè) 3 實(shí)驗(yàn)內(nèi)容及其基本要求 見(jiàn)實(shí)驗(yàn)教學(xué)大綱 4 考核要求 熟練應(yīng)用 C 或 JAVA 編程環(huán)境 綜合分析各類(lèi)應(yīng)用問(wèn)題并設(shè)計(jì)相應(yīng)算法 編寫(xiě) 調(diào)試 運(yùn)行程序 以求解相應(yīng)問(wèn)題 各實(shí)驗(yàn)項(xiàng)目實(shí)驗(yàn)報(bào)告 三 參考書(shū)目 1 王嘵東 編著 計(jì)算機(jī)算法設(shè)計(jì)與分析 電子工業(yè)出版社 2001 年 11 月第一版 2 陳增武 編著 算法設(shè)計(jì)與分析 浙江大學(xué)出版社 1994 年 8 月第一版 3 Sara Baase Computer Algorithms Introduction to Design and Analysis Second edition Addison Wesley 1988 本課程使用教具和現(xiàn)代教育技術(shù)的指導(dǎo)性意見(jiàn) 微型計(jì)算機(jī) C 編程環(huán)境 JAVA 編程環(huán)境 序號(hào) 實(shí)驗(yàn)項(xiàng)目名稱(chēng) 學(xué)時(shí) 項(xiàng)目類(lèi)別 項(xiàng)目類(lèi)型 12 多會(huì)場(chǎng)多活動(dòng)安排問(wèn)題 2 綜合 選做 13 裝載問(wèn)題 2 設(shè)計(jì) 必做 14 批處理作業(yè)調(diào)度問(wèn)題 2 設(shè)計(jì) 選做 15 圖的 M 著色問(wèn)題 2 設(shè)計(jì) 必做 16 運(yùn)動(dòng)員最佳配對(duì)問(wèn)題 2 設(shè)計(jì) 選做 17 布線(xiàn)問(wèn)題 2 設(shè)計(jì) 必做 18 裝載問(wèn)題 2 設(shè)計(jì) 必做 19 最大團(tuán)問(wèn)題 2 設(shè)計(jì) 選做 20 用隨機(jī)投點(diǎn)法計(jì)算 值 2 設(shè)計(jì) 必做 21 線(xiàn)性時(shí)間選擇 Sherwood 算法 2 設(shè)計(jì) 必做 22 n 后問(wèn)題 Las Vegas 算法 2 設(shè)計(jì) 必做 23 矩陣互逆問(wèn)題 Monte Carlo 算法 2 設(shè)計(jì) 必做