面向問題求解的學(xué)習(xí)和實(shí)踐

1、面向問題求解的學(xué)習(xí)和實(shí)踐陶先平南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系目錄為什么我們命名這個(gè)兩年的課程是“問題求解”我們學(xué)習(xí)過哪些問題求解的基本知識(shí)？我們的問題求解能力訓(xùn)練到底如何？圍繞問題求解的課程體系課程體系的線索課程體系主線之一：理論與方法（解決問題的方法）；課程體系主線之二：支撐與平臺(tái)（平臺(tái)與系統(tǒng)支撐）準(zhǔn)入計(jì)算思維程序基礎(chǔ)離散數(shù)學(xué)數(shù)字邏輯電路準(zhǔn)出數(shù)據(jù)結(jié)構(gòu)算法設(shè)計(jì)與分析計(jì)算機(jī)系統(tǒng)基礎(chǔ)操作系統(tǒng)計(jì)算機(jī)網(wǎng)絡(luò)計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)平臺(tái)課程計(jì)算機(jī)系統(tǒng)設(shè)計(jì)綜合實(shí)驗(yàn)大數(shù)據(jù)處理綜合實(shí)驗(yàn)軟件工程綜合實(shí)驗(yàn)綜合實(shí)驗(yàn)理論與算法平臺(tái)與系統(tǒng)“問題的求解”能力是什么？什么叫“問題的求解”？解問題的基本方法Polya的Problem

2、solving基本方法如何理解問題和制定計(jì)劃問題的形式化模糊問題的數(shù)學(xué)描述基礎(chǔ)理論數(shù)學(xué)模型算法的設(shè)計(jì)、分析及優(yōu)化含設(shè)計(jì)策略、正確性證明數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)及算法的實(shí)現(xiàn)程序設(shè)計(jì)及優(yōu)化理解問題制定計(jì)劃計(jì)劃執(zhí)行回顧檢查問題基礎(chǔ)理論1基礎(chǔ)理論2基礎(chǔ)理論n1基礎(chǔ)理論知識(shí)模型1模型2模型n1面向問題的數(shù)學(xué)模型精巧、簡明、高效的編碼算法1算法2算法n1面向問題的算法數(shù)據(jù)結(jié)構(gòu)1數(shù)據(jù)結(jié)構(gòu)2數(shù)據(jù)結(jié)構(gòu)n1面向問題的數(shù)據(jù)結(jié)構(gòu)程序=數(shù)據(jù)結(jié)構(gòu)+算法但是：背后的數(shù)學(xué)、邏輯更為關(guān)鍵傳統(tǒng)的課程體系存在的不足在于知識(shí)點(diǎn)及其應(yīng)用在時(shí)序上有錯(cuò)位程序設(shè)計(jì)課程總是難以定位復(fù)雜程序難度太大，toy級(jí)程序?qū)嵲跓o趣知識(shí)點(diǎn)及其應(yīng)用在時(shí)序上被脫節(jié)書到用

3、時(shí)已忘了數(shù)理邏輯中的命題符號(hào)化、數(shù)學(xué)歸納法和循環(huán)不變式概率論和算法時(shí)間漸進(jìn)復(fù)雜度分析知識(shí)點(diǎn)及其應(yīng)用在安排上各自為營，效率低下課程之間邊界模糊，教學(xué)目標(biāo)不明確重復(fù)太多，缺失不知我們的答案是：重構(gòu)知識(shí)體系：盡量圍繞具體問題，從理論到模型到算法到實(shí)現(xiàn)開展組織和學(xué)習(xí)消除重復(fù)，避免遺漏強(qiáng)化應(yīng)用訓(xùn)練，知識(shí)點(diǎn)學(xué)習(xí)中始終貫穿應(yīng)用場景在解問題中，不斷運(yùn)用以前學(xué)過的知識(shí)點(diǎn)以程序設(shè)計(jì)能力培養(yǎng)為貫穿全課程的基礎(chǔ)目標(biāo)將程序語言及編程的訓(xùn)練隱藏到課堂講解（引導(dǎo)環(huán)節(jié)）的”背面”穿插在各個(gè)課堂講授中自學(xué)、自練將自學(xué)能力培養(yǎng)放到足夠的高度問題1基礎(chǔ)理論1基礎(chǔ)理論2基礎(chǔ)理論n1算法1算法2算法n3基礎(chǔ)理論知識(shí)面向問題的算法模型1

4、模型2模型n2面向問題的數(shù)學(xué)模型數(shù)據(jù)結(jié)構(gòu)1數(shù)據(jù)結(jié)構(gòu)2數(shù)據(jù)結(jié)構(gòu)n4精巧、簡明、高效的編碼面向問題的數(shù)據(jù)結(jié)構(gòu)問題2問題n0形成全新的課程內(nèi)容體系整個(gè)課程內(nèi)容不是按照傳統(tǒng)數(shù)學(xué)與計(jì)算機(jī)類課程各自的橫向體系劃分，而是圍繞問題求解組織成四個(gè)“論域”：第一個(gè)論域“計(jì)算入門與數(shù)學(xué)證明”安排在1年級(jí)上學(xué)期；第二個(gè)論域“經(jīng)典數(shù)據(jù)結(jié)構(gòu)與算法”安排在1年級(jí)下學(xué)期;第三個(gè)論域“典型應(yīng)用問題及其求解方法”安排在2年級(jí)上學(xué)期;第四個(gè)論域“復(fù)雜性理論初步與難問題的算法”安排在2年級(jí)下學(xué)期。上述內(nèi)容涵蓋了傳統(tǒng)基礎(chǔ)課程：程序設(shè)計(jì)、離散數(shù)學(xué)、數(shù)據(jù)結(jié)構(gòu)、算法設(shè)計(jì)與分析希望新體系帶來的好處：學(xué)以致用，緩解“學(xué)這些東西有啥用”的焦慮；壓

5、縮冗余，接觸更多的內(nèi)容；學(xué)會(huì)學(xué)習(xí)，開啟終身學(xué)習(xí)模式。四個(gè)論域論域1：計(jì)算入門與數(shù)學(xué)證明幫助學(xué)生理解計(jì)算思維最核心的概念，接受基本的形式化訓(xùn)練，掌握抽象數(shù)學(xué)證明的基本方法。論域2：經(jīng)典數(shù)據(jù)結(jié)構(gòu)與算法幫助學(xué)生理解抽象數(shù)據(jù)類型，理解并應(yīng)用常用的數(shù)據(jù)結(jié)構(gòu)掌握重要的算法設(shè)計(jì)策略以及算法設(shè)計(jì)與分析的基本理論與方法理解并能夠應(yīng)用支持上述內(nèi)容的離散數(shù)學(xué)工具與方法。論域3：典型應(yīng)用問題及其求解方法引導(dǎo)學(xué)生掌握典型應(yīng)用中抽象出來的重要算法問題的求解方法，理解并能夠應(yīng)用支持上述內(nèi)容的離散數(shù)學(xué)工具與方法。論域4：復(fù)雜性理論基礎(chǔ)與“難”問題的算法涵蓋問題求解中復(fù)雜性理論的基本內(nèi)容與問題規(guī)約方法，解決“難”問題的主要方法

6、、技術(shù)以及相關(guān)的重要理論結(jié)果。論題的結(jié)構(gòu)模型及實(shí)施方案解題能力學(xué)習(xí)能力自學(xué)材料(教材)課程講義課外作業(yè)編程訓(xùn)練研討內(nèi)容經(jīng)典教材摘選學(xué)生課前自學(xué)以解題為目的以深度為優(yōu)先以啟發(fā)為手段教師選題學(xué)生講解教材中的習(xí)題為主覆蓋全部自學(xué)內(nèi)容圍繞論題選編題目問題求解2年中的核心價(jià)值點(diǎn)形式化和證明方法抽象數(shù)據(jù)類型及數(shù)據(jù)結(jié)構(gòu)算法復(fù)雜度評(píng)估算法設(shè)計(jì)策略若干經(jīng)典問題的數(shù)學(xué)模型及算法難問題的“難” 以及我們的妥協(xié)妥協(xié)中的堅(jiān)持所有的一切，歸根結(jié)底，體現(xiàn)為：程序設(shè)計(jì)能力（狹義上的問題求解）形式化及證明方法命題邏輯及謂詞邏輯如何用人工（數(shù)學(xué)）語言重述自然語言的事實(shí)或者過程消除歧義、嚴(yán)謹(jǐn)過程如何建立一個(gè)一致的、完備的系統(tǒng)基本證

7、明方法及這些方法的邏輯基礎(chǔ)推理/演繹歸納遞歸、數(shù)學(xué)歸納法算法正確性證明算法復(fù)雜度評(píng)估組合和計(jì)數(shù)在算法分析中也經(jīng)常用到離散概率模型隨機(jī)變量、指示器隨機(jī)變量、期望算法的時(shí)間漸進(jìn)復(fù)雜度Worst case VS Average case VS Best case遞歸式求解O標(biāo)記算法復(fù)雜度的若干話題問題的難度和算法的復(fù)雜度容易的問題 VS 難的問題我們的妥協(xié)數(shù)學(xué)模型、抽象數(shù)據(jù)類型及數(shù)據(jù)結(jié)構(gòu)典型的離散數(shù)學(xué)模型集合及其上的關(guān)系、函數(shù)偏序、格圖、樹ADT的“抽象” VS 數(shù)據(jù)結(jié)構(gòu)的“具體”ADT：動(dòng)態(tài)集合的基本數(shù)據(jù)類型 + 獨(dú)有的數(shù)據(jù)特性和基本操作維持?jǐn)?shù)據(jù)特性的“建增刪查改”特別的操作經(jīng)典的數(shù)據(jù)結(jié)構(gòu)：隊(duì)列、

8、堆、棧、鏈表、樹（基本的經(jīng)典）、并查集紅黑樹、B樹圖算法設(shè)計(jì)基本策略暴力法分治法歸并、快速排序、Strassen算法遞歸和分治的天然關(guān)聯(lián)Master定理動(dòng)態(tài)規(guī)劃法任何一個(gè)動(dòng)態(tài)規(guī)劃算法都和一個(gè)遞歸表達(dá)式關(guān)聯(lián)最優(yōu)子結(jié)構(gòu)特性用空間換時(shí)間：子問題拓?fù)渑判蚧蛘咦訂栴}結(jié)果被暫存Rod-cut問題（每個(gè)人心中都必須有一個(gè)經(jīng)典場景）貪心法貪心選擇性質(zhì)最小生成樹、哈夫曼編碼算法的正確性證明循環(huán)不變式反證法若干經(jīng)典問題的數(shù)學(xué)模型及算法圖模型及其算法集：圖的建模：圖本身+問題的抽象遍歷：skeleton of almost every graph algorithm路徑相關(guān)算法: 最短路旅行算法最大流最小割原理：最

9、大流算法匹配和覆蓋算法著色若干經(jīng)典問題的數(shù)學(xué)模型及算法編碼及糾錯(cuò)代數(shù)系統(tǒng)、群（群的對(duì)稱性）碼字和Hamming 距離編碼和糾錯(cuò)Hashing方法作用和基本原理沖突解決我們學(xué)到的僅僅是“冰山一角”矩陣計(jì)算：LUP算法線性規(guī)劃松弛，simplex算法若干經(jīng)典問題的數(shù)學(xué)模型及算法數(shù)論算法模算術(shù)、擴(kuò)充的GCD算法，還有？費(fèi)馬定理和歐拉定理素?cái)?shù)判定算法偽素?cái)?shù)密碼算法公鑰體系的數(shù)學(xué)和算法基礎(chǔ)我們把什么公布出去了？把什么藏起來了？難問題的“難” 以及我們的妥協(xié)形式化描述文字、語言、元組P、NP、NPC判定、優(yōu)化問題如何證明一個(gè)問題的難我們的妥協(xié)近似、隨機(jī)、啟發(fā)我們在妥協(xié)中的堅(jiān)持你能說出多少？問題求解能力：程序設(shè)計(jì)能力曲不離口，拳不離手程序設(shè)計(jì)能力是每個(gè)專業(yè)人才的終極能力程序設(shè)計(jì)能力的形成，始終貫穿于每一門課程中程序設(shè)計(jì)能力