黨的二十大報告指出,教育、科技、人纔是全面建設社會主義現代化國家的基礎性、戰略性支撐。必須堅持科技是生產力、人纔是資源、創新是動力,深入實施科教興國戰略、人纔強國戰略、創新驅動發展戰略,開闢發展新領域新賽道,不斷塑造發展新動能新優勢。
用計算機求解問題是將特定問題的求解過程轉換為計算機可以執行的程序。能夠設計好的程序是計算機專業學生的基本功。在計算機教學體繫中涉及編程的主要課程有“高級程序設計語言”“數據結構”“算法設計與分析”。這些課程相互承接,程序設計語言是求解問題的工具,數據結構是求解問題的基礎,算法設計是求解問題的關鍵。
“算法設計與分析”課程是計算機科學與技術等專業的專業必修課,課程目的是通過學習、理解並掌握算法設計的主要策略和算法復雜性分析的方法,能熟練運用各種數據結構和常用算法策略設計高效算法,培養學生分析問題和解決復雜工程問題的能力,為學生進一步學習後續課程奠定良好的基礎。
本書是編者長期從事“數據結構”“算法設計與分析”課程本科生和研究生教學的經驗總結,凝聚了編者的教學體會和理念。
1. 本書內容
全書由9章構成,各章內容如下。
第1章為概論,介紹算法的概念、算法描述方法、算法設計步驟和算法時空分析方法。
第2章為常用數據結構及其應用,結合STL介紹線性表、字符串、棧、隊列、雙端隊列、樹、二叉樹、二叉排序樹、平衡二叉樹、優先隊列、並查集、圖和哈希表等數據結構的原理和應用,討論如何針對求解問題設計好的數據結構。
第3章為基本算法設計方法,介紹窮舉法、歸納法、迭代法和遞歸法等常用的算法設計方法,討論遞推式計算等基本算法分析方法。
第4章為分治法,介紹分治法的原理和框架,討論利用分治法求解排序問題、查找問題、組合問題、求xn和An問題,包括求連續子序列和、字符串匹配、樓梯問題、求冪集和求全排列等典型算法。
第5章為回溯法,介紹解空間概念和回溯法框架,根據解空間的類型分別討論基於子集樹框架的問題求解方法和基於排列樹框架的問題求解方法,包括子集和問題、簡單裝載問題、0/1背包問題、n皇後問題、任務分配問題、出棧序列、圖的m著色和貨郎擔問題等典型算法。
第6章為分支限界法,介紹分支限界法的要點和框架,討論廣度優先搜索、隊列式分支限界法和優先隊列式分支限界法,包括圖的單源短路徑、0/1背包問題、任務分配問題和貨郎擔問題等典型算法。
第7章為貪心法,介紹貪心法的策略和要點,討論采用貪心法求解組合問題、圖問題、調度問題和哈夫曼編碼,包括活動安排問題Ⅰ、Prim、Kruskal、Dijkstra和不帶/帶懲罰的調度問題等典型算法。
第8章為動態規劃,介紹動態規劃的原理和要點,討論一維動態規劃、二維動態規劃、三維動態規劃、字符串動態規劃、背包動態規劃、樹形動態規劃和區間動態規劃算法設計方法,包括連續子序列和、長遞增子序列、活動安排問題Ⅱ、三角形小路徑和、Floyd算法、雙機調度、長公共子序列、編輯距離、0/1背包問題、完全背包問題和多重背包問題等典型算法。
第9章為NP完全問題,介紹P類、NP類和NP完全問題。
書中帶“*”號的部分作為選學內容。
2. 本書特色
本書具有如下鮮明特色:
(1) 由淺入深,循序漸進。每種算法策略從設計思想、算法框架入手,由易到難地講解經典問題的求解過程,使讀者既能學到求解問題的方法,又能通過對算法策略的反復應用掌握其核心原理,以收到融會貫通之效。
(2) 示例豐富,重視啟發。書中列舉大量的具有典型性的求解問題,深入剖析采用相關算法策略求解的思路,展示算法設計的清晰過程,並舉一反三,激發學生學習算法設計的興趣。
(3) 注重求解問題的多維性。同一個問題采用多種算法策略實現,例如任務分配問題采用基於子集樹框架和排列樹框架以及分支限界法求解,0/1背包問題采用回溯法、分支限界法和動態規劃求解等。通過不同算法策略的比較,使學生更容易體會到每種算法策略的設計特點和各自的優缺點,以提高算法設計的效率。
(4) 強調實踐和動手能力的培養。書中以實戰形式討論了部分在線編程題的設計過程,包括求解問題的相關知識點、完整可通過的程序代碼和提交結果,這些實戰題來自力扣中國、北京大學POJ和杭州電子科技大學HDU網站,讓學生體會到“學以致用”和解決實際問題的樂趣。
(5) 本書配套有《算法設計與分析基礎(C 版)學習和實驗指導》(李春葆等,清華大學出版社),涵蓋所有練習題、上機實驗題和在線編程題的參考答案。
3. 教學資源
為了方便教師教學和學生學習,本書提供了全面而豐富的教學資源,內容如下。
(1) “算法設計與分析”課程教學大綱(含課程思政)和電子教案: 包含教學目的、課程內容和學時分配(42學時),以及各章的課程思政要點和每個課時的教學內容安排。
(2) 教學PPT: 提供全部教學內容的精美PPT課件(947頁),供任課教師在教學中使用。
(3) 源程序代碼: 所有源程序代碼按章組織,例如ch3文件夾存放第3章的源程序代碼,其中perm.cpp為求全排列的源程序代碼,Example\\\\exam33.cpp為例33的源程序代碼,HDU1274.cpp為實戰題HDU1274的源程序代碼。
(4) “算法設計與分析”實驗課程教學大綱: 包含課程介紹、教學目的、實驗基本要求與方式、實驗報告、實驗內容與學時分配(15~21學時),以及每個實驗可供選擇的單機實驗題和在線編程題。
(5) 本書配套有絕大部分知識點的教學視頻,視頻采用微課碎片化形式組織(含96個小視頻,累計超過20小時)。
資源下載提示
課件等資源: 掃描封底的“課件下載”二維碼,在公眾號“書圈”下載。
素材(源碼)等資源: 掃描目錄上方的二維碼下載。
在線作業: 掃描封底的作業繫統二維碼,登錄網站在線做題及查看答案。
視頻等資源: 掃描封底的文泉雲盤防盜碼,再掃描書中相應章節的二維碼,可以在線學習。
本書第1、3、4章由中國勞動關繫學院陳良臣編寫,第2章和第9章由武漢大學喻丹丹編寫,第5~8章由武漢大學李春葆編寫,李春葆完成全書的規劃和統稿工作。本書的出版得到清華大學出版社魏江江分社長的全力支持,王冰飛老師給予精心編輯,LeetCode、POJ和HDU網站提供了無私的幫助,編者在此一並表示衷心感謝。
盡管編者不遺餘力,但由於水平所限,本書仍可能存在不足之處,敬請教師和同學們批評指正。
編者
2023年4月