Google 面向教育者的計算思維課程

1Google面向教育者的計算思維課程課程目錄一、計算思維簡介 41-1什么是計算思維? 41-1-1計算思維(CT:ComputationalThinking) 51-1-2計算思維要素 61-1-3將計算思維應用在未來課堂中 61-2課程如何運作 81-2-1課程結構 81-2-2其他內容 9二、算法探究 2-1概述 2-1-1計算機科學:旅行 2-1-2人文學科:與時俱進的字詞 2-1-3數學:元胞自動機 2-1-4科學:基因組學 212-2課程反思 24三、模式發(fā)掘 263-1概述 263-1-1計算機科學:數據壓縮 273-1-2人文學科:音樂 323-1-3數學:小海龜幾何 353-1-4科學:分類 403-2課程反思 44四、算法開發(fā) 464-1概述 464-1-1計算機科學:漢諾塔 474-1-2人文學科:聊天機器人 514-1-3數學:計算器 544-1-4科學:彈力球 604-2課程反思 632五、應用計算思維 665-1項目概要 665-2反饋、評估、評分 665-2-1項目,第一部分 665-2-2項目,第二部分 665-3樣例項目 675-4總結 683本課程的目標是幫助教育工作者學習計算思維(CT:ComputationalThinking),了解它與計算機科學的區(qū)別,以及理解如何將其整合到不同的學科中。在課程學習過程中,你將深化對于計算思維的認知,探究計算思維與特定學科相結合的案例,參與將計算思維應用到特定學科領域的綜合實踐活動,制定一個計劃將計算思維整合到你自己的課程中。本課程分為五個單元,每個單元的要點如下:●計算思維簡介:什么是計算思維,它出現在哪里?它為何需要你的關注?以及它是被如何應用的?●算法探究:課程帶你親歷學科領域中的算法實例。認識到算法是一種可以提高學習者做事能力的強大工具,同時認識到技術對于實現算法和完成算法的自動化是非常有用●模式發(fā)掘:探索學科案例中蘊含的模式例子,通過模式識別形成一套自己獨有的、探●算法開發(fā):增強你在解決問題過程中應用算法過程的信心,并了解算法是如何清晰地●課程項目:應用計算思維。撰寫一份如何將計算思維應用到你的學科中的計劃,陳述41-1什么是計算思維?這部分是5分38秒的視頻,譯文如下:如何繪制人類的完整DNA序列?威廉莎士比亞的著作是否全部親筆所著?是否能編寫出可自主作曲的智能電腦程序?以上這三個現實問題有什么共性嗎?要想回答這些問題,需要使用所謂的計算思維。每天都有越來越多的人正在使用這種思維方式解決各式各樣的問題。因此,無論教授數學、科學、計算機或者人文學科,計算思維都能為你的課堂活動添磚加瓦。那么,什么是計算思維呢?計算思維是一種問題解決的方式。這種思維將問題分解,并且利用所掌握的計算知識找出解決問題的辦法。計算思維可以劃分為四個主要組成部分:其一,所謂“解構或分解”,即把問題進行拆分,同時厘清各個部分的屬性,明晰如何拆解一個任務;其二,所謂“模式識別”,即找出拆分后問題各部分之間的異同,為后續(xù)的預測提供依據;其三,所謂“模式歸納”,或“抽象化”,即探尋形成這些模式背后的一般規(guī)律;其四,所謂“算法開發(fā)”,即針對相似的問題提供逐步的解決辦法。如今人們嘗試在許多學科領域中應用計算思維解決問題。當大數據分析探尋內部規(guī)律的難題的時候,表明他們正在運用計算思維進行思考。計算思維帶動了計算生物學、計算化學等領域的發(fā)展,同時也帶來了能夠運用在文學、社會研究和藝術方面的全新技術。計算思維早已來到我們身邊,存在于我們生活各處,所以我們沒必要對其感到恐懼。5有些人將計算思維和計算機科學混為一談,但事實上這二者涇渭分明。計算機科學是一門學術性學科,包括了可計算性的研究及其借助計算機的應用。相比之下,計算思維則是我們攻克難題的一種方式。即是一種直觀與抽象的思維方式。無論你是否是計算機科學家,還是其他什么人,你都會用到計算思維。這是一種讓人獲益匪淺的普適思維技能。計算思維還能增雜的或開放性的問題時候的自信心。因此,任何學科背景或年齡段的學生都應該學習計算思維。將問題分解成大小不同的部分,并逐一處理解決,最終進行總結歸納以解決整體問題,這是一種讓人受益的技能。假設你現在是一名記者,想要了解人們對待即將到來的大選所持的各種觀點。一種方法是在大街上詢問他們的想法,另一種方法是使用一種能夠在幾秒之內分析數以萬計的社交媒體網站內容的計算機程序。這是一個能夠體現基于計算思維解決問題優(yōu)勢的例子。因此,過去的學生如果想要尋找和理解數據,需要人工收集數據,而現在的學生可以通過改進算法迅速地獲得結果,將更多的注意力放在對數據進行深入研究上,而不是放在收集與計算數據上面。通過運用科技的力量,我們能夠會聚精力,增強洞察力,分析具體情況,并且得出結論。學生們不應該只是簡單地使用教給他們的模型,而應該能夠創(chuàng)建出來自己的模型。為了做到這點,學生們必須借助計算思維,發(fā)現或者洞察出隱藏在事物背后的聯系。計算思維不是額外的負擔或需要單獨教授的內容,而是對現有課程的優(yōu)化。因此,早期我多以日常生活的案例來說明計算思維,幫助學生理解計算思維是一種與其自身息息相關的事物,他們就會明白計算思維確實存在于生活的各個方面。如果我們的學生掌握了計算思維技能,成為技術創(chuàng)新者,那么,他們不僅能夠在國際專業(yè)領域找到立足之地,還可以通過創(chuàng)造性地解決重要問題而造福社會。那么如何繪制人類基因序列呢?答案是借助算法與電腦程序給DNA中數以百萬計的堿基對進行排序。如何破解莎士比亞著作之謎呢?答案是通過計算機分析莎翁作品的詞匯、主題和風格,能夠確認莎士比亞確實編著了自己名下所有的作品,實至名歸。至于那個如何實現智能作曲的問題,則可以通過計算思維發(fā)現已有音樂作品中的存在方式與規(guī)律,編寫程序,生成全新的音樂作品。今天的人類所面臨的全球重大問題,都需要跨學科來解決。通過將計算思維的技能整合進入所有學科之中,所培養(yǎng)出來的學生能夠對過去看似無解的問題,提出全新的解決方案。當然今天或許還無法解決很多大自然的謎題,諸如重力如何產生,能否治愈癌癥,等等,但是在不久的將來,我們的學1-1-1計算思維(CT:ComputationalThinking)計算思維是一個有著諸多特點和要求的問題解決過程。計算思維不但6常重要,而且它也可以用于所有學科的問題解決,包括人文學科、數學和科學等。學生在完成計算思維的課程后,不但能了解各學科之間的關聯,同時也能夠體會到課外生活與課堂內知識之間的聯1-1-2計算思維要素本課程提供了一次機會來體驗計算思維的基本要素,包括:?分解:把數據、過程或問題分解成更小的、易于管理或解決的部分?模式識別:觀察數據的模式、趨勢和規(guī)律?抽象:識別模式形成背后的一般原理?算法開發(fā):為解決某一類問題撰寫一系列詳細的指令。國際教育技術協會(ISTE),計算機科學教師協會(CSTA)和英國學校計算課程工作小組(CAS)與教育界和工業(yè)界的代表們合作,共同開發(fā)了面向教育工作者的計算思維資源。學校計算課程工作小組(CAS)計算思維網站谷歌探索計算思維(ECT)網站(見附件一)1-1-3將計算思維應用在未來課堂中我們的目標是你可以盡快地在教學中使用或傳授計算思維相關概念。相比于重新創(chuàng)設一門計算思維的新課程而言,教師在自己已有的課堂教學中使用計算思維的方法和概念反而能夠獲得更好的效果。表1-1顯示了計算思維與計算機科學的區(qū)別:將計算圖表問題拆分成四部分來處理,每7度,并注意到它的發(fā)展趨勢相對于復雜的編程,用較少代碼實現復數計算機科學是關于信息的研究:如何表征信息?如何優(yōu)化存儲信息?如何處理信息?計算機科學是使用計算機進行計算及其應用的研究。而另一方面,計算思維則包括編寫計算機程序時所使用文學:通過對韻律、韻文、意象、結構、語經濟:尋找國家經濟增長和下降的循環(huán)模式烹飪藝術:撰寫供他人使用的菜譜數學:找出二階多項式分解法則化學:找出化學鍵(類型)及(分子間)相在左列中,所有技能都是計算思維涉及的技能或概念。而在右列,這些技能被應用到文學、經濟、烹飪藝術和音樂中。就本質來說,計算思維是計算機科學家的基本技能和思維方式。然而你可以將它應用在你所教授的學科領域或主題,甚至是任何學科領域或主題。并且,你可以在設計流程或算法以解決問題過程中,隨時應用這些思維技巧。你可能會注意到課程中包含了程序設計的內容。計算思維并不囿于使用某一種編程語言,然而8編程其實是一種很好的觀察問題解決方式的途徑。編寫代碼既不是本課程的學習目標,也不是開始本課程學習的前提條件。如果你在課程中的某個環(huán)節(jié)遇到障礙,包括代碼部分,可以在課程社區(qū)(或者參考附件二)中尋求幫助。1-2課程如何運作這門課程的目的是增加世界范圍內教育者對于計算思維(CT:ComputationalThinking)的了解認識并鼓勵他們將計算思維整合到他們的教學大綱中。這門課程分為五個部分,其主要內容包括:●計算思維簡介:什么是計算思維——計算思維是什么,哪里可以使用計算思維?為什么我們要關注計算思維和如何應用計算思維?●算法探究:回顧一下在你熟悉的領域中使用算法的例子。思考一下為什么算法是一個可以讓你事半功倍的強大工具,各種技術如何借助算法執(zhí)行以及自動化,提●模式發(fā)掘:通過探索存在不同領域中不同事物中的各種模式,形成屬于你自己的●算法開發(fā):增加你對使用計算思維解決指定問題的信心,并且讓你了解如何用算●課程項目:應用計算思維。闡述你如何在學科中應用計算思維,并嘗試制定一個1-2-1課程結構課程:由五個單元組成,其中包括一個由兩部分組成的課程項目單元:由一組小課程組成;每個單元包含一組適合四個不同群體的混合課程與活動:課程活動:包括用于增強學習者計算思維意識的實例模擬、程序與練習,計算思維整合案例9的展示,并允許學習者通過互動方式將計算思維應用到各自的學科領域。課程活動同時提供了完成活動任務的操作步驟,延伸學習內容的一些鏈接,用于實踐技能和反饋獲取的活動,以及一個課程項目:提供把你在課堂上所學技巧應用于實踐的機會。1-2-2其他內容更多的資源本課程僅是開始,找到課程、資源、刊載論文,更多請參閱探索計算思維(或者參考附件一)。討論社區(qū)這是你提出問題、分享創(chuàng)意,并向同行提供反饋的地方。?國內討論社區(qū):TBD?Google全球計算思維課程討論社區(qū):計算思維社區(qū)鏈接(或者參考附件二)2-1概述在本節(jié)中,你可以體驗一些稍作修改就能用于你的課堂教學的活動。這些活動不需要任何編碼,并打算提供一些合理使用算法和計算思維的例子,請點擊下面的活動的鏈接來體驗吧。也歡迎隨意體驗學科領域以外的活動,像你所期待的學生們那樣探索、試驗、游戲和享受吧!2-1-1計算機科學:旅行你和家人正在計劃穿越區(qū)域內所有主要地點的自駕游,且你需要規(guī)劃出最短的路線以節(jié)省燃油在圖2-5-a中的地圖中從下拉菜單中選擇緯度、經度、隨機、可拖拽,運行一個自駕游樣例。看到結果后,嘗試將模式切換到“可拖拽”,并完善出你認為最好的路線。圖2-5-a互動式地圖探索示意圖(所有國家)圖2-5-b互動式地圖探索示意圖(可拖拽模式下的路線規(guī)劃)圖2-5-c互動式地圖探索示意圖(按緯度排序模式下的路線規(guī)劃)圖2-5-d互動式地圖探索示意圖(按經度排序模式下的路線規(guī)劃)圖2-5-e互動式地圖探索示意圖(隨機模式下的路線規(guī)劃)互動時地圖網址(原課程英文網站)現在你有機會測試一些選項,并思考如何解釋來說服家人采用你所建議的路線。你的提議中是否包含一些城市列表或諸如“由西向東”的指導原則呢?以下是一些需要考慮的問題:1.出發(fā)城市的選擇是否重要?2.你的路線策略(經度、緯度等)適用于任何國家還是需要因地制宜?請嘗試在另一個國家中使用你的策略,看它是否同樣有效。3.這個難題的成因是什么?這類問題通常被稱為旅行推銷員問題,其面臨的挑戰(zhàn)在于每個城市只能經過一次,并且最后需要回到起點城市。雖然此類問題尚未被人們完美地解決,但是人們研究這個問題和發(fā)展算法試圖解決這個問題(即使以一個次優(yōu)的方式)的過程與成果,已經被用來提高許多其他相關問題的效率。路徑規(guī)劃和海量數據搜索(如DNA和網頁),就是兩種類似的問題。如希望進一步探討此主題,請在互聯網搜索:旅行推銷員問題、NP(Non-DeterministicPolynomial,非確定多項式)問題。若與學生一起使用,可為此活動增加活動標準(或者參考附件三)。2-1-2人文學科:與時俱進的字詞假設你想知道近些年在不同文化背景下,“愛”這個字是如何被使用的。假定書籍就承載了文化中有價值和有意義的部分,如果要清點“愛”字在一本書,甚至是大量書中出現的次數,要花費你多長時間?谷歌NgramViewer(見圖2-6-a所示)直觀地顯示出許多已經被谷歌掃描過的書籍里某請嘗試在下面的搜索欄里把“l(fā)ove”字替換為其它字詞。隨著時間的推移,哪些字詞呈現上升或下降趨勢?是否有字詞在圖表中呈波峰曲線?圖2-6-a谷歌NgramViewer的搜索結果(關鍵詞“l(fā)ove”)圖2-6-b谷歌NgramViewer的搜索結果(關鍵詞“computer”)圖2-6-c谷歌NgramViewer的搜索結果(關鍵詞“愛”)圖2-6-d谷歌NgramViewer的搜索結果(關鍵詞“計算機”)互動網址:/ngrams你把今天的報紙交給一群人,并讓他們找到出現頻率最高的字,你建議他們用什么方法以便在最短時間內得出答案?若要求同樣一群人用幾句話總結當天的新聞,你會怎樣提示以協助他們找到當天最重要的信息?假若是回顧一年里報紙最有價值的信息又將如何呢?用于掃描書中所有字詞的算法和抓取網頁,從中分析重要的,和你的查詢有密切關聯語詞的過程是類似的。此類算法已使搜索大量數據信息成為可能。如果你想繼續(xù)探索這些可能性,請嘗試以下想法:1.在NgramViewer中查詢多個單詞。請鍵入“l(fā)ove”、“money”至上面Ngram的搜索欄,并對趨勢是否是一個巧合、一個有意義事件的反映或文化變遷提出假設。加入“悲傷”,以查看這些趨勢與你的搜索詞是否相關。2.嘗試相反的方法。針對一件特殊的重要事件,思考看能否找到恰當的搜索關鍵詞,可以3.哪種媒介最能代表你的文化修養(yǎng)?報紙、書籍、音樂、電影、短信、YouTube視頻或其它?知更多主題。如果學生使用,此活動的潛能標準(或者參考附件二)亦可作相應匹配。2-1-3數學:元胞自動機現在有一個由多個方塊組成的網格,當點擊某個方塊就可以激活它,方塊的顏色也會從白色變?yōu)槌壬?方塊上的數字代表與它相鄰的方塊有多少是“存活”的(每個方塊都有8個相鄰的方塊)。例如,如果只有一個方格被選中,然后所有方格周圍顯示1。圖示2-7是一些例子:請嘗試點擊網格中的一些方格,然后按幾次前進,觀察網格如何變化。在圖2-8的運動界面中,你還可以單擊開始/停止來看看它繼續(xù)運行。是什么導致了方格的出現和消失?互動鏈接:/edit/MathCellularAutomata在網格中依次點擊若干方塊,再點擊“Advance”按鈕若干次,單步運行程序,觀察網格的變化。也可以點擊Start/Stop按鈕自動多步運行示或者消失呢?這個游戲有趣的地方在于它所使用的規(guī)則。上面這段代碼的第2和第3行定義了游戲規(guī)則:如果某個方塊是“活”的(橙色)狀態(tài),并且它相鄰的方塊中有2~3個是“活”的,那方塊就保持“活”的或“幸存”狀態(tài)。如這兩種狀態(tài)的方塊:2、3,在程序運行后仍然是“存活”的狀態(tài)。如果某個方塊是“死”(白色)的,但是若它相鄰的方塊中有3個或6個方塊是“活”的,那么這個死的方塊就會被激活。如這兩種狀態(tài)的方塊:3、6,在程序運行后,這兩種方塊都會被激除了以上四種情況,其他狀態(tài)的方塊在程序運行后都會是“死”的狀態(tài)(方塊顏色從橙色變?yōu)榘咨?。這只是個仿真游戲,沒有任何方塊會被傷害哦!下面是一些例子:程序單步運行后,左圖中“4”周圍所有“3”的方塊或者仍然保持“存活”狀態(tài)或者被激活,“4”的方塊會從“存活”的狀態(tài)轉為“死亡”狀態(tài),且由于它周圍所有的方塊都是“存活”狀態(tài),所以方塊的數字從“4”變?yōu)榱恕?”,其余各方塊的數字也隨之發(fā)生了變化,最后結果如右圖。(大家想想,如果再點擊一次Advance,方塊又會有何變化?)程序單步運行后,左圖中所有“3”的方塊全部被激活,其余處于“存活”狀態(tài)的“1”和“4”的方塊都會從“存活”狀態(tài)轉為“死亡”狀態(tài),各方塊相應的數字也隨之發(fā)生變化,運行結果如右圖。(大家想想,如果再點擊一次Advance,方塊又會有何變化?)程序單步運行后,左圖中處于“存活”狀態(tài)的“2”仍然保持存活,處于“死亡”狀態(tài)的“3”全部被激活,處于“存活”狀態(tài)的“1”轉為“死亡狀態(tài)”。各方塊上的相應數字也發(fā)生了變化,最后運行結果如右圖。(大家想想,如果再點擊一次Advance,方塊又會有何變化?)20上圖中只有中間一個方塊是“存活狀態(tài)”,所有的方塊都不滿足“存活”或“復活”的條件,因此程序單步運行后,所有方塊都是“死亡”狀態(tài),方塊消失。單擊網格來創(chuàng)建自己喜歡的圖案,你可以不斷點擊Advance來看看每個周期應用規(guī)則的結果,也可以點擊Start來看看多個周期自動應用規(guī)則的結果。如此有趣的交互來自看似隨意的規(guī)則。人們研究這些圖案多年,并發(fā)現了一些特定的組合,就像在野外發(fā)現某種類型的動物一樣。在網格上創(chuàng)建圖案,點擊Start來試著讓圖案應用規(guī)則后能滿足下面這些類型:?穩(wěn)定的-圖案不隨時間發(fā)生變化?振蕩器-圖案會隨時間變化,但會在N個周期后重復?飛行物-圖案本身不會發(fā)生變化,但是會像鳥和飛船一樣移動位置?找出你自己的圖案屬于哪種類型修改系統(tǒng)的另外一種方式是改變規(guī)則本身。上面仿真的例子中所應用多規(guī)則中為人所熟知中的一種,每一個新規(guī)則都會產生全新的屬性集。上述的仿真使用的是一連串"S/B"規(guī)則,S代表survival幸存者,B代表births新生者。在這個“人生游戲”(GameofLife)的仿真中,S/B的值是23/36,意思是某個存活方塊如果有2個或3個相鄰的存活方塊,該方塊仍然是存活的,某個死亡的方塊如果有3個或6個相鄰的存活方塊,該方塊就會復活。你可以看看這些人們研究了多年的各種規(guī)則,并試著在仿真中修改第2和第3行代碼來應用這些規(guī)則。如果你修改了規(guī)則,記住要點擊Play按鈕來重新運行代碼。數學是一個跨領域的課題,關于系統(tǒng)及其行為的研究已經影響并開拓了許多科學和人文研究領域。而很多新知的發(fā)現和新研究領域開辟,往往是由于新算法的設計和應用所產生的。如果你對于元胞自動機以及生命游戲的研究感興趣,你可以通過網絡搜索這兩個關鍵詞來獲得更多的信息。StephenWolfram曾研發(fā)過一個為元胞自動機創(chuàng)建規(guī)則的系統(tǒng),并對其性質進行了廣容。當你在對學生進行教學的時候,可以使用該標準來評測本活動。212-1-4科學:基因組學根據人類基因組計劃的研究結果,人類細胞中DNA的堿基對長度大約在5千萬到2.5億之間。研究者們仍在不斷加深對基因功能和基因表達方面的理解。編碼在DNA中的信息量巨大,同時基因之間的相互作用也非常復雜。那么科學家是如何從如此多的可能性和數據中獲得有用的結論的呢?算法的應用起到了很大的作用。即使在這些技術能被高效的使用之前,人們就已經嘗試將算格雷戈爾·孟德爾是研究豌豆雜交育種和古老選擇育種技術的先驅。孟德爾所進行的試驗中影響最為深遠的部分,是他從結果中發(fā)現的模式。孟德爾研究了數千種植物,從中尋找那些特定性狀被選擇出的結果。通過研究這些數據,孟德爾發(fā)現了遺傳的模式,并揭示了如今被稱為遺傳定律的規(guī)律。盡管旁氏表要在數年后才被發(fā)明出來,但是它能夠幫助你將這些遺傳可能性可視化。你可以想象這對孟德爾是一個多么大的挑戰(zhàn)!首先我們想象有一個可以決定花朵顏色的基因。如同人類一樣,花從它的父母那里分別獲得一個基因。這些基因可能彼此不同,使得花朵呈現出遺傳的多樣性。對于該顏色基因,我們假設它有兩種表現型:紫花(P)和白花或者無顏色花(p)。當有機體中的兩種基因都是白花基因(pp)時,花朵顏色呈白色。只要有一個顏色基因為紫色基因(Pp或者PP)時,花朵呈紫色。下面的旁氏表展示了當父母分別具有兩種基因時,子代的全部四種可能的基因型。這樣的父母被稱為雜合子。雜合子的子代有75%的可能性顯性基因時,這一結果就會發(fā)生變化。當存在復數的基因時,其子代的基因型的可能性的數目也呈指數方式增長。一次雙因子雜種雜交(兩種基因)將會有16種可能性,而三因子雜交則有64種PpPp22你可以看到這些數據的采集量和計算量驚人的增長速度。很難想果,格雷戈爾·孟德爾在七年的試驗中需要投入多大的精力和耐心。而當你想到人類的基因組包含有超過20000種基因時,你會發(fā)現紙、筆以及傳統(tǒng)的計算方式已經無法滿足基因研究的需求。然而,當你關注這些研究數據時,你會跟孟德爾一樣發(fā)現:數據中的模式可以用來歸納法則,并幫助算法是一系列具體指令的集合,這些指令可以通過對數據進行模式搜索、計算概率以及其他方式來幫助我們理解這些數據。甚至人類細胞在進行DNA復制和蛋白質合成時使用的過程,也是某種轉錄和翻譯算法。該過程的每一步都可以被清晰的記錄和理解。人類的不在重復著這一過程,而這清晰的向我們展示了算法的威力。理解這個過程能夠幫助科學家們更好的了解人體的生理過程,并能夠幫助我們找到對抗病毒的新方法。轉寫和翻譯的實例以下是一個用代碼模擬DNA轉寫成信使RNA,再將信使RNA翻譯成氨基酸鏈的例子。的細胞每天都在經歷這一過程來合成身體所需的蛋白質。通過模擬這一過程,我們將能夠觀察到單在以下的實例中,第一個DNA片段來自血紅蛋白的DNA編碼(HBB)。第二個和第三個DNA片段大體上是相同的,除了第二個片段中的第五個堿基對由“C”被改為“T”而第三個片段的“C”轉寫和翻譯算法的實例:transcription_dict={'A':'U','G':'C','C':'G','T':'A'}translation_dict={'UUU':'Phe','UUC':'Phe','UUA':'Leu','UUG':'Leu','UCU':'Ser','UCC':'Ser','UCA':'Ser','UCG':'Ser','UAA':'Stop','UAG':'Stop','UAU':'Tyr','UAC':'Tyr','AUU':'Ter','AUC':'Ter','UGU':'Cys','UGC':'Cys','ACU':'Ter','UGA':'Stop','UGG':'Trp','CUU':'Leu','CUC':'Leu','CUA':'Leu','CUG':'Leu','CCU':'Pro','CCC':'Pro','CCA':'Pro','CCG':'Pro','CAU':'His','CAC':'His','GUU':'Gln','GUC':'Gln','CGU':'Arg','CGC':'Arg','CGA':'Arg','CGG':'Arg','AUU':'Ile','AUC':'Ile','AUA':'Ile','AUG':'Met','ACU':'Thr','ACC':'Thr','ACA':'Thr','ACG':'Thr','AAU':'Asn','AAC':'Asn','AAA':'Lys','AAG':'Lys','AGU':'Ser',23'AGC':'Ser','AGA':'Arg','AGG':'Arg','GUU':'Val','GUC':'Val','GUA':'Val','GUG':'Val','GCU':'Ala','GCC':'Ala','GCA':'Ala','GCG':'Ala','GAU':'Asp','GAC':'Asp','GAA':'Glu','GAG':'Glu','GGU':'Gly','GGC':'Gly','GGA':'Gly','GGG':'Gly'}deftranscription(DNA):forbaseinDNA:mRNA+=transcriptiondeftranslation(mRNA):whileribosome_two<=end:codon=mRNA[ribosome_one:ribosome_two]ifcodonintranslation_dictandtranslation_dict[codon]isnot'Stop':amino_acid=translation_dictionamino_acid_chain.append(a結果:DNA#1:GGATCCTCACATGAGTTCAGTATATAATTGTAACAGAATAAAAAATmRNA:CCUAGGAGUGUACUCAAGUCAUAUAUUAACAUUGUCUUAUUUUUUAAminoAcidChain:Pro-Arg-Ser-Val-Leu-Lys-Ser-Tyr-Ile-Asn-Ile-Val-Leu-Phe-PheDNA#2:GGATTCTCACATGAGTTCAGTATATAATTGTAACAGAATAAAAAATmRNA:CCUAAGAGUGUACUCAAGUCAUAUAUUAACAUUGUCUUAUUUUUUAAminoAcidChain:Pro-Lys-Ser-Val-Leu-Lys-Ser-Tyr-Ile-Asn-Ile-Val-Leu-Phe-Phe24DNA#3:GGATCTCACATGAGTTCAGTATATAATTGTAACAGAATAAAAAATCmRNA:CCUAGAGUGUACUCAAGUCAUAUAUUAACAUUGUCUUAUUUUUUAGAminoAcidChain:Pro-Arg-Val-Tyr-Ser-Ser-His-Ile-Leu-Thr-Leu-Ser-Tyr-Phe-Leu這幾種變異,甚至只是很微小的一個堿基對的變化或刪除,都能對最終的蛋白質產物造成顯著的影響。因此,如果一個遺傳學家想通過手動過程來對這些進行研究的話,工作量是十分巨大的。與之相比,使用算法和代碼來模擬這一過程就能讓我們及時的看到這些變異對蛋白質產物的影響。將算法整合進科學領域能夠幫助科學家更有效率的進行研究,并節(jié)省下大量的實驗和分析時間。目前為止,人們還在對應用算法的成本和可行性進行優(yōu)化。當你和你的學生們能夠探索這些基因數據時,你們不僅可以了解到基因學的知識,還可以進行屬于你們自己的研究,甚至有所發(fā)現。如果你們對于如何將算法應用到基因研究的領域感興趣,RosalindProblems會是一個很好的關知識,而且可以學習到如何設計算法來解決這一類問題。即使你們沒有真正使用Python或者其他編程語言來實現這些算法,你的學生們也可以通過寫下解決問題的步驟,來加深對這些過程的了你可以從BLAST和GoogleGenomicsAPI(或者參考附件六)中找到那些被應用于生物信息學的工具。你也可以從Fold.it中親身體會到算法的威力,甚至能夠參與到生物學研究中來。這里有一些搜索關鍵詞能為你提供更多的信息:旁氏表(PunnettSquares),生物信息學(Bioinformatics),計算生物學(ComputationalBiology),和人類基因組計劃(HumanGenomeProject)。當你在對學生進行教學的時候,可以使用該標準來評測本活動。2-2課程反思定義一種算法的方法之一就是通過創(chuàng)建一連串的逐步指令,并使用這些指示去解決一個問題或者執(zhí)行某個任務。這一章節(jié)的目的就是展示算法的可能性。你也許在力,比如當你使用搜索引擎很快找到你想要的信息時,或者你使用的GPS設備基于交通狀況給出一個更好的路線時。你也許曾經意識到,開發(fā)一個算法或者對算法進行測試是不需要具體的代碼的。然而,使用編程技術則可以比手動更快更好的執(zhí)行算法的許多步驟。旅行問題旅行推銷員問題是計算機科學家所提出的一個經典挑戰(zhàn):為一名旅行推銷員規(guī)劃出一條穿過一25個國家的最優(yōu)路線。對于該問題來說,找到一條可行路線并不難。你只需要按照你自己的步驟創(chuàng)建一條經過所有城市的路線即可。然而,該問題的困難之處在與:如何確定一條最短路線或者步驟最少的路線,以及是否能在合理的時間內求得一個最優(yōu)可行方案。與時俱進的字詞當我們將算法用計算機技術實現的時候,我們會發(fā)現指令的執(zhí)行要比人工執(zhí)行快得多。這樣的效率優(yōu)勢在處理大規(guī)模數據的時候尤為明顯。以往需要大量人手共同工作數年才能得出的結果,如今在很短的時間就能得到。一個經典的計算機應用案例就是我們身邊的計算器:從前需要許多人共同合作才能完成計算量,在今天可以用任何袖珍計算器迅速完成。N-gramViewer就是一個將算法應用到大規(guī)模數據集合中,以獲得某些文化中有趣甚至是滑稽的發(fā)現。隨著越來越多的人了解如何分析數據和整理信息,他們將能夠把這些技能應用到新的領域當中,并幫助他們以一種以往難以想元胞自動機給定一個系統(tǒng)一些初始參數,并規(guī)定系統(tǒng)的運行規(guī)則,然后讓該系統(tǒng)自行運作——該過程我們稱之為混沌系統(tǒng)。對于元胞自動機來說,任何一點初始細胞生存狀態(tài)的或細胞繁殖的規(guī)則的變化,基因組學農民們早已知道動物和植物們已經用相似的特性繁衍后代長達一千多生命都使用相同的基因編碼和遺傳信息時,他們意識到其中蘊含著探索生命奧秘的巨大機會。從蒼蠅的研究中獲得的知識可以被應用到豬和其他的物種當中。更加深入的研究人類基因組,了解人類基因組是如何隨著時間而變化的,以及發(fā)現不同文化的人類種群間的基因差異,都有助于我們改善醫(yī)療技術和為人類這個種族留下歷史記錄。人類的DNA包括數千種不同的基因,而每一種基因都可能需要耗盡一個人的一生來進行研究。算法已經被應用到快速搜索和分析生物樣本之中,這能幫助科學家尋找模式與基因突變和某些治療手段造成的影響。沒有任何兩個現型。深入對于基因的研究將有助于人們了解自身的獨特性,并且體會到個體是如何融入更廣大的263-1概述在本節(jié)中,你可以試著參與到一些能被應用到你的課堂中的活動中來。這些活動涉及到編輯已有的代碼,但并不需要你事先對編程有所了解。這是一個體驗不同領域中計算思維過程的好機會,所以請不要有顧慮的去嘗試那些你不熟悉領域中的活動吧。點擊一個活動以開始課程,探索并享受其中的樂趣吧!273-1-1計算機科學:數據壓縮就在不久之前,內存容量和存儲空間大小仍然是困擾手機和電腦消費者的主要因素?，F如今,當你在考慮購買相關設備,尤其是準備購買移動設備并準備在里面存儲大量多媒體信息時,存儲空間的大小依舊是一個需要考慮的重要因素。在當今時代,有很多的信息和數據都來源于網絡。開發(fā)者們不得不思考如何才能壓縮數據規(guī)模,以避免存儲空間消耗殆盡和支付昂貴的存儲成本。信息可以通過多種途徑被壓縮。對于文本信息,你可以使用縮略詞來進行壓縮,諸如DNA、3D、TTYL、assoc、orig、gov等。搜索阿雷西博信息(Arecibomessage),你可以看到一個嘗試用很小的空間就可以傳輸人類文化和信息中關鍵部分的例子。你也許聽過這么一句話:一張照片勝過千言萬語。圖像確實能夠傳輸大量關于復雜的場景或情感內容的信息絡中、短信中使用圖片。而在你使用圖片的時候,通常需要經過一個上傳和下載信息的過程。根據圖像或視頻的質量和尺寸的不同,這個信息傳輸過程可能會花費你大量的時間和金錢。當軟件開發(fā)涉及到使用多媒體信息時(例如文本、圖片、視頻),開發(fā)者們通常都要考慮應該提供什么品質的信息給接收者,以使他們愿意下載或使用流媒體播放。圖像在屏幕上是以像素集合的形式顯示出來的。圖片的像素就是數據的比特位,為了降低存儲圖片所需的空間,人們可能會使用一種叫做位掩碼的技術。在圖3-5中,你應該可以看到兩幅相似的圖片,其中標識有兩幅照片分別占據的字節(jié)數,也就是存儲空間大小。事實上,這兩幅圖片完全相同,因為表示圖片的比特數并沒有任何的減少。28互動案例:/unit?lesson=13&unit=12互動鏈接:/edit/CSDataCompressionActivity位掩碼在圖片像素的比特位中運用了某種邏輯運算。這個邏輯運算將原始圖片的比特位與位掩碼按位進行“&(與)”操作。只有當源文件中的比特位和位掩碼對應的比特位均為1時,目標文件的對應比特值才是1。上述代碼中第26行(target[j]=source[j]&0xFFFFFFFF),試著將0xFFFFFFFF改為0XFF000000,點擊play來重新運行代碼來看看結果如何。注意:第一組FF表示的是像素不透明度的比特值,FF表示圖片完全不透明,這樣我們就可以看清楚生成的圖像(如果值是00,生成的圖像就是全透明的)。前綴0x表示這一串數字是1629背景知識一張圖片在屏幕上是通過一組像素在屏幕上顯示出來的。每像素包含了顏色的RGB(紅、綠、藍)值及不透明度值(圖片的透明度)的信息。以下是表示一個像素顏色信息的幾種方法:l使用二進制數值來表示顏色信息,每個二進制位(比特位)由0或1來表示。紅綠藍l使用十六進制數值來表示顏色信息,十進制中的數字0-15分別由0-F(1,2,3,4,5,6,7,8,9,A,B,C,D,E,F)來表示。紅綠藍通過改變代表顏色信息的那些數值,你可以讓顯示屏顯示出來任何你熟悉的顏色。當你試圖改變一個網頁的顏色的時候,你可以改變代表背景顏色的顏色數值或者代表文字顏色的數值。如果你想將一個網頁的背景顏色設置為白色,你很有可能會使用十六進制數值#FFFFFF,其將代表背景像素的紅,綠,藍三個顏色的數值設置成100%,這意味著屏幕上顯示為白色。反過來,如果你想將網頁上的文字設為黑色,你可以使用#000000,其將代表文字像素的紅,綠,藍三個顏色的數值設如果你對于如何將一個數字通過二進制或者十六進制表示出來,請查閱wikipedia網頁上關于位掩碼為0xFF000000時,紅綠藍三色的位掩碼比特位的值全部為0。位掩碼運算結束后,正如下表中所看到的一樣,該像素的每一個bit位的值都變?yōu)?,沒有留下任何的顏色信息。這是因為在二進制的&(與)操作中,只有當兩個操作數均為1時,結果才是1。因此,0&0=0,0&1=0,1&1=1。由此生成的圖像基本是空白的,只保留了少量字節(jié)以表明這是一張圖片。如下圖:如果你將位掩碼改回一開始的0xFFFFFFFF,運算后將不會改變像素的原始信息,而這就是現在,你已經看過了兩個極端的例子。當使用位掩碼0xFF000000的時候,沒有任何比特位能夠通過該位掩碼,這使得圖像會最大程度上減少存儲所需的空間,但這是以犧牲所有的信息和品質為代價的。當使用位掩碼0xFFFFFFFF的時候,所有的比特位都可以通過而所需的存儲空間沒通過改變位掩碼的值,你可以自己嘗試一些其他組合。通過不同的嘗試,你可以發(fā)現其中的一些模式,使得你可以在圖片質量和存儲空間做出最佳的取舍。如果你需要關于二進制和十六進制互相轉換的幫助,你可以搜索二進制轉換成十六進制,或者十六進制轉換成二進制?，F在你已經嘗試過不同的組合了,你在其中找到了什么模式了嗎?你有沒有找到一個位掩碼,使得既能保證圖片有足夠的質量同時也能大幅度減少所需的存儲空間?這里有一些組合你也許可以試一試。記錄下所需的存儲空間和圖片質量(尺度為1-10)。在你改變了比特位的值以后,按位掩碼的值(base16)1哪一個位掩碼的值你認為是最優(yōu)的?或者你有沒有發(fā)現其它你覺得更好的位掩碼值?也許對于不同的使用者來說,圖片的品質是一個非常主觀的概念。你在嘗試不同位掩碼的時候發(fā)現了什么模式了嗎?試著將其歸納概括出來,好讓你能夠向其他人解釋如何在維持一定圖片質量的同時,盡可能的減少所需要存儲的信息。如果你正在開發(fā)一款用來傳輸圖片的軟件,而不是開發(fā)一款圖像編輯軟件,你可能對圖片質量有著不同的需求。改變代碼第二行中的圖片URL地址以指向其它類型的圖片,你可以看到這一技術是否能被應用到高分辨率的圖像和黑白位圖中。理解這些一般原理能讓你更好的開發(fā)一個算法,在本活動中,你在存儲空間和圖片質量中尋找應用位掩碼的模式時使用了計算思維。這些模式幫助你確定你想使用的位掩碼值,并能夠幫助你創(chuàng)建一些普遍規(guī)則用來應用位掩碼以減少圖片的存儲空間。如果你對該課題感興趣,你可以搜索如下關鍵詞來獲得更進一步的信息:阿雷西博信息、不插電的計算機科學(CSUnplugged)也有一個關于文本內容壓縮的活動。當你在對學生進行教學的時候,可以使用該標準(或者參考附件二)來評測本活動。3-1-2人文學科:音樂喜愛音樂是人類的天性。在所有的文化中,各個年齡層的人都在制作和聆聽音樂,無論這些音音樂是各個文化的產物。那么我們是否能在大多數音樂中找到呢?通過應用計算思維,你可以創(chuàng)作一首歌曲并使用發(fā)現的模式和原理來改良它。請帶上你的耳機,打開你的麥克風。然后按下圖中的“Play”按鈕來創(chuàng)作一些音樂。互動鏈接:/edit/HumanitiesMusicActivity個音。世界上的許多文化都使用五聲音階來創(chuàng)作音樂。音階的設置在代碼的第24行,你可以通過更改這里的內容來使用任何你想使用的其它音階。例如,刪除notes=pentatonic并改寫為notes每當你改變了代碼的內容的時候,請確認都按下了“play”來運行代碼。因為代碼只是隨機挑選的音符,所以所生成的音樂并不像一個優(yōu)秀的作曲家所創(chuàng)作的樂曲那樣。然而,這里有些方法可以節(jié)拍高低長短不同的音符組成了音樂的旋律。當你以每秒四拍的節(jié)奏唱一首歌,你會發(fā)現這跟你以每秒一拍的節(jié)奏唱一首歌完全不同。音樂家們使用共同的語言來創(chuàng)作和討論音符的節(jié)拍,所以他們能夠互相理解別人的作品。其中的一些拍子為全音符、二分音符、四分音符、以及八分音符,你可作為音樂旋律的主要節(jié)奏,并在低音部使用了全音符用作音樂的節(jié)奏。舉例來說,你可以通過改變代碼27行中的melodyBeats=[quarter,eighth],在旋律中添加八分音符,或者用同樣的方法在28行中改變bassBeats。音程和和弦你也許會發(fā)現單個音符聽起來還不錯,但是當某些音符被一起演奏的時候,音樂的感覺就會被改變。兩個音符同時被演奏或依次演奏被稱為音程。而當三個或更多的音符被同時演奏的時候,我們稱之為和弦,這其中有許多種可行的配置。在上面的仿真中,每一個音階中的音符都有同樣的機階中的音符每次被選中加入樂曲中的概率。這些值都小于1,且所有的值相加后應為1。這里有一個概率配置biasForNotes=[0.5,0.0,0.0,0.5,0.0,0.0,0.0]。在該配置中,僅有第一個音符和第四個音符會被選中加入音樂中。試著用不同的概率配置并找出整完代碼后,按“Play”以運行代碼。和聲兩個是否一定強于一個?許多樂隊都有不止一個歌手,而且在一個管弦樂隊,很多的樂器會同時演奏相同或相似的音符。這種演奏方法被稱為和聲。和聲可以在合唱中添加豐富的聲音,或者當音符為互補的時候,在聲音中添加新奇的復雜的效果。通過在代碼第23行中添加pianos=[melody,harmony,bass],可以在代碼中添加另一個鋼琴來在你的音樂中引入和聲。在你調整過代碼之后,按下“play”來重新運行代碼。在添加和聲后,你是否還想改變諸如偏好或拍子等其它變量?除了上述提到的以外,你還有很多可行的調整或添加其它內容來使代碼生成更加出色的音樂。你可以盡情按自己的意愿來“玩”這些代碼。如果你遇到了什么麻煩,你可以通過刷新頁面或者嘗試再次運行更改后的代碼來解決。在上面的活動中,你將一首歌曲解構成不同的成分,并嘗試進行調整。在經過多次嘗試以后,你也許會發(fā)現某些設置比其它設置能生成更好的音樂。這些音樂制作的原理眾所周知,音樂創(chuàng)作者可以通過算法生成一段旋律或“hook”來讓歌曲更譯者注:hook是一種音樂的表現形式。詳情可百度“音樂hook”。如果你想了解更多關于音樂中的模式和定律的信息,你可以搜索如下關鍵詞:五度循環(huán),畢達哥拉斯的調諧,和弦,算法作曲,媒體計算。當你在對學生進行教學的時候,可以使用該標準(或者參考附件二)來評測本活動3-1-3數學:小海龜幾何在幾個星期的培訓以后,你已經成功讓寵物小海龜學會根據你的指令咬上筆,前進以及轉彎?，F在,看看你是否能教會小海龜畫出一些形狀圖案。試著向小海龜發(fā)出指令,讓它畫出來一個正方形。使用fd指令來讓小海龜前進一個指定的距離,使用rt指令來讓小海龜轉動一個指定的角度,如下例:fd100這條指令是讓小海龜在屏幕上前進100個像素,而rt更多的指令,點擊運行按鍵運行指令,看看會發(fā)生什么?；渔溄?/edit/MathTurtleGeometry為什么不給小海龜一個可以睡覺的家呢?繼續(xù)添加你的指令,看你是否可以讓你的小海龜畫出來一個如同下圖一樣的房子。如果你的小海龜第一次沒有做出來,那沒有什么,再來一次,繼續(xù)努力!現在你的小海龜已經訓練的很好了,只要你告訴它需要重復的步驟和次數,它就可以按部就班地執(zhí)行了。使用命令for[a..b]來重寫畫房子的指令,告訴小海龜循環(huán)開始和結束的數值以確定循環(huán)的次數。你可以使用上面學到的這些指令來設計一個算法,畫出任何你想要的常見的正多邊形。你可以把你的計算思維“灌輸”給小海龜,讓它能畫出任意邊數的正多邊形(如正五邊形,正十二邊形等等)。為了讓這個挑戰(zhàn)更可控,將它分解成一些比較小而容易解決的簡單任務是非常必要的。將一個復雜任務分解成一系列簡單小任務的過程就叫做任務分解。下面是一個畫一個正方形的指令:下面的步驟是完成這個任務的一個簡單版本:重復執(zhí)行下面的指令4遍:如果你已經寫出了一些代碼,可以將你的想法在PencilCode網站上用小海龜測試。做錯了不要怕,這是好事,因為你可以從錯誤中找到正確的方法。對比一下你設計的畫五邊形和正方形的步驟的異同。你是否有注意到多驟重復次數之間存在某種關聯或者模式?相等:代碼行數和多邊形邊數相等(4行代碼對應一個四邊形,5行代碼對應一個五邊形)兩倍:代碼行數大約是多邊形邊數的兩倍(8行代碼對應一個四邊形,10行代碼對應一個五邊形)三倍:代碼行數大約是多邊形邊數的三倍(12行代碼對應一個四邊形,15行代碼對應一個五邊形)這里是一個五邊形指令的例子四邊形使用了8行代碼,五邊形使用了10行代碼。點擊下一步返回,描述一下邊的個數和代兩倍:代碼行數大約是多邊形邊數的兩倍(8行代碼對應一個四邊形,10行代碼對應一個五邊形)對數據進行模式識別是計算思維另一個關鍵步驟,因為它提供了能揭示潛在原理、規(guī)律的關鍵信息。現在你已經知道步驟數量和角度之間存在關系了,這樣你就可以借助這個一般原理建立算法,解決類似的問題。只需要進行兩處修改,上面給小海龜建房子的代碼就可以實現代碼重用。這可以推廣到任意正在圖3-7-g的代碼中,改變sides=4。接下來,重寫for語句,將邊數從4改為變量“sides”,你也許已經發(fā)現轉動的角度是360/邊數,這是因為你的小海龜要轉一圈回到起點。所以把第三行從rt90變到360/sides,就可以根據邊的數量計算出角度的數值。40通過命令控制小海龜畫圖是經典的算法學習方式。學生需要設計畫圖的算法,才能創(chuàng)造出自己獨特的作品。事實上,Logo語言或小海龜有各種不同編程語言的版本。根據偏好或者需求,你可以繼續(xù)探索使用紙筆代碼(PencilCode)或Blockly游戲進行編程教學。CSunplugged中也有畫圖活動。如果你對用算法解決數學問題感興趣的話,可以試試歐拉計劃的問題(ProjectEulerproblems)。你可以嘗試使用if指令來標準化這些聯系。3-1-4科學:分類你有沒有聽過過一個游戲叫:20個問題?在這個游戲中,一個玩家在心中想著某個東西,例如一架飛機,另一名玩家可以通過詢問20個是非問題來猜測對方心中所想的東西。最近一項研究表明,地球上的不同種類的生命大約有八百萬到九百萬之間。你認為需要多少個問題可以讓你精確定位到任何一個心中所想的物種呢?5個嗎?這是一個巨大的挑戰(zhàn),但是我們可以用分解法解決這個問題,所謂分解法就是把一個大問題41如圖3-8-a,我在想以上其中一種生物,看看你能否通過只問3個問題來猜出我想的是什么?問:這個生物有腿嗎?答:是的,我想的這種生物有腿。于是剩下了:熊、鳥、老虎、公雞,如圖3-8-b。問:這種生物有皮毛嗎?答:是的。我想的這種生物有皮毛。于是剩下了熊和老虎,如圖3-8-c。42再問我另一個問題看看你能否猜出我想的是哪種生物,你還可以問一個問題。問:這種生物的身上有條紋嗎?答:是的,我想的這種生物身上有條紋。于是就剩下了老虎,如圖3-8-d。只用了3個問題,你能從8個選項中猜出我在想的是老虎。既然你已經看見了這個過程,你就可以運用這一概念,根據元素的屬性指出元素周期表的元素,正如門捷列夫在發(fā)明元素周期表時所做的一樣。除了將這些元素按照原子質量排列外,(質子直到近50年后才被發(fā)現),你可以看到他還在計算思維不總是和電腦或是否運用了技術有關。它是一種幾百年來一直為科學家們所使用的過程。在傳統(tǒng)科學方法各個環(huán)節(jié)中,計算思維最適合在實驗及分析階段使用。在前面提到的兩個例子中,你接受了一項艱巨的任務——猜出了我在想的生物或是元素是什么,并且通過問只能回答是或否的問題完成了任務。計算思維是從分解開始的,在這一步中,你把大問題分解為一個個的小問題。在第一項活動中,你僅問了3個問題就指出了我想的是8種中的哪43如果讓你猜出我在16種生物中想的是哪一種,每問一個問題排除一般選項,你需要問幾個問題呢?不妨來畫張表看一下。如果每個問題能排除一半選項:所以對于16個選項來說,每個問題能排除一半選項的話,我們只需要4個問題,就能得出答案。所以對于32中生物我們需要問多少問題呢?在多項實驗中查看數據時,識別是否存在模式、存在什么樣的模式對找出潛在的原因或原理是假設地球上有8億種生物。每問一個問題排除一半選項,你需要多少個問題能猜出我想的是哪種生物呢?這將需要33個問題,想要從上億種可能性準確的找出答案,這個數字看起來也許有點小。20個問題的游戲可以從超過100萬種可能性中猜出答案,這對于大多數的物體來說都應該是足夠現在,你可能搞清楚了,你需要提問的次數可以通過計算所有可能性的log2對數得到,或者通過計算2的幾次方接近或等于可能性總個數:2=16,2=32...2≈8.5億。這種從實驗中總結出規(guī)律,并上升為一種普遍規(guī)律、公式或者定律的方法,就是通常所說的在此次學習中,通過使用計算思維的步驟,你學到了理論上你需要多少問題來對地球上的生物加以分類。計算思維不僅讓我們得到了答案,而且明白了內在的,可以遷移到其他新問題中使用的如果你對此想有更多了解,可以搜索以下信息:信息理論及決策樹?？珊箤W院有關于信息理論的視頻,不插電的計算機(CSUnplugged)有關于檢索和分類算法的活動,也有這次活動的數據443-2課程反思下面是本章所討論的、可以從中找到計算思維過程的科的內容,你可以在任何其它學科中找到相關的活動。數據壓縮●模式識別-應用不同的位掩碼,以了解不同的位掩碼對圖片所需存儲空間和圖片質量的關●抽象化-使用發(fā)現的模式來決定使用合適的位掩碼,既能夠壓縮圖片體積也能夠保持合適●算法開發(fā)-盡管在本章節(jié)中你并沒有開發(fā)任何算法,你也許已經認識到位掩碼的不同屬性音樂●分解-觀察歌曲的不同部分并將其劃分為不同的組成,例如:節(jié)拍,音符,以及和聲,然●模式識別-調整每個變量,諸如音符的長度以及音階中音符的頻率,來找到一個你最喜歡●算法開發(fā)-盡管在本章節(jié)中你并沒有設計任何算法,使用已經完成的代碼來調整設置,使用另一種音階,以及添加額外的鋼琴來得更加輕松以使你能夠進行探索。你也許有一些關于音樂其它屬性的不同想法,并嘗試將它們應用到以后對音樂的改進之中。小海龜幾何●分解-將一個任務轉換為一系列步伐和轉向,例如畫一個正方形?！癯橄蠡?使用轉向角度和步伐的數目中的模式來深入了解步伐數目,角度和多邊形邊的數45●算法開發(fā)-設計一個算法用來繪制任意形狀的多邊形。我們有很如,當計算小海龜的每一步應該多長的時候將邊數考慮到。分類●分解-觀察生物體的不同的分類方式。例如:生物體是水生生物或者是有翅膀能在天上●抽象化-測定使用該方法的情況下需要多長時間來進行分類,有助于你了解對所有已知生●算法開發(fā)-在本章節(jié)中你并沒有開發(fā)出一個算法,但是你也許已經想到了如何更有效的對現在你已經大致體驗過計算思維的過程了。在你的課程表中,是否還有其它課題能夠從學生應用計算思維中獲得幫助呢?你可以在課程社區(qū)中分享你的觀點。464-1概述在本節(jié)中,你可以嘗試體驗一些稍作修改就能應用于課堂教學上的活動。這些活動會涉及到算法開發(fā),以及編輯一段已有的代碼或增添新的代碼,但是并不要求提前對編程有所了解。這些活動中都涉及到計算思維過程,其重點在于算法開發(fā)。請點擊下面的活動的鏈接來開始體驗吧。你也可以隨意嘗試其他領域的活動。像你對學生所期待的那樣,探索、試驗、游戲和享受活動吧!474-1-1計算機科學:漢諾塔傳說在一個房間里有三根柱子(塔)。在最左邊的塔上有64個金制的圓盤擺成一垛,從上到下按照從小到大進行排列(圖4-5中是一個只有3個圓盤的簡化版本)。負責看管并移動圓盤的人被告知,當所有的圓盤從一個柱子移到另一個柱子上的時候,世界末日就會降臨。移動圓盤時要遵守的規(guī)則:1.一次只能移動一個圓盤,并只能從一根柱子的頂端移到另一根柱子的頂端。2.較大的圓盤必須位于較小的圓盤下方。(換句話說,塔上的圓盤永遠保持金字塔型)如果一個人每次移動圓盤都要花1秒的時間,你認為他要花多久才能解決這個問題?圖4-53個圓盤的漢諾塔你可以直接嘗試使用64個圓盤來解決這個問題,你也可以嘗試將這個復雜問題簡化成一個比較簡單的任務,看看是否可以在指定圓盤的數量的情況下,使用最少的移動步驟來解決這個問題,或者,你也可以試著猜猜看。在計算思維里面,這個過程叫做“任務分解”。在上面的漢諾塔的例子中,在左邊的塔上有3個圓盤,試試看,如何將這3個圓盤移到中間或同樣,在嘗試解決這個問題的時候,必須遵守下面的規(guī)則:1.每次只能移動一個圓盤,而且只能從最上面的圓盤拿起并移動到另外一個塔的上面2.任何時候,任何一個塔上面的圓盤不能比它下面的圓盤大。在你解決了或者嘗試解決了下面的問題以后,試試看如果有4個圓盤,你該怎么辦?根據你前面的嘗試,對于4個圓盤的問題,估計你最少需要移動多少步才能解決這個問題?48圖4-64個圓盤漢諾塔的操作界面當你將圓盤在不同塔之間移動的時候,你有沒有發(fā)現一些規(guī)律,即便你可能還說不清楚具體規(guī)律是什么(有或沒有)。最少的移動步驟是:基于這些實例的解決方案,你認為它能解決漢諾塔問題中的5個圓盤的移動嗎?n漢諾塔這個問題的最少移動次數遵守這個規(guī)律:2?1。這里n是圓盤的數目。比方說,如果有5個圓盤,那么最少需要的移動次數就是25?1=31。下面是一個有3個圓盤的漢諾塔難題的移動順序:1.塔A,塔C2.塔A,塔B3.塔C,塔B4.塔A,塔C5.塔B,塔A6.塔B,塔C7.塔A,塔C根據上面移動的列表,在第幾次移動的時候開始重復?答案是在第四行移動的時候開始重復。移動三個圓盤的例子可以看出:一個圓盤在第四步在A和C塔間移動,并在第七步開始重通過觀察移動的規(guī)律,我們發(fā)現:1.在A和C塔間的移動是第一步,因此應該被放在移動的第一步。2.由于A和C塔間的移動在第四步和第七步重復,你應該需要重復這些步驟直到問題解決。493.A塔和C塔的移動是第四步,因此,必定在第四步到第七步之間還得有2個移動。根據上面的這些規(guī)律,你可以建立你的算法了。解決一個有3個圓盤的算法是:根據上面3個圓盤的漢諾塔難題的移動順序,塔A和塔C的步驟重復之后,下一步是哪兩個塔?(是塔A塔B,塔A塔C還是塔B塔C?)是的,這就是模式中需要重復的步驟,你可以把它添加為算法的第二步。解決3個圓盤的漢諾塔的算法如下:太好了,我們的算法馬上就要做好了。解決一個有3個圓盤的例子是:1.將圓盤在A和C塔移動7.將圓盤在A和C塔移動你能找出最終的模式并寫成算法嗎?在上面的例子當中,最后重復的塔是什么?(是塔A到塔B,塔A到塔C還是塔B到塔C?)恭喜你,你已經發(fā)現了這個問題的規(guī)律并將它抽象成為一個算法。解決一個有3個圓盤的算法是:3.在塔C和塔B之間移動圓盤,重復這些過程直到問題解決事實證明,只要圓盤的數目是奇數(3,7,13),就可以用上面的辦法來解決這個問題。將這兩個算法結合,只要有足夠的時間就可以解決任何版本的漢諾塔問題。現在我們再重新看一下原始的問題:如果某人解決一個有64個圓盤的漢諾塔的問題,并且他每秒鐘移動一個圓盤,當他解決這個問題的時候,世界將會毀滅。你覺得這個事情會多久發(fā)生?根據你前面發(fā)現的規(guī)律,解決這個問題需要多長時間?(1天?100年?或者幾百萬年?)nn64推算解決有n個圓盤的漢諾塔需要的時間,如果有64個圓盤,需要的時間是2?1,這個數字是一個超級大的數字,如果每一秒移動一個圓盤,解決這個問題需要的時間甚至超過了宇宙的年齡,現在,你大可放心了!這個例子很有名不僅僅是因為它的算法和趣味,其重要性在于它是一個遞歸的絕佳例子。遞歸算法是計算機科學專門用來描述一個算法本身的問題,所以接近作為一系列較小的問題來解決。你不愿意看看你是如何通過遞歸運算來解決漢諾塔這個問題的?如果你愿意在這個方面深入鉆研的話,后面將會有更加讓人興奮的發(fā)現。你已經有了一個解決漢諾塔的算法?，F在你可以將計算思維再次使在進入這個漢諾塔問題之前,再看一下使用乘法運算進行遞歸運算的一個例子。當你把乘法運算當作一個重復的加法運算的時候,你就可以構造出一個遞歸的算法。任務:將兩個數a和b相乘1.規(guī)則1:如果b等于1,那么結果就是a2.規(guī)則2:將a和b-1兩個數相乘,然后將乘積加到a例子:5*4這看上去挺復雜,一個遞歸運算有的時候看上去更簡潔。例如當你使用某些算法,如排序數字在前面我們重復提到的漢諾塔算法步驟中,有些步驟被不停的重復直到問題得到解答。然而,除了這個辦法,還有另外一個更通用的辦法,那就是不斷將比較小的圓盤移動到其它塔上直到你可因此,使用遞歸運算解決這個漢諾塔的算法可以被描述為:任務:將所有的圓盤從A塔移動到C塔2.將最后一個圓盤從A塔移動到C塔。如果你仔細觀察的話,你就會發(fā)現,你一個移動步驟其實都需要一組更小的算法步驟來實現。如果你對于這個話題還有進一步的興趣,你可以搜索排序算法,遞歸,漢諾塔游戲來進一步了4-1-2人文學科:聊天機器人在本活動中,你會通過應用計算思維過程來創(chuàng)建一個聊天機器人程序。你也許想知道什么是聊天機器人?一個名叫阿蘭圖靈的數學家曾經預測過,未來某一天計算機這個測試被稱為圖靈測試。這是一個十分直白的測試:如果一臺計算機能夠和人類進行交流,而人類無法分辨出跟他進行交流的是一個人還是計算機的話,該電腦就被認為通過了圖靈測試而擁該聊天機器人是基于世界上第一個計算機程序員阿達·洛芙萊斯(她出生于1815年,她的父親是一個詩人,她的母親單獨撫養(yǎng)阿達長大,并把她培養(yǎng)成了一名數學家和科學家)。阿達編寫了第在1843年的時候,27歲的阿達在分析機上翻譯了一篇文章,并在其中添加了她自己的筆記。在這其中包含了一段被認為是世界上第一個計算機程序的內容。程序是一連串指令的集合,這些指令會被機器所執(zhí)行。阿達曾經預測過像這樣的機器可以被用來創(chuàng)作音樂,畫圖,以及其它不僅僅是用來做計算的功能。她在計算機真正實現這些功能的一個世紀前就有了這樣和科學相結合,認為想象力和直覺對于數學和科學有著非常重大的作用。當阿達寫下這篇著名的關于分析機時,她已經和洛芙萊斯伯爵結婚并有了三個年幼的孩子。令人悲傷的是,阿達的一生都被疾病所困擾,最終年僅三十六歲的她在1852年死于子宮癌。在被阿達了不起的事跡所啟迪之后,你可以開始創(chuàng)造一個會像阿達本人一樣回答問題的聊天機如圖4-6-b是阿達的初始聊天機器人。當你運行這個代碼的時候,一個用來輸入你的問題的文本框會出現。目前為止,“她”可以回答的問題只有她的名字和她的出生日期。如果你輸入問題“你是誰?(Whoareyou?”或者“你生日是什么時候?(Whenwereyouborn?)”你就可以看得到答案。圖4-6-b阿達的初始聊天機器人互動鏈接:/edit/HumanitiesChatbot假設你是一個對阿達(Ada)一無所知的人,你會問她什么問題?如果你必須以阿達的身份回答這些問題,她會知道哪些事情以及她會如何回答這些問題?你可以根據前面提供的信息來設計答案,或者自己做一些相關研究。模仿一個人類是一項十分困難的任務。首先,你可以將其分解成若干個容易處理的任務。你認為人們會問阿達哪些問題?這個聊天機器人使用了邏輯語句If和Else。下面是算法的具體步驟:2.算法檢查用戶名是否匹配,如果(If)用戶的回答和數據庫匹配,就(Then)給出一個答復3.否則(Else),計算機就給出“我不理解你說的是什么”的答復。條件語句If和Else非常有用,基本上每一個軟件的重要功能都會使用到這個語句。利用現有的代碼作為一個指導,在第7行添加新的If/Else語句,當你問“你是哪里出生的時候”,阿達聊天機器人可以回答“我是在英國倫敦出生的”。當你根據已經有的例子添加了一個新的問題以后,點擊播放按鍵,重新運行代碼。除了邏輯語句If以外,你還可以添加布爾值邏輯量讓聊天機器人可以測試在某個單一條件下,某兩件事是否真實的。聊天機器人可以回答諸如“你是誰”這樣的問題,但是如果你想加入“你叫什么名字”這樣的問題的時候,你應當可以針對“什么”加入一個If語句,但是最好算法可以自動搜尋“名不同于通過在算法中添加一個同樣答復的算法,代碼應該可以自動檢查問題是否包含諸如“誰”編程語言是一門像其它語言一樣,有一定語法規(guī)則。事實上由于計算機不能接受自然語言測試,因此你在使用編程語言的時候必須很小心你的輸入代碼必須滿足那些規(guī)則。盡管如果一封郵件有一些小的語法或者拼寫錯誤,你還可以理解這封郵件。但是計算機就不是這樣了,它僅僅會執(zhí)行你讓它做的,哪怕它是錯誤的。使用不正確的語法和拼寫錯誤會造成計算機錯誤?；蛟S未來的某一天計算機可以能夠覺察到你的一些細小的失誤并認識到你真實的意圖,但是在那天來臨以前,我們必須按照規(guī)則和算法編寫我們的程序,并檢查程序中可能的錯誤,以避免失誤。你可能會繼續(xù)讓你的聊天機器人在許多方面繼續(xù)重復回答問題。但問題,你的程序也會變得越來越長。你可以上網查看其它聊天機器人的例子,你會發(fā)現其中絕大多數都和我們的阿達機器人有著相類似的邏輯基礎。他們都會檢查特定的內容或者模式,然后應用對應的算法。如圖4-6-c是一個聊天機器人,它能在遇到它無法回答的問題時進行學習,并在內存中記住問題和對應的答案。圖4-6-c一個聊天機器人的例子試著運行這段代碼,然后回答一些問題。在你教會機器人一個新問題之后,它應該就能回答這個問題了(前提是你得用同樣的方式問這個問題)。這種通過訓練編寫算法而非提前列出每種可能性的過程,便是機器學習的一個范例。谷歌正利用機器學習來更好地理解模糊檢索和網絡上的很多其它實例中。然而,算法學習和有機體(比如人類)學習之間的差距仍然存在。為何不反思一下這些差距,同時想想看作為一個有生命和智慧的存在意味著什么。如果有學生參與其中,還有很多標準可供設置。4-1-3數學:計算器科技時常可以迅速而高效的為你提供許多問題的答案,諸如:為什么天空是藍色的?我朋友的生日是什么時候?π的值是多少?僅僅可以用來回答諸如天為什么是藍色的或者畫出x2-1的圖像使用計算器是一回事,但是想象一下你也許可以制作一個你自己的計算器!你認為你的基礎計算器應該擁有哪些功能?好了,我們先從加法開始。你準備如何向一個兒童解釋加法的流程?在數學中,和計算機科學一樣,一個函數表示的是當將一組變量輸入到一組公式中的時候,可以對應的一組輸出。如F(x)=x2,F(3)=9,F(10)=100。對于計算器來說,你可以創(chuàng)建一個叫add的函數,這個函數可以輸入兩個輸入值,并且一個輸出值用來得到這兩個輸入值的和。如:add(3,5)→8在Python編程代碼中加法算法的例子如下,嘗試使用不同的輸入數字輸入到函數中,看看代碼運行以后,結果是什么。圖4-7-a加法函數的例子如圖4-7-a是一個加法函數的例子?，F在,每當語句add(a,b)被使用的時候,你應當可以看到結果是a+b。盡管在計算的時候你使用的是+這個運算符號,但是在函數中這樣表示(a,b)是可以接受的。那么乘法是怎么通過函數實現的呢?你可以使用一個叫multiply(a,b)的函數,這個函數將兩個輸入值相乘并將結果返回出來。想想看,你是否可以使用已知的加法函數來實現一個乘法的功能?想想看,你準備如何解決上述問題,請繼續(xù)往下看。對于計算器來說,創(chuàng)建一個乘法函數的方法是使用遞歸。這個概念在數學和計算機科學中很受關注。遞歸是一個和它自己相關的算法,遞歸可以讓一個復雜的問題分解成一個個小的容易問題并的結果,公式如下:F(n)=Fn?2+Fn?1。舉例來說,最開始的兩個數1,1的和就是2(第三個數),而第二個數1和第三個數2相加就是第三個數3。以此類推。這個規(guī)律當你需要開發(fā)一個和下面是一組使用add(加)的功能來表現乘法規(guī)律的例子。任務:將兩個數a和b相乘。規(guī)則1:如果b等于1,那么答案是a。規(guī)則2:將a和(b–1)相乘,并將結果輸出給a。例子:5*4的乘法例子。在遞歸函數中,需要一個“初始狀態(tài)”,這個初始狀態(tài)是用來讓函數停止運行的。規(guī)則1就是一個初始狀態(tài)。因為乘法單位是1,當b=1的時候,這個函數就應該停下來。在前面的例子中,你重寫了指令,并將這些指令放入函數中。