高級(jí)算法設(shè)計(jì)與分析-課程介紹

課程介紹

高級(jí)算法設(shè)計(jì)與分析個(gè)人介紹(林秋鎮(zhèn))2019年深圳大學(xué)副教授，研究員2014年深圳大學(xué)講師（孔雀C類人才）2014年香港城市大學(xué)博士2013年德國(guó)康斯坦茨大學(xué)

訪問(wèn)學(xué)者2009年香港城市大學(xué)研究助理科研介紹：從事安全、多目標(biāo)優(yōu)化、計(jì)算智能等領(lǐng)域的研究，累計(jì)發(fā)表SCI檢索論文100多篇。目前主持了國(guó)家自然科學(xué)基金面上基金項(xiàng)目、青年科學(xué)基金項(xiàng)目，廣東省面上基金項(xiàng)目，廣東省教育廳青年創(chuàng)新人才類項(xiàng)目（自然科學(xué)類），深圳市孔雀計(jì)劃科研啟動(dòng)項(xiàng)目，深圳市基礎(chǔ)研究項(xiàng)目，累計(jì)獲得500多萬(wàn)科研經(jīng)費(fèi)。課程目標(biāo)目標(biāo)：該課程是一門面向算法理論與設(shè)計(jì)，處于計(jì)算機(jī)科學(xué)與技術(shù)學(xué)科核心地位的專業(yè)基礎(chǔ)課程。通過(guò)對(duì)計(jì)算機(jī)算法系統(tǒng)的學(xué)習(xí)與研究，理解和掌握算法設(shè)計(jì)的主要方法，培養(yǎng)對(duì)算法的計(jì)算復(fù)雜性進(jìn)行正確分析的能力，為獨(dú)立地設(shè)計(jì)算法和對(duì)給定算法進(jìn)行復(fù)雜性分析奠定堅(jiān)實(shí)的理論基礎(chǔ)。本課程系統(tǒng)地介紹計(jì)算機(jī)算法的設(shè)計(jì)方法與分析技巧，以期為計(jì)算機(jī)學(xué)科的學(xué)生提供廣泛堅(jiān)實(shí)的計(jì)算機(jī)算法基礎(chǔ)知識(shí)。課程任務(wù)任務(wù)：分析處理字符串、樹(shù)、圖和網(wǎng)絡(luò)的常見(jiàn)算法，比較排序與搜索算法，掌握算法設(shè)計(jì)策略、包括分治法、貪心法、動(dòng)態(tài)規(guī)劃、線性規(guī)劃、回溯法、分支定界法、圖算法、NP完全理論、近似算法、隨機(jī)算法，及最新算法向沿方向，要求學(xué)生參與課堂活動(dòng)和演講。課程教材書名：算法導(dǎo)論（第三版）

著者：ThomasH.Cormen,CharlesE.Leiserson,andRonaldL.Rivest譯者：殷建平、徐云等出版社：機(jī)械工業(yè)出版社出版日期：2013-01優(yōu)點(diǎn)：詳細(xì)、嚴(yán)謹(jǐn)缺點(diǎn)：枯燥主要參考材料算法導(dǎo)論OpenMITCourse/special/opencourse/algorithms.html

算法設(shè)計(jì)與分析基礎(chǔ)（第3版）AnanyLevition著，潘彥譯算法之道：從無(wú)有到無(wú)窮，鄒恒明TheArtofComputerProgramming,DonaldE.Knuth.Volume1-3,SecondEdition.算法競(jìng)賽入門經(jīng)典，劉汝佳;算法實(shí)踐;計(jì)算機(jī)算法設(shè)計(jì)與分析（第三版）、課后習(xí)題，王曉東主要內(nèi)容序號(hào)課程內(nèi)容對(duì)應(yīng)課本章節(jié)1算法基礎(chǔ)及函數(shù)的增長(zhǎng)（6學(xué)時(shí)）第1、2、3章2概率分析和隨機(jī)算法（6學(xué)時(shí)）第5章3遞歸、分治策略（6學(xué)時(shí)）第4章4回溯法（6學(xué)時(shí)）課本中沒(méi)有對(duì)應(yīng)5貪心算法（6學(xué)時(shí)）第16章6動(dòng)態(tài)規(guī)劃（6學(xué)時(shí)）第15章7P與NP問(wèn)題（6學(xué)時(shí)）第34章8近似算法（6學(xué)時(shí)）第35章9排序和順序統(tǒng)計(jì)量（6學(xué)時(shí)）第6,7,8,9章與本科課程主要區(qū)別部分重疊：算法的基本分析基本的算法設(shè)計(jì)方法（分治、回溯、貪心、動(dòng)態(tài)規(guī)劃）加入概率分析、近似算法詳細(xì)講解NP完全性不講“數(shù)據(jù)結(jié)構(gòu)”“高級(jí)數(shù)據(jù)結(jié)構(gòu)”“圖算法”注重深度1-9騰訊的一道面試題假設(shè)有1000瓶水，其中有一瓶有毒，小白鼠只要嘗一點(diǎn)帶毒的水24小時(shí)后就會(huì)死亡，至少要多少只小白鼠才能在24小時(shí)時(shí)鑒別出那瓶水有毒？答案是什么？1-10思路1：轉(zhuǎn)換最簡(jiǎn)單直觀：1000稍微改進(jìn)：999喝999瓶，都沒(méi)死就是剩下的一瓶有毒問(wèn)題轉(zhuǎn)換：如何從0～999中找到特定的數(shù)字？查找問(wèn)題：折半查找1只老鼠喝0-499，死了（0-499），沒(méi)死（500-999）效率log2n，需要log21000=10只問(wèn)題：要等到24小時(shí)后才能繼續(xù)做實(shí)驗(yàn)，需要10天。如何提高時(shí)間效率？1-11思路2：規(guī)模1瓶：1只老鼠2瓶：1只老鼠3瓶：2只老鼠4瓶：2只（A，B）A喝0，1；B喝0，2A喝0，1死（0，1）B喝0死000死（0，1）沒(méi)死101沒(méi)死（2，3）B喝2死210沒(méi)死（2，3）沒(méi)死3111-12思路2：規(guī)模8瓶呢？3只老鼠A喝0123，B喝0145，C喝0246A-0123死B-0145死C-0246死0000沒(méi)死1001沒(méi)死C-2死2010沒(méi)死3011沒(méi)死B-45死C-4死4100沒(méi)死5101沒(méi)死死6110沒(méi)死71111-13另一種思路以3個(gè)老鼠確定8個(gè)瓶子為例：

000=0

001=1

010=2

011=3

100=4

101=5

110=6

111=7每個(gè)瓶子按順序編號(hào)：“0”代表不喝該瓶水“1”代表喝該瓶水第i只老鼠喝第i位為“1”的瓶子水老鼠活狀態(tài)為“0”，死狀態(tài)為“1”最終老鼠存活狀態(tài)二進(jìn)制碼確定毒水瓶1-14最終解答假設(shè)有1000瓶水，其中有一瓶有毒，小白鼠只要嘗一點(diǎn)帶毒的水24小時(shí)后就會(huì)死亡，至少要多少只小白鼠才能在24小時(shí)后鑒別出那瓶水有毒？答案：根據(jù)210=1024，10個(gè)老鼠可以確定1000個(gè)瓶子具體哪個(gè)瓶子有毒。1-15什么他能想到，我想不到？依賴于天才的解題方法不是個(gè)好的方法。對(duì)于天才，靈機(jī)一閃的背后是龐大的無(wú)意識(shí)洪流，這種無(wú)意識(shí)是以什么為根據(jù)運(yùn)行的，這是一個(gè)無(wú)法預(yù)測(cè)和控制的問(wèn)題。不需要天才的解題思路才是王道！1-16什么他能想到，我想不到？解題思路：1：1000的數(shù)量很大，把問(wèn)題做對(duì)數(shù)分解，不難想到210=10242：既然有210=1024，可以把問(wèn)題簡(jiǎn)化為23=8，那么思考8個(gè)瓶子需要幾只老鼠？3:一只老鼠有兩個(gè)狀態(tài)：生(0)、死(1)，由此想到了二進(jìn)制碼。1-17這個(gè)問(wèn)題與算法的關(guān)系？如何設(shè)計(jì)算法使用最少老鼠檢驗(yàn)毒水—算法設(shè)計(jì)我是如何設(shè)計(jì)這個(gè)算法的？—算法思想我的這個(gè)算法效率如何？—算法分析通過(guò)本課程學(xué)習(xí)，希望你能掌握：一個(gè)問(wèn)題如何利用現(xiàn)有算法求解？如何利用已有算法思想創(chuàng)造新算法求解問(wèn)題？1-18為什么要學(xué)習(xí)算法？受過(guò)良好訓(xùn)練的計(jì)算機(jī)科學(xué)家知道怎樣處理算法：如何構(gòu)造算法、操作算法、理解算法及分析算法——算法是計(jì)算機(jī)科學(xué)的基石；程序=數(shù)據(jù)結(jié)構(gòu)+算法—算法是解決實(shí)際問(wèn)題的手段將知識(shí)表示為算法，把知識(shí)教授給計(jì)算機(jī)；只有把知識(shí)教給“計(jì)算機(jī)”，才能“真正”掌握它。授人以魚(yú)，不如授人以漁《數(shù)據(jù)結(jié)構(gòu)與算法》課講述過(guò)一部分，為什么還要學(xué)《算法設(shè)計(jì)與分析》？初級(jí)目標(biāo)：掌握更多解決問(wèn)題的方法（算法）中級(jí)目標(biāo)：掌握算法設(shè)計(jì)的思想（分治、貪心、回溯…）掌握算法分析方法高級(jí)目標(biāo)拓展思路提升數(shù)學(xué)水平，理解為什么Computer可以稱為Science（只學(xué)一點(diǎn)編程，那叫Engineering或者Technology）為什么要學(xué)習(xí)算法設(shè)計(jì)與分析？算法分析是指對(duì)算法所需的時(shí)間和空間等資源進(jìn)行預(yù)測(cè)途徑(狹義)理論/數(shù)學(xué)上的分析經(jīng)驗(yàn)/計(jì)算機(jī)上的執(zhí)行情況廣義效率分析：時(shí)間復(fù)雜度、空間復(fù)雜度正確性分析：算法為什么是正確的？可讀性：有些算法容易理解，有些則不健壯性分析Robust：算法對(duì)不合理數(shù)據(jù)輸入的反應(yīng)能力和處理能力可伸縮性Scalability：規(guī)模增大之后，算法是否還能正常工作？…算法分析同一個(gè)問(wèn)題會(huì)有多個(gè)不同的算法排序問(wèn)題：冒泡、快排、歸并、基數(shù)…有些問(wèn)題可以進(jìn)行轉(zhuǎn)換規(guī)約：把未知問(wèn)題轉(zhuǎn)換到已知問(wèn)題縮小規(guī)模進(jìn)行嘗試，逐步擴(kuò)大規(guī)模有些問(wèn)題就不可能解決（哥德?tīng)柌煌耆ɡ?、圖靈停機(jī)問(wèn)題）有些問(wèn)題理論上可以解決，實(shí)際不可行（PvsNP問(wèn)題）拓展思路古代謎題：一個(gè)農(nóng)夫在河邊要過(guò)河，但是他帶著一匹狼、一只羊和一顆白菜。他需要用船將這三樣?xùn)|西運(yùn)至對(duì)岸，然而，這艘船的空間有限，只容得下他自己和另一樣?xùn)|西（或狼或羊或白菜）。若他不在場(chǎng)看管的話，狼就會(huì)吃羊，羊就會(huì)去吃白菜。此人如何才能過(guò)河。廣義的算法現(xiàn)代謎題：晚上有四個(gè)人要過(guò)橋，只有一個(gè)手電