新編計算機導論 課件全套 張瑾 第1-9章 計算機與計算-IT職業(yè)道德

計算機與計算新編計算機導論計算機概述01計算理論03計算機的產(chǎn)生與發(fā)展02本章CAPACITY內(nèi)容23計算的概念方法1：研究復雜運算的簡化方法；方法2：設計一些簡單規(guī)則，讓機械來完成計算，即考慮能否讓“機械”代替人按照“規(guī)則”自動計算?！坝嬎恪笔侵浮皵?shù)據(jù)”在“運算符”操作下，基于“規(guī)則”進行的數(shù)據(jù)變換。1.計算機概述“規(guī)則”可以學習與掌握，應用“規(guī)則”進行計算則可能超出人的計算能力，從而無法得到結(jié)果。怎么辦？？狹義的計算是指“數(shù)”的狀態(tài)變換，廣義的計算可以是自然界一切具體的狀態(tài)轉(zhuǎn)換計算本質(zhì)上是對輸入數(shù)據(jù)進行處理，得到一定輸出結(jié)果的過程。4計算的基礎ⅰ.從最右邊的數(shù)字開始相加；ⅱ.如果需要則進1；ⅲ.依次對左邊余下的各位數(shù)字重復上述過程。“計算”是基于算法（algorithm）的，所謂算法就是為解決一個問題而采取的方法和步驟。1.計算機概述比如，最基本的用紙和筆進行的加法也需要算法，其步驟包括：5計算與自動計算一般要解決下述4個問題數(shù)據(jù)的表示1.計算機概述數(shù)據(jù)的存儲與自動存儲計算規(guī)則的表示計算規(guī)則的執(zhí)行及自動執(zhí)行上述問題促進了機械技術(shù)與電子技術(shù)的結(jié)合，并導致了現(xiàn)代計算機的產(chǎn)生6什么是計算機計算機（Computer）是一種能夠按照事先存儲的程序，自動、高速地進行大量數(shù)值計算和各種信息處理的現(xiàn)代化智能電子設備。由硬件和軟件所組成，兩者不可分割，沒有安裝任何軟件的計算機稱為裸機。1.計算機概述7計算機的特點最大特點是可以不斷重復地執(zhí)行大量相似動作從而獲得結(jié)果，通過計算可以使只會簡單操作的計算機能夠完成復雜的任務1.計算機概述不同于其他機器，計算機具有存儲功能，無需人工干預即可根據(jù)事先存儲的程序自動完成各種計算計算機的各種復雜功能都源于“計算”的威力8計算機算法一個能夠被計算機處理的，有限長的操作序列1.計算機概述計算機算法可分為兩大類數(shù)值運算算法數(shù)值運算的目的是求數(shù)值解非數(shù)值運算算法應用范圍最為廣泛的算法計算機算法可分為幾類？9思考若能明確乘法的本質(zhì)就是若干相同數(shù)據(jù)的重復加法運算過程，那么問題就不難解決，關(guān)鍵是編寫合適的指令序列讓她機械地執(zhí)行在紙上寫0，記住結(jié)果；在所記結(jié)果上加第1個a，記住新結(jié)果；在所記結(jié)果上加第2個a，記住新結(jié)果；依此類推，直至在所記結(jié)果上加第b個a，記住新結(jié)果，即為a×b的積琪琪是一個小學一年級學生，她剛剛學習了加法運算，如果給她一個乘法運算任務，如計算a×b，她能夠完成嗎？1.計算機概述人類的思維是用有限的步驟去解決問題，講究優(yōu)化與簡潔計算機則可以進行大量的、重復地精確運算，并樂此不疲計算機通過重復執(zhí)行大量簡單動作即可完成復雜運算新編計算機導論謝謝觀看10計算機與計算新編計算機導論計算機的產(chǎn)生與發(fā)展計算機史前史01計算機的產(chǎn)生與發(fā)展02本節(jié)CAPACITY內(nèi)容1213文字發(fā)明之前的初期計算工具1.計算機史前史結(jié)繩為記，事大，大結(jié)其繩；事小，小結(jié)其繩，之多少，隨物眾寡。--東漢鄭玄《周易注》14手動式計算工具1.計算機史前史特點：手動輔助數(shù)字計算過程，計算過程/方法（即算法）需要使用者來記錄并操作執(zhí)行算籌算籌的擺法算盤納皮爾計算器計算尺15機械式計算工具1.計算機史前史計算鐘——1623年，德國數(shù)學家謝克哈特發(fā)明第一臺機械式計算設備，計算鐘上部附加一套納皮爾算籌能進行6位加減乘除運算，利用一組互相咬合的齒輪的轉(zhuǎn)動來完成計算，鈴聲輸出答案齒輪上有10根輻條分別表示一個數(shù)字，每當一個齒輪轉(zhuǎn)過一周時，其左邊齒輪則移動一格，并刻痕表示進一位加法器——1642年，帕斯卡發(fā)明齒輪式能實現(xiàn)加減法運算的加法器；用齒輪表示和存儲十進制各數(shù)位上的數(shù)字，低位齒輪每轉(zhuǎn)動10圈，高位齒輪轉(zhuǎn)動一圈機器可自動執(zhí)行一些運算規(guī)則，“數(shù)”在計算過程中自動存儲乘法器——1673年萊布尼茨對加法器進行改進，制造了一臺能夠進行加減乘除四則運算的機械式計算器，實現(xiàn)了計算規(guī)則的自動、連續(xù)、重復執(zhí)行，開辟了自動計算的道路；進行乘法運算時采用進位加方法，該方法后來演化為二進制算術(shù)運算規(guī)則，被現(xiàn)代計算機采用這些機器都缺乏程序控制的功能16雅各織布機1804年，法國機械師約瑟夫·雅各發(fā)明了可編程織布機雅各織布機雖然不是計算工具，但是它第一次使用了穿孔卡片這種輸入方式通過讀取穿孔卡片上的編碼信息來自動控制織布機的編織圖案，引起了法國紡織工業(yè)革命1.計算機史前史用孔洞位置或其組合表示信息（紙帶上穿孔為1，無孔為0）17差分機由多個直立銅柱組成，每個銅柱垂直裝配有6個齒輪，齒輪對應的字輪上有0~9，不同的字輪代表十進制的不同位，通過齒輪的彼此咬合傳動完成計算。1822年，英國劍橋大學著名數(shù)學家查爾斯·巴貝奇受編織機啟發(fā)，耗時10年，研制成功第一臺差分機1.計算機史前史可用于計算數(shù)的平方、立方、對數(shù)和三角函數(shù)，能進行8位數(shù)運算，計算精度達6位小數(shù)創(chuàng)新之處有三組字輪作為寄存器（Register）來存放計算中涉及的數(shù)據(jù)可以按預先安排好的計算步驟進行一連串的計算，可以看作是“程序自動控制”思想的萌芽18分析機輸入裝置——穿孔卡片輸入數(shù)據(jù)齒輪式的存儲裝置（“倉庫”）——能存儲1000個50位十進制數(shù)的容量資料處理裝置“工廠”——完成加減乘除，還能根據(jù)運算符號改變計算進程控制裝置——使用指令進行控制，指令通過穿孔卡片順序輸入處理裝置輸出裝置——穿孔卡片或者打印機輸出1833年，巴貝奇設計出分析機模型，模型包含現(xiàn)代計算機所具有的5個基本組成部分1.計算機史前史分析機同樣是以蒸汽引擎驅(qū)動，吸收提花織布機的優(yōu)點，使用打孔卡輸入資料，其中的重要創(chuàng)新是用齒輪模擬算盤的算珠巴貝奇在1835年提到，分析機是一部一般用途的可編程化計算機，其思想超越了當時的科學水平，分析機沒有完成。但在巴貝奇的設計中，它擁有可擴展的內(nèi)存、一個中央處理器、微指令、并使用穿孔卡來編程19機電式計算工具1.計算機史前史圖1Z3計算機（1941年）圖3哈佛大學MarkⅠ（1944年）圖2ABC模型機（1940年）圖4COLOSSUS機（1943年）20第一臺計算機ENIAC運算速度為每秒5000次加法，比已有計算工具快1000倍，當時需要100多名工程師花費1年才能解決的計算問題，它只需要2個小時就能給出答案，一度被譽為“比炮彈還要快的計算機”世界上第一臺電子計算機ENIAC（ElectronicNumericalIntegratorAndCalculator，電子數(shù)字積分儀和計算機）于1946年在美國研制成功ENIAC奠定了電子計算機的發(fā)展基礎，開辟了一個計算機科學技術(shù)的新紀元。有人將其稱為人類第三次產(chǎn)業(yè)革命開始的標志2.計算機的產(chǎn)生與發(fā)展耗電量驚人，功率為150千瓦存儲容量小，至多只能存20個字長為10位的十進制數(shù)與后來的存儲程序型的計算機不同，它的程序是外插型的，計算某題目前需要先由人工接通數(shù)條線路，使用不方便使用的仍然是十進制，基本結(jié)構(gòu)和機電式計算機沒有什么區(qū)別21馮·諾依曼計算機1944年，美籍匈牙利數(shù)學家馮?諾依曼參加的原子彈研制項目受阻，主要因為遇到了極為困難的計算問題，在得知ENIAC的研制計劃后，馮?諾依曼加入了研發(fā)工作。經(jīng)過對ENIAC不足之處的認真分析和討論，馮?諾依曼提出了重大的改進理論，即EDVAC（ElectronicDiscreteVariableAutomaticComputer，意為“離散變量自動電子計算機”）方案2.計算機的產(chǎn)生與發(fā)展計算機的基本結(jié)構(gòu)應由五大部件組成：運算器、控制器、存儲器、輸入設備和輸出設備，并描述了這五部分的職能和相互關(guān)系計算機應采用二進制形式表示數(shù)據(jù)和指令提出了“二進制”與“存儲程序”的設計思想1945年6月，馮?諾依曼發(fā)表計算機史上著名的“101頁報告”，報告對EDVAC計劃進行了描述，馮諾依曼思想的核心要點如下22馮·諾依曼計算機馮·諾依曼思想標志著自動運算的實現(xiàn)和電子計算機的成熟，該思想已成為電子計算機設計的基本原則“存儲程序”概念被譽為“計算機發(fā)展史上的一個里程碑”，它確定了現(xiàn)代電子計算機硬件的基本結(jié)構(gòu)，奠定了現(xiàn)代計算機的基礎2.計算機的產(chǎn)生與發(fā)展計算機科學界把采用0、1符號編碼方法和存儲程序方法設計的計算機稱為馮·諾依曼計算機世界上第一臺存儲程序計算機是劍橋大學研制的電子延遲存儲自動計算機EDSAC（ElectronicDelayStorageAutomaticCalculator），于1949年投入運行23計算機的發(fā)展階段（按照采用的電子器件劃分）第一代計算機（1946——1957年）第二代計算機（1958——1964年）2.計算機的產(chǎn)生與發(fā)展第三代計算機（1965——1970年）第四代計算機（1971s—）新一代計算機電子管計算機，主要邏輯元件采用電子管晶體管計算機，主要邏輯元件采用晶體管中/小規(guī)模集成電路計算機大規(guī)模/超大規(guī)模集成電路計算機1980s年代提出，也稱第五代計算機，是各種未來型計算機的總稱，將改變傳統(tǒng)馮·諾依曼結(jié)構(gòu)，具有利用已有知識進行推理判斷、聯(lián)想和學習功能的新型智能化計算機系統(tǒng)新編計算機導論謝謝觀看24計算機與計算新編計算機導論計算理論可計算性01計算復雜性02本節(jié)CAPACITY內(nèi)容2627可計算性需要計算的問題多種多樣，什么樣的問題才是可計算的？這是關(guān)系到計算機能做什么、不能做什么的根本問題。3.計算理論可計算性理論（ComputabilityTheory）是研究計算的一般性質(zhì)的數(shù)學理論，其中心課題就是將算法這一概念精確化，建立計算的數(shù)學模型，研究哪些是可計算的，哪些是不可計算的。下面將列舉若干計算學科的典型實例對上述問題進行說明由于計算與算法相連，因此也將可計算性理論稱為算法理論。可計算問題是指存在算法可解的問題，不可計算問題則是不存在算法可解的問題。通俗來說，若存在一個機械的過程，對給定的某個輸入，若能在有限步內(nèi)給出答案，則該問題就是可計算的。28排序問題目前已知有幾十種排序算法，如最簡單的插入排序和冒泡排序?qū)臻g要求不高，但時間效率低，其時間復雜度為O(n2)3.計算理論歸并排序、希爾排序等對空間要求高，但時間效率穩(wěn)定在較高水平，其時間復雜度為O(nlog2n)排序問題是計算科學中一個十分重要的問題，需結(jié)合具體問題選擇合適的排序算法，但無論何種算法，排序問題都是可以計算的，并且計算代價不高29漢諾塔問題在印度北部的世界中心貝拿勒絲的圣廟里，一個黃銅板上插著三根寶石針A、B、C，印度教主神梵天在創(chuàng)造世界時，將其中一根針由下到上穿好了由大至小排列的64片金片。不分白晝總有一個僧侶按照下述法則移動金片：一次只移動一片，必須保證小片在大片上面。3.計算理論僧侶們預言，當所有的金片都從梵天穿好的那根針上移動到另一根針上時，世界就將在一聲霹靂中消失，梵塔、廟宇和眾生都將同歸于盡！漢諾塔問題求解使用遞歸算法，假設有n片，移動次數(shù)是f(n)。顯然f(1)=1,f(2)=?,f(3)=？f(k+1)=2*f(k)+1可以證明f(n)=2n-1當n=64時，f(64)=18446744073709551615，若每秒移動一次，共需要多久？一年31536000秒，則需584942417335年，即5849億年以上，太陽系的預期壽命不過數(shù)百億年此問題理論上可計算，實際上不可行，屬于算法的時間復雜度問題3731國王的婚姻從前，有個酷愛數(shù)學的年輕國王向鄰國一位美麗聰明的公主求婚，公主給國王出了一道題：求出48770428433377171的一個真因子。國王若在一天內(nèi)求出，公主便會接受他的求婚。3.計算理論國王回去后立刻開始逐個數(shù)進行計算，從早到晚，共算了3萬多個數(shù)，仍未求出結(jié)果。國王向公主求情，公主告訴答案：223092827是一個真因子，公主說：“我再給你一次機會，如果還求不出，將來你只好做我的證婚人了?！眹鯌撛趺崔k？32國王的婚姻問題求解國王請教國內(nèi)時任宰相的大數(shù)學家：數(shù)學家在思考分析后發(fā)現(xiàn)，該數(shù)為17位，其最小的一個真因子不會超過9位，然后給國王出了一個主意。3.計算理論按自然數(shù)順序給全國百姓每人編一個號發(fā)下去，公主給出題目后立即通報全國，讓每個百姓用自己的編號去驗證，除盡則立即上報并賞金萬兩。國王最后求婚成功什么主意？？33國王的婚姻故事帶來的啟示故事就是一個求大數(shù)真因子的問題，由于數(shù)字很大，國王第一次采用的是一種順序的求解算法，其復雜性表現(xiàn)在時間復雜性方面，時間消耗非常大；3.計算理論宰相采用的是并行的方法，國王通過將可能的數(shù)字分發(fā)給百姓，才能在有限的時間內(nèi)求取結(jié)果，復雜性體現(xiàn)在空間資源方面；雖然宰相的方法增加了空間復雜度，但大大降低了時間的消耗，這就是非常典型的分治法，也就是將復雜的問題分而治之，這也是我們面臨很多復雜問題時經(jīng)常會采用的解決方法，也可將該方法作為并行的思想看待，而這種思想在計算機中的應用比比皆是，如現(xiàn)在CPU的發(fā)展。34計算復雜性在實際應用中，對于某個特定問題，需考慮計算的難度有多大、計算所需付出的代價如何？3.計算理論計算復雜性理論將多項式時間復雜性作為易解問題（P類問題）與難解問題（NP類問題）的分界線。35計算復雜性之P類問題P（polynominal，多項式）類問題是指在多項式時間內(nèi)可解的問題類，此類問題為易解問題，如排序問題3.計算理論事實上，典型的多項式（如n3）與典型的指數(shù)（如2n）在增長率上存在巨大的差異比如，當n=1000時，n3是10億，雖然是大數(shù)，但還可以處理，而2n則是一個比宇宙中的原子數(shù)還大得多的數(shù)因此，多項式時間的算法是高效的，指數(shù)時間的算法是低效的36計算復雜性之NP類問題NP（

nondeterministic

polynominal，非確定性多項式）類問題是指在多項式時間內(nèi)可驗證的問題類，或者說可以在多項式時間內(nèi)猜出一個解的問題類，此類問題為難解問題，如漢諾塔問題，TSP問題等3.計算理論非確定性是一種技術(shù)表達，指可以猜測到正確答案并在多項式時間內(nèi)驗證經(jīng)驗表明，驗證某個解要比求出某個解容易比如大整數(shù)的因式分解問題，如果求9938550的兩個因數(shù)是比較困難的但若有人很幸運的猜出并告訴你這兩個數(shù)是1123和8850時，為了判斷這個猜想是否正確，你可以很容易的用最簡單的計算器進行驗證對于難解的問題，不可能每次都能幸運的猜到正確解，不知道是否存在一個多項式時間的算法，每次都能解決該問題37難解問題之求解思想弄清問題困難的根源后，可能會做某些改動，使問題變得容易解決；求問題的一個并不完美的解，在某些情況下，尋找問題的近似最優(yōu)解會相對容易一些。面對難解的問題時往往可以有若干選擇3.計算理論比如，課程表的安排必須滿足一些限制（如兩個班不能在同一時間同一教室上課等）如果有1000個班需要排課，即使用一臺超級計算機，也可能需要花費若干世紀的時間才能制定出一份最好的課程表。38經(jīng)典NP類問題-TSP問題物流配送問題歸結(jié)為帶時間窗的TSP；汽車生產(chǎn)線上汽車涂色問題對應為非對稱TSP。TSP問題一直是算法分析與設計領(lǐng)域的一個重要研究內(nèi)容，也是研究算法時經(jīng)常采用的一個經(jīng)典實例。3.計算理論現(xiàn)實世界中很多問題最終都可以歸結(jié)為TSP問題，應用領(lǐng)域遍及傳統(tǒng)的物理、化學、計算機科學、機器人、集成電路布線、工件排序、生產(chǎn)調(diào)度等科技、管理和社會生活等諸多領(lǐng)域。比如：39TSP問題描述TSP問題又稱旅行商問題：一位商人要去n個城市推銷貨物，所有城市走一遍后再回到起點，如何事先確定一條最佳線路，使其旅行費用最少。3.計算理論假設有A、B、C、D四個城市，城市間距離如圖所示：共有多少可能路徑？ABCD224466ABCDA路徑長：4+6+4+6=20ABDCA路徑長：4+2+4+2=12ACBDA路徑長：2+6+2+6=16ACDBA路徑長：2+4+2+4=12ADBCA路徑長：6+2+6+2=16ADCBA路徑長：6+4+6+4=2040旅行商問題求解分析若城市數(shù)為n，則組合路徑數(shù)為(n-1)!3.計算理論隨著城市數(shù)目的不斷加大，組合路線數(shù)將呈指數(shù)級規(guī)律急速增長，以致無法計算，即所謂組合爆炸問題如有20個城市，組合路徑數(shù)為：（20-1）!≈1.216*1017若按計算機以每秒1000萬條路線的速度計算：需386年??！41旅行商問題求解方法（續(xù)）3.計算理論TSP問題屬于NP類問題，本質(zhì)上難以求解，雖然無法找到其有效算法，但在實際應用中必須解決，常采用的方法如精確算法，如割平面法、分支定界法、動態(tài)規(guī)劃法等，此類方法能求解的問題規(guī)模較小，實用性較差；啟發(fā)式算法（或近似算法），如插入算法、最近鄰算法、CW算法等智能算法，如遺傳算法、模擬退火算法、蟻群算法等近些年出現(xiàn)了機器學習算法42計算復雜性與加密技術(shù)3.計算理論可計算性理論與計算復雜性理論密切相關(guān)，前者把問題分成可解和不可解的；后者則是把問題分成容易計算和難以計算的。受計算復雜性理論直接影響的一個應用領(lǐng)域是密碼技術(shù)。在絕大多數(shù)領(lǐng)域中，選擇容易計算的問題比選擇難計算的問題更可取，因為容易問題的求解代價更小。密碼技術(shù)則與眾不同，它特別需要難計算的問題，從而加大密碼被破解的難度，公開密鑰密碼系統(tǒng)RSA就是一個典型的例子。43RSA非對稱加密算法3.計算理論RSA是最著名、使用最廣泛的一種公鑰加密算法，1977年由RonRivest、AdiShamirh和LenAdleman在麻省理工開發(fā)，RSA取名來自于三人名字的首字母，已被ISO推薦為公鑰數(shù)據(jù)加密標準RSA算法基于一個十分簡單的數(shù)論事實：將兩個大素數(shù)相乘十分容易，但想要對其乘積進行因式分解卻極其困難，因此可以將乘積公開作為加密密鑰公開密鑰密碼系統(tǒng)采用的是非對稱的加密方法，其加密和解密過程采用不同的密鑰，加密密鑰用于加密，是公開的，稱為公鑰；解密密鑰用于解密，只有所有者知道，是不公開的，稱為私鑰公鑰和私鑰之間一一對應，用公鑰加密的信息只能用相應的私鑰解密，反之亦然，想由一個密鑰推知另一個密鑰，在計算上是不可行的44阿姆達爾定律3.計算理論在國王的婚姻故事中，國王在第一次采用順序的求解方法失敗后，第二次采用了并行方法求得答案并求婚成功對于難解性問題，人們可能就會產(chǎn)生這樣的疑問：順序算法解決不了的問題是否可以用并行算法求解？求解速度能否伴隨處理器數(shù)目的增加而不斷提高，從而使難解性問題得以解決？阿姆達爾定律是計算機系統(tǒng)設計的重要定量原理之一，于1967年由IBM360系列機的主要設計者阿姆達爾提出。阿姆達爾定律是指系統(tǒng)中對某一部件采用更快執(zhí)行方式所能獲得的系統(tǒng)性能改進程度，取決于這種執(zhí)行方式被使用的頻率，或所占總執(zhí)行時間的比例。45阿姆達爾定律-續(xù)3.計算理論對于并行系統(tǒng)，阿姆達爾給出了如下結(jié)論：設S為固定負載情況下描述并行處理效果的加速比，f為串行計算部分所占比例，a為并行計算部分所占比例，n為并行處理結(jié)點個數(shù)，則有S≤1/(1-a+a/n)設a=99%，n→∞，則f=1%，由公式計算可得S=100這說明在并行計算機系統(tǒng)中即使有無窮多個處理器，若串行操作占全部操作的1%，則其解題速度與單處理器的計算機相比最多只能提高100倍當將一個問題分解到多個處理器上求解時，因算法中不可避免地存在必須串行執(zhí)行的操作，從而極大限制了并行計算機系統(tǒng)的加速能力因此，對難解性問題而言，單純提高計算機系統(tǒng)的速度遠遠不夠，降低算法復雜度的數(shù)量級才是最關(guān)鍵的問題。新編計算機導論謝謝觀看46計算思維新編計算機導論導讀被稱為“20世紀最聰明的人”的愛因斯坦曾經(jīng)說過：想象力比知識更重要，要是沒有能獨立思考和獨立創(chuàng)造能力的人，社會的向上發(fā)展就會不可想象。懶于思考，不愿意鉆研和深入理解，自滿或滿足于微不足道的知識，都是智力缺乏的原因，這種缺乏用一個詞語來概括，就是“愚昧”。人是因為思維而降生的，所以一刻也不能停止思維。48計算思維概述01計算思維應用舉例03計算思維與傳統(tǒng)思維02本章CAPACITY內(nèi)容491.計算思維概述50為何學習計算思維計算機科學不僅提供一種科技工具、一套知識體系，更重要的是提供了一種從信息變換角度有效定義、分析和解決問題的思維方式，即作為計算機科學主線的計算思維。計算思維是計算時代的產(chǎn)物，是相關(guān)學者在審視計算機科學所蘊含的思想和方法時被挖掘出來的。隨著計算機應用的全面普及，計算思維成為人們認識和解決問題的重要思維方式之一，與理論思維和實驗思維并肩。圖靈獎得主迪杰斯特拉曾在1972年說過：“我們所使用的工具影響著我們的思維方式和思維習慣，從而也深刻地影響我們的思維能力”，這就是著名的“工具影響思維”的論點。從計算機科學到計算思維51科學思維主要分三大類理論源于數(shù)學，理論思維支撐著所有的學科領(lǐng)域。正如數(shù)學一樣，定義是理論思維的靈魂，定理和證明則是它的精髓。公理化方法是最重要的理論思維方法。理論思維：以數(shù)學為基礎實驗思維：以物理等學科為基礎計算思維：以計算機科學為基礎實驗思維的先驅(qū)首推意大利著名的物理學家、天文學家和數(shù)學家伽利略，他開創(chuàng)了以實驗為基礎，具有嚴密邏輯理論體系的近代科學，被人們譽為“近代科學之父”。計算思維又叫構(gòu)造性思維，以設計與構(gòu)造為特征。具體而言，可以說，計算思維是通過約簡、嵌入、轉(zhuǎn)化和仿真等方法，把一個看來困難的問題重新闡釋成一個我們知道問題怎樣解決的思維方法；計算思維又可以認為是一種遞歸思維，是一種并行思維，是一種……1.計算思維概述52計算思維的概念計算思維是運用計算機科學的基礎概念進行問題求解、系統(tǒng)設計以及人類行為理解等一系列思維活動的統(tǒng)稱。計算思維直面機器智能的不解之謎，即：什么問題人類能比計算機做得更好？什么問題計算機能比人類做得更好？它涉及這樣的問題，即什么是可計算的？此處“計算”是廣義的計算，它提出了面向問題解決的一系列觀點和方法，當人們在處理諸如問題求解、系統(tǒng)設計等方面的問題并對其進行描述與規(guī)劃時都會涉及計算思維。2006年3月，美國卡內(nèi)基梅隆大學的計算機科學家周以真教授（JeannetteM.Wing）在美國計算機權(quán)威期刊ACM通信（CommunicationsoftheACM）上發(fā)表名為“計算思維”（ComputationalThinking）的文章。周以真卡內(nèi)基梅隆1.計算思維概述53圖靈獎獲得者理查德?卡普（RichardM.Karp）的觀點自然問題和社會問題自身就蘊含豐富的屬于計算的演化規(guī)律，這些演化規(guī)律伴隨著物質(zhì)、能量以及信息的變換。正確提取這些信息變換，并通過恰當?shù)姆绞奖磉_出來，使之成為利用計算機處理的形式，這就是基于計算思維概念解決自然和社會問題的基本原理和方法論。1935年生于波士頓，1955年在哈佛大學獲文學學士學位，1956年獲理科碩士學位，之后進入哈佛大學計算實驗室攻讀博士，于1959年取得應用數(shù)學博士學位。

現(xiàn)任美國加州大學伯克利分校計算機科學講座教授，美國科學院、美國工程院、美國藝術(shù)與科學院、歐洲科學院院士。因其在計算機科學領(lǐng)域的基礎貢獻，曾獲圖靈獎、馮諾依曼獎、美國國家科學勛章、哈佛大學百年獎章等獎項，擔任美國科學院會刊（PNAS）等多個國際著名刊物編委。抽象：算法思維角度合理抽象，高效算法自動：工程思維角度合理建模，高效實施自動抽象1.計算思維概述55計算思維的本質(zhì)抽象就是對事物的性質(zhì)、狀態(tài)及其變化過程（規(guī)律）進行符號化描述，只保留某些重要特征以便于計算處理復雜問題。計算思維中抽象的最終目的是能夠機械地一步步自動執(zhí)行，計算工具基于某種方法自動執(zhí)行問題的求解過程，即計算思維的自動化特征。計算思維建立在計算工具的能力和限制之上，由人控制機器自動執(zhí)行。計算思維的本質(zhì)是抽象（abstract）和自動化（automation），它反映了計算的根本問題，即什么能被有效地自動執(zhí)行。1.計算思維概述56計算思維的本質(zhì)計算思維中的抽象超越了物理的時空觀，可以完全用符號表示除數(shù)學抽象外，計算思維涉及的數(shù)據(jù)類型和計算更加復雜，比如，用數(shù)字表示文本、聲音、圖形、圖像等。計算思維中的抽象可以劃分為不同層次，人們可以根據(jù)抽象的不同層次有選擇地忽視某些細節(jié)，最終控制系統(tǒng)的復雜性如，外賣平臺騎手的定位與電商平臺網(wǎng)購時快件物流追蹤的位置顯示微信發(fā)送消息時普通用戶無需掌握網(wǎng)絡傳輸知識抽象自動化為確保機械地自動化，需在抽象過程中進行精確、嚴格的符號標記和建模，同時要求計算機系統(tǒng)或軟件系統(tǒng)生產(chǎn)商能夠提供各種不同抽象層次之間的翻譯工具。1.計算思維概述57國際教育技術(shù)協(xié)會（ISTE）和計算機科學教師協(xié)會（CSTA）在2011年給計算思維下了一個可操作性定義形式化問題，并能夠借助計算機和其他工具解決問題；合理組織和分析數(shù)據(jù)；通過抽象（如模型、仿真等）的方式呈現(xiàn)數(shù)據(jù)；通過算法（一系列有序步驟）思想支持自動化的解決方案；分析可能的方案，找到最有效的方案，并有效應用這些方案和資源；將該問題的求解過程進行推廣，并移植到更廣泛的問題中。即計算思維是一個包含如下特征的問題解決過程1.計算思維概述58計算思維的核心思維并非一個伴隨計算機的出現(xiàn)而產(chǎn)生的概念，其思想早在中國古代數(shù)學中就有體現(xiàn)，只不過由周以真教授進行了清晰化和系統(tǒng)化。如，中國古代學者認為，當一個問題能夠在算盤上解算的時候，這個問題就是可解的，這就是中國的“算法化”思想中科院院士吳文俊圍繞幾何定理的證明展開研究，開拓了一個在國際上被稱為“吳方法”的新領(lǐng)域—數(shù)學的機械化領(lǐng)域，即把邏輯推理問題轉(zhuǎn)換為計算問題，用計算機證明幾何定理。計算思維的核心是解決問題的思維與能力1.計算思維概述59計算思維的特征計算思維是概念化，而非程序化。計算機科學不等于計算機編程，像計算機科學家一樣思考不僅僅意味著能夠給計算機編程，它需要在多個抽象層次上進行思考計算思維是能力，而非刻板的技能計算思維是分析和解決問題的能力，而非單純學習某種軟件的使用這樣一種刻板的、機械的重復計算思維是人類求解問題的一條途徑，但絕非試圖使人類像計算機那樣思考，計算思維具有如下6個特征1.計算思維概述60計算思維的特征（續(xù)1）計算思維是人的思維，而非計算機的思維。計算思維是人類求解問題的一種重要方法，而非讓人像計算機那樣思考AlphaGo戰(zhàn)勝著名圍棋大師并不意味著機器能夠思維，而是人類賦予了機器“人的思維”計算思維是數(shù)學和工程思維的互補與融合計算機科學在本質(zhì)上源自數(shù)學思維，其形式化基礎構(gòu)筑于數(shù)學之上計算機科學又源自工程思維，因為人們建造的是能夠與現(xiàn)實世界互動的系統(tǒng)，由于受底層計算設備和應用場景的限制，計算思維比數(shù)學思維更加具體，更加受限計算機科學家必須從計算角度思考，而不能僅考慮數(shù)學性思考1.計算思維概述61計算思維的特征（續(xù)2）計算思維是思想，而非人造品。計算思維不僅以軟件、硬件等人造物品的形式呈現(xiàn)并時刻影響人們的生活，更重要的是計算概念，這種概念能用于問題求解、日常生活管理、與他人交流互動等與計算相關(guān)的多種場景計算思維面向所有人，所有地方當計算思維真正融入人類活動，成為人人都掌握，處處被使用的問題求解工具，且不再表現(xiàn)為一種顯式哲學時，就成為一種人類特有的思想2.計算思維與傳統(tǒng)思維62計算思維與其他思維的關(guān)系綜合看來，計算思維就是在計算機科學的基礎上定義、理解和解決問題。計算思維建立在計算過程的能力和限制之上，這是計算思維區(qū)別于其他思維方式的一個重要特征，在用計算機解決問題時要遵循的基本原則是既要充分利用計算機的計算和存儲能力，又不能超出計算機的能力范圍計算思維在實踐中共用了算法思維、編程思維、數(shù)學思維和工程思維，如右圖63算法思維算法思維（AlgorithmicThinking）是計算思維的核心概念之一，是理解計算機科學的關(guān)鍵，與構(gòu)建和理解算法的指令有關(guān)，包括：功能分解、重復（迭代和/或遞歸）、基本數(shù)據(jù)組織（記錄、數(shù)組、列表）、泛化和參數(shù)化算法和程序，自頂向下的設計和細化算法思維就是能清楚說明問題解決的方法能夠?qū)⒁粋€復雜問題轉(zhuǎn)化為若干子問題并進一步簡化，以達到解決問題的目的算法思維還能夠明確并分析問題解決方法的優(yōu)劣，能夠設計與構(gòu)造操作步驟更少、更經(jīng)濟的算法。2.計算思維與傳統(tǒng)思維64編程思維編程思維（Programming/CodingThinking）是以程序的方式來思考，簡單來說，就是從發(fā)現(xiàn)問題到解決問題的思維過程，由分解思維、抽象思維、模式識別、算法執(zhí)行4個步驟構(gòu)成分解思維將一個大問題分解為若干更容易解決的小問題，即把復雜問題簡單化模式識別簡單來說就是找到事物規(guī)律，找出不同問題中的相似模式，制定規(guī)則以舉一反三解決更一般的問題編寫程序是培養(yǎng)計算思維最重要的手段，編程思維包括框架思維、拆解思維、函數(shù)思維等。2.計算思維與傳統(tǒng)思維65數(shù)學思維數(shù)學思維（MathematicalThinking）是一種看待事物的方式，即把事物分解成數(shù)字、結(jié)構(gòu)或邏輯的本質(zhì)，并分析其潛在的模式，其最大的認知特征是概念化、抽象化、模式化在解決問題時強調(diào)定義和概念，明確問題條件，把握其中的函數(shù)關(guān)系，通過抽象、歸納、推導和證明，將概念和定義、數(shù)學模型、計算方法等與現(xiàn)實事物建立聯(lián)系計算思維吸收了數(shù)學思維的部分理論和方法用以解決問題，如抽象化、模式化等數(shù)學思維所形成的解決方案可以單純依靠人的大腦實現(xiàn)，而經(jīng)過計算思維形成的解決方案，大都可以借助計算工具，通過機器的“自動執(zhí)行”實現(xiàn)。2.計算思維與傳統(tǒng)思維66工程思維工程思維（EngineeringThinking）是在工程的設計和研究中形成的思維，是運用各種知識解決工程實踐問題的核心工程思維最大的特點就是要在時間、成本、質(zhì)量等約束條件下“把事情做成”，即“交付可靠、可用的成果”相比較而言，“科學思維”是認識規(guī)律、發(fā)現(xiàn)規(guī)則，不關(guān)注于實際應用；工程思維就是要“腳踏實地”，將科學家發(fā)現(xiàn)的原理轉(zhuǎn)化并實際應用；從解決問題的視角，計算思維可以說是工程思維的一個組成部分，但計算思維強調(diào)的是在計算機科學基礎上的問題解決2.計算思維與傳統(tǒng)思維3.計算思維應用舉例七橋問題在18世紀初普魯士的哥尼斯堡城，有一條河穿過，河上有兩個小島，有七座橋把兩個島與河岸聯(lián)系起來，如圖所示。當?shù)鼐用裣矚g散步，并提出這樣一個問題：一個步行者怎樣操作才能不重復、不遺漏地一次走完七座橋，最后返回起點？但是任何人也沒有找到這樣一條理想的路徑3.計算思維應用舉例68七橋問題保留問題最本質(zhì)的部分，忽略如橋的長度、寬度等非本質(zhì)部分，將陸地抽象為點，橋抽象為線，從而把問題歸結(jié)為如圖所示的簡單的點和線連接的一筆畫問題，即能否從某一點開始，一筆不重復地畫出此圖形，最后回到出發(fā)點。歐拉證明了上述走法是不存在的，其本質(zhì)原因在于，圖中每個點所關(guān)聯(lián)的都是奇數(shù)條邊。歐拉給出了連通圖可以一筆畫的充要條件是：幾何圖中的奇點(與奇數(shù)條邊相連的點)個數(shù)為0或2。圖論奠基人，瑞士數(shù)學家歐拉（Euler，1707-1783）在1736年對七橋問題進行了解答七橋問題是對問題進行抽象處理的典型實例，如何抽象、忽略哪些信息、保留哪些信息是根據(jù)問題決定的歐拉3.計算思維應用舉例69四色問題用數(shù)學語言表示，就是將平面任意細分為不相重疊的區(qū)域，每一個區(qū)域總可以用1、2、3、4這四個數(shù)字之一來標記，且不會使相鄰的兩個區(qū)域得到相同的數(shù)字。四色問題是公認的數(shù)學難題，與哥德巴赫猜想、費馬大定理一起被稱為世界三大著名數(shù)學難題。1976年6月，美國伊利諾伊大學兩位數(shù)學家阿佩爾（Appel）與哈肯（Haken）憑借計算機“不畏重復不懼枯燥”、快速高效的優(yōu)勢，利用兩臺計算機，耗費將近1200小時，驗證了100多億個邏輯判斷，終于完成了四色定理的證明。四色問題又稱四色猜想、四色定理，由英國一位大學生于1852年提出。四色問題要求證明，在平面地圖上只用四種顏色就可以使任何復雜形狀的各塊相鄰區(qū)域間顏色不會重復，也就是說，相互之間都有交界的區(qū)域最多只能有四塊。3.計算思維應用舉例70計算思維與其它學科生物信息學是伴隨人類基因組計劃發(fā)展起來的新興交叉學科，是由生物學、計算機科學、數(shù)學和統(tǒng)計學等多學科交叉融合而形成的一門綜合學科，其實質(zhì)是利用計算機技術(shù)分析和處理不同類型的生物分子數(shù)據(jù)，以發(fā)掘數(shù)據(jù)中蘊涵的生物學意義。研究重點主要體現(xiàn)在基因組學和蛋白質(zhì)組學兩方面，研究內(nèi)容大致包括三個方面：新算法和統(tǒng)計學方法研究；各類數(shù)據(jù)的分析和解釋；研制有效利用和管理數(shù)據(jù)的新工具比如利用計算機模擬細胞間蛋白質(zhì)的交換，發(fā)現(xiàn)控制西紅柿大小的基因與人體癌癥的控制基因具有相似性?！镄畔W（Bioinformatics）在計算分子生物學中，DNA是所有生命體的遺傳基礎，DNA長鏈中包含許多基因，利用逆序和移位兩種操作對DNA中的基因組進行重排列，找出不同物種間的差異和進化距離，對于生物進化樹和進化圖譜的構(gòu)造具有極其重要的意義。該問題可歸結(jié)為一個組合優(yōu)化問題，即找出從一個基因組序列到另一個基因組序列，通過逆序和移位操作進行重排列的最少操作步數(shù)，該操作步數(shù)被稱為兩個基因組序列所代表的生物物種之間的進化距離。3.計算思維應用舉例71計算思維與其它學科建立在化學、數(shù)學、計算機科學等多學科基礎上的交叉學科，主要是通過對化學信息進行表示、管理、分析、模擬和傳播，以實現(xiàn)化學信息的提取、轉(zhuǎn)化與共享，揭示化學信息的實質(zhì)與內(nèi)在聯(lián)系?；瘜W信息學的本質(zhì)就是將信息學方法、計算機及網(wǎng)絡技術(shù)等應用于化學等學科的相關(guān)研究之中，其主要內(nèi)容涉及化學信息的獲取與表達、管理與傳播，并在此基礎上進行化學信息的分析與挖掘，進而實現(xiàn)化學學科的知識創(chuàng)新。例如，在化工領(lǐng)域，用來對反應條件進行優(yōu)化和篩選催化劑等，這主要是通過對實驗數(shù)據(jù)進行建模，然后使用該預測模型實現(xiàn)對實驗工作的指導；在藥物設計領(lǐng)域，用來進行分子模擬、虛擬合成、構(gòu)效關(guān)系分析、虛擬篩選等如何根據(jù)某一復雜過程的測試數(shù)據(jù)，建立數(shù)學模型、預測化學反應效果、預報化合物性質(zhì)……化學信息學（cheminformatics）3.計算思維應用舉例72計算思維與其它學科經(jīng)濟學為人類生產(chǎn)、分配、消費行為等提供了分析方法，輔助人們進行預測和決策。而計算機科學則告訴人們?nèi)绾卧O計、分析、運行各種算法，使人們從大規(guī)模復雜計算中解脫出來。計算經(jīng)濟學是經(jīng)濟學的一個重要分支，是計算機科學和經(jīng)濟學的交叉學科。比如，在互聯(lián)網(wǎng)經(jīng)濟中，對互聯(lián)網(wǎng)廣告的生產(chǎn)、分配以及消費的分析與設計是一個重要課題，計算廣告學研究如何高效、精確地將廣告通過面向大眾的互聯(lián)網(wǎng)服務傳遞至受眾，并以廣告收入來支撐互聯(lián)網(wǎng)公司，甚至獲取巨大的利潤基于機器學習對用戶行為進行分析，學習最優(yōu)廣告競價策略，設計最優(yōu)的廣告拍賣機制在電力市場，隨著智能電表的普及，針對用戶用電曲線，基于人工智能用戶畫像實現(xiàn)市場定價等…計算經(jīng)濟學（ComputationalEconomics）3.計算思維應用舉例73計算思維與其它學科又稱數(shù)字人文（DigitalHumanities）是針對計算與人文學科之間的交叉領(lǐng)域進行研究、學習以及創(chuàng)新的一門學科。人文計算以數(shù)據(jù)為研究的基本素材，研究過程涉及統(tǒng)計學、計算機科學、語言學、圖書情報學、人文科學等諸多學科領(lǐng)域。比如，有學者以貝葉斯公式為理論依據(jù)來統(tǒng)計單詞出現(xiàn)頻次，通過詞與詞之間的依存關(guān)系實現(xiàn)了美國歷史上地位崇高的、中小學生的必讀書《聯(lián)邦黨人文集》的作者識別新西蘭學者將生物信息計算的概率推理模型引入語言發(fā)源研究，通過量化考察語言的變化時間和空間上的表現(xiàn)，成功推斷出印歐語系起源的地理位置等。人文計算（Humanities）3.計算思維應用舉例74計算思維與其它學科DIKW模型是一個關(guān)于數(shù)據(jù)（Data）、信息（Information）、知識（Knowledge）、智慧（Wisdom）的模型，它描述了人類認知的金字塔等級，其中，數(shù)據(jù)處于最基礎的地位，信息、知識和智慧都可以與數(shù)據(jù)關(guān)聯(lián)起來。關(guān)聯(lián)思維和計算思維相結(jié)合，可以使藝術(shù)中的關(guān)聯(lián)思維用算法表示，并進一步體現(xiàn)在人工智能藝術(shù)以及情感計算等方面。比如，美劇《紙牌屋》的出品公司Netflix在制作電視劇時，通過大數(shù)據(jù)對色彩的分析來“測量客戶之間的差別”，進而幫助公司分析客戶對不同色彩、情節(jié)、人物和故事的偏好GoogleDeepdream程序、清華“道子”程序可以生成油畫和中國畫作品等。文化和藝術(shù)小結(jié)75計算思維并不是僅僅為計算機編程，而是在多個層次上抽象的思維，是一種以有序編碼、機械執(zhí)行和有效可行方式解決問題的模式計算思維是一項根本能力，是每一個人在現(xiàn)代社會中必須掌握的計算思維是以信息的獲取和有效計算，進行算法求解、系統(tǒng)構(gòu)建、自然與人類行為理解為主要特征，實現(xiàn)認知世界和解決問題的思想與方法計算思維不僅僅是計算機科學家解決問題的思想方法，也是所有科學家在使用計算時所具有的思維模式，它的關(guān)鍵是計算模型，而在物理學、生物學等不同的學科里，計算模型具有不同的形式和性質(zhì)僅就計算而言，傳統(tǒng)的物理學主要依賴于確定的和非確定的計算模型，人工智能主要依賴各種學習模型，社會科學則更多使用統(tǒng)計計算模型新編計算機導論謝謝觀看76新編計算機導論計算的基礎1計算機與二進制數(shù)據(jù)的概念01邏輯代數(shù)03為何采用二進制02二進制與問題求解04本節(jié)CAPACITY內(nèi)容數(shù)據(jù)的概念數(shù)據(jù)的基本概念信息人通過接受信息來認識事物，從這個意義上說，信息是一種知識，是接受者原來不了解的知識數(shù)據(jù)數(shù)據(jù)是信息的載體，信息在計算機內(nèi)部具體的表示形式就是數(shù)據(jù)。信息是有意義的，而數(shù)據(jù)則沒有。數(shù)值、文字、語言、圖形、圖像等都是不同形式的數(shù)據(jù)數(shù)據(jù)的基本概念數(shù)據(jù)分類數(shù)據(jù)在計算機中都是以二進制表示、存儲和處理的。計算機中數(shù)據(jù)數(shù)值型數(shù)據(jù)非數(shù)值型數(shù)據(jù)字符漢字多媒體信息圖形圖像動畫音頻視頻超文本數(shù)據(jù)的概念為何采用二進制二進制易于物理實現(xiàn)只需表示“0”和“1”兩個狀態(tài)，如晶體管通為“1”，截止為“0”；高電壓為“1”，低電壓為“0”；機器可靠性使用二進制數(shù)只有兩個狀態(tài)，數(shù)字的傳輸和處理不容易出錯運算簡單二進制的運算法則比較簡單，使得計算機的運算器結(jié)構(gòu)簡單，控制簡單通用性強只有0和1兩個數(shù)，可以代表邏輯代數(shù)中的“真”和“假”，因而邏輯代數(shù)成為計算機設計的數(shù)學基礎為何采用二進制基本的容量單位位（bit）位是計算機存儲數(shù)據(jù)的最小單位。一個二進制位只能表示0或1兩種狀態(tài)，每個0或1就是一個位。字節(jié)（Byte）字節(jié)是計算機數(shù)據(jù)存儲和處理的最常用的基本單位，簡記為B。規(guī)定一個字節(jié)為8位，即1B=8bit，每個字節(jié)由8個二進制位組成。計算機的存儲器通常是以多少字節(jié)來表示容量。為何采用二進制基本的容量單位字（Word）在計算機中，作為一個整體來處理或運算的一串數(shù)碼，稱為一個計算機字，簡稱字。一個字通常由一個或若干個字節(jié)組成。計算機一次能直接處理的二進制數(shù)據(jù)的位數(shù)稱為字長。為何采用二進制基本的容量單位衡量數(shù)據(jù)容量的單位KB，千字節(jié)，簡稱K，1KB=210B=1024BMB，兆字節(jié)，簡稱M，1MB=210KB=220BGB，吉字節(jié)，簡稱G，1GB=210MB=230BTB，太字節(jié)，簡稱T，1TB=210GB=240BPB，拍字節(jié)，簡稱P，1PB=210TB=250BEB，艾字節(jié)，簡稱E，1EB=210PB=260BZB，澤字節(jié)，簡稱Z，1ZB=210EB=270BYB，堯字節(jié)，簡稱Y，1YB=210ZB=280B邏輯代數(shù)起源于19世紀初，又稱布爾代數(shù)，由19世紀英國數(shù)學家喬治·布爾創(chuàng)立邏輯代數(shù)是實現(xiàn)邏輯運算的數(shù)學工具

用來表達事物和演算間的邏輯關(guān)系，只有兩個值，即“真”和“假”常用于邏輯線路的設計以及程序設計中條件的描述等是計算機的理論基礎，也是計算機實現(xiàn)控制的基本理論依據(jù)在邏輯代數(shù)中，有與、或、非三種基本邏輯運算邏輯代數(shù)邏輯常量與變量邏輯常量只有兩個，即0和1，用來表示兩個對立的邏輯狀態(tài)。邏輯變量與普通代數(shù)一樣，也可以用字母、符號、數(shù)字及其組合來表示但它們之間有著本質(zhì)區(qū)別，因為邏輯常量的取值只有兩個，即0和1，而沒有中間值。邏輯代數(shù)基本邏輯關(guān)系與：當決定一事件的所有條件都具備時，事件才發(fā)生邏輯變量與普通代數(shù)一樣，也可以用字母、符號、數(shù)字及其組合來表示但它們之間有著本質(zhì)區(qū)別，因為邏輯常量的取值只有兩個，即0和1，而沒有中間值。邏輯代數(shù)邏輯與運算（and）與運算可用&表示1&1=1，0&1=0，1&0=0，0&0=0，同時為1，結(jié)果為1，任意一方為0，則結(jié)果為0。邏輯或運算（or）與運算可用|表示1|1=1，0|1=1，1|0=1，0|0=0，同時為0，結(jié)果為0，任意一方為1，則結(jié)果為1。邏輯非運算（not）與運算可用!表示!1=0，!0=1邏輯運算二進制與問題求解趣味故事：小白鼠驗毒有1000瓶水，其中一瓶是有毒的，小白鼠只要嘗一點帶毒的水，24小時內(nèi)就會死亡，問：至少需要多少只小白鼠才能在24小時內(nèi)檢驗出哪瓶水有毒?如何檢驗？二進制與問題求解求解思路若將1000瓶水從0~999逐一編號，假設第997瓶水有毒，哪瓶有毒？用十進制編碼很難看出如何求解因每瓶水存在有毒或無毒兩種狀態(tài)，可以用0表示無毒，1表示有毒，考慮采用二進制求解將每瓶水的編號由十進制轉(zhuǎn)換為二進制，則需要10位二進制數(shù)如何讓小白鼠試毒？小白鼠喝了毒水后可能很快死亡，也可能在接近24小時的時候死亡，考慮時間因素，不能一只只的試驗是否需要10只小白鼠？二進制與問題求解求解方法每瓶水的編號都由10位二進制數(shù)構(gòu)成，其編碼為B9B8B7B6B5B4B3B2B1B0十只小白鼠編號分別為M9，M8，M7，M6，M5，M4，M3，M2，M1，M0，制定下述規(guī)則：對于任一瓶水，若編碼Bi為1，則讓編號為Mi的小白鼠喝一口，否則不讓小白鼠Mi喝1000瓶水均按上述規(guī)則處理，24小時后觀察二進制與問題求解求解方法若小白鼠Mi死了，則Mi=1，否則Mi=0，將十只小白鼠的狀態(tài)值相連，即可得出有毒水瓶的二進制編號將編號轉(zhuǎn)換為10進制，即可得知幾號瓶中的水有毒二進制與問題求解求解方法比如現(xiàn)在是第997瓶水有毒，其編號為1111100101（B9B8B7B6B5B4B3B2B1B0）；編號M9

，M8

，M7

，M6

，M5

，M2

，M0的小白鼠喝第997瓶水；編號M4

，M3

，M1的小白鼠不喝第997瓶水；將小白鼠狀態(tài)相連，編號M9

，M8

，M7

，M6

，M5

，M2

，M0的小白鼠健康狀況出現(xiàn)問題；編號M4

，M3

，M1的小白鼠正常，依題則有M9M8M7M6M5M4M3M2M1M0=1111100101；將編號轉(zhuǎn)為10進制，可知第997瓶水有毒。二進制與問題求解求解方法比如現(xiàn)在是第2瓶水有毒，其編號為0000000010（B9B8B7B6B5B4B3B2B1B0）；編號M2的小白鼠喝第2瓶水；M9

，

M8

，

M7

，

M6

，

M5

，

M4

，

M3

，

M1

，

M0的小白鼠不喝第2瓶水；將小白鼠狀態(tài)相連，依題則有M9M8M7M6M5M4M3M2M1M0=0000000010；將編號轉(zhuǎn)為10進制，可知第2瓶水有毒。二進制與問題求解總結(jié)小白鼠問題的求解運用了二進制思維，它可以將很多事物（或狀態(tài)）巧妙地統(tǒng)一起來比如0和1可以表示為有毒與無毒、喝與不喝、死與不死，對同一串0和1可以有不同的解讀，比如：000010，可以是編號為000010（第2瓶）的水瓶000010，第i位對應第i只小白鼠，1表示喝，0表示不喝000010，第i位對應第i只小白鼠，1表示死，0表示不死新編計算機導論謝謝觀看新編計算機導論計算的基礎2數(shù)制的表示與轉(zhuǎn)換（上）數(shù)制01數(shù)制之間的轉(zhuǎn)換03數(shù)制的表示02本節(jié)CAPACITY內(nèi)容數(shù)制數(shù)制數(shù)制也稱為進位計數(shù)制，是指用一組固定的符號和統(tǒng)一的規(guī)則來表示數(shù)值的方法。基數(shù)表示每種數(shù)值所需要的數(shù)碼個數(shù)稱為該數(shù)制的基數(shù)?；鶖?shù)簡稱“基”或“底”,常用字母R(radix)表示。如十進制數(shù)制，可用“0，1，2，…，9”，10個符號來表示，基數(shù)為10，即R=10。位權(quán)一個數(shù)碼處在不同位置所代表的值不同。每個數(shù)碼所表示的數(shù)值等于該數(shù)碼乘以一個與數(shù)碼所在位置相關(guān)的常數(shù)，這個常數(shù)叫做位權(quán)?；颍阂环N數(shù)制中某一位上的“1”所表示的數(shù)值大小位權(quán)的大?。阂曰鶖?shù)為底、數(shù)碼所在位置的序號為指數(shù)的整數(shù)次冪。數(shù)制按位展開

例如：219=2×102+1×101+9×100可將任意數(shù)制的數(shù)K表示為如下通式：

數(shù)制數(shù)制的表示常用的數(shù)制表示方法常用的數(shù)制十進制——符合人們習慣。二進制——計算機內(nèi)部表示和存儲數(shù)據(jù)，便于物理實現(xiàn)。十六進制、八進制——便于書寫，可以與二進制進行轉(zhuǎn)換。下標法字符法數(shù)制的表示下標法用小括號將要表示的數(shù)括起來，然后在右括號外的右下角寫上數(shù)制的基數(shù)R。一般用（）角標表示不同進制的數(shù)據(jù)。如：十進制數(shù)用（）10表示，二進制數(shù)用（）2表示（1056.78）10，表示1056.78是十進制數(shù)（756）8，表示756是八進制數(shù)（1101.0101）2，表示1101.0101是二進制數(shù)數(shù)制的表示字母法在計算機中，在數(shù)字后加字母表示不同進制數(shù)據(jù)。其中：B(binary)—二進制

D(decimal)—十進制（D可省略）O(octonary)—八進制(有的地方用Q)H(hexadecimal)—十六進制如：1011.01B，678O，156D數(shù)制的表示幾種進位計數(shù)制的表示和運算規(guī)則進位計數(shù)制的表示方法

對于任意的R進制數(shù)：

位置計數(shù)法：（N）R=an-1an-2…a1a0.a-1…a-m

按權(quán)展開法：

（N）R=an-1×Rn-1+an-2×Rn-2+… +a1×R1+a0×R0+a-1×R-1+…+a-m×R-m

(其中n為整數(shù)位數(shù)，m為小數(shù)位數(shù)，R為基數(shù))數(shù)制進位計數(shù)制的表示方法

如，十進制：

（34958.34）10=3×104+4×103+9×102+

5×101+8×100+3×10-1+4×10-2

如：二進制：

（100101.01）2=1×25+0×24+0×23+ 1×22+0×21+1×20+0×2-1+1×2-2數(shù)制數(shù)制之間的轉(zhuǎn)換加減運算規(guī)則對于任意的R進制數(shù)逢R進一（進位原則）借一當R（借位原則）數(shù)制之間的轉(zhuǎn)換運算規(guī)則二進制加法

0+0=0，0+1=1，1+0=1，1+1=10(逢二進一)二進制減法

0-0=0，1-0=1，1-1=0，0-1=1(借一當二)

不夠減時，需要向高位借位，借位后有10-1=1二進制乘法

0×0=0，0×1=0，1×0=0，1×1=1二進制除法

0÷0（無意義），0÷1=0，1÷0（無意義），1÷1=1數(shù)制之間的轉(zhuǎn)換運算規(guī)則例1求（10011.01）2

＋（100011.11）2

＝？10011.01100011.11````＋）0.0111011（110111）2數(shù)制之間的轉(zhuǎn)換運算規(guī)則例2求（10110.01）2

－（1100.10）2

＝？10110.011100.10```

－）1.1001（1001.11）21數(shù)制之間的轉(zhuǎn)換運算規(guī)則例3求（1101.01）2×（110.11）2

＝？1101.01110.11×）（1011001.0111）21101011101010000001

101011101011011001.0111數(shù)制之間的轉(zhuǎn)換運算規(guī)則例4求（1101.1）2÷（110）2

＝？（10.01）21101

.1011010.01-110110-1

100數(shù)制之間的轉(zhuǎn)換R進制轉(zhuǎn)十進制方法：相應位置的數(shù)碼乘以對應位的權(quán)值，再將所有的乘積進行累加，即得對應的十進制數(shù)。[例]求(1001.101)2的十進制數(shù)值。解：(1001.101)2=1×23+0×22+0×21+

1×20+1×2-1+0×2-2+1×2-3

=8+1+0.5+0.125=(9.625)10[例]求(653)8對應的十進制數(shù)值？(653)8＝6×82＋5×81＋3×80＝384＋40＋3＝427數(shù)制之間的轉(zhuǎn)換十進制轉(zhuǎn)二進制整數(shù)部分的轉(zhuǎn)換

----除2取余法小數(shù)部分的轉(zhuǎn)換----乘2取整法數(shù)制之間的轉(zhuǎn)換十進制整數(shù)轉(zhuǎn)二進制整數(shù)—除2取余法用2多次除被轉(zhuǎn)換的十進制數(shù)至商為0，每次所得余數(shù)構(gòu)成相應二進制數(shù)，第一個余數(shù)是最低位，最后一個余數(shù)是最高位。數(shù)制之間的轉(zhuǎn)換十進制整數(shù)轉(zhuǎn)二進制整數(shù)例5求(19)10的二進制數(shù)值。解:

因此，(19)10=(10011)2222221942101........1........0........0........1........余數(shù)低位高位9117數(shù)制之間的轉(zhuǎn)換十進制小數(shù)轉(zhuǎn)二進制小數(shù)—乘2取整法用2多次乘被轉(zhuǎn)換的十進制數(shù)的小數(shù)部分，所得乘積的整數(shù)部分變?yōu)閷亩M制數(shù)。第一次所得整數(shù)為最高位，其次為次高位，最后一次為最低位。至乘積為0。數(shù)制之間的轉(zhuǎn)換十進制小數(shù)轉(zhuǎn)二進制小數(shù)例6求(0.6875)10的二進制數(shù)值。解:因此，(0.6875)10=(0.1011)2

數(shù)制之間的轉(zhuǎn)換十進制小數(shù)轉(zhuǎn)二進制小數(shù)—乘2取整法十進制小數(shù)轉(zhuǎn)換為二進制小數(shù)過程中，有時會出現(xiàn)乘積的小數(shù)部分總不等于0的情況，或者出現(xiàn)循環(huán)小數(shù)的情況。如：(0.2)10

=(0.001100110011…)2

這樣的情況下，乘2過程的結(jié)束由所要求的轉(zhuǎn)換精度確定。一般當要求二進制數(shù)取m位小數(shù)時，可求出m+1位，然后對最低位作0舍1入處理。數(shù)制之間的轉(zhuǎn)換十進制小數(shù)轉(zhuǎn)二進制小數(shù)例7求(0.323)10的二進制數(shù)值。（保留4位小數(shù)）解:1.2920.6460.323×2×20.5841.168×2×20.336×2高位低位因此，(0.323)10=(0.0101)2

數(shù)制之間的轉(zhuǎn)換十進制小數(shù)轉(zhuǎn)二進制小數(shù)例8求(237.652)10的二進制數(shù)值。（保留4位小數(shù)）解:則，(237.625)10=(11101101.101)2

整數(shù)除2取余10110111591182372914731222222220小數(shù)乘2取整0.6251.2500.250.501.0×2×2×2101數(shù)制之間的轉(zhuǎn)換十進制轉(zhuǎn)換為R進制數(shù)整數(shù)部分:除R取余法,即整數(shù)部分不斷除以R取余數(shù)，直到商為0為止。最先得到的余數(shù)為最低位，最后得到的為最高位。又稱為“除R反向取余法”.小數(shù)部分:乘R取整法，首先不斷地對前次得到的積的小數(shù)部分乘R并列出該次得到的整數(shù)數(shù)值，直到小數(shù)部分乘積為0或者達到有效精度為止，最先得到的整數(shù)為小數(shù)部分的最高位（最靠近小數(shù)點），最后得到的整數(shù)為最低位

新編計算機導論謝謝觀看計算機科學導論計算的基礎2數(shù)制的表示與轉(zhuǎn)換（下）數(shù)制01數(shù)制之間的轉(zhuǎn)換03數(shù)制的表示02本節(jié)CAPACITY內(nèi)容數(shù)制之間的轉(zhuǎn)換二進制與R進制間的轉(zhuǎn)換把二進制轉(zhuǎn)換為八進制數(shù)時，只需將整數(shù)部分自右向左，小數(shù)部分自左向右分別按每三位為一組，不足三位用0補齊，用相應的八進制數(shù)寫出。反之，把八進制數(shù)轉(zhuǎn)換為二進制數(shù)，只要把每位八進制數(shù)用對應的三位二進制數(shù)表示。二進制數(shù)與十六進制數(shù)的轉(zhuǎn)換同二進制與八進制轉(zhuǎn)換相似，只是按四位進行分組。數(shù)制之間的轉(zhuǎn)換二進制與八進制間的轉(zhuǎn)換例9將（1101101.10101）2轉(zhuǎn)換為八進制數(shù)。000~0001~1010~2011~3100~4101~5110~6111~7二進制數(shù)：

001

101

101.101

010155

.52八進制數(shù)：所以(1101101.10101)2

＝(155.52)8數(shù)制之間的轉(zhuǎn)換八進制與二進制間的轉(zhuǎn)換例10將八進制數(shù)（345.64）8轉(zhuǎn)換為二進制數(shù)。八進制數(shù)：3

4

5.6

4011二進制數(shù)：100101

.110100000~0001~1010~2011~3100~4101~5110~6111~7所以(345.64)2

＝(11100101.1101)2數(shù)制之間的轉(zhuǎn)換二進制與十六進制間的轉(zhuǎn)換轉(zhuǎn)換原則：每四位二進制對應一位十六進制數(shù)。二進制轉(zhuǎn)十六進制：“四位一并”法方法：從小數(shù)點開始分別往兩邊，整數(shù)部分自右向左，小數(shù)部分自左向右，按每四位為一組，不足四位用0補齊，每組用相應的十六進制數(shù)寫出。十六進制轉(zhuǎn)二進制：“一分為四”法方法：每位十六進制數(shù)用四位二進制數(shù)代替。數(shù)制之間的轉(zhuǎn)換二進制與十六進制間的轉(zhuǎn)換例11將（1101101.10101）2轉(zhuǎn)換為16進制數(shù)。0000~00001~10010~20011~30100~40101~50110~60111~71000~81001~91010~A1011~B1100~C1101~D1110~E1111~F所以(1101101.10101)2

＝(6D.A8)16二進制數(shù)：

0110

1101.1010

10006十六進制數(shù)：D

.A8數(shù)制之間的轉(zhuǎn)換十六進制與二進制間的轉(zhuǎn)換例12將十六進制數(shù)（A9D.6C）16轉(zhuǎn)換為二進制數(shù)。所以(A9D.6C)2

＝(101010011101.011011)2十六進制數(shù)：A

9

D.6

C1010二進制數(shù)：10011101

.011011000000~00001~10010~20011~30100~40101~50110~60111~71000~81001~91010~A1011~B1100~C1101~D1110~E1111~F數(shù)制之間的轉(zhuǎn)換十進制與二進制、八進制、十六進制之間的轉(zhuǎn)換十進制數(shù)二進制數(shù)八進制數(shù)十六進制數(shù)000011112102231133410044510155611066711177數(shù)制之間的轉(zhuǎn)換二進制與十進制、八進制、十六進制之間的轉(zhuǎn)換十進制數(shù)二進制數(shù)八進制數(shù)十六進制數(shù)81000

10891001

119101010

12A（10）111011

13B（11）121100

14C（12）131101

15D（13）141110

16E（14）151111

17F（15）數(shù)制之間的轉(zhuǎn)換課后練習將（75.453）10轉(zhuǎn)換為二進制數(shù)（取4位小數(shù)）將（152.32）10轉(zhuǎn)換為八進制數(shù)（取3位小數(shù)）將（237.45）10轉(zhuǎn)換為十六進制數(shù)（取3位小數(shù)）新編計算機導論謝謝觀看計算機科學導論計算的基礎3數(shù)值型數(shù)據(jù)的表示（上）無符號數(shù)01定點數(shù)與浮點數(shù)03有符號數(shù)02本節(jié)CAPACITY內(nèi)容導言計算機編碼把信息編成二進制數(shù)碼的方法，稱為計算機的編碼。數(shù)值數(shù)據(jù)和字符等其它數(shù)據(jù)需采用不同的編碼方式。在計算機中參與運算的數(shù)有兩大類：無符號數(shù)和有符號數(shù)。無符號數(shù)無符號數(shù)是指沒有符號的數(shù)，即非負整數(shù)。機器字長中的全部數(shù)位均用來表示整數(shù)值的大小，相當于數(shù)的絕對值。無符號數(shù)的表示范圍：字長為n位的無符號數(shù)的表示范圍是0~（2n-1）如機器字長為16位，則無符號數(shù)的表示范圍是0~（216-1），即0~65535無符號數(shù)有符號數(shù)據(jù)的表示日常，我們在絕對值前面加“+”、“-”符號來表示有符號數(shù)。在計算機中，有符號數(shù)中的正負號及小數(shù)中的小數(shù)點都以二進制形式表示。有符號數(shù)數(shù)的符號數(shù)值化在計算機中，有符號數(shù)的符號同樣用0和1表示。在計算機中，數(shù)的最高位定義為符號位，用“0”表示正數(shù)，用“1”表示負數(shù)。機器數(shù)和真值連同符號位一起數(shù)值化了的數(shù)，稱為機器數(shù),能被計算機識別的數(shù)稱為機器數(shù)。把機器數(shù)所表示的真實數(shù)值稱為機器數(shù)的真值。真值是正、負號加某進制數(shù)絕對值的形式。一般的，機器數(shù)與真值之間存在著一一對應的關(guān)系。有符號數(shù)機器數(shù)和真值【例】有符號數(shù)真值機器數(shù)+52