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

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

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

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

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

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

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

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

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

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

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

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

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

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

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