冬令營講義王建德提要

1、2003 年冬令營講義2002 年雖然 2001 年信息學(xué)活動的簡析信息學(xué)競賽中含許多可“一題多解”的試題，但如果按照較優(yōu)算法標(biāo)準分類的話，大致可分為2002 年競賽概述算法知識分布特點：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)系日益凸算法分區(qū)聯(lián)賽賽組隊賽物理題落體字符串處理字符近似查找并查集與路徑壓縮模擬策略滅鼠行動回溯法購房計劃數(shù)算選數(shù)、字串變換動態(tài)

2、程序設(shè)計方法級數(shù)求和、 均分紙牌貪吃的九頭龍過河卒二分圖的匹配玩具兵“構(gòu)造法”解題調(diào)皮的小孩、新俄羅斯方塊丹奇方塊貪心法月亮森林數(shù)論（最大公約數(shù)）荒島野人組合分析（函數(shù)）機器人 M 號幾何計算（點和矩形的關(guān)系）矩形覆蓋現(xiàn)，數(shù)學(xué)素質(zhì)好的人雖然不一定會編程，但希望學(xué)習(xí)編程的人愈來愈多；編程解題能力強的人勢必有數(shù)學(xué)的潛質(zhì)和，他們中愈來愈多的人也希望深造數(shù)學(xué)。兩門學(xué)科的交融和整合是信息學(xué)活動發(fā)展的一個大趨勢（有提議，數(shù)學(xué)講算法，信息科技講語言，的信息科技出現(xiàn)真值表（初中）和 c 語言（高中）。2、“構(gòu)造法”(調(diào)皮的小孩、新俄羅斯方塊、丹奇方塊 )或貪心策略類試題（月亮森林）的引入，使得算法知識的不確定

3、性和不穩(wěn)定性增加。這正體現(xiàn)了科學(xué)的本質(zhì)知識是不斷推陳出新的。3、試題的綜合性增加，并不一定隨知識的分類而發(fā)生變化，有時幾乎找不到一個單一的經(jīng)典算法(玩具兵通過最短路徑構(gòu)造二分圖)，也找不到一個純粹的數(shù)據(jù)結(jié)構(gòu)問題（要求計算并查集中元素的相對位置），關(guān)鍵是你從哪個角度去分析，也就是說能不能綜合所學(xué)的知識，應(yīng)用自如地解決問題。選手的綜合素質(zhì)愈高，得勝的機率愈大； ?4、經(jīng)常面對著不知道算法的試題，面對著誰都不知如何處置的情境（經(jīng)常出現(xiàn)許多選手在一題中得 0 分、優(yōu)秀選手表現(xiàn)失常的情況），因此必須使學(xué)生正確地理解問題、深入問題的空間并形成解決問題的意識、和能力。能不能創(chuàng)造性地應(yīng)答沒有遇到過的，成為培訓(xùn)

4、的基本要求和目標(biāo)。啟 示：1、培養(yǎng)問題意識和問題能力。創(chuàng)造始于問題?！坝辛藛栴}才會思考，有了思考才有解決問題的方法，才有找到獨立思路的可能（）”。有問題雖然不一定有創(chuàng)造，但沒有問題一定沒有創(chuàng)造（想當(dāng)前的解法有沒有缺陷，有沒有更好的算法，它與哪些問題有聯(lián)系，與哪些知識相關(guān)聯(lián)，還可以出哪些問題，要解決這些問題還需要哪些知識）；?2、處理好前沿性與基礎(chǔ)性、直線培訓(xùn)和散點培訓(xùn)、循序漸進與跳躍式的。如果恪守按部就班的培訓(xùn)程序，不謀求跳躍式學(xué)習(xí)，將離和國際奧信息學(xué)活動的前沿、離世界程序設(shè)計知識的前沿愈來愈遠。因此在進行基礎(chǔ)課程學(xué)習(xí)的同時，必須有追逐前沿的選擇性學(xué)習(xí)。這里，有時候心理的障礙比科學(xué)上的更難，敢

5、不敢比能不能更突出。其實在學(xué)習(xí)中或多或少地都有必要的跳躍，不少人還能夠?qū)崿F(xiàn)比較大的跳躍（ 2002 年noi 中的函數(shù)、冬令營營員講的 polya 定理、博弈原理和遺傳算法，小學(xué)三年級退學(xué)、.大學(xué)三年級退學(xué)）學(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é)生，讓他們

6、自己去探索若干知識點之間的聯(lián)系，補充自己認為需要補充的知識。3、參與活動的學(xué)生應(yīng)由競爭關(guān)系和獨立關(guān)系（你做你的，程序和算法互相，彼此津津樂道于對方和自己的成功）轉(zhuǎn)向合作學(xué)習(xí)的關(guān)系（通過研討算法、集中編程、互測數(shù)據(jù)等互相合作的方式完成學(xué)習(xí)任務(wù)）前提條件：水平相當(dāng)?shù)耐|(zhì)成員或各有（包括數(shù)學(xué)知識、編程能力和思維方式等解題所需的各種）的異質(zhì)成員是開展合作學(xué)習(xí)的組織基礎(chǔ)；學(xué)生的心理調(diào)適：我掌握的知識僅不過是滄海一粟(進取心)；固守錯誤的概念比一無所知更可怕（明智）；三人之行必有我?guī)煟ㄖt虛）；知識生產(chǎn)社會化條件下人的基本素質(zhì)之一是合作精神（現(xiàn)在的科學(xué)發(fā)明需要成百上千科學(xué)家進行長期甚至的合作，例如制作 windows，人類基因工程）（現(xiàn)代意識）；合作學(xué)習(xí)的效應(yīng)：集思廣益容易出好的算法；群體設(shè)計的測試數(shù)據(jù)相對全面；在群體活動中能比較客觀的反映自己能力情況；每個學(xué)生在付出與給予中可提高合作精神和編程能力，成功者往往是那些相容性好、 樂于幫助他人，并且取