計(jì)算機(jī)問題求解傳統(tǒng)計(jì)算機(jī)專業(yè)基礎(chǔ)課程的整合與實(shí)踐

計(jì)算機(jī)問題求解

-

傳統(tǒng)計(jì)算機(jī)專業(yè)基礎(chǔ)課程的

整合與實(shí)踐代開場白“復(fù)雜工程問題”必須具備下述特征（1），同時(shí)具備下述特征（2）-（7）的部分或全部：（1）必須運(yùn)用深入的工程原理經(jīng)過分析才可能得到解決；（2）需求涉及多方面的技術(shù)、工程和其它因素，并可能相互有一定沖突；（3）需要通過建立合適的抽象模型才能解決，在建模過程中需要體現(xiàn)出創(chuàng)造性；（4）不是僅靠常用方法就可以完全解決的；（5）問題中涉及的因素可能沒有完全包含在專業(yè)標(biāo)準(zhǔn)和規(guī)范中；（6）問題相關(guān)各方利益不完全一致；（7）具有較高的綜合性，包含多個(gè)相互關(guān)聯(lián)的子問題。如何將培養(yǎng)學(xué)生解決“復(fù)雜問題”的能力貫穿與本科四年教學(xué)的始終？-摘自中國工程教育專業(yè)認(rèn)證通用標(biāo)準(zhǔn)2015年版前言問題1:我們該如何建設(shè)一門課?關(guān)鍵在于:上課究竟是為了什么?我們?nèi)绾谓ㄔO(shè)一門課程1.學(xué)生2.課程目標(biāo)3.考核要求5.課程內(nèi)容6.上課方式7.支持條件4.持續(xù)改進(jìn)學(xué)生為什么需要這個(gè)課？要讓學(xué)生得到什么？如何判定？通過什么內(nèi)容來實(shí)現(xiàn)目標(biāo)？什么上課方式對這樣的內(nèi)容最有效？問題２:怎樣才是以學(xué)生為中心?如果我們的目標(biāo)是培養(yǎng)學(xué)生的“研究能力”，那么必須回答：什么是“研究能力”？怎么才能讓學(xué)生“得到”，而不是“應(yīng)該得到”？問題３：那么究竟什么是我們期望學(xué)生得到的呢？意識、知識、能力、技能。任何一門課不應(yīng)該以灌輸知識為唯一目標(biāo)！目標(biāo)決定方式一般原則：意識：熏陶與引導(dǎo)知識：梳理和講解能力：指導(dǎo)下的實(shí)踐技能：足夠的訓(xùn)練做到“無縫連接”，應(yīng)該是我們的追求。問題４：為什么我們認(rèn)為需要改革？當(dāng)然是因?yàn)槲覀冇X得現(xiàn)在的教學(xué)有問題。問題５：“關(guān)鍵問題”究竟是什么?主問題：思維與能力；輔問題：學(xué)生學(xué)習(xí)動力問題６：我們需要什么能力？學(xué)生如何得到能力？解決問題；終身學(xué)習(xí)課程建設(shè)的動機(jī)基本認(rèn)識：學(xué)生能力不足受到普遍關(guān)注；其重要原因之一是課程教學(xué)沒有能夠很好地承擔(dān)能力培養(yǎng)的任務(wù)；課程教學(xué)是整個(gè)教學(xué)活動的主體能力培養(yǎng)過多依賴高年級綜合課程和畢業(yè)設(shè)計(jì)考試成績不能反映學(xué)生實(shí)際能力特別是專業(yè)基礎(chǔ)課程本應(yīng)在能力培養(yǎng)方面發(fā)揮重要作用。改革的切入點(diǎn)專業(yè)基礎(chǔ)課程在能力培養(yǎng)方面的作用以及實(shí)施方案課程目標(biāo)本課程期望學(xué)生在以下四個(gè)方面達(dá)成目標(biāo):意識：建立在計(jì)算機(jī)科學(xué)領(lǐng)域持續(xù)追求效率更高，質(zhì)量更好的算法的創(chuàng)新意識；知識：掌握能支持在計(jì)算機(jī)科學(xué)領(lǐng)域進(jìn)行探索所需的離散數(shù)學(xué)、問題建模、數(shù)據(jù)抽象、算法設(shè)計(jì)與分析、算法復(fù)雜性理論等方面的基礎(chǔ)知識；能力：具備分析問題，并采用一定策略進(jìn)行算法設(shè)計(jì)的能力，并能對算法進(jìn)行基本分析的能力；具備自我探索學(xué)習(xí)，并凝練問題的能力；技能：掌握熟練使用C++語言及其開發(fā)環(huán)境,實(shí)現(xiàn)能正確運(yùn)行的程序的技能。本課程教學(xué)基本理念自我探索深度引導(dǎo)理論嚴(yán)密訓(xùn)練充分指定教材索引–教科書DH:DavidHarel,etc.:Algorithmics–theSpiritofComputing,3rded.PearsonEducation,2004(有高教社影印版)UD:UlrichDaepp,etc.:Reading,Writing,andProving–aCloserLookatMathematics,Springer-Verlag,2003(有清華社影印版)CS:CliffordStein,etc.:DiscreteMathematicsforComputerScientists,PearsonEducation,2011

(有電子社影印版)CZ:GaryChartrand,etc.:AFirstCourseinGraphTheory,Dover2012(有郵電社影印版)TC:ThomasCormen:IntroductiontoAlgorithms,3rded.MIT,2009

(有機(jī)工社影印版)TJ:ThomasJudson:AbstractAlgebra–TheoryandApplications,GNU,1997JH:JuarjHromkovic:AlgorithmicsforHardProblems–IntroductiontoCombinatorialOptimization,Randomization,Approximation,andHeuristics,2nded.Springer,2004WS:WalterSavitch:ProblemSolvingwithC++,7thed.PearsonEducation,2009

(有清華社影印版)關(guān)于本課程與傳統(tǒng)課程的關(guān)系本課程建設(shè)的目標(biāo)主觀上是從期望目標(biāo)出發(fā)的,不是為了替代哪些課程。但客觀上，修讀本課程的學(xué)生不需另外修讀下列課程：計(jì)算機(jī)導(dǎo)論(如果那個(gè)導(dǎo)論是“導(dǎo)思維”的)離散數(shù)學(xué)程序設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)計(jì)算機(jī)算法設(shè)計(jì)與分析四個(gè)論域及其基本要求論域1：計(jì)算入門與數(shù)學(xué)證明理解計(jì)算思維最核心的概念，了解計(jì)算的基本方法與局限接受基本的形式化訓(xùn)練，掌握抽象數(shù)學(xué)證明的基本方法論域2：經(jīng)典數(shù)據(jù)結(jié)構(gòu)與算法理解數(shù)據(jù)抽象，理解并能夠應(yīng)用常用的數(shù)據(jù)結(jié)構(gòu)掌握重要的算法設(shè)計(jì)策略，以及算法設(shè)計(jì)與分析的基本理論與方法理解并能夠應(yīng)用支持上述內(nèi)容的離散數(shù)學(xué)工具與方法論域3：典型應(yīng)用問題及其求解方法掌握典型應(yīng)用中抽象出來的重要算法問題的求解方法理解并能夠應(yīng)用支持上述內(nèi)容的離散數(shù)學(xué)工具與方法論域4：復(fù)雜性理論初步與“難”問題的算法掌握復(fù)雜性理論的基本內(nèi)容與問題規(guī)約方法理解解決“難”問題的主要方法、技術(shù)以及相關(guān)的重要理論結(jié)果建設(shè)初期最引起“質(zhì)疑”的問題程序設(shè)計(jì)教學(xué)不在課堂上“講編程”“思想”和“基于語言的技能”分別處理（離散）數(shù)學(xué)希望“強(qiáng)化”但“強(qiáng)化”的方式不是增加系統(tǒng)講授時(shí)間“反復(fù)”和“應(yīng)用”“浸入式”論域1：計(jì)算入門與數(shù)學(xué)證明1-01：為什么計(jì)算機(jī)能解題1-02：什么樣的推理是正確的1-03：常用的證明方法1-04：基本的算法結(jié)構(gòu)1-05：數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)1-06：算法的描述1-07：不同的程序設(shè)計(jì)方法1-08：集合及其運(yùn)算1-09：關(guān)系及其基本性質(zhì)1-10：函數(shù)1-11：算法方法1-12：算法正確性1-13：有限與無限1-14：算法的效率1-15：問題的難度1-16：基本計(jì)算模型與不可

計(jì)算性1-17：并行與并發(fā)1-18：模算術(shù)與費(fèi)馬小定理論域2：經(jīng)典數(shù)據(jù)結(jié)構(gòu)與算法2-01：算法問題與解題的算法2-02：組合與計(jì)數(shù)2-03：分治法與遞歸2-04：遞歸及其數(shù)學(xué)基礎(chǔ)2-05：離散概率基礎(chǔ)2-06：概率分析與隨機(jī)算法2-07：排序與選擇2-08：基本數(shù)據(jù)結(jié)構(gòu)2-09：堆與堆排序2-10：Hashing方法2-11：搜索樹2-12：動態(tài)規(guī)劃2-13：貪心算法2-14：用于動態(tài)等價(jià)關(guān)系的

數(shù)據(jù)結(jié)構(gòu)2-15：圖的基本概念2-16：圖的計(jì)算機(jī)表示與遍歷2-17：樹的數(shù)學(xué)性質(zhì)2-18：最小生成樹算法論域3：典型應(yīng)用問題及其求解方法3-01：單源最短通路算法3-02：多源最短通路算法3-03：圖中的匹配與覆蓋3-04：圖的連通度與網(wǎng)絡(luò)流3-05：最大流算法3-06：圖論中的其它專題3-07：矩陣計(jì)算3-08：線性規(guī)劃3-09：多項(xiàng)式與FFT3-10：群與拉格郎日定理3-11：環(huán)與域3-12：數(shù)論基礎(chǔ)3-13：數(shù)論算法3-14：密碼算法3-15：代數(shù)編碼3-16：群與對稱3-17：串匹配3-18：計(jì)算幾何算法論域4：復(fù)雜性理論初步與“難”問題的算法4-01：問題的形式化描述4-02：NP完全理論初步4-03：偽多項(xiàng)式算法4-04：分枝-界限算法4-05：局部搜索算法4-06：松弛算法4-07：近似算法的基本概念4-08：覆蓋問題與最大割集

問題4-09：背包問題4-10：旅行推銷商問題4-11：Bin-Packing問題4-12：隨機(jī)算法的基本概念4-13：素性判定問題4-14：等價(jià)測試問題4-15：最小割集問題4-16：可滿足問題4-17：去隨機(jī)方法4-18：啟發(fā)式算法課程指南與書面考試每學(xué)期開始時(shí)將課程指南發(fā)給學(xué)生，以“周”為單位安排本學(xué)期的學(xué)習(xí)任務(wù)。..\教學(xué)\珠峰計(jì)劃班教學(xué)資料\2014級\第2學(xué)期\計(jì)算機(jī)問題求解-課程指南-2014級第2學(xué)期.docx試題實(shí)錄..\教學(xué)\珠峰計(jì)劃班教學(xué)資料\2014級\第1學(xué)期\計(jì)算機(jī)問題求解試題-2015-01.docx..\拔尖班問題求解試題-2015-06.docx課堂實(shí)踐示例計(jì)算入門:

..\教學(xué)\珠峰計(jì)劃班教學(xué)資料\2014級\第1學(xué)期\計(jì)算機(jī)問題求解-2014-10-13-基本的算法結(jié)構(gòu).ppt

數(shù)據(jù)與結(jié)構(gòu):

..\教學(xué)\珠峰計(jì)劃班教學(xué)資料\2012級\第1學(xué)期\計(jì)算機(jī)問題求解-2012-10-30-數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu).ppt..\教學(xué)\珠峰計(jì)劃班教學(xué)資料\2014級\第2學(xué)期\計(jì)算機(jī)問題求解-2015-04-20-基本的數(shù)