算法藝術與信息學競賽

定　價：￥45.00

作　者：	劉汝佳，黃亮著
出版社：	清華大學出版社
叢編項：
標　簽：	算法

購買這本書可以去

ISBN：	9787302078005	出版時間：	2004-01-01	包裝：	精裝
開本：	24cm	頁數(shù)：	428	字數(shù)：

內(nèi)容簡介

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

作者簡介

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

圖書目錄

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