算法分析與設(shè)計(jì)

前言

　　“算法分析與設(shè)計(jì)”是一門理論性與實(shí)踐性結(jié)合很強(qiáng)的課程。在信息技術(shù)高速發(fā)展的今天，計(jì)算機(jī)技術(shù)已經(jīng)應(yīng)用到了很多科學(xué)領(lǐng)域。從理論上來(lái)說(shuō)，算法研究已經(jīng)被公認(rèn)為是計(jì)算機(jī)科學(xué)的基石。David Harel在他的《算法學(xué)： 計(jì)算精髓》一書中說(shuō)道： “算法不僅是計(jì)算機(jī)科學(xué)的一個(gè)分支，它更是計(jì)算機(jī)科學(xué)的核心。可以毫不夸張地說(shuō)，它和絕大多數(shù)的科學(xué)、商業(yè)和技術(shù)都是相關(guān)的?！薄　〗陙?lái)，針對(duì)大學(xué)生的各種類型的程序設(shè)計(jì)競(jìng)賽開展得越來(lái)越多，比較常見的有ACM?ICPC、TopCoder、百度之星、Google挑戰(zhàn)賽、有道難題等。其中ACM國(guó)際大學(xué)生程序設(shè)計(jì)競(jìng)賽（ACM International Collegiate Programming Contest，ACM?ICPC），是歷史最悠久、規(guī)模最大的競(jìng)賽。競(jìng)賽題目涉及的知識(shí)面廣，難度大； 主要強(qiáng)調(diào)算法的高效性，不僅要解決一個(gè)指定的命題，而且必須要以最佳的方式解決指定的命題； 涉及知識(shí)與大學(xué)計(jì)算機(jī)專業(yè)本科以及研究生如程序設(shè)計(jì)、離散數(shù)學(xué)、數(shù)據(jù)結(jié)構(gòu)、人工智能、算法分析與設(shè)計(jì)等相關(guān)課程直接關(guān)聯(lián)，對(duì)數(shù)學(xué)要求很高?！　≡贏CM國(guó)際大學(xué)生程序設(shè)計(jì)競(jìng)賽中，在線裁判系統(tǒng)是開展競(jìng)賽的核心，它是一個(gè)在線的程序與算法設(shè)計(jì)的練習(xí)和競(jìng)賽平臺(tái)。系統(tǒng)可以提供大量的關(guān)于程序和算法設(shè)計(jì)的題目供學(xué)生練習(xí)或競(jìng)賽，學(xué)生可以使用自己熟悉的語(yǔ)言提交相關(guān)題目的程序代碼，系統(tǒng)編譯提交代碼，如果沒有錯(cuò)誤，則生成可執(zhí)行文件。利用系統(tǒng)的測(cè)試用例來(lái)測(cè)試，如果輸出結(jié)果正確，則返回程序消耗的內(nèi)存空間和時(shí)間。對(duì)于競(jìng)賽題目，系統(tǒng)可以從程序正確性、運(yùn)行總時(shí)間、消耗內(nèi)存空間、返回結(jié)果等方面來(lái)考查學(xué)生提交的代碼。系統(tǒng)可以實(shí)現(xiàn)在指定的時(shí)間段舉行競(jìng)賽的功能，根據(jù)學(xué)生解題數(shù)目和時(shí)間進(jìn)行排名，也可以批量導(dǎo)出學(xué)生代碼進(jìn)行分析?！　』诔绦蛟O(shè)計(jì)競(jìng)賽的教學(xué)模式的優(yōu)勢(shì)： 　?。?） 提供了一個(gè)開放的、自主學(xué)習(xí)的實(shí)驗(yàn)環(huán)境，在線評(píng)測(cè)系統(tǒng)通過(guò)網(wǎng)絡(luò)使用，學(xué)生可以隨時(shí)隨地地提交程序代碼，并可在豐富的程序與算法設(shè)計(jì)題庫(kù)中尋找適合自己的題目，訓(xùn)練程序設(shè)計(jì)能力?！　。?） 有效地訓(xùn)練了學(xué)生程序設(shè)計(jì)能力，培養(yǎng)創(chuàng)新型IT人才。本課程的學(xué)習(xí)難點(diǎn)在于如何將常見的算法策略應(yīng)用到實(shí)際的應(yīng)用環(huán)境中。通過(guò)在線評(píng)測(cè)系統(tǒng)的實(shí)踐訓(xùn)練，讓學(xué)生熟練掌握常見的算法設(shè)計(jì)策略，訓(xùn)練學(xué)生的創(chuàng)新思維，加深學(xué)生對(duì)各種算法設(shè)計(jì)策略的認(rèn)識(shí)，使學(xué)生理解算法的意義及精髓，達(dá)到學(xué)以致用?！　。?） 形成了良好的學(xué)習(xí)氛圍，加強(qiáng)了學(xué)生之間的交流。使用在線評(píng)測(cè)系統(tǒng)進(jìn)行課程考核并舉辦程序與算法設(shè)計(jì)競(jìng)賽，學(xué)生以團(tuán)隊(duì)方式參與，可以形成良好的校園競(jìng)爭(zhēng)和交流的學(xué)習(xí)氛圍； 使學(xué)生有了在課余時(shí)間自主進(jìn)行本學(xué)科知識(shí)鉆研的機(jī)會(huì)和環(huán)境； 也讓學(xué)生體驗(yàn)團(tuán)隊(duì)協(xié)作的重要性，為軟件項(xiàng)目團(tuán)隊(duì)化的合作要求做好準(zhǔn)備。　　算法分析與設(shè)計(jì)是面向設(shè)計(jì)的核心課程，主要通過(guò)介紹常見的算法設(shè)計(jì)策略及復(fù)雜性分析方法，培養(yǎng)學(xué)生分析問題和解決問題的能力，為開發(fā)高效的軟件系統(tǒng)及參加相關(guān)領(lǐng)域的研究工作奠定堅(jiān)實(shí)的基礎(chǔ)。該課程理論與實(shí)踐并重，內(nèi)容具有綜合性、廣泛性和系統(tǒng)性，是一門集應(yīng)用性、創(chuàng)造性及實(shí)踐性為一體的綜合性極強(qiáng)的課程?！　∧壳?，該課程的教學(xué)方法還是以傳統(tǒng)的講解為主，通常只是將經(jīng)典算法在已有的數(shù)學(xué)模型和數(shù)據(jù)結(jié)構(gòu)上解釋給學(xué)生； 在實(shí)踐環(huán)節(jié)只是盲目地驗(yàn)證算法，而對(duì)該算法的運(yùn)行效率、測(cè)試數(shù)據(jù)規(guī)模以及實(shí)際的應(yīng)用場(chǎng)景則很少考慮。學(xué)生的學(xué)習(xí)則主要以理解和記憶的繼承式學(xué)習(xí)為主，雖然記住了大量的算法理論，但沒有“理解”和“消化”，不能靈活運(yùn)用算法； 在實(shí)踐環(huán)節(jié)學(xué)生代碼抄襲嚴(yán)重，很難達(dá)到訓(xùn)練的效果。在這種教學(xué)模式下，學(xué)生缺乏問題抽象能力，在遇到實(shí)際問題時(shí)無(wú)從下手，思維創(chuàng)新能力和實(shí)踐能力難以得到有效的提高，很難培養(yǎng)出高水平的程序員?！　”緯贸绦蛟O(shè)計(jì)競(jìng)賽模式和在線評(píng)測(cè)系統(tǒng)的特點(diǎn)，結(jié)合課程特點(diǎn)和實(shí)際教學(xué)，彌補(bǔ)課程教學(xué)中存在的不足，以此探討算法分析與設(shè)計(jì)的課程教學(xué)改革，培養(yǎng)高水平的編程人才?！　”緯卜譃?章?！　〉?章算法概述： 主要是算法的基本概念、算法的復(fù)雜性、大學(xué)生程序設(shè)計(jì)競(jìng)賽概述和程序設(shè)計(jì)在線題庫(kù)的基本情況?！　〉?章數(shù)據(jù)結(jié)構(gòu)和標(biāo)準(zhǔn)模板庫(kù)STL： 主要介紹棧（Stack）、向量（Vector）、映射（Map）、列表（List）、集合（Set）、隊(duì)列（Queue）和優(yōu)先隊(duì)列（Priority Queue），并應(yīng)用這些STL解題： ZOJ1004?Anagrams by Stack，ZOJ1094?Matrix Chain Multiplication，ZOJ1062?Trees Made to Order和ZOJ1944?Tree Recovery等。　　第3章遞歸與分治策略： 主要介紹遞歸算法和分治策略。典型例題有循環(huán)賽日程表、棋盤覆蓋問題、選擇問題和整數(shù)因子分解等?！　〉?章動(dòng)態(tài)規(guī)劃： 主要介紹動(dòng)態(tài)規(guī)劃算法的基本要素。典型例題有矩陣連乘積、最長(zhǎng)公共子序列、最大子段和、0?1背包問題和最長(zhǎng)單調(diào)遞增子序列等，并求解ZOJ1013?Great Equipment、Human Gene Functions、To the Max、FatMouse and Cheese和Railroad等問題?！　〉?章貪心算法： 主要介紹貪心算法的理論基礎(chǔ)。典型例題有活動(dòng)安排問題、背包問題、最優(yōu)裝載問題、單源最短路徑和最小生成樹等，并求解ZOJ1012?Mainframe、ZOJ1025?Wooden Sticks、ZOJ1076?Gene Assembly和ZOJ2109?FatMouse? Trade等問題?！　〉?章回溯算法： 主要介紹回溯算法的理論基礎(chǔ)。典型例題有裝載問題、0?1背包問題、圖的m著色問題、n皇后問題、旅行商問題和流水作業(yè)調(diào)度問題等，并求解ZOJ1145?Dreisam Equations、ZOJ1157?A Plug for UNIX和ZOJ1166?Anagram Checker等問題?！　〉?章分支限界算法： 主要介紹分支限界算法的基本理論，并對(duì)回溯算法與分支限界算法進(jìn)行比較。典型例題有單源最短路徑問題、裝載問題、0?1背包問題和旅行商問題，并求解ZOJ1136?Multiple?！　〉?章圖的搜索算法： 主要介紹圖的深度和廣度優(yōu)先搜索遍歷算法。求解ZOJ1002?Fire Net、ZOJ1142?Maze、ZOJ1245?Triangles、ZOJ1079? Robotic Jigsaw、ZOJ1217?Eight和ZOJ1091?Knight Moves等問題?！　≡Q、馮志林、吳艷、金獻(xiàn)珍、金海溶和曹平老師參加了本書的編寫工作。

內(nèi)容概要

　　《21世紀(jì)高等學(xué)校規(guī)劃教材·計(jì)算機(jī)科學(xué)與技術(shù)·算法分析與設(shè)計(jì)：以大學(xué)生程序設(shè)計(jì)競(jìng)賽為例》主要介紹經(jīng)典的算法設(shè)計(jì)技術(shù)，內(nèi)容包括數(shù)據(jù)結(jié)構(gòu)和標(biāo)準(zhǔn)模板庫(kù)STL、遞歸與分治策略、動(dòng)態(tài)規(guī)劃、貪心算法、回溯算法、分支限界算法和圖的搜索算法?！?1世紀(jì)高等學(xué)校規(guī)劃教材·計(jì)算機(jī)科學(xué)與技術(shù)·算法分析與設(shè)計(jì)：以大學(xué)生程序設(shè)計(jì)競(jìng)賽為例》內(nèi)容基本上涵蓋了目前大學(xué)生程序設(shè)計(jì)競(jìng)賽所要掌握的算法?！?1世紀(jì)高等學(xué)校規(guī)劃教材·計(jì)算機(jī)科學(xué)與技術(shù)·算法分析與設(shè)計(jì)：以大學(xué)生程序設(shè)計(jì)競(jìng)賽為例》通過(guò)大量的問題剖析實(shí)例，并在浙江大學(xué)在線題庫(kù)中精選了部分題目，詳細(xì)地分析解題的方法，深入淺出地講解所使用的算法。還把在浙江大學(xué)在線題庫(kù)中精選的題目作為每章后面的習(xí)題，供讀者練習(xí)，以鞏固所學(xué)的算法?！　　?1世紀(jì)高等學(xué)校規(guī)劃教材·計(jì)算機(jī)科學(xué)與技術(shù)·算法分析與設(shè)計(jì)：以大學(xué)生程序設(shè)計(jì)競(jìng)賽為例》可作為計(jì)算機(jī)科學(xué)與技術(shù)系、軟件學(xué)院、數(shù)學(xué)系等專業(yè)本科及研究生課程的教材，特別適合有志于參加大學(xué)生程序設(shè)計(jì)競(jìng)賽的學(xué)生學(xué)習(xí)和訓(xùn)練。

書籍目錄

第1章 算法概述1.1 引言1.1.1 算法的描述1.1.2 算法的設(shè)計(jì)1.2 算法的復(fù)雜性1.2.1 時(shí)間復(fù)雜性1.2.2 空間復(fù)雜性1.3 大學(xué)生程序設(shè)計(jì)競(jìng)賽概述1.4 程序設(shè)計(jì)在線測(cè)試題庫(kù)第2章 數(shù)據(jù)結(jié)構(gòu)和標(biāo)準(zhǔn)模板庫(kù)2.1 棧2.2 向量2.3 映射2.4 列表2.5 集合2.6 隊(duì)列2.7 優(yōu)先隊(duì)列2.8 ZOJ1004-Anagramsby Stack2.9 ZOJ1094-Matrix Chain Multiplication2.10 ZOJ1011-NTA2.11 ZOJ1062-Trees Madeto Order2.12 ZOJ1097-Codethe Tree2.13 ZOJ1156-Unscrambling Images2.14 ZOJ1167-Trees on the Level2.15 ZOJ1016-Parencodings2.16 ZOJ1944-Tree Recovery2.17 ZOJ2104-Letthe Balloon Rise上機(jī)練習(xí)題第3章 遞歸與分治策略3.1 遞歸算法3.1.1 Fibonacci數(shù)列3.1.2 集合的全排列問題3.1.3 整數(shù)劃分問題3.2 分治策略3.2.1 分治法的基本步驟3.2.2 分治法的適用條件3.2.3 二分搜索技術(shù)3.2.4 循環(huán)賽日程表3.2.5 棋盤覆蓋問題3.2.6 選擇問題3.2.7 輸油管道問題3.2.8 半數(shù)集問題3.2.9 整數(shù)因子分解3.2.10 取余運(yùn)算3.3 Big String上機(jī)練習(xí)題第4章 動(dòng)態(tài)規(guī)劃4.1 矩陣連乘積問題4.1.1 分析最優(yōu)解的結(jié)構(gòu)4.1.2 建立遞歸關(guān)系4.1.3 計(jì)算最優(yōu)值4.1.4 構(gòu)造最優(yōu)解4.2 動(dòng)態(tài)規(guī)劃算法的基本要素4.2.1 最優(yōu)子結(jié)構(gòu)4.2.2 重疊子問題4.2.3 備忘錄方法4.3 最長(zhǎng)公共子序列4.3.1 最長(zhǎng)公共子序列的結(jié)構(gòu)4.3.2 子問題的遞歸結(jié)構(gòu)4.3.3 計(jì)算最優(yōu)值4.3.4 構(gòu)造最長(zhǎng)公共子序列4.4 最大子段和4.5 01背包問題4.5.1 遞歸關(guān)系分析4.5.2 算法實(shí)現(xiàn)4.6 最長(zhǎng)單調(diào)遞增子序列4.7 數(shù)字三角形問題4.8 ZOJ1013-Great Equipment4.9 ZOJ1027-Human Gene Functions4.10 ZOJ1074-Tothe Max4.11 ZOJ1093-Monkeyand Banana4.12 ZOJ1100-Mondriaans Dream4.13 ZOJ1102-Phylogenetic Trees Inherited4.14 ZOJ1107-Fat Mouseand Cheese4.15 ZOJ1108-Fat Mouses Speed4.16 ZOJ1132-Railroad4.17 ZOJ1147-Formatting Text4.18 ZOJ1149-Dividing4.19 ZOJ1163-The Staircases4.20 ZOJ1183-Scheduling Lectures4.21 ZOJ1196-Fast Food4.22 ZOJ1206-Winthe Bonus4.23 ZOJ1227-Free Candies4.24 ZOJ1234-Chopsticks上機(jī)練習(xí)題第5章 貪心算法5.1 活動(dòng)安排問題5.2 貪心算法的理論基礎(chǔ)5.2.1 貪心選擇性質(zhì)5.2.2 最優(yōu)子結(jié)構(gòu)性質(zhì)5.2.3 貪心算法的求解過(guò)程5.3 背包問題5.4 最優(yōu)裝載問題5.5 單源最短路徑5.6 最小生成樹5.6.1 最小生成樹的性質(zhì)5.6.2 Prim算法5.6.3 Kruskal算法5.7 刪數(shù)問題5.7.1 問題的貪心選擇性質(zhì)5.7.2 問題的最優(yōu)子結(jié)構(gòu)性質(zhì)5.8 多處最優(yōu)服務(wù)次序問題5.8.1 問題的貪心選擇性質(zhì)5.8.2 問題的最優(yōu)子結(jié)構(gòu)性質(zhì)5.9 ZOJ1012 Mainframe5.10 ZOJ1025 Wooden Sticks5.11 ZOJ1029 Moving Tables5.12 ZOJ1076 Gene Assembly5.13 ZOJ1161 Gone Fishing5.14 ZOJ1171 Sortingthe Photos5.15 ZOJ2109 Fat Mouse Trade上機(jī)練習(xí)題第6章 回溯算法6.1 回溯算法的理論基礎(chǔ)6.1.1 問題的解空間6.1.2 回溯法的基本思想6.1.3 子集樹與排列樹6.2 裝載問題6.3 01背包問題6.4 圖的m著色問題6.5 n皇后問題6.6 旅行商問題6.7 流水作業(yè)調(diào)度問題6.8 子集和問題6.9 ZOJ1145-Dreisam Equations6.10 ZOJ1157-A Plug for UNIX6.11 ZOJ1166-Anagram Checker6.12 ZOJ1213-Lumber Cutting上機(jī)練習(xí)題第7章 分支限界算法7.1 分支限界算法的基本理論7.1.1 分支限界算法策略7.1.2 分支結(jié)點(diǎn)的選擇7.1.3 提高分支限界算法的效率7.1.4 限界函數(shù)7.2 單源最短路徑問題7.3 裝載問題7.4 01背包問題7.5 旅行商問題7.6 ZOJ1136-Multiple7.7 回溯算法與分支限界算法的比較上機(jī)練習(xí)題第8章 圖的搜索算法8.1 圖的深度優(yōu)先搜索遍歷8.2 ZOJ1002 FireNet8.3 ZOJ1008 GnomeTetravex8.4 ZOJ1047 ImagePerimeters8.5 ZOJ1084 ChannelAllocation8.6 ZOJ1142 Maze8.7 ZOJ1190 OptimalPrograms8.8 ZOJ1191 TheDieIsCast8.9 ZOJ1204 AdditiveEquations8.10 ZOJ1245 Triangles8.11 ZOJ2100 Seeding8.12 圖的廣度優(yōu)先搜索遍歷8.13 ZOJ1055 Oh,ThoseAchinFeet8.14 ZOJ1079 RoboticJigsaw8.15 ZOJ1085 AlienSecurity8.16 ZOJ1103 HikeonaGraph8.17 ZOJ1148 TheGame8.18 ZOJ1217 Eight8.19 ZOJ1091 KnightMoves上機(jī)練習(xí)題參考文獻(xiàn)

章節(jié)摘錄

版權(quán)頁(yè)：插圖：5.可行性在有限時(shí)間內(nèi)完成計(jì)算過(guò)程。算法1.1用一個(gè)正整數(shù)來(lái)除另一個(gè)正整數(shù)，判斷一個(gè)整數(shù)是否為0以及整數(shù)賦值等，這些運(yùn)算都是可行的。因?yàn)檎麛?shù)可以用有限的方式表示，所以至少存在一種方法來(lái)完成一個(gè)整數(shù)除以另一個(gè)整數(shù)的運(yùn)算。必須注意到，在實(shí)際應(yīng)用中，有限性的限制是不夠的。一個(gè)實(shí)用的算法，不僅要求步驟有限，同時(shí)要求運(yùn)行這些步驟所花費(fèi)的時(shí)間是人們可以接受的。如果一個(gè)算法需要執(zhí)行數(shù)萬(wàn)億億計(jì)數(shù)的運(yùn)算步驟，從理論上說(shuō)，它是有限的，最終可以結(jié)束。但是，以當(dāng)代計(jì)算機(jī)每秒數(shù)億次的運(yùn)算速度，也必須運(yùn)行數(shù)百年以上，這是人們所無(wú)法接受的，因而它是不實(shí)用的算法。1.1.2 算法的設(shè)計(jì)算法設(shè)計(jì)的整個(gè)過(guò)程，可以包含對(duì)問題需求的說(shuō)明、數(shù)學(xué)模型的擬制、算法的詳細(xì)設(shè)計(jì)、算法的正確性驗(yàn)證、算法的實(shí)現(xiàn)、算法分析、程序測(cè)試和文檔資料的編制。計(jì)算機(jī)科學(xué)家尼克勞斯·沃思曾著過(guò)一本著名的書《數(shù)據(jù)結(jié)構(gòu)+算法一程序》，可見算法在計(jì)算機(jī)科學(xué)界與計(jì)算機(jī)應(yīng)用界的地位。同一問題可用不同算法解決，而一個(gè)算法的質(zhì)量?jī)?yōu)劣將影響到算法乃至程序的效率。算法分析的目的在于選擇適用算法和改進(jìn)算法。一個(gè)算法的評(píng)價(jià)主要從時(shí)間復(fù)雜性和空間復(fù)雜性來(lái)考慮。算法可大致分為基本算法、數(shù)據(jù)結(jié)構(gòu)的算法、數(shù)論與代數(shù)算法、計(jì)算幾何的算法、圖論的算法、動(dòng)態(tài)規(guī)劃以及數(shù)值分析、加密算法、排序算法、檢索算法、隨機(jī)化算法和并行算法。算法大致分為以下三類。

編輯推薦

《算法分析與設(shè)計(jì):以大學(xué)生程序設(shè)計(jì)競(jìng)賽為例》內(nèi)容主要介紹經(jīng)典的算法設(shè)計(jì)技術(shù)，包括數(shù)據(jù)結(jié)構(gòu)和標(biāo)準(zhǔn)模板庫(kù)STL等。教學(xué)門標(biāo)明確，注重理論與實(shí)踐的結(jié)合。教學(xué)方法靈活，培養(yǎng)學(xué)生自主學(xué)習(xí)的能力。教學(xué)內(nèi)容先進(jìn)，反映了計(jì)算機(jī)學(xué)科的最新發(fā)展。教學(xué)模式完善，提供配套的教學(xué)資源解決方案。

圖書封面

圖書標(biāo)簽Tags

無(wú)

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

---

    算法分析與設(shè)計(jì) PDF格式下載

---