算法學(xué)習(xí)報(bào)告2900字

算法學(xué)習(xí)報(bào)告2900字

算法設(shè)計(jì)與分析學(xué)習(xí)報(bào)告姓名：學(xué)號：院系：日期：2014.01.141.總結(jié)歸納學(xué)習(xí)內(nèi)容1.1綜述算法在CS中占有重要的地位，在之前的學(xué)習(xí)中只是了解和運(yùn)用部分算法來解決實(shí)際問題，并沒有對算法內(nèi)容進(jìn)行系統(tǒng)的學(xué)習(xí)與總結(jié)。算法的分析與設(shè)計(jì)這門課的目的就在于使我們非數(shù)值計(jì)算方法的層面上具備抽象描述、解決實(shí)際問題的能力，學(xué)會運(yùn)用算法設(shè)計(jì)與分析的典型方法進(jìn)行算法的設(shè)計(jì)，具備分析算法效率的能力。本學(xué)期的算法課程主要講了三個方面的內(nèi)容：第一，在計(jì)算機(jī)應(yīng)用中經(jīng)常遇到的問題和求解的算法；第二，設(shè)計(jì)算法的基本原理、技巧以及算法復(fù)雜性的分析（包括分治法、動態(tài)規(guī)劃法、集合上的算法、隨機(jī)算法等）；第三，計(jì)算理論簡介（Turing機(jī)、遞歸函數(shù)、NP-完全性等）。1.2算法相關(guān)基本概念及數(shù)學(xué)知識這一單元主要先學(xué)習(xí)計(jì)算機(jī)算法的一些基本常識和發(fā)展歷史，對其發(fā)展有個整體的把握，了解算法在CS中的重要性。其次，學(xué)習(xí)算法的一些基本概念，包括算法的概念、算法研究步驟、算法的評價(jià)、算法的時間復(fù)雜性分析研究等。最后，學(xué)習(xí)算法分析的數(shù)學(xué)基礎(chǔ)，包括母函數(shù)、普通與指數(shù)生成函數(shù)、普通生成函數(shù)的應(yīng)用（排列組合問題和遞歸方程）和主定理。其中，主定理對于算法的研究和設(shè)計(jì)具有重要的意義。1.3分治法分治法，是算法常用技術(shù)之首?？偟膩碇v，分治法是分為將原問題分解為子問題（Divide）、求解子問題（Conquer）、組合子問題的解得到原問題的解（Combine）三個步驟來進(jìn)行。首先是學(xué)習(xí)分治法的要領(lǐng)和主要步驟、分治法求最大最小元問算法、strassen矩陣相乘算法的思路和意義。其次是對平衡概念的理解以及分治法與平衡的密切關(guān)系。最后分別學(xué)習(xí)求第K小元算法、尋找最近點(diǎn)對算法以及離散傅立葉變換（DFT）、快速傅立葉變換（FFT）（利用FFT計(jì)算多項(xiàng)式乘積），通過對這些利用分治法思想的算法的理解和學(xué)習(xí)來把握分治法的要領(lǐng)和精髓。1.4動態(tài)規(guī)劃動態(tài)規(guī)劃法，是跟分治法類似的方法，它們都是把大規(guī)模的問題分解為小規(guī)模的問題來解決問題。但是，動態(tài)規(guī)劃法分解后的子問題是重復(fù)的。一個問題具備兩個條件：1）可分解為若干高度重復(fù)的子問題。2）問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)，那么這個問題就可以用動態(tài)規(guī)劃法來求解。了解動態(tài)規(guī)劃法的基礎(chǔ)上分別討論學(xué)習(xí)了矩陣連乘問題、最長公共子序列問題、最優(yōu)二分搜索樹問題，這些問題都利用動態(tài)規(guī)劃法可以得到良好的解決方法，提高算法的效率。此外，了解了備忘錄方法（它是動態(tài)規(guī)劃的變形應(yīng)用）。最后，學(xué)習(xí)了一個不能直接使用動態(tài)規(guī)劃的例子（需要改進(jìn)才能得到更好的效率）-流水作業(yè)問題。1.5集合算法首先學(xué)習(xí)了平攤分析的算法分析方法以及平攤分析常用的三種方法（聚集方法、會計(jì)方法、勢能方法），總體來講平攤分析是對若干指令整體進(jìn)行考慮時間復(fù)雜度而不是逐一考慮執(zhí)行每條指令所需時間再累加。其次是簡單不相交集的合并算法的學(xué)習(xí)、Union-Find的樹結(jié)構(gòu)，主要是union和find指令的應(yīng)用和改進(jìn)，通過對link指令和find指令的修改實(shí)現(xiàn)路徑壓縮功能和兩個森林的合并，還有union-find算法的應(yīng)用及推廣。此外，學(xué)習(xí)了什么是2-3樹以及2-3樹節(jié)點(diǎn)的的插入和刪除以及應(yīng)用，學(xué)習(xí)了能夠?qū)崿F(xiàn)不同的指令的一些數(shù)據(jù)結(jié)構(gòu)，包括字典（實(shí)現(xiàn)MEMBER、INSERT、DELETE）、優(yōu)先隊(duì)列、可堆并（實(shí)現(xiàn)INSERT、DELETE、UNION、MIN）、可連接隊(duì)列（實(shí)現(xiàn)INSERT、DELETE、FIND、CONCATENATE），以及在這些數(shù)據(jù)結(jié)構(gòu)上各種操作的實(shí)現(xiàn)。1.6隨機(jī)算法隨機(jī)算法，可以用于解決一些利用確定性算法常規(guī)時間內(nèi)得不到所需結(jié)果的問題，而且隨著問題規(guī)模的擴(kuò)大，隨機(jī)算法的結(jié)果也是相當(dāng)可信的。主要學(xué)習(xí)了兩種隨機(jī)算法：LasVegas算法和MonteCarlo算法。基于隨機(jī)算法的思想先后學(xué)習(xí)了RandomSampling（隨機(jī)取數(shù)）問題、找第K小元素的隨機(jī)算法、Sherwood隨機(jī)化方法、TestingStringEquality算法以及誤判率的分析。重點(diǎn)實(shí)現(xiàn)了KMP、MonteCarlo、LasVegas三種模式匹配算法以及根據(jù)運(yùn)行結(jié)果對三種算法進(jìn)行全面的性能分析。最后是素?cái)?shù)測試問題，學(xué)習(xí)了在Fermat小定理和其推論的基礎(chǔ)上建立起來的Miller-Rabin素?cái)?shù)判定算法。1.7計(jì)算模型計(jì)算模型的提出對現(xiàn)代計(jì)算機(jī)的問世有著重要的影響，有重要的意義。這里學(xué)習(xí)了幾種計(jì)算模型以及相互之間的關(guān)系等，主要包括隨機(jī)存取機(jī)（RAM）和RAM程序的時間復(fù)雜度分析、存儲程序模型RASP以及RAM和RASP之間的關(guān)系（分別從均勻耗資和對數(shù)耗資標(biāo)準(zhǔn)下比較）。其次學(xué)習(xí)了另外一個計(jì)算模型-TuringMachine的概念、特點(diǎn)、分類及復(fù)雜度分析。最后總結(jié)了TuringMachine和RAM以及RASP之間的相互關(guān)系。1.8NP完全問題首先學(xué)習(xí)非確定性Turing機(jī)的特點(diǎn)及與確定性Turing機(jī)的主要區(qū)別。然后學(xué)習(xí)P類、NP類語言、NP完全性語言和NP類問題、NP完全性問題、NP-Hard問題以及NP完全性在語言角度和問題角度的意義。最后是近似算法的學(xué)習(xí)，設(shè)計(jì)近似算法必須討論的問題是算法所得近似解與最優(yōu)解之間的差距到底有多大。主要包括近似算法的刻劃、多項(xiàng)式時間近似方案（PTAS）和完全多項(xiàng)式時間近似方案（FPTAS）等。2.學(xué)習(xí)體會在學(xué)習(xí)這門課程之前，對于算法的理解并不深刻，只是局限在一些常見的簡單算法，重點(diǎn)是對于算法的思想、算法設(shè)計(jì)沒有一個較清醒的理解，一些問題可能經(jīng)過自己的研究會寫出相應(yīng)的算法，但是效率方面可能會很低?？傊?，存在有很多算法設(shè)計(jì)、分析、總結(jié)方面的問題。這學(xué)期對于算法的學(xué)習(xí)是從那本厚厚的《算法導(dǎo)論》開始的，開始看的時候還沒有上課，感覺還是可以，但是沒有想到數(shù)學(xué)理論基礎(chǔ)在算法設(shè)計(jì)中那么的重要，而且鄧?yán)蠋熢陂_始也重點(diǎn)講了一些數(shù)學(xué)理論基礎(chǔ)。從分治法、動態(tài)規(guī)劃法開始開始，感覺每學(xué)習(xí)一種方法，一種思想，都會受益頗深，在算法設(shè)計(jì)的過程中就會有更多的選擇。慢慢地也體會到了算法思想的重要性，有些問題只要思想搞明白了，設(shè)計(jì)也就是順其自然的問題了。有的時候聽課也是聽的理論，不去實(shí)踐是不行的，感覺上課期間的三次算法作業(yè)對自己的幫助還是挺大的，能夠加深對該算法思想算法設(shè)計(jì)的理解和認(rèn)識。不過，到最后NP完全性理論和近似算法部分就比較吃力，也許是因?yàn)樗緛砭捅容^難理解，上課的時候總是跟不上節(jié)奏，只是在最近的總體復(fù)習(xí)中才有所理解?？偟膩碚f，這學(xué)期的算法分析設(shè)計(jì)課對自己的幫助還是很大，認(rèn)識和學(xué)習(xí)了一些重要的算法及思想，學(xué)會了運(yùn)用不同的方法來解決問題，并且在算法設(shè)計(jì)中要綜合考慮其設(shè)計(jì)方法、效率等問題實(shí)現(xiàn)算法的優(yōu)化?，F(xiàn)在對算法有了初步的了解和認(rèn)識，在今后的學(xué)習(xí)工作過程中會接觸解決不同的問題，對于算法的理解還要進(jìn)一步加深，進(jìn)一步升華。最后，感謝老師辛苦的授課和幫助。

第二篇：大學(xué)生創(chuàng)新方法訓(xùn)練學(xué)習(xí)報(bào)告2100字大學(xué)生創(chuàng)新方法訓(xùn)練學(xué)習(xí)報(bào)告通過這學(xué)期對創(chuàng)新思維課的學(xué)習(xí)，感觸非常深刻。我了解到創(chuàng)新思維不僅僅教會我們解決問題的方法，我覺得更重要的是，我知道了如何去思考、發(fā)現(xiàn)問題這樣一個過程。只有當(dāng)你了解了這個過程，并不斷的反復(fù)去訓(xùn)練，你才有可能真正領(lǐng)悟到創(chuàng)新思維的神奇，真正獲取靈感。因此不得不說，創(chuàng)新思維這種科學(xué)的思維方法，在我們生活中有著何等重要地位。下面我就來談?wù)勱P(guān)于學(xué)習(xí)了這么多有關(guān)創(chuàng)新思維方法的具體感受。首先什么是創(chuàng)新思維呢：就是指一切能提出新穎的思維成果的非習(xí)慣性思維，即凡是沒有有效的方法可供直接應(yīng)用、不存在確定規(guī)則的思維活動，都屬于創(chuàng)造性思維。在這門課上，唐昌松老師進(jìn)行了教學(xué)創(chuàng)新，經(jīng)常讓同學(xué)自己選取不同的思維方法上臺演講，我們學(xué)到了各種創(chuàng)新思維的方法及根據(jù)不同的實(shí)踐需要作出有效的選擇，減少思維活動的盲目性，提高了思維的效率和成功率。在課堂上，唐昌松老師運(yùn)用生動的案例，并啟發(fā)引導(dǎo)同學(xué)們提出許多有趣的思考題，鍛煉了我們的思維能力。時老師分析的創(chuàng)造性思維的幾種策略，其目的就是幫助我們突破思維定勢。因?yàn)?，我們在遇到問題時，總是喜歡習(xí)慣性地思考，跟著經(jīng)驗(yàn)走。例如：“狗憑著嗅覺找食物”它只知道要沿著有食物的方向，這樣一個邏輯思維才能獲取食物，卻不知有時要接近目標(biāo)，反而得遠(yuǎn)離目標(biāo)的道理。還有“直線與曲線插空”我們要想知道這兩組字母的不同，我們總是喜歡沿著習(xí)慣性思維，去找這些字母的內(nèi)在邏輯，就是不知道從它們的外形去尋找不同點(diǎn)。突破思維定勢也就是要突破設(shè)置在你面前的一堵墻，從而尋找到解決問題的新路徑、新方法。例如：1，如何將雞蛋立起，僅僅是哥倫布解題時的一種方法嗎？2，杯子里裝著空氣，為何很多人看不見？3，給你一盒圖釘幾根火柴一支蠟燭，你怎樣用最簡單的方法，將蠟燭固定在門上？在解決諸如此類的問題時，因?yàn)?，我們都處在思維定勢當(dāng)中，導(dǎo)致要么解不了題，要么找不到簡便有效的方法。舉第3題來說，我們通常都會想到是將蠟燭的蠟滴在門上，然后把蠟燭粘上去等等，但卻忽略了圖釘盒的潛在功能，就是改變它的容器功能，而拓展它的支撐用途，這樣小小的突破，就可以輕而易舉地用圖釘把圖釘盒固定在門上，然后直接將蠟燭放進(jìn)去。我們常常把自己給限定在某個狹小的領(lǐng)域，個人在知覺上受到問題情景中經(jīng)驗(yàn)功能的局限，而不能發(fā)現(xiàn)其可能的或潛在的功能，以致于不能解決問題。講一個關(guān)于想象力的例子：任意給你一組詞好比火水魚蝦，問你這些東西內(nèi)在的關(guān)系，或者說你怎么把它們聯(lián)系在一起，其實(shí)火與水是對比聯(lián)想，水與魚是相似聯(lián)想，魚與蝦又是接近聯(lián)想，很多東西并不是靠邏輯推理出來的，而只有當(dāng)我們?nèi)ゴ竽懴胂?，通過各種聯(lián)想去尋找各種解決問題的途徑和方法，而不是只靠邏輯思維這一種方法。也許這就是我們?yōu)槭裁磳W(xué)習(xí)創(chuàng)新思維，這種不同于一般邏輯思維科學(xué)方法的原因吧。曾有一項(xiàng)調(diào)查：員工中最缺乏的是什么？百分之九十九的領(lǐng)導(dǎo)者的答案是缺乏創(chuàng)造性思維。二十一世紀(jì)擁有知識和信息的越來越多，這就意味著知識和信息量的價(jià)值正在呈下降趨勢，而相反擁有創(chuàng)造力和想象力的人，價(jià)值正在上升，愛因斯坦有句名言“想象力比知識更重要”。很多企業(yè)再雇傭員工的時候，領(lǐng)導(dǎo)者會用這個測試去察看候選人的創(chuàng)造力和想象力，你能用磚做什么。在企業(yè)中較量的不是知識和信息，因?yàn)槟隳塬@得這些，別人也可以獲得，真正較量的企業(yè)中靈活的創(chuàng)造力。或許在沒突破思維定勢沒有學(xué)創(chuàng)新思維時，我們一般只能想到它能用來修房子，其實(shí)它還有很多種用途?？墒俏覀兒苌僮⒅厮季S方法的學(xué)習(xí)，遇到問題也沒有選擇行之有效的思維方法來指導(dǎo)自己，思維技能的訓(xùn)練也只有上課才有真正練到。如何去突破思維定勢，跳出邏輯箱突破那堵墻，想出更有效更簡便的辦法，加強(qiáng)我們的想象力，通過各種聯(lián)想去尋找出解決問題的新路徑新方法呢，因此我們就不得不加強(qiáng)對創(chuàng)新思維的學(xué)習(xí)。在靈感思維中我們了解到，一個青年工從他女朋友穿得緊身裙上得到靈感，設(shè)計(jì)出可口可樂的瓶身。如今滿街遍地是看得人們眼花繚亂的廣告，那我們何不做“廣告門”，這樣豈不是大大增加廣告的暴光率嗎。如果是為了好看，也可以做“水簾門”，即新穎又好看且增加店面的檔次。當(dāng)一張書桌只能一個人做，但這時有同學(xué)想一起加入，或是家教老師得做旁邊，為何不發(fā)明一個可以向四周延伸開來的分散折疊式書桌呢。。。它既可以一個人用也可以四五個人一起用多好呢！你能想象一條船和一個降落傘結(jié)合起來是什么？答案是：帶降落傘的船。也許聽起來很好笑，但它已經(jīng)被發(fā)明并應(yīng)用在實(shí)際生活中了，目的就是為了節(jié)省船的耗油量。當(dāng)今社會領(lǐng)導(dǎo)者一方面要求員工大膽創(chuàng)新，另一方面卻沒給員工足夠的思考空間和時間，更多企業(yè)甚至鼓勵員工加班加點(diǎn)，讓員工疲憊不堪，認(rèn)為工作時間的延