算法設計與分析——以ACM大學生程序設計競賽在線題庫為例(微課版)

趙端陽 王超

  • 出版商: 清華大學
  • 出版日期: 2021-11-01
  • 定價: $474
  • 售價: 8.5$403
  • 語言: 簡體中文
  • 頁數: 412
  • 裝訂: 平裝
  • ISBN: 7302587256
  • ISBN-13: 9787302587255
  • 立即出貨

  • 算法設計與分析——以ACM大學生程序設計競賽在線題庫為例(微課版)-preview-1
  • 算法設計與分析——以ACM大學生程序設計競賽在線題庫為例(微課版)-preview-2
  • 算法設計與分析——以ACM大學生程序設計競賽在線題庫為例(微課版)-preview-3
算法設計與分析——以ACM大學生程序設計競賽在線題庫為例(微課版)-preview-1

買這商品的人也買了...

相關主題

商品描述

本書內容包括經典的算法設計技術,主要介紹數據結構和標準模板庫、遞歸與分治策略、動態規劃、貪心算法、回溯算法、分支限界算法、圖的搜索算法、圖論、數論和組合數學問題。本書包括大量的問題實例,並在北京大學、浙江大學和杭州電子科技大學在線題庫中精選原題,詳細地分析解題的方法,深入淺出地講解用到的算法,章後的上機練習題也選自在線題庫中的典型題目,供讀者練習,以鞏固所學算法。本書內容基本上涵蓋了目前大學生程序設計競賽所要掌握的算法。 本書結構清晰、內容豐富,適合作為電腦科學與技術、軟件工程以及相關學科算法課程的教材或參考書,特別適合有志於參加信息學競賽和ACM大學生程序設計競賽的讀者學習和訓練。

作者簡介

趙端陽,教授,1987年中國礦業大學碩士研究生畢業,留校工作兩年,1989-1999,杭州市杭州船舶工業學校任教,1999年併入浙江工業大學。從1987年起,一直從事計算機專業課程的教學。 2002.9~2003.7,到英國Plymouth大學網絡研究組,作為高級訪問學者從事網絡安全的研究。
作者在工作期間一直從事算法設計與分析的研究,從2005年起就一直指導學生參加大學生程序設計競賽,並每年都獲得浙江省大學生程序設計競賽的銀牌和銅牌,2017年度,獲得ACM大學生程序設計競賽青島和南寧賽區的銅牌,和東亞賽區的銅牌。
編寫《算法分析與設計—以大學生程序設計競賽為例》教程,清華大學出版社,2012年3月出版,2015年改版;編寫《ACM大學生程序設計競賽題解(1)》和《ACM大學生程序設計競賽題解(2)》,電子工業出版社,2010年7月出版。從2007年起承擔本科《算法分析與設計》課程的教學,本課程2013年評為浙江工業大學精品課程,2013年,獲得浙江省課堂教學改革SPOC立項。
2015年版《算法設計與分析—以ACM大學生程序設計競賽在線題庫為例》獲得浙江省“十二五優秀教材”,浙江省“十三五”新形態教材立項。

目錄大綱

第1章算法概述
1.1引言
1.1.1算法的描述
1.1.2算法的設計
1.2算法的複雜度
1.2.1時間複雜度
1.2.2空間複雜度
1.3大學生程序設計競賽概述
1.4程序設計在線題庫

第2章數據結構和標準模板庫
2.1棧
2.2向量
2.3映射
2.4列表
2.5集合
2.6隊列
2.7優先隊列
2.8ZOJ1004Anagrams by Stack
2.9ZOJ1094Matrix Chain Multiplication
2.10ZOJ1011NTA
2.11ZOJ1062Trees Made to Order
2.12ZOJ1097Code the Tree
2.13ZOJ1156Unscrambling Images
2.14ZOJ1167Trees on the Level
2.15ZOJ1016Parencodings
2.16ZOJ1944Tree Recovery
2.17ZOJ2104Let the Balloon Rise
上機練習題

第3章遞歸與分治策略
3.1遞歸算法
3.1.1Fibonacci數列
3.1.2集合的全排列問題
3.1.3整數劃分問題
3.2分治策略
3.2.1分治策略的基本步驟
3.2.2分治策略的適用條件
3.2.3二分搜索算法
3.2.4循環賽日程表
3.2.5棋盤覆蓋問題
3.2.6選擇問題
3.2.7輸油管道問題
3.2.8半數集問題
3.2.9整數因子分解
3.2.10取餘運算
3.3ZOJ1633Big String
上機練習題

第4章動態規劃
4.1矩陣連乘積問題
4.1.1分析最優解的結構
4.1.2建立遞歸關係
4.1.3計算最優值
4.1.4構造最優解
4.2動態規划算法的基本要素
4.2.1最優子結構
4.2.2重疊子問題
4.2.3備忘錄方法
4.3最長公共子序列
4.3.1最長公共子序列的結構
4.3.2子問題的遞歸結構
4.3.3計算最優值
4.3.4構造最長公共子序列
4.4最大子段和
4.501背包問題
4.5.1遞歸關係分析
4.5.2算法實現
4.6最長單調遞增子序列
4.7數字三角形問題
4.8ZOJ1027Human Gene Functions
4.9ZOJ1074To the Max
4.10ZOJ1093Monkey and Banana
4.11ZOJ1107FatMouse and Cheese
4.12ZOJ1108FatMouses Speed
4.13ZOJ1147Formatting Text
4.14ZOJ1149Dividing
4.15ZOJ1163The Staircases
4.16ZOJ1183Scheduling Lectures
4.17ZOJ1196Fast Food
4.18ZOJ1206Win the Bonus
4.19ZOJ1227Free Candies
4.20ZOJ1234Chopsticks
上機練習題

第5章貪心算法
5.1活動安排問題
5.2貪心算法的理論基礎
5.2.1貪心選擇性質
5.2.2最優子結構性質
5.2.3貪心算法的求解過程
5.3背包問題
5.4最優裝載問題
5.5單源最短路徑
5.6最小生成樹
5.6.1最小生成樹的性質
5.6.2Prim算法
5.6.3Kruskal算法
5.7刪數問題
5.7.1問題的貪心選擇性質
5.7.2問題的最優子結構性質
5.8多處最優服務次序問題
5.8.1問題的貪心選擇性質
5.8.2問題的最優子結構性質
5.9ZOJ1012Mainframe
5.10ZOJ1025Wooden Sticks
5.11ZOJ1029Moving Tables
5.12ZOJ1076Gene Assembly
5.13ZOJ1161Gone Fishing
5.14ZOJ1171Sorting the Photos
5.15ZOJ2109FatMouse Trade
上機練習題

第6章回溯算法
6.1回溯算法的理論基礎
6.1.1問題的解空間
6.1.2回溯算法的基本思想
6.1.3子集樹與排列樹
6.2裝載問題
6.301背包問題
6.4圖的m著色問題
6.5n皇后問題
6.6旅行商問題
6.7流水作業調度問題
6.8子集和問題
6.9ZOJ1145Dreisam Equations
6.10ZOJ1157A Plug for UNIX
6.11ZOJ1166Anagram Checker
6.12ZOJ1213Lumber Cutting
上機練習題

第7章分支限界算法
7.1分支限界算法的基本理論
7.1.1分支限界算法策略
7.1.2分支結點的選擇
7.1.3提高分支限界算法的效率
7.1.4限界函數
7.2單源最短路徑問題
7.3裝載問題
7.401背包問題
7.5旅行商問題
7.6ZOJ1136Multiple
7.7回溯算法與分支限界算法的比較
上機練習題

第8章圖的搜索算法
8.1圖的深度優先搜索遍歷
8.2ZOJ1002Fire Net
8.3ZOJ1008Gnome Tetravex
8.4ZOJ1047Image Perimeters
8.5ZOJ1084Channel Allocation
8.6ZOJ1142Maze
8.7ZOJ1190Optimal Programs
8.8ZOJ1191The Die Is Cast
8.9ZOJ1204Additive equations
8.10ZOJ1245Triangles
8.11ZOJ2100Seeding
8.12圖的廣度優先搜索遍歷
8.13ZOJ1079Robotic Jigsaw
8.14ZOJ1085Alien Security
8.15ZOJ1103Hike on a Graph
8.16ZOJ1148The Game
8.17ZOJ1217Eight
8.18ZOJ1091Knight Moves
上機練習題

第9章圖論
9.1網絡流問題
9.1.1流和割的概念
9.1.2剩餘網絡和增廣路徑
9.1.3FordFulkerson算法
9.1.4EdmondsKarp算法
9.1.5ZOJ1734Power Network——EdmondsKarp算法
9.1.6ISAP算法
9.1.7ZOJ1734Power Network——ISAP算法
9.1.8Dinic算法
9.1.9ZOJ1734Power Network——Dinic算法
9.1.10最小費用流——SPFA算法
9.1.11ZOJ2404Going Home——SPFA算法
9.2二分圖匹配問題
9.2.1匹配問題
9.2.2二分圖最大匹配——匈牙利算法
9.2.3ZOJ1137Girls and Boys
9.2.4ZOJ1140Courses——匈牙利算法
9.2.5PJU1247The Perfect Stall——匈牙利算法
9.2.6HopcroftKarp算法
9.2.7ZOJ1140Courses——HopcroftKarp算法
9.2.8PJU1274The Perfect Stall——HopcroftKarp算法
9.2.9二分圖最佳匹配——Kuhn Munkres算法
9.2.10ZOJ2404Going Home——Kuhn Munkres算法
上機練習題

第10章數論
10.1擴展歐幾里得算法
10.2PJU2115C Looooops
10.3歐拉函數
10.4ZOJ1906Relatives
10.5PJU2480Longges problem
10.6PJU3696The Luckiest number
10.7中國剩餘定理
10.8ZOJ1160Biorhythms
10.9一元線性同餘方程組
10.10PJU2891Strange Way to Express Integers
10.11HDU1573X問題
上機練習題

第11章組合數學
11.1母函數
11.1.1普通型母函數
11.1.2指數型母函數
11.1.3Stirling數
11.1.4Catalan數
11.2HDU2082找單詞
11.3HDU1521排列組合
11.4HDU2065“紅色病毒”問題
11.5HDU3625Examining the Rooms
11.6POJ2084Game of Connection
11.7容斥原理與鴿巢原理
11.7.1容斥原理
11.7.2錯排問題
11.7.3鴿巢原理
11.8HDU2048“恭喜你,中獎了!”
11.9POJ2356Find a multiple
11.10ZOJ2836Number Puzzle
上機練習題

參考文獻