計(jì)算機(jī)算法與程序設(shè)計(jì)

前言

“計(jì)算機(jī)算法與程序設(shè)計(jì)”（computer algorithm and programming design）是計(jì)算機(jī)科學(xué)技術(shù)領(lǐng)域研究的重要基礎(chǔ)課程，己成為眾多理工科專業(yè)學(xué)生所喜愛(ài)的必修課之一。眾所周知，計(jì)算機(jī)系統(tǒng)軟件和應(yīng)用軟件，如操作系統(tǒng)、高級(jí)語(yǔ)言編譯器、數(shù)據(jù)庫(kù)管理系統(tǒng)及各種計(jì)算機(jī)應(yīng)用軟件，無(wú)論是單機(jī)環(huán)境的系統(tǒng)軟件，還是分布式、并行計(jì)算軟件都是程序設(shè)計(jì)的結(jié)晶，當(dāng)然都離不開(kāi)算法的設(shè)計(jì)與實(shí)現(xiàn)。計(jì)算機(jī)系統(tǒng)中的任何軟件，都是按特定的算法進(jìn)行設(shè)計(jì)并且編寫(xiě)必需的程序源代碼予以實(shí)現(xiàn)的。算法性能的好壞，直接決定了所實(shí)現(xiàn)軟件性能的優(yōu)劣。對(duì)于算法的設(shè)計(jì)除了需要考慮算法自身的功能外，還需考慮算法的時(shí)空復(fù)雜度，關(guān)鍵是設(shè)計(jì)一個(gè)功能強(qiáng)、效率高、時(shí)空復(fù)雜性低的優(yōu)化算法并用程序?qū)崿F(xiàn)。因此，計(jì)算機(jī)算法與程序設(shè)計(jì)是計(jì)算機(jī)科學(xué)與技術(shù)的一個(gè)核心問(wèn)題，也是大學(xué)計(jì)算機(jī)專業(yè)本科生的一門(mén)重要的專業(yè)基礎(chǔ)課程。本書(shū)的內(nèi)容選材適當(dāng)，循序漸進(jìn)，互相銜接，逐步展開(kāi)，具有系統(tǒng)性、先進(jìn)性和實(shí)用性。（1）系統(tǒng)性。系統(tǒng)深入地介紹計(jì)算機(jī)專業(yè)基礎(chǔ)課程“算法設(shè)計(jì)與分析”的理論知識(shí)；全面地講解程序設(shè)計(jì)對(duì)于算法的設(shè)計(jì)與實(shí)現(xiàn)。全書(shū)包括：算法基礎(chǔ)，數(shù)據(jù)抽象與數(shù)據(jù)結(jié)構(gòu)，初等數(shù)論，組合數(shù)學(xué)初步；講述了遞歸與分治策略，動(dòng)態(tài)規(guī)劃，貪心算法，搜索技術(shù)，圖論算法；進(jìn)一步研究了計(jì)算幾何，排序算法；最后給出了程序設(shè)計(jì)典型實(shí)例。（2）先進(jìn)性。計(jì)算機(jī)應(yīng)用領(lǐng)域?qū)＜?、?yōu)秀的重點(diǎn)高校教師、ACM-ICPC國(guó)際大學(xué)生程序設(shè)計(jì)競(jìng)賽金牌教練，近年的科研與教學(xué)的積累與提煉，內(nèi)容體系先進(jìn)性與計(jì)算機(jī)算法、程序設(shè)計(jì)的有機(jī)結(jié)合的研究成果與經(jīng)驗(yàn)結(jié)晶。

內(nèi)容概要

　　將本科“計(jì)算機(jī)算法與程序設(shè)計(jì)”課程與大學(xué)生程序設(shè)計(jì)競(jìng)賽有機(jī)地結(jié)合是新時(shí)期教學(xué)改革、培養(yǎng)實(shí)用型計(jì)算機(jī)優(yōu)秀人才的創(chuàng)新?！队?jì)算機(jī)算法與程序設(shè)計(jì)》既系統(tǒng)深入地介紹算法設(shè)計(jì)的理論知識(shí)，又詳盡地將其應(yīng)用于實(shí)際編程，做到理論與實(shí)踐的統(tǒng)一。　　書(shū)中首先從理論的角度介紹了算法基礎(chǔ)，數(shù)據(jù)抽象與數(shù)據(jù)結(jié)構(gòu)，初等數(shù)論，組合數(shù)學(xué)初步；講述了遞歸與分治策略，動(dòng)態(tài)規(guī)劃，貪心算法，搜索技術(shù)，圖論算法；進(jìn)一步研究了計(jì)算幾何，排序算法；最后從實(shí)踐的角度給出了程序設(shè)計(jì)典型實(shí)例及詳細(xì)解析。

作者簡(jiǎn)介

朱青，博士，中國(guó)人民大學(xué)信息學(xué)院副教授，高級(jí)CCF會(huì)員：曾于2004年3月-9月在美國(guó)加州大學(xué)圣迭戈分校UCSD作訪問(wèn)學(xué)者。在2007年1月-3月作為訪問(wèn)學(xué)者到香港中文大學(xué)合作研究。2006年獲教育部寶鋼優(yōu)秀教師獎(jiǎng)，2005年獲中國(guó)人民大學(xué)優(yōu)秀教師獎(jiǎng)，2005年國(guó)家精品課程獎(jiǎng)、北京市精品課程獎(jiǎng)、2008年中國(guó)人民大學(xué)教學(xué)改革獎(jiǎng)等獎(jiǎng)勵(lì)。中國(guó)人民大學(xué)ACM-ICPC（ACM國(guó)際大學(xué)生程序競(jìng)賽）代表隊(duì)總教練，曾獲亞洲賽區(qū)金牌，帶隊(duì)進(jìn)入世界總決賽。主要研究方向：網(wǎng)格與并行計(jì)算，分布式系統(tǒng)可信與安全技術(shù)、高性能數(shù)據(jù)庫(kù)與信息檢索、Web Service計(jì)算。

書(shū)籍目錄

第1章 緒論1.1 算法研究的意義1.2 算法與程序1.3 算法的描述工具1.4 算法的復(fù)雜性分析1.4.1 時(shí)間復(fù)雜度1.4.2 空間復(fù)雜度1.5 常用數(shù)學(xué)分析公式第2章 數(shù)據(jù)抽象與數(shù)據(jù)結(jié)構(gòu)2.1 數(shù)據(jù)抽象概念2.1.1 數(shù)據(jù)結(jié)構(gòu)的基本概念和術(shù)語(yǔ)2.1.2 數(shù)據(jù)抽象2.2 基本數(shù)據(jù)結(jié)構(gòu)2.2.1 線性表與向量2.2.2 鏈表2.2.3 棧和隊(duì)列2.2.4 二叉樹(shù)2.2.5 圖2.3 關(guān)鍵數(shù)據(jù)結(jié)構(gòu)拓廣2.3.1 哈希表2.3.2 并查集（等價(jià)類）2.3.3 線段樹(shù)2.3.4 二叉堆第3章 初等數(shù)論3.1 數(shù)論基礎(chǔ)3.1.1 素?cái)?shù)與算術(shù)基本定理3.1.2 最大公約數(shù)與最小公倍數(shù)3.2 同余方程3.2.1 同余方程概念3.2.2 中國(guó)剩余定理3.3 數(shù)論函數(shù)3.3.1 歐拉函數(shù)3.3.2 積性函數(shù)3.4 素?cái)?shù)和整除3.4.1 篩法求素?cái)?shù)3.4.2 整數(shù)Ⅳ的因子函數(shù)3.5 高精度計(jì)算第4章 組合數(shù)學(xué)初步4.1 加法原理與乘法原理4.2 鴿籠原理和Ramsey數(shù)4.3 遞推關(guān)系和生成函數(shù)4.3.1 Fibonacci數(shù)4.3.2 Catalan數(shù)4.3.3 第二類Stirlin9數(shù)4.4 排列組合4.4.1 字典序排列4.4.2 組合算法4.4.3 二項(xiàng)式系數(shù)4.5 容斥原理4.5.1 容斥原理的概念4.5.2 錯(cuò)排問(wèn)題4.6 Polya定理及其應(yīng)用第5章 遞歸與分治策略5.1 遞歸概念5.1.1 遞歸與遞歸調(diào)用5.1.2 遞歸應(yīng)用5.2 分治法概述5.2.1 分治法基本思想5.2.2 分治算法設(shè)計(jì)和特點(diǎn)5.3 分治法的基本應(yīng)用5.3.1 最大最小值5.3.2 Strassen矩陣乘法5.4 分治法解騎士周游5.5 大整數(shù)乘法5.5.1 常規(guī)大整數(shù)乘法5.5.2 分治法解大整數(shù)乘法5.6 棋盤(pán)覆蓋問(wèn)題第6章 貪心算法6.1 貪心算法概述6.1.1 貪心舉例6.1.2 貪心算法的理論基礎(chǔ)6.1.3 貪心算法與動(dòng)態(tài)規(guī)劃算法的區(qū)別6.2 背包問(wèn)題6.3 機(jī)器任務(wù)調(diào)度算法6.3.1 多機(jī)調(diào)度問(wèn)題6.3.2 活動(dòng)安排問(wèn)題6.4 最小生成樹(shù)6.4.1 普里姆（Prim）算法6.4.2 克魯斯卡爾（Kruskal）算法6.5 哈夫曼（Huffman）樹(shù)及其應(yīng)用6.5.1 Huffman樹(shù)6.5.2 哈夫曼編碼6.5.3 Huffman算法的正確性第7章 動(dòng)態(tài)規(guī)劃7.1 動(dòng)態(tài)規(guī)劃算法思想7.1.1 動(dòng)態(tài)規(guī)劃最優(yōu)決策原理7.1.2 動(dòng)態(tài)規(guī)劃求解步驟7.1.3 動(dòng)態(tài)規(guī)劃的數(shù)學(xué)抽象7.2 矩陣連乘問(wèn)題7.3 最長(zhǎng)子序列探索7.3.1 最長(zhǎng)遞增子序列7.3.2 最長(zhǎng)公共子序列7.4 多段圖的最短路徑7.5 資源分配問(wèn)題7.6 樹(shù)狀動(dòng)態(tài)規(guī)劃第8章 搜索技術(shù)8.1 盲目搜索算法8.1.1 對(duì)分搜索8.1.2 DFS與BFS搜索算法8.1.3 盲目搜索算法應(yīng)用8.2 回溯算法8.3 啟發(fā)式搜索8.3.1 啟發(fā)式搜索策略8.3.2 A*算法8.4 博弈問(wèn)題8.4.1 博弈樹(shù)8.4.2 極小極大搜索法8.5 α-β剪枝技術(shù)第9章 圖論算法9.1 基本概念和定理9.1.1 可行遍性問(wèn)題9.1.2 平面圖9.1.3 獨(dú)立集、覆蓋與支配集9.2 最短路徑9.2.1 Diikstra算法9.2.2 Floyd算法求一對(duì)點(diǎn)最短路徑9.3 道路和回路9.3.1 歐拉道路和歐拉回路9.3.2 哈密爾頓圖和貨郎擔(dān)問(wèn)題9.4 網(wǎng)絡(luò)流算法9.4.1 基本概念9.4.2 最大流問(wèn)題9.4.3 最小費(fèi)用流9.5 二分圖相關(guān)問(wèn)題9.5.1 二分圖的最大匹配9.5.2 二分圖的最佳匹配第10章 計(jì)算幾何10.1 計(jì)算幾何基本問(wèn)題10.1.1 矢量與線段10.1.2 幾何計(jì)算公式10.2 點(diǎn)與線段的關(guān)系10.2.1 點(diǎn)與線段的距離10.2.2 線段與直線的交點(diǎn)10.3 多邊形10.3.1 多邊形基本概念10.3.2 點(diǎn)與多邊形的關(guān)系10.4 凸包問(wèn)題10.4.1 判斷凸包10.4.2 尋找凸包10.5 歐拉定理及其應(yīng)用.第11章 排序11.1 排序基礎(chǔ)11.2 比較排序法11.2.1 插入排序11.2.2 冒泡排序11.2.3 簡(jiǎn)單選擇排序11.3 基于分治策略的排序算法11.3.1 快速排序11.3.2 歸并排序11.4 堆排序11.4.1 樹(shù)狀選擇排序11.4.2 堆排序11.5 基數(shù)排序11.6 排序小結(jié)第12章 算法與程序經(jīng)典實(shí)例12.1 計(jì)算機(jī)算法設(shè)計(jì)實(shí)例12.2 國(guó)際競(jìng)賽程序?qū)嵗治?/pre>


章節(jié)摘錄
插圖：第1章 緒論計(jì)算機(jī)算法與程序設(shè)計(jì)（Computer Algorithm and Programming Design）是計(jì)算機(jī)科學(xué)技術(shù)領(lǐng)域研究的重要基礎(chǔ)課程，目前在各個(gè)高校普遍開(kāi)設(shè)的本科課程，已成為眾多理工科專業(yè)學(xué)生所喜愛(ài)的選修課之一。算法（algorithm）是一組有限規(guī)則，即為某個(gè)特定問(wèn)題提供了計(jì)算機(jī)求解的運(yùn)算序列。通俗點(diǎn)說(shuō)，就是計(jì)算機(jī)解題的過(guò)程。算法分為并行算法和“傳統(tǒng)意義”上的單處理器計(jì)算機(jī)上執(zhí)行的算法，本書(shū)重點(diǎn)研究后者，重點(diǎn)講述構(gòu)成算法與程序的基本方法，解題思路，求解過(guò)程，求解效果的優(yōu)劣分析等重要特征。本章主要內(nèi)容：1.1節(jié)算法研究的意義，列舉多個(gè)實(shí)例，詳細(xì)討論“算法，的概念和研究算法的意義；1.2節(jié)算法與程序，講述算法如何逐步求精，實(shí)現(xiàn)程序設(shè)計(jì)；1.3節(jié)算法的描述工具，討論算法的偽代碼表示，說(shuō)明算法的精確描述工具；l.4節(jié)算法的復(fù)雜性分析，簡(jiǎn)要介紹算法分析技術(shù)，研究時(shí)間復(fù)雜度與空問(wèn)復(fù)雜度分析；1.5節(jié)常用數(shù)學(xué)分析公式，提出在算法分析中實(shí)施計(jì)算的一些必備數(shù)學(xué)基礎(chǔ)，這些方法將會(huì)幫助設(shè)計(jì)和分析算法。1.1 算法研究的意義隨著信息技術(shù)的發(fā)展，計(jì)算機(jī)算法與程序設(shè)計(jì)的普及，依據(jù)其難易等級(jí)，已從大學(xué)本科課程、研究生基礎(chǔ)教學(xué)擴(kuò)展到中學(xué)、高職高專教育；尤其是計(jì)算機(jī)信息類ACM國(guó)際大學(xué)生程序設(shè)計(jì)競(jìng)賽（ACM International Collegiate Programming Contest，ACM—ICPC），中學(xué)信息學(xué)奧林匹克國(guó)際競(jìng)賽，已從計(jì)算機(jī)算法與程序設(shè)計(jì)研究的高端到低端全面展開(kāi)。其目的是培養(yǎng)學(xué)生良好的程序設(shè)計(jì)技巧和熟練的算法分析能力，能夠開(kāi)發(fā)出高效率的有效高級(jí)語(yǔ)言程序。




編輯推薦
《計(jì)算機(jī)算法與程序設(shè)計(jì)》是由清華大學(xué)出版社出版的。





圖書(shū)封面



圖書(shū)標(biāo)簽Tags
無(wú)




評(píng)論、評(píng)分、閱讀與下載



還沒(méi)讀過(guò)(64)
勉強(qiáng)可看(467)
一般般(798)
內(nèi)容豐富(3309)
強(qiáng)力推薦(271)


 


    計(jì)算機(jī)算法與程序設(shè)計(jì) PDF格式下載