第一篇：“算法設(shè)計與分析”課程教學(xué)大綱與教學(xué)規(guī)程

“算法設(shè)計與分析”課程教學(xué)大綱和教學(xué)規(guī)程

1.課程基本信息

課程編號：

課程名稱（中文）：算法設(shè)計與分析

課程名稱（英文）：The design and analysis of algorithms 開課學(xué)期： 見培養(yǎng)方案與教學(xué)計劃 課程類別： 專業(yè)基礎(chǔ)課程

課程學(xué)時數(shù)與學(xué)分： 56學(xué)時（4學(xué)分，不含實驗課時，4學(xué)時/周）

實驗學(xué)時數(shù)與學(xué)分： 28學(xué)時（學(xué)分計算并入計算機科學(xué)實驗課程，4學(xué)時/次/周）先修課程： 高等數(shù)學(xué)或數(shù)學(xué)分析，線性代數(shù)或高等代數(shù)，概率論與數(shù)理統(tǒng)計，離散數(shù)學(xué)，高級語言程序設(shè)計，數(shù)據(jù)結(jié)構(gòu)

教學(xué)形式： 課堂講授 + 課外教學(xué) + 實驗教學(xué)（實驗課程實行單列）使用教材：

張德富，算法設(shè)計與分析，國防工業(yè)出版社，2009,8。教學(xué)參考書：

[1] T.H.Cormen, C.E.Leiserson, R.L.Rivest and C.Stein, Introduction to Algorithms(the second edition)，The MIT Press，2001 該書國內(nèi)已引進(jìn)，見《算法導(dǎo)論（第二版）》（影印版，中文本），高等教育出版社，2003 [2] M.H.Alsuwaiyel，Algorithms Design Techniques and Analysis，World Scientific Publishing Company，1998 M.H.Alsuwaiyel，吳偉昶 等譯，《算法設(shè)計技巧與分析》（中文版），電子工業(yè)出版社，2004 [3] Sartaj Sahni著，汪詩林等譯，《數(shù)據(jù)結(jié)構(gòu)、算法與應(yīng)用--C++語言描述》，機械工業(yè)出版社，2003 [4] 王曉東編著，《計算機算法設(shè)計與分析》，電子工業(yè)出版社，2005 [5] Gilles Brassard, Paul Bratley.《FUNDAMENTALS OF ALGORITHMICS》(算法基礎(chǔ))，清華大學(xué)出版社，2005 注：[1]和[2]兩本書為主要教學(xué)參考書。

大綱制定者： 張德富、趙致琢、蘇 暢（廈門大學(xué)計算機科學(xué)系）大綱審定者： 趙致琢（廈門大學(xué)計算機科學(xué)系）

2．課程性質(zhì)、類別與任務(wù)

“算法設(shè)計與分析”是計算機科學(xué)與技術(shù)專業(yè)一門重點專業(yè)基礎(chǔ)課程，也是學(xué)科核心專業(yè)基礎(chǔ)課程之一，屬于必修課程。本課程主要介紹算法的基礎(chǔ)知識，包括抽象計算模型、算法基本概念、算法復(fù)雜性分析基礎(chǔ)、算法設(shè)計的基本方法、以及算法復(fù)雜性理論基礎(chǔ)。通過本課程的學(xué)習(xí)，要求學(xué)生理解并熟練掌握：了解可支持算法運行的抽象機器計算模型，算法的定義和復(fù)雜性概念，算法設(shè)計的基本技術(shù)方法，包括遞歸與分治法、貪心法、動態(tài)規(guī)劃方法、回溯法、分支限界法以及高級圖論算法等，理解并掌握算法復(fù)雜性的分析方法、NP完全性理論基礎(chǔ)等計算復(fù)雜性的基本知識以及完全性證明概要。通過教學(xué)和實踐，培養(yǎng)學(xué)生運用數(shù)學(xué)工具和方法分析問題和從算法的角度運用數(shù)學(xué)工具解決問題的基本能力，培養(yǎng)學(xué)生設(shè)計算法和分析算法復(fù)雜性的基本能力，訓(xùn)練學(xué)生的邏輯思維能力和想象力，從而使他們能夠正確地分析和評價一個算法，進(jìn)一步設(shè)計出真正有效或更有效的算法，并使之了解算法理論的基礎(chǔ)知識和發(fā)展概況。在教學(xué)中，鼓勵學(xué)生運用算法知識解決各個學(xué)科的實際計算問題，培養(yǎng)學(xué)生初步的獨立開展科研工作的能力和理論聯(lián)系實踐，解決實際問題的能力，同時，為后續(xù)課程以及將來的研究工作提供必要的算法設(shè)計與分析的基礎(chǔ)。

此外，配合實驗課程的教學(xué)，學(xué)生應(yīng)理論聯(lián)系實際，理論指導(dǎo)實踐，通過規(guī)范地完成一系列算法設(shè)計實驗進(jìn)一步鞏固所學(xué)的相關(guān)書本知識，在知識、能力、素質(zhì)上得到進(jìn)一步的提高。

3．課程教學(xué)的基本要求（教學(xué)內(nèi)容和教學(xué)重點）

“算法設(shè)計與分析”內(nèi)容的重點是各種常用的算法設(shè)計方法和復(fù)雜性分析方法，包括遞歸與分治法、貪心法、動態(tài)規(guī)劃方法、回溯法、分支限界法，以及高級圖論算法、時空復(fù)雜性的分析方法、NP完全性理論基礎(chǔ)。課程教學(xué)的基本要求是通過教學(xué)活動，使每一個學(xué)生較好地掌握課程的主要內(nèi)容，同時具備對實際問題應(yīng)用所學(xué)知識設(shè)計出有效算法并編程實現(xiàn)這些算法的能力。課程的教學(xué)內(nèi)容主要包括如下知識點，其中，屬于重點的內(nèi)容用黑體標(biāo)示，今后教學(xué)改革擬增加的內(nèi)容用“{??}”標(biāo)示，部分非重要內(nèi)容用括弧標(biāo)注為“一般了解”： 基本概念：問題;抽象計算模型；算法的概念；算法正確性;算法效率；問題下界 算法的評估：時間復(fù)雜性和空間復(fù)雜性分析；算法的最優(yōu)、最差和平均效率；漸近復(fù)雜性符號和基本效率類型；非遞歸算法的數(shù)學(xué)分析；{概率分析（一般了解）；分?jǐn)偡治觯ㄒ话懔私猓?；算法的?jīng)驗分析；算法可視計算方法}； 遞歸：遞歸設(shè)計；遞歸算法轉(zhuǎn)非遞歸算法；遞歸算法的設(shè)計實例；遞歸算法的數(shù)學(xué)分析，{三種求解遞歸方程的方法}；

分治法：分治法的基本思想；分治法設(shè)計的特點；分治法的時間復(fù)雜性；分治法的應(yīng)用（大整數(shù)乘法和Strassen矩陣乘法；棋盤覆蓋）； 基本的排序算法及其復(fù)雜性分析：插入排序；堆排序；快速排序；排序算法復(fù)雜度分析及其比較（此處的教學(xué)重點在于算法分析，透過算法分析從中深入了解算法的特性，進(jìn)一步揭示設(shè)計更為有效的算法的思路和途徑）； 動態(tài)規(guī)劃方法：動態(tài)規(guī)劃的基本要素（含最優(yōu)性原理）；矩陣連乘問題；0/1背包問題；裝配線的調(diào)度問題；最長公共子序列；

貪心算法：貪心算法的基本要素；背包問題；哈夫曼編碼；活動選擇問題；{貪心算法的理論基礎(chǔ)（一般了解）}；

回溯法：回溯法的基本思想；裝載問題；0/1背包問題；旅行商問題；批處理的作業(yè)調(diào)度問題；n皇后問題；子集合問題；回溯法的效率分析；

分支限界法（分支定界法）：分支限界算法的基本思想；裝載問題；0/1背包問題；旅行商問題；批處理的作業(yè)調(diào)度問題；分支限界法的效率分析；

網(wǎng)絡(luò)與高級圖論算法：最短路徑問題（Prim算法；Kruskal算法；Dijkstra算法；Warshall算法和Floyd算法）；最大流問題（Ford-Fulkerson標(biāo)號算法等）；最小費用最大流問題（最小費用算法等）；{匹配問題及其求解算法}； 問題的復(fù)雜性：NP完全性理論基礎(chǔ)（P類與NP類問題，NP完全性問題及其歸約；NP完全性證明；典型的NP完全問題）；{ 如何求算法復(fù)雜性的下界（一般了解）}。

4．關(guān)于教學(xué)目標(biāo)、教學(xué)內(nèi)容的建議和教學(xué)過程中應(yīng)該注意的事項

算法設(shè)計與分析是計算機科學(xué)的核心問題之一。由于計算機科學(xué)與技術(shù)的大多數(shù)研究都與算法緊密相關(guān)，因此，高起點的算法理論基礎(chǔ)逐步成為了高素質(zhì)計算機科學(xué)與技術(shù)專門人才應(yīng)該具備的必要的理論修養(yǎng)。設(shè)計算法的目的是要解決大量實際問題，對于較復(fù)雜的問題要求能設(shè)計出有效的算法。大量的研究實踐表明，一個問題求解質(zhì)量和效率的高低，主要取決于算法設(shè)計的質(zhì)量。因此，算法設(shè)計與分析的重點是掌握算法的概念和基礎(chǔ)理論，運用數(shù)學(xué)工具分析問題，從計算方法的角度如何給出非數(shù)值計算問題的計算方法、采用算法設(shè)計的常用方法設(shè)計算法，掌握分析和估計算法復(fù)雜性的方法，并特別注意以下幾點：

第一，在介紹算法的基本概念時，應(yīng)該著重介紹計算模型、算法的概念、考察算法的角度和算法評估的標(biāo)準(zhǔn)、復(fù)雜性分析的方法以及算法研究的目標(biāo)與實際問題的關(guān)系；

第二，在介紹一些數(shù)據(jù)結(jié)構(gòu)已經(jīng)學(xué)習(xí)過的排序算法時，不應(yīng)過多強調(diào)算法設(shè)計，而應(yīng)該重點結(jié)合算法分析技術(shù)，用分析的方法評價算法的優(yōu)劣，從分析結(jié)果得到設(shè)計更優(yōu)算法的啟示。在介紹高級的數(shù)據(jù)結(jié)構(gòu)時，重點應(yīng)放在對數(shù)據(jù)結(jié)構(gòu)的復(fù)雜性分析上；

第三，在介紹算法設(shè)計的基本方法（例如分治法、貪心法、動態(tài)規(guī)劃方法、回溯法與分支限界法）時，應(yīng)該通過對大量經(jīng)典問題的算法設(shè)計與分析，使學(xué)生逐漸掌握算法設(shè)計與分析的技巧，并特別注意各種算法的比較分析。例如，遞歸與分治、貪心與動態(tài)規(guī)劃、回溯與分支限界；

第四，在介紹NP完全性理論時，應(yīng)該著重從問題的分類以及各類問題的性質(zhì)、相互關(guān)系入手進(jìn)行研究，揭示問題的本質(zhì)，從而為算法的設(shè)計提供方法指導(dǎo)。另外，應(yīng)該著重掌握問題的轉(zhuǎn)化及NP完全性理論的有關(guān)證明思想；

第五，在介紹線性規(guī)劃問題及其相應(yīng)算法時，應(yīng)該著重介紹該算法的應(yīng)用；

第六，鼓勵教師將自己的研究或最新算法設(shè)計與分析的思想，結(jié)合到教學(xué)過程之中，鼓勵和幫助學(xué)生運用所學(xué)的知識去解決實際問題，掌握理論與實踐相結(jié)合的思想方法。第七，鼓勵教師結(jié)合學(xué)科范型（也稱范式），將學(xué)科方法論的內(nèi)容融入教學(xué)過程之中（對教師暫不作基本要求），以幫助學(xué)生建立與“算法設(shè)計與分析”課程內(nèi)容相關(guān)的科學(xué)的思想方法。

5．課外教學(xué)要求

本課程的課外教學(xué)內(nèi)容和形式主要由學(xué)生閱讀經(jīng)典教材，任課教師輔導(dǎo)、答疑、批改作業(yè)、實踐環(huán)節(jié)等幾部分構(gòu)成。本課程要求學(xué)生在有時間的情況下，盡可能完成教材中所有的習(xí)題。學(xué)生應(yīng)在任課教師的幫助下，認(rèn)真聽課，反復(fù)思考，大量完成作業(yè)，在學(xué)習(xí)中反復(fù)進(jìn)行閱讀、思考、做習(xí)題，通過閱讀、思考、做習(xí)題、分析、聯(lián)想、概括、歸納、總結(jié)等多種有效的方式方法，比較全面、準(zhǔn)確地掌握課程的主要內(nèi)容和教學(xué)重點。

任課教師（包括助教）每周安排1次輔導(dǎo)、答疑，每次2小時。每次輔導(dǎo)、答疑至少應(yīng)有一位教師參加，一般不得合并執(zhí)行。主講教師應(yīng)批改全班學(xué)生作業(yè)量的5%，參加輔導(dǎo)、答疑的次數(shù)不少于總次數(shù)的1/5，以掌握教學(xué)的效果，調(diào)控教學(xué)進(jìn)度。

課程對學(xué)生作業(yè)的質(zhì)量要求是：正確、簡潔、規(guī)范。

要求做題正確，意味著學(xué)生必須掌握基本概念、基本原理、基本方法、基本技術(shù)等課程的基本知識，基本知識不掌握，就很難正確解答問題，這是對學(xué)生知識水平和解決問題能力的考核。要求做題簡潔和規(guī)范，意味著在正確解題的情況下，不應(yīng)該存在“拖泥帶水”和“東拉西扯”的問題，書面表達(dá)簡練、規(guī)范，與教材中例題求解的表述基本一致。這些，正反映出學(xué)生在這方面訓(xùn)練有素，這是對學(xué)生素質(zhì)的考核。

6．課程的實驗教學(xué)

實驗課程將安排一些有代表性的上機實驗單元與本課程相呼應(yīng)，目的是通過實驗讓學(xué)生體會理論與實踐高度統(tǒng)一的學(xué)科特點，進(jìn)一步認(rèn)識理論、抽象、算法設(shè)計等三個過程及其相互關(guān)系，形成對學(xué)科范型更深入的體會和認(rèn)識。它要求學(xué)生從分析問題出發(fā)，利用所學(xué)的算法設(shè)計技術(shù)去解決某一實際問題。通過實驗工作，借助程序設(shè)計語言，掌握運用數(shù)據(jù)結(jié)構(gòu)、算法和程序解決一些實際問題的方法。

學(xué)生應(yīng)按照理論聯(lián)系實際，理論指導(dǎo)實踐的要求，在實際操作中規(guī)范地完成各項實驗。通過實驗工作，借助程序設(shè)計語言，設(shè)計并實現(xiàn)算法，進(jìn)一步掌握運用數(shù)學(xué)工具，分析問題，提出求解方法，設(shè)計算法，分析算法的復(fù)雜性，對算法進(jìn)行科學(xué)的評價等方面得到嚴(yán)格的訓(xùn)練。

實驗教學(xué)按照實驗單元進(jìn)行，一個實驗單元完成后或相近內(nèi)容的一組實驗單元完成后，每一個學(xué)生要撰寫和提交實驗報告。任課教師應(yīng)依據(jù)每一個學(xué)生的實驗報告和完成實驗的情況，在學(xué)期結(jié)束時給出學(xué)生該門課程的學(xué)術(shù)評語和成績，并與四個學(xué)年所有實驗課程評語一起，最終產(chǎn)生對學(xué)生的實踐能力作出綜合評定的學(xué)術(shù)評語與成績。學(xué)術(shù)評語應(yīng)著重從發(fā)展的眼光和視角，考察學(xué)生是否能夠理論聯(lián)系實際，理論指導(dǎo)實踐，按照實驗課程的教學(xué)要求，規(guī)范地完成實驗單元，較好或基本掌握了實驗教學(xué)的內(nèi)容。

在實驗課程單列之前，課程的實踐環(huán)節(jié)擬安排28學(xué)時（實際執(zhí)行7次共7*4=28學(xué)時），教學(xué)內(nèi)容由大綱確定，實驗課程單列之后，實驗考核成績單獨計算，不計入課程考核成績。各實驗單元和內(nèi)容如下：

實驗單元一：用貪心法求解一個具體問題的實驗（程序?qū)崿F(xiàn)）； 實驗單元二：用動態(tài)規(guī)劃方法求解一個具體問題的實驗（程序?qū)崿F(xiàn)）； 實驗單元二：用回溯法求解一個具體問題的實驗（程序?qū)崿F(xiàn)）； 實驗單元四：用分支限界法求解一個具體問題的實驗（程序?qū)崿F(xiàn)）； 實驗單元五：用高級圖論算法求解一個具體問題的實驗（程序?qū)崿F(xiàn)）。

上述五個實驗完成后，每個學(xué)生應(yīng)提交二個實驗報告。前三個實驗完成后提交一個實驗報告，后兩個實驗完成后，提交一個實驗報告。

7．考核的方式方法

課程結(jié)束考核方式： 閉卷考試 課堂考試時間： 3小時（180分鐘）

考試命題： 任課教師命題，教研室分管該課程的負(fù)責(zé)人和分管教學(xué)的系副主任審題； 課程考試的命題內(nèi)容要從大綱的要求出發(fā)，圍繞本課程的教學(xué)內(nèi)容、知識點和教學(xué)要求，著重從知識、能力、素質(zhì)三個方面對學(xué)生進(jìn)行全面的考核，重點考核學(xué)生運用知識解決問題的能力，同時考察學(xué)生的綜合素質(zhì)?？己朔秶鸀槌俗詈笠恢芙虒W(xué)的內(nèi)容外，其他大綱確定的知識點都在考試范圍之內(nèi)，課程考試的試卷命題范圍不得免除期中考試已經(jīng)考過的內(nèi)容。試卷中不少于85%的內(nèi)容應(yīng)來自課程重點內(nèi)容的范圍，不少于10%的內(nèi)容應(yīng)來自課程非重點內(nèi)容的范圍，要求學(xué)生全面復(fù)習(xí)，以達(dá)到系統(tǒng)掌握，全面考核的目的。試卷的題型要力戒避免文科標(biāo)準(zhǔn)化試卷的題型，避免出現(xiàn)簡單概念問答題和簡答題。試卷題目數(shù)量一般為5、6、7題，以優(yōu)秀學(xué)生在全部會做的情況下正常書寫速度能夠在120分鐘內(nèi)完成為宜。試卷題目數(shù)量的減少與全面考核的目的并不矛盾。由于考核的范圍是明確的，只要教師不透露題型和范圍，學(xué)生就必須全面復(fù)習(xí)，這樣，即使題目不覆蓋某些教學(xué)內(nèi)容，也不會影響實際的教學(xué)效果。

隨堂監(jiān)考授權(quán)： 主講教師和助教

期中考試： 由任課教師決定是否安排期中考試，主要用于檢查教學(xué)情況。最后成績計算辦法： 期終考試成績80%+平時成績20%

第二篇：數(shù)據(jù)結(jié)構(gòu)與算法課程教學(xué)大綱

教學(xué)大綱

數(shù)據(jù)結(jié)構(gòu)與算法（Data Structures）

計算機技術(shù)已成為現(xiàn)代化發(fā)展的重要支柱和標(biāo)志，并逐步滲透到人類生活的各個領(lǐng)域。隨著計算機硬件的發(fā)展，對計算機軟件的發(fā)展也提出了越來越高的要求。由于軟件的核心是算法，而算法實際上是對加工數(shù)據(jù)過程的描述，所以研究數(shù)據(jù)結(jié)構(gòu)對提高編程能力和設(shè)計高性能的算法是至關(guān)重要的。

非數(shù)值計算問題的數(shù)學(xué)模型不再是傳統(tǒng)的數(shù)學(xué)方程問題，而是諸如表、樹、圖之類的數(shù)據(jù)結(jié)構(gòu)。因此，簡單地說，數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設(shè)計問題的學(xué)科，主要研究數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和算法。

一、教學(xué)目的與要求---了解數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)；

教學(xué)要求在每章教學(xué)內(nèi)容給出，大體上為三個層次：了解、掌握和熟練掌握。他們的含義大致為：了解是正確理解概念，掌握是學(xué)會所學(xué)知識，熟練掌握就是運用所學(xué)知識解決實際問題。

教學(xué)目的為：了解算法對于程序設(shè)計的重要性 ； 學(xué)習(xí)掌握基本數(shù)據(jù)結(jié)構(gòu)的描述與實現(xiàn)方法，熟練掌握典型數(shù)據(jù)結(jié)構(gòu)及其應(yīng)用算法的設(shè)計。了解算法分析方法。

二、教學(xué)重點與難點--數(shù)據(jù)結(jié)構(gòu)中基本概念和術(shù)語，算法描述和分析方法。

1、鏈表插入、刪除運算的算法。算法時間復(fù)雜度

2、后綴表達(dá)式的算法，數(shù)制的換算

利用本章的基本知識設(shè)計相關(guān)的應(yīng)用問題

3、循環(huán)隊列的特點及判斷溢出的條件

利用隊列的特點設(shè)計相關(guān)的應(yīng)用問題

4、串的模式匹配運算算法

5、二叉樹遍歷算法的設(shè)計

利用二叉樹遍歷算法，解決簡單應(yīng)用問題 哈夫曼樹的算法

6、圖的遍歷

最小生成樹

最短路徑

7、二叉排序樹查找

平衡樹二叉樹

8、堆排序

快速排序 歸并排序

三、教學(xué)方法與手段-充分利用多媒體教學(xué)工具，配合黑板上的教學(xué)內(nèi)容較難部分的算法實現(xiàn)過程演義

四、教學(xué)內(nèi)容、目標(biāo)與學(xué)時分配

教學(xué)內(nèi)容 教學(xué)目標(biāo) 課時分配

1、緒論

數(shù)據(jù)結(jié)構(gòu)的內(nèi)容

邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)

算法和算法分析

2、線性表

線性表的定義與運算

線性表的順序存儲

線性表的鏈?zhǔn)酱鎯?/p>

3、棧

棧的定義與運算

棧存儲和實現(xiàn)

棧的應(yīng)用舉例

4、隊列

隊列的定義與基本運算

隊列的存儲與實現(xiàn)

隊列的應(yīng)用舉例

5、串

串的定義與基本運算

串的表示與實現(xiàn)

串的基本運算

6、樹和二叉樹

樹的定義和術(shù)語

二叉樹樹的基本概念和術(shù)語 遍歷二叉數(shù)和線索二叉樹

二叉樹的轉(zhuǎn)換

二叉樹的應(yīng)用

哈夫曼樹及其應(yīng)用

7、圖

圖的定義和術(shù)語

圖的存儲結(jié)構(gòu)

圖的遍歷算法

圖的連通性

8、查找

查找的基本概念與靜態(tài)查找 動態(tài)查找

哈希表

了解

了解

掌握

熟練掌握順序表存儲地址的計算

掌握單鏈表的結(jié)構(gòu)特點和基本運算

掌握雙鏈表的結(jié)構(gòu)特點和基本運算

掌握棧的定義與運算

掌握棧的存儲與實現(xiàn)

熟練掌握棧的各種實際應(yīng)用

掌握隊列的定義與基本運算

熟練掌握隊列的存儲與實現(xiàn)

掌握循環(huán)隊列的特征和基本運算

了解串的邏輯結(jié)構(gòu)

掌握串的存儲結(jié)構(gòu)

熟練掌握串的基本運算

了解

了解二叉樹

熟練掌握二叉樹定義和存儲結(jié)構(gòu)

了解二叉樹的遍歷算法

掌握

掌握哈夫曼的建立及編碼

了解

了解

熟練掌握

熟練掌握

了解

熟練掌握

了解哈希表與哈希方法

4學(xué)時

1學(xué)時

1學(xué)時

2學(xué)時

8學(xué)時

2學(xué)時

2學(xué)時

4學(xué)時

8學(xué)時

2學(xué)時

2學(xué)時

4學(xué)時

6學(xué)時

2學(xué)時

2學(xué)時

2學(xué)時

6學(xué)時

2學(xué)時

2學(xué)時

2學(xué)時

12學(xué)時

2學(xué)時

2學(xué)時

2學(xué)時

2學(xué)時

2學(xué)時

2學(xué)時

8學(xué)時

2學(xué)時

2學(xué)時

2學(xué)時

2學(xué)時

8學(xué)時

4學(xué)時

2學(xué)時

2學(xué)時

9、排序

12學(xué)時 插入排序

熟練掌握基本思想

3學(xué)時 快速排序

了解各種內(nèi)部排序方法和特點

3學(xué)時 選擇排序

掌握

2學(xué)時 各種排序方法比較

掌握

2學(xué)時

實驗內(nèi)容 實驗?zāi)繕?biāo) 課時分配 算法編程實驗：

1、用指針方式編寫程序 復(fù)習(xí)C（C++）語言指針、結(jié)構(gòu)體等的用法

2、對單鏈表進(jìn)行遍歷

鏈表的描述與操作實現(xiàn)

3、棧及其操作

描述方法及操作

4、編寫串子系統(tǒng)1 串的特點及順序定長存儲、操作、查找

5、編寫串子系統(tǒng) 2 串的特點及順序定長存儲、操作、查找

6、編寫樹子系統(tǒng)1 二叉樹的特點及存儲方式、創(chuàng)建、顯示、遍歷等

7、編寫樹子系統(tǒng)2 二叉樹的特點及存儲方式、創(chuàng)建、顯示、遍歷等

8、圖子系統(tǒng)

圖的鄰接矩陣的存儲、遍歷、廣度/深度優(yōu)先搜索

9、查找子系統(tǒng)

理解查找基本算法、平均查找長度、靜態(tài)、動態(tài)查找等

五、考試范圍與題型

1、考試范圍與分?jǐn)?shù)比例

1)緒論

12% 2)線性表

17% 3)棧

7% 4)隊列

6% 5)串

4% 6)樹和二叉樹

14% 7)圖

15% 8)查找

4% 9)排序

21%

2、考試題型與分?jǐn)?shù)比例

1)名詞解釋

18% 2)判斷對錯

16% 3)填空

16% 4)單項選擇

18% 5)應(yīng)用

32%

六、教材與參考資料

1、教材： 實用數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)（譚浩強）中國鐵道出版社

2、參考資料： 數(shù)據(jù)結(jié)構(gòu)（嚴(yán)蔚敏）清華大學(xué)出版社

數(shù)據(jù)結(jié)構(gòu)實用教程（徐孝凱）清華大學(xué)出版社

（撰寫人：

，審核人： 2學(xué)時 2學(xué)時 2學(xué)時 2學(xué)時 2學(xué)時 2學(xué)時 2學(xué)時 2學(xué)時 2學(xué)時）

第三篇：算法設(shè)計與分析課程論文

“卓越工程師教育培養(yǎng)計劃”(簡稱卓越計劃)旨在培養(yǎng)一批創(chuàng)新能力強、適應(yīng)經(jīng)濟社會發(fā)展需要的高質(zhì)量工程技術(shù)人才。在南通大學(xué)計算機科學(xué)與技術(shù)學(xué)院制定的軟件工程專業(yè)卓越工程師的培養(yǎng)計劃中，算法設(shè)計與分析被設(shè)置為一門核心必修課程。通過該門課程的系統(tǒng)授課，重點培養(yǎng)學(xué)生的計算機問題求解能力，該能力是軟件工程專業(yè)學(xué)生成長為卓越工程師必備的一項核心競爭力。一個典型的計算機問題的求解一般需要經(jīng)歷5個階段:①問題的分析和建模;②算法設(shè)計方法和相應(yīng)數(shù)據(jù)結(jié)構(gòu)的選擇;③算法的實現(xiàn);④算法的正確性證明和復(fù)雜度分析;⑤算法實現(xiàn)的優(yōu)化等。

經(jīng)過多輪的教學(xué)實踐發(fā)現(xiàn)，學(xué)生之間水平參差不齊是教學(xué)過程中面臨的最大問題。隨著高校招生規(guī)模的不斷增大，不同學(xué)生之間在基礎(chǔ)知識、智力水平、興趣愛好、學(xué)習(xí)動機和學(xué)習(xí)方法上存在較大的差異性。相同的教學(xué)內(nèi)容，對于一些基礎(chǔ)較好的學(xué)生來說理解難度不大，但對于一些基礎(chǔ)較弱的學(xué)生來說，則難以理解。因此，如何尊重學(xué)生個性差異、發(fā)展學(xué)生個性特長，在考慮學(xué)生整體發(fā)展的同時兼顧學(xué)生的個性特長發(fā)展，從而最終提高各個層次學(xué)生的綜合素質(zhì)是算法設(shè)計與分析課程的教學(xué)改革實踐中需要重點關(guān)注的問題。

通過多次與學(xué)生的深入交流發(fā)現(xiàn)，學(xué)生在這門課程的學(xué)習(xí)過程中面臨如下問題:

1）課程教學(xué)內(nèi)容難度高。課程需要學(xué)生掌握常見的算法設(shè)計策略，如分治法、動態(tài)規(guī)劃法和貪婪法等，對設(shè)計出的算法能進(jìn)行正確性證明和復(fù)雜度分析。很多知識點抽象層次高，需要學(xué)生具備一定的數(shù)學(xué)分析能力，同時，通常算法內(nèi)部邏輯比較復(fù)雜，因此需要學(xué)生具備較強的編程功底。筆者在講授這些知識點時，均假設(shè)學(xué)生具備一定的數(shù)學(xué)分析能力和編程基礎(chǔ)，但實際情況卻不容樂觀，很多學(xué)生在大一和大二的時候并未重視相關(guān)課程的學(xué)習(xí)，很多知識點都已經(jīng)還給授課老師，在課堂上需要花費一定時間幫助學(xué)生回憶這些知識點。同時，部分學(xué)生因編程經(jīng)驗較為匾乏，難以順利地將偽代碼轉(zhuǎn)化成可運行的程序代碼。

2)學(xué)生問題求解能力弱。為輔助學(xué)生對知識點的理解，授課老師一般在實例選擇時均采用一些經(jīng)典實例，例如歸并排序、最小生成樹等。這些問題在一些預(yù)修課程(例如高級程序設(shè)計語言或數(shù)據(jù)結(jié)構(gòu))中均進(jìn)行過講解，因此理解起來難度不大。但是，學(xué)生在上機實踐時，面對老師布置的新問題，卻很難將學(xué)到的知識進(jìn)行靈活運用，難以選擇合理的算法設(shè)計策略，并借助熟悉的高級編程語言去解決。

3)學(xué)生自主學(xué)習(xí)意識薄弱。該門課程本身課時較少(僅有犯學(xué)時)，其中8學(xué)時為上機實踐，在剩余的24學(xué)時內(nèi)，僅能講授基本的算法設(shè)計與分析策略。學(xué)生即使了解常見的算法設(shè)計與分析方法，但現(xiàn)實生活中問題千變?nèi)f化，更需要學(xué)生靈活使用學(xué)到的知識。因此，要提高學(xué)習(xí)效果和實踐能力，需要學(xué)生在課外花費更多時間，閱讀相關(guān)資料和進(jìn)行大量編碼。但是，授課過程中發(fā)現(xiàn)，真正能夠完成自主學(xué)習(xí)的學(xué)生并不多。一方面，很多學(xué)生長期受應(yīng)試教育的影響，習(xí)慣于填鴨式的教學(xué)模式，同時，學(xué)習(xí)時具有較強的功利性，很多學(xué)生普遍有應(yīng)付考試和及格萬歲的思想，有的學(xué)生甚至為了應(yīng)付老師的作業(yè)檢查，大量抄襲作業(yè)，僅做一些表面上的修改來敷衍了事。另一方面，即使有少量同學(xué)對新知識比較好奇，愿意自己去積極探索，但在選擇相關(guān)經(jīng)典資料時經(jīng)驗不足、效率較低，因此，需要有經(jīng)驗的老師進(jìn)行有效引導(dǎo)。

目前高校很多教室都配有多媒體設(shè)備，造成大部分專業(yè)課程均采用多媒體課件方式進(jìn)行授課。多媒體課件雖然具有豐富的表現(xiàn)力、良好的交互性和較高的共享性，但與其他核心專業(yè)課程相比，算法設(shè)計與分析課程的理論程度更高，數(shù)學(xué)推導(dǎo)較多，因此筆者認(rèn)為，采用板書為主的教學(xué)方式可能會效果更好。為驗證該推測，對Leiserson教授和Demaine教授開設(shè)的麻省理工學(xué)院公開課的在線視頻進(jìn)行分析，發(fā)現(xiàn)他們在授課時，絕大部分教學(xué)內(nèi)容均采用板書方式進(jìn)行講解，通過在黑板上一步一步地推導(dǎo)，在一些關(guān)鍵節(jié)點上與學(xué)生充分交互，使得學(xué)生可以更好地掌握算法設(shè)計與分析過程中的一些重要技巧。筆者在實際教學(xué)中通過精心設(shè)計板書，取得了較好的課堂效果。

綜上所述，在學(xué)生水平參差不齊的情況下，針對算法課程教學(xué)中存在的問題，提出了一系列教學(xué)改革措施以提高不同層次學(xué)生的計算機問題求解能力。其中將教學(xué)問題與教學(xué)改革措施的對應(yīng)關(guān)系，以及教學(xué)改革措施與不同層次學(xué)生的對應(yīng)關(guān)系進(jìn)行總結(jié)。而且具備良好的交叉學(xué)科基礎(chǔ)和文化底蘊，能培養(yǎng)出滿足市場需要的復(fù)合型人才。

如何使相關(guān)專業(yè)的教育教學(xué)滿足將來ICT產(chǎn)業(yè)的發(fā)展是個相當(dāng)復(fù)雜的問題，希望筆者提出的一些改進(jìn)措施能對信息科學(xué)相關(guān)專業(yè)的工程教育具有參考意義，并對其他領(lǐng)域也有借鑒之處。

第四篇：“算法設(shè)計與分析”課程教學(xué)方法探究（精選）

“算法設(shè)計與分析”課程教學(xué)方法探究

摘要：該文分析了算法設(shè)計與分析課程教學(xué)和學(xué)生學(xué)習(xí)時存在的問題，根據(jù)近幾年積累的教學(xué)經(jīng)驗，提出了一些教學(xué)方法的建議，如互動式教學(xué)，板書和多媒體相結(jié)合，重視上機練習(xí)以及考核方式的改革。

關(guān)鍵詞：計算機；算法設(shè)計與分析；教學(xué)方法

中圖分類號：TP311 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2015）08-0102-02

21世紀(jì)以來，計算機的普及極大地改變了人們的生活。目前，各行業(yè)、各領(lǐng)域都廣泛采用了計算機信息技術(shù)，并由此產(chǎn)生出設(shè)計并開發(fā)各種應(yīng)用軟件的需求。為了以最小的成本、最快的速度、最好的質(zhì)量開發(fā)出應(yīng)用軟件，就必須掌握并能設(shè)計出高效的算法。算法分析與設(shè)計是一門理論性與實踐性兼顧的課程，是計算機科學(xué)與技術(shù)專業(yè)的一門很重要的專業(yè)課，該課程在整個教學(xué)體系中占有非常重要的地位。通過對計算機算法系統(tǒng)的學(xué)習(xí)與研究，理解和掌握算法設(shè)計的主要方法，培養(yǎng)對算法的計算復(fù)雜性進(jìn)行正確分析的能力，為獨立地設(shè)計算法和對給定算法進(jìn)行復(fù)雜性分析奠定堅實的理論基礎(chǔ)[1]。

該課程不像其他記憶性的課程，它重在理解并能應(yīng)用到實際中，是一門集應(yīng)用性、實踐性及創(chuàng)新性為一體的綜合性課程。再加上這門課程相對枯燥、難度大，因此，對于很多教師來說，要想上好這門課程，成了一個很大的挑戰(zhàn)。該課程要求教師要有扎實的數(shù)學(xué)和數(shù)據(jù)結(jié)構(gòu)理論基礎(chǔ)，還要有編程和科研經(jīng)歷，還要結(jié)合本課程的特點，采用適當(dāng)?shù)慕虒W(xué)方法，才能使得學(xué)生把枯燥，難學(xué)的算法真正學(xué)會，并應(yīng)用到以后的開發(fā)實踐中。

本文根據(jù)筆者的教學(xué)經(jīng)驗，總結(jié)了一些教學(xué)方法，包括互動式教學(xué)，板書和多媒體相結(jié)合以及考核方式的改革等。算法課程教學(xué)及學(xué)生學(xué)習(xí)存在的問題

現(xiàn)在，算法設(shè)計與分析課程在教學(xué)和學(xué)生學(xué)習(xí)方面都存在著問題，經(jīng)過分析總結(jié)如下：

1）該課程難度較大：算法設(shè)計與分析課程中介紹的都是數(shù)學(xué)或計算機專業(yè)領(lǐng)域的經(jīng)典算法，例如動態(tài)規(guī)劃和分支限界法。單純的算法思想比較抽象，課程本身難度較大，容易使學(xué)生對該門課程產(chǎn)生恐懼心理。

2）學(xué)生不感興趣：現(xiàn)在大多數(shù)學(xué)生功利性比較強，學(xué)習(xí)一門課程時，希望它馬上就能應(yīng)用到實際中。比如學(xué)習(xí)了靜態(tài)網(wǎng)頁設(shè)計就可以做網(wǎng)站，學(xué)習(xí)了asp、jsp等動態(tài)網(wǎng)頁設(shè)計就可以開發(fā)系統(tǒng)。學(xué)會了開發(fā)網(wǎng)站和系統(tǒng)，就可以找到工作。所以學(xué)生對這些課程很感興趣。剛才提到的課程都是立竿見影，學(xué)完后都知道最終的目的，而算法設(shè)計與分析課程則不同。算法設(shè)計與分析課程屬于高層次的課程，各種編程語言是它的先修課程。沒有編程基礎(chǔ)，沒有開發(fā)經(jīng)驗，談?wù)撍惴ň拖喈?dāng)于紙上談兵。因此，學(xué)生學(xué)習(xí)算法設(shè)計與分析課程時，他們感覺不能立即用上，甚至覺得與以后找工作沒有太大關(guān)系。這種心理導(dǎo)致學(xué)生對該課程不感興趣，緊緊抱著混學(xué)分的思想去學(xué)習(xí)，給教師授課帶來了很大的困難。

3）考核方式不太合理：目前，在大多數(shù)高校中針對算法設(shè)計與分析課程采用的考核方式和其他課程一樣，總成績=試卷成績*70%+平時成績*30%。這里的平時成績包括作業(yè)，考勤和課堂表現(xiàn)。這種考核方式只能反映出學(xué)生對理論知識的掌握程度，但無法考核出學(xué)生對知識的真正應(yīng)用能力。采用這種傳統(tǒng)的考核方式檢驗學(xué)生是否能把算法思想應(yīng)用到編程中，無法學(xué)以致用。

2教學(xué)方法探討

近年來，本人一直教授該門課程，現(xiàn)將自己教學(xué)過程中摸索的教學(xué)經(jīng)驗以及教學(xué)改革建議進(jìn)行總結(jié)，希望能對廣大教師有所幫助。

2.1互動式教學(xué)

講授算法課程過程中，由于該門課程具有很強的邏輯性和抽象性，并且要求有較好的數(shù)學(xué)基礎(chǔ)，很容易形成教師向?qū)W生的單向傳輸教學(xué)。這種情況下，課堂教學(xué)枯燥無味，學(xué)生沒有興趣去思考和回答教師的問題，以至于形成課堂氣氛死氣沉沉，教師自問自答的局面。

在講課過程中，教師應(yīng)時刻注意和學(xué)生的互動?；邮浇虒W(xué)可以變傳統(tǒng)教學(xué)中的單向傳輸式教學(xué)為雙向互動式，這樣可以提高學(xué)生學(xué)習(xí)該門課程的興趣。興趣是最好的老師，只有學(xué)生產(chǎn)生了興趣，才能更好的掌握算法知識并應(yīng)用到實際中。

教師實現(xiàn)互動式教學(xué)的方法有很多種，比如可以通過提問的方式。這就要求教師在備課時下功夫，而不是簡單的備課本上的知識點，而是吃透每一個知識點，然后在相應(yīng)的知識點上為學(xué)生設(shè)置相應(yīng)的思考方向，提出問題，充分調(diào)動學(xué)生的積極性，讓學(xué)生參與到課堂中來。同時，學(xué)生也會在枯燥的理論知識中尋找到樂趣。

2.2傳統(tǒng)的板書教學(xué)和多媒體教學(xué)相結(jié)合，齊頭并進(jìn)

目前大多數(shù)高校計算機類的課程基本都使用多媒體進(jìn)行教學(xué)。傳統(tǒng)的黑板教學(xué)和多媒體教學(xué)各有利弊，我們應(yīng)根據(jù)教學(xué)內(nèi)容的需要，揚長避短，選擇適當(dāng)?shù)慕虒W(xué)手段，而不是因多媒體的方便性，將單純的將黑板教學(xué)摒棄。在講解算法課程過程中，更是需要兩者的結(jié)合，才能收到良好的課堂教學(xué)效果。

采用多媒體教學(xué)的好處是可以加大課堂信息量，使得講課更加形象生動。在講解算法課程第2章中的插入排序，選擇排序，歸并排序時，就可以采用多媒體教學(xué)中視頻教學(xué)。三種排序算法很抽象，單純的靠講述加上板書教學(xué)，學(xué)生很難掌握三種排序的算法思想，并且容易混淆。本人在講解該部分內(nèi)容時，從網(wǎng)上找到了真人以民族舞蹈形式來表現(xiàn)各種計算機排序算法的工作原理的視頻。首先口頭介紹某種排序的算法思想，然后在學(xué)生對此排序有初步了解的基礎(chǔ)上，讓其觀看相應(yīng)的視頻，使得學(xué)生在輕松快樂的氛圍中掌握了排序算法，收到了很好的教學(xué)效果。

有些情況下，掌握某些經(jīng)典算法的核心思想需要教師采用傳統(tǒng)的黑板教學(xué)，一步一步帶著學(xué)生去推導(dǎo)，最終得到答案。如果此時采用ppt課件進(jìn)行教學(xué)，就會加快講課的進(jìn)度，向下翻一頁可能答案就會直接出來，沒有給學(xué)生充分多的思考時間，沒有在學(xué)生腦中留下深刻的印象。比如講解棋盤覆蓋問題時（如圖1，圖2），如果采用板書教學(xué)，一步一步去演示覆蓋的過程，學(xué)生的思路經(jīng)歷了從有到無的過程，在循序漸進(jìn)中掌握了知識。整個推導(dǎo)過程學(xué)生如同細(xì)細(xì)咀嚼了一個蘋果，不僅嘗到了味道，也吸收了營養(yǎng)。

2.3 重視上機練習(xí)

教室課堂上，教師向?qū)W生講授的是算法的基本思想。算法僅僅靠掌握理論知識是不夠的，必須把它應(yīng)用到編程中，才能真正去領(lǐng)會算法的思想和靈魂。脫離計算機和編程去談?wù)撍惴ň腿缤埳险劚遣磺袑嶋H的。

在教學(xué)過程中，教師至少應(yīng)把1/3的課程分給上機實驗課，只有給學(xué)生充足的上機時間，才可以將算法的思想應(yīng)到實際中。當(dāng)然，作為教師必須努力找一些難度合適的題目，讓學(xué)生在實驗課上完成，將教室課堂上學(xué)的理論知識有所應(yīng)用。通過上機實際操練，促進(jìn)學(xué)生真正掌握算法的精髓。

2.4考核方式改革

本文前面已經(jīng)分析過現(xiàn)在算法課程大多數(shù)學(xué)校采用的是以紙質(zhì)試卷為主的考核方式算作期末成績，其實這種考核方式和課程的性質(zhì)是互相矛盾的。算法課程是理論和實踐都很重要的一門課程，傳統(tǒng)的考核方式只能考查學(xué)生對理論知識的掌握程度。

本人對算法課程采用如下考核方式：

除常規(guī)期末試卷成績外，實驗成績占的比例為40%，加大了實驗成績所占的比例。這樣可以增強學(xué)生對實驗上機課的重視程度，上機實驗時，學(xué)生會比較認(rèn)真，有助于他們能將算法的思想應(yīng)用編程中，培養(yǎng)學(xué)生的動手和實踐能力。

3總結(jié)

筆者結(jié)合近幾年的課堂教學(xué)情況，分析了算法課程教學(xué)存在的問題，并針對這些問題提出了一些教學(xué)方法。當(dāng)然這些方法還需要進(jìn)一步的完善，進(jìn)而使算法課程的教學(xué)質(zhì)量能得到很大的提高。

參考文獻(xiàn)：

[1] 李涵.“算法分析與設(shè)計”課程改革和實踐[J].中國電力教育，2010（16）：74-75.[2] 王曉東.計算機算法設(shè)計與分析[M].北京：電子工業(yè)出版社，2008.[3] 劉波“.算法設(shè)計與分析”教學(xué)探討[J].高等理科教育，2007（4）：78-80.[4] 余祥宣，崔國華，鄒海明.計算機算法基礎(chǔ)[M].武漢：華中科技大學(xué)出版社，2006.[5]馬健.啟發(fā)式教學(xué)法在課堂教學(xué)中的應(yīng)用[J].中國電子教育，2008（3）：68-71.

第五篇：算法設(shè)計與分析課程的心得體會

《算法設(shè)計與分析》課程的心得體會

以最少的成本、最快的速度、最好的質(zhì)量開發(fā)出合適各種各樣應(yīng)用需求的軟件，必須遵循軟件工程的原則，設(shè)計出高效率的程序。一個高效的程序不僅需要編程技巧，更需要合理的數(shù)據(jù)組織和清晰高效的算法。這正是計算機科學(xué)領(lǐng)域里數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計所研究的主要內(nèi)容。一些著名的計算機科學(xué)家認(rèn)為，算法是一種創(chuàng)造性思維活動，并且處于計算機科學(xué)與技術(shù)學(xué)科的核心。

在計算機軟件專業(yè)中算法分析與設(shè)計是一門非常重要的課程，很多人為它如癡如醉。很多問題的解決，程序的編寫都要依賴它，在軟件還是面向過程的階段，就有程序=算法+數(shù)據(jù)結(jié)構(gòu)這個公式。算法的學(xué)習(xí)對于培養(yǎng)一個人的邏輯思維能力是有極大幫助的，它可以培養(yǎng)我們養(yǎng)成思考分析問題，解決問題的能力。

如果一個算法有缺陷，或不適合某個問題，執(zhí)行這個算法將不會解決這個問題。不同的算法可能用不同的時間、空間或效率來完成同樣的任務(wù)。一個算法的優(yōu)劣可以用空間復(fù)雜性和時間復(fù)雜度來衡量。算法可以使用自然語言、偽代碼、流程圖等多種不同的方法來描述。

計算機系統(tǒng)中的操作系統(tǒng)、語言編譯系統(tǒng)、數(shù)據(jù)庫管理系統(tǒng)以及各種各樣的計算機應(yīng)用系統(tǒng)中的軟件，都必須使用具體的算法來實現(xiàn)。

算法設(shè)計與分析是計算機科學(xué)與技術(shù)的一個核心問題。因此，學(xué)習(xí)算法無疑會增強自己的競爭力，提高自己的修為，為自己增彩。

那么，什么是算法呢？算法是指解決問題的方法或過程。算法滿足四個性質(zhì)，即輸入、輸出、確定性和有限性。為了了解算法，這個學(xué)期馬老師帶我們走進(jìn)了算法的世界。

馬老師這學(xué)期提出不少實際的問題，以及解決問題的算法。我在此只說比較記憶深刻的問題，即0-1背包的問題。

0-1背包問題可以描述為：給定一組物品，每種物品都有自己的重量和價格，在限定的總重量內(nèi)，我們?nèi)绾芜x擇，才能使得物品的總價格最高。問題的名稱來源于如何選擇最合適的物品放置于給定背包中。

首先，0-1背包問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)和子問題重疊性質(zhì)，適于采用動態(tài)規(guī)劃方法求解。動態(tài)規(guī)劃算法與分治法類似，其基本思想是將待求解問題分解成若干個子問題，然后從這些子問題的解得到原問題的解。與分治法不同的是，用動態(tài)規(guī)劃法求解的問題，經(jīng)分解得到的子問題往往不是互相獨立的，若用分治法解這類問題，則分解得到的子問題數(shù)目太多，以至于最后解決原問題需要耗費過多的時間。動態(tài)規(guī)劃法又和貪婪算法有些一樣，在動態(tài)規(guī)劃中，可將一個問題的解決方案視為一系列決策的結(jié)果。不同的是，在貪婪算法中，每采用一次貪婪準(zhǔn)則便做出一個不可撤回的決策，而在動態(tài)規(guī)劃中，還要考察每個最優(yōu)決策序列中是否包含一個最優(yōu)子序列。

用動態(tài)規(guī)劃法解決問題的思路如下：

最優(yōu)決策序列由最優(yōu)決策子序列組成。假設(shè)f(i,y)表示剩余容量為y，剩余物品為i, i+1, ?, n時的最優(yōu)解的值，即：

f(n,y)= Pn,if y≥Wn f(n,y)= 0, if 0≤y≤Wn 和

f(i,y)=max(f(i+1,y),f(i+1,y-Wi)+Pi)y≥Wi f(i,y)=f(i+1,y)0≤y≤Wi 這個方程非常重要，基本上所有跟背包相關(guān)的問題的方程都是由它衍生出來的，所以有必要將它詳細(xì)解釋一下：“將前i件物品放入容量為y的背包中”這個子問題，若只考慮第i件物品的策略（放或不放），那么就可以轉(zhuǎn)化為一個只牽扯前i-1件物品的問題。如果不放第i件物品，那么問題就轉(zhuǎn)化為“前i-1件物品放入容量為y的背包中”，價值為f[i-1][y]；如果放第i件物品，那么問題就轉(zhuǎn)化為“前i-1件物品放入剩下的容量為y-Wi的背包中”，此時能獲得的最大價值就是f[i-1][y-Wi]再加上通過放入第i件物品獲得的價值Pi。

用貪心算法解決問題的基本思路如下：

由所有解元素組合成問題的一個可行解；從問題的某一個初始解出發(fā)逐步逼近給定的目標(biāo)，以盡可能快的地求得更好的解。當(dāng)達(dá)到某算法中的某一步不能再繼續(xù)前進(jìn)時，算法停止。

實現(xiàn)該算法的過程： 從問題的某一初始解出發(fā)；while 能朝給定總目標(biāo)前進(jìn)一步do求出可行解的一個解元素；

該算法存在問題：首先不能保證求得的最后解是最佳的；其次不能用來求最大或最小解問題，并且只能求滿足某些約束條件的可行解的范圍。

回溯法是一個既帶有系統(tǒng)性又帶有跳躍性的的搜索算法。所以0-1背包問題也可以用回溯法解決。其基本思路是可先將物品依其單位重量價值從大到小排序，此后只要順序考察各物品即可，這是為了便于計算上界。在實現(xiàn)時，由bound計算當(dāng)前結(jié)點處的上界。在搜索解空間樹時，只要其左兒子節(jié)點是一個可行結(jié)點，搜索就進(jìn)入左子樹，在右子樹中有可能包含最優(yōu)解是才進(jìn)入右子樹搜索。否則將右子樹剪去。

當(dāng)然0-1背包問題還有許多的解決方案，此處就不一一列出。不過通過0-1背包問題，我深刻體會到算法的魅力，體會到同一個問題用不同的方法解決的妙處。學(xué)無止境，《算法設(shè)計與分析》僅僅是我學(xué)習(xí)算法知識入門課，我不會停下腳步，在此之后我依然會努力學(xué)習(xí)算法知識。