信息學(xué)奧林匹克教程·提高篇

內(nèi)容概要

全國青少年信息學(xué)奧林匹克競賽(NOI)和聯(lián)賽(NOIP)是由教育部、中國科協(xié)批準(zhǔn)和舉辦的面向全國青少年在校學(xué)生的一項重大賽事，每年在全國各省、市、自治區(qū)舉行。它與國際信息學(xué)奧林匹克競賽(IOI)直接接軌。該項賽事已成為我國校外計算機活動中最有代表性的形式，每年都吸引著數(shù)以萬計的青少年投身到這一活動當(dāng)中。 　 NOl和NOIP在試題難度上有一個層次關(guān)系，NOl注重提高，人數(shù)相對少一點，而NOIP注重普及，每年參加的人數(shù)較多，普及面相對較廣。由于NOl競賽的內(nèi)容多，而且目前使用的信息技術(shù)教材內(nèi)容與競賽不完全適應(yīng)，為此，湖南師范大學(xué)出版社和湖南省青少年信息學(xué)奧林匹克競賽組織委員會組織多年從事信息學(xué)奧林匹克競賽命題、培訓(xùn)等工作的專家、教授、博士和湖南省信息學(xué)奧賽優(yōu)秀輔導(dǎo)教師編寫了這套“信息學(xué)奧林匹克教程”。該書是作者十幾年來培養(yǎng)學(xué)生參加國際、國內(nèi)信息學(xué)奧林匹克競賽的經(jīng)驗總結(jié)。全套教程分為三本，其中《語言篇》主要介紹競賽規(guī)定語言之一，也是競賽使用最為廣泛、最適應(yīng)競賽的編程語言——Turbo Pascal 7.0環(huán)境、語句與程序結(jié)構(gòu)；《基礎(chǔ)篇》主要面向競賽入門的學(xué)生，介紹了國際、國內(nèi)青少年信息學(xué)奧林匹克競賽活動的發(fā)展、競賽條例和規(guī)程，以及信息學(xué)奧林匹克的指導(dǎo)思想、命題原則和教育思想，詳細(xì)闡述了計算機基礎(chǔ)知識、算法概述、簡單數(shù)據(jù)結(jié)構(gòu)和基礎(chǔ)算法模型等，培養(yǎng)學(xué)生參加NOIP的活動；《提高篇》主要針對提高競賽水平的學(xué)生，詳細(xì)闡述了基本算法設(shè)計策略、搜索及搜索優(yōu)化方法、圖論算法處理及其動態(tài)規(guī)劃的應(yīng)用等內(nèi)容，為適應(yīng)信息學(xué)競賽新的發(fā)展的需要，還簡單介紹了Linux操作系統(tǒng)、Gcc、Free Pascal編程環(huán)境。    整套教程根據(jù)NOIP、NOl及IOl的要求，以算法為主線，以習(xí)題分析為載體，深入淺出，既有各個算法設(shè)計基本思路的講解及對求解問題的分析，注重了算法引導(dǎo)分析與不同算法的比較，又給出了具體的編程思路與參考程序，程序采用信息學(xué)競賽流行的Turbo Pascal 7.0語言編寫，并注重結(jié)構(gòu)化與可讀性，并提供了競賽模擬試題，方便讀者檢測競賽學(xué)生或自我檢測。    　  該教程是一套中學(xué)生參加IOl和NOl、NOIP的培訓(xùn)教材，《提高篇》也可作為大學(xué)生參加國際ACM競賽的培訓(xùn)教材，并可作為大、中學(xué)生學(xué)習(xí)和研究算法設(shè)計的參考用書。

作者簡介

吳耀斌
    中南大學(xué)計算機科學(xué)與技術(shù)專業(yè)副教授。編著《信息學(xué)奧林匹克教程》《信息學(xué)(計算機)奧林匹克Turbo C++2.0》等教材20本，已發(fā)表論文30余篇，多次獲得省部級科技進(jìn)步和教學(xué)成果獎?，F(xiàn)任國家信息學(xué)奧林匹克聯(lián)賽湖南省特派員、國家信息學(xué)奧林匹克競賽湖南省領(lǐng)隊、湖南省信息學(xué)奧林匹克競賽組織委員會副主任兼秘書長。

書籍目錄

1　基本算法設(shè)計策略　1.1　枚舉策略　1.2　歸納策略　1.3　遞推策略　1.4　遞歸算法策略　1.5　分治策略　1.6　貪心策略　1.7　模擬方法2　深度優(yōu)先和廣度優(yōu)先　2.1　產(chǎn)生式系統(tǒng)　2.2　深度優(yōu)先搜索　2.3　廣度優(yōu)先搜索　2.4　深度優(yōu)先和廣度優(yōu)先搜索的深入討論　2.5　深度優(yōu)先搜索中的剪枝優(yōu)化方法　2.6　廣度優(yōu)先搜索的優(yōu)化方法　2.7　搜索對象與策略的選取3　圖論算法　3.1　最小生成樹　3.2　最短路徑的算法　3.3　拓?fù)渑判蛩惴ā?.4　關(guān)鍵路徑的算法　3.5　網(wǎng)絡(luò)流算法　3.6　圖論模型的構(gòu)造4　動態(tài)規(guī)劃　4.1　動態(tài)規(guī)劃的基本模型　4.2　動態(tài)規(guī)劃的設(shè)計與實現(xiàn)　4.3　動態(tài)規(guī)劃的深入思考　4.4　動態(tài)規(guī)劃與其他算法的比較5　排序　5.1　簡單排序算法　5.2　快速排序　5.3　堆排序　5.4　線性時間排序　5.5　排序的應(yīng)用6　模型構(gòu)建與綜合算法設(shè)計  6.1　模型的建立  6.2　構(gòu)造法解題和綜合算法設(shè)計7　Linttx操作系統(tǒng)與編程環(huán)境　7.1　Linux操作系統(tǒng)　7.2　Gee編程環(huán)境　7.3　Free Pascal編程環(huán)境　7.4　模擬試題

章節(jié)摘錄

　　1　基本算法設(shè)計策略　　在信息學(xué)奧林匹克競賽中，其主要任務(wù)是設(shè)計一個有效的算法，去求解所給出的問題。實際問題的算法設(shè)計方法總是建立在各種基本算法設(shè)計策略的基礎(chǔ)上，本章將圍繞設(shè)計算法時常用的一些基本算法設(shè)計策略來展開討論，如枚舉、歸納、遞推和遞歸、分治、數(shù)學(xué)方法等。在介紹每一種基本算法設(shè)計策略時，給出了算法效率的分析和應(yīng)用的實例。讀者通過本章的學(xué)習(xí)，應(yīng)該掌握基本的算法設(shè)計策略以及如何在競賽中運用這些策略找到解決問題的具體思考方法?！　?．1　枚舉策略　　1．1．1適合枚舉策略的問題　　枚舉法，常常稱之為窮舉法，是指在一個有窮的可能的解的集合中，枚舉出集合中的每一個元素，用問題給定的解的檢驗條件去判斷其是否符合條件，若滿足條件，該元素即為問題的一個解，若不滿足，該元素就不是這一問題的解?！　∶杜e的思想往往是最容易想到的一種解題策略，枚舉方法從本質(zhì)上說，它是一種搜索算法，即對問題的所有可能解的狀態(tài)集合進(jìn)行一次掃描或遍歷。因此，適合枚舉策略求解的問題，首先必須滿足其問題規(guī)模和可能解的規(guī)模(個數(shù))不是特別大，且解變量的值的變化具有一定的規(guī)律性，在具體的程序?qū)崿F(xiàn)過程中，可以通過循環(huán)和條件判斷語句來完成。

編輯推薦

《信息學(xué)奧林匹克教程》(提高篇)是作者幾年來成功培養(yǎng)學(xué)生參加國際、國內(nèi)信息學(xué)奧林匹克競賽并獲獎的經(jīng)驗總結(jié)。

圖書封面

圖書標(biāo)簽Tags

無

評論、評分、閱讀與下載

---

    信息學(xué)奧林匹克教程·提高篇 PDF格式下載

---