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

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

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

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

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

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 (有機(jī)工社影印版)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è)的目標(biāo)主觀上是從期望目標(biāo)出發(fā)的, 不是為了替代哪些課程。n但客觀上，修讀本課程的學(xué)生 不需另外修讀下列課程：q計(jì)算機(jī)導(dǎo)論(如果那個導(dǎo)論是“導(dǎo)思維”的

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

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

10、無限n1-14：算法的效率n1-15：問題的難度n1-16：基本計(jì)算模型與不可 計(jì)算性n1-17：并行與并發(fā)n1-18：模算術(shù)與費(fèi)馬小定理論域2：經(jīng)典數(shù)據(jù)結(jié)構(gòu)與算法n2-01：算法問題與解題的算法n2-02：組合與計(jì)數(shù)n2-03：分治法與遞歸n2-04：遞歸及其數(shù)學(xué)基礎(chǔ)n2-05：離散概率基礎(chǔ)n2-06：概率分析與隨機(jī)算法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)等價(jià)關(guān)系的 數(shù)據(jù)結(jié)構(gòu)n2-15：圖的基本概念n2-16：圖的計(jì)算機(jī)表示與遍歷n2-17：樹的數(shù)學(xué)性質(zhì)

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

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