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

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

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

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

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

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

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

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

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

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

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

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