計算機算法與程序設計

前言

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

內容概要

　　將本科“計算機算法與程序設計”課程與大學生程序設計競賽有機地結合是新時期教學改革、培養(yǎng)實用型計算機優(yōu)秀人才的創(chuàng)新?！队嬎銠C算法與程序設計》既系統(tǒng)深入地介紹算法設計的理論知識，又詳盡地將其應用于實際編程，做到理論與實踐的統(tǒng)一?！　惺紫葟睦碚摰慕嵌冉榻B了算法基礎，數據抽象與數據結構，初等數論，組合數學初步；講述了遞歸與分治策略，動態(tài)規(guī)劃，貪心算法，搜索技術，圖論算法；進一步研究了計算幾何，排序算法；最后從實踐的角度給出了程序設計典型實例及詳細解析。

作者簡介

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

書籍目錄

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

章節(jié)摘錄

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

編輯推薦

《計算機算法與程序設計》是由清華大學出版社出版的。

圖書封面

圖書標簽Tags

無

評論、評分、閱讀與下載

---

    計算機算法與程序設計 PDF格式下載

---