數(shù)據(jù)結(jié)構(gòu)與算法教學(xué)方法探討

1、哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 張巖張巖Slide 1-1第第1章章 緒論緒論4123 數(shù)據(jù)結(jié)構(gòu)與算法教學(xué)方法探討數(shù)據(jù)結(jié)構(gòu)與算法教學(xué)方法探討2022-6-14 李秀坤李秀坤哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 張巖張巖Slide 1-2第第1章章 緒論緒論4123 數(shù)據(jù)結(jié)構(gòu)與算法教學(xué)方法探討數(shù)據(jù)結(jié)構(gòu)與算法教學(xué)方法探討2022-6-14關(guān)注教學(xué)目標(biāo)關(guān)注教學(xué)目標(biāo)關(guān)注教學(xué)設(shè)計(jì)關(guān)注教學(xué)設(shè)計(jì) 關(guān)注實(shí)驗(yàn)教學(xué)關(guān)注實(shí)驗(yàn)教學(xué)關(guān)注學(xué)生狀態(tài)關(guān)注學(xué)生狀態(tài)4123哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 張巖張巖Sl

2、ide 1-3第第1章章 緒論緒論4123 數(shù)據(jù)結(jié)構(gòu)與算法教學(xué)方法探討數(shù)據(jù)結(jié)構(gòu)與算法教學(xué)方法探討2022-6-14關(guān)注教學(xué)目標(biāo)關(guān)注教學(xué)目標(biāo)基本的數(shù)據(jù)結(jié)構(gòu)和算法基礎(chǔ)知識(shí)、設(shè)計(jì)與分析的技術(shù)和方法，提基本的數(shù)據(jù)結(jié)構(gòu)和算法基礎(chǔ)知識(shí)、設(shè)計(jì)與分析的技術(shù)和方法，提高程序設(shè)計(jì)的質(zhì)量；高程序設(shè)計(jì)的質(zhì)量；能夠根據(jù)所求問(wèn)題的性質(zhì)，選擇合理的數(shù)據(jù)結(jié)構(gòu)，并對(duì)時(shí)間復(fù)雜能夠根據(jù)所求問(wèn)題的性質(zhì)，選擇合理的數(shù)據(jù)結(jié)構(gòu)，并對(duì)時(shí)間復(fù)雜性進(jìn)行必要的控制。性進(jìn)行必要的控制。培養(yǎng)能運(yùn)用數(shù)據(jù)結(jié)構(gòu)并設(shè)計(jì)有效算法解決實(shí)際問(wèn)題的能力。培養(yǎng)能運(yùn)用數(shù)據(jù)結(jié)構(gòu)并設(shè)計(jì)有效算法解決實(shí)際問(wèn)題的能力。為后續(xù)課程的學(xué)習(xí)和將來(lái)從事相關(guān)的研究和開發(fā)工作打下扎實(shí)的為后續(xù)

3、課程的學(xué)習(xí)和將來(lái)從事相關(guān)的研究和開發(fā)工作打下扎實(shí)的基礎(chǔ)?；A(chǔ)。哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 張巖張巖Slide 1-4第第1章章 緒論緒論4123 數(shù)據(jù)結(jié)構(gòu)與算法教學(xué)方法探討數(shù)據(jù)結(jié)構(gòu)與算法教學(xué)方法探討2022-6-14關(guān)注教學(xué)設(shè)計(jì)關(guān)注教學(xué)設(shè)計(jì) 講好緒論課講好緒論課 主要包括教學(xué)目的、教學(xué)內(nèi)容、教學(xué)特點(diǎn)、教學(xué)要求、教學(xué)重點(diǎn)、主要包括教學(xué)目的、教學(xué)內(nèi)容、教學(xué)特點(diǎn)、教學(xué)要求、教學(xué)重點(diǎn)、學(xué)習(xí)方法和教學(xué)總體安排等內(nèi)容。學(xué)習(xí)方法和教學(xué)總體安排等內(nèi)容。 為學(xué)生建立起一門課程的知識(shí)輪廓。為學(xué)生建立起一門課程的知識(shí)輪廓。 概括說(shuō)明教材的整體內(nèi)容以及教材或課程在學(xué)科中的地位，從而使概括說(shuō)明

4、教材的整體內(nèi)容以及教材或課程在學(xué)科中的地位，從而使學(xué)生更清楚地了解學(xué)科的全貌。學(xué)生更清楚地了解學(xué)科的全貌。哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 張巖張巖Slide 1-5第第1章章 緒論緒論4123 數(shù)據(jù)結(jié)構(gòu)與算法教學(xué)方法探討數(shù)據(jù)結(jié)構(gòu)與算法教學(xué)方法探討2022-6-14增加課程廣度增加課程廣度 介紹一些與課程相關(guān)的計(jì)算機(jī)界理論大師介紹一些與課程相關(guān)的計(jì)算機(jī)界理論大師 經(jīng)典算法的故事經(jīng)典算法的故事關(guān)注教學(xué)設(shè)計(jì)關(guān)注教學(xué)設(shè)計(jì) 哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 張巖張巖Slide 1-6第第1章章 緒論緒論4123 數(shù)據(jù)結(jié)構(gòu)與算法教學(xué)方法探討數(shù)據(jù)結(jié)構(gòu)與算法教學(xué)方法探

5、討2022-6-141938年出生，年出生，25歲畢業(yè)于加州理工學(xué)院數(shù)歲畢業(yè)于加州理工學(xué)院數(shù)學(xué)系，博士畢業(yè)后留校任教，學(xué)系，博士畢業(yè)后留校任教，28歲任副教授歲任副教授。30歲時(shí)，加盟斯坦福大學(xué)計(jì)算機(jī)系，任教歲時(shí)，加盟斯坦福大學(xué)計(jì)算機(jī)系，任教授。從授。從31歲起，開始出版他的歷史性經(jīng)典巨歲起，開始出版他的歷史性經(jīng)典巨著：著：The Art of Computer Programming他計(jì)劃共寫他計(jì)劃共寫7卷，然而出版三卷之后，已震卷，然而出版三卷之后，已震驚世界，使他獲得計(jì)算機(jī)科學(xué)界的最高榮譽(yù)驚世界，使他獲得計(jì)算機(jī)科學(xué)界的最高榮譽(yù)圖靈獎(jiǎng)，此時(shí)，他年僅圖靈獎(jiǎng)，此時(shí)，他年僅36歲。歲。計(jì)算機(jī)科學(xué)

6、技術(shù)中兩個(gè)最基本的概念：計(jì)算機(jī)科學(xué)技術(shù)中兩個(gè)最基本的概念：“算算法法”(Algorithm)和和“數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)”(Data Structure)就是克努特于就是克努特于29歲時(shí)提出來(lái)的。歲時(shí)提出來(lái)的。1973年他首創(chuàng)雙向鏈表。年他首創(chuàng)雙向鏈表。數(shù)據(jù)結(jié)構(gòu)的創(chuàng)始人數(shù)據(jù)結(jié)構(gòu)的創(chuàng)始人Donald. E. Knuth哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 張巖張巖Slide 1-7第第1章章 緒論緒論4123 數(shù)據(jù)結(jié)構(gòu)與算法教學(xué)方法探討數(shù)據(jù)結(jié)構(gòu)與算法教學(xué)方法探討2022-6-14 歐拉1707年出生在瑞士的巴塞爾城，19歲開始發(fā)表論文，直到76歲。 幾乎每一個(gè)數(shù)學(xué)領(lǐng)域都可以看到歐拉的名

7、字，從初等幾何的歐拉線，多面體的歐拉定理，立體解析幾何的歐拉變換公式，四次方程的歐拉解法到數(shù)論中的歐拉函數(shù)，微分方程的歐拉方程，級(jí)數(shù)論的歐拉常數(shù)，變分學(xué)的歐拉方程，復(fù)變函數(shù)的歐拉公式等等。 據(jù)統(tǒng)計(jì)他一生，共寫下了886本書籍和論文，其中分析、代數(shù)、數(shù)論占40%，幾何占18%，物理和力學(xué)占28%，天文學(xué)占11%，彈道學(xué)、航海學(xué)、建筑學(xué)等占3%。 1733年，年僅26歲的歐拉擔(dān)任了彼得堡科學(xué)院數(shù)學(xué)教授。1741年到柏林擔(dān)任科學(xué)院物理數(shù)學(xué)所所長(zhǎng)，直到1766年，重回彼得堡。 歐拉在數(shù)學(xué)上的建樹很多，對(duì)著名的哥尼斯堡七橋問(wèn)題的解答開創(chuàng)了圖論的研究。哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院

8、張巖張巖Slide 1-8第第1章章 緒論緒論4123 數(shù)據(jù)結(jié)構(gòu)與算法教學(xué)方法探討數(shù)據(jù)結(jié)構(gòu)與算法教學(xué)方法探討2022-6-14哥尼斯堡七橋問(wèn)題哥尼斯堡七橋問(wèn)題從某個(gè)陸地區(qū)域出發(fā)，是否存在一條能夠經(jīng)過(guò)每座橋一次且僅一次，最后從某個(gè)陸地區(qū)域出發(fā)，是否存在一條能夠經(jīng)過(guò)每座橋一次且僅一次，最后回到出發(fā)地回到出發(fā)地?哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 張巖張巖Slide 1-9第第1章章 緒論緒論4123 數(shù)據(jù)結(jié)構(gòu)與算法教學(xué)方法探討數(shù)據(jù)結(jié)構(gòu)與算法教學(xué)方法探討2022-6-14 羅伯特塔揚(yáng)普林斯頓大學(xué)計(jì)算機(jī)科學(xué)系教授，1948年4月30日生于加利福尼亞州。1969年本科畢業(yè)，進(jìn)入斯坦福大

9、學(xué)研究生院，1972年獲得博士學(xué)位。平面圖測(cè)試的高效算法 ；合并-搜索問(wèn)題 ；“分?jǐn)偂彼惴ǖ母拍?；八字形樹；持久性?shù)據(jù)結(jié)構(gòu) John Edward Hopcroft Robert Endre Tarjan 約翰霍普克洛夫特1939年生于西雅圖。美國(guó)國(guó)家科學(xué)院和工程院院士、康奈爾大學(xué)智能機(jī)器人實(shí)驗(yàn)室主任。1962和1964年獲斯坦福大學(xué)碩士和博士學(xué)位。先后在普林斯頓大學(xué)、斯坦福大學(xué)等工作，也曾任職于一些科學(xué)研究機(jī)構(gòu)如NSF和NRC。著作很多如算法設(shè)計(jì)與分析基礎(chǔ) 數(shù)據(jù)結(jié)構(gòu)與算法自動(dòng)機(jī)理論、語(yǔ)言和計(jì)算導(dǎo)論形式語(yǔ)言及其與自動(dòng)機(jī)的關(guān)系 1986年圖靈獎(jiǎng)獲得者年圖靈獎(jiǎng)獲得者哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院哈工大

10、計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 張巖張巖Slide 1-10第第1章章 緒論緒論4123 數(shù)據(jù)結(jié)構(gòu)與算法教學(xué)方法探討數(shù)據(jù)結(jié)構(gòu)與算法教學(xué)方法探討2022-6-14哈夫曼編碼哈夫曼編碼 是哈夫曼于是哈夫曼于1952年提出的一種編碼方法，該方法完全依據(jù)字符出現(xiàn)概率來(lái)構(gòu)年提出的一種編碼方法，該方法完全依據(jù)字符出現(xiàn)概率來(lái)構(gòu)造異字頭的平均長(zhǎng)度最短的碼字，也稱之為最佳編碼。造異字頭的平均長(zhǎng)度最短的碼字，也稱之為最佳編碼。 1952年，年，David A. Huffman在在麻省理工麻省理工攻讀博士時(shí)所發(fā)明的，并發(fā)表于攻讀博士時(shí)所發(fā)明的，并發(fā)表于一種構(gòu)建極一種構(gòu)建極小多余編碼的方法小多余編碼的方法（A Method f

11、or the Construction of Minimum-Redundancy Codes）一文。）一文。 1951年，年，霍夫曼霍夫曼和他在和他在MIT信息論信息論的同學(xué)需要選擇是完成學(xué)期報(bào)告還是期末的同學(xué)需要選擇是完成學(xué)期報(bào)告還是期末考試考試。導(dǎo)。導(dǎo)師師Robert M. Fano給他們的學(xué)期報(bào)告的題目是，查找最有效的二進(jìn)制編碼。由于無(wú)法證明給他們的學(xué)期報(bào)告的題目是，查找最有效的二進(jìn)制編碼。由于無(wú)法證明哪個(gè)已有編碼是最有效的，霍夫曼放棄對(duì)已有編碼的研究，轉(zhuǎn)向新的探索，最終發(fā)現(xiàn)了基哪個(gè)已有編碼是最有效的，霍夫曼放棄對(duì)已有編碼的研究，轉(zhuǎn)向新的探索，最終發(fā)現(xiàn)了基于有序頻率于有序頻率二叉樹二叉

12、樹編碼的想法，并很快證明了這個(gè)方法是最有效的。編碼的想法，并很快證明了這個(gè)方法是最有效的。關(guān)鍵路徑問(wèn)題：關(guān)鍵路徑問(wèn)題：項(xiàng)目管理及成本核算問(wèn)題。關(guān)鍵路線法是一種網(wǎng)絡(luò)圖方法，由項(xiàng)目管理及成本核算問(wèn)題。關(guān)鍵路線法是一種網(wǎng)絡(luò)圖方法，由雷明頓雷明頓-蘭德蘭德公司公司(Remington- Rand)的的JE克里克里(JE Kelly)和和杜邦公司杜邦公司的的MR沃爾克沃爾克(MR Walker)在在1957年提出的，用于對(duì)化工工廠的維護(hù)項(xiàng)目進(jìn)行日程安排。它適用于有很多作業(yè)而且必須按時(shí)年提出的，用于對(duì)化工工廠的維護(hù)項(xiàng)目進(jìn)行日程安排。它適用于有很多作業(yè)而且必須按時(shí)完成的項(xiàng)目。關(guān)鍵路線法是一個(gè)動(dòng)態(tài)系統(tǒng)，它會(huì)隨

13、著項(xiàng)目的進(jìn)展不斷更新，該方法采用單完成的項(xiàng)目。關(guān)鍵路線法是一個(gè)動(dòng)態(tài)系統(tǒng)，它會(huì)隨著項(xiàng)目的進(jìn)展不斷更新，該方法采用單一時(shí)間估計(jì)法，其中時(shí)間被視為一定的或確定的。，一時(shí)間估計(jì)法，其中時(shí)間被視為一定的或確定的。，哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 張巖張巖Slide 1-11第第1章章 緒論緒論4123 數(shù)據(jù)結(jié)構(gòu)與算法教學(xué)方法探討數(shù)據(jù)結(jié)構(gòu)與算法教學(xué)方法探討2022-6-14增加課程深度增加課程深度 延伸知識(shí)內(nèi)容，擴(kuò)展思維，并說(shuō)明解決辦法，讓學(xué)生自己實(shí)現(xiàn)，可以給一延伸知識(shí)內(nèi)容，擴(kuò)展思維，并說(shuō)明解決辦法，讓學(xué)生自己實(shí)現(xiàn)，可以給一定的加分。定的加分。問(wèn)題問(wèn)題1 1：棧的應(yīng)用棧的應(yīng)用 設(shè)計(jì)一

14、種數(shù)據(jù)結(jié)構(gòu)，滿足棧的性質(zhì)，實(shí)現(xiàn)下列設(shè)計(jì)一種數(shù)據(jù)結(jié)構(gòu)，滿足棧的性質(zhì)，實(shí)現(xiàn)下列3 3個(gè)操作：個(gè)操作： 1 1）Push(v):Push(v):將將v v加入到棧；加入到棧； 2 2）Pop():Pop():刪除棧頂元素并返回此元素；刪除棧頂元素并返回此元素； 3 3）Maxelement():Maxelement():返回棧中最大元素；返回棧中最大元素； 讓它們的時(shí)間復(fù)雜度都為讓它們的時(shí)間復(fù)雜度都為O(1)O(1)關(guān)注教學(xué)設(shè)計(jì)關(guān)注教學(xué)設(shè)計(jì) 哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 張巖張巖Slide 1-12第第1章章 緒論緒論4123 數(shù)據(jù)結(jié)構(gòu)與算法教學(xué)方法探討數(shù)據(jù)結(jié)構(gòu)與算法教學(xué)方法

15、探討2022-6-14增加課程深度增加課程深度 問(wèn)題問(wèn)題2 2：隊(duì)列的應(yīng)用隊(duì)列的應(yīng)用 代碼密鑰：凱撒加密法是一種簡(jiǎn)單的消息編碼方式，它是按照字母表將消息中的每個(gè)字母移動(dòng)常量的k位，但這種方式極易破解，因?yàn)樽帜傅囊苿?dòng)只有26種可能。 可以使用重復(fù)密鑰：將每個(gè)字母移動(dòng)數(shù)位不同，利用一個(gè)密鑰值列表，將各個(gè)字母移動(dòng)不同的位數(shù)。如果消息比密鑰值長(zhǎng)，可以從頭再使用這個(gè)密鑰值列表； 問(wèn)題3：哈夫曼樹問(wèn)題 哈夫曼樹也可以是k叉的，只是在構(gòu)造k叉哈夫曼樹時(shí)需要先進(jìn)行一些調(diào)整。構(gòu)造哈夫曼樹的思想是每次選k個(gè)權(quán)重最小的元素來(lái)合成一個(gè)新的元素，該元素權(quán)重為k個(gè)元素權(quán)重之和。但是當(dāng)k大于2時(shí)，按照這個(gè)步驟做下去可能到最

16、后剩下的元素少于k個(gè)。哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 張巖張巖Slide 1-13第第1章章 緒論緒論4123 數(shù)據(jù)結(jié)構(gòu)與算法教學(xué)方法探討數(shù)據(jù)結(jié)構(gòu)與算法教學(xué)方法探討2022-6-14問(wèn)題問(wèn)題4：圖問(wèn)題圖問(wèn)題 1）Prim算法與Dijkstra算法的區(qū)別？ 2）為什么出現(xiàn)負(fù)權(quán)值Dijkstra算法會(huì)有問(wèn)題？如何解決？ 3）如果圖本身是無(wú)環(huán)路的有向圖，求最短路徑算法如何優(yōu)化？問(wèn)題問(wèn)題5：散列問(wèn)題散列問(wèn)題 1）有一個(gè)龐大的字符串?dāng)?shù)組，然后給一個(gè)單獨(dú)的字符串，從這個(gè)數(shù)組中查找是否有這個(gè)字符串并找到它。 2）搜索引擎會(huì)通過(guò)日志文件把用戶每次檢索使用的所有檢索串都記錄下來(lái)，每個(gè)查詢串

17、的長(zhǎng)度為1-255字節(jié)。 假設(shè)目前有一千萬(wàn)個(gè)記錄（這些查詢串的重復(fù)度比較高，雖然總數(shù)是1千萬(wàn)，但如果除去重復(fù)后，不超過(guò)3百萬(wàn)個(gè)。一個(gè)查詢串的重復(fù)度越高，說(shuō)明查詢它的用戶越多，也就是越熱門。），請(qǐng)你統(tǒng)計(jì)最熱門的10個(gè)查詢串，要求使用的內(nèi)存不能超過(guò)1G。 增加課程深度增加課程深度哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 張巖張巖Slide 1-14第第1章章 緒論緒論4123 數(shù)據(jù)結(jié)構(gòu)與算法教學(xué)方法探討數(shù)據(jù)結(jié)構(gòu)與算法教學(xué)方法探討2022-6-14關(guān)注實(shí)驗(yàn)教學(xué)關(guān)注實(shí)驗(yàn)教學(xué)訓(xùn)練基礎(chǔ)，加強(qiáng)計(jì)算機(jī)方面的能力作業(yè)作業(yè)：小作業(yè)、大作業(yè)實(shí)驗(yàn)實(shí)驗(yàn)：驗(yàn)證課堂學(xué)習(xí)的理論 閱讀程序的能力；分析問(wèn)題的能力； 調(diào)試程序的能力；編寫程序的能力； 撰寫文檔的能力；總結(jié)問(wèn)題的能力； 數(shù)據(jù)抽象的能力；理論與實(shí)際結(jié)合能力；數(shù)據(jù)抽象的能力；理