123,123

內(nèi)容簡(jiǎn)介

　　《算法藝術(shù)與信息學(xué)競(jìng)賽》較為系統(tǒng)和全面地介紹了算法學(xué)最基本的知識(shí)。這些知識(shí)和技巧既是高等院?！八惴ㄅc數(shù)據(jù)結(jié)構(gòu)”課程的主要內(nèi)容，也是國(guó)際青少年信息學(xué)奧林匹克（IOI）競(jìng)賽和ACM/ICPC國(guó)際大學(xué)生程序設(shè)計(jì)競(jìng)賽中所需要的。書中分析了相當(dāng)數(shù)量的問題。本書共3章。第1章介紹算法與數(shù)據(jù)結(jié)構(gòu)；第2章介紹數(shù)學(xué)知識(shí)和方法；第3章介紹計(jì)算機(jī)幾何。全書內(nèi)容豐富，分析透徹，啟發(fā)性強(qiáng)，既適合讀者自學(xué)，也適合于課堂講授。本書適用于各個(gè)層次的信息學(xué)愛好者、參賽選手、輔導(dǎo)老師和高等院校計(jì)算機(jī)專業(yè)的師生。本書既是信息學(xué)入門和提高的好幫手，也是一本內(nèi)容豐富、新穎的資料集。

作者簡(jiǎn)介

　　劉汝佳，1982年12月生。于2000年3月獲得NOI2000全國(guó)青少年信息學(xué)奧林匹克競(jìng)賽一等獎(jiǎng)第四名，進(jìn)入國(guó)家集訓(xùn)隊(duì)，并因此保送到清華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系學(xué)習(xí)至今。2000年9月建立個(gè)人網(wǎng)站“信息學(xué)初學(xué)者之家（OIBH）”，該網(wǎng)站現(xiàn)已成為國(guó)內(nèi)最具影響力的信息學(xué)競(jìng)賽網(wǎng)站之一。大一時(shí)參加ACM/ICPC國(guó)際大學(xué)生程序設(shè)計(jì)競(jìng)賽，獲得2001年亞洲-上海賽區(qū)冠軍和2002年世界總決賽銀牌（世界第四），并擔(dān)任2002年和2003年北京賽區(qū)裁判。2003年12月為止全國(guó)青少年信息學(xué)競(jìng)賽（NOI）、IOI中國(guó)國(guó)家隊(duì)選拔賽、科令營(yíng)、ACM/ICPC亞洲分區(qū)賽命題10余道。擔(dān)任IOI2002、2003和2004三屆中國(guó)國(guó)家集訓(xùn)隊(duì)教練，并在重慶、成都、長(zhǎng)沙、北京、天津等地授課多次，深受選手歡迎。于2002年底被中國(guó)計(jì)算機(jī)學(xué)會(huì)聘為全國(guó)青少年信息學(xué)競(jìng)賽科學(xué)委員會(huì)學(xué)生委員。

圖書目錄

第1章  算法與數(shù)據(jù)結(jié)構(gòu)
  1.1  編程的靈魂——數(shù)據(jù)結(jié)構(gòu)+算法=程序
  1.2  基本算法
    1.2.1  枚舉
    1.2.2  貪心法
    1.2.3  遞歸與分治法
    1.2.4  遞推
  1.3  數(shù)據(jù)結(jié)構(gòu)(1)——入門
    1.3.1  棧和隊(duì)列
    1.3.2  串
    1.3.3  樹和二叉樹
    1.3.4  圖及其基本算法
    1.3.5  排序與檢索基本算法
  1.4  數(shù)據(jù)結(jié)構(gòu)(2)——拓寬和應(yīng)用舉例
    1.4.1  并查集
    1.4.2  堆及其變種
    1.4.3  字典的兩種實(shí)現(xiàn)方式：哈希表、二叉搜索樹
    1.4.4  兩個(gè)特殊樹結(jié)構(gòu)：線段樹和Trie
  1.5  動(dòng)態(tài)規(guī)劃
    1.5.1  動(dòng)態(tài)規(guī)劃的兩種動(dòng)機(jī)
    1.5.2  常見模型的分析
    1.5.3  若干經(jīng)典問題和常見優(yōu)化方法
  1.6  狀態(tài)空間搜索
    1.6.1  狀態(tài)空間
    1.6.2  盲目搜索算法
    1.6.3  啟發(fā)式搜索算法
    1.6.4  博弈問題算法
    1.6.5  剪枝
   *1.6.6  專題：路徑尋找問題
   *1.6.7  約束滿足問題
第2章  數(shù)學(xué)方法與常見模型
  2.1  代數(shù)方法和模型
  2.2  數(shù)論基礎(chǔ)
    2.2.1  素?cái)?shù)和整除問題
    2.2.2  進(jìn)位制
    2.2.3  同余模算術(shù)
  2.3  組合數(shù)學(xué)初步
    2.3.1  鴿籠原理和Ramsey定理
    2.3.2  排列組合和容斥原理
    2.3.3  群論與P61ya定理
    2.3.4  遞推關(guān)系與生成函數(shù)
    2.3.5  離散變換與反演
  2.4  圖論基本知識(shí)和算法
    2.4.1  基本概念和定理
    2.4.2  可行遍性問題簡(jiǎn)介
    2.4.3  平面圖
    2.4.4  圖的基本算法與應(yīng)用舉例
  2.5  圖論基本算法
    2.5.1  生成樹問題
    2.5.2  最短路問題
    2.5.3  網(wǎng)絡(luò)流問題
    2.5.4    分圖相關(guān)問題和模型
第3章  計(jì)算幾何初步
  3.1  位置和方向的世界——計(jì)算幾何的基本問題
    3.1.1  從相交到左右——基本問題的轉(zhuǎn)化
    3.1.2  左右和前后——叉積和點(diǎn)積
  3.2  多邊形和多面體的相關(guān)問題
    3.2.1  衛(wèi)兵問題——多邊形和多面體的概念
    3.2.2  求多邊形、多面體的容積和重心；高維情形
    3.2.3  判點(diǎn)在形內(nèi)形外形上；多面體的情形
  3.3  打包裹與制造合金——凸包及其應(yīng)用
    3.3.1  凸包的普遍性和廣泛應(yīng)用性；凸的定義與優(yōu)美性質(zhì)
    3.3.2  凸包的實(shí)現(xiàn)
    3.3.3  凸包算法正確性與時(shí)間效率
    3.3.4  應(yīng)用舉例
    3.3.5  凸多邊形的深入討論
  3.4  幾種常用的特殊算法
    3.4.1  蛋糕被切成幾塊?——離散化法
    3.4.2  切蛋糕的周長(zhǎng)和面積——掃除法
    3.4.3  凸包與快速排序——分治法
    3.4.4  凸包的又一種求法——增量法
    3.4.5  專題——隨機(jī)增量算法
參考文獻(xiàn)