NOI教練員培訓初中級教學大綱

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

2、普及組的培訓工作。培訓班還將為從事信息學奧林匹克培訓的一線教師提供一個直接交流的平臺，交流和探討各校的培訓內容、方法、培訓模式和成功的經驗，以便推動全國各省市信息學奧林匹克競賽水平的均衡發(fā)展。 二、教學內容 （1）程序設計語言由于學員水平不一，使用的程序設計語言不同，首先用一天的時間介紹程序設計的基本概念和培訓中將要使用的程序設計語言的核心內容，主要包括：（1.1）程序設計的基本概念和方法（1.2）條件語句、循環(huán)語句與數(shù)組、簡單的排序與查找的算法。（1.3）指針、結構、函數(shù)（或過程）的定義和引用、鏈表的實現(xiàn)等。（1.4）如何檢驗程序的正確性和如何設計測試數(shù)據(jù)。建議任課教師使用C/C+語言，也可

3、以使用Pascal語言。程序運行環(huán)境由任課教師參照NOIP競賽環(huán)境選定。（2）算法設計與數(shù)據(jù)結構基礎（2.1）簡單枚舉和模擬算法（2.2）基本數(shù)值處理問題以及高精度數(shù)值處理技巧。（2.3）遞歸回溯與基本搜索方法（遞歸的基本思想與實現(xiàn)過程，深度優(yōu)先搜索與廣度優(yōu)先搜索，n后問題、0-1背包問題、圖的m著色問題等；近幾年NOIP相關試題）。（2.4）貪心算法（單源最短路徑、最小生成樹、哈夫曼編碼等）。（2.5）線性結構、圖與樹的相關問題（鏈表、隊列、堆棧、串、哈希表、樹的存貯結構、樹的遍歷、圖的存貯結構、圖的遍歷等；近幾年NOIP相關試題）。（2.6）動態(tài)規(guī)劃的思想及其簡單應用（3）歷屆NOIP綜合

4、性試題分析（適當選擇各屆聯(lián)賽（普及組）的最后一題進行分析研究）。三、其他活動（1）經驗交流與討論（2）教學檢測與評估在培訓后期進行一次上機考試，以了解教學效果和學員程序設計能力的基本情況。四、具體時間安排第一天授課內容（8小時）上午：程序設計的基本概念和方法下午：程序設計語言（包括簡單的排序和查找算法）重 點程序設計的基本概念和方法難 點條件語句與循環(huán)語句；函數(shù)（或過程）的定義和引用；排序、查找算法討論主題（2小時）晚上：信息學奧賽的各類競賽了解及競賽規(guī)則討論第二天授課內容（8小時）上午：簡單枚舉和模擬算法下午：基本數(shù)值處理問題以及多精度數(shù)值處理技巧重 點枚舉、模擬算法、高精度處理方法難 點數(shù)

5、值處理技巧討論主題（2小時）晚上：LINUX系統(tǒng)與WINDOWS系統(tǒng)的區(qū)別以及各種評測系統(tǒng)的比較第三天授課內容（8小時）上午：遞歸與回溯算法下午：簡單鏈表操作，隊列、堆棧的操作及其應用重 點遞歸、回溯算法，隊列、堆棧的基本應用難 點遞歸、回溯算法的理解與應用討論主題（2小時）晚上：上機實踐第四天授課內容（8小時）上午：樹、基本概念及其存儲結構，二叉樹的性質、構造、遍歷及其應用下午：圖的基本概念及其存儲結構，圖的深度優(yōu)先遍歷和寬度優(yōu)先遍歷算法重 點二叉樹的基本應用，深度優(yōu)先、寬度優(yōu)先算法難 點二叉樹的應用技巧、深度優(yōu)先與寬度優(yōu)先算法的應用討論主題（2小時）晚上：上機實踐第五天授課內容（8小時）上

6、午：貪心算法下午：動態(tài)規(guī)劃的思想及其簡單應用重 點動態(tài)規(guī)劃的應用難 點動態(tài)規(guī)劃的應用技巧討論主題（2小時）晚上：聯(lián)賽試題類型、難度分析與討論第六天授課內容（8小時）上午：近幾年NOIP普及組復賽試題分析下午：測試講評重 點NOIP普及組復賽試題分析難 點NOIP復賽難題分析討論主題（2小時）晚上：如何成為一名出色的信息學教師說明： （1）上述時間安排不是強制性的，任課教師可就授課內容和授課順序做適當調整。 （2）授課使用的參考書目由任課教師在培訓班開課之前根據(jù)授課內容確定，并與教學大綱一同下發(fā)給學員。五、參考教材1 中國計算機學會主編，2006全國信息學奧林匹克年鑒，河南電子音像出版社，鄭州，

7、2007年1月。 2 中國計算機學會主編，2007全國信息學奧林匹克年鑒，河南電子音像出版社，鄭州，2008年1月。 3 吳文虎、李立新等，全國信息學奧林匹克聯(lián)賽試題精解（2001-2003）（普及本），清華大學出版社，北京，2004年7月。4 吳文虎等，全國信息學奧林匹克聯(lián)賽培訓教程（二）（普及本），清華大學出版社，北京，2006年12月重印。5 向期中，信息學奧林匹克教程-數(shù)據(jù)結構篇，湖南師范大學出版社，長沙，2006年8月。6 吳文虎等，全國信息學奧林匹克聯(lián)賽培訓教程（一）（普及本），清華大學出版社，北京，2008年11月重印。7 李學武，中學生C語言入門演練100例，清華大學出版社，北

8、京，2007年4月。六、證書參照全國信息學奧林匹克指導教師評級條例，由中國計算機學會另行制定頒發(fā)指導教師證書的具體實施辦法。7、 初級大綱編寫步驟1、由黃福銘、滕偉、邱桂香分別提供大綱初稿2、由李學武、朱全民負責對以上初稿進行初審、編定 3、由王宏、孫輝負責共同復審和最終定稿 2008年12月1日全國信息學奧林匹克競賽中級指導教師培訓班教學大綱一、宗旨中國計算機學會將定期舉辦全國信息學奧林匹克中級指導教師培訓班，旨在提高各地中學從事信息學奧林匹克培訓指導教師的整體水平，從而更好地在中學里開展計算機應用和程序設計的普及教育，為培養(yǎng)高水平的計算機專業(yè)人才奠定良好的基礎。培訓班將依據(jù)全國青少年信息學

9、奧林匹克聯(lián)賽（NOIP）大綱確定教學內容。鑒于培訓時間較短（一般在一周左右），教學以傳授相關知識為主，學員業(yè)務能力的提高主要依靠個人自身的努力。通過培訓，應使學員了解參與信息學競賽必備的知識要點；掌握基本的程序設計、算法和數(shù)據(jù)結構的有關內容；經過繼續(xù)努力，可以獨立承擔NOIP提高組的培訓工作。培訓班還將為從事信息學奧林匹克培訓的一線教師提供一個直接交流的平臺，交流和探討各校的培訓內容、方法、培訓模式和成功的經驗，以便推動全國各省市信息學奧林匹克競賽水平的均衡發(fā)展。 二、教學內容 （1）程序設計語言概要由于學員水平不一，使用的程序設計語言不同，有必要用一定的時間介紹培訓中將要使用的程序設計語言的

10、核心內容（條件語句、循環(huán)語句、指針、結構、函數(shù)（或過程）的定義和引用等）。建議任課教師使用C/C+語言，也可以使用Pascal語言。程序運行環(huán)境由任課教師參照NOIP競賽環(huán)境選定。建議適當介紹如何檢驗程序的正確性和如何設計測試數(shù)據(jù)。（2）算法設計與數(shù)據(jù)結構基礎（2.1）遞歸回溯與基本搜索方法（遞歸的基本思想與實現(xiàn)過程，深度優(yōu)先搜索，n后問題、0-1背包問題、圖的m著色、連續(xù)郵資問題、最大團問題等；近幾年NOIP相關試題）。（2.2）貪心算法（單源最短路徑、最小生成樹、哈夫曼編碼等）。（2.3）線性結構、圖與樹的相關問題（鏈表、堆棧、隊列、串、哈希表、樹的存貯結構、幾類典型的二叉樹、樹的遍歷、圖

11、的存貯結構、圖的遍歷、圖的連通性、拓撲排序與關鍵路徑等；近幾年NOIP相關試題）（2.4）分治算法（二分搜索、棋盤覆蓋問題、快速排序、跳馬問題）（2.5）動態(tài)規(guī)劃（基本思想、0-1背包問題、矩陣連乘問題、最長公共子列、最優(yōu)二叉搜索樹等；近幾年NOIP相關試題）（3）歷屆NOIP綜合性試題分析（適當選擇各屆聯(lián)賽（提高組）的最后一題進行分析研究）三、其他活動（1）經驗交流與討論（2）教學檢測與評估在培訓后期進行一次上機考試，以了解教學效果和學員程序設計能力的基本情況四、具體時間安排第一天授課內容（8小時）上午：程序設計語言概要、遞歸與遞推算法下午：貪心與分治算法重 點遞歸、遞推、貪心與分治算法難

12、點遞歸與遞推的理解，遞推、貪心的分析，分治算法的實現(xiàn)討論主題（2小時）晚上：算法的核心思想在哪里？第二天授課內容（8小時）上午：深度優(yōu)先搜索策略及其優(yōu)化技巧下午：寬度優(yōu)先搜索策略及其優(yōu)化技巧重 點深度優(yōu)先與寬度優(yōu)先策略的優(yōu)化難 點深度優(yōu)先與寬度優(yōu)先策略的優(yōu)化技巧討論主題（2小時）晚上：什么情況下采用搜索？搜索的本質是什么？第三天授課內容（8小時）上午：堆棧和隊列的應用技巧下午：最優(yōu)二叉樹、二叉堆、二叉搜索樹的構造與應用重 點堆棧、隊列、最優(yōu)二叉樹、二叉堆、二叉搜索樹的構造與應用難 點堆棧、隊列、最優(yōu)二叉樹、二叉堆、二叉搜索樹的應用技巧討論主題（2小時）晚上：為什么要構造數(shù)據(jù)結構？怎樣構造合適的

13、數(shù)據(jù)結構？第四天授課內容（8小時）上午：圖的連通性問題與最小生成樹算法及其有向圖的拓撲序列下午：圖的最短路徑算法，HASH表及并查集的構造與應用重 點圖的最小生成樹與最短路徑算法難 點圖的各種算法應用場合討論主題（2小時）晚上：圖在競賽中扮演什么樣的角色？與圖相關的算法還有哪些？第五天授課內容（8小時）上午：動態(tài)規(guī)劃基本原理與應用下午：2005、2006年NOIP提高組復賽試題分析重 點動態(tài)規(guī)劃基本原理與應用技巧難 點動態(tài)規(guī)劃的應用討論主題（2小時）晚上：怎樣判定動態(tài)規(guī)劃問題？動態(tài)規(guī)劃中階段的劃分有沒有規(guī)律？第六天授課內容（8小時）上午：2007、2008年NOIP提高組復賽試題分析下午：測試

14、講評重 點2007、2008年NOIP提高組復賽試題分析難 點2007、2008年NOIP提高組復賽難題分析討論主題（2小時）晚上：聯(lián)賽命題的走向與建議 說明： （1）上述時間安排不是強制性的，任課教師可就授課內容和授課順序做適當調整。 （2）授課使用的參考書目由任課教師在培訓班開課之前根據(jù)授課內容確定，并與教學大綱一同下發(fā)給學員。五、參考教材1 中國計算機學會主編，2006全國信息學奧林匹克年鑒，河南電子音像出版社，鄭州，2007年1月。 2 中國計算機學會主編，2007全國信息學奧林匹克年鑒，河南電子音像出版社，鄭州，2008年1月。 3 吳文虎、李立新等，全國信息學奧林匹克聯(lián)賽試題精解（2001-2003）（普及本），清華大學出版社，北京，2004年7月。4 吳文虎等，全國信息學奧林匹克聯(lián)賽培訓教程（二）（普及本），清華大學出版社，北京，2