計算機問題求解

-

傳統計算機專業基礎課程的

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

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

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

計算性1-17：并行與并發1-18：模算術與費馬小定理論域2：經典數據結構與算法2-01：算法問題與解題的算法2-02：組合與計數2-03：分治法與遞歸2-04：遞歸及其數學基礎2-05：離散概率基礎2-06：概率分析與隨機算法2-07：排序與選擇2-08：基本數據結構2-09：堆與堆排序2-10：Hashing方法2-11：搜索樹2-12：動態規劃2-13：貪心算法2-14：用于動態等價關系的

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

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

..\教學\珠峰計劃班教學資料\2014級\第1學期\計算機問題求解-2014-10-13-基本的算法結構.ppt

數據與結構:

..\教學\珠峰計劃班教學資料\2012級\第1學期\計算機問題求解-2012-10-30-數據與數據結構.ppt..\教學\珠峰計劃班教學資料\2014級\第2學期\計算機問題求解-2015-04-20-基本的數