數(shù)據(jù)結(jié)構(gòu)章節(jié)程知識體系和教學(xué)實(shí)踐.ppt

數(shù)據(jù)結(jié)構(gòu)課程 知識體系和教學(xué)實(shí)踐,張 銘,北京大學(xué)信息科學(xué)與技術(shù)學(xué)院 /mzhang/ds/ 2005年高等學(xué)校計(jì)算機(jī)系列課程教師培訓(xùn)暨教學(xué)研討會 山東煙臺師范學(xué)院 2005年8月,北京大學(xué)信息學(xué)院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 2,內(nèi)容提要,一、知識體系 二、教學(xué)實(shí)踐 三、教學(xué)案例,北京大學(xué)信息學(xué)院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 3,一、知識體系,1.數(shù)據(jù)的定義 2.算法的效率問題 3.抽象數(shù)據(jù)類型,北京大學(xué)信息學(xué)院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 4,1. 數(shù)據(jù)結(jié)構(gòu)的定義,數(shù)據(jù)的邏輯結(jié)構(gòu) 數(shù)據(jù)的存儲結(jié)構(gòu) 數(shù)據(jù)的運(yùn)算,北京大學(xué)信息學(xué)院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 5,常見的邏輯關(guān)系,線性結(jié)構(gòu) 樹形結(jié)構(gòu) 圖結(jié)構(gòu) 文件結(jié)構(gòu) 圖樹二叉樹線性表,北京大學(xué)信息學(xué)院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 6,常見的存儲方法,順序方法 鏈接方法 索引方法（線性、樹形 ） 散列方法,北京大學(xué)信息學(xué)院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 7,運(yùn)算,建立、清除數(shù)據(jù)結(jié)構(gòu) 插入一個新數(shù)據(jù)元素 刪除、修改某個數(shù)據(jù)元素 排序 檢索,北京大學(xué)信息學(xué)院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 8,一、知識體系,1.數(shù)據(jù)的定義 2.算法的效率問題 3.抽象數(shù)據(jù)類型,北京大學(xué)信息學(xué)院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 9,算法效率的基本問題權(quán)衡,對于給定的一類問題 算法需要多少存儲空間和時間？ 最好算法的最壞情況是什么？ 平均來說，算法的運(yùn)行好到何種程度？ 算法一般化到何種程度？ 什么情況下，最好的算法是什么？ 算法分析技術(shù),北京大學(xué)信息學(xué)院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 10,一、知識體系,1.數(shù)據(jù)的定義 2.算法的效率問題 3.抽象數(shù)據(jù)類型,北京大學(xué)信息學(xué)院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 11,抽象數(shù)據(jù)類型ADT,抽象數(shù)據(jù)類型是定義了一組運(yùn)算的數(shù)學(xué)模型 把數(shù)據(jù)結(jié)構(gòu)的存儲與實(shí)現(xiàn)細(xì)節(jié)剝離 在適當(dāng)?shù)某橄髮哟紊峡紤]程序的結(jié)構(gòu)和算法 封裝和信息隱蔽,北京大學(xué)信息學(xué)院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 12,二、教學(xué)實(shí)踐,1. 教學(xué)目的 2. 教材編寫 3. 教學(xué)策略,北京大學(xué)信息學(xué)院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 13,數(shù)據(jù)結(jié)構(gòu)課程的主要內(nèi)容,理論 算法的數(shù)學(xué)基礎(chǔ) 算法的時間和空間度量 抽象 排序、檢索等重要問題類的有效算法 重要數(shù)據(jù)結(jié)構(gòu)技術(shù) 設(shè)計(jì) 算法的選擇、實(shí)現(xiàn)和測試,北京大學(xué)信息學(xué)院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 14,教學(xué)目的,“數(shù)據(jù)結(jié)構(gòu)算法程序” 把數(shù)據(jù)結(jié)構(gòu)和算法理論與編程實(shí)踐相結(jié)合 能夠在實(shí)際的工程實(shí)踐中靈活地予以應(yīng)用 培養(yǎng)數(shù)據(jù)抽象的能力 提高程序設(shè)計(jì)的質(zhì)量,北京大學(xué)信息學(xué)院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 15,二、教學(xué)實(shí)踐,1. 教學(xué)目的 2. 教材編寫 3. 教學(xué)策略,北京大學(xué)信息學(xué)院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 16,教材編寫,許卓群、楊冬青、唐世渭、張銘，數(shù)據(jù)結(jié)構(gòu)與算法，高等教育出版社，2004年 7月。ISBN 7-04-014616-9。 張銘、趙海燕、王騰蛟，數(shù)據(jù)結(jié)構(gòu)與算法學(xué)習(xí)指導(dǎo)與習(xí)題解析，高等教育出版社，2004年 9月。ISBN 7-04-017829-X。,北京大學(xué)信息學(xué)院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 17,數(shù)據(jù)結(jié)構(gòu)與算法,C+模板, 抽象數(shù)據(jù)類型(ADT) 第1章概論 數(shù)據(jù)結(jié)構(gòu)的定義 抽象數(shù)據(jù)類型 基本的算法分析技術(shù) 第2-6章 從邏輯結(jié)構(gòu)的角度系統(tǒng)地介紹各種基本數(shù)據(jù)結(jié)構(gòu) 線性表、字符串、二叉樹、樹和圖,北京大學(xué)信息學(xué)院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 18,第7章 內(nèi)排序 第8章 文件與外排序 第9章 檢索 第10章 索引 第11章 高級線性結(jié)構(gòu) 第12章 高級樹形結(jié)構(gòu) Patricia樹、伸展樹，k-d樹、PR四分樹、R*樹,北京大學(xué)信息學(xué)院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 19,數(shù)據(jù)結(jié)構(gòu)與算法學(xué)習(xí)指導(dǎo)與習(xí)題詳解,第1-12章，涵蓋了主教材的基本內(nèi)容 主教材重要的數(shù)據(jù)結(jié)構(gòu)和算法知識點(diǎn)、學(xué)習(xí)重點(diǎn)和難點(diǎn) 習(xí)題詳解 第13章上機(jī)報告 ACM競賽：窮舉、回溯、分治、搜索、DP 實(shí)習(xí)報告要求和樣例 第14章為考試題及其解答 2004年秋季學(xué)期的期中、期末考題和答案 1999-2005年北大研究生入學(xué)考試,北京大學(xué)信息學(xué)院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 20,習(xí)題詳解,212道習(xí)題、53道上機(jī)題 題意分析、邊界處理提示 典型解法（算法描述） 算法代價分析 典型錯誤 170道新習(xí)題，40道新上機(jī)題,北京大學(xué)信息學(xué)院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 21,二、教學(xué)實(shí)踐,1. 教學(xué)目的 2. 教材編寫 3. 教學(xué)策略,北京大學(xué)信息學(xué)院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 22,（1）啟發(fā)式教學(xué),數(shù)學(xué)特性 抽象數(shù)據(jù)類型 不同的存儲方法 不同存儲方法的可能算法 結(jié)合算法分析來討論各種存儲方法和算法的利弊，摒棄不適宜的方法,北京大學(xué)信息學(xué)院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 23,（2）引進(jìn)新理論技術(shù),“搜索引擎”中的數(shù)據(jù)結(jié)構(gòu)技術(shù) 圖搜索 排序 索引技術(shù),北京大學(xué)信息學(xué)院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 24,（3）加強(qiáng)實(shí)踐環(huán)節(jié)的訓(xùn)練,數(shù)據(jù)結(jié)構(gòu)與算法， 3學(xué)分/周3學(xué)時 每周布置6道書面作業(yè)或小程序?qū)嵙?xí) 數(shù)據(jù)結(jié)構(gòu)與算法實(shí)習(xí)，2學(xué)分/周2學(xué)時 一個學(xué)期8道ACM競賽題 6道綜合上機(jī)實(shí)習(xí)題 上機(jī)實(shí)習(xí)時間，120小時/學(xué)生,北京大學(xué)信息學(xué)院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 25,（4）新教育技術(shù),建立了高質(zhì)量的課程網(wǎng)站 /mzhang/ds/ 1500ppt, 50多小時rm（全程錄像） 標(biāo)準(zhǔn)C+模板編寫的可執(zhí)行的源程序代碼 9209代碼總行數(shù)，非注釋行7498 習(xí)題和上機(jī)題及其參考答案 BBS討論版(2005年7月28日數(shù)據(jù)) 2244名注冊會員，653個問題，1863回帖 助教講答,北京大學(xué)信息學(xué)院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 26,北京大學(xué)信息學(xué)院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 27,每章內(nèi)容,概述、前測 知識點(diǎn)詳解 動畫 習(xí)題解、新習(xí)題 電子教案 pdf、視頻 擴(kuò)展資源 參考網(wǎng)站、論文、講義,北京大學(xué)信息學(xué)院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 28,（5）嚴(yán)格要求，教書育人,每一屆都布置全新作業(yè) “誠實(shí)代碼” 助教嚴(yán)格檢查,北京大學(xué)信息學(xué)院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 29,教學(xué)實(shí)施,1. 教師面授重點(diǎn)難點(diǎn)講解（30%） 2. 學(xué)生利用網(wǎng)絡(luò)課件和網(wǎng)絡(luò)資源自學(xué)（40%） 3. 課后作業(yè)和小組協(xié)作（課上和課下）（20%） 4. 助教網(wǎng)絡(luò)答疑和網(wǎng)絡(luò)討論（10%） 5. 重點(diǎn)難點(diǎn)時間放在網(wǎng)絡(luò)自學(xué)及教師面授講解上。,北京大學(xué)信息學(xué)院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 30,主課教學(xué)評價,1. 平時(書面作業(yè)、課堂測試)：20% 2. 上機(jī)實(shí)習(xí)(+實(shí)習(xí)報告)：15% 3. 期中考試：20% 4. 期末考試：40% 5. 考勤和態(tài)度：5%,北京大學(xué)信息學(xué)院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 31,實(shí)習(xí)課教學(xué)評價,平時(考勤+開卷隨堂測試課堂表現(xiàn))占30% 上機(jī)題（源程序?qū)嵙?xí)報告）70%,北京大學(xué)信息學(xué)院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 32,1線性表；2二叉樹；3樹；4圖；5散列與檢索；6排序；7索引；8高級數(shù)據(jù)結(jié)構(gòu)。,學(xué)生對知識點(diǎn)的認(rèn)識,北京大學(xué)信息學(xué)院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 33,學(xué)生評估,專業(yè)