《算法設(shè)計(jì)》課程實(shí)施大綱

《算法設(shè)計(jì)》課程實(shí)施大綱教學(xué)理念要設(shè)計(jì)一個(gè)簡單易行的正確算法是一件困難的工作，他需要算法的編寫者有獨(dú)到的創(chuàng)新能力，嚴(yán)謹(jǐn)?shù)乃季S能力。所以在教學(xué)過程中就要注重培養(yǎng)學(xué)生這方面的能力。在教學(xué)過程中要圍繞算法設(shè)計(jì)技術(shù)組織素材，對(duì)每種算法技術(shù)選擇多個(gè)典型范例進(jìn)行分析。將直觀性與嚴(yán)謹(jǐn)性完美地結(jié)合起來。每章從實(shí)際問題出發(fā)，經(jīng)過具體、深入、細(xì)致的分析，自然且富有啟發(fā)性地引出相應(yīng)的算法設(shè)計(jì)思想，并對(duì)算法的正確性、復(fù)雜性進(jìn)行恰當(dāng)?shù)姆治觥⒄J(rèn)證。以各種算法設(shè)計(jì)技術(shù)（如貪心法、分治策略、動(dòng)態(tài)規(guī)劃、網(wǎng)絡(luò)流、近似算法、隨機(jī)算法等）為主線來安排教學(xué)內(nèi)容，突出了算法設(shè)計(jì)的思想和分析的基本原則，為從事實(shí)際問題的算法設(shè)計(jì)與分析工作提供清晰的、整體的思路和方法。通過使用豐富的教學(xué)方法，不但深入系統(tǒng)地闡述算法設(shè)計(jì)與分析的理論，而且給出大量的典型范例和參考文獻(xiàn)。以算法為主線來處理算法與數(shù)據(jù)結(jié)構(gòu)的關(guān)系。這種教學(xué)安排突出了算法設(shè)計(jì)的中心思想，避免了與數(shù)據(jù)結(jié)構(gòu)課程在內(nèi)容上的重復(fù)，更加適合于教學(xué)計(jì)劃。使得教學(xué)內(nèi)容由淺入深，由具體到抽象，從算法設(shè)計(jì)技術(shù)與分析方法自然過渡到計(jì)算復(fù)雜性理論，選配大量難度適當(dāng)?shù)木毩?xí)，并給出求解范例。從而達(dá)到相應(yīng)的教學(xué)目標(biāo)。2．課程介紹2.1課程的性質(zhì)計(jì)算機(jī)科學(xué)是一種創(chuàng)造性思維活動(dòng)，其教育必須面向設(shè)計(jì)。計(jì)算機(jī)算法設(shè)計(jì)與分析正是一門面向設(shè)計(jì)，且處于計(jì)算機(jī)學(xué)科核心地位的教育課程。設(shè)計(jì)一個(gè)高效的程序不僅需要編程小技巧，更需要合理的數(shù)據(jù)組織和清晰高效的算法，這正是計(jì)算機(jī)科學(xué)領(lǐng)域里數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)所研究的主要內(nèi)容。算法設(shè)計(jì)這門課程就是通過對(duì)常用的，有代表性的算法的研究，讓學(xué)生理解并且掌握算法設(shè)計(jì)的基本技術(shù)。培養(yǎng)學(xué)生分析算法復(fù)雜度的初步能力，鍛煉學(xué)生的邏輯思維能力和想象能力，讓學(xué)生了解算法理論的發(fā)展。通過該課程的學(xué)習(xí)提高學(xué)生運(yùn)用算法理論解決其它學(xué)科的實(shí)際問題，從而不斷提高學(xué)生的獨(dú)立科研能力以及理論聯(lián)系實(shí)際的動(dòng)手操作能力。2.2課程在學(xué)科專業(yè)結(jié)構(gòu)中的地位、作用“算法設(shè)計(jì)”課程是計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)的核心專業(yè)基礎(chǔ)課之一，在計(jì)算機(jī)專業(yè)人才培養(yǎng)中具有重要的意義。教學(xué)內(nèi)容的難度大，涉及的學(xué)生人數(shù)多。該課程在教學(xué)內(nèi)容、教學(xué)手段、實(shí)驗(yàn)教學(xué)、課程考核、教研教改、師資隊(duì)伍、網(wǎng)絡(luò)資源建設(shè)、師生科研工作等方面已形成了有優(yōu)勢的教學(xué)體系。該課程一直采用國家教育部推薦的優(yōu)秀教材，教學(xué)內(nèi)容豐富。先進(jìn)，主講教師的課堂教學(xué)十分注重理論聯(lián)系實(shí)際，信息量大，重點(diǎn)突出，條理清晰，語言生動(dòng)，互動(dòng)和啟發(fā)性強(qiáng)，運(yùn)用多媒體教學(xué)手段恰當(dāng)，網(wǎng)絡(luò)教學(xué)資源較豐富。課外輔導(dǎo)、答疑、實(shí)驗(yàn)指導(dǎo)、考核和教學(xué)管理規(guī)范，文檔齊全。該課程較重視教學(xué)改革研究，教學(xué)內(nèi)容和考核形式有利于培養(yǎng)學(xué)生的學(xué)習(xí)能力和創(chuàng)新精神?！八惴ㄔO(shè)計(jì)”這門課程的教學(xué)難度大，但課程組的老師能夠以對(duì)學(xué)生高度負(fù)責(zé)的態(tài)度認(rèn)真對(duì)待每一個(gè)教學(xué)環(huán)節(jié)，注重教學(xué)內(nèi)容和教學(xué)方法研究，加強(qiáng)課外輔導(dǎo)和答疑等輔助性教學(xué)環(huán)節(jié)，盡可能及時(shí)解決學(xué)生學(xué)習(xí)中存在的問題，學(xué)生反映好。該教研室還經(jīng)常舉行公開課和教學(xué)評(píng)價(jià)，充分聽取廣大老師的意見，力求對(duì)教學(xué)精益求精。2.3課程的前沿及發(fā)展趨勢當(dāng)今時(shí)代，在純粹科學(xué)研究，通信、交通運(yùn)輸、工業(yè)設(shè)計(jì)和企事業(yè)管理部門，在社會(huì)軍事、政治和商業(yè)的斗爭中涌現(xiàn)出大量的算法問題。若按經(jīng)典的純粹數(shù)學(xué)家們所熟悉的窮舉方法求解，則計(jì)算時(shí)間動(dòng)輒達(dá)到天文數(shù)字，根本沒有實(shí)用價(jià)值。數(shù)學(xué)界許多有經(jīng)驗(yàn)的人認(rèn)為對(duì)于這些問題根本上就不存在完整、精確、而又不是太慢的求解算法?？赡苁沁@個(gè)世紀(jì)最重要的數(shù)學(xué)問題了。算法可以看作是解決問題的一類特殊方法，它不是問題的答案，而是經(jīng)過精確定義的、用來獲得答案的求解過程。因此，無論是否涉及計(jì)算機(jī)，特定的算法設(shè)計(jì)及技術(shù)都可以看作是問題求解的有效策略。著名的計(jì)算機(jī)科學(xué)家史努特是這樣論述這個(gè)問題的：受過良好訓(xùn)練的計(jì)算機(jī)科學(xué)家知道如何處理算法，如何構(gòu)造算法、操作算法、理解算法以及分析算法?，F(xiàn)在設(shè)計(jì)算法，主要是方便編程進(jìn)行運(yùn)算解決實(shí)際問題，因?yàn)殡娔X只會(huì)簡單的運(yùn)算，不轉(zhuǎn)化成它的語言，它無法識(shí)別，從電腦問世以來，各種層出不窮的新電腦的產(chǎn)生，但是不管有多少品牌的電腦，算法始終是靈魂，沒有了程序，沒有了算法，它就是一個(gè)普通的硬件，甚至什么都做不了，現(xiàn)在算法也是越來越復(fù)雜，但是復(fù)雜的算法是建立在簡單的算法基礎(chǔ)之上的，不過就算是最簡單的算法，比如描述輸入、輸出，已經(jīng)是最簡單了，也需要人來編寫算法，而計(jì)算機(jī)自己是無法編寫算法，更不用說轉(zhuǎn)化成程序進(jìn)行運(yùn)算了。如何讓電腦成為真正的智能，這是現(xiàn)在全世界都在關(guān)注的，如果僅僅是移入芯片，讓電腦執(zhí)行各種已經(jīng)設(shè)計(jì)好的程序，按部就班按照人類的思維進(jìn)行運(yùn)算，那也就不算只能，頂多是仿智能，所以，未來算法的走向，是如何能使電腦也會(huì)編寫算法，轉(zhuǎn)化成程序，也就是自動(dòng)思考，解決我們?nèi)祟愄岢龅膯栴}。算法可以看作是解決問題的一類特殊方法，它不是問題的答案，而是經(jīng)過精確定義的、用來獲得答案的求解過程。因此，無論是否涉及計(jì)算機(jī)，特定的算法設(shè)計(jì)及技術(shù)都可以看作是問題求解的有效策略。著名的計(jì)算機(jī)科學(xué)家史努特是這樣論述這個(gè)問題的：受過良好訓(xùn)練的計(jì)算機(jī)科學(xué)家知道如何處理算法，如何構(gòu)造算法、操作算法、理解算法以及分析算法。 2.4學(xué)習(xí)本課程的必要性“計(jì)算機(jī)既是數(shù)學(xué)的創(chuàng)造物,又是數(shù)學(xué)的創(chuàng)造者”,而算法既是計(jì)算機(jī)理論和實(shí)踐的核心,也是數(shù)學(xué)的最基本內(nèi)容之一。甚至有人說,數(shù)學(xué)學(xué)習(xí)的主要作用是形成“算法思維”。算法有著悠久的發(fā)展歷史,中國古代數(shù)學(xué)曾經(jīng)以算法為特色,取得了舉世矚目的輝煌成就。在已經(jīng)逐步進(jìn)入信息化社會(huì)的今天,算法的基本知識(shí)、方法、思想日益融入人們社會(huì)生活的方方面面,已經(jīng)也應(yīng)該成為現(xiàn)代人所應(yīng)具備的一種基本素質(zhì)。算法學(xué)習(xí)有助于我們?nèi)娴睦斫膺\(yùn)算能力很多時(shí)候,人們對(duì)運(yùn)算存在一些誤解,認(rèn)為運(yùn)算就是按照各種運(yùn)算法則進(jìn)行加、減、乘、除,從而學(xué)習(xí)運(yùn)算就是背誦書本中給出的計(jì)算法則,形成一些基本的計(jì)算技巧,也就是說,能夠根據(jù)熟記的法則,迅速的計(jì)算給定式子的正確答案。實(shí)際上,按照算法規(guī)則進(jìn)行邏輯推理而獲得正確結(jié)果僅僅是計(jì)算的很小的一個(gè)方面,更重要的是,在運(yùn)算中構(gòu)造、設(shè)計(jì)、選擇一個(gè)合理的算法,理解相應(yīng)的算理。在算法學(xué)習(xí)中,我們要讓學(xué)生給出一個(gè)問題的不同算法,并比較這些算法的優(yōu)劣,并作出選擇,從而提高效率,而這個(gè)過程才是一個(gè)真正的運(yùn)算過程,因此算法學(xué)習(xí)使得我們更加全面的理解運(yùn)算能力。算法學(xué)習(xí)能夠培養(yǎng)學(xué)生的邏輯思維能力我們常常說數(shù)學(xué)是思維的體操,能夠訓(xùn)練學(xué)生的思維能力。算法作為數(shù)學(xué)的一個(gè)基本內(nèi)容,在培養(yǎng)學(xué)生的邏輯思維能力上能夠發(fā)揮重要的作用。算法是解題方法的精確描述。算法一方面具有具體化、程序化、機(jī)械化的特點(diǎn),同時(shí)又有高度抽象性、概括性和精確性。因此,將解決具體問題的方法整理成算法的過程是一個(gè)條理化,精確化和邏輯化的過程,有助于培養(yǎng)學(xué)生的邏輯思維能力。3．教師簡介4．先修課程數(shù)學(xué)分析、高等代數(shù)、C語言、離散數(shù)學(xué)、程序設(shè)計(jì)、數(shù)據(jù)結(jié)構(gòu)5．課程目標(biāo)5.1知識(shí)與技能方面通過對(duì)本課程的學(xué)習(xí)與研究，使學(xué)生掌握算法設(shè)計(jì)的基本知識(shí)，培養(yǎng)對(duì)算法的計(jì)算復(fù)雜性正確分析的能力，為獨(dú)立設(shè)計(jì)算法和對(duì)算法復(fù)雜性分析奠定堅(jiān)實(shí)的理論基礎(chǔ)，對(duì)學(xué)生將來從事計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)、系統(tǒng)軟件和應(yīng)用軟件的研究與開發(fā)提供一個(gè)廣泛扎實(shí)的計(jì)算機(jī)算法知識(shí)基礎(chǔ)。在剛開始學(xué)習(xí)的時(shí)候就應(yīng)該弄清楚各種變量的定義方法,還要掌握各種類型的輸入、輸出格式。這一步做到后，上機(jī)就沒有多大的問題了。在對(duì)函數(shù)的學(xué)習(xí)過程中，一定要弄明白函數(shù)的作用和具體格式。值得強(qiáng)調(diào)的是在寫循環(huán)程序時(shí)，一定要弄清楚循環(huán)的條件。對(duì)每一個(gè)知識(shí)點(diǎn)，都應(yīng)該立即編出對(duì)應(yīng)的程序，有時(shí)可能還會(huì)有語法錯(cuò)誤，碰到更好的方法也可以試一下，很多時(shí)候你想想代碼怎么寫和你真的寫出來了是有很大的差距的。最終通過認(rèn)真學(xué)習(xí)掌握最基本的知識(shí)點(diǎn)，打好堅(jiān)實(shí)的理論基礎(chǔ)，這一點(diǎn)尤其重要。；另外還要掌握一定的算法設(shè)計(jì)技能，這也是學(xué)習(xí)這門課程的目的。堅(jiān)實(shí)的理論基礎(chǔ)加上靈活的算法技巧才有可能設(shè)計(jì)出可靠有效的算法。5.2過程與方法方面對(duì)每一教學(xué)內(nèi)容，首先介紹一種算法設(shè)計(jì)策略的基本思想，然后從解決計(jì)算機(jī)科學(xué)和應(yīng)用中的實(shí)際問題入手，由簡到繁地描述幾個(gè)經(jīng)典的精巧算法。同時(shí)對(duì)每個(gè)算法所需的時(shí)間和空間進(jìn)行分析，使學(xué)生既能學(xué)到一些常用的精巧算法，又能通過對(duì)算法設(shè)計(jì)策略的反復(fù)應(yīng)用，牢固掌握這些算法設(shè)計(jì)的基本策略，以期收到融會(huì)貫通之效。在為各種算法設(shè)計(jì)策略選擇用于展示其設(shè)計(jì)思想與技巧的具體應(yīng)用問題時(shí)，有意義重復(fù)選擇某些經(jīng)典問題，使學(xué)生能深刻地體會(huì)到一個(gè)問題可以用多種設(shè)計(jì)策略求解。同時(shí)通過對(duì)解同一問題的不同算法的比較，使學(xué)生更容易體會(huì)到每一種具體算法的設(shè)計(jì)要點(diǎn)。隨著內(nèi)容的逐步展開，學(xué)生也將進(jìn)一步感受到綜合應(yīng)用多種設(shè)計(jì)策略可以更有效地解決問題。要寫出一個(gè)好的算法絕不是一蹴而就的事情，它需要不斷的修改不斷的完善，這也是自我能力提高的一個(gè)過程。所以，學(xué)生應(yīng)該認(rèn)真對(duì)待每一個(gè)算法的完成過程，以及它涉及到的不同方法。即使最后的計(jì)算結(jié)果不是那么的理想，但是我們知道之后應(yīng)該如何改進(jìn)，這個(gè)過程需要每一個(gè)算法的設(shè)計(jì)者自己去體會(huì)和領(lǐng)悟，只有這樣才能夠從每一個(gè)算法的設(shè)計(jì)過程中有所收獲有所提高，只有這樣才真正的達(dá)到了教學(xué)的目標(biāo)。5.3情感、態(tài)度與價(jià)值觀方面教師要注重學(xué)生的情感體驗(yàn)和實(shí)踐。課程目標(biāo)中無論是熱愛集體具有責(zé)任感，競爭意識(shí)，團(tuán)結(jié)合作和奉獻(xiàn)精神等，都需要學(xué)生的獨(dú)立思考和生活體驗(yàn)，需要在教學(xué)中不斷創(chuàng)造條件促進(jìn)學(xué)生的實(shí)踐，豐富他們的情感體驗(yàn)，感悟和理解社會(huì)的思想道德價(jià)值要求，逐步形成正確的道德觀和良好的行為習(xí)慣。教師要注意學(xué)生的自主學(xué)習(xí)。學(xué)生只有主動(dòng)地對(duì)教材所涉及到的方方面面內(nèi)容進(jìn)行探究，才能與老師上課所提到的問題產(chǎn)生共鳴，并在經(jīng)過自覺的加工組織后，最終升華至健康積極的價(jià)值觀層面。在教學(xué)中要突出情感、態(tài)度、價(jià)值觀的主導(dǎo)地位，學(xué)生的品德心理的發(fā)展是以認(rèn)知、情感、行為三者為主體的綜合發(fā)展。但是，長期以來我們更多的是看重學(xué)生的認(rèn)知發(fā)展，關(guān)心學(xué)生對(duì)某個(gè)結(jié)論是否記住，記得是否準(zhǔn)確，對(duì)某項(xiàng)技能是否掌握，運(yùn)用得是否得心應(yīng)手，而忽略了對(duì)學(xué)生在認(rèn)知過程中產(chǎn)生的情感體驗(yàn)和正確得價(jià)值觀的形成。造成學(xué)生的學(xué)習(xí)情緒低下，知行不能統(tǒng)一。因此，教師在教學(xué)過程中應(yīng)注重引導(dǎo)和促進(jìn)學(xué)生在知情行方面的和諧發(fā)展，充分發(fā)揮情感和態(tài)度價(jià)值觀的主導(dǎo)作用，備課中首先考慮如何以認(rèn)知的手段達(dá)到情感、態(tài)度、價(jià)值觀的目標(biāo)，做到以情導(dǎo)行。具體來說，就是處理好新教材中的探究園、實(shí)踐與評(píng)價(jià)和心靈導(dǎo)航的關(guān)系，帶領(lǐng)學(xué)生通過活動(dòng)的探究來領(lǐng)會(huì)導(dǎo)航上的知識(shí)點(diǎn)。盡量設(shè)立多種活動(dòng)來激發(fā)學(xué)生的情感體驗(yàn)。教師要通過創(chuàng)設(shè)一定的情景或開展多項(xiàng)活動(dòng)來引起學(xué)生的注意、產(chǎn)生興趣，表示認(rèn)同，愿意接受，同時(shí)引起情緒上的變化，并產(chǎn)生情感上的體驗(yàn)。通過這些活動(dòng)和體驗(yàn)，引起學(xué)生對(duì)所學(xué)內(nèi)容的注意和興趣，產(chǎn)生想學(xué)的需要。值得注意的是，在這一環(huán)節(jié)，教師要善于烘托情感氛圍，選擇恰當(dāng)?shù)囊妆粚W(xué)生接受的切入點(diǎn)。在選擇切入點(diǎn)時(shí)，既要考慮其中具有的豐富情感因素；又要考慮到學(xué)生實(shí)際的心理發(fā)展水平。通過引導(dǎo)學(xué)生自主學(xué)習(xí)，自我探索來內(nèi)化學(xué)生的態(tài)度和價(jià)值觀。學(xué)生在情感體驗(yàn)的過程中，會(huì)伴隨著一些語言和行為上的贊同、反對(duì)等態(tài)度、價(jià)值觀的傾向性，但是這些贊同和反對(duì)還僅僅是一種受情感或情緒的影響而產(chǎn)生的表面的傾向，很容易受他人的言語影響而改變。因此，還需要教師引導(dǎo)他們形成正確的評(píng)價(jià)，并把這種評(píng)價(jià)內(nèi)化成為他們固有的價(jià)值觀。而這種內(nèi)化需要靠學(xué)生自己去探索，不斷深化才能完成。這樣經(jīng)過學(xué)生的自我探索，就把基于情感情緒而產(chǎn)生的態(tài)度價(jià)值觀傾向性，通過有機(jī)合理的整合，不斷深化形成較為穩(wěn)固系統(tǒng)的價(jià)值觀。6．課程內(nèi)容6.1課程的內(nèi)容概要 算法及算法復(fù)雜性基本概念，算法描述，有效算法最常用的設(shè)計(jì)策略——遞歸和分治法，動(dòng)態(tài)規(guī)劃法的設(shè)計(jì)要點(diǎn)與適用性，貪心算法，回溯法和分支限界法，許多難解問題的高效算法——概率算法，以及NP完全理論和NP難問題的近似解法。傳統(tǒng)算法實(shí)例分析，算法領(lǐng)域研究熱點(diǎn)介紹。本課程在學(xué)習(xí)之前，最好具有離散數(shù)學(xué)、程序設(shè)計(jì)、數(shù)據(jù)結(jié)構(gòu)等方面的知識(shí)。什么是算法設(shè)計(jì)，如何進(jìn)行算法設(shè)計(jì)，需要準(zhǔn)備哪些預(yù)備知識(shí)，算法及其重要特性，算法的描述方法以及算法設(shè)計(jì)的一般過程，對(duì)于算法設(shè)計(jì)的概念的掌握程度要求了解，明白應(yīng)該怎么做，怎樣才能設(shè)計(jì)好一個(gè)算法，從學(xué)習(xí)概念學(xué)生可以了解什么是算法設(shè)計(jì)，如何通過分析實(shí)際問題設(shè)計(jì)出優(yōu)良，可操作的高效的算法。在此基礎(chǔ)上通過本課程的學(xué)習(xí)，掌握算法的定義及基本概念、計(jì)算模型和復(fù)雜度的質(zhì)量；為分析算法的復(fù)雜性做準(zhǔn)備，在這個(gè)基礎(chǔ)上，學(xué)習(xí)一些常用的算法設(shè)計(jì)策略，掌握其基本思想和相應(yīng)算法，編制出相應(yīng)程序上機(jī)調(diào)試。6.2教學(xué)重點(diǎn)、難點(diǎn)（1）遞歸的概念；分治法的基本思想；分治法的典型例子，如：二分搜索技術(shù)、大整數(shù)乘法、最接近點(diǎn)對(duì)問題。了解遞歸概念和分治法的基本思想，以及各種典型例子的分治思想，要求可以熟練的編寫出按分治法設(shè)計(jì)的算法問題。（2）矩陣連乘問題；動(dòng)態(tài)規(guī)劃算法的基本要素；動(dòng)態(tài)規(guī)劃法的典型例子，如：最長公共子序列、凸多邊形最優(yōu)三角剖分、圖像壓縮、電路布線、流水作業(yè)調(diào)度、0－1背包問題、最優(yōu)二叉搜索樹。（3）了解動(dòng)態(tài)規(guī)劃的基本思想，以及各種典型例子的動(dòng)態(tài)規(guī)劃思想，要求可以熟練的編寫出按動(dòng)態(tài)低歸設(shè)計(jì)的算法問題?；顒?dòng)安排問題；貪心算法的基本要素；貪心算法的典型例子，如：最優(yōu)裝載、哈夫曼編碼、單源最短路徑、最小生成樹。（4）了解貪心算法的基本思想，以及各種典型例子的貪心算法思想，如:活動(dòng)安排問題，最優(yōu)裝載等。要求可以熟練的編寫出按貪心算法設(shè)計(jì)的算法問題?；厮莘ǖ乃惴蚣?；回溯法的典型例子，如：裝載問題、批處理作業(yè)調(diào)度、符號(hào)三角形問題、n后問題、0－1背包問題、圖的m著色問題、旅行售貨員問題、圓排列問題、電路板排列問題。（5）了解回溯法的基本思想，以及各種典型例子的回溯思想，如：裝載問題，批處理作業(yè)調(diào)度，n后問題等。要求可以熟練的編寫出按回溯法設(shè)計(jì)的算法問題。分支限界法的基本思想；分支限界法的典型例子，如：單源最短路徑問題、裝載問題、布線問題、0－1背包問題、最大團(tuán)問題、旅行售貨員問題、電路板排列問題、批處理作業(yè)調(diào)度。（6）了解分支限界法的基本思想，以及各種典型例子的分支限界法思想，如：單源最短路徑問題、布線問題、0-1背包問題等。要求可以熟練的編寫出按分支限界法設(shè)計(jì)的算法問題。隨機(jī)數(shù)；數(shù)值概率算法；舍伍德算法；拉斯維加斯算法；蒙特卡羅算法。（7）了解隨機(jī)數(shù)與偽隨機(jī)的概念與產(chǎn)生；掌握數(shù)值概率算法，用隨機(jī)投點(diǎn)法計(jì)算∏值、計(jì)算定積分等；掌握舍伍德算法，并用之解決線性時(shí)間選擇和跳躍表等問題；掌握拉斯維加斯算法，并用之解決n后問題和整數(shù)因子分解問題等；掌握蒙特卡羅算法，并用之解決素?cái)?shù)測試等問題。6.3學(xué)時(shí)安排理論課時(shí)6第一章：算法設(shè)計(jì)的基本概念第二章：NP完全理論第一節(jié)：什么是NP問題第一節(jié)：NP問題的一般解法理論課時(shí)6第二章：NP完全理論第二節(jié)：NP問題的求解方法概述第三章：蠻力法第一節(jié)：什么是蠻力法及蠻力法的設(shè)計(jì)思路第一節(jié)：蠻力法計(jì)算步驟理論課時(shí)6第三章：蠻力法第二節(jié)：查找問題中的蠻力法第三章：蠻力法第三節(jié)：排序問題中的蠻力法第三節(jié)：排序問題中的蠻力法計(jì)算步驟理論課時(shí)6第三章：蠻力法第四節(jié)：組合和圖論問題中的蠻力法第四節(jié)：組合和圖論問題中的蠻力法計(jì)算步驟習(xí)題課理論課時(shí)6第四章：分治法第一節(jié)：分治法的基本概念和設(shè)計(jì)思想第四章：分治法第二節(jié)：遞歸算法第二節(jié)：遞歸算法計(jì)算步驟理論課時(shí)6第四章：分治法第三節(jié)：排序問題中的分治法第四章：分治法第四節(jié)：組合問題中的分治法第四節(jié)：組合問題中的分治法計(jì)算步驟理論課時(shí)6第四章：分治法第五節(jié)：幾何問題中的分治法第五節(jié)：幾何問題中的分治法計(jì)算步驟習(xí)題課理論課時(shí)6第五章：減治法第一節(jié)：基本概念及其在查找問題中的應(yīng)用第五章：減治法第二節(jié)：排序和組合問題中的減治法第二節(jié)：排序和組合問題中的減治法計(jì)算步驟7.課程實(shí)施7.1教學(xué)單元一7.1.1教學(xué)日期第一周周一、周二、周四7.1.這一個(gè)教學(xué)單元學(xué)生要學(xué)習(xí)算法設(shè)計(jì)的概念，即什么是算法設(shè)計(jì)，如何進(jìn)行算法設(shè)計(jì)，需要準(zhǔn)備哪些預(yù)備知識(shí)，算法及其重要特性，算法的描述方法以及算法設(shè)計(jì)的一般過程，對(duì)于算法設(shè)計(jì)的概念的掌握程度要求了解，明白應(yīng)該怎么做，怎樣才能設(shè)計(jì)好一個(gè)算法，從學(xué)習(xí)概念學(xué)生可以了解什么是算法設(shè)計(jì)，如何通過分析實(shí)際問題設(shè)計(jì)出優(yōu)良，可操作的高效的算法。第二個(gè)要學(xué)習(xí)的部分就是NP完全理論，NP完全理論是理論信息學(xué)中的計(jì)算復(fù)雜度理論領(lǐng)域里的NPC，簡單的說，如果任何一個(gè)NP問題都能通過一個(gè)多項(xiàng)式時(shí)間算法轉(zhuǎn)換為某個(gè)NP問題，那么這個(gè)NP問題就稱為NPC問題。換言之，如果這個(gè)問題解決了，那么所有NP問題也都能解決了。第一個(gè)被證明是NPC的問題是3SAT問題。首先需要介紹P(Polynomial,多項(xiàng)式)問題.P問題是可以在多項(xiàng)式時(shí)間內(nèi)被確定機(jī)(通常意義的計(jì)算機(jī))解決的問題.NP(Non-DeterministicPolynomial,非確定多項(xiàng)式)問題,是指可以在多項(xiàng)式時(shí)間內(nèi)被非確定機(jī)(他可以猜,他總是能猜到最能滿足你需要的那種選擇,如果你讓他解決n皇后問題,他只要猜n次就能完成----每次都是那么幸運(yùn))解決的問題.這里有一個(gè)著名的問題----千禧難題之首,是說P問題是否等于NP問題,也即是否所有在非確定機(jī)上多項(xiàng)式可解的問題都能在確定機(jī)上用多項(xiàng)式時(shí)間求解。學(xué)生需要初步了解什么是NP完全問題。7.1.3教學(xué)內(nèi)容（含重點(diǎn)、難點(diǎn)）首先講算法設(shè)計(jì)的概念，分為五個(gè)部分。第一部分為什么要學(xué)習(xí)算法，第二部分是算法及其重要特性，第三部分是算法的描述方法，第四部分是算法設(shè)計(jì)的一般過程，第五部分是如何設(shè)計(jì)算法，章建躍博士曾經(jīng)說過：“理解數(shù)學(xué)”是第一基石。教什么比怎么教更重要，數(shù)學(xué)課要教數(shù)學(xué)，這就要求教師自己先理解好數(shù)學(xué)：了解數(shù)學(xué)的背景，掌握概念的邏輯意義，理解內(nèi)容所反映的思想方法，把握概念的“多元聯(lián)系表示”，挖掘知識(shí)所蘊(yùn)含的科學(xué)方法、理性精神等價(jià)值資源。在這節(jié)課的備課過程中，教師認(rèn)真研究了在本節(jié)課之前，學(xué)生學(xué)習(xí)了哪些知識(shí)，進(jìn)而發(fā)現(xiàn)，學(xué)生已經(jīng)積累了大量的算法的實(shí)踐經(jīng)驗(yàn)，只不過沒有明確提出“算法”這一概念。同時(shí)，為了進(jìn)一步培養(yǎng)學(xué)生歸納總結(jié)、提煉概括的能力，因而教師沒有像一般老師那樣從二元一次方程組的解法提煉出算法的概念，而是通過教師講一個(gè)有嚴(yán)格程序和步驟的問題，引導(dǎo)學(xué)生回顧相關(guān)實(shí)例（“坐標(biāo)方法”解決幾何問題的三部曲、求圓的方程常用“待定系數(shù)法”，那么它的大致步驟是怎樣的、實(shí)際問題使用數(shù)學(xué)建模的步驟、給點(diǎn)精確度，用二分法求函數(shù)零點(diǎn)近似值的步驟），再從這些實(shí)例中提煉出算法的概念。這樣也就充分體現(xiàn)了從學(xué)生“最近發(fā)展區(qū)”設(shè)計(jì)問題，從而提高了課堂教學(xué)的有效性。本節(jié)課“數(shù)學(xué)味道”特別濃，充分體現(xiàn)了“數(shù)學(xué)課要教數(shù)學(xué)”．一方面，本節(jié)課在選材上沒有把算法泛化，所選的實(shí)例全都是數(shù)學(xué)問題；另一方面，本節(jié)課更注重了數(shù)學(xué)思想方法的滲透，充分挖掘出蘊(yùn)含在算法概念之中的算法思想，通過實(shí)例讓學(xué)生體會(huì)算法思想，再通過算法的設(shè)計(jì)讓學(xué)生運(yùn)用算法特征設(shè)計(jì)具體案例，達(dá)到培養(yǎng)學(xué)生理性思維能力的目的。本節(jié)課，教師在充分挖掘了教學(xué)內(nèi)容的內(nèi)在聯(lián)系，充分分析了學(xué)情后，確定的教學(xué)目標(biāo)具有具體而準(zhǔn)確、科學(xué)而有效的特點(diǎn)。這節(jié)課的教學(xué)目標(biāo)不像一般課教學(xué)目標(biāo)的那樣抽象而空泛，而是具體、明確的，每一個(gè)教學(xué)目標(biāo)都與具體教學(xué)流程遙相呼應(yīng)，都可以落實(shí)到具體的教學(xué)流程之中。而且目標(biāo)中將“知識(shí)目標(biāo)”、“能力目標(biāo)”、“情感目標(biāo)”融為一體，充實(shí)而準(zhǔn)確．因此，這節(jié)課的教學(xué)目標(biāo)是具體而準(zhǔn)確的。這節(jié)課的教學(xué)目標(biāo)符合學(xué)生“認(rèn)知規(guī)律”以遞進(jìn)形式呈現(xiàn)：“體會(huì)、了解、初步形成——認(rèn)識(shí)、完善——理解、準(zhǔn)確把握、學(xué)會(huì)”，而且在師生的共同努力下，跳一跳就可以達(dá)到，因而該目標(biāo)是科學(xué)的、有效的。接著講NP完全問題，這里有一個(gè)著名的問題----千禧難題之首,是說P問題是否等于NP問題,也即是否所有在非確定機(jī)上多項(xiàng)式可解的問題都能在確定機(jī)上用多項(xiàng)式時(shí)間求解。這樣一來,只要我們找到一個(gè)NPC問題的多項(xiàng)式解,所有的NP問題都可以多項(xiàng)式時(shí)間內(nèi)劃歸成這個(gè)NPC問題,再用多項(xiàng)式時(shí)間解決,這樣NP就等于P了。換一種說法,如果一個(gè)問題的復(fù)雜度是該問題的一個(gè)實(shí)例規(guī)模n的多項(xiàng)式函數(shù)，則這種可以在多項(xiàng)式時(shí)間內(nèi)解決的問題屬于P類問題.通俗地稱所有復(fù)雜度為多項(xiàng)式時(shí)間的問題為易解的問題類，否則為難解的問題。有些問題很難找到多項(xiàng)式時(shí)間的算法（或許根本不存在）。例如“找出無向圖中哈密頓回路”問題。但如果給了該問題的一個(gè)答案，可以在多項(xiàng)式時(shí)間內(nèi)判斷這個(gè)答案是否正確。例如說對(duì)于哈密頓回路問題，給一個(gè)任意的回路，很容易判斷它是否是哈密頓回路（只要看是不是所有的頂點(diǎn)都在回路中就可以了）。這里給出NP問題的另一個(gè)定義,這種可以在多項(xiàng)式時(shí)間內(nèi)驗(yàn)證一個(gè)解是否正確的問題稱為NP問題，亦稱為驗(yàn)證問題類。簡單的說，存在多項(xiàng)式時(shí)間的算法的一類問題，稱之為P類問題；而像梵塔問題，推銷員旅行問題等問題，至今沒有找到多項(xiàng)式時(shí)間算法解的一類問題，稱之為NP問題。同時(shí)，P類問題是NP問題的一個(gè)子集。本單元重點(diǎn)是算法設(shè)計(jì)的概念，難點(diǎn)是NP完全理論。7.1.算法設(shè)計(jì)的概念里主要講解算法設(shè)計(jì)的一般過程，算法是問題的解決方案，這個(gè)解決方案本身并不是問題的答案，而是能獲得答案的指令序列。不言而喻，由于實(shí)際問題千奇百怪，問題求解的方法千變?nèi)f化，所以，算法的設(shè)計(jì)過程是一個(gè)靈活的充滿智慧的過程，他要求設(shè)計(jì)人員根據(jù)實(shí)際情況，，具體情況具體分析?？梢钥隙ǖ氖?，發(fā)明算法是一個(gè)非常具有創(chuàng)造性和值得付出精力的過程。在設(shè)計(jì)算法時(shí)，遵循下列步驟可以在一定程度上指導(dǎo)算法的設(shè)計(jì)。第一個(gè)是理解問題，在面對(duì)一個(gè)算法任務(wù)時(shí)，算法設(shè)計(jì)者往往不能準(zhǔn)確的理解要求他做的是什么，對(duì)算法希望實(shí)現(xiàn)什么只有一個(gè)大致的想法就匆忙地落筆寫算法，其后果往往是寫出的算法漏洞百出。在設(shè)計(jì)算法是需要做的第一件事就是完全理解要解決的問題，仔細(xì)閱讀問題的描述，手工處理一些小例子。對(duì)設(shè)計(jì)算法來說，這是一項(xiàng)重要的技能：準(zhǔn)確的理解算法的輸入是什么？要求算法做的是什么？即明確算法的入口和出口，這是設(shè)計(jì)算法的切入點(diǎn)。第二個(gè)部分是預(yù)計(jì)所有可能的輸入，算法的輸入確定了該算法所解問題的一個(gè)實(shí)例。事實(shí)上，無法保證一個(gè)算法永遠(yuǎn)不會(huì)遇到一個(gè)錯(cuò)誤的輸入，一個(gè)對(duì)大部分輸入都運(yùn)行正確而只有一個(gè)輸入不行的算法，就像一顆等待爆炸的炸彈。第三個(gè)部分是在精確解和近似解之間做選擇，計(jì)算機(jī)科學(xué)研究的目標(biāo)是用計(jì)算機(jī)來求解人類所面臨的各種問題。但是，有些問題無法求得精確解，例如計(jì)算pi值，求平方根，解非線性方程，求定積分等；有些問題由于其固有的復(fù)雜性，求精確解需要花費(fèi)太長的時(shí)間，其中最著名的要算旅行商問題，此時(shí)，只能求出近似解，有時(shí)需要根據(jù)問題以及問題所受的資源限制，在近似解和精確解之間做選擇。第四部分是確定適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)。第五部分是算法設(shè)計(jì)技術(shù)。第六部分是描述算法。第七部分是跟蹤算法。第八部分是分析算法的效率。最后一部分是根據(jù)算法編寫代碼。對(duì)于NP完全問題，首先需要介紹P(Polynomial,多項(xiàng)式)問題.P問題是可以在多項(xiàng)式時(shí)間內(nèi)被確定機(jī)(通常意義的計(jì)算機(jī))解決的問題.NP(Non-DeterministicPolynomial,非確定多項(xiàng)式)問題,是指可以在多項(xiàng)式時(shí)間內(nèi)被非確定機(jī)(他可以猜,他總是能猜到最能滿足你需要的那種選擇,如果你讓他解決n皇后問題,他只要猜n次就能完成----每次都是那么幸運(yùn))解決的問題.這里有一個(gè)著名的問題----千禧難題之首,是說P問題是否等于NP問題,也即是否所有在非確定機(jī)上多項(xiàng)式可解的問題都能在確定機(jī)上用多項(xiàng)式時(shí)間求解。這樣一來,只要我們找到一個(gè)NPC問題的多項(xiàng)式解,所有的NP問題都可以多項(xiàng)式時(shí)間內(nèi)劃歸成這個(gè)NPC問題,再用多項(xiàng)式時(shí)間解決,這樣NP就等于P了。換一種說法,如果一個(gè)問題的復(fù)雜度是該問題的一個(gè)實(shí)例規(guī)模n的多項(xiàng)式函數(shù)，則這種可以在多項(xiàng)式時(shí)間內(nèi)解決的問題屬于P類問題.通俗地稱所有復(fù)雜度為多項(xiàng)式時(shí)間的問題為易解的問題類，否則為難解的問題。有些問題很難找到多項(xiàng)式時(shí)間的算法（或許根本不存在）。例如“找出無向圖中哈密頓回路”問題。但如果給了該問題的一個(gè)答案，可以在多項(xiàng)式時(shí)間內(nèi)判斷這個(gè)答案是否正確。例如說對(duì)于哈密頓回路問題，給一個(gè)任意的回路，很容易判斷它是否是哈密頓回路（只要看是不是所有的頂點(diǎn)都在回路中就可以了）。這里給出NP問題的另一個(gè)定義,這種可以在多項(xiàng)式時(shí)間內(nèi)驗(yàn)證一個(gè)解是否正確的問題稱為NP問題，亦稱為驗(yàn)證問題類。簡單的說，存在多項(xiàng)式時(shí)間的算法的一類問題，稱之為P類問題；而像梵塔問題，推銷員旅行問題等問題，至今沒有找到多項(xiàng)式時(shí)間算法解的一類問題，稱之為NP問題。同時(shí)，P類問題是NP問題的一個(gè)子集。7.1.5教學(xué)方法主要是采用ppt教學(xué)，這樣形象直觀，允許學(xué)生有不懂的問題馬上提出來，這樣互動(dòng)會(huì)及時(shí)解決學(xué)生的疑惑，然后就是舉例子，這樣讓學(xué)生頭腦里有一個(gè)大致的印象，可以理解得更深，當(dāng)然課講完了后，就會(huì)給學(xué)生布置作業(yè)及課后反思，這樣才能進(jìn)一步提升對(duì)所學(xué)知識(shí)的鞏固，不會(huì)遺忘，還會(huì)思考些新的東西，這樣，就可以達(dá)到教與學(xué)真正的溝通。首先它是指具體的教學(xué)方法，從屬于教學(xué)方法論，是教學(xué)方法論的一個(gè)層面。教學(xué)方法論由教學(xué)方法指導(dǎo)思想、基本方法、具體方法、教學(xué)方式四個(gè)層面組成。教學(xué)方法包括教師教的方法（教授法）和學(xué)生學(xué)的方法（學(xué)習(xí)方法）兩大方面，是教授方法與學(xué)習(xí)方法的統(tǒng)一。教授法必須依據(jù)學(xué)習(xí)法，否則便會(huì)因缺乏針對(duì)性和可行性而不能有效地達(dá)到預(yù)期的目的。但由于教師在教學(xué)過程中處于主導(dǎo)地位，所以在教法與學(xué)法中，教法處于主導(dǎo)地位。教學(xué)方法不同于教學(xué)方式，但與教學(xué)方式有著密切的聯(lián)系。教學(xué)方式是構(gòu)成教學(xué)方法的細(xì)節(jié)，是運(yùn)用各種教學(xué)方法的技術(shù)。任何一種教學(xué)方法都由一系列的教學(xué)方式組成，可以分解為多種教學(xué)方式；另一方面，教學(xué)方法是一連串有目的的活動(dòng)，能獨(dú)立完成某項(xiàng)教學(xué)任務(wù)，而教學(xué)方式只被運(yùn)用于教學(xué)方法中，并為促成教學(xué)方法所要完成的教學(xué)任務(wù)服務(wù)，其本身不能完成一項(xiàng)教學(xué)任務(wù)。7.1.作業(yè)就是算法設(shè)計(jì)的概念后面的全部習(xí)題，課后反思主要探討背包問題。背包問題(Knapsackproblem)是在1978年由Merkel和Hellman提出的，是一種組合優(yōu)化的NP完全問題。問題可以描述為：給定一組物品，每種物品都有自己的重量和價(jià)格，在限定的總重量內(nèi)，我們?nèi)绾芜x擇，才能使得物品的總價(jià)格最高。問題的名稱來源于如何選擇最合適的物品放置于給定背包中。相似問題經(jīng)常出現(xiàn)在商業(yè)、組合數(shù)學(xué)，計(jì)算復(fù)雜性理論、密碼學(xué)和應(yīng)用數(shù)學(xué)等領(lǐng)域中。也可以將背包問題描述為決定性問題，即在總重量不超過W的前提下，總價(jià)值是否能達(dá)到V？背包問題是熟知的不可計(jì)算問題，背包體制以其加密，解密速度快而引人注目。但是，大多數(shù)一次背包體制均被破譯了，因此很少有人使用它。它的主要思路是假定某人擁有大量物品，重量各不同。此人通過秘密地選擇一部分物品并將它們放到背包中并加密消息。背包中的物品總重量是公開的，所有可能的物品也是公開的，但背包中的物品是保密的。附加一定的限制條件，給出重量，而要列出可能的物品，在計(jì)算上是不可實(shí)現(xiàn)的。背包問題是熟知的不可計(jì)算問題，背包體制以其加密，解密速度快而引人注目。但是，大多數(shù)一次背包體制均被破譯了，因此很少有人使用它。有N件物品和一個(gè)容量為V的背包。第i件物品的重量是c[i]，價(jià)值是w[i]。求解將哪些物品裝入背包可使這些物品的重量總和不超過背包容量，且價(jià)值總和最大。這是最基礎(chǔ)的背包問題，特點(diǎn)是：每種物品僅有一件，可以選擇放或不放。用子問題定義狀態(tài)：即f[i][v]表示前i件物品恰放入一個(gè)容量為v的背包可以獲得的最大價(jià)值。則其狀態(tài)轉(zhuǎn)移方程便是：f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}?？梢詨嚎s空間，f[v]=max{f[v],f[v-c[i]]+w[i]}這個(gè)方程非常重要，基本上所有跟背包相關(guān)的問題的方程都是由它衍生出來的。所以有必要將它詳細(xì)解釋一下：“將前i件物品放入容量為v的背包中”這個(gè)子問題，若只考慮第i件物品的策略（放或不放），那么就可以轉(zhuǎn)化為一個(gè)只牽扯前i-1件物品的問題。如果不放第i件物品，那么問題就轉(zhuǎn)化為“前i-1件物品放入容量為v的背包中”，價(jià)值為f[i-1][v]；如果放第i件物品，那么問題就轉(zhuǎn)化為“前i-1件物品放入剩下的容量為v-c[i]的背包中”，此時(shí)能獲得的最大價(jià)值就是f[i-1][v-c[i]]再加上通過放入第i件物品獲得的價(jià)值w[i]。注意f[v]有意義當(dāng)且僅當(dāng)存在一個(gè)前i件物品的子集，其費(fèi)用總和為v。所以按照這個(gè)方程遞推完畢后，最終的答案并不一定是f[N][V]，而是f[N][0..V]的最大值。如果將狀態(tài)的定義中的“恰”字去掉，在轉(zhuǎn)移方程中就要再加入一項(xiàng)f[v-1]，這樣就可以保證f[N][V]就是最后的答案。至于為什么這樣就可以，由你自己來體會(huì)了。以上方法的時(shí)間和空間復(fù)雜度均為O(N*V），其中時(shí)間復(fù)雜度基本已經(jīng)不能再優(yōu)化了，但空間復(fù)雜度卻可以優(yōu)化到O(N）。先考慮上面講的基本思路如何實(shí)現(xiàn)，肯定是有一個(gè)主循環(huán)i=1..N，每次算出來二維數(shù)組f[i][0..V]的所有值。那么，如果只用一個(gè)數(shù)組f[0..V]，能不能保證第i次循環(huán)結(jié)束后f[v]中表示的就是我們定義的狀態(tài)f[i][v]呢？[i][v]是由f[i-1][v]和f[i-1][v-c[i]]兩個(gè)子問題遞推而來，能否保證在推f[v]時(shí)（也即在第i次主循環(huán)中推f[v]時(shí)）能夠得到f[v]和f[v-c[i]]的值呢？事實(shí)上，這要求在每次主循環(huán)中我們以v=V..0的順序推f[v]，這樣才能保證推f[v]時(shí)f[v-c[i]]保存的是狀態(tài)f[i-1][v-c[i]]的值。偽代碼如下：ori=1..Nforv=V..0f[v]=max{f[v],f[v-c[i]]+w[i]};其中的f[v]=max{f[v],f[v-c[i]]}一句恰就相當(dāng)于我們的轉(zhuǎn)移方程f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]}，因?yàn)榈膄[v-c[i]]就相當(dāng)于原來的f[i-1][v-c[i]]。如果將v的循環(huán)順序從上面的逆序改成順序的話，那么則成了f[i][v]由f[i][v-c[i]]推知，與本題意不符，但它卻是另一個(gè)重要的背包問題P02最簡捷的解決方案，故學(xué)習(xí)只用一維數(shù)組解01背包問題是十分必要的。0/1背包問題是最基本的背包問題，它包含了背包問題中設(shè)計(jì)狀態(tài)、方程的最基本思想，另外，別的類型的背包問題往往也可以轉(zhuǎn)換成0/1背包問題求解。故一定要仔細(xì)體會(huì)上面基本思路的得出方法，狀態(tài)轉(zhuǎn)移方程的意義，以及最后怎樣優(yōu)化的空間復(fù)雜度。這個(gè)問題非常類似于01背包問題，所不同的是每種物品有無限件。也就是從每種物品的角度考慮，與它相關(guān)的策略已并非取或不取兩種，而是有取0件、取1件、取2件……等很多種。如果仍然按照解01背包時(shí)的思路，令f[i,v]表示前i種物品恰放入一個(gè)容量為v的背包的最大權(quán)值。仍然可以按照每種物品不同的策略寫出狀態(tài)轉(zhuǎn)移方程，像這樣：f[i,v]=max{f[i,v-vi]+wi,f[i-1,v]}。這跟01背包問題一樣有O(N*V）個(gè)狀態(tài)需要求解，但求解每個(gè)狀態(tài)的時(shí)間則不是常數(shù)了，求解狀態(tài)f[v]的時(shí)間是O(v/c），總的復(fù)雜度是超過O(VN）的。將01背包問題的基本思路加以改進(jìn)，得到了這樣一個(gè)清晰的方法。這說明01背包問題的方程的確是很重要，可以推及其它類型的背包問題。但我們還是試圖改進(jìn)這個(gè)復(fù)雜度。完全背包問題有一個(gè)很簡單有效的優(yōu)化，是這樣的：若兩件物品i、j滿足c<=c[j]且w>=w[j]，則將物品j去掉，不用考慮。這個(gè)優(yōu)化的正確性顯然：任何情況下都可將價(jià)值小體積高的j換成物美價(jià)廉的i，得到至少不會(huì)更差的方案。對(duì)于隨機(jī)生成的數(shù)據(jù)，這個(gè)方法往往會(huì)大大減少物品的件數(shù)，從而加快速度。然而這個(gè)并不能改善最壞情況的復(fù)雜度，因?yàn)橛锌赡芴貏e設(shè)計(jì)的數(shù)據(jù)可以一件物品也去不掉。既然01背包問題是最基本的背包問題，那么我們可以考慮把完全背包問題轉(zhuǎn)化為01背包問題來解。最簡單的想法是，考慮到第i種物品最多選V/c件，于是可以把第i種物品轉(zhuǎn)化為V/c件體積及價(jià)值均不變的物品，然后求解這個(gè)01背包問題。這樣完全沒有改進(jìn)基本思路的時(shí)間復(fù)雜度，但這畢竟給了我們將完全背包問題轉(zhuǎn)化為01背包問題的思路：將一種物品拆成多件物品。你會(huì)發(fā)現(xiàn)，這個(gè)偽代碼與P01的偽代碼只有v的循環(huán)次序不同而已。為什么這樣一改就可行呢？首先想想為什么P01中要按照v=V..0的逆序來循環(huán)。這是因?yàn)橐ＷC第i次循環(huán)中的狀態(tài)f[v]是由狀態(tài)f[v-c]遞推而來。換句話說，這正是為了保證每件物品只選一次，保證在考慮“選入第i件物品”這件策略時(shí)，依據(jù)的是一個(gè)絕無已經(jīng)選入第i件物品的子結(jié)果f[v-c]。而完全背包的特點(diǎn)恰是每種物品可選無限件，所以在考慮“加選一件第i種物品”這種策略時(shí)，卻正需要一個(gè)可能已選入第i種物品的子結(jié)果f[v-c]，所以就可以并且必須采用v=0..V的順序循環(huán)。這就是這個(gè)簡單的程序?yàn)楹纬闪⒌牡览?。完全背包問題也是一個(gè)相當(dāng)基礎(chǔ)的背包問題，它有兩個(gè)狀態(tài)轉(zhuǎn)移方程，分別在“基本思路”以及“O(VN）的算法“的小節(jié)中給出。希望你能夠?qū)@兩個(gè)狀態(tài)轉(zhuǎn)移方程都仔細(xì)地體會(huì)，不僅記住，也要弄明白它們是怎么得出來的，最好能夠自己想一種得到這些方程的方法。事實(shí)上，對(duì)每一道動(dòng)態(tài)規(guī)劃題目都思考其方程的意義以及如何得來，是加深對(duì)動(dòng)態(tài)規(guī)劃的理解、提高動(dòng)態(tài)規(guī)劃功力的好方法。如果將P01、P02、P03混合起來。也就是說，有的物品只可以取一次（01背包），有的物品可以取無限次（完全背包），有的物品可以取的次數(shù)有一個(gè)上限（多重背包）。應(yīng)該怎么求解呢？如果再加上有的物品最多可以取有限次，那么原則上也可以給出O(VN）的解法：遇到多重背包類型的物品用單調(diào)隊(duì)列解即可。但如果不考慮超過NOIP范圍的算法的話，用P03中將每個(gè)這類物品分成O(logn）個(gè)01背包的物品的方法也已經(jīng)很優(yōu)了。有人說，困難的題目都是由簡單的題目疊加而來的。這句話是否公理暫且存之不論，但它在本講中已經(jīng)得到了充分的體現(xiàn)。本來01背包、完全背包、多重背包都不是什么難題，但將它們簡單地組合起來以后就得到了這樣一道一定能嚇倒不少人的題目。但只要基礎(chǔ)扎實(shí)，領(lǐng)會(huì)三種基本背包問題的思想，就可以做到把困難的題目拆分成簡單的題目來解決。有N種物品和一個(gè)容量為V的背包。第i種物品最多有n件可用，每件體積是c，價(jià)值是w。求解將哪些物品裝入背包可使這些物品的體積總和不超過背包容量，且價(jià)值總和最大。這題目和完全背包問題很類似?；镜姆匠讨恍鑼⑼耆嘲鼏栴}的方程略微一改即可，因?yàn)閷?duì)于第i種物品有n+1種策略：取0件，取1件……取n件。令f[v]表示前i種物品恰放入一個(gè)容量為v的背包的最大權(quán)值，則：f[v]=max{f[v-k*c]+k*w|0<=k<=n}。復(fù)雜度是O(V*∑n）。另一種好想好寫的基該方法是轉(zhuǎn)化為01背包求解：把第i種物品換成n件01背包中的物品，則得到了物品數(shù)為∑n的01背包問題，直接求解，復(fù)雜度仍然是O(V*∑n）。但是我們期望將它轉(zhuǎn)化為01背包問題之后能夠像完全背包一樣降低復(fù)雜度。仍然考慮二進(jìn)制的思想，我們考慮把第i種物品換成若干件物品，使得原問題中第i種物品可取的每種策略——取0..n件——均能等價(jià)于取若干件代換以后的物品。另外，取超過n件的策略必不能出現(xiàn)。方法是：將第i種物品分成若干件物品，其中每件物品有一個(gè)系數(shù)，這件物品的費(fèi)用和價(jià)值均是原來的費(fèi)用和價(jià)值乘以這個(gè)系數(shù)。使這些系數(shù)分別為1,2,4,...,2^(k-1），n-2^k+1，且k是滿足n-2^k+1>0的最大整數(shù)。例如，如果n為13，就將這種物品分成系數(shù)分別為1,2,4,6的四件物品。分成的這幾件物品的系數(shù)和為n，表明不可能取多于n件的第i種物品。另外這種方法也能保證對(duì)于0..n間的每一個(gè)整數(shù)，均可以用若干個(gè)系數(shù)的和表示，這個(gè)證明可以分0..2^k-1和2^k..n兩段來分別討論得出，并不難，希望你自己思考嘗試一下。這樣就將第i種物品分成了O(logn）種物品，將原問題轉(zhuǎn)化為了復(fù)雜度為O(V*∑logn）的01背包問題，是很大的改進(jìn)。多重背包問題同樣有O(VN）的算法。這個(gè)算法基于基本算法的狀態(tài)轉(zhuǎn)移方程，但應(yīng)用單調(diào)隊(duì)列的方法使每個(gè)狀態(tài)的值可以以均攤O⑴的時(shí)間求解。由于用單調(diào)隊(duì)列優(yōu)化的DP已超出了NOIP的范圍，故本文不再展開講解。我最初了解到這個(gè)方法是在樓天成的“男人八題”幻燈片上。這里我們看到了將一個(gè)算法的復(fù)雜度由O(V*∑n）改進(jìn)到O(V*∑logn）的過程，還知道了存在應(yīng)用超出NOIP范圍的知識(shí)的O(VN）算法。希望你特別注意“拆分物品”的思想和方法，自己證明一下它的正確性，并用盡量簡潔的程序來實(shí)現(xiàn)。二維費(fèi)用的背包問題是指：對(duì)于每件物品，具有兩種不同的費(fèi)用；選擇這件物品必須同時(shí)付出這兩種代價(jià)；對(duì)于每種代價(jià)都有一個(gè)可付出的最大值（背包容量）。問怎樣選擇物品可以得到最大的價(jià)值。設(shè)這兩種代價(jià)分別為代價(jià)1和代價(jià)2，第i件物品所需的兩種代價(jià)分別為a和b。兩種代價(jià)可付出的最大值（兩種背包容量）分別為V和U。物品的價(jià)值為w。費(fèi)用加了一維，只需狀態(tài)也加一維即可。設(shè)f[v]表示前i件物品付出兩種代價(jià)分別為v和u時(shí)可獲得的最大價(jià)值。狀態(tài)轉(zhuǎn)移方程就是：fi[i][v][u]=max{f[i-1][v][u],f[i-1][v-a[i]][u-b[i]]+w[i]}。如前述方法，可以只使用二維的數(shù)組：當(dāng)每件物品只可以取一次時(shí)變量v和u采用逆序的循環(huán)，當(dāng)物品有如完全背包問題時(shí)采用順序的循環(huán)。當(dāng)物品有如多重背包問題時(shí)拆分物品。有時(shí)，“二維費(fèi)用”的條件是以這樣一種隱含的方式給出的：最多只能取M件物品。這事實(shí)上相當(dāng)于每件物品多了一種“件數(shù)”的費(fèi)用，每個(gè)物品的件數(shù)費(fèi)用均為1，可以付出的最大件數(shù)費(fèi)用為M。換句話說，設(shè)f[v][m]表示付出費(fèi)用v、最多選m件時(shí)可得到的最大價(jià)值，則根據(jù)物品的類型（01、完全、多重）用不同的方法循環(huán)更新，最后在f[0..V][0..M]范圍內(nèi)尋找答案。另外，如果要求“恰取M件物品”，則在f[0..V][M]范圍內(nèi)尋找答案。事實(shí)上，當(dāng)發(fā)現(xiàn)由熟悉的動(dòng)態(tài)規(guī)劃題目變形得來的題目時(shí)，在原來的狀態(tài)中加一維以滿足新的限制是一種比較通用的方法。希望你能從本講中初步體會(huì)到這種方法。這種背包問題的物品間存在某種“依賴”的關(guān)系。也就是說，i依賴于j，表示若選物品i，則必須選物品j。為了簡化起見，我們先設(shè)沒有某個(gè)物品既依賴于別的物品，又被別的物品所依賴；另外，沒有某件物品同時(shí)依賴多件物品。這個(gè)問題由NOIP2006金明的預(yù)算方案一題擴(kuò)展而來。遵從該題的提法，將不依賴于別的物品的物品稱為“主件”，依賴于某主件的物品稱為“附件”。由這個(gè)問題的簡化條件可知所有的物品由若干主件和依賴于每個(gè)主件的一個(gè)附件集合組成。按照背包問題的一般思路，僅考慮一個(gè)主件和它的附件集合?？墒?，可用的策略非常多，包括：一個(gè)也不選，僅選擇主件，選擇主件后再選擇一個(gè)附件，選擇主件后再選擇兩個(gè)附件……無法用狀態(tài)轉(zhuǎn)移方程來表示如此多的策略。（事實(shí)上，設(shè)有n個(gè)附件，則策略有2^n+1個(gè)，為指數(shù)級(jí)。）考慮到所有這些策略都是互斥的（也就是說，你只能選擇一種策略），所以一個(gè)主件和它的附件集合實(shí)際上對(duì)應(yīng)于P06中的一個(gè)物品組，每個(gè)選擇了主件又選擇了若干個(gè)附件的策略對(duì)應(yīng)于這個(gè)物品組中的一個(gè)物品，其費(fèi)用和價(jià)值都是這個(gè)策略中的物品的值的和。但僅僅是這一步轉(zhuǎn)化并不能給出一個(gè)好的算法，因?yàn)槲锲方M中的物品還是像原問題的策略一樣多。再考慮P06中的一句話：可以對(duì)每組中的物品應(yīng)用P02中“一個(gè)簡單有效的優(yōu)化”。這提示我們，對(duì)于一個(gè)物品組中的物品，所有費(fèi)用相同的物品只留一個(gè)價(jià)值最大的，不影響結(jié)果。所以，我們可以對(duì)主件i的“附件集合”先進(jìn)行一次01背包，得到費(fèi)用依次為0..V-c所有這些值時(shí)相應(yīng)的最大價(jià)值f'[0..V-c]。那么這個(gè)主件及它的附件集合相當(dāng)于V-c+1個(gè)物品的物品組，其中費(fèi)用為c+k的物品的價(jià)值為f'[k]+w。也就是說原來指數(shù)級(jí)的策略中有很多策略都是冗余的，通過一次01背包后，將主件i轉(zhuǎn)化為V-c+1個(gè)物品的物品組，就可以直接應(yīng)用P06的算法解決問題了。更一般的問題是：依賴關(guān)系以圖論中“森林”的形式給出（森林即多叉樹的集合），也就是說，主件的附件仍然可以具有自己的附件集合，限制只是每個(gè)物品最多只依賴于一個(gè)物品（只有一個(gè)主件）且不出現(xiàn)循環(huán)依賴。7.1.課前我主要是準(zhǔn)備了些例子，對(duì)于一些經(jīng)典的算法，比如貪婪法，枚舉法，遞歸法，對(duì)于貪婪法：貪婪法一般可以快速得到滿意的解，因?yàn)樗∪チ藶檎易顑?yōu)解要窮盡所有可能而必須耗費(fèi)的大量時(shí)間。貪婪法常以當(dāng)前情況為基礎(chǔ)作最優(yōu)選擇，而不考慮各種可能的整體情況，所以貪婪法不要回溯。貪婪法是一種不追求最優(yōu)解，只希望得到較為滿意解的方法。貪婪法一般可以快速得到滿意的解，因?yàn)樗∪チ藶檎易顑?yōu)解要窮盡所有可能而必須耗費(fèi)的大量時(shí)間。貪婪法常以當(dāng)前情況為基礎(chǔ)作最優(yōu)選擇，而不考慮各種可能的整體情況，所以貪婪法不要回溯。對(duì)于枚舉法：枚舉法是利用計(jì)算機(jī)運(yùn)算速度快、精確度高的特點(diǎn)，對(duì)要解決問題的所有可能情況，一個(gè)不漏地進(jìn)行檢驗(yàn)，從中找出符合要求的答案，因此枚舉法是通過犧牲時(shí)間來換取答案的全面性。在數(shù)學(xué)和計(jì)算機(jī)科學(xué)理論中，一個(gè)集的枚舉是列出某些有窮序列集的所有成員的程序，或者是一種特定類型對(duì)象的計(jì)數(shù)。這兩種類型經(jīng)常（但不總是）重疊。對(duì)于遞歸法：遞歸算法是一種直接或者間接地調(diào)用自身算法的過程。在計(jì)算機(jī)編寫程序中，遞歸算法對(duì)解決一大類問題是十分有效的，它往往使算法的描述簡潔而且易于理解。遞歸算法解決問題的特點(diǎn)：(1)遞歸就是在過程或函數(shù)里調(diào)用自身。(2)在使用遞歸策略時(shí)，必須有一個(gè)明確的遞歸結(jié)束條件，稱為遞歸出口。(3)遞歸算法解題通常顯得很簡潔，但遞歸算法解題的運(yùn)行效率較低。所以一般不提倡用遞歸算法設(shè)計(jì)程序。(4)在遞歸調(diào)用的過程當(dāng)中系統(tǒng)為每一層的返回點(diǎn)、局部量等開辟了棧來存儲(chǔ)。遞歸次數(shù)過多容易造成棧溢出等。所以一般不提倡用遞歸算法設(shè)計(jì)程序。7.1.組合數(shù)學(xué)6-8頁，算法設(shè)計(jì)與分析3-4頁，嚴(yán)蔚敏.數(shù)據(jù)機(jī)構(gòu)第一章7.2教學(xué)單元二7.2.1教學(xué)日期第二周周一、周二、周四7.2.讓學(xué)生進(jìn)一步掌握以下內(nèi)容：（1）NP完全理論（2）NP問題的求解方法概述初步掌握（1）什么是蠻力法及蠻力法的設(shè)計(jì)思路（2）蠻力法計(jì)算步驟7.2.有些計(jì)算問題是確定性的，比如加減乘除之類，你只要按照公式推導(dǎo)，按部就班一步步來，就可以得到結(jié)果。但是，有些問題是無法按部就班直接地計(jì)算出來。比如，找大質(zhì)數(shù)的問題。有沒有公式，你一套公式，就可以一步步推算出來，下一個(gè)質(zhì)數(shù)應(yīng)該是多少呢？這樣的公式是沒有的。再比如，大的合數(shù)分解質(zhì)因數(shù)的問題，有沒有一個(gè)公式，把合數(shù)代進(jìn)去，就直接可以算出，它的因子各自是多少？也沒有這樣的公式。這種問題的答案，是無法直接計(jì)算得到的，只能通過間接的“猜算”來得到結(jié)果。這就是非確定性問題。而這些問題的通常有個(gè)算法，它不能直接告訴你答案是什么，但可以告訴你，某個(gè)可能的結(jié)果是正確的答案還是錯(cuò)誤的。這個(gè)可以告訴你“猜算”的答案正確與否的算法，假如可以在多項(xiàng)式時(shí)間內(nèi)算出來，就叫做多項(xiàng)式非確定性問題。而如果這個(gè)問題的所有可能答案，都是可以在多項(xiàng)式時(shí)間內(nèi)進(jìn)行正確與否的驗(yàn)算的話，就叫完全多項(xiàng)式非確定問題。完全多項(xiàng)式非確定性問題可以用窮舉法得到答案，一個(gè)個(gè)檢驗(yàn)下去，最終便能得到結(jié)果。但是這樣算法的復(fù)雜程度，是指數(shù)關(guān)系，因此計(jì)算的時(shí)間隨問題的復(fù)雜程度成指數(shù)的增長，很快便變得不可計(jì)算了。人們發(fā)現(xiàn)，所有的完全多項(xiàng)式非確定性問題，都可以轉(zhuǎn)換為一類叫做滿足性問題的邏輯運(yùn)算問題。既然這類問題的所有可能答案，都可以在多項(xiàng)式時(shí)間內(nèi)計(jì)算，人們于是就猜想，是否這類問題存在一個(gè)確定性算法，可以在多項(xiàng)式時(shí)間內(nèi)直接算出或是搜尋出正確的答案呢？這就是著名的NP=P？的猜想。解決這個(gè)猜想，無非兩種可能，一種是找到一個(gè)這樣的算法，只要針對(duì)某個(gè)特定NP完全問題找到一個(gè)算法，所有這類問題都可以迎刃而解了，因?yàn)樗麄兛梢赞D(zhuǎn)化為同一個(gè)問題。另外的一種可能，就是這樣的算法是不存在的。那么就要從數(shù)學(xué)理論上證明它為什么不存在。最常被引用的結(jié)果之一設(shè)計(jì)神喻。假想你有一個(gè)魔法機(jī)器可以解決單個(gè)問題，例如決定一個(gè)給定的數(shù)字是否為質(zhì)數(shù)，但可以瞬間解決這個(gè)問題。我們的新問題是，若我們被允許任意利用這個(gè)機(jī)器，是否存在我們可以在多項(xiàng)式時(shí)間內(nèi)驗(yàn)證但無法在多項(xiàng)式時(shí)間內(nèi)解決的問題？結(jié)果是，依賴于機(jī)器能解決的問題，P=NP和P≠NP二者都可以證明。這個(gè)結(jié)論的后果是，任何可以修改來證明該機(jī)器的存在性的結(jié)果不能解決問題。不幸的是，幾乎所有經(jīng)典的方法和大部分已知的方法可以這樣修改（我們稱它們?cè)谙鄬?duì)化）。如果這還不算太糟的話，1993年Razborov和Rudich證明的一個(gè)結(jié)果表明，給定一個(gè)特定的可信的假設(shè)，在某種意義下“自然”的證明不能解決P=NP問題。這表明一些現(xiàn)在似乎最有希望的方法不太可能成功。隨著更多這類的定理得到證明，該定理的可能證明有越來越多的陷阱要規(guī)避。這實(shí)際上也是為什么NP完全問題有用的原因：若有一個(gè)多項(xiàng)式時(shí)間算法，或者沒有一個(gè)這樣的算法，對(duì)于NP完全問題存在，這將用一種相信不被上述結(jié)果排除在外的方法來解決P=NP問題。P=NP問題可以用邏輯命題的特定類的可表達(dá)性的術(shù)語來重新表述。所有P中的語言可以用一階邏輯加上最小不動(dòng)點(diǎn)操作（實(shí)際上，這允許了遞歸函數(shù)的定義）來表達(dá)。類似地，NP是可以用存在性二階邏輯來表達(dá)—也就是，在關(guān)系、函數(shù)、和子集上排除了全域量詞的二階邏輯。多項(xiàng)式等級(jí)，PH中的語言對(duì)應(yīng)與所有的二階邏輯。這樣，“P是NP的真子集嗎”這樣的問題可以表述為“是否存在性二階邏輯能夠表達(dá)帶最小不動(dòng)點(diǎn)操作的一階邏輯的所不能表達(dá)的語言？”普林斯頓大學(xué)計(jì)算機(jī)系樓將二進(jìn)制代碼表述的“P=NP?”問題刻進(jìn)頂樓西面的磚頭上。如果證明了P=NP，磚頭可以很方便的換成表示“P=NP！”?？的螤柎髮W(xué)的HubertChen博士提供了這個(gè)玩笑式的P不等于NP的證明：“反證法。設(shè)P=NP。令y為一個(gè)P=NP的證明。證明y可以用一個(gè)合格的計(jì)算機(jī)科學(xué)家在多項(xiàng)式時(shí)間內(nèi)驗(yàn)證，我們認(rèn)定這樣的科學(xué)家的存在性為真。但是，因?yàn)镻=NP，該證明y可以在多項(xiàng)式時(shí)間內(nèi)由這樣的科學(xué)家發(fā)現(xiàn)。但是這樣的發(fā)現(xiàn)還沒有發(fā)生（雖然這樣的科學(xué)家試圖發(fā)現(xiàn)這樣的一個(gè)證明），我們得到矛盾。常用搜索方法（1）近鄰法近鄰法（nearestneighbor)推銷員從某個(gè)城鎮(zhèn)出發(fā)，永遠(yuǎn)選擇前往最近且尚未去過的城鎮(zhèn)，最后再返回原先的出發(fā)點(diǎn)。這方法簡單，也許是多數(shù)人的直覺做法，但是近鄰法的短視使其表現(xiàn)非常不好，通常后段的路程會(huì)非常痛苦。（2）插入法插入法（insertion)先產(chǎn)生連接部分點(diǎn)的子路線，再根據(jù)某種法則將其它的點(diǎn)逐一加入路線。比如最近插入法（nearestinsertion），先針對(duì)外圍的點(diǎn)建構(gòu)子路線，然后從剩余的點(diǎn)里面評(píng)估何者加入后路線總長度增加的幅度最小，再將這個(gè)點(diǎn)加入路線。又比如最遠(yuǎn)插入法（farthest，insertion），是從剩余的點(diǎn)里面選擇距離子路線最遠(yuǎn)的點(diǎn)，有點(diǎn)先苦后甜的滋味。（3）模擬退火算法模擬退火算法（RecuitAlgorithm)來源于固體退火原理，將固體加溫至充分高，再讓其徐徐冷卻，加溫時(shí)，固體內(nèi)部粒子隨溫升變?yōu)闊o序狀，內(nèi)能增大，而徐徐冷卻時(shí)粒子漸趨有序，在每個(gè)溫度都達(dá)到平衡態(tài)，最后在常溫時(shí)達(dá)到基態(tài)，內(nèi)能減為最小。根據(jù)Metropolis準(zhǔn)則，粒子在溫度T時(shí)趨于平衡的概率為e-ΔE/(kT），其中E為溫度T時(shí)的內(nèi)能，ΔE為其改變量，k為Boltzmann常數(shù)。用固體退火模擬組合優(yōu)化問題，將內(nèi)能E模擬為目標(biāo)函數(shù)值f，溫度T演化成控制參數(shù)t，即得到解組合優(yōu)化問題的模擬退火算法：由初始解i和控制參數(shù)初值t開始，對(duì)當(dāng)前解重復(fù)“產(chǎn)生新解→計(jì)算目標(biāo)函數(shù)差→接受或舍棄”的迭代，并逐步衰減t值，算法終止時(shí)的當(dāng)前解即為所得近似最優(yōu)解。（4）遺傳算法遺傳算法是仿真生物遺傳學(xué)和自然選擇機(jī)理，通過人工方式所構(gòu)造的一類搜索算法，從某種程度上說遺傳算法是對(duì)生物進(jìn)化過程進(jìn)行的數(shù)學(xué)方式仿真。生物種群的生存過程普遍遵循達(dá)爾文進(jìn)化準(zhǔn)則，群體中的個(gè)體根據(jù)對(duì)環(huán)境的適應(yīng)能力而被大自然所選擇或淘汰。進(jìn)化過程的結(jié)果反映在個(gè)體的結(jié)構(gòu)上，其染色體包含若干基因，相應(yīng)的表現(xiàn)型和基因型的聯(lián)系體現(xiàn)了個(gè)體的外部特性與內(nèi)部機(jī)理間邏輯關(guān)系。通過個(gè)體之間的交叉、變異來適應(yīng)大自然環(huán)境。生物染色體用數(shù)學(xué)方式或計(jì)算機(jī)方式來體現(xiàn)就是一串?dāng)?shù)碼，仍叫染色體，有時(shí)也叫個(gè)體；適應(yīng)能力是對(duì)應(yīng)著一個(gè)染色體的一個(gè)數(shù)值來衡量；染色體的選擇或淘汰則按所面對(duì)的問題是求最大還是最小來進(jìn)行。（5）神經(jīng)網(wǎng)絡(luò)算法根據(jù)一個(gè)簡化的統(tǒng)計(jì)，人腦由百億條神經(jīng)組成—每條神經(jīng)平均連結(jié)到其它幾千條神經(jīng)。通過這種連結(jié)方式，神經(jīng)可以收發(fā)不同數(shù)量的能量。神經(jīng)的一個(gè)非常重要的功能是它們對(duì)能量的接受并不是立即作出響應(yīng)，而是將它們累加起來，當(dāng)這個(gè)累加的總和達(dá)到某個(gè)臨界閾值時(shí)，它們將它們自己的那部分能量發(fā)送給其它的神經(jīng)。大腦通過調(diào)節(jié)這些連結(jié)的數(shù)目和強(qiáng)度進(jìn)行學(xué)習(xí)。盡管這是個(gè)生物行為的簡化描述。但同樣可以充分有力地被看作是神經(jīng)網(wǎng)絡(luò)的模型。（6）蠻力法蠻力法就是一種解決問題的最簡單最直觀的最容易理解方法，雖然它簡單，而且在實(shí)際應(yīng)用中因?yàn)樾实脑蚩赡懿荒芘缮嫌脠?，但是還是不能忽略它。在解決小規(guī)模問題的時(shí)候也不失為一個(gè)方法，而且也是更復(fù)雜算法的基礎(chǔ)。1.蠻力法的基本思想蠻力法是一種簡單直接地解決問題的方法.2．選擇排序問題描述及算法講解演示；歸納算法時(shí)間效率關(guān)系式；推導(dǎo)并求解除選擇排序的時(shí)間效率為Θ(n2)。3．冒泡排序冒泡排序算法講解演示；歸納算法時(shí)間效率關(guān)系式；推導(dǎo)并求解除選擇排序的時(shí)間效率為Θ(n2)4．順序查找和蠻力字符串匹配查找和字符串匹配問題描述及算法講解演示；歸納算法時(shí)間效率關(guān)系式。5．最近對(duì)問題最近對(duì)問題的描述及模型；最近對(duì)問題的蠻力算法及時(shí)間效率分析。6．凸包問題凸包的定義及舉例及問題的描述；凸包問題的蠻力解決方法及時(shí)間效率分析。7．窮舉查找旅行商問題、背包問題、分配問題。7.2.本課程是信息與計(jì)算科學(xué)專業(yè)的重要專業(yè)方向理論課，是軟件開發(fā)賴以生存的重要基礎(chǔ)。在教學(xué)方法上，采用課堂講授，課后自學(xué)，課堂討論等教學(xué)形式。本課程屬于專業(yè)方向理論課程。在傳授知識(shí)原理的前提下，配合實(shí)際應(yīng)用例子，由淺入深善于誘導(dǎo)，使學(xué)生從被動(dòng)吸收知識(shí)的狀態(tài)下，轉(zhuǎn)化到主動(dòng)索取知識(shí)的狀態(tài)中來，并采用多媒體輔助教學(xué)，加大課堂授課的知識(shí)含量。注重培養(yǎng)學(xué)生的學(xué)習(xí)興趣，提高學(xué)生的基本素質(zhì)。7.2.為了培養(yǎng)學(xué)生整理歸納，綜合分析和處理問題的能力，每章都安排一部分內(nèi)容，課上教師只給出自學(xué)提綱，不作詳細(xì)講解，課后學(xué)生自學(xué)。課堂討論的目的是活躍學(xué)習(xí)氣氛，開拓思路。教師應(yīng)認(rèn)真組織，安排重點(diǎn)發(fā)言，充分調(diào)動(dòng)每一名同學(xué)的學(xué)習(xí)積極性，做好總結(jié)。課外作業(yè)為了讓學(xué)生鞏固所學(xué)的知識(shí)，每章都布置一定數(shù)量課外作業(yè)。這樣，就可以達(dá)到教與學(xué)真正的溝通。7.2.6作業(yè)安排及課后反思算法設(shè)計(jì)后面相應(yīng)的習(xí)題，嘗試應(yīng)用蠻力法解決找旅行商問題、背包問題、分配問題。通過這個(gè)單元的教學(xué)，我試著教學(xué)生如何運(yùn)用蠻力法解決找旅行商問題，背包問題。通過對(duì)相關(guān)理論知識(shí)的講解和典型習(xí)題的講解，引導(dǎo)學(xué)生自己解決此類問題。雖然一開始接受起來有些吃力，教學(xué)內(nèi)容不能夠按要求完成，但通過幾節(jié)課的耐心講解，學(xué)生開始學(xué)會(huì)自己獨(dú)立的思考，通過課堂討論，課后練習(xí)的綜合練習(xí)，學(xué)生有了很大的提高。通過這幾次的上課，我了解到光是自己講理論是不行的，必須和學(xué)生互動(dòng)起來，教他們?nèi)绾巫约邯?dú)立的思考，如何通過學(xué)過的知識(shí)來解決新的難題。知識(shí)點(diǎn)就那么多，在掌握了一些必要的知識(shí)點(diǎn)以后，如何運(yùn)用起來，如何去解決不同的問題，這才是教學(xué)的內(nèi)容和目的。也只有學(xué)生真的能夠把所學(xué)的知識(shí)運(yùn)用到實(shí)際中，這些知識(shí)才是有意義的，否則，掌握再多的理論那也只是理論，沒有任何的實(shí)用價(jià)值。所以一定要通過大量的練習(xí)題和實(shí)際問題來幫助同學(xué)提高這方面的能力。7.2.提前預(yù)習(xí)教材相關(guān)部分，了解相關(guān)內(nèi)容。搜集相關(guān)的練習(xí)題在課堂上講解，羅列所用到的知識(shí)點(diǎn)以及經(jīng)典的解題技巧。7.2算法設(shè)計(jì)與分析13-17頁，嚴(yán)蔚敏.數(shù)據(jù)機(jī)構(gòu)第二、三章7.3教學(xué)單元三7.3.1教學(xué)日期第三周周一、周二、周四7.3.2教學(xué)目標(biāo)讓學(xué)生進(jìn)一步掌握以下內(nèi)容：（1）查找問題中的蠻力法（2）排序問題中的蠻力法（3）排序問題中的蠻力法計(jì)算步驟7.3.3教學(xué)內(nèi)容（含重點(diǎn)、難點(diǎn)）（1）蠻力法的設(shè)計(jì)思想：直接基于問題的描述（2）蠻力法所依賴的基本技術(shù)——掃描技術(shù)（3）關(guān)鍵——依次處理所有元素（4）基本的掃描技術(shù)——遍歷集合的遍歷線性表的遍歷樹的遍歷圖的遍歷雖然巧妙和高效的算法很少來自于蠻力法，基于以下原因，蠻力法也是一種重要的算法設(shè)計(jì)技術(shù)：（1）理論上，蠻力法可以解決可計(jì)算領(lǐng)域的各種問題。（2）蠻力法經(jīng)常用來解決一些較小規(guī)模的問題。（3）對(duì)于一些重要的問題蠻力法可以產(chǎn)生一些合理的算法，他們具備一些實(shí)用價(jià)值，而且不受問題規(guī)模的限制。（4）蠻力法可以作為某類問題時(shí)間性能的底線，來衡量同樣的更高效的算法。集合的遍歷：viewplaincopyprint?importjava.util.ArrayList;importjava.util.Iterator;importjava.util.List;publicclassTest{publicstaticvoidmain(String[]args){Listlist=newArrayList();list.add(3);list.add(2);list.add(10);list.add(4);list.add(70);/*System.out.println("---方法一-----");for(Iteratoriterator=list.iterator();iterator.hasNext();){inti=(Integer)iterator.next();System.out.println(i);}/*System.out.println("---方法二-----");Iteratoriterator=list.iterator();while(iterator.hasNext()){inti=(Integer)iterator.next();System.out.println(i);}System.out.println("---方法三-----");for(Objectobject:list){System.out.println(object);}*/System.out.println("---方法四-----");for(inti=0;i<list.size();i++){intj=(Integer)list.get(i);System.out.println(j);}}}給定一個(gè)輸入序列，建立順序表，訪問輸出順序表中各結(jié)點(diǎn)的內(nèi)容。給定一個(gè)輸入序列，建立線性鏈表，訪問輸出線性鏈表中各結(jié)點(diǎn)的內(nèi)容。線性結(jié)構(gòu)中的所有結(jié)點(diǎn)按它們之間的關(guān)系可以排成一個(gè)線性序列：k1，k2，?，kn其中k1是開始結(jié)點(diǎn)，kn是終端結(jié)點(diǎn)，ki是ki+1的前驅(qū)結(jié)點(diǎn)，而ki+1是ki的后繼結(jié)點(diǎn)(i=1，2，?，n-1)。通常把上述線性序列稱為“線性表”，把線性結(jié)構(gòu)中的結(jié)點(diǎn)稱為元素或“表目”。將一個(gè)線性表存放到計(jì)算機(jī)中，可以采用不同的方法，其中最簡單而自然的就是順序的方法，即把表目按其索引值從小到大一個(gè)接一個(gè)地存放在相鄰的單元里。順序方法存儲(chǔ)的線性表簡稱“順序表”，順序表是一種緊湊結(jié)構(gòu)。常用的鏈表有單鏈表和雙鏈表。在單鏈表中分配給每個(gè)結(jié)點(diǎn)的存儲(chǔ)單元可分為兩個(gè)部分：一部分存放結(jié)點(diǎn)的數(shù)據(jù)，稱為data域，另一部分存放指向結(jié)點(diǎn)后續(xù)結(jié)點(diǎn)的指針，稱為next域，終端結(jié)點(diǎn)沒有后繼結(jié)點(diǎn)，其next域?yàn)镹ULL，在計(jì)算機(jī)中可以表示成零或負(fù)數(shù)，另外還需要一個(gè)表頭變量head指向鏈表的第一個(gè)結(jié)點(diǎn)。其中k1是開始結(jié)點(diǎn)，kn是終端結(jié)點(diǎn)，ki是ki+1的前驅(qū)結(jié)點(diǎn)，而ki+1是ki的后繼結(jié)點(diǎn)(i=1，2，?，n-1)。通常把上述線性序列稱為“線性表”，把線性結(jié)構(gòu)中的結(jié)點(diǎn)稱為元素或“表目”。將一個(gè)線性表存放到計(jì)算機(jī)中，可以采用不同的方法，其中最簡單而自然的就是順序的方法，即把表目按其索引值從小到大一個(gè)接一個(gè)地存放在相鄰的單元里。順序方法存儲(chǔ)的線性表簡稱“順序表”，順序表是一種緊湊結(jié)構(gòu)。常用的鏈表有單鏈表和雙鏈表。在單鏈表中分配給每個(gè)結(jié)點(diǎn)的存儲(chǔ)單元可分為兩個(gè)部分：一部分存放結(jié)點(diǎn)的數(shù)據(jù)，稱為data域，另一部分存放指向結(jié)點(diǎn)后續(xù)結(jié)點(diǎn)的指針，稱為next域，終端結(jié)點(diǎn)沒有后繼結(jié)點(diǎn)，其next域?yàn)镹ULL，在計(jì)算機(jī)中可以表示成零或負(fù)數(shù)，另外還需要一個(gè)表頭變量head指向鏈表的第一個(gè)結(jié)點(diǎn)。7.3.4教學(xué)過程算法的實(shí)現(xiàn)：viewplaincopyprint?importjava.util.ArrayList;importjava.util.Iterator;importjava.util.List;publicclassTest{publicstaticvoidmain(String[]args){Listlist=newArrayList();list.add(3);list.add(2);list.add(10);list.add(4);list.add(70);線性結(jié)構(gòu)中的所有結(jié)點(diǎn)按它們之間的關(guān)系可以排成一個(gè)線性序列：k1，k2，?，kn其中k1是開始結(jié)點(diǎn)，kn是終端結(jié)點(diǎn)，ki是ki+1的前驅(qū)結(jié)點(diǎn)，而ki+1是ki的后繼結(jié)點(diǎn)(i=1，2，?，n-1)。通常把上述線性序列稱為“線性表”，把線性結(jié)構(gòu)中的結(jié)點(diǎn)稱為元素或“表目”。為了避免生成那些不可能產(chǎn)生最佳解的問題狀態(tài)，要不斷地利用限界函數(shù)(boundingfunction)來處死那些實(shí)際上不可能產(chǎn)生所需解的活結(jié)點(diǎn)，以減少問題的計(jì)算量。這種具有限界函數(shù)的深度優(yōu)先生成法稱回溯法。對(duì)于有n種可選物品的0/1背包問題，其解空長度為n的0-1向量組成,可用子集數(shù)表示。在搜索解空間樹時(shí)，只要其左兒子結(jié)點(diǎn)是一個(gè)可行結(jié)點(diǎn)，搜索就進(jìn)入左子樹。當(dāng)右子樹中有可能包含最優(yōu)解時(shí)就進(jìn)入右子樹搜索。分支限界法類似于回溯法，也是在問題的解空間上搜索問題解的算法。一般情況下，分支限界法與回溯法的求解目標(biāo)不同?；厮莘ǖ那蠼饽繕?biāo)是找出解空間中滿足約束條件的所有解，而分支限界法的求解目標(biāo)則是找出滿足約束條件的一個(gè)解，或是在滿足約束條件的解中找出使某一目標(biāo)函數(shù)值達(dá)到極大或極小的解，即在某種意義下的最優(yōu)解。首先，要對(duì)輸入數(shù)據(jù)進(jìn)行預(yù)處理，將各物品依其單位重量價(jià)值從大到小進(jìn)行排列。在下面描述的優(yōu)先隊(duì)列分支限界法中，節(jié)點(diǎn)的優(yōu)先級(jí)由已裝袋的物品價(jià)值加上剩下的最大單位重量價(jià)值的物品裝滿剩余容量的價(jià)值和。算法首先檢查當(dāng)前擴(kuò)展結(jié)點(diǎn)的左兒子結(jié)點(diǎn)的可行性。如果該左兒子結(jié)點(diǎn)是可行結(jié)點(diǎn)，則將它加入到子集樹和活結(jié)點(diǎn)優(yōu)先隊(duì)列中。當(dāng)前擴(kuò)展結(jié)點(diǎn)的右兒子結(jié)點(diǎn)一定是可行結(jié)點(diǎn)，僅當(dāng)右兒子結(jié)點(diǎn)滿足上界約束時(shí)才將它加入子集樹和活結(jié)點(diǎn)優(yōu)先隊(duì)列。當(dāng)擴(kuò)展到葉節(jié)點(diǎn)時(shí)為問題的最優(yōu)值。算法的實(shí)現(xiàn)：intp;//物體價(jià)值};structHEAP//堆元素結(jié)構(gòu)體{KNAPNODE*p;//結(jié)點(diǎn)數(shù)據(jù)intb;//所指結(jié)點(diǎn)的上界};//交換兩個(gè)堆元素voidswap(HEAP&a,HEAP&b){HEAPtemp=a;a=b;b=temp;}//堆中元素上移voidmov_up(HEAPH[],inti){booldone=false;if(i!=1){while(!done&&i!=1){if(H[i].b>H[i/2].b){swap(H[i],H[i/2]);}else{done=true;}i=i/2;}}}//堆中元素下移voidmov_down(HEAPH[],intn,inti){booldone=false;if((2*i)<=n){while(!done&&((i=2*i)<=n)){if(i+1<=n&&H[i+1].b>H[i].b){i++;}if(H[i/2].b<H[i].b){swap(H[i/2],H[i]);}else{done=true;}}}}//往堆中插入結(jié)點(diǎn)voidinsert(HEAPH[],HEAPx,int&n){n++;H[n]=x;mov_up(H,n);}//刪除堆中結(jié)點(diǎn)voiddel(HEAPH[],int&n,inti){HEAPx,y;x=H[i];y=H[n];n--;if(i<=n){H[i]=yif(y.b>=x.){mov_up(H,i);}else{mov_down(H,n,i);}}}//獲得堆頂元素并刪除HEAPdel_top(HEAPH[],int&n){HEAPx=H[1];del(H,n,1);returnx;}//計(jì)算分支節(jié)點(diǎn)的上界voidbound(KNAPNODE*node,intM,goodsa[],intn){inti=node->k;floatw=node->w;floatp=node->p;if(node->w>M){//物體重量超過背包載重量node->b=0;//上界置為0}else{while((w+a[i].w<=M)&&(i<n)){w+=a[i].w;//計(jì)算背包已裝入載重p+=a[i++].p;//計(jì)算背包已裝入價(jià)值}if(i<n){node->b=p+(M-w)*a[i].p/a[i].w;}else{node->b=p;}}}//用分支限界法實(shí)現(xiàn)0/1背包問題intKnapSack4(intn,goodsa[],intC,intX[]){inti,k=0;//堆中元素個(gè)數(shù)的計(jì)數(shù)器初始化為0intv;KNAPNODE*xnode,*ynode,*znode;HEAPx,y,z,*heap;heap=newHEAP[n*n];//分配堆的存儲(chǔ)空間for(i=0;i<n;i++){a[i].sign=i;//記錄物體的初始編號(hào)}sort(a,a+n,m);//對(duì)物體按照價(jià)值重量比排序xnode=newKNAPNODE;//建立父親結(jié)點(diǎn)for(i=0;i<n;i++){//初始化結(jié)點(diǎn)xnode->s1[i]=false;}xnode->k=xnode->w=xnode->p=0;while(xnode->k<n){ynode=newKNAPNODE;//建立結(jié)點(diǎn)y*ynode=*xnode;//結(jié)點(diǎn)x的數(shù)據(jù)復(fù)制到結(jié)點(diǎn)yynode->s1[ynode->k]=true;//裝入第k個(gè)物體ynode->w+=a[ynode->k].w;//背包中物體重量累計(jì)ynode->p+=a[ynode->k].p;//背包中物體價(jià)值累計(jì)ynode->k++;//搜索深度++bound(ynode,C,a,n);//計(jì)算結(jié)點(diǎn)y的上界y.b=ynode->b;y.p=ynode;insert(heap,y,k);//結(jié)點(diǎn)y按上界的值插入堆中znode=newKNAPNODE;//建立結(jié)點(diǎn)z*znode=*xnode;//結(jié)點(diǎn)x的數(shù)據(jù)復(fù)制到結(jié)點(diǎn)zznode->k++;