算法分析與設(shè)計

前言

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

內(nèi)容概要

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

書籍目錄

第1章 算法概述1.1 引言1.1.1 算法的描述1.1.2 算法的設(shè)計1.2 算法的復(fù)雜性1.2.1 時間復(fù)雜性1.2.2 空間復(fù)雜性1.3 大學(xué)生程序設(shè)計競賽概述1.4 程序設(shè)計在線測試題庫第2章 數(shù)據(jù)結(jié)構(gòu)和標(biāo)準(zhǔn)模板庫2.1 棧2.2 向量2.3 映射2.4 列表2.5 集合2.6 隊列2.7 優(yōu)先隊列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上機練習(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 取余運算3.3 Big String上機練習(xí)題第4章 動態(tài)規(guī)劃4.1 矩陣連乘積問題4.1.1 分析最優(yōu)解的結(jié)構(gòu)4.1.2 建立遞歸關(guān)系4.1.3 計算最優(yōu)值4.1.4 構(gòu)造最優(yōu)解4.2 動態(tài)規(guī)劃算法的基本要素4.2.1 最優(yōu)子結(jié)構(gòu)4.2.2 重疊子問題4.2.3 備忘錄方法4.3 最長公共子序列4.3.1 最長公共子序列的結(jié)構(gòu)4.3.2 子問題的遞歸結(jié)構(gòu)4.3.3 計算最優(yōu)值4.3.4 構(gòu)造最長公共子序列4.4 最大子段和4.5 01背包問題4.5.1 遞歸關(guān)系分析4.5.2 算法實現(xiàn)4.6 最長單調(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上機練習(xí)題第5章 貪心算法5.1 活動安排問題5.2 貪心算法的理論基礎(chǔ)5.2.1 貪心選擇性質(zhì)5.2.2 最優(yōu)子結(jié)構(gòu)性質(zhì)5.2.3 貪心算法的求解過程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上機練習(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上機練習(xí)題第7章 分支限界算法7.1 分支限界算法的基本理論7.1.1 分支限界算法策略7.1.2 分支結(jié)點的選擇7.1.3 提高分支限界算法的效率7.1.4 限界函數(shù)7.2 單源最短路徑問題7.3 裝載問題7.4 01背包問題7.5 旅行商問題7.6 ZOJ1136-Multiple7.7 回溯算法與分支限界算法的比較上機練習(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上機練習(xí)題參考文獻

章節(jié)摘錄

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

編輯推薦

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

圖書封面

圖書標(biāo)簽Tags

無

評論、評分、閱讀與下載

---

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

---