全國信息學奧林匹克競賽中級指導教師培訓班

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

2、作。培訓班還將為從事信息學奧林匹克培訓的一線教師提供一個直接交流的平臺，交流和探討各校的培訓內(nèi)容、方法、培訓模式和成功的經(jīng)驗，以便推動全國各省市信息學奧林匹克競賽水平的均衡發(fā)展。二、教學內(nèi)容（1）程序設計語言概要由于學員水平不一，使用的程序設計語言不同，有必要用一定的時間介紹培訓中將要使用的程序設計語言的核心內(nèi)容（條件語句、循環(huán)語句、指針、結(jié)構(gòu)、函數(shù)（或過程）的定義和引用等）。建議任課教師使用C/C+語言，也可以使用Pascal語言。程序運行環(huán)境由任課教師參照NOIP競賽環(huán)境選定。建議適當介紹如何檢驗程序的正確性和如何設計測試數(shù)據(jù)。（2）算法設計與數(shù)據(jù)結(jié)構(gòu)基礎（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、適當選擇各屆聯(lián)賽（提高組）的最后一題進行分析研究）三、其他活動（1）經(jīng)驗交流與討論（2）教學檢測與評估在培訓后期進行一次上機考試，以了解教學效果和學員程序設計能力的基本情況四、具體時間安排第授課內(nèi)容（8小時）上午：程序設計語言概要、遞歸與遞推算法下午：貪心與分治算法天重點遞歸、遞推、貪心與分治算法難點遞歸與遞推的理解，遞推、貪心的分析，分治算法的實現(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)容上午：堆棧和隊列的應用技巧二（8小時）下午：最優(yōu)二叉樹、二叉堆、二叉搜索樹的構(gòu)造與應用天重點堆棧、隊列、最優(yōu)二叉樹、二叉堆、二叉搜索樹的構(gòu)造與應用難點堆棧、隊列、最優(yōu)二叉樹、二叉堆、二叉搜索樹的應用技巧討論主題（2小時）晚上：為什么要構(gòu)造數(shù)據(jù)結(jié)構(gòu)？怎樣構(gòu)造合適的數(shù)據(jù)結(jié)構(gòu)？第授課內(nèi)容上午：圖的連通性問題與最小生成樹算法及其有向圖的拓撲序列四（8小時）下午：圖的最短路徑算法，HASH表及并查集的構(gòu)造與應用天重點圖的最小生成樹與最短路徑算法難點圖的各種算法應用場合討論主題（2小時）晚上：圖在競賽中扮演什么樣的角色？與圖相關(guān)的算法還有哪些？第授課內(nèi)容上午：動態(tài)規(guī)劃基本原理

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

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