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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

算法設(shè)計(jì)與分析是計(jì)算機(jī)科學(xué)與技術(shù)的一個(gè)核心問(wèn)題。因此，學(xué)習(xí)算法無(wú)疑會(huì)增強(qiáng)自己的競(jìng)爭(zhēng)力，提高自己的修為，為自己增彩。

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

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

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

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

用動(dòng)態(tài)規(guī)劃法解決問(wèn)題的思路如下：

最優(yōu)決策序列由最優(yōu)決策子序列組成。假設(shè)f(i,y)表示剩余容量為y，剩余物品為i, i+1, ?, n時(shí)的最優(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 這個(gè)方程非常重要，基本上所有跟背包相關(guān)的問(wèn)題的方程都是由它衍生出來(lái)的，所以有必要將它詳細(xì)解釋一下：“將前i件物品放入容量為y的背包中”這個(gè)子問(wèn)題，若只考慮第i件物品的策略（放或不放），那么就可以轉(zhuǎn)化為一個(gè)只牽扯前i-1件物品的問(wèn)題。如果不放第i件物品，那么問(wèn)題就轉(zhuǎn)化為“前i-1件物品放入容量為y的背包中”，價(jià)值為f[i-1][y]；如果放第i件物品，那么問(wèn)題就轉(zhuǎn)化為“前i-1件物品放入剩下的容量為y-Wi的背包中”，此時(shí)能獲得的最大價(jià)值就是f[i-1][y-Wi]再加上通過(guò)放入第i件物品獲得的價(jià)值Pi。

用貪心算法解決問(wèn)題的基本思路如下：

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

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

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

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

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

第三篇：數(shù)據(jù)結(jié)構(gòu)與算法課程論文

數(shù)據(jù)結(jié)構(gòu)與算法課程小論文

10計(jì)本一班 王曉龍 1004011026 一． 內(nèi)容概要：

如何合理地組織數(shù)據(jù)、高效地處理數(shù)據(jù)是擴(kuò)大計(jì)算機(jī)領(lǐng)域、提高軟件效率的關(guān)鍵。在軟件開(kāi)發(fā)過(guò)程中要求“高效地”組織數(shù)據(jù)和設(shè)計(jì)“好的”算法，并使算法用程序來(lái)實(shí)現(xiàn)，通過(guò)調(diào)試而成為軟件，必須具備數(shù)據(jù)結(jié)構(gòu)領(lǐng)域和算法設(shè)計(jì)領(lǐng)域的專門知識(shí)。

本課程主要學(xué)習(xí)在軟件開(kāi)發(fā)中涉及到的各種常用數(shù)據(jù)結(jié)構(gòu)及其常用的算法，在此基礎(chǔ)上，學(xué)習(xí)如何利用數(shù)據(jù)結(jié)構(gòu)和算法解決一些基本的應(yīng)用問(wèn)題。通過(guò)數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)、基本算法和相關(guān)應(yīng)用問(wèn)題來(lái)介紹其基本知識(shí)和應(yīng)用知識(shí)。

二． 關(guān)鍵字：

數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)、基本算法；算法分析

三． 課程主要內(nèi)容和基本原理：

A．?dāng)?shù)據(jù)結(jié)構(gòu)：

數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)存儲(chǔ)、組織數(shù)據(jù)的方式。數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。通常情況下，精心選擇的數(shù)據(jù)結(jié)構(gòu)可以帶來(lái)更高的運(yùn)行或者存儲(chǔ)效率。數(shù)據(jù)結(jié)構(gòu)往往同高效的檢索算法和索引技術(shù)有關(guān)。

在許多類型的程序的設(shè)計(jì)中，數(shù)據(jù)結(jié)構(gòu)的選擇是一個(gè)基本的設(shè)計(jì)考慮因素。許多大型系統(tǒng)的構(gòu)造經(jīng)驗(yàn)表明，系統(tǒng)實(shí)現(xiàn)的困難程度和系統(tǒng)構(gòu)造的質(zhì)量都嚴(yán)重的依賴于是否選擇了最優(yōu)的數(shù)據(jù)結(jié)構(gòu)。許多時(shí)候，確定了數(shù)據(jù)結(jié)構(gòu)后，算法就容易得到了。有些時(shí)候事情也會(huì)反過(guò)來(lái)，我們根據(jù)特定算法來(lái)選擇數(shù)據(jù)結(jié)構(gòu)與之適應(yīng)。不論哪種情況，選擇合適的數(shù)據(jù)結(jié)構(gòu)都是非常重要的。

（1）.分類：

數(shù)據(jù)元素相互之間的關(guān)系稱為結(jié)構(gòu)。有四類基本結(jié)構(gòu)：集合、線性結(jié)構(gòu)、樹(shù)形結(jié)構(gòu)、圖狀結(jié)構(gòu)（網(wǎng)狀結(jié)構(gòu)）。樹(shù)形結(jié)構(gòu)和圖形結(jié)構(gòu)全稱為非線性結(jié)構(gòu)。集合結(jié)構(gòu)中的數(shù)據(jù)元素除了同屬于一種類型外，別無(wú)其它關(guān)系。線性結(jié)構(gòu)中元素之間存在一對(duì)一關(guān)系，樹(shù)形結(jié)構(gòu)中元素之間存在一對(duì)多關(guān)系，圖形結(jié)構(gòu)中元素之間存在多對(duì)多關(guān)系。在圖形結(jié)構(gòu)中每個(gè)結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)數(shù)和后續(xù)結(jié)點(diǎn)數(shù)可以任意多個(gè)。

數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示（映像）稱為數(shù)據(jù)的物理（存儲(chǔ)）結(jié)構(gòu)。它包括數(shù)據(jù)元素的表示和關(guān)系的表示。數(shù)據(jù)元素之間的關(guān)系有兩種不同的表示方法：順序映象和非順序映象，并由此得到兩種不同的存儲(chǔ)結(jié)構(gòu)：順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。順序存儲(chǔ)方法：它是把邏輯上相鄰的結(jié)點(diǎn)存儲(chǔ)在物理位置相鄰的存儲(chǔ)單元里，結(jié)點(diǎn)間的邏輯關(guān)系由存儲(chǔ)單元的鄰接關(guān)系來(lái)體現(xiàn)，由此得到的存儲(chǔ)表示稱為順序存儲(chǔ)結(jié)構(gòu)。順序存儲(chǔ)結(jié)構(gòu)是一種最基本的存儲(chǔ)表示方法，通常借助于程序設(shè)計(jì)語(yǔ)言中的數(shù)組來(lái)實(shí)現(xiàn)。鏈接存儲(chǔ)方法：它不要求邏輯上相鄰的結(jié)點(diǎn)在物理位置上亦相鄰，結(jié)點(diǎn)間的邏輯關(guān)系是由附加的指針字段表示的。由此得到的存儲(chǔ)表示稱為鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)通常借助于程序設(shè)計(jì)語(yǔ)言中的指針類型來(lái)實(shí)現(xiàn)。索引存儲(chǔ)方法：除建立存儲(chǔ)結(jié)點(diǎn)信息外，還建立附加的索引表來(lái)標(biāo)識(shí)結(jié)點(diǎn)的地址。散列存儲(chǔ)方法：就是根據(jù)結(jié)點(diǎn)的關(guān)鍵字直接計(jì)算出該結(jié)點(diǎn)的存儲(chǔ)地址。

數(shù)據(jù)結(jié)構(gòu)中，邏輯上（邏輯結(jié)構(gòu)：數(shù)據(jù)元素之間的邏輯關(guān)系）可以把數(shù)據(jù)結(jié)構(gòu)分成線性結(jié)構(gòu)和非線性結(jié)構(gòu)。線性結(jié)構(gòu)的順序存儲(chǔ)結(jié)構(gòu)是一種隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)，線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是一種順序存取的存儲(chǔ)結(jié)構(gòu)。線性表若采用鏈?zhǔn)酱鎯?chǔ)表示時(shí)所有結(jié)點(diǎn)之間的存儲(chǔ)單元地址可連續(xù)可不連續(xù)。邏輯結(jié)構(gòu)與數(shù)據(jù)元素本身的形式、內(nèi)容、相對(duì)位置、所含結(jié)點(diǎn)個(gè)數(shù)都無(wú)關(guān)。（2）.四類基本結(jié)構(gòu)：

⑴集合結(jié)構(gòu)。該結(jié)構(gòu)的數(shù)據(jù)元素間的關(guān)系是“屬于同一個(gè)集合”。⑵線性結(jié)構(gòu)。該結(jié)構(gòu)的數(shù)據(jù)元素之間存在著一對(duì)一的關(guān)系。⑶樹(shù)型結(jié)構(gòu)。該結(jié)構(gòu)的數(shù)據(jù)元素之間存在著一對(duì)多的關(guān)系。

⑷圖形結(jié)構(gòu)。該結(jié)構(gòu)的數(shù)據(jù)元素之間存在著多對(duì)多的關(guān)系，也稱網(wǎng)狀結(jié)構(gòu)。從上面所介紹的數(shù)據(jù)結(jié)構(gòu)的概念中可以知道，一個(gè)數(shù)據(jù)結(jié)構(gòu)有兩個(gè)要素。一個(gè)是數(shù)據(jù)元素的集合，另一個(gè)是關(guān)系的集合。在形式上，數(shù)據(jù)結(jié)構(gòu)通常可以采用一個(gè)二元組來(lái)表示。

（3）.常用的數(shù)據(jù)結(jié)構(gòu)：

a.數(shù)組： 在程序設(shè)計(jì)中，為了處理方便，把具有相同類型的若干變量按有序的形式組織起來(lái)。這些按序排列的同類數(shù)據(jù)元素的集合稱為數(shù)組。在C語(yǔ)言中，數(shù)組屬于構(gòu)造數(shù)據(jù)類型。一個(gè)數(shù)組可以分解為多個(gè)數(shù)組元素，這些數(shù)組元素可以是基本數(shù)據(jù)類型或是構(gòu)造類型。因此按數(shù)組元素的類型不同，數(shù)組又可分為數(shù)值數(shù)組、字符數(shù)組、指針數(shù)組、結(jié)構(gòu)數(shù)組等各種類別。b.棧：

是只能在某一端插入和刪除的特殊線性表。它按照先進(jìn)后出的原則存儲(chǔ)數(shù)據(jù)，先進(jìn)入的數(shù)據(jù)被壓入棧底，最后的數(shù)據(jù)在棧頂，需要讀數(shù)據(jù)的時(shí)候從棧頂開(kāi)始彈出數(shù)據(jù)（最后一個(gè)數(shù)據(jù)被第一個(gè)讀出來(lái)）。c.隊(duì)列：

一種特殊的線性表，它只允許在表的前端（front）進(jìn)行刪除操作，而在表的后端（rear）進(jìn)行插入操作。進(jìn)行插入操作的端稱為隊(duì)尾，進(jìn)行刪除操作的端稱為隊(duì)頭。隊(duì)列中沒(méi)有元素時(shí)，稱為空隊(duì)列。d.鏈表：

是一種物理存儲(chǔ)單元上非連續(xù)、非順序的存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過(guò)鏈表中的指針鏈接次序?qū)崿F(xiàn)的。鏈表由一系列結(jié)點(diǎn)（鏈表中每一個(gè)元素稱為結(jié)點(diǎn)）組成，結(jié)點(diǎn)可以在運(yùn)行時(shí)動(dòng)態(tài)生成。每個(gè)結(jié)點(diǎn)包括兩個(gè)部分：一個(gè)是存儲(chǔ)數(shù)據(jù)元素的數(shù)據(jù)域，另一個(gè)是存儲(chǔ)下一個(gè)結(jié)點(diǎn)地址的指針域。e.樹(shù)：

是包含n（n>0）個(gè)結(jié)點(diǎn)的有窮集合K，且在K中定義了一個(gè)關(guān)系N，N滿足以下條件：

（1）有且僅有一個(gè)結(jié)點(diǎn) k0，他對(duì)于關(guān)系N來(lái)說(shuō)沒(méi)有前驅(qū)，稱K0為樹(shù)的根結(jié)點(diǎn)。簡(jiǎn)稱為根（root）。（2）除K0外，k中的每個(gè)結(jié)點(diǎn)，對(duì)于關(guān)系N來(lái)說(shuō)有且僅有一個(gè)前驅(qū)。

（3）K中各結(jié)點(diǎn)，對(duì)關(guān)系N來(lái)說(shuō)可以有m個(gè)后繼（m>=0）。f.圖：

圖是由結(jié)點(diǎn)的有窮集合V和邊的集合E組成。其中，為了與樹(shù)形結(jié)構(gòu)加以區(qū)別，在圖結(jié)構(gòu)中常常將結(jié)點(diǎn)稱為頂點(diǎn)，邊是頂點(diǎn)的有序偶對(duì)，若兩個(gè)頂點(diǎn)之間存在一條邊，就表示這兩個(gè)頂點(diǎn)具有相鄰關(guān)系。g.堆： 在計(jì)算機(jī)科學(xué)中，堆是一種特殊的樹(shù)形數(shù)據(jù)結(jié)構(gòu)，每個(gè)結(jié)點(diǎn)都有一個(gè)值。通常我們所說(shuō)的堆的數(shù)據(jù)結(jié)構(gòu)，是指二叉堆。堆的特點(diǎn)是根結(jié)點(diǎn)的值最小（或最大），且根結(jié)點(diǎn)的兩個(gè)子樹(shù)也是一個(gè)堆。h.散列表：

若結(jié)構(gòu)中存在關(guān)鍵字和K相等的記錄，則必定在f(K)的存儲(chǔ)位置上。由此，不需比較便可直接取得所查記錄。稱這個(gè)對(duì)應(yīng)關(guān)系f為散列函數(shù)(Hash function)，按這個(gè)思想建立的表為散列表。B．算法分析：

算法分析是對(duì)一個(gè)算法需要多少計(jì)算時(shí)間和存儲(chǔ)空間作定量的分析。算法是解題的步驟，可以把算法定義成解一確定類問(wèn)題的任意一種特殊的方法。在計(jì)算機(jī)科學(xué)中，算法要用計(jì)算機(jī)算法語(yǔ)言描述，算法代表用計(jì)算機(jī)解一類問(wèn)題的精確、有效的方法。算法+數(shù)據(jù)結(jié)構(gòu)=程序，求解一個(gè)給定的可計(jì)算或可解的問(wèn)題，不同的人可以編寫出不同的程序，來(lái)解決同一個(gè)問(wèn)題，這里存在兩個(gè)問(wèn)題：一是與計(jì)算方法密切相關(guān)的算法問(wèn)題；二是程序設(shè)計(jì)的技術(shù)問(wèn)題。算法和程序之間存在密切的關(guān)系。分析算法可以預(yù)測(cè)這一算法適合在什么樣的環(huán)境中有效地運(yùn)行，對(duì)解決同一問(wèn)題的不同算法的有效性作出比較。

四．心得體會(huì)：

在做完這次課程論文后，讓我再次加深了對(duì)數(shù)據(jù)結(jié)構(gòu)與算法的理解，對(duì)數(shù)據(jù)結(jié)構(gòu)的構(gòu)建也有更深層次的體會(huì)。算法的每一次改進(jìn)和提高，都凝聚著人類的智慧和辛勤勞動(dòng)，每一次創(chuàng)新都給人類帶來(lái)了巨大的進(jìn)步。數(shù)據(jù)結(jié)構(gòu)與先進(jìn)的算法能夠合理地組織數(shù)據(jù)、高效地處理數(shù)據(jù)，擴(kuò)大計(jì)算機(jī)的應(yīng)用領(lǐng)域，提高軟件的效率。這充分體現(xiàn)了其重要意義。

五． 參考文獻(xiàn)：

數(shù)據(jù)結(jié)構(gòu)與算法王昆侖，李紅

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

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

1.課程基本信息

課程編號(hào)：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

6．課程的實(shí)驗(yàn)教學(xué)

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

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

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

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

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

上述五個(gè)實(shí)驗(yàn)完成后，每個(gè)學(xué)生應(yīng)提交二個(gè)實(shí)驗(yàn)報(bào)告。前三個(gè)實(shí)驗(yàn)完成后提交一個(gè)實(shí)驗(yàn)報(bào)告，后兩個(gè)實(shí)驗(yàn)完成后，提交一個(gè)實(shí)驗(yàn)報(bào)告。

7．考核的方式方法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2教學(xué)方法探討

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

2.1互動(dòng)式教學(xué)

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

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

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

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

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

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

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

2.3 重視上機(jī)練習(xí)

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

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

2.4考核方式改革

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

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

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

3總結(jié)

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

參考文獻(xiàn)：

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