全國信息學(xué)奧林匹克競賽中級指導(dǎo)教師培訓(xùn)班

1、全國信息學(xué)奧林匹克競賽中級指導(dǎo)教師培訓(xùn)班教學(xué)大綱,_4+匕、小白中國計算機學(xué)會將定期舉辦全國信息學(xué)奧林匹克中級指導(dǎo)教師培訓(xùn)班，旨在提高各地中學(xué)從事信息學(xué)奧林匹克培訓(xùn)指導(dǎo)教師的整體水平，從而更好地在中學(xué)里開展計算機應(yīng)用和程序設(shè)計的普及教育，為培養(yǎng)高水平的計算機專業(yè)人才奠定良好的基礎(chǔ)。培訓(xùn)班將依據(jù)全國青少年信息學(xué)奧林匹克聯(lián)賽（NOIP）大綱確定教學(xué)內(nèi)容。鑒于培訓(xùn)時間較短（一般在一周左右），教學(xué)以傳授相關(guān)知識為主，學(xué)員業(yè)務(wù)能力的提高主要依靠個人自身的努力。通過培訓(xùn)，應(yīng)使學(xué)員了解參與信息學(xué)競賽必備的知識要點；掌握基本的程序設(shè)計、算法和數(shù)據(jù)結(jié)構(gòu)的有關(guān)內(nèi)容；經(jīng)過繼續(xù)努力，可以獨立承擔(dān)NOIP提高組的培訓(xùn)工

2、作。培訓(xùn)班還將為從事信息學(xué)奧林匹克培訓(xùn)的一線教師提供一個直接交流的平臺，交流和探討各校的培訓(xùn)內(nèi)容、方法、培訓(xùn)模式和成功的經(jīng)驗，以便推動全國各省市信息學(xué)奧林匹克競賽水平的均衡發(fā)展。二、教學(xué)內(nèi)容（1）程序設(shè)計語言概要由于學(xué)員水平不一，使用的程序設(shè)計語言不同，有必要用一定的時間介紹培訓(xùn)中將要使用的程序設(shè)計語言的核心內(nèi)容（條件語句、循環(huán)語句、指針、結(jié)構(gòu)、函數(shù)（或過程）的定義和引用等）。建議任課教師使用C/C+語言，也可以使用Pascal語言。程序運行環(huán)境由任課教師參照NOIP競賽環(huán)境選定。建議適當(dāng)介紹如何檢驗程序的正確性和如何設(shè)計測試數(shù)據(jù)。（2）算法設(shè)計與數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)（2.1）遞歸回溯與基本搜索方法（

3、遞歸的基本思想與實現(xiàn)過程，深度優(yōu)先搜索，n后問題、0-1背包問題、圖的m著色、連續(xù)郵資問題、最大團問題等；近幾年NOIP相關(guān)試題）。（2.2）貪心算法（單源最短路徑、最小生成樹、哈夫曼編碼等）。（2.3）線性結(jié)構(gòu)、圖與樹的相關(guān)問題（鏈表、堆棧、隊列、申、哈希表、樹的存貯結(jié)構(gòu)、幾類典型的二叉樹、樹的遍歷、圖的存貯結(jié)構(gòu)、圖的遍歷、圖的連通性、拓撲排序與關(guān)鍵路徑等；近幾年NOIP相關(guān)試題）（2.4）分治算法（二分搜索、棋盤覆蓋問題、快速排序、跳馬問題）（2.5）動態(tài)規(guī)劃（基本思想、0-1背包問題、矩陣連乘問題、最長公共子列、最優(yōu)二叉搜索樹等；近幾年NOIP相關(guān)試題）（3）歷屆NOIP綜合性試題分析（

4、適當(dāng)選擇各屆聯(lián)賽（提高組）的最后一題進行分析研究）三、其他活動（1）經(jīng)驗交流與討論（2）教學(xué)檢測與評估在培訓(xùn)后期進行一次上機考試，以了解教學(xué)效果和學(xué)員程序設(shè)計能力的基本情況四、具體時間安排第授課內(nèi)容（8小時）上午：程序設(shè)計語言概要、遞歸與遞推算法下午：貪心與分治算法天重點遞歸、遞推、貪心與分治算法難點遞歸與遞推的理解，遞推、貪心的分析，分治算法的實現(xiàn)討論主題（2小時）晚上：算法的核心思想在哪里？第授課內(nèi)容上午：深度優(yōu)先搜索策略及其優(yōu)化技巧一（8小時）下午：寬度優(yōu)先搜索策略及其優(yōu)化技巧天重點深度優(yōu)先與寬度優(yōu)先策略的優(yōu)化難點深度優(yōu)先與寬度優(yōu)先策略的優(yōu)化技巧討論主題（2小時）晚上：什么情況下采用搜索

5、？搜索的本質(zhì)是什么？第授課內(nèi)容上午：堆棧和隊列的應(yīng)用技巧二（8小時）下午：最優(yōu)二叉樹、二叉堆、二叉搜索樹的構(gòu)造與應(yīng)用天重點堆棧、隊列、最優(yōu)二叉樹、二叉堆、二叉搜索樹的構(gòu)造與應(yīng)用難點堆棧、隊列、最優(yōu)二叉樹、二叉堆、二叉搜索樹的應(yīng)用技巧討論主題（2小時）晚上：為什么要構(gòu)造數(shù)據(jù)結(jié)構(gòu)？怎樣構(gòu)造合適的數(shù)據(jù)結(jié)構(gòu)？第授課內(nèi)容上午：圖的連通性問題與最小生成樹算法及其有向圖的拓撲序列四（8小時）下午：圖的最短路徑算法，HASH表及并查集的構(gòu)造與應(yīng)用天重點圖的最小生成樹與最短路徑算法難點圖的各種算法應(yīng)用場合討論主題（2小時）晚上：圖在競賽中扮演什么樣的角色？與圖相關(guān)的算法還有哪些？第授課內(nèi)容上午：動態(tài)規(guī)劃基本原理

6、與應(yīng)用五（8小時）下午：2005、2006年NOIP提高組復(fù)賽試題分析天重點動態(tài)規(guī)劃基本原理與應(yīng)用技巧難點動態(tài)規(guī)劃的應(yīng)用討論主題（2小時）晚上：怎樣判定動態(tài)規(guī)劃問題？動態(tài)規(guī)劃中階段的劃分有沒有規(guī)律？第六授課內(nèi)容（8小時）上午：2007、2008年NOIP提高組復(fù)賽試題簡要分析下午：測試講評天重點2007、2008年NOIP提高組復(fù)賽試題簡要分析難點2007、2008年NOIP提高組復(fù)賽難題分析討論主題（2小時）晚上：NOIP命題的走向與建議說明：（1）上述時間安排不是強制性的，任課教師可就授課內(nèi)容和授課順序做適當(dāng)調(diào)整。（2）授課使用的參考書目由任課教師在培訓(xùn)班開課之前根據(jù)授課內(nèi)容確定，并與教學(xué)

7、大綱一同下發(fā)給學(xué)員。五、參考教材1中國計算機學(xué)會主編，2006全國信息學(xué)奧林匹克年鑒，河南電子音像出版社，鄭州，2007年1月。2 中國計算機學(xué)會主編，2007全國信息學(xué)奧林匹克年鑒，河南電子音像出版社，鄭州，2008年1月。3 吳文虎、李立新等，全國信息學(xué)奧林匹克聯(lián)賽試題精解（2001-2003）（普及本），清華大學(xué)出版社，北京，2004年7月。4吳文虎等，全國信息學(xué)奧林匹克聯(lián)賽培訓(xùn)教程（二）（普及本），清華大學(xué)出版社，北京，2006年12月重印。5向期中，信息學(xué)奧林匹克教程-數(shù)據(jù)結(jié)構(gòu)篇，湖南師范大學(xué)出版社，長沙，2006年8月。6李學(xué)武，中學(xué)生學(xué)C語言，清華大學(xué)出版社，北京，2004年8月。六、證書參照全國信息學(xué)奧林匹克指導(dǎo)教師評級條