第4章 問題求解與計算思維

.,第4章問題求解與計算思維,主講教師：鄭立垠,計算機與通信工程學院計算機應用技術(shù)系,.,中國自古就有喝茶的歷史習俗，有同學知道泡茶的流程嗎？燒水溫具置茶沖泡奉茶賞茶續(xù)水,引入,.,有一個牧羊人帶著一只羊,一匹狼和一顆大白菜準備過河,他找到一只很小的船,每次只能帶一樣東西過去,可是如果讓狼與羊單獨在一起,狼會吃羊,讓羊與白菜單獨在一起,羊會吃白菜，牧羊人應如何過河？,過河的方案:第一步：人和羊過河，人返回，留下羊；第二步：人和狼過河，人和羊返回，留下狼；第三步：人和菜過河，人返回，留下菜；第四步：人和羊過河。,人在解決問題時，要先對問題進行分析思考，然后確定解決問題的方法和步驟，這種解決問題的方法和步驟就稱為算法。,引入,.,1、算法2、計算思維,本章內(nèi)容,.,算法的由來,算法算法被譽為計算學科和計算機器的靈魂“算法”（Algorithm）一詞源于：公元825年，阿拉伯數(shù)學家阿科瓦里茨米（AlKhowarizmi）寫了著名的波斯教科書（PersianTextbook），書中概括了進行四則算術(shù)運算的法則。,.,算法的定義：一個有窮規(guī)則的集合，規(guī)則規(guī)定了一個解決某一特定類型問題的運算序列。定義了任務執(zhí)行/問題求解的一系列步驟。算法的特征：輸入：有零個或多個的輸入。輸出：有一個或多個的輸出。有窮性：一個算法在執(zhí)行有窮步之后必須結(jié)束。確定性：算法的每一個步驟必須要確切地定義，不得有歧義性?？尚行裕核惴ㄔ瓌t上能夠精確地運行。,算法的定義及特征,.,算法描述,自然語言容易引起歧義，造成誤解；對較復雜的問題，難以表達準確流程圖直觀形象，但計算機不能識別和執(zhí)行程序代碼用計算機能理解和執(zhí)行的程序設計語言把算法表示出來，然后由計算機按照預定的算法去解決問題。,.,算法設計數(shù)學建模數(shù)據(jù)結(jié)構(gòu)控制流程算法策略遍歷搜索遞歸動態(tài)規(guī)劃貪心.,算法設計,.,算法的正確性：問題求解的過程、方法算法是正確的嗎？算法的輸出是問題的解嗎？20世紀60年代，美國一架發(fā)往金星的航天飛機由于控制程序出錯而永久丟失在太空中算法的效果評價：算法的輸出是最優(yōu)解還是可行解？如果是可行解，與最優(yōu)解的偏差多大？兩種方法：分析方法：利用數(shù)學方法證明仿真分析方法：產(chǎn)生或選取大量的、具有代表性的問題實例，利用該算法對這些問題實例進行求解，并對算法產(chǎn)生的結(jié)果進行統(tǒng)計分析,算法分析,.,算法的效率：時間效率和空間效率時間復雜性:如果一個問題的規(guī)模是n，解這一問題的某一算法所需要的時間為T(n)，它是n的某一函數(shù)，T(n)稱為這一算法的“時間復雜性”?！按驩記法”：基本參數(shù)n問題實例的規(guī)模把復雜性或運行時間表達為n的函數(shù)。“O”表示量級(order)，允許使用“=”代替“”，如n2+n+1=(n2)算法的空間復雜度：算法在執(zhí)行過程中所占存儲空間的大小。,算法效率,.,算法的復雜性,當算法的時間復雜度的表示函數(shù)是一個多項式，如O(n2)時，計算機對于大規(guī)模問題可以處理算法的時間復雜度用一個指數(shù)函數(shù)表示，如O(2n)，當n很大（如10000）時計算機是無法處理的，在計算復雜性中將這一類問題稱為難解性問題。,算法效率,當n值增大時，各種時間復雜度存在下列關(guān)系：O(log2n)O(n)O(nlog2n)O(n2)C-B-A,示例,旅行商問題,城市之間的距離,.,問題求解中的過程控制,問題求解過程中需要組織并控制操作、指令的過程和順序,TSP問題求解的流程控制,求解TSP問題需要控制指令、基本操作的邏輯過程/流程遍歷所有的組合路徑判斷某條路徑的距離是不是比另外一條短，并據(jù)此作出不同的處理累加一條路徑的距離之和,旅行商問題,.,算法策略,可行解與最優(yōu)解遍歷能夠獲得最優(yōu)解，然而，由于組合爆炸，對于較大規(guī)模的某些問題，無法在可接受的時間內(nèi)獲得最優(yōu)解退而求其次，在可接受的時間內(nèi)獲得足夠好的（可行）解,TSP問題的可行解與最優(yōu)解,旅行商問題,.,算法策略貪心,貪心算法“今朝有酒今朝醉”一定要做當前情況下的最好選擇，否則將來可能會后悔，故名“貪心”,TSP問題的貪心求解示例,每次在選擇下一個城市的時候，只考慮當前情況，保證迄今為止經(jīng)過的路徑總距離最短,城市之間的距離,旅行商問題,.,TSP問題貪心算法的模擬與分析,TSP問題貪心算法的正確性：直觀上只需檢查算法的輸出結(jié)果中，每個城市出現(xiàn)且僅出現(xiàn)一次，該結(jié)果即是TSP問題的可行解，說明算法正確的求解了這些問題實例TSP問題貪心算法的效果評價：如果實例的最優(yōu)解已知（問題規(guī)模小或問題已被成功求解），利用統(tǒng)計方法對若干問題實例的算法結(jié)果與最優(yōu)解進行對比分析，即可對其進行效果評價；對于較大規(guī)模的問題實例，其最優(yōu)解往往是未知的，因此，算法的效果評價只能借助于與前人算法結(jié)果的比較。,旅行商問題,.,TSP問題算法的效率,TSP問題遍歷算法：列出每一條可供選擇的路線，計算出每條路線的總里程，最后從中選出一條最短的路線組合爆炸：路徑組合數(shù)目為(n-1)!時間復雜度是O(n-1)!)計算機不能處理TSP問題貪心算法：時間復雜度是O(n3)。計算機可以處理,旅行商問題,.,問題求解總結(jié),.,1.科學與思維的含義(1)科學達爾文曾給科學下過一個定義：“科學就是整理事實，從中發(fā)現(xiàn)規(guī)律，作出結(jié)論”?？茖W一般包含：自然科學、社會科學和思維科學。(2)思維思維是高級的心理活動，是認識的高級形式。思維是人腦對現(xiàn)實事物概括、加工、揭露本質(zhì)特征。人腦對信息的處理包括分析、抽象、綜合、概括等。2.人類文明進步和科學發(fā)現(xiàn)的三大科學(1)理論科學、實驗科學和計算科學作為科學發(fā)現(xiàn)三大支柱，正推動著人類文明進步和科技發(fā)展。(2)該說法已被科學文獻廣泛引用，并在美國得到國會聽證、聯(lián)邦和私人企業(yè)報告的承同。,計算思維,.,3.科學思維(1)一般而論，三種科學對應著三種思維：理論科學理論思維：理論思維又叫推理思維，以推理和演繹為特征，以數(shù)學學科為代表。實驗科學實驗思維：實驗思維又叫實證思維，以觀察和總結(jié)自然規(guī)律為特征，以物理學科為代表。計算科學計算思維：計算思維又叫構(gòu)造思維，以設計和構(gòu)造為特征，以計算機學科為代表。(2)科學思維的含義及重要性：一般指的是理性認識及其過程，也即經(jīng)過感性階段獲得的大量材料，通過整理和改造，形成概念、判斷和推理，以反映事物的本質(zhì)和規(guī)律。國科發(fā)財2008197號文關(guān)于創(chuàng)新方法工作的若干意見認為“科學思維不僅是一切科學研究和技術(shù)發(fā)展的起點，而且始終貫穿于科學研究和技術(shù)發(fā)展的全過程，是創(chuàng)新的靈魂”。,計算思維,.,計算思維,計算思維(ComputationalThinking，CT)是運用計算的基礎(chǔ)概念(FundamentalConcept)去求解問題、設計系統(tǒng)和理解人類行為的一種方法(Approach)。CT的本質(zhì)是抽象(Abstract)和自動化(Automation)。它是如同所有人都具備“讀、寫、算”（簡稱3R）能力一樣，都必須具備的思維能力?；靖拍睿杭s簡、嵌入、轉(zhuǎn)化、仿真、遞歸、并行、多維分析、類型、抽象、分解、SoC，保護、冗余、容錯、糾錯、系統(tǒng)恢復、啟發(fā)式、規(guī)劃、學習、調(diào)度、折衷。,.,程序設計課程中問題求解能力培養(yǎng),問題表示(如何建立模型)問題求解（如何設計算法）效率（如何有效地求解）,.,尋找兩個正整數(shù)的最大公約數(shù)的歐幾里德算法輸入：正整數(shù)M和正整數(shù)N輸出：M和N的最大公約數(shù)算法過程：Step1.將較大的數(shù)賦給M,較小的數(shù)賦給N;Step2.M除以N,記余數(shù)為RStep3.如果R不是0,將N的值賦給M,R的值賦給N,返回Step2;否則,最大公約數(shù)是N,輸出N,算法結(jié)束,歐幾里德算法：求解兩個數(shù)的最大公因子的算法（公元前300年）表述了最大公因子的求解過程表述了一個判定過程，即判定“m和n是互質(zhì)的”（即除1以外，m和n沒有公因子）命題的真假。,求最大公約數(shù),.,乒乓球挑選,有13個乒乓球，其中有一個是壞的，其質(zhì)量與其它球不同，請設計算法將其挑出。,建模與設計,.,解答1：步驟1：將13個球分成4,4,4,1四份，分別記為a，b，c，d組；步驟2：先比較a，b兩組的輕重，若a與b一樣重，取c中任意4個球與a或b比較，若都一樣重，則d組為次品，若不一樣重，則可知次品在c組取出的4個球中，并且可判斷次品是輕還是重；若a與b不一樣重，取c組與a或b進行稱量對比，得出含有次品組為a組或者b組以及判斷出次品是輕還是重。步驟3：從步驟2中得到含有4個球的次品組，將這4個球平分成2組稱量，根據(jù)次品是輕或重得到含有次品組e，再將次品組e中2個球分別放置天平兩端，根據(jù)次品輕重判斷得到次品球。,乒乓球挑選,.,解答2：（1）將13個球分為三個部分，6，6,1，將6,6兩部分進行稱量，若平衡，則1所代表物品為次品；否則（2）（2）取一組6，將其平分為兩組計為a，b；另一組6再平分為c,d；取a,b,c兩兩稱量，若都平衡則次品在d中，轉(zhuǎn)到（3）；若有一次不平衡，則次品在a,b,c之中，轉(zhuǎn)到（3）（3）將三個任取兩個稱量，若平衡，則次品為未稱量的物品；若不平衡，則轉(zhuǎn)到（4）（4）若不平衡再測一次即可得次品。,乒乓球挑選,.,解答3：將13個球記為1,2,3,4,5,5,6,7,8,9,10,11,12,13。16記為A，712號記為B；步驟1：將AB組球放在天平上，若天平平衡，則次品為13號球；若不平衡，則轉(zhuǎn)向步驟2；步驟2：取較輕的一組，不妨設為A,將A組重新分成兩組放在天平兩端，若平衡，則轉(zhuǎn)向步驟3，不平衡轉(zhuǎn)向步驟4；步驟3：將B組分成兩組記為a,b，放在天平兩端，（由步驟2值次品較重），取較重的一組，不妨設其為a，任取兩個球放在天平兩端，若天平平衡，則為a中的另一個球；若不平衡，則較重的為次品；步驟4：將A組分成兩組，取較重的一組（三個球），任取兩個放在天平兩端，若平衡，則為三個中的另一個，若不平衡，則為較重的的球；,乒乓球挑選,.,解答4：步驟1：從這堆產(chǎn)品中任意拿出2產(chǎn)品，放在天平兩端；步驟2：記下天平兩端是否相平；相平執(zhí)行步驟3；否則執(zhí)行步驟5；步驟3：從天平的右端拿下產(chǎn)品，再從剩余產(chǎn)品中任意拿出一個放在右端，記下是否相平；步驟4：若相平，重復步驟3，直到不平為止，則此時右端產(chǎn)品為劣質(zhì)；步驟5：拿下右端產(chǎn)品，再從剩余產(chǎn)品中任意拿出放在右端，若相平，則之前拿下的為劣質(zhì)；否則左端為劣質(zhì),乒乓球挑選,.,兩