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

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

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

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

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

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

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

7、述時(shí)間安排不是強(qiáng)制性的，任課教師可就授課內(nèi)容和授課順序做適當(dāng)調(diào)整。（ 2）授課使用的參考書(shū)目由任課教師在培訓(xùn)班開(kāi)課之前根據(jù)授課內(nèi)容確定，并與教學(xué)大綱一同下發(fā)給學(xué)員。五、參考教材1 中國(guó)計(jì)算機(jī)學(xué)會(huì)主編， 2006 全國(guó)信息學(xué)奧林匹克年鑒，河南電子音像出版社，鄭州， 2007 年 1 月。2 中國(guó)計(jì)算機(jī)學(xué)會(huì)主編， 2007 全國(guó)信息學(xué)奧林匹克年鑒，河南電子音像出版社，鄭州， 2008 年 1 月。3 吳文虎、李立新等，全國(guó)信息學(xué)奧林匹克聯(lián)賽試題精解（ 2001-2003 ）（普及本），清華大學(xué)出版社，北京， 2004 年 7 月。4 吳文虎等，全國(guó)信息學(xué)奧林匹克聯(lián)賽培訓(xùn)教程（二） （普及本），清華大學(xué)出版社，北京， 2006 年 12 月重印。5 向期中，信息學(xué)奧林匹克教程 - 數(shù)據(jù)結(jié)構(gòu)篇，湖南師范大學(xué)出版社，長(zhǎng)沙， 2006 年8月。6 李學(xué)武，中學(xué)生學(xué) C 語(yǔ)言，清華大學(xué)出版社，北京， 2004 年 8 月。六、證書(shū)參照全國(guó)信息學(xué)奧林匹克指導(dǎo)教師評(píng)級(jí)條