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

1、全國信息學(xué)奧林匹克競賽中級指導(dǎo)教師培訓(xùn)班教學(xué)大綱一、宗旨中國計算機(jī)學(xué)會將定期舉辦全國信息學(xué)奧林匹克中級指導(dǎo)教師培訓(xùn)班，旨在提高各地中學(xué)從事信息學(xué)奧林匹克培訓(xùn)指導(dǎo)教師的整體水平，從而更好地在中學(xué)里開展計算機(jī)應(yīng)用和程序設(shè)計的普及教育，為培養(yǎng)高水平的計算機(jī)專業(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é)競賽必備的知識要點(diǎn)；掌握基本的程序設(shè)計、算法和數(shù)據(jù)結(jié)構(gòu)的有關(guān)內(nèi)容；經(jīng)過繼續(xù)努力，可以獨(dú)立承擔(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語言。程序運(yùn)行環(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ù)郵資問題、最大團(tuán)問題等；近幾年 NOIP 相關(guān)試題）。（ 2.2 ）貪心算法（單源最短路徑、最小生成樹、哈夫曼編碼等）。（ 2.3 ）線性結(jié)構(gòu)、圖與樹的相關(guān)問題（鏈表、堆棧、隊列、串、哈希表、樹的存貯結(jié)構(gòu)、幾類典型的二叉樹、樹的遍歷、圖的存貯結(jié)構(gòu)、圖的遍歷、圖的連通性、拓?fù)渑判蚺c關(guān)鍵路徑等；近幾年 NOIP 相關(guān)試題）（ 2.4 ）分治算法（二分搜索、棋盤覆蓋問題、快速排序、跳馬問題）（ 2.5 ）動態(tài)規(guī)劃（基本思想、 0-1 背包問題、矩陣連乘問題、最長公共子列、最優(yōu)二叉搜索樹等；近幾年 N

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

5、優(yōu)先與寬度優(yōu)先策略的優(yōu)化技巧討論主題晚上：什么情況下采用搜索？搜索的本質(zhì)是什么？（2 小時）第授課內(nèi)容上午：堆棧和隊列的應(yīng)用技巧三（ 8 小時）下午：最優(yōu)二叉樹、二叉堆、二叉搜索樹的構(gòu)造與應(yīng)用天重點(diǎn)堆棧、隊列、最優(yōu)二叉樹、二叉堆、二叉搜索樹的構(gòu)造與應(yīng)用難點(diǎn)堆棧、隊列、最優(yōu)二叉樹、二叉堆、二叉搜索樹的應(yīng)用技巧討論主題晚上：為什么要構(gòu)造數(shù)據(jù)結(jié)構(gòu)？怎樣構(gòu)造合適的數(shù)據(jù)結(jié)構(gòu)？（2 小時）第授課內(nèi)容上午：圖的連通性問題與最小生成樹算法及其有向圖的拓?fù)湫蛄兴模? 小時）下午：圖的最短路徑算法，HASH 表及并查集的構(gòu)造與應(yīng)用天重點(diǎn)圖的最小生成樹與最短路徑算法難點(diǎn)圖的各種算法應(yīng)用場合討論主題晚上：圖在競賽中扮

6、演什么樣的角色？與圖相關(guān)的算法還有哪些？（2 小時）第授課內(nèi)容上午：動態(tài)規(guī)劃基本原理與應(yīng)用五 （ 8 小時） 下午： 2005 、 2006 年 NOIP 提高組復(fù)賽試題分析天 重 點(diǎn) 動態(tài)規(guī)劃基本原理與應(yīng)用技巧難點(diǎn)動態(tài)規(guī)劃的應(yīng)用討論主題晚上：怎樣判定動態(tài)規(guī)劃問題？動態(tài)規(guī)劃中階段的劃分有沒有規(guī)律？（2 小時）第授課內(nèi)容上午： 2007 、 2008 年 NOIP 提高組復(fù)賽試題簡要分析六（8 小時）下午：測試講評天重點(diǎn)2007、2008年 NOIP 提高組復(fù)賽試題簡要分析難點(diǎn)2007、2008年 NOIP 提高組復(fù)賽難題分析討論主題晚上： NOIP 命題的走向與建議（2 小時）說明：（ 1）上

7、述時間安排不是強(qiáng)制性的，任課教師可就授課內(nèi)容和授課順序做適當(dāng)調(diào)整。（ 2）授課使用的參考書目由任課教師在培訓(xùn)班開課之前根據(jù)授課內(nèi)容確定，并與教學(xué)大綱一同下發(fā)給學(xué)員。五、參考教材1 中國計算機(jī)學(xué)會主編， 2006 全國信息學(xué)奧林匹克年鑒，河南電子音像出版社，鄭州， 2007 年 1 月。2 中國計算機(jī)學(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)教師評級條