123,123,123

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

　　本書是針對(duì)世界大學(xué)生程序設(shè)計(jì)競(jìng)賽（ACM/ICPC）而編寫的參考書。ACM/ICPC是大學(xué)生的智力與計(jì)算機(jī)解題能力的競(jìng)賽，是世界公認(rèn)的最具影響力的、規(guī)模最大的國(guó)際頂級(jí)賽事，被稱為大學(xué)生的信息學(xué)奧林匹克。計(jì)算機(jī)解題的核心是算法設(shè)計(jì)，而算法設(shè)計(jì)需要具備良好的數(shù)學(xué)素養(yǎng)。數(shù)學(xué)具有運(yùn)用抽象思維去把握實(shí)際的能力，應(yīng)用數(shù)學(xué)知識(shí)去解決實(shí)際問題時(shí)的建模過程是一個(gè)突出主要因素的科學(xué)抽象過程。進(jìn)行抽象和形式化需要學(xué)習(xí)和掌握常用的計(jì)算思維方式。本書主要介紹了大賽程序設(shè)計(jì)中的常用思維方式，主要包括正確認(rèn)識(shí)和處理整體與部分的關(guān)系、構(gòu)造性思維、目標(biāo)轉(zhuǎn)化的思想、分類與分治思想、逆向思維、猜想與試驗(yàn)六個(gè)章節(jié)，旨在引導(dǎo)參賽學(xué)生學(xué)習(xí)并掌握編程解題的一般思維方法和過程，提高解題能力。本書面向參加世界大學(xué)生程序設(shè)計(jì)競(jìng)賽（ACM/ICPC）的高等院校學(xué)生，也可作為程序設(shè)計(jì)愛好者的參考用書。

作者簡(jiǎn)介

　　吳文虎，教授1955年—1961年分別就讀于清華大學(xué)電機(jī)工程系及自動(dòng)控制系，現(xiàn)為計(jì)算機(jī)系教授、博士生導(dǎo)師，主要研究方向包括語音識(shí)別及語言理解、語音合成、語音信號(hào)數(shù)字處理等。吳教授學(xué)術(shù)水平精湛、教學(xué)水平高超、教學(xué)經(jīng)驗(yàn)豐富。多年來用對(duì)學(xué)生無私的愛詮釋了最好的師恩師德。他于1997年獲清華大學(xué)優(yōu)秀教學(xué)成果特等獎(jiǎng)，1998年獲“全國(guó)優(yōu)秀教師一等獎(jiǎng)”，1999年獲國(guó)家科技部（原國(guó)家科委）授予的“全國(guó)科學(xué)普及先進(jìn)個(gè)人獎(jiǎng)”。1999年榮獲“首都勞動(dòng)獎(jiǎng)?wù)隆保?001年獲“全國(guó)師德先進(jìn)個(gè)人獎(jiǎng)”，2001年、2004年獲北京市高等教育教學(xué)優(yōu)秀成果一等獎(jiǎng)，2003年為本科生講授的“程序設(shè)計(jì)基礎(chǔ)”課程被列為教育部首批“國(guó)家級(jí)精品課”，2004年獲中國(guó)計(jì)算機(jī)學(xué)會(huì)頒發(fā)的“杰出貢獻(xiàn)獎(jiǎng)”，2006年獲北京市高等教育教學(xué)名師獎(jiǎng)；吳教授深受清華學(xué)子的愛戴，2003年獲清華大學(xué)教書育人獎(jiǎng)。2005年獲清華大學(xué)第八屆“良師益友”榮譽(yù)稱號(hào)。2008年被清華大學(xué)學(xué)生會(huì)評(píng)為第一屆“我最喜愛的教師”。從1989年至今，吳教授作為總教練和領(lǐng)隊(duì)，曾15次帶領(lǐng)中國(guó)隊(duì)參加國(guó)際信息學(xué)奧林匹克競(jìng)賽，中國(guó)隊(duì)累計(jì)獲金牌51塊，屆屆名列前茅，2002年獲信息學(xué)奧林匹克國(guó)際委員會(huì)頒發(fā)的“特別貢獻(xiàn)獎(jiǎng)”。1997年—2008年，吳教授連續(xù)13年指導(dǎo)清華大學(xué)的學(xué)生進(jìn)入ACM世界大學(xué)生程序設(shè)計(jì)大賽總決賽，多次獲金牌、銀牌，并于2009年被大賽組委會(huì)授予“杰出教練獎(jiǎng)”。

圖書目錄

第1章正確認(rèn)識(shí)和處理整體與部分的關(guān)系
　1.1 整體實(shí)現(xiàn)的關(guān)鍵是準(zhǔn)確地應(yīng)用必要條件
　　1.1.1 選擇有助于簡(jiǎn)化問題、變難為易的必要條件
　　1.1.2 合成必要條件，從整體結(jié)構(gòu)上優(yōu)化
　　1.1.3 必要條件與原有模型比較，更新算法
　　小結(jié)
　1.2 整體思考的一個(gè)重要角度是“守恒”
　　1.2.1 從具體問題中抽象出守恒量
　　1.2.2 根據(jù)問題的本質(zhì)構(gòu)造守恒量
　　1.2.3 在交互問題中構(gòu)造變化中的不變量
　　小結(jié)
　1.3 提高整體實(shí)現(xiàn)效率的基本途徑是“充分利用有效信息”和“壓縮冗余信息”
　　1.3.1 計(jì)算過程中充分利用有效信息
　　1.3.2 通過“壓縮法”消除冗余的圖形和數(shù)據(jù)信息
　　小結(jié)
　1.4 改善整體性能狀態(tài)的基礎(chǔ)是處理好細(xì)節(jié)問題
　　1.4.1 必須解決導(dǎo)致錯(cuò)誤結(jié)果的細(xì)節(jié)問題
　　1.4.2 爭(zhēng)取降低算法時(shí)間復(fù)雜度的階
　　1.4.3 注意降低算法時(shí)間復(fù)雜度的系數(shù)
　　小結(jié)
第2章構(gòu)造性思維
　2.1 模型的基本概念
　　2.1.1 模型的一般特點(diǎn)與功能
　　2.1.2 模型的一般分類
　　2.1.3 模型與信息原型間的關(guān)系
　　小結(jié)
　2.2 建模的一般方法
　　2.2.1 建模的機(jī)理分析方法
　　2.2.2 建模的統(tǒng)計(jì)分析法
　　小結(jié)
　2.3 建模的一般思維方式
　　2.3.1 直接構(gòu)造法
　　2.3.2 分類構(gòu)造法
　　2.3.3 歸納構(gòu)造法
　　小結(jié)
　2.4 在建模過程中注意應(yīng)用序關(guān)系
　　2.4.1 在交互式問題中應(yīng)用序
　　2.4.2 利用典型的“序”關(guān)系簡(jiǎn)化問題
　　2.4.3 尋找蘊(yùn)涵在題意中的序關(guān)系
　　小結(jié)
　2.5 模型選擇
　　小結(jié)
第3章目標(biāo)轉(zhuǎn)化的思想
　3.1 “降維”——縮小目標(biāo)
　　3.1.1 引入“降維思想”
　　3.1.2 高維降為低維
　　3.1.3 一般降為特殊
　　3.1.4 抽象降為具體
　　3.1.5 整體降為局部
　　3.1.6 簡(jiǎn)化數(shù)據(jù)關(guān)系
　　小結(jié)
　3.2 “升維”——放大目標(biāo)
　　3.2.1 讓步假設(shè)
　　3.2.2 倍增思想
　　小結(jié)
第4章分類與分治思想
　4.1 應(yīng)用于一般有序序列的二分法
　　4.1.1 在給定的序列中“二分查找”
　　4.1.2 在交互式問題中應(yīng)用“二分插入”
　　小結(jié)
　4.2 應(yīng)用于退化了的有序序列的“二分枚舉”
　　4.2.1 用二分枚舉求可行方案
　　4.2.2 用二分枚舉求最優(yōu)性問題
　　小結(jié)
　4.3 應(yīng)用于無序序列的“二分搜索”
　　4.3.1 在“二分搜索”的基礎(chǔ)上構(gòu)造可行解
　　4.3.2 在“二分搜索”的基礎(chǔ)上構(gòu)造最優(yōu)解
　　小結(jié)
　4.4 應(yīng)用于多維情況的“多重二分”
　　小結(jié)
第5章逆向思維
第6章猜想與試驗(yàn)