信息學(xué)奧林匹克競賽指導(dǎo)

前言

　　國際信息學(xué)奧林匹克（International 0lympiad in Informatics，IOI）從1989年到1999年，11年賽事的健康發(fā)展得益于聯(lián)合國教科文組織（UNESCO）為這項賽事所做的準(zhǔn)確定位：通過競賽形式對有才華的青少年起到激勵作用，促其能力得以發(fā)展；讓青少年彼此建立聯(lián)系，推動經(jīng)驗交流，給學(xué)校這一類課程增加活力；建立起教育工作者與專家檔次上的國際聯(lián)系，推進學(xué)術(shù)思想的交流。概括起來說，就是啟迪思路，激勵英才，發(fā)展學(xué)科，促進交流?！　W(xué)科奧林匹克是智力與能力的競賽，注重考查全面素質(zhì)與創(chuàng)造能力。從這個意義上講，信息學(xué)奧林匹克活動是素質(zhì)教育的一個大課堂。在我國，每年國家集訓(xùn)隊都要將“怎樣做人，怎樣做事，怎樣求知和怎樣健體”的指導(dǎo)思想納入培訓(xùn)計劃。這11年中國隊共派出參賽選手43人次，累計獲金牌23塊、銀牌11塊、銅牌9塊，屆屆名列前茅，正是因為堅持了全面素質(zhì)教育的指導(dǎo)思想，把造就高素質(zhì)有創(chuàng)造精神的人才作為活動的定位目標(biāo)?！　』仡?1年的競賽可以看出，參加高手云集的這種世界大賽是有相當(dāng)難度的，第一，沒有大綱，賽題范圍沒有界定，誰也無法去猜測每年的主辦國會出什么類型的難題；第二，計算機科學(xué)與技術(shù)發(fā)展很快，層出不窮的新思路和新成果會反映到試題中來；第三，所要解決的試題往往涉及圖論、組合數(shù)學(xué)、人工智能等大學(xué)開設(shè)的課程知識；第四，比較短的給定解題時間與刁難的測試數(shù)據(jù)讓選手必須拿出高超和精巧的解法，無論在時間上還是空間上都是優(yōu)化的解法才能取得高分。有許多賽題沒有固定的現(xiàn)成的解法，選手要在比賽現(xiàn)場憑借實力，理出思路，構(gòu)建數(shù)學(xué)模型，寫出算法，編出程序，運行并驗證整個構(gòu)思是否正確，出解的時間是否能達到題目的要求，等等?？梢钥闯觯谶@一過程中最重要的是要有創(chuàng)造能力。為激發(fā)創(chuàng)新精神，培養(yǎng)創(chuàng)造能力，就需要樹立新的教育觀念和教學(xué)方法，還要利用現(xiàn)代化的教學(xué)手段。引導(dǎo)學(xué)生學(xué)用電腦，在使用中幫助開發(fā)人腦，這可能是信息學(xué)奧林匹克活動的最重要的一個特點。我認為在這項活動中應(yīng)該培養(yǎng)學(xué)生的四種能力：自學(xué)能力；實踐動手能力；創(chuàng)新能力；上網(wǎng)獲取信息，并能區(qū)分有用信息和無用信息的能力。這樣做的結(jié)果使許多選手不但有能力在世界賽場上拿金牌，也有能力在學(xué)校的學(xué)習(xí)中名列前茅。

內(nèi)容概要

本書收錄了1997～1998年國際國內(nèi)信息學(xué)(計算機)奧林匹克競賽試題，重點分析解題思路和方法，其中包括如何根據(jù)題意構(gòu)建數(shù)學(xué)模型與相關(guān)算法，以及如何編寫程序等。

書籍目錄

一，第九屆國際奧林匹克信息學(xué)競賽中國組隊賽試題分析
二，第十四屆全國奧林匹克信息學(xué)競賽試題分析
三，第九屆國際奧林匹克信息學(xué)競賽試題分析
四，第十屆國際奧林匹克信息學(xué)中國組隊賽試題分析
五，第十五屆全國奧林匹克信息學(xué)競賽試題分析
六，第十屆國際奧林匹克信息學(xué)競賽試題分析

章節(jié)摘錄

　　顯然，圖1．2．1中不能求出s至t的關(guān)鍵路徑，但這是否意味問題無解呢？不一定。實際上這是試題設(shè)計者巧設(shè)的一個誤區(qū)，以此告誡選手，尋求正確算法應(yīng)從試題給出的條件和目標(biāo)出發(fā)，而不是生搬硬套“本本”上的算法?！　?．每個項目最早開始時間的計算方法　　正確的算法應(yīng)該是，在項目間制約關(guān)系圖的基礎(chǔ)上，增設(shè)一個人度為0的源點s，表示工程開始。s向每一個頂點引出一條權(quán)為O的有向弧。為了便于判別圖中可能出現(xiàn)的權(quán)和非零的有向環(huán)，除s外的每一個頂點連一條權(quán)為O的自反弧。例如上述例子對應(yīng)的新圖G’見圖1．2．2。　　由于在新圖G中的每個項目可以獨立并行的進行，所以項目i[1≤i≤n（項目數(shù)）]的最早開始時間是從源點s到頂點i的最長路徑的長度，即最長路徑上各活動持續(xù)時間之和。顯然在圖1．2．2中，項目1的最早開始時間一0，項目2的最早開始時間=O。　　如果在圖中出現(xiàn)權(quán)和大于零的有向環(huán)，意味著有向環(huán)上的項目應(yīng)以自己為先決條件，其最早開始時間的計算沿這個有向環(huán)死循環(huán)下去，勢必得出一個無窮大的值，顯然這是荒謬的。因此，一旦在計算過程中發(fā)現(xiàn)路徑長度大于零的有向環(huán)，則算法應(yīng)以無解而告終。

圖書封面

圖書標(biāo)簽Tags

無

評論、評分、閱讀與下載

---

    信息學(xué)奧林匹克競賽指導(dǎo) PDF格式下載

---