信息學(xué)奧林匹克匯總課件

1、信息學(xué)奧林匹克（Olympiad in Informatics）簡介成都七中 張君亮 About OIOI，即信息學(xué)奧林匹克(Olympiad in Informatics)OI的題目八皇后問題統(tǒng)計110000的數(shù)中末位為7的質(zhì)數(shù)的個數(shù)And moreActivitiesOI的比賽、活動全國聯(lián)賽(NOIP)省級選拔活動四川省冬令營(SCWC)四川省選拔賽(SCTSC)國家級競賽活動全國競賽(NOI)全國冬令營(WC)國家隊選拔賽(CTSC)亞太地區(qū)競賽(APIO)國際競賽(IOI)DetailsNOIPSCWCSCTSCNOIWCAPIOCTSCIOINOIPNOIP，即全國青少年信息學(xué)奧林匹

2、克聯(lián)賽(National Olympiad in Informatics in Provinces)NOIP每年由中國計算機學(xué)會統(tǒng)一組織，全國統(tǒng)一大綱、統(tǒng)一試卷，各省市、自治區(qū)都應(yīng)參加聯(lián)賽，參加聯(lián)賽是參加NOI的必要條件。NOIP是普及性質(zhì)的比賽，其成績也會關(guān)系到其他一些比賽比賽分初賽和復(fù)賽初賽是筆試，主要考察基礎(chǔ)知識復(fù)賽上機考試，內(nèi)容為程序設(shè)計初賽于每年10月的最后一個星期六下午舉行復(fù)賽于每年11月的最后一個星期六舉行，提高上午、普及下午 NOIP分賽區(qū)評獎，設(shè)賽區(qū)一、二、三等獎聯(lián)賽大綱NOIP大綱初賽復(fù)賽在初賽的內(nèi)容上增加以下內(nèi)容： 計算機的基本常識1計算機和信息社會（信息社會的主要特征、

3、計算機的主要特征、數(shù)字通信網(wǎng)絡(luò)的主要特征、數(shù)字化）2信息輸入輸出基本原理（信息交換環(huán)境、文字圖形多媒體信息的輸入輸出方式）3信息的表示與處理（信息編碼、微處理部件MPU、內(nèi)存儲結(jié)構(gòu)、指令，程序，和存儲程序原理、程序的三種基本控制結(jié)構(gòu)）4信息的存儲、組織與管理（存儲介質(zhì)、存儲器結(jié)構(gòu)、文件管理、數(shù)據(jù)庫管理）5信息系統(tǒng)組成及互連網(wǎng)的基本知識（計算機構(gòu)成原理、槽和端口的部件間可擴展互連方式、層次式的互連結(jié)構(gòu)、互聯(lián)網(wǎng)絡(luò)、TCP/IP協(xié)議、HTTP協(xié)議、WEB應(yīng)用的主要方式和特點）6人機交互界面的基本概念（窗口系統(tǒng)、人和計算機交流信息的途徑（文本及交互操作）7信息技術(shù)的新發(fā)展、新特點、新應(yīng)用等。計算機的基

4、本操作1. WINDOWS和LINUX的基本操作知識2. 互聯(lián)網(wǎng)的基本使用常識 （網(wǎng)上瀏覽、搜索和查詢等）3. 常用的工具軟件使用（文字編輯、電子郵件收發(fā)等） 程序設(shè)計的基本知識數(shù)據(jù)結(jié)構(gòu)1程序語言中基本數(shù)據(jù)類型(字符、整數(shù)、長整數(shù)、浮點)2. 浮點運算中的精度和數(shù)值比較3一維數(shù)組（串）與線性表4記錄類型（PASCAL）/ 結(jié)構(gòu)類型（C）程序設(shè)計1結(jié)構(gòu)化程序設(shè)計的基本概念 2閱讀理解程序的基本能力3具有將簡單問題抽象成適合計算機解決的模型的基本能力4具有針對模型設(shè)計簡單算法的基本能力5程序流程描述（自然語言/偽碼/NS圖/其他）6程序設(shè)計語言（PASCAL/C/C+）基本算法的處理1初等算法（計

5、數(shù)、統(tǒng)計、數(shù)學(xué)運算等）2排序算法（冒泡法、插入排序、合并排序、快速排序）3查找（順序查找、二分法）4回溯算法數(shù)據(jù)結(jié)構(gòu)1指針類型2多維數(shù)組3單鏈表及循環(huán)鏈表4二叉樹5文件操作（從文本文件中讀入數(shù)據(jù)，并輸出到文本文件中） 程序設(shè)計1算法的實現(xiàn)能力2程序調(diào)試基本能力3設(shè)計測試數(shù)據(jù)的基本能力4程序的時間復(fù)雜度和空間復(fù)雜度的估計 算法處理1離散數(shù)學(xué)知識的應(yīng)用（如排列組合、簡單圖論、數(shù)理邏輯）2分治思想3模擬法4貪心法5簡單搜索算法（深度優(yōu)先 廣度優(yōu)先）搜索中的剪枝6動態(tài)規(guī)劃的思想及基本算法 SCWC SCTSCSCWC，即四川省冬令營(SiChuan Winter Camp)在每年寒假期間（2月）舉行，

6、地點在成都或者綿陽內(nèi)容主要為講座和省集訓(xùn)隊選拔省集訓(xùn)隊選拔分兩試，共選出12名省集訓(xùn)隊選手（其中必須有2名女生）SCTSC，即四川省隊選拔賽(SiChuans Team Selection Contest)省集訓(xùn)隊選手參加每年6月初，成都共選出5男1女，作為四川省代表隊參加NOI，同時選出2名夏令營選手NOINOI，即全國青少年信息學(xué)奧林匹克競賽(National Olympiad in Informatics)時間一般為每年7月底至8月初，歷時7天每一屆都在全國不同城市舉行NOI2008在浙江紹興各省市自治區(qū)以及港澳地區(qū)都派出一個代表隊參加主要活動有：參觀、交流比賽團體對抗賽NOI比賽共有兩

7、試，比賽評出一、二、三等獎（金銀銅牌）以及優(yōu)秀獎，前20名（即金牌的選手）進入國家集訓(xùn)隊，有資格參加國家隊選拔同期舉行NOI夏令營和NOI網(wǎng)上同步賽Winter Camp 全國冬令營(Winter Camp)于每年寒假期間（1月）舉行，舉辦地點為當(dāng)年NOI承辦地冬令營共8天，其中6天為培訓(xùn)和交流。參加冬令營的營員分：正式營員和非正式營員。獲得NOI前20名的選手和指導(dǎo)教師為正式營員，非正式營員限量自愿報名參加（NOIP成績相關(guān)）冬令營培訓(xùn)內(nèi)容：包括授課、講座、討論、國家集訓(xùn)隊論文答辯、測試論文答辯和測試的成績關(guān)系到正式營員（國家集訓(xùn)隊成員）參加國家隊選拔的最后成績APIO CTSCAPIO，即

8、亞太地區(qū)信息學(xué)奧林匹克競賽(Asia-Pacific Informatics Olympiad)參加者為：國家集訓(xùn)隊成員、NOIP成績?nèi)珖?0、各省的分配名額參賽者前6名作為中國隊的正式選手，參加APIO評比，其余選手評中國賽區(qū)獎中國賽區(qū)的獲獎比例同NOI，即金銀銅牌比例分別為百分之十、二十和三十。 CTSC，即IOI中國隊選拔賽(Chinas Team Selection Contest)，中國OI最高水平的競賽5月中旬，北京CTSC分兩試，第一試即為APIOIOI中國代表隊（4人）的產(chǎn)生：論文、WC、作業(yè)、CTSC、面試IOIIOI，即國際信息學(xué)奧林匹克競賽(International

9、Olympiad in Informatics)自1989年開始舉辦，每年8月舉行，歷時一星期每年由不同國家承辦IOI2008在埃及各國派出代表隊參加中國隊的成績輝煌算法知識分布 雖然2001年全國奧林匹克信息學(xué)競賽中含許多可“一題多解” 的試題，但如果按照較優(yōu)算法標準分類的話，大致可分為 算法分區(qū)聯(lián)賽 全國賽 組隊賽 物理題自由落體字符串處理字符近似查找 并查集與路徑壓縮銀河英雄傳說 模擬策略滅鼠行動回溯法選數(shù)、字串變換 購房計劃 數(shù)學(xué)運算級數(shù)求和、 均分紙牌動態(tài)程序設(shè)計方法頒獎典禮貪吃的九頭龍過河卒算法分區(qū)聯(lián)賽 全國賽 組隊賽 二分圖的匹配玩具兵“構(gòu)造法”解題調(diào)皮的小孩、新俄羅斯方塊丹奇方

10、塊 貪心法月亮森林數(shù)論（最大公約數(shù)）荒島野人組合分析（歐拉函數(shù)）機器人M號幾何計算（點和矩形的關(guān)系）矩形覆蓋信息學(xué)奧林匹克競賽特 點 1、凸現(xiàn)信息學(xué)知識和數(shù)學(xué)知識整合的趨勢。 為了考核學(xué)生的數(shù)學(xué)能力，激發(fā)學(xué)生的創(chuàng)造力，2002年全國奧林匹克信息競賽(NOI)、IOI組隊賽和IOI，數(shù)論(荒島野人)、組合分析(機器人M號)、圖論類(玩具兵)的試題增加，并且首次出現(xiàn)了計算幾何類的試題(矩形覆蓋)。這說明信息學(xué)與數(shù)學(xué)的依賴關(guān)系日益凸現(xiàn)，數(shù)學(xué)素質(zhì)好的人雖然不一定會編程，但希望學(xué)習(xí)編程的人愈來愈多；編程解題能力強的人勢必有數(shù)學(xué)的潛質(zhì)和愛好，他們中愈來愈多的人也希望深造數(shù)學(xué)。兩門學(xué)科的交融和整合是奧林匹克

11、信息學(xué)活動發(fā)展的一個大趨勢（有專家提議，數(shù)學(xué)教材講算法，信息科技教材講語言，上海的信息科技教材出現(xiàn)真值表（初中）和c語言（高中）。 “構(gòu)造法”(調(diào)皮的小孩、新俄羅斯方塊、丹奇方塊 )或貪心策略類試題（月亮森林）的引入，使得算法知識的不確定性和不穩(wěn)定性增加。這正體現(xiàn)了科學(xué)的本質(zhì)知識是不斷推陳出新的。2、算法知識的不確定性和不穩(wěn)定性增加 試題的綜合性增加，并不一定隨知識的分類而發(fā)生變化，有時幾乎找不到一個單一的經(jīng)典算法(玩具兵通過最短路徑構(gòu)造二分圖)，也找不到一個純粹的數(shù)據(jù)結(jié)構(gòu)問題（銀河英雄傳說 要求計算并查集中元素的相對位置），關(guān)鍵是你從哪個角度去分析，也就是說能不能綜合所學(xué)的知識，應(yīng)用自如地解

12、決問題。選手的綜合素質(zhì)愈高，得勝的機率愈大； 3、試題的綜合性增加 經(jīng)常面對著不知道算法的試題，面對著誰都不知如何處置的情境（經(jīng)常出現(xiàn)許多選手在一題中得0分、優(yōu)秀選手表現(xiàn)失常的情況），因此必須使學(xué)生正確地理解問題、深入問題的空間并形成解決問題的意識、習(xí)慣和能力。能不能創(chuàng)造性地應(yīng)答沒有遇到過的挑戰(zhàn)，成為培訓(xùn)的基本要求和目標。4、創(chuàng)造性地應(yīng)答沒有遇到過的挑戰(zhàn)信息學(xué)奧林匹克競賽啟 示 創(chuàng)造始于問題?！坝辛藛栴}才會思考，有了思考才有解決問題的方法，才有找到獨立思路的可能（陶行知）”。有問題雖然不一定有創(chuàng)造，但沒有問題一定沒有創(chuàng)造（想一想當(dāng)前的解法有沒有缺陷，有沒有更好的算法，它與哪些問題有聯(lián)系，與哪些

13、知識相關(guān)聯(lián)，還可以拓延出哪些問題，要解決這些問題還需要哪些知識）；1、培養(yǎng)問題意識和問題能力。 如果恪守按部就班的培訓(xùn)程序，不謀求跳躍式學(xué)習(xí)，將離全國和國際奧林匹克信息學(xué)活動的前沿、離世界程序設(shè)計知識的前沿愈來愈遠。因此在進行基礎(chǔ)課程學(xué)習(xí)的同時，必須有追逐前沿的選擇性學(xué)習(xí)。這里，有時候心理的障礙比科學(xué)上的障礙更難跨越，敢不敢的問題比能不能的問題更突出。其實在學(xué)習(xí)中或多或少地都有必要的跳躍，不少人還能夠?qū)崿F(xiàn)比較大的跳躍（ 2002年noi中的歐拉函數(shù)、冬令營營員講的polya定理、博弈原理和遺傳算法，愛笛生小學(xué)三年級退學(xué)、比爾.蓋茨大學(xué)三年級退學(xué)）2、處理好前沿性與基礎(chǔ)性、直線培訓(xùn)和散點培訓(xùn)、循

14、序漸進與跳躍式的矛盾。學(xué)生必須學(xué)會從浩如煙海的信息中選擇最有價值的知識，構(gòu)建個性化（符合自己能力結(jié)構(gòu)和興趣結(jié)構(gòu)）和競爭需要的知識結(jié)構(gòu)培訓(xùn)內(nèi)容要有選擇性，因為除了出題者，誰也說不清楚在未來競賽中究竟什么知識是必要的（對基礎(chǔ)的理解是主觀的選擇。例如中國、美國和俄羅斯的理科教材大不相同，有的同年級同學(xué)科的教材相差三分之二），因此不可能把所有重要的東西都選擇好了給學(xué)生，而是應(yīng)該將直線培訓(xùn)與散點培訓(xùn)相結(jié)合，選擇部分重要的東西交給學(xué)生，讓他們自己去探索若干知識點之間的聯(lián)系，補充自己認為需要補充的知識。 3、參與活動的學(xué)生應(yīng)由競爭關(guān)系和獨立關(guān)系（你做你的，我干我的，程序和算法互相保密，彼此津津樂道于對方的失敗和自己的成功）轉(zhuǎn)向合作學(xué)習(xí)的關(guān)系（通過研討算法、集中編程、互測數(shù)據(jù)等互相合作的方式完成學(xué)習(xí)任務(wù)）學(xué)生的心理調(diào)適：我掌握的知識僅不過是滄海一粟(進取心)；固守錯誤的概念比一無所知更可怕（明智）；三人之行必有我?guī)煟ㄖt虛）；知識生產(chǎn)社會化條件下人的基本素質(zhì)之一是合作精神（現(xiàn)在的重大科學(xué)發(fā)明需要成百上千科學(xué)家進行長期甚至跨國的合作，例如制作windows，人類基因工程）（現(xiàn)代意識）；前提條件：水平相當(dāng)?shù)耐|(zhì)成員或各有所長（包括數(shù)學(xué)知