算法設(shè)計(jì)與問題求解 教學(xué)大綱

算法設(shè)計(jì)與問題求解教學(xué)大綱01基本信息課程名稱：算法設(shè)計(jì)與問題求解

英文名稱：AlgorithmDesignandProblemSolving課程類別：專業(yè)基礎(chǔ)教育課程課程性質(zhì)：必修課學(xué)分：5總學(xué)時(shí)：80其中，講授44學(xué)時(shí)，上機(jī)22學(xué)時(shí)，研討14適用專業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)、軟件工程、網(wǎng)絡(luò)工程、大數(shù)據(jù)、人工智能、信息與計(jì)算科學(xué)等先修課程與知識(shí)儲(chǔ)備：程序設(shè)計(jì)與問題求解、數(shù)據(jù)結(jié)構(gòu)與問題求解后繼課程：離散數(shù)學(xué)、數(shù)據(jù)庫原理與技術(shù)、操作系統(tǒng)02課程簡介《算法設(shè)計(jì)與問題求解》致力于培養(yǎng)信息技術(shù)類相關(guān)專業(yè)學(xué)生的算法設(shè)計(jì)能力和問題求解能力，使學(xué)生能夠針對(duì)問題進(jìn)行分析研究，獲得合適的解決方案進(jìn)行建模，并能夠結(jié)合分治法、貪心法、回溯法、分支限界法、動(dòng)態(tài)規(guī)劃法、圖計(jì)算方法等基本的算法思想針對(duì)性設(shè)計(jì)算法，最終實(shí)現(xiàn)對(duì)問題的高效求解，具備良好的復(fù)雜工程問題求解能力。03教學(xué)目標(biāo)1、課程思政教學(xué)目標(biāo)：通過課程思政教學(xué)，培養(yǎng)愛國、愛黨、具有良好職業(yè)道德和高度職業(yè)責(zé)任感的專業(yè)人才。2、課程教學(xué)總目標(biāo)：通過本課程的學(xué)習(xí)，學(xué)生能很好地掌握遞歸、分治法、動(dòng)態(tài)規(guī)劃、貪心算法、回溯法、分支限界法、圖計(jì)算方法等算法知識(shí)，并能夠應(yīng)用算法知識(shí)對(duì)所求解的問題進(jìn)行分析建模、算法設(shè)計(jì)、編碼實(shí)現(xiàn)、算法性能分析，強(qiáng)化學(xué)生計(jì)算思維能力和實(shí)踐創(chuàng)新能力，為求解復(fù)雜工程問題打下堅(jiān)實(shí)的基礎(chǔ)。3、課程目標(biāo)與學(xué)生能力和素質(zhì)培養(yǎng)的關(guān)系課程思政目標(biāo)的實(shí)施有利于培養(yǎng)學(xué)生愛國精神、職業(yè)責(zé)任感，團(tuán)隊(duì)合作、組織、溝通等社會(huì)能力。課程教學(xué)目標(biāo)的實(shí)施有利于培養(yǎng)學(xué)生對(duì)信息類專業(yè)復(fù)雜問題的分析判斷能力，培養(yǎng)學(xué)生信息類專業(yè)復(fù)雜系統(tǒng)的設(shè)計(jì)仿真能力和創(chuàng)新思維。4、畢業(yè)要求—課程目標(biāo)關(guān)系（OBE結(jié)果導(dǎo)向）課程與專業(yè)畢業(yè)要求的支撐關(guān)系見表1?！?/p>

表1

畢業(yè)要求-課程目標(biāo)關(guān)系表04課程內(nèi)容及學(xué)時(shí)分配本課程內(nèi)容、建議學(xué)時(shí)以及知識(shí)單元與課程目標(biāo)支撐關(guān)系如表2所示?！?/p>

表2

課程內(nèi)容及學(xué)時(shí)分配05教學(xué)方法及要求1、教學(xué)方法要求要求任課教師具有計(jì)算機(jī)類專業(yè)學(xué)習(xí)背景；教學(xué)大綱的基本內(nèi)容要認(rèn)真執(zhí)行，根據(jù)課程目標(biāo)、教學(xué)計(jì)劃和所選教材在深度上可做恰當(dāng)處理；在理論教學(xué)時(shí)，以課堂教學(xué)為主，采用線上+線下混合式教學(xué)，結(jié)合多媒體和網(wǎng)絡(luò)等多種教學(xué)手段，增加教學(xué)內(nèi)容的信息量，增強(qiáng)教學(xué)的互動(dòng)性；注重聯(lián)系實(shí)際，介紹算法的典型應(yīng)用實(shí)例，幫助學(xué)生掌握基本分析方法。2、課程思政教學(xué)方法及要求：在算法的介紹中引入算法的真實(shí)應(yīng)用場景、新聞、事件等，加深對(duì)算法的發(fā)展以及應(yīng)用的認(rèn)識(shí)；運(yùn)用案例式、討論式教學(xué)方法加深學(xué)生對(duì)算法的認(rèn)識(shí)；通過課程分組實(shí)驗(yàn)，培養(yǎng)學(xué)生的溝通、組織、團(tuán)隊(duì)合作的能力。06重點(diǎn)與難點(diǎn)1、重點(diǎn)：算法設(shè)計(jì)基礎(chǔ)和算法分析基礎(chǔ)，蠻力法、分治法、動(dòng)態(tài)規(guī)劃法、貪心法、回溯法、分支限界法等算法設(shè)計(jì)策略，以及針對(duì)問題提出解決方案并能夠?qū)Ψ桨高M(jìn)行評(píng)價(jià)。2、難點(diǎn)：分析問題，針對(duì)問題提出優(yōu)化的算法思想，并建立模型和編碼實(shí)現(xiàn)。07學(xué)習(xí)要求研討表現(xiàn)：能夠針對(duì)問題進(jìn)行資料查閱，整理并收集有效的資料。綜合所收集的材料，提出優(yōu)化的算法設(shè)計(jì)方案，并能夠?qū)Σ煌姆桨高M(jìn)行評(píng)價(jià)。作業(yè)要求：每章提交一次課后作業(yè)，針對(duì)實(shí)際問題進(jìn)行建模，并能夠選擇合適的算法思路進(jìn)行問題求解。自主學(xué)習(xí)：每次課前對(duì)將要開展的課堂教學(xué)內(nèi)容進(jìn)行知識(shí)學(xué)習(xí)，并能夠解決簡單問題。提交一次文獻(xiàn)調(diào)研大作業(yè)，進(jìn)行文獻(xiàn)調(diào)研，閱讀一定量的相關(guān)文獻(xiàn)，對(duì)算法的特性、應(yīng)用條件等進(jìn)行調(diào)查?？荚囈螅簷C(jī)試考試，采用OJ考試形式進(jìn)行問題求解能力的考核。08考核內(nèi)容及考核方式1.考核內(nèi)容及評(píng)價(jià)依據(jù)本課程考核內(nèi)容、建議評(píng)價(jià)依據(jù)以及與課程目標(biāo)對(duì)應(yīng)關(guān)系如表3所示。最終成績由平時(shí)成績、期末成績組合而成。各部分所占比例如下：平時(shí)成績：50%。主要考核對(duì)每堂課知識(shí)點(diǎn)的掌握情況，包括研討表現(xiàn)、每章課程作業(yè)、自主學(xué)習(xí)。考試成績：50%?？荚囆问綖闄C(jī)試，主要考查學(xué)生動(dòng)手編程求解問題的能力等。■

表3課程目標(biāo)-考核方式關(guān)系表2.成績?cè)u(píng)定（1）成績?cè)u(píng)定標(biāo)準(zhǔn)：平時(shí)成績占總成績的50%，根據(jù)自主學(xué)習(xí)、課后作業(yè)、研討表現(xiàn)等形式綜合評(píng)定。期末機(jī)考占總成績的50%，根據(jù)期末統(tǒng)一機(jī)考成績確定。（2）課程目標(biāo)與評(píng)分標(biāo)準(zhǔn)之間的對(duì)應(yīng)關(guān)系自主學(xué)習(xí)成績的評(píng)定標(biāo)準(zhǔn)見表4：■

表4

自主學(xué)習(xí)評(píng)分標(biāo)準(zhǔn)表課后作業(yè)成績的評(píng)定標(biāo)準(zhǔn)見表5：■

表5

課后作業(yè)評(píng)分標(biāo)準(zhǔn)表研討作業(yè)成績的評(píng)定標(biāo)準(zhǔn)見表6：■

表6研討作業(yè)評(píng)分標(biāo)準(zhǔn)表期末機(jī)考考核成績的評(píng)定標(biāo)準(zhǔn)見表7：表7期末機(jī)考評(píng)分標(biāo)準(zhǔn)表

（2）課程目標(biāo)與評(píng)分標(biāo)準(zhǔn)之間的對(duì)應(yīng)關(guān)系■

表8課程目標(biāo)-成績?cè)u(píng)定標(biāo)準(zhǔn)關(guān)系表09教材、主要參考書（一本主教材、三本參考書）主教材：[1]鄧澤林、李峰編《算法分析與問題求解（第2版、微課版）》北京清華大學(xué)大學(xué)出版社，2024主要參考書：[1]王曉東編.計(jì)算機(jī)算法設(shè)計(jì)與分析(第三版)[M].北京：電子工業(yè)出版社，2011.[2]ThomasH.Cormen、CharlesE.Leiserson等編.算法導(dǎo)論[M].北京：機(jī)械工業(yè)出版社，2006.[3][美]MarkAllenWeiss編.數(shù)據(jù)結(jié)構(gòu)與算法分析[M].北京：人民郵電出版社，2007.[4]陳慧南編，算法設(shè)計(jì)與分析：C++語言描述（第2版）

[M].北京：電子工業(yè)出版社，2012.?參考書籍本書注重培養(yǎng)讀者的算法設(shè)計(jì)與分析、問題求解的能力。本書讀者需要掌握程序設(shè)計(jì)、數(shù)據(jù)結(jié)構(gòu)等基礎(chǔ)知識(shí)，并具備一定的編程能力。本書以算法設(shè)計(jì)與分析為主線，通過問題和案例引入內(nèi)容，重點(diǎn)講解利用算法求解問題的思路、算法執(zhí)行過程及能力拓展。本書主要介紹了算法基礎(chǔ)、遞歸算法設(shè)計(jì)、蠻力法、分治法、回溯法、貪心法、分支限界法、動(dòng)態(tài)規(guī)劃、圖算法設(shè)計(jì)等，講解了背包問題、任務(wù)分配問題、批處理作業(yè)調(diào)度問題、旅行商問題、計(jì)算幾何等經(jīng)典問題，并提供了能力拓展環(huán)節(jié)，引導(dǎo)讀者開展算法應(yīng)用實(shí)踐。算法使用C語言程序、偽代碼等形式加以描述，并用圖解的形式詳細(xì)描述算法的執(zhí)行過程，使讀者能夠深入了解算法的運(yùn)行過程和結(jié)果。本書可作為本科院校算法設(shè)計(jì)與分析的教學(xué)用書，也可作為從事算法設(shè)計(jì)的科技人員、算法競賽選手的參考書及培訓(xùn)教材。第1章算法基礎(chǔ)11.1算法概念11.2算法描述11.3算法主要類別及典型問題21.3.1遞歸法21.3.2遞推法21.3.3窮舉法31.3.4貪心算法31.3.5分治法41.3.6動(dòng)態(tài)規(guī)劃法41.3.7分支限界法51.3.8回溯法61.4算法復(fù)雜度61.4.1算法輸入規(guī)模度量61.4.2算法運(yùn)行時(shí)間的度量71.4.3漸進(jìn)符號(hào)71.4.4算法復(fù)雜度分析81.5標(biāo)準(zhǔn)模板庫131.5.1動(dòng)態(tài)數(shù)組vector的使用131.5.2集合set的使用151.5.3映射map的使用161.5.4棧stack的使用181.5.5隊(duì)列與優(yōu)先隊(duì)列的使用191.5.6排序sort的使用22習(xí)題24第2章遞歸算法設(shè)計(jì)252.1概念252.2遞歸算法設(shè)計(jì)思想25〖3〗算法設(shè)計(jì)與問題求解（第2版·微課版）目錄〖3〗2.3遞歸算法示例與過程分析262.3.1全排列問題262.3.2逆波蘭表達(dá)式282.4遞歸轉(zhuǎn)換302.4.1遞歸轉(zhuǎn)尾遞歸302.4.2遞歸轉(zhuǎn)非遞歸312.5能力拓展352.5.1K數(shù)列352.5.2自關(guān)聯(lián)樹狀數(shù)據(jù)362.5.3XML文件解析39習(xí)題43第3章蠻力法463.1概述463.2蠻力法的主要設(shè)計(jì)思想463.2.1使用蠻力法的幾種情況463.2.2蠻力法的求解步驟463.3蠻力法示例與分析473.3.1選擇排序473.3.2旅行商問題483.3.3字符串匹配蠻力解決503.3.401背包問題523.4能力拓展533.4.1連續(xù)數(shù)和533.4.2矩形個(gè)數(shù)54習(xí)題56第4章分治法594.1概述594.2分治法設(shè)計(jì)思路594.3分治法應(yīng)用與過程分析624.3.1最大子段和624.3.2歸并排序634.3.3棋盤覆蓋問題654.3.4最近點(diǎn)對(duì)問題684.3.5快速排序704.4能力拓展734.4.1二進(jìn)制的完全表示734.4.2求兩個(gè)等長有序序列的中位數(shù)744.4.3找第k大的元素76習(xí)題78第5章回溯法805.1概述805.2回溯法設(shè)計(jì)思路805.3回溯法示例與過程分析815.3.1n皇后問題815.3.201背包問題835.3.3圖的m著色問題855.3.4批處理作業(yè)調(diào)度問題885.4能力拓展915.4.1全排列問題915.4.2存在障礙物的迷宮問題935.4.3最少考場數(shù)量95習(xí)題97第6章貪心法1036.1概述1036.2貪心算法步驟及適用的問題1036.2.1貪心算法步驟1036.2.2適用貪心算法求解問題的特點(diǎn)1036.3貪心算法示例與過程分析1046.3.1部分背包問題1046.3.2最優(yōu)裝載問題1066.3.3區(qū)間調(diào)度問題1076.3.4旅行商問題1086.4能力拓展1106.4.1最小正整數(shù)1106.4.2數(shù)字游戲1116.4.3關(guān)閉鬧鐘1136.4.4過河114習(xí)題117第7章分支限界法1217.1概述1217.2分支限界法設(shè)計(jì)思路1217.3分支限界法示例與過程分析1237.3.101背包問題1237.3.2多段圖最短路徑問題1257.3.3旅行商問題1277.3.4作業(yè)調(diào)度問題1327.4能力拓展1377.4.1大富翁游戲1377.4.2最優(yōu)裝載問題138習(xí)題141第8章動(dòng)態(tài)規(guī)劃1448.1概述1448.2動(dòng)態(tài)規(guī)劃算法設(shè)計(jì)規(guī)則1448.3動(dòng)態(tài)規(guī)劃算法問題求解1458.3.101背包問題1458.3.2最長公共子序列1498.3.3最長上升子序列1538.3.4字符串相似度/編輯距離1588.3.5最大子段和1608.4能力拓展1638.4.1帶通配符的字符串匹配1638.4.2拼圖167習(xí)題170第9章圖算法設(shè)計(jì)1749.1概述1749.1.1圖的定義1749.1.2圖的相關(guān)概念1749.2圖算法示例與分析1759.2.1最短路問題1759.2.2網(wǎng)絡(luò)最大流問題1799.2.3二分圖染色問題1829.3能力拓展1849.3.1雜交育種1849.3.2小偷逃跑1889.3.3朋友滿意數(shù)量188習(xí)題192第10章計(jì)算幾何19910.1概述19910.2相關(guān)幾何知識(shí)20010.2.1向量20010.2.2點(diǎn)積和叉積20210.2.3基本應(yīng)用20310.2.4點(diǎn)是否在面內(nèi)20410.2.5方向20410.2.6面積和角度20510.2.7凸性20510.3計(jì)算幾何示例與分析20610.3.1點(diǎn)到直線的距離、判斷線段是否相交20610.3.2凸包問題(極角排序)21010.3.3利用叉積計(jì)算多邊形面積21210.4能力拓展21410.4.1不同直線計(jì)數(shù)21410.4.2面積最大的三角形21510.4.3面積最大的多邊形218習(xí)題221第