算法與程序設(shè)計(jì)浙教版教材介紹

1、算法與程序設(shè)計(jì)（浙教版）教材介紹1一、為什么標(biāo)準(zhǔn)要將這門課程列為選修模塊二、教材編寫思路三、計(jì)算機(jī)處理中的“難”的問題和不能處理的問題2計(jì)算機(jī)技術(shù)對(duì)社會(huì)和世界已經(jīng)產(chǎn)生了深刻的影響。每個(gè)公民都要熟知這項(xiàng)技術(shù)以及它在家庭、學(xué)校、工作場(chǎng)所和社區(qū)所起的重要作用。由于這門技術(shù)的細(xì)節(jié)發(fā)展日新月異，因此要跟上這些技術(shù)的細(xì)節(jié)是困難的，而且常常是徒勞的。所以，這門課的學(xué)習(xí)必須注重本領(lǐng)域基本的科學(xué)原理和概念。 摘自ACM高中計(jì)算機(jī)科學(xué)課程規(guī)范3當(dāng)今的高中計(jì)算機(jī)教學(xué)要么是將計(jì)算機(jī)作為其他學(xué)科的工具（字處理是為學(xué)英文，電子表格和數(shù)據(jù)庫(kù)是商科的工具，CAD/CAM是技術(shù)教學(xué)的工具，數(shù)學(xué)軟件包是數(shù)學(xué)和科學(xué)課的工具），要么

2、就是講授程序設(shè)計(jì)。這兩種講法都沒有抓住計(jì)算機(jī)科學(xué)的本質(zhì)，盡管兩者都包括了訓(xùn)練方面。計(jì)算機(jī)科學(xué)課的學(xué)習(xí)應(yīng)由一些最基本的一般概念組成，這些概念超越技術(shù)本身，并且是高中教育的一個(gè)基本組成部分。正是這些概念使學(xué)生們得以了解并有效地參與到現(xiàn)代世界中來。 摘自ACM高中計(jì)算機(jī)科學(xué)課程規(guī)范4目前，在高中計(jì)算機(jī)教師隊(duì)伍中還有不少人是在其他領(lǐng)域里受的教育，他們很少有機(jī)會(huì)接受計(jì)算機(jī)科學(xué)方面的正規(guī)培訓(xùn)，有些完全是自學(xué)的。因此在實(shí)施具體教學(xué)過程之前，其中的大多數(shù)人還需接受某種正規(guī)培訓(xùn)，以更好地理解和掌握現(xiàn)代計(jì)算機(jī)科學(xué)的理念。 摘自ACM高中計(jì)算機(jī)科學(xué)課程規(guī)范5在教學(xué)過程中，要讓學(xué)生們學(xué)會(huì)把一個(gè)算法看成是一個(gè)活生生的處

3、理過程的一種精確描述，而這種處理可以由計(jì)算機(jī)、人或某種機(jī)器來實(shí)現(xiàn)。學(xué)生要學(xué)會(huì)設(shè)計(jì)簡(jiǎn)單的算法，并對(duì)這種算法的效率能做出粗略評(píng)價(jià)；要能夠說明算法的基本構(gòu)件，如順序、選擇和重復(fù)；也要能夠認(rèn)識(shí)算法的許多不同形式的表示，程序設(shè)計(jì)語言只是許多表示方法中的一種。摘自ACM高中計(jì)算機(jī)科學(xué)課程規(guī)范6一、為什么標(biāo)準(zhǔn)要將這門課列入選修模塊12003年4月教育部頒布了普通高中課程方案，方案強(qiáng)調(diào)提高學(xué)生“分析和解決問題的能力”。同年，教育部制訂的技術(shù)課程標(biāo)準(zhǔn)(信息技術(shù)部分)在課程目標(biāo)中提出：“能熟練運(yùn)用信息技術(shù)，通過有計(jì)劃的、合理的信息加工進(jìn)行創(chuàng)造性探索或解決實(shí)際問題”。要求是比較高的。 怎樣培養(yǎng)學(xué)生分析問題和解決問題

4、的能力，通過算法與程序設(shè)計(jì)課程的教學(xué)是達(dá)到這一目標(biāo)的有效途徑之一，這一點(diǎn)在標(biāo)準(zhǔn)起草小組中有了共識(shí)。72信息技術(shù)和數(shù)學(xué)兩個(gè)標(biāo)準(zhǔn)起草小組曾兩次在一起討論，如何加強(qiáng)算法理念的教學(xué)。中科院張景中院士等人專門就“算法”列入教學(xué)內(nèi)容提出了看法和建議。83算法在問題求解中的地位 問題空間 計(jì)算機(jī)空間問題定義模型化自然語言偽代碼數(shù)學(xué)語言數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)算法制定自動(dòng)數(shù)據(jù)轉(zhuǎn)換機(jī)器指令程序設(shè)計(jì)語言計(jì)算機(jī)實(shí)現(xiàn)編碼問題定義模型化自然語言數(shù)學(xué)語言94基于問題求解驅(qū)動(dòng)的算法課程設(shè)計(jì)的教學(xué)模式之一優(yōu) 化問題定義問題描述引導(dǎo)形成問題描述算法與數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)編制代碼上機(jī)實(shí)現(xiàn)算法程序的質(zhì)量分析問題分析生成結(jié)果分析結(jié)果修正過濾分類抽象化問

5、題來源n問題來源2問題來源1問題來源2學(xué)教10二、教材編寫思路早先，在高中計(jì)算機(jī)課程中，不少學(xué)校曾試驗(yàn)過程序設(shè)計(jì)語言的教學(xué)，較多時(shí)間介紹該語言所用的符號(hào)、語句和規(guī)則等，在講解編程舉例時(shí)也講一點(diǎn)算法，用來作為語言應(yīng)用實(shí)例。實(shí)際上這是一種本末倒置。為此，我們嘗試在教材中強(qiáng)調(diào)算法在解決問題過程中的關(guān)鍵地位，得到了教育部評(píng)審專家的肯定。審查意見認(rèn)為：“突出了“算法”的核心地位，有一定特點(diǎn)，可以探索使用?！?11.嘗試新的教材體系著名的計(jì)算機(jī)科學(xué)家Kunth認(rèn)為：計(jì)算機(jī)科學(xué)是算法的學(xué)習(xí)。瑞士科學(xué)家Wirth給出公式：算法數(shù)據(jù)結(jié)構(gòu)程序。算法是程序設(shè)計(jì)的依據(jù)，而程序設(shè)計(jì)語言只是算法描述的手段之一。為此，我們

6、在教材中花了相當(dāng)多的篇幅，以問題解決為核心，用較易理解的自然語言和流程圖語言來描述算法，讓學(xué)生充分體驗(yàn)算法的作用，并逐步建立起算法思維的理念和方法。有了上述基礎(chǔ)再講“算法實(shí)現(xiàn)（編程、上機(jī)）”就比較自然了。122.幾種常用算法的介紹教材介紹了 5 種常用算法： 枚舉（蠻干）、解析、排序、查找、遞歸。這幾種算法在學(xué)習(xí)、生活和工作中是大量遇到的。(1)枚舉算法。 教材介紹了兩個(gè)例子，其中關(guān)于“單據(jù)”的實(shí)例比較有趣，而第二個(gè)例子是解不定方程，解不定方程技巧性很強(qiáng)，但用計(jì)算機(jī)進(jìn)行枚舉搜索卻比較容易，學(xué)生也易于理解。13 (2)解析算法。 將問題歸結(jié)為數(shù)學(xué)表達(dá)式，并通過計(jì)算機(jī)來實(shí)現(xiàn)問題求解，是學(xué)生較易接受

7、的。困難點(diǎn)可能是如何歸結(jié)出表達(dá)問題的數(shù)學(xué)表達(dá)式。 (3)排序和查找算法。 “排序和查找”在學(xué)校學(xué)習(xí)中被大量運(yùn)用，學(xué)生會(huì)排序，但不知道如何用計(jì)算機(jī)來排序；用計(jì)算機(jī)檢索資料對(duì)有些學(xué)生來說是輕而易舉的事，但他們可能不知道資料為什么會(huì)這么快被查到。這里面就有一個(gè)知其所以然的問題。14 Kunth在他的計(jì)算機(jī)程序設(shè)計(jì)的藝術(shù)的第3卷整卷探討了這兩種算法，可見其重要性。有專家稱這兩種算法是“使用頻率最高的算法”。(4)遞歸算法。 這種算法應(yīng)用很廣泛，它是一個(gè)把較大規(guī)模的問題逐次簡(jiǎn)化為一個(gè)簡(jiǎn)單易解問題的一般算法。遞歸就使程序調(diào)用自身。教材以計(jì)算n!為例來說明遞歸算法。153.教學(xué)實(shí)施建議(1)按教材編寫順序進(jìn)

8、行教學(xué)。 這確實(shí)是一種新的嘗試，突出了算法思想，但由于在第三章學(xué)習(xí)前較難安排上機(jī)實(shí)踐，會(huì)使學(xué)生感到不適應(yīng)。為此，我們?yōu)榻滩呐涮琢斯獗P，其中附有全部實(shí)例的算法執(zhí)行過程(流程圖)的演示動(dòng)畫，生動(dòng)直觀，有助理解。 (2)將第二章的“排序”、“查找”和第五章的程序?qū)崿F(xiàn)結(jié)合起來組織教學(xué)，這樣可使編程和上機(jī)的時(shí)間提前。16三、計(jì)算機(jī)處理中的“難”的問題和不可解問題現(xiàn)實(shí)世界中，大量非數(shù)值問題在求解時(shí)，首先要判定其是否可解。通過建立計(jì)算的數(shù)學(xué)模型（如圖靈機(jī)、遞歸函數(shù)、-演算、Post系統(tǒng)等）精確區(qū)分哪些是可計(jì)算的，哪些是不可計(jì)算的。但是許多問題本身是不可判定的(如悖論問題、圖靈機(jī)停機(jī)問題等)。只有是可判定、可

9、計(jì)算的問題，才能通過精確的算法描述進(jìn)行求解。 計(jì)算的過程就是執(zhí)行算法的過程?？捎?jì)算性的核心問題是將算法這一直觀概念精確化，變?yōu)橐粋€(gè)具有有限性、可執(zhí)行性、確定性、終止性、有限個(gè)輸入、1個(gè)或1個(gè)以上輸出的具體算法。 17現(xiàn)代計(jì)算機(jī)處理問題的能力確實(shí)很強(qiáng)，我們的學(xué)習(xí)、工作、生活都離不開計(jì)算機(jī)。這一點(diǎn)經(jīng)過多年的信息技術(shù)課程的學(xué)習(xí)，學(xué)生們都有體會(huì)。但是，計(jì)算機(jī)不是無所不能的，有些問題對(duì)計(jì)算機(jī)來說是很“難”的，有的則是計(jì)算機(jī)無法解決的。這些在教材中沒有寫入，而是在教師用書的第三部分作了一些介紹，盡管是淺顯的，任課老師讀一讀有好處，條件較好的學(xué)校，可將其中一些思想介紹給學(xué)生。181.多項(xiàng)式問題（P問題） 如

10、果一個(gè)問題的規(guī)模是n，按某種算法解決問題時(shí)用的計(jì)算次數(shù)是n的多項(xiàng)式，或者說計(jì)算的復(fù)雜度為O(log n)，O(n)，O(n2)，O(n3)或O(nk)（k為常數(shù)），則稱該算法為多項(xiàng)式算法，而這類問題稱為多項(xiàng)式(P)問題。以當(dāng)今計(jì)算機(jī)的處理速度，對(duì)于一個(gè)有合理輸入數(shù)量的多項(xiàng)式問題，計(jì)算機(jī)都能有效地予以解決。 一個(gè)問題會(huì)有多種算法，算法會(huì)有快、慢。例如教材中排序、查找部分，選擇排序比冒泡排序快，對(duì)分查找比順序查找快，等等。192.非多項(xiàng)式問題（NP問題） 有許多問題，當(dāng)它們的規(guī)模變得越來越大時(shí)，不管你采用什么算法，求解它所用的時(shí)間都會(huì)長(zhǎng)得驚人。就算是用當(dāng)今的快速計(jì)算機(jī)，都無法在可容忍的時(shí)間內(nèi)完成，

11、這就是所謂非多項(xiàng)式（NP）問題。20若問題求解時(shí)所用算法的計(jì)算時(shí)間的階等價(jià)于某種指數(shù)函數(shù)，或者說算法的復(fù)雜度為O(2n)，O(kn) （k為常數(shù)）或O(n!)， 則稱該算法為指數(shù)型算法，而這類問題就是非多項(xiàng)式（NP）問題。非多項(xiàng)式問題遠(yuǎn)比多項(xiàng)式問題難度大，當(dāng)問題規(guī)模增大時(shí)，用計(jì)算機(jī)處理需要數(shù)月甚至數(shù)年的時(shí)間才能得出問題結(jié)果。例如，梵塔問題、貨郎擔(dān)問題、因式分解問題、縱橫字謎問題、圖形著色問題、棋類博弈問題、可滿足性問題等等都是所謂“難”的問題。213.不可解問題 對(duì)這類問題，無法用計(jì)算機(jī)程序來解決。圖靈是較早發(fā)現(xiàn)這類問題的人。例如，他提出了“停機(jī)問題”就是一個(gè)不可解問題。還有很多不可解問題。問 題不可解的問題非多項(xiàng)式問題多項(xiàng)式問題可解的問題22小結(jié)： 計(jì)算機(jī)是現(xiàn)代化信息處理工具，“信息”在這里是以有限種符號(hào)的有限長(zhǎng)序列這種形式所表示的，而“處理”的過程就是按預(yù)先編好的程序?qū)@種序列做有窮的變換，以得到一組新的符號(hào)序列作為結(jié)果。這就是計(jì)算機(jī)科學(xué)中術(shù)語“計(jì)算”的確切含義。 要計(jì)算機(jī)去解決某種問題，有三個(gè)基本前提：231.必須把問題形式化計(jì)算機(jī)求解的過程就是從表示問題的符號(hào)串出發(fā)，按規(guī)則進(jìn)