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

1、計算機問題求解 - 傳統(tǒng)計算機專業(yè)基礎(chǔ)課程的整合與實踐整合與實踐代開場白“復雜工程問題復雜工程問題”必須具備下述特征（1），同時具備下述特征（2）-（7）的部分或全部：q（1）必須運用深入的工程原理經(jīng)過分析才可能得到解決；）必須運用深入的工程原理經(jīng)過分析才可能得到解決；q（2）需求涉及多方面的技術(shù)、工程和其它因素，并可能相互有一定沖突；q（3）需要通過建立合適的抽象模型才能解決，在建模過程中需要體現(xiàn)出創(chuàng)造性；q（4）不是僅靠常用方法就可以完全解決的；q（5）問題中涉及的因素可能沒有完全包含在專業(yè)標準和規(guī)范中；q（6）問題相關(guān)各方利益不完全一致；q（7）具有較高的綜合性，包含多個相互關(guān)聯(lián)的子問題

2、。如何將培養(yǎng)學生解決“復雜問題”的能力貫穿與本科四年教學的始終？- 摘自中國工程教育專業(yè)認證通用標準2015年版前言關(guān)鍵在于:上課究竟是為了什么?我們?nèi)绾谓ㄔO(shè)一門課程1. 學生2. 課程目標3. 考核要求5. 課程內(nèi)容6. 上課方式7. 支持條件4.持續(xù)改進學生為什么需要這個課？要讓學生得到什么？如何判定？通過什么內(nèi)容來實現(xiàn)目標？什么上課方式對這樣的內(nèi)容最有效？問題問題:怎樣才是以學生為中心怎樣才是以學生為中心?如果我們的目標是培養(yǎng)學生的“研究能力”，那么必須回答：什么是“研究能力”？怎么才能讓學生“得到”，而不是“應該得到”？意識、知識、能力、技能。任何一門課不應該以灌輸知識為唯一目標！任何

3、一門課不應該以灌輸知識為唯一目標！目標決定方式n一般原則：q意識：熏陶與引導q知識：梳理和講解q能力：指導下的實踐q技能：足夠的訓練n做到“無縫連接”，應該是我們的追求。當然是因為我們覺得現(xiàn)在的教學有問題。問題：問題：“關(guān)鍵問題關(guān)鍵問題”究竟是什么究竟是什么?主問題：思維與能力；輔問題：學生學習動力問題：問題：我們需要什么能力？學我們需要什么能力？學生如何得到能力？生如何得到能力？解決問題；終身學習課程建設(shè)的動機n基本認識：q學生能力不足受到普遍關(guān)注；q其重要原因之一是課程教學沒有能夠很好地承擔能力培養(yǎng)的任務；n課程教學是整個教學活動的主體n能力培養(yǎng)過多依賴高年級綜合課程和畢業(yè)設(shè)計n考試成績不

4、能反映學生實際能力q特別是專業(yè)基礎(chǔ)課程本應在能力培養(yǎng)方面發(fā)揮重要作用。n改革的切入點q專業(yè)基礎(chǔ)課程在能力培養(yǎng)方面的作用以及實施方案課程目標n本課程期望學生在以下四個方面達成目標:q意識：建立在計算機科學領(lǐng)域持續(xù)追求效率更高，質(zhì)量更好的算法的創(chuàng)新意識；q知識：掌握能支持在計算機科學領(lǐng)域進行探索所需的離散數(shù)學、問題建模、數(shù)據(jù)抽象、算法設(shè)計與分析、算法復雜性理論等方面的基礎(chǔ)知識；q能力：n具備分析問題，并采用一定策略進行算法設(shè)計的能力，并能對算法進行基本分析的能力；n具備自我探索學習，并凝練問題的能力；q技能：掌握熟練使用C+語言及其開發(fā)環(huán)境, 實現(xiàn)能正確運行的程序的技能。本課程教學基本理念指定教材

5、索引 教科書nDH: David Harel, etc.: Algorithmics the Spirit of Computing, 3rd ed. Pearson Education, 2004 (有高教社影印版)nUD: Ulrich Daepp, etc.: Reading, Writing, and Proving a Closer Look at Mathematics, Springer-Verlag, 2003(有清華社影印版)nCS: Clifford Stein, etc.: Discrete Mathematics for Computer Scientists, Pea

6、rson Education, 2011 (有電子社影印版)nCZ: Gary Chartrand, etc.: A First Course in Graph Theory, Dover 2012 (有郵電社影印版)nTC: Thomas Cormen: Introduction to Algorithms, 3rd ed. MIT, 2009 (有機工社影印版)nTJ: Thomas Judson: Abstract Algebra Theory and Applications, GNU, 1997nJH: Juarj Hromkovic: Algorithmics for Hard P

7、roblems Introduction to Combinatorial Optimization, Randomization, Approximation, and Heuristics, 2nd ed. Springer, 2004nWS: Walter Savitch: Problem Solving with C+, 7th ed. Pearson Education, 2009 (有清華社影印版)關(guān)于本課程與傳統(tǒng)課程的關(guān)系n本課程建設(shè)的目標主觀上是從期望目標出發(fā)的, 不是為了替代哪些課程。n但客觀上，修讀本課程的學生 不需另外修讀下列課程：q計算機導論(如果那個導論是“導思維”的

8、)q離散數(shù)學q程序設(shè)計q數(shù)據(jù)結(jié)構(gòu)q計算機算法設(shè)計與分析四個論域及其基本要求n論域1：計算入門與數(shù)學證明q理解計算思維最核心的概念，了解計算的基本方法與局限q接受基本的形式化訓練，掌握抽象數(shù)學證明的基本方法n論域2：經(jīng)典數(shù)據(jù)結(jié)構(gòu)與算法q理解數(shù)據(jù)抽象，理解并能夠應用常用的數(shù)據(jù)結(jié)構(gòu)q掌握重要的算法設(shè)計策略，以及算法設(shè)計與分析的基本理論與方法q理解并能夠應用支持上述內(nèi)容的離散數(shù)學工具與方法n論域3：典型應用問題及其求解方法q掌握典型應用中抽象出來的重要算法問題的求解方法q理解并能夠應用支持上述內(nèi)容的離散數(shù)學工具與方法n論域4：復雜性理論初步與“難”問題的算法q掌握復雜性理論的基本內(nèi)容與問題規(guī)約方法q理

9、解解決“難”問題的主要方法、技術(shù)以及相關(guān)的重要理論結(jié)果建設(shè)初期最引起“質(zhì)疑”的問題n程序設(shè)計教學q不在課堂上“講編程”q“思想”和“基于語言的技能”分別處理n（離散）數(shù)學q希望“強化”q但“強化”的方式不是增加系統(tǒng)講授時間n“反復”和“應用”n“浸入式”論域1：計算入門與數(shù)學證明n1-01：為什么計算機能解題n1-02：什么樣的推理是正確的n1-03：常用的證明方法n1-04：基本的算法結(jié)構(gòu)n1-05：數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)n1-06：算法的描述n1-07：不同的程序設(shè)計方法n1-08：集合及其運算n1-09：關(guān)系及其基本性質(zhì)n1-10：函數(shù)n1-11：算法方法n1-12：算法正確性n1-13：有限與

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

11、n2-18：最小生成樹算法論域3：典型應用問題及其求解方法n3-01：單源最短通路算法n3-02：多源最短通路算法n3-03：圖中的匹配與覆蓋n3-04：圖的連通度與網(wǎng)絡流n3-05：最大流算法n3-06：圖論中的其它專題n3-07：矩陣計算n3-08：線性規(guī)劃n3-09：多項式與FFTn3-10：群與拉格郎日定理n3-11：環(huán)與域n3-12：數(shù)論基礎(chǔ)n3-13：數(shù)論算法n3-14：密碼算法n3-15：代數(shù)編碼n3-16：群與對稱n3-17：串匹配n3-18：計算幾何算法論域4：復雜性理論初步與“難”問題的算法n4-01：問題的形式化描述n4-02： NP完全理論初步n4-03：偽多項式算法n

12、4-04：分枝-界限算法n4-05：局部搜索算法n4-06：松弛算法n4-07：近似算法的基本概念n4-08：覆蓋問題與最大割集 問題n4-09：背包問題n4-10：旅行推銷商問題n4-11：Bin-Packing問題n4-12：隨機算法的基本概念n4-13：素性判定問題n4-14：等價測試問題n4-15：最小割集問題n4-16：可滿足問題n4-17：去隨機方法n4-18：啟發(fā)式算法課程指南與書面考試n每學期開始時將課程指南發(fā)給學生，以“周”為單位安排本學期的學習任務。q.教學珠峰計劃班教學資料2014級第2學期計算機問題求解-課程指南-2014級第2學期.docxn試題實錄q.教學珠峰計劃班教學資料2014級第1學期計算機問題求解試題-2015-01.docxq.拔尖班問題求解試題-2015-06.docx課堂實踐示例n計算入門: .教學珠峰計劃班教學資料2014級第1學期計算機問題求解-2014-10-13-基本的算法結(jié)構(gòu).pptn 數(shù)據(jù)與結(jié)構(gòu): q.教學珠峰計劃班教學資料2012級第1學期計算機問題求解-2012-10-30-數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu).pptq.教學珠峰計劃班教學資料2014級第2學期計算機問題求解-2015